Введение
Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является Python.
Постановка задачи
В публикациях [1,2] рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.
Однако известно [3], что каждой задаче линейного программирования соответствует так называемая выделенная(двойственная)задача. В ней по сравнению с прямой задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума — максимум). Задача, двойственная к двойственной — эта сама исходная задача.
Решение двойственной задачи очень важно для анализа использования ресурсов. В данной публикации будет доказано, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной).
Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.
Решение прямой задачи о оптимальной производственной программе
Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub — вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с — вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.
Функция цели
maxF(x)=c×x
Ограничения
A×x≤b
Численные значения переменных:
N=5; m=4; b_ub = [700,250,600,400]; A_ub = [[1,2,3,2,4], [5,4,3,2,1], [3,4,2,5,3],[4,2,5,3,1]]; c = [25, 35,25,40,30].
Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1
Особенности решения с библиотекой scipy. optimize
Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.
Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.
Листинг решения прямой задачи оптимизации
#!/usr/bin/python
# -*- coding: utf-8 -*-
import scipy
from scipy.optimize import linprog # загрузка библиотеки ЛП
c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели
b_ub = [700,250,600,400] # список объёмов ресурсов
A_ub = [[1,2,3,2,4], # матрица удельных значений ресурсов
[5,4,3,2,1],
[3,4,2,5,3],
[4,2,5,3,1]]
d=linprog(c, A_ub, b_ub) # поиск решения
for key,val in d.items():
print(key,val) # вывод решения
if key=='x':
q=[sum(i) for i in A_ub*val]#использованные ресурсы
print('A_ub*x',q)
q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов
print('b_ub-A_ub*x', q1)
Результаты решения задачи
nit 3
status 0
message Optimization terminated successfully.
success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x [700.0, 250.0, 600.0, 309.09090909090912]
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]
Выводы
- Найден оптимальный план по видам продукции [0.0 0. 0 18.182 22.727 150. 0]
- Найдено фактическое использование ресурсов [700.0, 250.0, 600.0, 309.091]
- Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
- Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack
Решение двойственной задачи о оптимальной производственной программе
Четвёртый вид ресурса в прямой задаче использована не полностью. Тогда ценность этого ресурса для предприятия оказывается более низкой по сравнению с ресурсами, ограничивающими выпуск продукции, и предприятие готово заплатить более высокую цену за приобретение ресурсов, позволяющих увеличить прибыль.
Введём новое назначение искомой переменной x как некоторой «теневой» цены, определяющей ценность данного ресурса в отношении прибыли от реализации выпускаемой продукции.
Далее для сравнительного анализа частично сохраним ранее принятые обозначения, но с новым содержанием:
c – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.
Функция цели
minF(x)=c×x
Ограничения
A_ub_T ×x≥ b_ub
Численные значения и соотношения для переменных:
с = [700,250,600,400]; A_ub_T transpose(A_ub); b_ub = [25, 35,25,40,30].
Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.
Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).
Листинг решения двойственной задачи оптимизации
#!/usr/bin/python
# -*- coding: utf-8 -*-
import scipy
from scipy.optimize import linprog
A_ub = [[1,2,3,2,4],
[5,4,3,2,1],
[3,4,2,5,3],
[4,2,5,3,1]]
c=[700,250,600,400]
b_ub = [-25, -35,-25,-40,-30]
A_ub_T =-scipy.transpose(A_ub)
d=linprog(c, A_ub_T, b_ub)
for key,val in d.items():
print(key,val)
Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True
Выводы
Третий вид ресурсов имеет наибольшую ценность для производителя поэтому данный вид ресурсов должен быть закуплен в первую очередь, затем первый и второй вид. Четвёртый вид ресурса имеет для производителя нулевую ценность и закупается последним.
Результаты сравнения прямой и двойственной задачи
- Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
- Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
- Прямая задача является задачей максимизации, а двойственная — задачей минимизации, и наоборот.
- Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
- Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
- Знаки неравенств в ограничениях меняются на противоположные.
- Матрица системы равенств транспонируется.
Ссылки
