Двойственность в линейном программировании

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

Рассмотрим задачу о планируемом выпуске продукции.

F= 3х₁+ 5х₂+ 4х₃+ 5х₄→ max.
5x₁+0.4x₂+2x₃+0.5x₄≤400
5x₂+x₃+x₄≤300
x₁+x₃+x₄≤100
x₁≥0, x₂≥0, x₃≥0, x₄≥0

Содержательная постановка прямой задачи: составить такой план выпуска продукции X = (х₁,х₂ ..., х_n), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Общие правила составления двойственной задачи:

Построим двойственную ей задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
4. Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных y_i в задаче II - это, соответственно, коэффициенты i-го неравенства в задаче I.
Полученная модель и есть экономико-математическая модель задачи, двойственной к прямой задаче.

Неравенства, соединенные стрелочками, будем называть сопряженными.
Содержательная постановка двойственной задачи: найти такой набор цен (оценок) ресурсов Y = (y₁, у₂ ..., у_m), при котором общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Цены ресурсов у₁, у₂ ..., у_m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен с₁, с₂ ..., с_n на продукцию, известных, как правило, до начала производства цены ресурсов у₁, у₂ ..., у_m являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Теоремы двойственности

Первая теорема двойственности.

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*) = G(y*), где х*, у* - оптимальные решения задач I и II

Вторая теорема двойственности.

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х* и у* - допустимые решения прямой и двойственной задач и если c^Tx*=b^Ty*, то х* и у* – оптимальные решения пары двойственных задач.

Третья теорема двойственности. Значения переменных y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i системы ограничений - неравенств прямой задачи на величину целевой функции этой задачи:
Δf(x) = b_iy_i

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Значения переменных двойственной задачи y_i, в оптимальном плане называют объективно обусловленными, или двойственными оценками. В прикладных задачах двойственные оценки y_i часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов.

Свойство взаимно двойственных задач

1. В одной задаче ищут максимум линейной функции, в другой — минимум.
2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤, а в задаче минимизации все неравенства вида ≥.
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
6. Условия неотрицательности переменных имеются в обеих задачах.

Итак, имеем исходную задачу I и ее оптимальное решение х* = (0, 40, 0, 100) и F(х*) = 700.

Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи II у* = (у₁, у₂, у₃), не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.

Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

Заметим, что действительно G(y*) = 400y₁+ 300y₂+ 100y₃= 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).

Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.
Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:

Установив такую связь, можно заметить, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл.), мы фактически решим и задачу II.
Запишем таблицу, учитывая соответствие между переменными х_i и y_j.

В силу соответствия и II теоремы двойственности переменные у₁, у₅, у₇ обязаны равняться 0, т.к. х₅, х₂, х₄>0 строго. А переменные у₄, у₂, у₆, у₃ принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х₁, х₆, х₃, х₇ = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

у* = (у₁*, у₂*, у₃*, у₄*, у₅*, у₆*, у₇*) = (0, 1, 4, 1, 0, 1, 0).

Мы научились по решению исходной задачи находить решение двойственной. Это оказалось возможно благодаря глубокой связи между переменными х_i и y_j. Осталось разобраться, каково экономическое содержание этих взаимосвязей.

Теорема равновесия

Теорема равновесия. Пусть X*=(x₁*,...,x_n*) и Y*=(y₁*,...,y_n*) - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:


Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением.
Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.
В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений.

Пример 2
Составить двойственную задачу и найти ее решение по теореме равновесия
x₂-2x₃+2x₄-2x₅≤4
-2x₁-2x₂+2x₃+2x₄+x₅≥2
x_i≥0, i=1,5
Z=10x₁-9x₂-19x₃-13x₄-11x₅ → max, если известно решение исходной задачи: Zmax=(3;4;0;0;0).
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.

Z=10x₁-9x₂-19x₃-13x₄-11x₅ → max
Двойственная задача:

W=4y₁-2y₂ → min
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.
y₁(4-(x₂-2x₃+2x₄-2x₅))=0
y₂(-2-(2x₁-2x₂-2x₃-2x₄-x₅))=0
x₁(-2y₂-10)=0
x₂(y₁-2y₂+9)=0
x₃(-2y₁-2y₂+19)=0
x₄(2y₁-2y₂+13)=0
x₅(-2y₁-y₂+11)=0
Подставим в составленную систему оптимальное решение исходной задачи: x₁=3, x₂=4, x₃=0, x₄=0, x₅=0.
y₁(4-(4-2·0+2·0-2·0))=0
y₂(-2-(2·3-2·4-2·0-2·0-0))=0
3·(-2y₂-10)=0
4·(y₁-2y₂+9)=0
0·(-2y₁-2y₂+19)=0
0·(2y₁-2y₂+13)=0
0·(-2y₁-y₂+11)=0
Произведение равно нулю, если один из множителей равен 0. Получаем
y₁·0=0
y₂·0=0
2y₂-10=0
y₁-2y₂+9=0
0=0
0=0
0=0
Тогда,
-2y₂-10=0
y₁-2y₂+9=0
или
y₂=5, y₁=2y₂+9 = 10-9=1
Оптимальное решение двойственной задачи Wmin=W(1;5). По Теореме 3 Zmax=Wmin= -6. Окончательно, Wmin=W(1;5)=-6.

