Каждый из нас повседневно сталкивается с задачами оптимизации, часто не замечая этого. В магазине мы стремимся минимизировать затраты, не теряя в количестве и качестве необходимых нам продуктов. Организуя свой день, делаем его максимально продуктивным, стараясь успеть на все мероприятия. И так далее. Обычно мы справляемся с этим интуитивно и самостоятельно. Но в бизнесе и в науке всё должно быть максимально точно. И здесь на помощь приходят алгоритмы оптимизации. В этом тьюториале представлена задача оптимизации и ее решения с помощью 3-х алгоритмов с использованием библиотек python. Итак, начнём.
Если говорить об определениях, то оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. Количественная оценка оптимизируемого качества называется критерием оптимальности или целевой функцией.
Условные задачи оптимизации, или задачи с ограничениями, – это такие задачи, при формулировке которых на значения аргументов налагаются ограничения в виде равенств или неравенств.
Задачи оптимизации часто возникают в экономике, при планировании производственных процессов и количественной оценке альтернатив, связанных с принятием управленческих решений. Постановка этих задач обычно основана на анализе и сопоставлении расходуемых ресурсов и полученного результата. Такой подход принято называть методом “затраты - эффективность”. Применение этого подхода приводит, как правило, к двум связанным между собой типам задач: либо максимизировать эффективность при ограниченных затратах, либо обеспечивать эффективность не ниже заданной при минимальных затратах.
Такую задачу также можно назвать задачей линейного программирования (LP).
Задача взята отсюда.
Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля A, B, C с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, B, C чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена исходных продуктов приведены в таблице:
Для начала необходимо составить математическую модель задачи. Введем следующие обозначения: x1 – содержание угля A в смеси; x2 – содержание угля B в смеси; x3 – содержание угля C в смеси.
Тогда ограничения примут вид:
А целевая функция будет:
Перенесём правую часть через равно и упростим выражения, где это возможно. Таким образом, получим математическую модель нашей задачи.
Целевая функция:
Ограничения:
Математическая модель готова, пришло время приступать к алгоритмам оптимизации. Для этого я предлагаю рассмотреть 3 библиотеки Python:
Для того, чтобы убедиться в верной работе алгоритма, сразу дам ответ на эту задачу.
Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб).
Устанавливаем библиотеку:
!pip install pulp
PuLP – это бесплатное программное обеспечение с открытым исходным кодом, написанное на Python. Оно используется для описания задач оптимизации, как математических моделей. Также PuLP может вызвать любой из многочисленных внешних решателей LP (CBC, GLPK, CPLEX, Gurobi и т. д.) для решения этой модели, а затем использовать команды python для управления и отображения решения.
Для начала решения задачи оптимизации необходимо инициализировать переменную (например prob) с помощью функции LpProblem(): - prob = LpProblem("The Problem", LpMinimize)
Она имеет два параметра, первый из которых произвольное имя этой проблемы (в виде строки), а второй параметр либо LpMinimize или LpMaximize в зависимости от типа задачи оптимизации (минимизация/максимизация), которую вы пытаетесь решить.
Переменные задачи создаются с помощью класса LpVariable:
- x = LpVariable("example", 0, None, LpInteger)
Он имеет четыре параметра:
Границы могут быть введены непосредственно как число, или None, чтобы не представлять никакой границы (т. е. положительная или отрицательная бесконечность), None стоит по умолчанию.
Если первые несколько параметров введены, а остальные игнорируются, они принимают значения по умолчанию. Однако, если вы хотите указать третий параметр, но хотите, чтобы второй был значением по умолчанию, вам нужно будет специально установить второй параметр как значение по умолчанию. То есть, нельзя оставлять запись параметра пустой.
Далее, объявленная переменная prob начинает сбор данных с помощью оператора +=. Сначала вводится целевая функция с важной запятой в конце инструкции и короткой строкой, объясняющей, что это за целевая функция. Пример:
- prob += 0.013*x1 + 0.008*x2, "Total Cost of Ingredients per can"
Затем точно также вводятся ограничения. Например: - prob += x1 + x2 == 100, "PercentagesSum" - prob += 0.100x1 + 0.200x2 >= 8.0, "Requirement"
Строка в конце является необязательной.
Далее, решается задача оптимизации с помощью функции: - prob.solve()
Если задача решилась оптимально, то можно выводить значения найденных переменный в цикле. Для вывода на экран результата целевой функции нужно воспользоваться функцией value.
Напомним уже найденную математическую модель:
Целевая функция:
Ограничения:
Код с импользованием библиотеки PuLP:
from pulp import *
import time
start = time.time()
problem = pulp.LpProblem('0', pulp.LpMinimize)
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
problem += 30*x1 + 30*x2 + 45*x3, 'Целевая функция'
problem += 0.03*x1 + 0.01*x2 - 0.01*x3 <= 0, '1-е ограничение'
problem += -1.25*x1 + 0.75*x2 - 0.25*x3 <=0, '2-е ограничение'
problem += x1 + x2 + x3 == 1, '3-е ограничение'
problem.solve()
print ("Результат:")
for variable in problem.variables():
print (variable.name, "=", variable.varValue)
print ("Цена:")
print (value(problem.objective))
stop = time.time()
print ("Время:")
print(stop - start)
Результат: ('x1', '=', 0.083333333) ('x2', '=', 0.33333333) ('x3', '=', 0.58333333) Цена: 38.74999974 Время: 0.0930559635162
Ответ был: Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)
Ответы сошлись! Успех!
Устанавливаем библиотеку:
!pip install scipy
SciPy – это популярная библиотека для языка программирования Python, предназначенная для выполнения научных и инженерных расчётов. Библиотека включает компоненты для решения дифференциальных уравнений, интегрирования, обработки изображений, визуализации, оптимизации и многих других задач. В частности, для решения задач линейного программирования SciPy предлагает функцию linprog (входящую в компонент optimize).
scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
bounds=None, method='simplex', callback=None,
options={'disp': False,
'bland': False,
'tol': 1e-12,
'maxiter': 1000})
Минимальное количество пораметров – один, только параметр с.
Описание параметров:
Дополнителные опции, задаваемые через параметр options:
То есть, в пареметр A_ub мы записываем коэффиценты неравенства («≤»), в параметр A_eq коэффиценты равенства («=»). Для неравенства («≥») парметров нет, но это легко исправить, поменяв знаки коэффицентов и добавив их в пареметр A_ub.
Возвращаемым значением является объект scipy.optimize.OptimizeResult, содержащий следующие поля:
Напомню математическую модель задачи.
Целевая функция:
Ограничения:
Код:
from scipy.optimize import linprog
import time
start = time.time()
c = [30,30,45] # Целевая функция
A_ub = [[0.03,0.01,-0.01],[-1.25,0.75,-0.25]] # Коэффициенты первых 2-х функций ограничения
b_ub = [0,0] # Результат первых 2-х функций ограничения
A_eq = [[1,1,1]] # Коэффициенты 3-й функции ограничения
b_eq = [1] # Результат 3-й функции ограничения
print (linprog(c, A_ub, b_ub, A_eq, b_eq)) # Оптимизация
stop = time.time()
print ("Время :")
print(stop - start)
fun: 38.749999999999993 message: 'Optimization terminated successfully.' nit: 3 slack: array([ 0., 0.]) status: 0 success: True x: array([ 0.08333333, 0.33333333, 0.58333333]) Время : 0.00560903549194
Сравним с ответом задачи: для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)
Решено верно!
Устанавливаем:
!pip install cvxopt
Библиотека CVXOPT предназначена для решения более широкого класса задач – задач выпуклого программирования. Соответственно, в ней используются более универсальные алгоритмы, за счет чего время решения аналогичных задач может оказаться несколько больше, чем у специализированных библиотек, реализующих разновидности симплекс-метода.
Переменные оптимизации представлены объектами, которые являются векторной величиной. - cvxopt.modeling.variable([size[, name]])
Целевую функцию и ограничения можно определить с помощью перегруженных операций над переменными и другими функциями. Поддерживаются три типа функций: аффинные, выпуклые кусочно-линейные и вогнутые кусочно-линейные.
Задачи оптимизации строятся вызовом следующей функции. - cvxopt.modeling.op([objective[, constraints[, name]]])
Первый аргумент определяет целевую функцию, которая должна быть минимизирована. Это может быть аффинная или выпуклая кусочно-линейная функция с длиной 1, переменная с длиной 1 или скалярная константа (целое число, float или 1 на 1 плотная матрица). Значение по умолчанию – 0.0.
Второй аргумент – одно ограничение или список объектов ограничений. Значение по умолчанию – пустой список.
Третий аргумент – строка с именем задачи. Значением по умолчанию является пустая строка.
Задача оптимизации с выпуклой кусочно-линейной задачей и ограничениями может быть решена путем вызова метода solve. Эта функция преобразует задачу оптимизации в линейную программу в матричном виде, а затем решает ее.
- solve([format[, solver]])
Решатель сообщает о результатах оптимизации, задавая атрибут self.status и путем изменения значений атрибутов переменных и множителей ограничений задачи.
Исходная математическая модель:
Целевая функция:
Ограничения:
Код с использованием библиотеки cvxopt:
from cvxopt.modeling import variable, op
import time
start = time.time()
x = variable(3, 'x')
z=(30*x[0] + 30*x[1] + 45*x[2]) # Целевая функция
mass1 = (0.03*x[0] + 0.01*x[1] - 0.01*x[2] <= 0) # 1-е ограничение
mass2 = (-1.25*x[0] + 0.75*x[1] - 0.25*x[2] <= 0) # 2-е ограничение
mass3 = (x[0] + x[1] + x[2] == 1) # 3-е ограничение
problem = op(z,[mass1,mass2,mass3]) # Построение задачи
problem.solve(solver='glpk') # Оптимизация
problem.status
print ("Цена:")
print(abs(problem.objective.value()[0]))
print ("Результат:")
print(x.value)
stop = time.time()
print ("Время :")
print(stop - start)
Цена: 38.75 Результат: [ 8.33e-02] [ 3.33e-01] [ 5.83e-01] Время : 0.00599002838135
Ответ был: Для получения 1т угля необходимо взять 1/12т (0.0833т) первого компонента, 1/3т (0.333т) второго, 7/12т (0.583т) третьего. При этом его цена будет минимальной и составит 155/4 руб (38.75 руб)
Итак, алгоритм с использованием библиотеки CVXOPT также прекрасно справляется с задачей! Решено верно.
Данный ответ | Библиотека PuLP | Библиотека SciPy | Библиотека CVXOPT | ||
---|---|---|---|---|---|
y | 38.74 | 38.74999974 | 38.749999999999993 | 38.75 | |
x1 | 0.0833 | 0.083333333 | 0.08333333 | 8.33e-02 | |
x2 | 0.333 | 0.33333333 | 0.33333333 | 3.33e-01 | |
x3 | 0.583 | 0.58333333 | 0.58333333 | 5.83e-01 | |
Время, сек | - | 0.0930559635162 | 0.00560903549194 | 0.00599002838135 |
Как видно из таблицы, все библиотеки справились с задачей. Лучшей по времени оказалась библиотека SciPy. Но решение о применении той или иной библиотеки часто носит субъективный характер, поэтому целесообразно проводить их сравнительный анализ для области решаемых Вами задач.
Умение грамотно строить математическую модель ситуации и знание алгоритмов оптимизации может очень сильно пригодиться даже в бытовых вещах. Будь то планирование маршрута путешествий с наименьшими затратами и наибольшой пользой, или выбор в пользу той или иной работы. Стоит ещё упомянуть, что в своё время Б.А. Березовский занимался этим вопросом и даже написал не одну научную работу. Одну из самых известных Березовский написал с соавторами (с Ю. А. Барышниковым, В. И. Борзенко и Л. М. Кемпнером) "Многокритериальная оптимизация: математические аспекты". Кто знает, может быть, умение оптимизировать всё, что оптимизируется, очень сильно пригодиться Вам в жизни!
Если Вы нашли ошибку, или у вас есть замечания, пожалуйста, напишите мне на почту – elizavetazikeeva@gmail.com.
Большое спасибо, что уделили своё время этому тьюториалу! :)