Линейное программирование - один из наиболее распространенных методов оптимизации. Он имеет широкий спектр приложений и часто используется в исследованиях операций, промышленном дизайне, планировании и т. Д. Увы, он не так популярен, как машинное обучение (которое, безусловно, является формой оптимизации), но является основным методом решения проблем, которые можно сформулировать с помощью переменных решения, имеющих линейные отношения. Это быстрое практическое руководство, возможно, я расскажу об алгоритме Simplex и теории в одной из следующих статей.
Заявление о проблеме
Чтобы получить представление, мы собираемся решить простую задачу, касающуюся планирования производства. Представьте, что вы работаете в компании, производящей компьютеры. Компьютер - довольно сложный продукт, и есть несколько заводов, которые его собирают, и компания платит определенную сумму за единицу. Стоимость данной модели компьютера на рынке фиксирована на уровне 500 $, разные фабрики собирают компьютеры с разной скоростью и стоимостью. Завод f0 производит 2000 в день по 450 долларов за единицу, завод f1 1500 в день по 420 долларов за единицу и f2 1000 в день по 400. $ за единицу. У нас есть 1 месяц на сборку 80 000 единиц при условии, что ни один завод не должен производить более чем в два раза больше единиц, чем любой другой завод. Вопрос в том, каково оптимальное распределение производства между заводами, чтобы мы максимизировали прибыль, полученную от продажи компьютеров с учетом этих ограничений?
В этом руководстве мы собираемся использовать Python и пакет оптимизации линейного программирования PuLP, скопируйте и вставьте установку с помощью pip:
pip install pulp
Теперь, чтобы решить проблему производства компьютеров с помощью линейного программирования, нам понадобятся следующие вещи:
- Набор переменных решения
- Набор линейных ограничений на эти переменные
- Линейная целевая функция для максимизации или минимизации
Итак, откройте свой любимый редактор и приступим. Перед определением переменных в PuLP нам нужно создать объект проблемы со следующим кодом:
from pulp import *
problem = LpProblem("problemName", LpMaximize)
Мы собираемся добавить к этому объекту ограничения и целевую функцию. Обратите внимание, что конструктор задачи получает имя задачи и LpMaximize, что означает, что мы хотим максимизировать нашу целевую функцию. В нашем случае это прибыль от продажи определенного количества компьютеров. Кроме того, мы также определяем константы, которые мы получили из постановки задачи:
# factory cost per day cf0 = 450 cf1 = 420 cf2 = 400 # factory throughput per day f0 = 2000 f1 = 1500 f2 = 1000 # production goal goal = 80000 # time limit max_num_days = 30 num_factories = 3
В следующем разделе мы определим переменные решения.
Переменные решения
В PuLP переменная решения определяется следующим образом:
variable = LpVariable("variableName")
Иногда нам нужно указать границы для переменной (по умолчанию границы отсутствуют), в этом случае мы должны написать следующее:
var = LpVariable("boundedVariableName",lowerBound,upperBound)
Еще один полезный способ определения переменных в PuLP - использование функции dicts. Это может быть очень полезно в случаях, когда нам нужно определить большое количество переменных одного типа и границ, variableNames будет списком ключей для словаря:
varDict = LpVariable.dicts("varDict", variableNames, lowBound, upBound)
Итак, исходя из предыдущих определений, переменные решения для задачи производства компьютеров - это дни, которые мы тратим на производство для каждой фабрики:
# factories
num_factories = 3
factory_days = LpVariable.dicts("factoryDays", list(range(num_factories)), 0, 30, cat="Continuous")
Ограничения
Теперь, когда мы определили наши переменные решения, мы можем перейти к определению ограничений для проблемы. Обратите внимание, что ограничения должны быть линейными в настройке линейного программирования. Ограничения, о которых мы заботимся, заключаются в том, что количество собранных единиц должно быть больше или равно целевому количеству и производственному ограничению, согласно которому ни одна фабрика не должна производить более чем вдвое больше, чем другая фабрика:
# goal constraint c1 = factory_days[0]*f1 + factory_days[1]*f2 + factory_days[2] * f3 >= goal # production constraints c2 = factory_days[0]*f0 <= 2*factory_days[1]*f1 c3 = factory_days[0]*f0 <= 2*factory_days[2]*f2 c4 = factory_days[1]*f1 <= 2*factory_days[2]*f2 c5 = factory_days[1]*f1 <= 2*factory_days[0]*f0 c6 = factory_days[2]*f2 <= 2*factory_days[1]*f1 c7 = factory_days[2]*f2 <= 2*factory_days[0]*f0 # adding the constraints to the problem problem += c1 problem += c2 problem += c3 problem += c4 problem += c5 problem += c6 problem += c7
Целевая функция задачи сборки компьютеров сводится к минимуму затрат на сборку всех этих компьютеров. Это можно записать просто как максимизацию отрицательной стоимости:
# objective function problem += -factory_days[0]*cf0*f0 - factory_days[1]*cf1*f1 - factory_days[2]*cf2*f2
Давайте посмотрим на определение проблемы, это можно просто решить с помощью вызова:
print(problem)
Это приводит к следующему выводу, который, на мой взгляд, не требует пояснений, в нем перечислены целевая функция, ограничения и различные переменные решения в проблеме:
computerAssembly: MAXIMIZE -900000*factoryDays_0 + -630000*factoryDays_1 + -400000*factoryDays_2 + 0 SUBJECT TO _C1: 1500 factoryDays_0 + 1000 factoryDays_1 + 1000 factoryDays_2 >= 80000 _C2: 2000 factoryDays_0 - 3000 factoryDays_1 <= 0 _C3: 2000 factoryDays_0 - 2000 factoryDays_2 <= 0 _C4: 1500 factoryDays_1 - 2000 factoryDays_2 <= 0 _C5: - 4000 factoryDays_0 + 1500 factoryDays_1 <= 0 _C6: - 3000 factoryDays_1 + 1000 factoryDays_2 <= 0 _C7: - 4000 factoryDays_0 + 1000 factoryDays_2 <= 0 VARIABLES factoryDays_0 <= 30 Continuous factoryDays_1 <= 30 Continuous factoryDays_2 <= 30 Continuous
Решение
После того, как мы определили все необходимое в нашей задаче линейного программирования, мы можем вызвать метод решения, который выдает 1, если проблема решена, и -1, если она неосуществима, это простой однострочник:
# solving problem.solve()
Решение проблемы можно получить, обратившись к атрибуту varValue каждой переменной:
for i in range(3):
print(f"Factory {i}: {factory_days[i].varValue}")
Это приводит к следующему выводу:
Factory 0: 23.076923 Factory 1: 15.384615 Factory 2: 30.0
В линейном программировании мы предполагаем, что отношения между переменными являются линейными, а сами переменные - непрерывными. В продолжение этого руководства я расскажу о смешанном целочисленном программировании, где переменные могут быть целыми числами, что окажется очень полезным, поскольку его можно использовать для моделирования логической логики.