Пример 3
Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия
x₁+3x₂≥12
5x₁+4x₂≥31
2x₁+3x₂≥18
x₁, x₂≥0
Z(x₁,x₂)=12000x₁+16000x₂→min
В разделе 1.5 было найдено решение исходной задачи средствами MS Excel: Zmin(3;4)=100000
Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.

Z(x₁,x₂)=12000x₁+16000x₂→min
Двойственная задача:

W(y₁, y₂, y₃)=12y₁+31y₂+18y₃ → max
Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.
y₁(x₁+3x₂-12)=0
y₂(5x₁+4x₂-31)=0
y₃(2x₁+3x₂-18)=0
x₁(12000-(y₁+5y₂+2y₃))=0
x₂(16000-(3y₁+4y₂+3y₃))=0

Подставим в составленную систему оптимальное решение исходной задачи: x₁=3, x₂=4.
y₁(3+3·4-12)=0
y₂(5·3+4·4-31)=0
y₃(2·3+3·4-18)=0
3·(12000-(y₁+5y₂+2y₃))=0
4·(16000-(3y₁+4y₂+3y₃))=0
Произведение равно нулю, если один из множителей равен 0. Получаем
y₁·3=0, y₁=0
y₂·0=0
y₃·0=0
12000-(y₁+5y₂+2y₃)=0
16000-(3y₁+4y₂+3y₃)=0
Тогда,
12000-(0+5y₂+2y₃)=0
16000-(3·0+4y₂+3y₃)=0
или
5y₂+2y₃=12000 | × 3
4y₂+3y₃=16000 | × 2
или
15y₂+6y₃=36000
8y₂+6y₃=32000

Вычтем из первого уравнения второе:
,

Оптимальное решение двойственной задачи . По Теореме 3 Zmax=Wmin=100000.
Окончательно, Wmin=W(0; 4000/7; 32000/21) = 100000 ">Оценка целесообразности выпуска новой продукции Пример №1. Для изготовления трех видов продукции используют два типа сырья. Запасы сырья, нормы его расхода и цены реализации единицы каждого вида продукции приведены в таблице.

Решение.
Обозначим через х₁, х₂ и х₃ − объем выпуска изделий вида «А», «Б» и «В» соответственно. Запишем математическую модель задачи:
max (4x₁ + 3x₂ + 5x₃), (1)
3x₁ + 2x₂ + 4x₃ ≤ 200, (2)
2x₁ + x₂ + 3x₃ ≤ 160, (3)
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. (4)
В этой модели функциональные ограничения (2)-(3) отражают условия ограниченности объемов, используемых в производстве ресурсов.
Проверим, как удовлетворяется система функциональных ограничений оптимальным планом Х^* = (х₁ = 0, х₂ = 100, х₃ = 0):
3∙0 + 2∙100 + 4∙0 = 200, (5)
2∙0 + 100 +3∙0 =100 < 160. (6)
Значение целевой функции (1) на этом плане равно
f(Х^*) = 4∙0 + 3∙100 + 5∙0 = 300.
Отметим, что нулевые значения х₁ и х₃ означают нецелесообразность выпуска изделий вида «А» и «В» с точки зрения принятого критерия оптимальности.
Двойственная задача имеет вид:
min (200y₁ + 160y₂), (7)
3y₁ + 2y₂ ≥ 4, (8)
2y₁ + y₂ ≥ 3, (9)
4y₁ + 3y₂ ≥ 5, (10)
y₁ ≥ 0, y₂ ≥ 0. (11)
Для нахождения двойственных оценок y₁ и y₂ используем вторую теорему двойственности.
Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
Если j-я компонента оптимального плана исходной задачи положительна, то j-е ограничение двойственной задачи удовлетворяется ее оптимальным решением как строгое равенство.

