Из занятия 1 имеем прямую задачу линейного программирования.
Урок 1. Задача линейного программирования в EXCEL. Надстройка «Поиск решения»
СМЫСЛ. Помощь в учёбе. 6 декабря 2022
Прямая задача ЛП
Записываем матрицу прямой задачи:
Матрица прямой задачи ЛП
Транспонируем полученную матрицу и получаем матрицу двойственной задачи: ТРАНСП(C12:G16)
Матрица двойственной задачи ЛП
Двойственная задача запишется в виде:
Двойственная задача ЛП
Запишем обе задачи:
Пара двойственных задач ЛП
Запишем матрицы соответствия переменных прямых и двойственных задач:
Матрицы соответствия переменных прямой и двойственной задач
Единица по диагонали означает соответствие:
Подпишем соответствующие переменные к последней симплекс-таблице из урока 3.
Урок 3. Решение задачи линейного программирования симплекс-методом.
СМЫСЛ. Помощь в учёбе. 12 декабря 2022
Последняя симплекс-таблица
Видим, что значения двойственных переменных совпадают со значениями,
Урок 2. Двойственная задача линейного программирования. Решение двойственной задачи в Excel.
полученными нами через надстройку «поиск решения»
Анализ устойчивости
Значения целевых функций для оптимальных планов двойственных задач совпадают F min = f max = 30,667.
Значения Y6=3,3 и Y8=3,0333 означают, что при производстве одного вида продукции 2-го и 4-го вида значение целевой функции уменьшится на 3,3 и 3,0333 денежных единиц соответственно.
Y5=Y7=0 означает, что производство 1-го и 3-го видов продукции является наиболее эффективным.
Значения Y2=0,1 и Y3=0,267 означают, что при увеличении запасов 2-го и 3-го видов сырья на одну весовую единицу, значение целевой функции возрастёт на 0,1 и 0,267 денежных единиц соответственно. Так же это означает дефицитность этих видов ресурсов, так как оценки выше нуля.
Y1=Y4=0 – это означает, что ресурсы 1-го и 4-го видов не являются дефицитными и их увеличение никак не повлияет на значение целевой функции.
Эти выводы действительны в пределах интервалах устойчивости изменения ресурсов и коэффициентов целевой функции.
Надстройка «поиск решения» автоматически считает интервалы устойчивости для коэффициентов целевой функции и ресурсов. Интервалы устойчивости показаны в столбцах «допустимое увеличение» и «допустимое уменьшение».
В следующей статье мы рассмотрим определение интервалов устойчивости ресурсов и коэффициентов целевой функции на основании последней симплекс-таблице из занятия 3.
Материал подготовлен сайтом: https://pro-smysl.ru/
Онлайн помощь в решении задач, консультации, создание обучающих роликов.
Подписывайтесь на наши каналы:
Источник: dzen.ru
Решение двойственной задачи
Приводятся формулировки первой и второй теорем двойственности. Показано, как получить решение двойственной задачи из решения прямой, применяя эти теоремы. Подробно разобраны примеры решений задач.
Двойственная задача линейного программирования (ЗЛП)
Здесь мы рассмотрим вопрос, как из решения прямой задачи, получить решение двойственной задачи.
Теоремы двойственности
Первая теорема двойственности
Если одна из пары двойственных задач имеет оптимальное решение,
то и двойственная задача имеет оптимальное решение. При этом значения целевых функций прямой и двойственной задачи, для оптимальных решений, равны друг другу.
Если одна из пары двойственных задач не имеет решения вследствие неограниченности целевой функции,
то двойственная задача не имеет решения вследствие несовместимости системы ограничений.
Вторая теорема двойственности
Пусть мы имеем симметричную пару двойственных задач (1) и (2):
(1.1) ;
(1.2)
(2.1) ;
(2.2)
Для того чтобы допустимые решения и являлись оптимальными решениями двойственных задач (1) и (2),
необходимо и достаточно, чтобы выполнялись следующие равенства:
(3) , ;
(4) , .
Для наглядности, выпишем равенства (3) и (4) в развернутом виде:
(3.1)
(3.2)
(3.m)
Метод решения двойственной задачи
Применяя теоремы двойственности, можно получить решение двойственной задачи из решения прямой. Опишем метод решения двойственной задачи.
Пусть мы нашли решение прямой задачи (1) с оптимальным значением целевой функции и с оптимальным планом . Подставим найденные значения в систему ограничений (1.2). Тогда если -е неравенство не является равенством, то есть если
,
то, согласно (3.i),
.
Рассматривая все строки системы ограничений (1.2), мы найдем, что часть переменных двойственной задачи равна нулю.
Далее замечаем, что если , то, согласно (4.k), -я строка системы ограничений (2.2) является равенством:
.
Составив все строки системы ограничений (2.2), для которых , мы получим систему уравнений, из которой можно найти ненулевые значения переменных .
На основании первой теоремы двойственности, минимальное значение целевой функции
.
Если известно решение задачи (2), то аналогичным образом можно найти решение задачи (1).
Примеры решения двойственной задачи из решения прямой
Пример 1
Пусть дана задача линейного программирования:
;
Известно решение этой задачи:
; .
Составить двойственную задачу и получить ее решение из решения прямой.
Согласно первой теореме двойственности, оптимальное значение целевой функции равно
.
Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи.
(П1.1.1) ;
(П1.1.2) ;
(П1.1.3) ;
(П1.1.4) .
Поскольку первая и четвертая строки являются строгими неравенствами (не являются равенствами), то
и .
Поскольку и , то 2-я и 4-я строки двойственной задачи являются равенствами:
Подставим уже найденные значения и , имеем:
Отсюда
;
; .
Двойственная задача имеет вид:
;
Ее решение
;
Пример 2
Дана задача линейного программирования:
(П2.1.1) ;
(П2.1.2)
Найти решение этой задачи, решив двойственную задачу графическим методом.
Решение задачи (П2.2) приводится на странице “Решение задач линейного программирования графическим методом”. Решение задачи (П2.2) имеет вид:
; .
Согласно первой теореме двойственности, оптимальное значение целевой функции равно
.
Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи (П2.2).
;
;
.
Поскольку третья строка является строгим неравенством (не являются равенством), то
.
Поскольку и , то 1-я и 2-я строки двойственной задачи (П2.1) являются равенствами:
Подставим найденное значение .
Решаем систему уравнений.
;
;
;
; ;
.
Решение исходной задачи (П2.1) имеет вид:
; .
Источник: 1cov-edu.ru
Решение прямой и двойственной задачи линейного программирования средствами 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 – количество произведенных итераций.
Листинг решения прямой задачи оптимизации
#!/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 выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
- Прямая задача является задачей максимизации, а двойственная — задачей минимизации, и наоборот.
- Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
- Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
- Знаки неравенств в ограничениях меняются на противоположные.
- Матрица системы равенств транспонируется.
- Решение закрытой транспортной задачи с дополнительными условиями средствами Python.
- Решение задач линейного программирования с использованием Python.
- Двойственность в задачах линейного программирования.
- Задачи линейного программирования
- двойственные задачи
- методы оптимизации
- scipy. optimize
- python
Источник: habr.com