- PVSM.RU - https://www.pvsm.ru -
Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является 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]
Выводы
Четвёртый вид ресурса в прямой задаче использована не полностью. Тогда ценность этого ресурса для предприятия оказывается более низкой по сравнению с ресурсами, ограничивающими выпуск продукции, и предприятие готово заплатить более высокую цену за приобретение ресурсов, позволяющих увеличить прибыль.
Введём новое назначение искомой переменной 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
Третий вид ресурсов имеет наибольшую ценность для производителя поэтому данный вид ресурсов должен быть закуплен в первую очередь, затем первый и второй вид. Четвёртый вид ресурса имеет для производителя нулевую ценность и закупается последним.
Ссылки
Автор: Юрий Тараненко
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/262842
Ссылки в тексте:
[1] Решение закрытой транспортной задачи с дополнительными условиями средствами Python.: https://habrahabr.ru/users/scorobey/posts/
[2] Двойственность в задачах линейного программирования.: http://studopedia.ru/5_89027_dvoystvennost-v-zadachah-lineynogo-programmirovaniya.html
[3] Источник: https://habrahabr.ru/post/336480/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.