Анализ программных продуктов для решения задач линейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

fT • x ^ min,

A - x

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

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

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

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

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

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

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

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

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

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

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

масштаба;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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