Программы для решения задач линейного программирования
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .Проиллюстрируем этот факт графически:
F(x) → min | F(x) → max |
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.
Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.
Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является Python.
Постановка задачи
В публикациях [1,2] рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.
Однако известно [3], что каждой задаче линейного программирования соответствует так называемая выделенная(двойственная)задача. В ней по сравнению с прямой задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума — максимум). Задача, двойственная к двойственной — эта сама исходная задача.
Решение двойственной задачи очень важно для анализа использования ресурсов. В данной публикации будет доказано, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной).
Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.
Решение прямой задачи о оптимальной производственной программе
Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub — вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с — вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.
Функция цели
maxF(x)=c×x
Ограничения
A×x≤b
Численные значения переменных:
N=5; m=4; b_ub = [700,250,600,400]; A_ub = [[1,2,3,2,4], [5,4,3,2,1], [3,4,2,5,3],[4,2,5,3,1]]; c = [25, 35,25,40,30].
Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1
Особенности решения с библиотекой scipy. optimize
Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.
Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.
Результаты решения задачи
nit 3
status 0
message Optimization terminated successfully.
success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x [700.0, 250.0, 600.0, 309.09090909090912]
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]
- Найден оптимальный план по видам продукции [0.0 0. 0 18.182 22.727 150. 0]
- Найдено фактическое использование ресурсов [700.0, 250.0, 600.0, 309.091]
- Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
- Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack
Решение двойственной задачи о оптимальной производственной программе
Четвёртый вид ресурса в прямой задаче использована не полностью. Тогда ценность этого ресурса для предприятия оказывается более низкой по сравнению с ресурсами, ограничивающими выпуск продукции, и предприятие готово заплатить более высокую цену за приобретение ресурсов, позволяющих увеличить прибыль.
Введём новое назначение искомой переменной x как некоторой «теневой» цены, определяющей ценность данного ресурса в отношении прибыли от реализации выпускаемой продукции.
Далее для сравнительного анализа частично сохраним ранее принятые обозначения, но с новым содержанием:
c – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.
Функция цели
minF(x)=c×x
Ограничения
A_ub_T ×x≥ b_ub
Численные значения и соотношения для переменных:
с = [700,250,600,400]; A_ub_T transpose(A_ub); b_ub = [25, 35,25,40,30].
Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.
Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).
Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True
Выводы
Третий вид ресурсов имеет наибольшую ценность для производителя поэтому данный вид ресурсов должен быть закуплен в первую очередь, затем первый и второй вид. Четвёртый вид ресурса имеет для производителя нулевую ценность и закупается последним.
Недавно появилась необходимость создать с нуля программу, реализующую алгоритм симплекс-метода. Но в ходе решения я столкнулся с проблемой: в интернете не так уж много ресурсов, на которых можно посмотреть подробный теоретический разбор алгоритма (его обоснование: почему мы делаем те или иные шаги) и советы по практической реализации — непосредственно, алгоритм. Тогда я дал себе обещание — как только завершу задачу, напишу свой пост на эту тему. Об этом, собственно, и поговорим.
Замечание. Пост будет написан достаточно формальным языком, но будет снабжен комментариями, которые должны внести некоторую ясность. Такой формат позволит сохранить научный подход и при этом, возможно, поможет некоторым в изучении данного вопроса.
§1. Постановка задачи линейного программирования
Определение: Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n- мерного пространства, задаваемых системами линейными уравнений и неравенств.
Общая задача линейного программирования (далее – ЛП) имеет вид:
§2. Каноническая форма задачи ЛП
Каноническая форма задачи ЛП:
Замечание: Любая задача ЛП сводится к канонической.
Алгоритм перехода от произвольной задачи ЛП к канонической форме:
- Неравенства с отрицательными умножаем на (-1).
- Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
- Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
- Делаем замену переменных:
- Если , то
- Если — любой, то , где
§3. Угловые точки. Базисные/свободные переменные. Базисные решения
Определение: Точка называется угловой точкой, если представление возможно только при .
Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит (т.е. – не внутренняя точка).
Графический способ решения задачи ЛП показывает, что нахождение оптимального решения ассоциируется с угловой точкой. Это является основной концепцией при разработке симплекс-метода.
§4. Симплекс-метод
Симплекс-метод позволяет эффективно найти оптимальное решение, избегая простой перебор всех возможных угловых точек. Основной принцип метода: вычисления начинаются с какого-то «стартового» базисного решения, а затем ведется поиск решений, «улучшающих» значение целевой функции. Это возможно только в том случае, если возрастание какой-то переменной приведет к увеличению значения функционала.
Необходимые условия для применения симплекс-метода:
- Задача должна иметь каноническую форму.
- У задачи должен быть явно выделенный базис.
Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.
Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:
- В первой строке указывают «наименование» всех переменных.
- В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
- В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
- Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
- Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.
Замечание: Если ограничения в исходной задаче представлены неравенствами вида ≤, то при приведении задачи к канонической форме, введенные дополнительные переменные образуют начальное базисное решение.
Замечание: Коэффициенты в строке функционала берутся со знаком “-”.
Алгоритм симплекс-метода:
1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:
- Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
- Если задача на максимум – выбираем минимальный отрицательный.
Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.
Определение: Столбец симплекс-таблицы, отвечающий выбранному коэффициенту, называется ведущим столбцом.
2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:
- Вектор правых частей почленно делится на ведущий столбец
- Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)
Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.
3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.
Определение: Такой элемент называется ведущим элементом.
4. Вместо исключаемой переменной в первом столбце (с названиями базисных переменных) записываем название переменной, которую мы вводим в базис.
5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.
- Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
- Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка
6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.
§5. Интерпретация результата работы симплекс-метода
1. Оптимальность
Условие оптимальности полученного решения:
- Если задача на максимум – в строке функционала нет отрицательных коэффициентов (т.е. при любом изменении переменных значение итогового функционала расти не будет).
- Если задача на минимум – в строке функционала нет положительных коэффициентов (т.е. при любом изменении переменных значение итогового функционала уменьшаться не будет).
Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:
При выборе ведущей строки (исключаемой переменной) результат почленного деления вектора правых частей на ведущий столбец содержит только нулевые и отрицательные значения.
Фактически, это значит, что какой бы рост мы не задавали новой базисной переменной, мы никогда не найдем новую вершину. А значит, наша функция не ограничена на множестве допустимых решений.
3. Альтернативные решения
При нахождении оптимального решения возможен еще один вариант – есть альтернативные решения (другая угловая точка, дающая то же самое значение функционала).
Алгебраический признак существования альтернативы:
После достижения оптимального решения имеются нулевые коэффициенты при свободных переменных в строке функционала.
Это значит, что при росте соответствующей переменной с нулевым коэффициентом значение функционала не изменится и новое базисное решение будет также давать оптимум функционала.
Эпилог
Данная статья направлена на более глубокое понимание теоретической части. В замечаниях и пояснениях здесь можно получить ответы на вопросы, которые обычно опускают при изучении этого метода и принимают априори. Однако, надо понимать, что многие методы численной оптимизации основаны на симплекс-методе (например, метод Гомори, М-Метод) и без фундаментального понимания вряд ли получится сильно продвинуться в дальнейшем изучении и применении всех алгоритмов этого класса.
Чуть позже напишу статью о практической реализации симплекс-метода, а также несколько статей о Методе искусственных переменных (М-Метод), Методе Гомори и Методе ветвей и границ.
Спасибо за внимание!
Сегодня мы попытаемся ответить на вопрос « Какое программное обеспечение лучше всего подходит для линейного программирования? «Ну, линейное программирование (ЛП), как правило, требует много времени. Это, возможно, причина, почему разработчикам программного обеспечения для линейного программирования потребовалась целая вечность.
Но, похоже, все, наконец, повернуло за угол, если что-то не заставит долго ждать появления какого-то сверхмощного программного обеспечения для линейного программирования.
Используя надежные основы моделирования, эти программы способны минимизировать или максимизировать линейные ограничения с учетом некоторых линейных равенств и / или неравенств для получения оптимизированных решений.
И их удивительные способности делают их любимыми для профессионалов исследования операций.
Как работает программное обеспечение для линейного программирования
Программное обеспечение LP включает в себя структуры, которые зависят от традиционных алгоритмов линейного программирования, таких как симплекс и архитектура поддержки.
Это, плюс варианты других математических методов, позволяют быстро и эффективно решать задачи оптимизации.
Некоторые применяют традиционный подход Excel Solver, а другие используют тактику моделирования для решения сложных задач линейного программирования.
Итак, что такое лучшее программное обеспечение для линейного программирования?
Мы постараемся ответить на этот вопрос в этом руководстве. Прокрутите вниз, чтобы узнать, что является одним из наиболее рекомендуемых программ для линейного программирования на сегодняшний день.
Программное обеспечение для линейного программирования для Windows 10
Visual Math (Выбор редакции)
Движок Visual Math, узнаваемое приложение для множества компаний и отраслей, мгновенно превращает данные в умные решения.
Пользователи могут сначала заявить о своих самых сложных головоломках в виде математических моделей. Затем программное обеспечение автоматически просматривает миллиарды, а иногда и триллионы предлагаемых решений, чтобы выбрать лучшее.
Революционное программное обеспечение для линейного программирования также поставляется со всем необходимым, чтобы помочь провести тщательный анализ чувствительности по мере развертывания решения.
Здоровая библиотека Visual Math удобно подкреплена набором интуитивно понятных интерфейсов, позволяющих начинающим легко начать работу сразу после загрузки .
Поставщик также предоставляет отличную техническую поддержку при развертывании и возможном использовании.
Студенческие лицензии, как и ожидалось, субсидируются в размере 30 долларов США, в то время как бизнес- пользователи могут заплатить до 90 долларов США за доступ к выдающейся программе .
Gurobi
Короче говоря, Gurobi Optimizer — один из самых универсальных решений для оптимизации LP.
Частично причина в том, что код создан для использования параллелизма, так что пользователи могут в основном запускать разные наборы параллельного кода во время тестов решения.
Кроме того, их подпрограммы резки MIP (смешанно-целочисленное программирование) затмевают таковые у конкурирующих продуктов и помогают уловить ключевой дискретный характер различных решений.
Разработчики также вышли за рамки обычного и включили исключительно превосходные классы срезов, чтобы упростить моделирование.
Гладкая эвристика MIP этой программы часто дает решения наилучшего качества даже с проблемами, включающими десятки переменных решения.
Кроме того, его барьерные алгоритмы используют новейшую технологию компьютерной архитектуры, позволяющую поддерживать первоклассную производительность.
Наконец, его хорошо продуманные API-интерфейсы легки, современны и интуитивно понятны, а также сокращают время обучения новых пользователей в дополнение к повышению производительности.
GAMS (Общая алгебраическая система моделирования)
GAMS — это высокоуровневое программное обеспечение для линейного программирования для математической оптимизации, предназначенное для быстрого решения задач максимизации / минимизации.
Благодаря своей интерактивной платформе GAMS позволяет пользователям легко формулировать математические модели, почти аналогичные их математическим описаниям.
Адаптивная структура программ и их комплексные функции делают подачу данных и последующую постановку задачи проще простого.
Поэтому пользователи могут сосредоточиться на моделировании, которое само по себе довольно просто. Действительно, GAMS приступает к работе, как только узнает точные спецификации сущностей и существующие отношения, поэтому операторам это очень просто.
В результате разработчики моделей могут делать разные вещи сами, делая GAMS фаворитом настоящих экспертов в предметной области.
Программное обеспечение также имеет идеально сбалансированное сочетание процедурных и декларативных элементов, поэтому пользователи могут реализовывать сложные методы декомпозиции. Это делает его очень актуальным для моделей, занимающихся необычными проблемами, которые могут вызвать проблемы с производительностью.
GAMS имеет два прайс-листа: один для академических и коммерческих пользователей .
— Примечание редактора. Если вас интересует другое программное обеспечение для проектирования, ознакомьтесь с нашей обширной коллекцией руководств .
CPLEX
Студия линейного программирования ILOG CPLEX (от IBM) предоставляет один из самых быстрых способов построения моделей оптимизации, ориентированных на бизнес, и поддерживает решения для широкого спектра общих проблем планирования и планирования .
Он имеет описательный язык моделирования, полностью интегрированную среду разработки и множество встроенных инструментов, так что он является мастером всего процесса разработки модели.
Построенные модели обычно не зависят от применяемых данных, а это означает, что пользователям не нужно изменять код модели при работе с различными экземплярами проблемы.
Можно также комбинировать переменные решения и различные элементы данных для определения расширенных выражений, целевых функций или ограничений.
CPLEX также выделяется своей современной функциональностью и мощным механизмом оптимизации, который очень помогает при анализе указанных результатов.
Он даже доступен для тех, кто испытывает трудности с использованием указывающих устройств, таких как мышь, благодаря сочетанию клавиш для различных процессов и задач.
Коммерческая цена кажется немного высокой, но есть бесплатная пробная версия .
жаргон
LINGO — еще один комплексный инструмент, разработанный для быстрого создания и решения моделей оптимизации.
Как и CPLEX, LINGO представляет собой полезный пакет, включающий надежный язык для выражения практических моделей оптимизации, полнофункциональную среду для подачи и редактирования задач, а также быстрые встроенные решатели.
Последние версии включают некоторые заметные улучшения, такие как улучшенные симплексные решатели, чтобы ускорить преобразование линейных моделей.
Эта программа также довольно быстрая, даже когда трудно предсказать, какой из двойных, первичных или барьерных решателей даст самое быстрое решение.
Улучшенный многоядерный процессор также позволяет пользователям назначать отдельное ядро для каждого решателя и запускать их одновременно.
Есть также многостартовый решатель, который позволяет пользователям указывать целевые значения для текущей целевой функции.
Также заслуживают внимания новые функции диаграммы для лучшего представления результатов, включая сложенные вертикальные / горизонтальные столбцы и диаграммы Гранта.
В целом, приложение является верным выбором, если вы ищете программное обеспечение, которое может предоставить ответы в кратчайшие сроки.
Наше последнее слово о том, что является лучшим программным обеспечением для линейного программирования
На вопрос о том, что является лучшим программным обеспечением для линейного программирования, нет простого ответа. Вам нужно будет взглянуть на простоту развертывания, другие желаемые возможности, такие как совместимость с различными надстройками, поддержка поставщиков и тому подобное.
В целом, мы считаем, что Visual Math определенно находится в своей собственной лиге в том, что касается основных функций .
Другие варианты (Gurobi, cplex, GAMS и Lingo) также довольно популярны по-своему и являются отличными альтернативами.
В конечном счете, это может сводиться к вашим собственным предпочтениям и опыту.
СВЯЗАННЫЕ ИСТОРИИ:
Примечание редактора: этот пост был первоначально опубликован в ноябре 2018 года и с тех пор обновлен для свежести и точности.
Симплекс-метод - программа для решения задач линейного программирования симплекс-методом. Это приложение приводит задачу к каноническому виду и производит ее итеративное решение с помощью пересчета симплекс-таблицы. При этом выводится подробный отчет о ходе решения задачи. Всего имеется три режима решения задач: автоматический, пошаговый, ручной.
В автоматическом режиме инструмент сам выбирает разрешающий столбец и строку, которые обеспечивают максимальное возрастание или уменьшение целевой функции, а также автоматически пересчитывает все таблицы.
В пошаговом режиме каждая пересчитанная таблица выводится на экран, что удобно для просмотра промежуточных результатов решения задачи. В этом режиме разрешающий столбец и строку программа также выбирает сама.
В ручном режиме пользователь сам выбирает разрешающую строку и столбец.
Есть возможность экспорта в Excel всех таблиц, полученных в ходе решения задачи.
MathType - отличное приложение для работы с формулами, математическими выражениями и.
Advanced Grapher - Мощная и простая в использовании программа для построения графиков и их анализа.
Maxima — система компьютерной алгебры для работы с символьными и численными выражениями.
SMath Studio - бесплатная программа для вычисления математических выражений и построения.
Инженерный калькулятор - небольшая программа, в которой собраны наиболее важные функции для инженерных расчетов.
Крутое ПО, предлагающее широкий набор возможностей и функций (около 5000), охватывающих.
Отзывы о программе Симплекс-метод
Программа не всегда даёт правильный результат.
3*x1 + 1*x2 + 1*x3 + 0*x4 = 15
2*x1 + 0*x2 + 1*x3 + 1*x4 = 11
F(x) = 4*x1 - 1*x2 + 2*x3 + 0*x4 -> max
Получаем
x1 = 5
x2 = 0
x3 = 0
x4 = 1
Значение целевой функции: Fmax = 20
Правильный ответ: Fmax = 22
Результат получен в программе Sim.exe (Softodrom)
2 | 14 | Ответить
Читайте также: