Размещено на http://www.allbest.ru/

АНАЛИЗ ПРОГРАММНЫХ ПРОДУКТОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Головачева М.И.

студент магистратуры 2 курса

Институт энергетики и автоматизированных систем

Магнитогорский государственный

технический университет им. Г.И. Носова

Российская Федерация, г. Магнитогорск

Аннотация

В статье дана характеристика программных продуктов, позволяющих решать задачи линейного программирования. Также были выявлены преимущества и недостатки каждого из них. На основе проведенного анализа было отмечено наиболее подходящее программное обеспечение для решения такого рода задач.

Ключевые слова: задача линейного программирования, MicrosoftExcel, MATLAB, IOSONM, многокритериальная оптимизация.

Abstract

Golovacheva M.I.

graduate student

2 course, Power Engineering and Automated Systems Institute

Nosov Magnitogorsk State Technical University

Russian Federation, Magnitogorsk

ANALYSIS OF LINEAR PROGRAMMING PROBLEM SOLVING SOFTWARE

In this article the characteristic of linear programming problem solving software is given. Also, the advantages and disadvantages of each of them have been identified. Based on the analysis, it was noted the most appropriate software to solve such problems.

Keywords: linear programming problem, Microsoft Excel, MATLAB, IOSO NM, multicriteria optimization.

На настоящий момент на рынке программного обеспечения представлен широкий ряд программных продуктов, которые могут решать математические задачи различного рода, в том числе и задачи линейного программирования (ЗЛП). Так как научная работа автора связанна с решением именно таких задач [1], то необходимо определить оптимальное по стоимости программное обеспечение, которое имеет наибольшее количество инструментов, позволяющих решать ЗЛП.

Одним из самых распространенных программных продуктов является Microsoft Excel, он предоставляет возможность не только работать с электронными таблицами, но и решать математические, финансовые, экономические, логические и оптимизационные задачи.

Решить ЗЛП можно с помощью надстройки «Поиск решения». Данный инструмент помогает найти решение задачи за счет изменения значений целевых ячеек. Целевые ячейки представляют собой целевые функции, которые можно минимизировать, максимизировать либо указать некоторое целевое значение. Задача решается посредством регулировки входных критериев (ограничений), которые назначает пользователь. Поиск решения использует нелинейный метод обобщенного понижающего градиента, а также симплекс-метод и эволюционный поиск решения. Базовая версия Microsoft Excel имеет ограничение на максимальное количество параметров: количество неизвестных - 200, количество формульных ограничений на неизвестные - 100, количество предельных условий на неизвестные - 400 [2]. Однако, практика показывает, что при приведении постановки задачи к реальным условиям, сильно возрастает размерность задачи и Excel не всегда может найти оптимальное решение. Также MicrosoftExcel не позволяет записывать двойные неравенства, поэтому каждое двойное неравенство необходимо разбивать на два, что доставляет дополнительные неудобства. Средствами MicrosoftExcel можно решать только однокритериальные задачи линейного программирования.

Помимо надстроек в MicrosoftExcel есть встроенный язык Visual Basic for Applications, с помощью которого можно программно реализовать другие алгоритмы для решения ЗЛП. Также программный продукт Microsoft Excel хорошо документирован, что позволяет самостоятельно решать поставленные задачи.

Данный программный продукт возможно приобрести в составе MicrosoftOffice 2016 за 5199 руб., либо MicrosoftOffice 365 за 269 руб. в месяц (год 2699 руб.) [3].

Таким образом, MicrosoftExcel имеет следующие преимущества:

- встроенный язык программирования;

- широкая функциональность;

- наличие трех методов оптимизации;

- возможность решать задачи средней размерности;

- простота использования;

- представление входных данных и результата в виде таблиц;

- наличие встроенной системы помощи в интерфейсе пользователя.

Несмотря на большое количество преимуществ, у MicrosoftExcel есть три существенных недостатка:

- задачи большой размерности не всегда поддаются оптимизации;

