Решение прямой и двойственной задачи линейного программирования средствами Python

Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является 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 – количество произведенных итераций.

Результаты решения задачи 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]

1. Найден оптимальный план по видам продукции [0.0 0. 0 18.182 22.727 150. 0]
2. Найдено фактическое использование ресурсов [700.0, 250.0, 600.0, 309.091]
3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
4. Нет необходимости в вычислениях по п.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).

Результаты решения задачи 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

Третий вид ресурсов имеет наибольшую ценность для производителя поэтому данный вид ресурсов должен быть закуплен в первую очередь, затем первый и второй вид. Четвёртый вид ресурса имеет для производителя нулевую ценность и закупается последним.