Существует два способа решения задач оптимизации (ЗО). Задачи линейного программирования (ЗЛП), во-первых, могут быть решены аналитически, используя определенный метод решения общей постановки задачи.
Однако для решения ЗЛП аналитическим способом, а именно методом множителей Лагранжа, когда целевая функция (ЦФ) и ограничения дифференцируются, создается множество сложностей для вычисления.
В данном случае, даже для минимального числа переменных и ограничений, решение ЗЛП приводитк нахождению частных производных функции Лагранжа с дальнейшим решением системы уравнений с множеством неизвестных. Отсюда вытекает сложность применения аналитического способа решения ЗЛП.
Второй подход для решения ЗЛП позволяет использовать алгоритмические методы решения, применимые для решения ЗО в постановке общего вида. Эти подходы решения ЗЛП базируются на идее градиентного поиска для ЗО с ограничивающими условиями. Тем не менее на практике широко распространены алгоритмические методы решения ЗЛП, с учетом специфики ЦФ и множества допустимых решений. Из всех методов наиболее распространенным считается симплекс-метод для решения ЗЛП и метод потенциалов для решения транспортной задачи (ТЗ).
Для решения поставленной задачи применяем модуль оптимизации SciPy – для Python. Результаты вычислений рассматриваемой задачи оцениваем, сравнивая разные методы вычислений: аналитическое и алгоритмическое решения.
Материалы и методы исследования
В нынешнее время в Кыргызской Республике рынок по производству натуральных безалкогольных напитков (НБН) очень насыщен и разнообразен. Рынок Кыргызстана предоставляет множество ассортиментов напитков своих национальных, а также напитков из дальнего и ближнего зарубежья.
С улучшением качества продукции по выпуску НБН, по экономической теории, повышается спрос на этот продукт. Соответственно, рождаются новые конкуренты на рынке по производству данного продукта. НБН можно классифицировать следующим образом:
• НБН с молочным составом (Чалап, Тан);
• НБН с зерновым составом (Шоро Максым);
• НБН минерально-лечебные воды (Легенда, Жалал-Абад, Ысык-Ата и др.) [1].
Рассмотрим задачу упрощенного типа перевозки. У нас есть множество клиентов натуральных безалкогольных напитков (НБН) I = {1, 2, 3, 4, 5} и множество предприятий по производству НБН J = {1, 2, 3}. У каждого покупателя есть фиксированная потребность в натуральных безалкогольных напитках pi, и у каждого предприятия есть фиксированная производственная мощность Mj. Также существуют фиксированные транспортные расходы на доставку одной единицы товара с производства j покупателю i.
Математически эту задачу оптимизации можно описать следующим образом:
Найти минимум
L(x) = ∑i∈I ∑j∈J cijxij (1)
при условиях
∑j∈J xij = pi , i ∈ I (2)
∑i∈I xij ≤ Mj , j ∈ J (3)
xij ≥ 0, i ∈ I, j ∈ J. (4)
Теперь, условия задачи (1)–(4) можно записать в виде следующей таблицы.
Решив задачу способом [2, 3], определим оптимальный план.
Наша задача – доставить каждому покупателю необходимое количество НБН (удовлетворить покупательский спрос и производственные мощности фабрик) с минимальными общими транспортными расходами. Чтобы сформулировать эту ситуацию как задачу оптимизации, мы должны разделить ее на три основных компонента:
− Переменные решения – количества товаров, которые должны быть отправлены с производства j покупателю i (положительные действительные числа).
− Ограничения – общее количество товаров НБН должно удовлетворять как потребительский спрос, так и производственные мощности фабрики (равенства / неравенства, которые имеют линейное выражение в левой части).
− ЦФ – найти такие значения переменных решения, при которых общая стоимость перевозки будет наименьшей (в данном случае линейное выражение).
Условия задачи (1)–(4)
|
Покупатель i |
|||||||
|
Транспортные расходы cji |
1 |
2 |
3 |
4 |
5 |
Производственная мощность Mj |
|
|
НБН j |
1 |
4 |
5 |
6 |
8 |
10 |
500 |
|
2 |
6 |
4 |
3 |
5 |
8 |
500 |
|
|
3 |
9 |
7 |
4 |
2 |
4 |
500 |
|
|
cпрос pi |
80 |
270 |
250 |
160 |
180 |
||
С точки зрения оптимизации эта конкретная ситуация представляет собой проблему смешанного целочисленного линейного программирования, поскольку переменные решения не ограничиваются целыми числами (целочисленное программирование), а в соответствии с бизнес-логикой все ограничения и ЦФ являются линейными. Наличие только одной бизнес-цели делает ее одноцелевой оптимизационной задачей (также возможна многокритериальная оптимизация) [4].
Приступим к реализации решения на Python [5].
import sys
import numpy as np
p = {1:80, 2:270, 3:250, 4:160, 5:180} # Спрос потребителя
M = {1:500, 2:500, 3:500} # Производственная мощность
I = [1,2,3,4,5] # Покупатели
J = [1,2,3] # Производители
st_per = {(1,1):4, (1,2):6, (1,3):9,
(2,1):5, (2,2):4, (2,3):7,
(3,1):6, (3,2):3, (3,3):3,
(4,1):8, (4,2):5, (4,3):3,
(5,1):10, (5,2):8, (5,3):4
} # стоимость перевозки
st_per2p = np.empty([len(I), len(J)])
for i in range(len(I)):
for j in range(len(J)):
st_per2p[i,j] = st_per[i+1,j+1]
x0 = np.ones(len(st_per))*100
bounds = list((0,max(p.values())) for _ in range(st_per2p.size))
def ob(x):
ob_func = sum(x[idx]*st_per2p[idx//len(J), idx%len(J)] for idx in range(st_per2p.size))
return ob_func
# Ограничения: сумма товаров == покупательский спрос
def st_per1():
tmp = []
for idx in range(0, st_per2p.size, len(J)):
tmp_constr = {
'type': 'eq',
'fun': lambda x, idx: p[idx//len(J) + 1] – np.sum(x[idx: idx + len(J)]),
'args': (idx,)
}
tmp.append(tmp_constr)
return tmp
# Ограничения: сумма товаров <= производственная мощность
def st_per2():
tmp = []
for idx in range(0, st_per2p.size, len(I)):
tmp_constr = {
'type': 'ineq',
'fun': lambda x, idx=idx: M[idx//len(I) + 1] – np.sum(x[idx: idx + len(I)])
}
tmp.append(tmp_constr)
return tmp
list_of_lists = [st_per1(), st_per2()]
constraints = [item for sublist in list_of_lists for item in sublist]
from scipy.optimize import minimize
solution = minimize(fun = ob,
x0 = x0,
bounds = bounds,
method = 'SLSQP',
constraints = constraints,
tol = None,
callback = None,
options = {'full_output':False, 'disp':False, 'xtol': 1e-8}
)
if (solution.success) and (solution.status == 0):
print("Оптимальное решение найдено")
print("Значение целевой функции = ", solution.fun)
elif solution.status != 0:
print("Ошибка при нахождении решения. EXIT CODE", solution.status)
else:
# при возникновении ошибки
print(solution.message)
if solution.success:
EPS = 1.e-6
for i,_ in enumerate(solution.x):
if solution.x[i] > EPS:
print("отправка количества %5s с производства %2s заказчику %3s" % (round(solution.x[i]), i%len(J) + 1, i//len(J) + 1))
Результаты исследования и их обсуждение
При запуске программы получаем следующий ответ:
Оптимальное решение найдено
Значение целевой функции = 3350.0000000194086
отправка количества 80 с производства 1 заказчику 1
отправка количества 270 с производства 2 заказчику 2
отправка количества 125 с производства 2 заказчику 3
отправка количества 125 с производства 3 заказчику 3
отправка количества 160 с производства 3 заказчику 4
отправка количества 180 с производства 3 заказчику 5
Заключение
Итак, из оптимального решения следует вывод: при заданных условиях задачи (2)–(4) мы нашли значение целевой функции L(x) = 3350.