Решить уравнение по линейному программированию

Решение происходит в три этапа:

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

Видео:Графический метод решения задач линейного программирования | Высшая математика TutorOnlineСкачать

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).

Переменные x₁, …, x_m, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x_m+1,…, x_n) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных x_j≥0, что эквивалентно условию неотрицательности b_j≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел b_j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Видео:Cимплексный метод решения задачи линейного программирования (ЗЛП)Скачать

Калькулятор симплекс-метода

Видео:Графический метод решения задачи линейного программирования (ЗЛП)Скачать

Как пользоваться калькулятором

• Задайте количество переменных и ограничений
• Введите коэффициенты целевой функции
• Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
• Выберите тип решения
• Нажмите кнопку «Решить»

Видео:Прямая и двойственная задачи линейного программирования (ЗЛП)Скачать

Что умеет калькулятор симплекс-метода

• Решает основную задачу линейного программирования
• Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
• Работает с произвольным количеством переменных и ограничений

Видео:Двойственная задача линейного программирования (ЗЛП)Скачать

Что такое симплекс-метод

Задача линейного программирования — это задача поиска неотрицательных значений параметров, на которых заданная линейная функция достигает своего максимума или минимума при заданных линейных ограничениях.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.

Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c₁·x₁ + c₂·x₂ + . + c_n·x_n

Ограничение — условие вида a₁·x₁ + a₂·x₂ + . + a_n·x_n v b , где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x₁ . x_n.

Видео:Графический метод решения задачи линейного программирования.Скачать

Алгоритм решения основной задачи ЛП симплекс-методом

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

Чтобы привести ограничения с неравенствами к каноническому виду, для каждого ограничения вводят переменную, называемую дополнительной с коэффициентом 1. В ответе эти переменные учитываться не будут, однако сильно упростят начальные вычисления. При этом дополнительные переменные являются базисными, а потому могут быть использованы для формирования начального опорного решения.

Формирование начального базиса

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

Иначе необходимо выделить среди коэффициентов ограничений столбец, который участвует в формировании единичной матрицы в заданной строке (например, если требуется определить вторую базисную переменную, то необходимо искать столбец, в котором второе число равно 1, а остальные равны нулю). Если такой столбец найден, то переменная, соответствующая этому столбцу, становится базисной.

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

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₆
Столбец 4 является частью единичной матрицы. Переменная x₄ входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x₅ , предварительно разделив третью строку на 2.
Симплекс-таблица

После преобразования получаем следующую таблицу:

Если такой столбец отсутствует, то для формирования базиса необходимо применить исключение Гаусса для первого ненулевого столбца, который ещё не является базисным. Для этого вся строка делится на элемент в найденном столбце, а из остальных строк вычитается полученная строка, разделённая на значение, стоящее в этом же столбце. После этой операции все значения вне данной строки будут обнулены, и столбец можно будет считать базисным.

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x₅

Начальная симплекс-таблица

Для определения второй базисной переменной ищем первый ненулевой столбец, который ещё не является базисным. Первый столбец не нулевой и не является базисным. Выполняем исключение Гаусса: делим строку 2 на 4, а из первой и третьей строк вычитаем вторую, умноженную на соответствующий элемент в первом столбце.

После исключения получаем следующую таблицу:

После того как базис сформирован, нужно построить начальную симплекс-таблицу. Она строится следующим образом:

• Для удобства в первой строке можно записать коэффициенты C_i целевой функции (для дополнительных переменных эти коэффициенты равны нулю)
• Вторая строка формирует шапку таблицы. В ней первый столбец называется базис, а остальные перечисляют основные переменные x₁..x_n и дополнительные x_n+1..x_n+k
• Затем построчно перечисляются базисные переменные и коэффициенты ограничений

Схематично начальная таблица будет выглядеть примерно так:

Избавляемся от отрицательных свободных коэффициентов

После приведения к каноническому виду или после алгебраических преобразований при формировании базиса некоторые из свободных коэффициентов (b_i) могли стать отрицательными, что не позволяет перейти к дальнейшим вычислениям. Чтобы избавиться от отрицательных значений b необходимо:

