Двойственные задачи линейного программирования знаки неравенства

Понятие двойственности в задачах линейного программирования. Правила построения двойственных задач (симметричных и несимметричных).

Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы ресурсов m видов в объемах b_i единиц соответственно (i=1;m). Из этих отходов, учитывая специализацию предприятия можно наладить выпуск n видов основной продукции.

a_i_j – норма расхода i-го ресурса на производство j-ой продукции;

c_j – цена реализации j-ой продукции;

x_j – объем выпуска j-ой продукции, обеспечивающей предприятию максимум прибыли.

Математическая модель задачи:

Оценки должны быть установлены исходя из следующих требований, отражающие несовпадающие интересы предприятия и организации:

1) общую стоимость отходов производства покупающая организация стремиться минимизировать;

2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку не меньшую той, что могло бы получить организовав собственное производство.

Эти требования формализуются в виде следующей ЗЛП:

– это требование покупающей организации.

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

Левая часть неравенства выражает стоимость ресурсов, идущих на производство единицы продукции первого вида; правая – цену продукции.

Аналогичные рассуждения можно провести относительно каждого вида продукции, в результате получим следующую систему ограничений:

Переменные y_i называются двойственными оценками или объективно обусловленными оценками. В зарубежной литературе их называют теневыми ценами.

Первая и вторая задачи называются парой взаимно двойственных ЗЛП. Т.к. эти задачи записаны в симметричной форме, то их принято называть парой симметричных двойственных задач.

В общем виде пара симметричных двойственных задач имеет следующий вид:

Прямая задача: Двойственная задача:

Если в качестве прямой принять задачу об определении оптимальных оценок на ресурсы, то в двойственной к ней будет задача об определении оптимального плана выпуска продукции.

Правила построения двойственных задач

Выделяют следующие правила построения симметричных двойственных задач:

если прямая задача на максимум, то двойственная к ней – на минимум, и наоборот;
коэффициенты c_j целевой функции прямой задачи являются свободными членами двойственной;
свободные члены b_i ограничений прямой задачи являются коэффициентами целевой функции двойственной;
матрицы ограничений прямой и двойственной задач являются транспонированными друг другу;
если прямая задача на максимум, то ее система ограничений представляется в виде неравенств со знаком «≤». Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств со знаком «≥»;
число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной – числу переменных прямой;
все переменные в обеих задачах неотрицательны.

Если среди ограничений прямой задачи имеются равенства или на некоторые переменные не наложено условие неотрицательности, то, построив двойственную ей задачу, получим пару несимметричных двойственных задач.

Правила построения несимметричной двойственной задачи:

если на переменную x_j прямой задачи наложено условие неотрицательности, то j—e условие системы ограничений двойственной задачи является неравенством;
если на переменную x_j прямой задачи не наложено условие неотрицательности, то j—e условие системы ограничений двойственной задачи записывается в виде строгого равенства;
если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.

Источник

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

Инструкция . Выберите количество переменных и количество ограничений прямой задачи линейного программирования, нажмите Далее . Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x_i ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных x_i неопределена, то можно использовать этот калькулятор.

Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных x₄ , x₅ , x₆ .
Тогда Y = C*A -1 =
Оптимальный план двойственной задачи равен: y₁ = 23.75, y₂ = 12.5, y₃ = 0
Z(Y) = 1100*23.75+120*12.5+8000*0 = 27625
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
0.1*250 + 0.2*5375 + 0.4*0 = 1100 = 1100
0.05*250 + 0.02*5375 + 0.02*0 = 120 = 120
3*250 + 1*5375 + 2*0 = 6125 < 8000 1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₃ = 0.
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
При постановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
0.1*23.75 + 0.05*12.5 + 3*0 = 3 = 3
0.2*23.75 + 0.02*12.5 + 1*0 = 5 = 5
0.4*23.75 + 0.02*12.5 + 2*0 = 9.75 > 4
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75 и станет равной: F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:

-3.8 ≤ с₁ ≤ 1
Таким образом, 1-параметр может быть уменьшен на 3.8 или увеличен на 1
Интервал изменения равен: [3-3.8; 3+1] = [-0.8;4]
Если значение c₁ будет лежать в данном интервале, то оптимальный план не изменится. 2-ый параметр целевой функции может изменяться в пределах:

-10 ≤ b₂ ≤ 30
Таким образом, 2-ый запас может быть уменьшен на 10 или увеличен на 30
Интервал изменения равен: [120-10; 120+30] = [110;150]
Составим субоптимальные варианты плана с учетом изменений исходных данных модели (таблицы).
Пусть 2-ый ресурс увеличили на 50

Базисные переменные	Значение базисных переменных	Коэффициент структурных сдвигов k c	Произведение k c на (50)	Расчет варианта плана
x 2	5375	6.25	312.5	5687.5
x 1	250	-2.5	-125	125
x 6	1875	1.25	62.5	1937.5
F(X)	27625	23.75	1187.5	28812.5

Пусть 1-ый ресурс уменьшили на -5

Базисные переменные	Значение базисных переменных	Коэффициент структурных сдвигов k c	Произведение k c на (-5)	Расчет варианта плана
x 2	5375	-12.5	62.5	5437.5
x 1	250	25	-125	125
x 6	1875	-62.5	312.5	2187.5
F(X)	27625	12.5	-62.5	27562.5

Задание : Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.
F(X) = 3x₁ + x₂ → min
— 2x₁ + x₂≥4
2x₁ + x₂≤8
3x₁ + 2x₂≥6
Решение.
I этап. Приводим систему к каноническому виду.
II этап. Решаем симплекс-методом.
Примечание: Если задача решается данным калькулятором, то предыдущие два этапа пропускаем, поскольку они автоматически включены в решение.
На втором этапе окончательный вариант симплекс-таблицы имеет вид:

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₅	2	-7	0	-2	0	1	2	-1
x₄	4	4	0	1	1	0	-1	0
x₂	4	-2	1	-1	0	0	1	0
F(X3)	4	-5	0	-1	0	0	1-M	-M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Записываем оптимальный план:
x₁ = 0, x₂ = 4, F(X) = 1•4 = 4 Составим двойственную задачу к прямой задаче.
— 2y₁ + 2y₂ + 3y₃≤3
y₁ + y₂ + 2y₃≤1
4y₁ + 8y₂ + 6y₃ → max
y₁ ≥ 0, y₂ ≤ 0, y₃ ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A -1 . Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Источник

A = (A₅, A₄, A₂) =