- отсутствие возможности указывать неравенства с двойными ограничениями;

- высокая стоимость.

На ряду с MicrosoftExcel существует большое количество других программных продуктов, позволяющих решать сложные математические задачи, одним из таких программных продуктов является MATLAB.

MATLAB - это высокоуровневый язык и интерактивная среда для программирования, численных расчетов и визуализации результатов. С помощью MATLAB можно анализировать данные, разрабатывать алгоритмы, создавать модели и приложения [4].

MATLAB обладает большим количеством встроенных математических функций, которые позволяют использовать различные подходы к решению задач, а также сократить время на нахождение решения.

Для решения ЗЛП в MATLAB необходимо использовать функцию linprog из пакета расширения OptimizationToolbox, предназначенного для решения ЗЛП вида:

,

где f - вектор коэффициентов целевой функции, x - оптимальный план задачи, A - матрица ограничений-неравенств, b - вектор правых частей ограничений-неравенств, Aeq - матрица ограничений-равенств, beq - матрица ограничений-равенств, lb, ub - вектора, ограничивающие план xснизу и сверху соответственно [5].

Для решения ЗЛП необходимо написать программу на языке MATLABc использованием данной функции. С помощью входного параметра options можно выбрать способ решения ЗЛП: крупно-масштабный метод оптимизации (interior-point-legacy), метод внутренней точки (interior-point) либо двойственный симплекс-метод (dual-simplex) [6]. Алгоритм внутренней точки используется по умолчанию. Функция linprog позволяет только минимизировать целевую функцию, чтобы найти максимум необходимо изменить знаки в матрице f.

MATLAB позволяет решать задачи среднего масштаба со следующей размерностью: количество неизвестных - более 1000, количество линейных равенств с нижними границами по всем переменным - более 500 и с верхними границами - более 400. Однако в студенческих версиях размерность задачи ограничивается 300 неизвестными и ограничениями. Также эффективность решения зависит от характера конкретной задачи. Документация к MATLAB представлена на английском языке.

Пакет Optimization Toolbox позволяет решать многокритериальные задачи в MATLAB. Для решения задач многокритериальной оптимизации есть две формулировки:

- задача «стремление к цели» предполагает уменьшение значения линейной или нелинейной вектор-функции для достижения значений, заданных в целевом векторе. Относительная значимость целевых значений определяется с использованием весового вектора. Задача стремления к цели может также иметь линейные и нелинейные ограничения.

- минимаксная задача включает минимизацию функции многих переменных, соответствующих самому худшему значению, возможны линейные и нелинейные ограничения.

Оба типа многокритериальных задач OptimizationToolbox преобразует к стандартной задаче условной оптимизации, а затем решает ее с помощью active-set подхода [7].

Стоимость студенческой версии MATLAB с OptimizationToolbox составляется 3240 руб. (54$), обычная версия стоит 6600 руб. (110$).

Итак, MATLAB имеет следующие достоинства:

- наличие большого количества математических функций;

- возможность решать задачи линейного программирования среднего масштаба;

- встроенный язык программирования;

- возможность решать многокритериальные задачи;

- наличие трех методов оптимизации;

- возможность задавать двойные неравенства.

Вместе с тем, у MATLAB есть свои недостатки:

- относительно высокая стоимость;

- ограничение на размерность задачи в зависимости от версии;

- отсутствие документации на русском языке;

- необходимость изучения встроенного языка;

- сложность освоения.

Также существуют специальные программные продукты, позволяющие решать многокритериальные оптимизационные задачи.

IOSONM - программный комплекс, предназначенный для повышения эффективности сложных технических систем на основе многокритериальной и многопараметрической оптимизации проектных параметров.

Данный программный комплекс позволяет решать задачи размерностью до 100 переменных, 20 критериев и 100 ограничений и хорошо подходит для решения реальных производственных задач [8]. IOSONM обладает возможностью интеграции с другими программными продуктами, такими как Excel, Mathcad и т.д. Процедуры оптимизации «тяжелых» задач можно распараллеливать, что существенно сокращает время, необходимое для их решения. программирование задача линейный matlab