• Найти строку, в которой находится максимальное по модулю значение b. Пусть это будет строка i;
• Найти максимальный по модулю элемент в этой строке. Пусть он находится в столбце j;
• Строку i разделить на элемент, стоящий на пересечении i-ой строки и j-го столбца;
• Из каждой оставшейся строки k вычесть строку i, умноженную на элемент строки k и столбца j;
• Переменную, соответствующую найденному столбцу j, сделать базисной (добавить в базис вместо переменной, находящейся в строке i).

Этот шаг необходимо повторять до тех пор, пока все отрицательные b не станут положительными или в строке не останется отрицательных элементов. Если строка с максимальным по модулю b_i не содержит отрицательных элементов, то такая задача не имеет решений и на этом алгоритм заканчивает свою работу. В противном случае все b_i положительны и алгоритм переходит к следующему этапу — расчёту дельт.

Для каждого ограничения с неравенством добавляем дополнительные переменные x₄..x₆.
Перепишем ограничения в каноническом виде:
— 4·x₁ — 3·x₂ — 2·x₃ + x₄ = -33
— 3·x₁ — 2·x₂ — x₃ + x₅ = -23
— x₁ — x₂ — 2·x₃ + x₆ = -12

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 2 содержит неравенство, базисной будет добавленная дополнительная переменная x₅
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x₆

Видео:СИМПЛЕКС МЕТОД: ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯСкачать

🐍 Линейное программирование. Практика решения задач оптимизации на Python

Видео:Решение задачи линейного программирования при помощи надстройки Поиск решенияСкачать

Leo Matyushkin

Данная публикация представляет собой сокращенный перевод руководства Мирко Стожилковича Hands-On Linear Programming: Optimization With Python. Для удобства читателей текст перевода также адаптирован в виде Jupyter-блокнота.

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

Экосистема Python включает несколько мощных инструментов линейного программирования. Из этого руководства вы узнаете:

• что такое линейное программирование и в чем его польза;
• какие инструменты Python подходят для линейного программирования;
• как построить модель и решить задачу линейного программирования на Python.

Видео:Уроки C++. Простые линейные уравненияСкачать

Что собой представляет линейное программирование

Системы линейных уравнений и неравенств часто имеют множество возможных решений.

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

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

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

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

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

Видео:Решение системы линейных уравнений графическим методом. 7 класс.Скачать

Линейное программирование на Python

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

Заметим, что почти все широко используемые библиотеки линейного программирования и смешанно-целочисленного линейного программирования написаны на языках Fortran, C или C++, так как линейное программирование требует интенсивной вычислительной работы с матрицами, часто очень большими. Соответствующие инструменты Python – это просто удобные интерфейсы для работы с низкоуровневыми библиотеками – солверами.

В этом руководстве для определения и решения задач линейного программирования мы будем использовать Python-библиотеки SciPy и PuLP.

Видео:Линейное программирование Часть 1. Постановка задачиСкачать

1. Примеры задач линейного программирования

Видео:Линейное программирование.Графический методСкачать

1.1. Небольшой показательный пример

Рассмотрим следующую задачу максимизации:

Нам нужно найти такие x и y , чтобы выполнялись «красное», «синее» и «желтое» неравенства, а также ограничения x ≥ 0 и y ≥ 0 . При этом решение должно соответствовать максимально возможному значению z .

Независимые переменные, которые нужно найти ( x и y ) называют переменными решения (decision variables). Функция, которую необходимо максимизировать или минимизировать ( z ), – это целевая функция (objective function), функция стоимости (cost function) или просто цель (goal). Неравенства (или уравнения), которым необходимо удовлетворять, называются ограничениями (inequality constraints или equality constraints для обычных уравнений).

Проблему можно визуализировать следующим образом.