Теорема позволяет, если известно оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Поскольку второе ограничение прямой задачи (см. соотношение (6)) выполняется как строгое неравенство, то y₂ = 0. Так как х₂> 0, то второе ограничение двойственной задачи (см. соотношение (9)) выполняется как равенство:
2y₁ + y₂ = 3.
Итак, для получения двойственных оценок имеем систему линейных уравнений:
y₂ = 0,
2y₁ + y₂ = 3,
т.е. Y^* = (y₁ = 3/2, y₂ = 0).
Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок имеют место следующие свойства.
1. Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны). В примере недефицитным ресурсом является сырье II-го типа, поскольку y₂ = 0. Дефицитным является сырье I-го типа, так как y₁ = 3/2.
2. Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственной оценкой измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи).
Заданные в примере изменения запасов ресурсов Δb₁ = 6 и Δb₂ =−10 находятся в пределах устойчивости двойственных оценок, поэтому:
− решение двойственной задачи останется тем же: Y^* = (y₁ = 3/2, y₂ = 0);
− изменение максимального значения целевой функции (общей стоимости продукции) составит
Δf_max = y₁∙Δb₁ + y₂∙Δb₂ = (3/2)∙6 + 0∙(−10) = 9;
− новый план выпуска продукции можно найти непосредственно из системы ограничений исходной задачи, в которой х₁ = 0, х₃ = 0, а в правых частях указаны новые запасы ресурсов (b₁' = 200 + 6 = 206, b₂' = 160 − 10 = 150):
3∙0 + 2∙х₂' + 4∙0 = 206,
2∙0 + х₂' +3∙0 < 150,
откуда х₂' = 103.
Итак, максимальное значение целевой функции составит
f(Х'^*) = 4∙0 + 3∙103 + 5∙0 = 309
при оптимальном плане производства Х'^* = (х₁' = 0, х₂' = 103, х₃' = 0).
3. Двойственные оценки служат инструментом определения эффективности отдельных хозяйственных решений (технологических способов), с их помощью можно определять выгодность производства новых изделий, эффективность новых технологических способов:
если ∆_j=∑a_ijy_i – c_j≤ 0 – выгодно,
если ∆_j>0 – невыгодно.
Для изделия «Г»:
∆_Г = 5∙(3/2) + 2∙0 – 6 = 3/2.
Поскольку ∆_Г = 3/2 > 0, то делаем вывод, что изделие «Г» невыгодно для включения в план, так как затраты на его изготовление больше цены, за которую его можно продать.

Пример №2. Задача. На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных.
Требуется:
Найти оптимальный план симплекс-методом.
Найти решение двойственной задачи
Указать дефицитность ресурсов
Обосновать эффективность плана производства
Оценить целесообразность приобретения ресурса
Оценить целесообразность выпуска новой продукции

Данные:
b₁ = 25, b₂ = 30, b₃ = 42
a₁₁= 2, a₁₂= 3, a₁₃= 2, a₁₄= 1
a₂₁= 4, a₂₂= 1, a₂₃= 3, a₂₄= 2
a₃₁= 3, a₃₂= 5, a₃₃= 2,a₃₄= 2
c₁= 6, c₂= 5, c₃= 4, c₄= 3
Математическая модель прямой задачи
max (Z= 6x₁+5x2+4x3+3x4)
2x₁+3x₂+2x₃+x₄< 25
4x₁+x₂+3x₃+2x₄< 30
3x₁+5x₂+2x₃+2x₄< 42
x₁, x₂, x₃, x₄ > 0

Перейти к онлайн решению своей задачи

Математическая модель двойственной задачи
min (Z*= 25y1+30y2+42y3)
2y1+4y2+3y3> 6
3y1+y2+5y3> 5
2y1+3y2+2y3> 4
y1+2y2+2y3> 3
y1, y2, y3, y4 > 0

Стандартный вид

min (Z= -6x1-5x2-4x3-3x4)
2x1+3x2+2x3+x4+S1=25
4x1+x2+3x3+2x4+S2=30
3x1+5x2+2x3+2x4+S3=42
x1, x2, x3, x4, S1, S2, S3 > 0

Экономический смысл переменных
Xi – количество произведенной продукции
Yj – цена ресурса
Si – количество оставшегося ресурса

Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц.
Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно.
Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен.

Эффективность производства
Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно
2*1,4+4*0,8+3*0< 6 6=6 Производство 1 вида продукции эффективно
3*1,4+1*0,8+5*0< 5 5=5 Производство 2 вида продукции эффективно
2*1,4+3*0,8+2*0< 4 5,2> 4 Производство 3 вида продукции не эффективно
1*1,4+2*0,8+2*0< 3 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен.

Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса.
а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4.
2*1,4+2*0,8+2*0< 4 4,4> 4
Производство 5 вида продукции не эффективно.