В IOSONM есть пошаговое руководство на русском языке по решению оптимизационных задач. Решение задачи включает 8 шагов:

- постановка задачи;

- создание математической модели;

- создание проекта оптимизационного исследования;

- настройка проекта;

- проверка правильности настройки проекта;

- настройка задачи оптимизации;

- запуск задачи оптимизации;

- анализ результатов.

Математическая модель задачи должна отражать существенные свойства объекта и быть реализована в виде исполняемого файла. Алгоритм для решения задачи выбирается автоматически в зависимости от топологии целевой функции. В IOSONM можно задать необходимую точность решения, точность соблюдения ограничений, предельное время работы и желаемое количество Парето-оптимальных решений (для многокритериальных задач). Полученный результат можно представить в виде таблицы, диаграммы либо таблицы и диаграмм одновременно.

Для студентов выпускных курсов и аспирантов программный комплекс предоставляется без оплаты лицензии.

Преимущества программы IOSONM:

- возможность решать многокритериальные задачи;

- достаточно большая размерность многокритериальных задач;

- автоматический подбор метода решения задачи;

- возможность распараллеливания процедур оптимизации;

- представление результатов в различном виде;

- предоставление программного комплекса студентам и аспирантам без оплаты лицензии.

Также можно отметить некоторые недостатки:

- необходимость представления математической модели в виде исполняемого файла;

- необходимость обучения работы с программным комплексом.

Таким образом, было проанализировано три программных продукта, позволяющих решать задачи линейного программирования. Среди них можно выделить программный комплекс IOSONM, который позволяет решать многокритериальные оптимизационные задачи большой размерности (до 20 критериев), что является главным достоинством по сравнению с другими программными продуктами. Также IOSONM предоставляется бесплатно для студентов и аспирантов, что также является неоспоримым преимуществом при выборе программного обеспечения. Однако нельзя не отметить тот факт, что для использования данного программного комплекса необходимо пройти обучение, так как в нем отсутствует интуитивно-понятный интерфейс. Кроме того, представление математической модели должно быть реализовано в виде исполняемого файла, для создания которого требуется написание программного кода. Проанализировав достоинства и недостатки рассмотренных программных продуктов, автор данной статьи пришел к выводу о необходимости создания собственного программного обеспечения для оптимизации состава агломерационной шихты, учитывающего эти недостатки. Тем не менее, программный продукт, созданный автором статьи, не сможет обладать такой же универсальностью и широкой функциональностью, как у IOSO NM.

Использованные источники

1. Головачева М.И. К проблеме оптимизации состава шихтовых материалов для производства агломерата / М.И. Головачева, Е.Г. Филиппов // Інформатика, управління та штучний інтелект. Матеріали третьої міжнародної науково-технічної конференції студентів, магістрів та аспірантів. - Х.: НТУ "ХПІ", 2016. - 90 с.

2. Технические характеристики и ограничения MicrosoftExcel [Электронный ресурс]. (дата обращения 02.02.2017).

3. Сравнение наборов приложений Office [Электронный ресурс]. (дата обращения 02.02.2017).

4. MATLAB [Электронный ресурс]. (дата обращения 01.02.2017).

5. Сергеев А.Н. Решение задач линейного программирования в среде MATLAB / А.Н. Сергеев, Н.А. Соловьёва, Е. К. Чернэуцану // Семинар по дискретному гармоническому анализу и геометрическому моделированию DHA & CAGD [Электронный ресурс]. (дата обращения 29.12.2016).

6. Linprog. MATLAB [Электронный ресурс]. (дата обращения 03.02.2017).

7. OptimizationToolbox. Решение стандартных и больших задач оптимизации [Электронный ресурс]. (дата обращения 01.02.2017).

8. Программный комплекс IOSONM [Электронный ресурс]. (дата обращения 02.02.2017).

Размещено на Allbest.ru