2x + y = 20 , а красная область над ней показывает, где красное неравенство не выполняется. Аналогично синяя линия – это −4x + 5y = 10 , желтая линия – это −x + 2y = −2 , окрашенные области – та часть плоскости, где неравенство не выполняется.» data-src=»https://media.proglib.io/posts/2020/11/26/5a6c3e3ee24ae5a228d7a0ee4ea9fb8a.png» > Красная линия представляет функцию 2x + y = 20 , а красная область над ней показывает, где красное неравенство не выполняется. Аналогично синяя линия – это −4x + 5y = 10 , желтая линия – это −x + 2y = −2 , окрашенные области – та часть плоскости, где неравенство не выполняется.

Каждая точка серой области удовлетворяет всем ограничениям и является потенциальным решением задачи. Эта область называется областью допустимых решений (feasible region), а ее точки – допустимыми решениями (feasible solutions).

Мы хотим максимизировать z . Решение, соответствующее максимальному значению z , называют оптимальным решением.

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

Представим, что в задачу введено дополнительное ограничение в виде равенства, окрашенного зеленым:

Его можно визуализировать, добавив соответствующую зеленую прямую:

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

Если добавить требование, что все значения x должны быть целыми числами, то мы получим задачу смешанно-целочисленного линейного программирования, и набор возможных решений снова изменится:

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

Эти три примера иллюстрируют задачи линейного программирования – они имеют ограниченные допустимые области решений и конечные решения.

Когда ни одно решение не может удовлетворить все ограничения сразу, задача в рамках линейного программирования неразрешима.

Видео:Решение задачи линейного программирования графическим методомСкачать

1.2. Задача о распределении ресурсов

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

Предположим, что фабрика производит четыре различных продукта, ежедневное количество первого продукта составляет x_1 , второго продукта – x_2 и т. д. Цель – определить максимальную прибыль ежедневного объема производства для каждого продукта с учетом следующих условий:

1. Прибыль (profit) на единицу продукта составляет 20, 12, 40 и 25 долларов для каждого из четырех продуктов соответственно.
2. Из-за нехватки рабочей силы (manpower) общее количество единиц, производимых в день, не может превышать 50.
3. На каждую единицу 1-го продукта расходуется 3 единицы сырья A. Каждая единица 2-го продукта требует 2 единиц сырья A и 1 единицы сырья B. Каждой единице 3-го продукта требуется 1 единица A и 2 единицы B. Наконец, каждая единица 4-го продукта требует трех единиц. B.
4. Из-за ограничений по транспортировке и хранению фабрика может потреблять до 100 единиц сырья A и 90 единиц B в день.

Математическую модель можно определить так:

Целевая функция (прибыль) определяется в условии 1. Ограничение рабочей силы следует из условия 2. Ограничения на сырье A и B могут быть получены из условий 3 и 4 путем суммирования потребностей в сырье для каждого продукта. Наконец, количество продуктов не может быть отрицательным.

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

Видео:Как решать уравнения? уравнение 7 класс. Линейное уравнениеСкачать

2. Линейное программирование на Python. Практическая реализация

В этом руководстве мы будем использовать для решения описанной выше задачи линейного программирования два пакета Python :

1. SciPy – универсальный пакет для научных вычислений с Python. Его внутренний пакет scipy.optimize можно использовать как для линейной, так и для нелинейной оптимизации.
2. PuLP – API линейного программирования Python для определения задачи и вызова солверов. По умолчанию в качестве солвера используется COIN-OR Branch and Cut Solver (CBC). Еще один отличный солвер с открытым исходным кодом – GNU Linear Programming Kit (GLPK).

Видео:Практическая работа "Решение задач линейного программирования графическим методом".Скачать

2.1. Установка SciPy и PuLP

Чтобы следовать этому руководству, вам необходимо установить SciPy и PuLP.

Возможно, вам потребуется запустить pulptest или sudo pulptest , чтобы включить солверы PuLP, особенно если вы используете Linux или Mac:

Видео:Решение задачи линейного программирования в ExcelСкачать

2.2. Использование SciPy

В этом разделе мы рассмотрим, как использовать библиотеку SciPy по оптимизации и поиску корней для линейного программирования. Начнём с импорта scipy.optimize.linprog() :

Видео:Двойственная задача. Как составить и решить? Вторая теорема двойственностиСкачать

2.3. Решение первого примера c помощью SciPy

