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

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

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

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

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

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

Прямая Двойственная
Целевая функция (max) Правая часть ограничений
Правая часть ограничений Целевая функция (min)
A — матрица ограничений A T – матрица ограничений
i -ое ограничение: ≤ 0, (≥ 0) Переменная yi ≥ 0, (≤ 0)
i -ое ограничение: = 0 Переменная yi≠ 0
Переменная xj ≥ 0 (≤ 0) j -ое ограничение: ≤ 0 (≥ 0)
Переменная xj ≠ 0 j -ое ограничение: = 0

max → min

Прямая Двойственная
Целевая функция (min) Правая часть ограничений
Правая часть ограничений Целевая функция (max)
A — матрица ограничений A T – матрица ограничений
i -ое ограничение: ≥ 0, (≤ 0) Переменная yi ≥ 0, (≤ 0)
i -ое ограничение: = 0 Переменная yi≠ 0
Переменная xj ≥ 0 (≤ 0) j -ое ограничение: ≤ 0 (≥ 0)
Переменная xj ≠ 0 j -ое ограничение: = 0

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

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

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

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

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

Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности. Первая теорема двойственности . Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*) = G(y*), где х *, у * — оптимальные решения задач I и II Вторая теорема двойственности . Планы х * и у * оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х * и у * — допустимые решения прямой и двойственной задач и если c T x*=b T y*, то х * и у * – оптимальные решения пары двойственных задач. Третья теорема двойственности . Значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений — неравенств прямой задачи на величину целевой функции этой задачи:
Δf(x) = biyi Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Значения переменных двойственной задачи yi, в оптимальном плане называют объективно обусловленными, или двойственными оценками. В прикладных задачах двойственные оценки yi часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов. Свойство взаимно двойственных задач

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

Итак, имеем исходную задачу I и ее оптимальное решение х * = (0, 40, 0, 100) и F(х*) = 700. Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи II у* = (у1, у2, у3), не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х *. Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

5x1+0,4x2+2x3+0,5x4≤400 5*0+0,4*40+2*0 + 0,5*100 = 66 Ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0.
5x2+x3+x4≤300 5*40 + 0 + 100 = 300 = 300 Ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2 ≠ 0)
x1 + x3 + x4 ≤ 100 0 + 0 + 100 = 100 = 100 y3 ≠ 0
x1 ≥ 0 x1 = 0 Первое ограничение в двойственной задаче будет неравенством
5y1 + y3 ≥ 3
x2 ≥ 0 x2 = 40 > 0 Второе ограничение в двойственной задаче будет равенством
0,4y1 + 5y2 = 5
x3 ≥ 0 x3 = 0 Третье ограничение в двойственной задаче будет неравенством
2y1 + y2 + y3 ≥ 4
x4 ≥ 0 x4 = 100 > 0 Четвертое ограничение в двойственной задаче будет равенством
0,5y1 + y2 + y3 = 5

Поскольку 1, 5, 7 неравенства строгие (имеют знак «»), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:
y1=0
0.4y1+5y2=5
0.5y1+y2+y3=5 или
y1=0, y2=1, y3=4
т.е. у* = (0, 1, 4) — оптимальное решение. Заметим, что действительно G(y*) = 400y1+ 300y2+ 100y3= 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*). Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.
Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:
Установив такую связь, можно заметить, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл.), мы фактически решим и задачу II.
Запишем таблицу, учитывая соответствие между переменными х i и yj .

у4 у2 у6 у3
базисные х1 х6 х3 х7 свободные
у1 х5 334
у5 х2 40
у7 х4 100
F 1 1 1 4 700

В силу соответствия и II теоремы двойственности переменные у1, у5, у7 обязаны равняться 0, т.к. х5, х2, х4>0 строго. А переменные у 4, у 2, у 6, у 3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т.к. им соответствующие переменные х1, х6, х3, х7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных: у* = (у1*, у2*, у3*, у4*, у5*, у6*, у7*) = (0, 1, 4, 1, 0, 1, 0). Мы научились по решению исходной задачи находить решение двойственной. Это оказалось возможно благодаря глубокой связи между переменными хi и yj. Осталось разобраться, каково экономическое содержание этих взаимосвязей.

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

Задача 2
Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.
3x1+x2≥12
x1+2x2≥14
4x1+11x2≥68 Теорема равновесия. Пусть X*=(x1*. xn*) и Y*=(y1*. yn*) — допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:

Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением.
Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.
В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений. Пример 2
Составить двойственную задачу и найти ее решение по теореме равновесия
x2-2x3+2x4-2x5≤4
-2x1-2x2+2x3+2x4+x5≥2
xi≥0, i= 1,5
Z=10x1-9x2-19x3-13x4-11x5 → max, если известно решение исходной задачи: Zmax=(3;4;0;0;0).
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.

Источник

Оцените статью