Существует два способа решения задач оптимизации (ЗО). Задачи линейного программирования (ЗЛП), во-первых, могут быть решены аналитически, используя определенный метод решения общей постановки задачи.

Однако для решения ЗЛП аналитическим способом, а именно методом множителей Лагранжа, когда целевая функция (ЦФ) и ограничения дифференцируются, создается множество сложностей для вычисления.

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

Второй подход для решения ЗЛП позволяет использовать алгоритмические методы решения, применимые для решения ЗО в постановке общего вида. Эти подходы решения ЗЛП базируются на идее градиентного поиска для ЗО с ограничивающими условиями. Тем не менее на практике широко распространены алгоритмические методы решения ЗЛП, с учетом специфики ЦФ и множества допустимых решений. Из всех методов наиболее распространенным считается симплекс-метод для решения ЗЛП и метод потенциалов для решения транспортной задачи (ТЗ).

Для решения поставленной задачи применяем модуль оптимизации 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)

С точки зрения оптимизации эта конкретная ситуация представляет собой проблему смешанного целочисленного линейного программирования, поскольку переменные решения не ограничиваются целыми числами (целочисленное программирование), а в соответствии с бизнес-логикой все ограничения и ЦФ являются линейными. Наличие только одной бизнес-цели делает ее одноцелевой оптимизационной задачей (также возможна многокритериальная оптимизация) [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.