Начнём с решения первого (дополненного) примера:

linprog() решает только задачи минимизации (не максимизации) и не допускает ограничений-неравенств со знаком больше или равно ( ≥ ). Чтобы обойти эти проблемы, нам необходимо изменить описание задачи перед запуском оптимизации:

• Вместо максимизации z = x + 2y минимизируем отрицательное значение ( −z = −x − 2y ).
• Вместо знака ≥ мы можем умножить «желтое» неравенство на -1 и получить противоположный знак (ограничения по осям рассмотрим далее).

На следующем шаге определяем входные значения:

Мы поместили значения из системы в соответствующие списки:

• obj содержит коэффициенты целевой функции,
• lhs_ineq и rhs_ineq содержат коэффициенты из ограничений-неравенств,
• lhs_eq и rhs_eq содержат коэффициенты из ограничивающего уравнения.

Следующим шагом является определение границ каждой переменной. В данном случае они находятся между нулем и положительной бесконечностью:

Однако эти границы совпадают с установленными по умолчанию в linprog() .

Наконец, пришло время оптимизировать и решить интересующую нас проблему:

Параметр c относится к коэффициентам из целевой функции. A_ub и b_ub соответственно связаны с коэффициентами из левой и правой частей ограничений-неравенств. Точно так же A_eq и b_eq относятся к ограничениям уравнений. Параметр bounds служит для указания нижней и верхней границ переменных решения.

Параметр method определяет используемый алгоритм линейного программирования. Доступны три варианта:

• по умолчанию используется метод внутренней точки: method = «inner-point»,
• измененный двухфазный симплекс-метод method=»revised simplex»,
• симплекс-метод method=»simplex»

linprog() возвращает структуру данных со следующими атрибутами:

• .con – остатки ограничения-равенства;
• .fun – оптимальное значение целевой функции (если найдено);
• .message – словесный статус решения;
• .nit – количество итераций, необходимых для завершения расчета;
• .slack – значения так называемых дополнительных переменных – разниц между значениями левой и правой сторонами ограничений;
• .status – целое число от 0 до 4, отражающих результат решения: например, 0, когда было найдено оптимальное решение;
• .success – логическое значение, показывающее, найдено ли оптимальное решение;
• .x – массив NumPy, содержащий оптимальные значения переменных решения.

Доступ к атрибутам можно получить по отдельности:

Графически результат можно отобразить следующим образом.

Вначале наша задача органичивалась только неравенствами. Если удалить параметры зеленого уравнения A_eq и b_eq из вызова linprog() , получим следующий результат:

Видео:ЛИНЕЙНЫЕ УРАВНЕНИЯ - Как решать линейные уравнения // Подготовка к ЕГЭ по МатематикеСкачать

2.4. Решение задачи о производстве с помощью SciPy

Рассмотрим теперь решение второй задачи – о продуктах, рабочей силе и используемом сырье.

Как и в предыдущем примере, нам нужно извлечь необходимые векторы и матрицу из задачи, передать их в качестве аргументов в linprog() :

Максимальная прибыль составляет 1900 и соответствует x_1 = 5 и x_3 = 45 . В данных условиях производить второй и четвертый продукты невыгодно. Результат позволяет сделать несколько интересных выводов:

1. Третий продукт приносит наибольшую прибыль.
2. Первая дополнительная переменная ( slack ) равна 0. Это означает, что равны значения левой и правой сторон ограничения для рабочей силы. Завод производит 50 единиц в день, и это его полная мощность.
3. Вторая дополнительная переменная равна 40: фабрика потребляет 60 единиц сырья A (15 единиц для первого продукта и 45 для третьего) из возможных 100 единиц.
4. Третья дополнительная переменная равен 0: фабрика потребляет все 90 единиц сырья B. При этом все это количество потребляется для производства третьего продукта. Вот почему фабрика вообще не может производить второй или четвертый товар и не может произвести более 45 единиц третьего товара. Cырья B просто не хватает.

Возможности линейного программирования SciPy полезны в основном для небольших задач. Для более крупных и сложных проблем разумно использовать другие библиотеки:

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

