2. Линейное программирование на Python. Практическая реализация
В этом руководстве мы будем использовать для решения описанной выше задачи линейного программирования два пакета Python :
- SciPy – универсальный пакет для научных вычислений с Python. Его внутренний пакет scipy.optimize можно использовать как для линейной, так и для нелинейной оптимизации.
- PuLP – API линейного программирования Python для определения задачи и вызова солверов. По умолчанию в качестве солвера используется COIN-OR Branch and Cut Solver (CBC). Еще один отличный солвер с открытым исходным кодом – GNU Linear Programming Kit (GLPK).
2.1. Установка SciPy и PuLP
Чтобы следовать этому руководству, вам необходимо установить SciPy и PuLP.
linprog() решает только задачи минимизации (не максимизации) и не допускает ограничений-неравенств со знаком больше или равно ( ≥ ). Чтобы обойти эти проблемы, нам необходимо изменить описание задачи перед запуском оптимизации:
- Вместо максимизации z = x + 2y минимизируем отрицательное значение ( −z = −x − 2y ).
- Вместо знака ≥ мы можем умножить «желтое» неравенство на -1 и получить противоположный знак (ограничения по осям рассмотрим далее).
На следующем шаге определяем входные значения:
Вначале наша задача органичивалась только неравенствами. Если удалить параметры зеленого уравнения A_eq и b_eq из вызова linprog() , получим следующий результат:
2.4. Решение задачи о производстве с помощью SciPy
Рассмотрим теперь решение второй задачи – о продуктах, рабочей силе и используемом сырье.
Как и в предыдущем примере, нам нужно извлечь необходимые векторы и матрицу из задачи, передать их в качестве аргументов в linprog() :
Как видите, оптимальным решением является крайняя правая зеленая точка на сером фоне. Это решение с наибольшими значениями как x , так и y , дающее максимальное значение целевой функции.
2.6. Решение задачи о производстве с помощью PuLP
Подход к определению и решению второй задачи такой же, как и в предыдущем примере:
# Определяем модель model = LpProblem(name="resource-allocation", sense=LpMaximize) # Описываем переменные x = ", lowBound=0) for i in range(1, 5)> # Добавляем ограничения model += (lpSum(x.values()) , ") print(f"objective: ") for var in x.values(): print(f": ") for name, constraint in model.constraints.items(): print(f": ") status: 1, Optimal objective: 1900.0 x1: 5.0 x2: 0.0 x3: 45.0 x4: 0.0 manpower: 0.0 material_a: -40.0 material_b: 0.0 Как видите, решение согласуется с тем, что мы молучили с помощью SciPy. Наиболее выгодное решение – производить в день 5 единиц первого продукта и 45 единиц третьего.
Давайте сделаем задачу более интересной. Допустим, из-за проблем с оборудованием, фабрика не может производить первую и третью продукцию параллельно. Какое решение наиболее выгодно в этом случае?
Теперь у нас есть еще одно логическое ограничение: если x_1 положительно, то x_3 должно равняться нулю, и наоборот. Здесь пригодятся бинарные переменные решения. Введем две переменные y_1 и y_3 , которые будут обозначать, генерируются ли вообще первый или третий продукты:
model = LpProblem(name="resource-allocation", sense=LpMaximize) x = ", lowBound=0) for i in range(1, 5)> y = ", cat="Binary") for i in (1, 3)> model += (lpSum(x.values()) , ") print(f"objective: ") for var in model.variables(): print(f": ") for name, constraint in model.constraints.items(): print(f": ") status: 1, Optimal objective: 1800.0 x1: 0.0 x2: 0.0 x3: 45.0 x4: 0.0 y1: 0.0 y3: 1.0 manpower: -5.0 material_a: -55.0 material_b: 0.0 x1_constraint: 0.0 x3_constraint: -55.0 y_constraint: 0.0 При таких условиях оказывается, что оптимальный подход – исключить первый продукт вовсе и производить только третий.
Заключение
Теперь вы в общих чертах представляете, с какими задачами имеет дело линейное программирование и как использовать Python для решения подобных задач.
Теперь – после прохождения этого руководства – вы умеете:
- определить модель, которая описывает задачу в SciPy и PuLP;
- создать программу Python для оптимизационной задачи;
- запустить программу оптимизации, чтобы найти решение задачи;
- получить результат оптимизации.
Если вы хотите узнать больше о линейном программировании, вот несколько отправных точек, с которых можно начать:
- русскоязычная и анлоязычная вики-страницы о линейном программировании;
- русскоязычная и англоязычная вики-страницы о целочисленном программировании;
- туториал на Brilliant.org;
- вводный курс MIT о математическом программировании.
Следите за нашими тегами Python и Математика!
Больше полезной информации вы можете получить на нашем телеграм-канале «Библиотека питониста». Рекомендуем также обратить внимание на учебный курс по Python от «Библиотеки программиста».