Видео:Симплексный метод (табличный оформление №1) решения задачи линейного программирования.Скачать

2.5. Решение первой задачи на линейное программирование с помощью PuLP

Итак, PuLP имеет более удобный API линейного программирования, чем SciPy. Начнем с импорта.

Первый шаг – инициализировать экземпляр LpProblem для описания модели:

Параметр sense определяет, решаем ли мы задачу минимизации (параметр LpMinimize или 1 , установлен по умолчанию) или максимизации ( LpMaximize или -1 ).

Создав модель, мы можем определить переменные решения как экземпляры класса LpVariable :

Значения границ по умолчанию – отрицательная и положительная бесконечности, поэтому в нашем случае необходимо указать нижнюю границу ( lowBound = 0 ).

Необязательный параметр cat определяет категорию переменной решения. При работе с непрерывными переменными можно использовать значение по умолчанию «Continuous» .

Переменные x и y теперь можно использовать для создания других PuLP-объектов, представляющих линейные выражения и ограничения:

Построив линейную комбинацию нескольких переменных решения, мы получаем экземпляр pulp.LpAffineExpression , представляющий линейное выражение. Выражения можно комбинировать с операторами == , и >= и получать экземпляры pulp.LpConstraint – линейные ограничения вашей модели.

Опишем теперь ограничения. В отличие от SciPy, с PuLP не нужно создавать списки и матрицы. Просто записываем выражения Python и добавляем в модель с помощью оператора += :

LpProblem позволяет добавлять ограничения в модель, определяя их как кортежи. Первый элемент кортежа – экземпляр LpConstraint , второй – его удобочитаемое имя.

Аналогично описывается целевая функция:

Теперь можно посмотреть полное определение модели:

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

Теперь мы готовы решить задачу. Достаточно лишь вызвать метод .solve() для объекта модели.

Метод .solve() вызывает базовый солвер, изменяет объект модели и возвращает целочисленный статус решения, равный 1, если найден оптимум. Остальные коды состояний описаны в документации.

Результаты оптимизации доступны в виде атрибутов модели:

model.objective содержит значение целевой функции, model.constraints – значения дополнительных переменных, а объекты x и y имеют оптимальные значения переменных решения.

Результаты получились примерно такие же, как у SciPy.

Чтобы получить смешанно-целочисленное решение, достаточно обозначить это при помощи параметра cat :

Теперь x – целое число, как указано в модели. Этот факт меняет решение. Покажем это на графике:

Как видите, оптимальным решением является крайняя правая зеленая точка на сером фоне. Это решение с наибольшими значениями как x , так и y , дающее максимальное значение целевой функции.

Видео:Урок 1. Решение задачи линейного программирование в Excel с помощью надстройки «Поиск решения»Скачать

2.6. Решение задачи о производстве с помощью PuLP

Подход к определению и решению второй задачи такой же, как и в предыдущем примере:

Как видите, решение согласуется с тем, что мы молучили с помощью SciPy. Наиболее выгодное решение – производить в день 5 единиц первого продукта и 45 единиц третьего.

Давайте сделаем задачу более интересной. Допустим, из-за проблем с оборудованием, фабрика не может производить первую и третью продукцию параллельно. Какое решение наиболее выгодно в этом случае?

Теперь у нас есть еще одно логическое ограничение: если x_1 положительно, то x_3 должно равняться нулю, и наоборот. Здесь пригодятся бинарные переменные решения. Введем две переменные y_1 и y_3 , которые будут обозначать, генерируются ли вообще первый или третий продукты:

При таких условиях оказывается, что оптимальный подход – исключить первый продукт вовсе и производить только третий.

Заключение

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

Теперь – после прохождения этого руководства – вы умеете:

• определить модель, которая описывает задачу в SciPy и PuLP;
• создать программу Python для оптимизационной задачи;
• запустить программу оптимизации, чтобы найти решение задачи;
• получить результат оптимизации.

Если вы хотите узнать больше о линейном программировании, вот несколько отправных точек, с которых можно начать:

Следите за нашими тегами Python и Математика!