Задача максимизации линейной формы  называется прямой задачей по отношению к задаче минимизации линейной формы  , которая называется двойственной. И наоборот(!) |
|
Задача максимизации линейной формы называется прямой задачей по отношению к задаче минимизации линейной формы , которая называется двойственной. И наоборот(!) |
Предприятие выпускает три вида продукции. Каждая продукция требует обработки на трех различных типах установок. Ресурс времени каждого типа установок ограничен. Известна прибыль от единицы каждого вида продукции: p1, p2, p3. Если количество выпускаемой продукции каждого вида: x1, x2, x3; тогда прибыль определяется по формуле
при ограничениях следующего вида:
,
,
,
,
где b1, b2, b3 – ресурсы времени установок первого, второго и третьего типов. Величины aij определяют количество ресурса времени установки i-го типа, которое необходимо для выпуска одной единицы продукции j-го вида.
Двойственная к ней задача будет иметь вид:
с ограничениями:
.
Здесь u1 - это оценка (цена), соответствующая одной единице ограниченного ресурса, соответствующего первой установке. И она равна величине, на которую могла бы увеличиться суммарная прибыль, если бы количество этого ограниченного ресурса увеличилось на единицу, и если это увеличение было бы использовано оптимально. Иными словами, u1 – это количество прибыли, недополученной из-за нехватки единицы ограниченного ресурса b1. Аналогичным образом можно интерпретировать смысл величин u2 и u3.
Пусть имеются прямая и двойственная задачи следующего вида:
| Прямая задача:
| Представим ограничения в виде:
|
| Двойственная к ней задача:
|
|
Для ограничений прямой задачи симплексная таблица имеет вид:
| -x1 | … | -xs | … | -xn | 1 | |
| y1 = | a11 | … | a1s | … | a1n | b1 |
| … | … | … | … | … | … | … |
| yr = | ar1 | … | ars | … | arn | br |
| … | … | … | … | … | … | … |
| ym = | am1 | … | ams | … | amn | bm |
 = |
-p1 | … | -ps | … | -pn | 0 |
Пусть ars - разрешающий элемент, сделаем шаг модифицированного жорданова исключения:
| -x1 | … | -yr | … | -xn | 1 | |
| y1 = | b11 | … | -a1s | … | b1n | b1,n+1 |
| … | … | … | … | … | … | … |
| xs = | ar1 | … | 1 | … | arn | br |
| … | … | … | … | … | … | … |
| ym = | bm1 | … | -ams | … | bmn | bm,n+1 |
| = |
bm+1,1 | … | ps | … | bm+1,n | bm+1,n+1 |
Здесь bij = aij . ars - arj . ais и всю данную таблицу следует разделить еще на ars.
Симплексную таблицу для двойственной задачи запишем, развернув ее на 90o. Получаем:
| v1 = | … | vs = | … | vn = | W = | |
| u1 | a11 | … | a1s | … | a1n | b1 |
| … | … | … | … | … | … | … |
| ur | ar1 | … | ars | … | arn | br |
| … | … | … | … | … | … | … |
| um = | am1 | … | ams | … | amn | bm |
| 1 | -p1 | … | -ps | … | -pn | 0 |
Пусть ars - направляющий элемент. Сделаем шаг обыкновенного жорданова исключения (отличие от модифицированного состоит в том, что элементы в разрешающей строке меняют знаки, а в столбце знаки сохраняются; в остальном преобразование остается тем же):
| v1 | … | ur | … | vn | W = | |
| u1 = | b11 | … | -a1s | … | b1n | b1,n+1 |
| … | … | … | … | … | … | … |
| vs | ar1 | … | 1 | … | arn | br |
| … | … | … | … | … | … | … |
| um | bm1 | … | -ams | … | bmn | bm,n+1 |
| 1 | bm+1,1 | … | ps | … | bm+1,n | bm+1,n+1 |
Здесь bij = aij . ars - arj . ais и всю данную таблицу также следует разделить еще на ars.
Не следует забывать при преобразованиях, что в данном случае у нас таблица развернута.
Таким образом, нетрудно заметить, что шаг модифицированного жорданова исключения над симплексной таблицей прямой задачи соответствует шагу обыкновенного жорданова исключения над симплексной таблицей двойственной задачи. Эти взаимно двойственные задачи можно совместить в одной симплексной таблице.
| v1 = -x1 |
… | vs = -xs |
… | vn = -xn |
W = 1 |
|
| u1 y1 = |
a11 | … | a1s | … | a1n | b1 |
| … | … | … | … | … | … | … |
| ur yr = |
ar1 | … | ars | … | arn | br |
| … | … | … | … | … | … | … |
| um ym = |
am1 | … | ams | … | amn | bm |
| 1 |
-p1 | … | -ps | … | -pn | 0 |
Можно показать, что, решая основную задачу линейного программирования, решаем и двойственную к ней. И наоборот. Причем, max Q = min W.
Пусть рассматривается пара двойственных задач:
|
|
| Прямая | Двойственная |
Если одна из этих задач обладает оптимальным решением, то и двойственная к ней задача также имеет оптимальное решение. Причем экстремальные значения соответствующих линейных форм равны: max Q = min W.
Если же у одной из этих задач линейная форма не ограничена, то двойственная к ней задача противоречива.
Доказательство: Пусть прямая задача имеет конечное решение и получена окончательная симплексная таблица:
| u1 = | …. | us = | vs+1 = | …. | vn = | W = | ||
| -y1 | …. | -ys | -xs+1 | …. | -xn | 1 | ||
| v1 | x1= | b1,1 | …. | b1,s | b1,s+1 | …. | b1,n | b1,n+1 |
| …. | …. | …. | …. | …. | …. | …. | …. | …. |
| vs | xs= | bs,1 | …. | bs,s | bs,s+1 | …. | bs,n | bs,n+1 |
| us+1 | ys+1= | bs+1,1 | …. | bs+1,s | bs+1,s+1 | …. | bs+1,n | bs+1,n+1 |
| …. | …. | …. | …. | …. | …. | …. | …. | …. |
| um | ym= | bm,1 | …. | bm,s | bm,s+1 | …. | bm,n | bm,n+1 |
| 1 | Q = | q1 = | …. | qs = | qs+1 = | …. | qn = | q0 |
Так как данная таблица, по предположению, соответствует оптимальному решению
прямой задачи, то
b1, n+1 ≥ 0, ..., bm, n+1 ≥ 0
и q1 ≥ 0, ..., qn ≥ 0. При этом max Q = q0
достигается при y1 = ... = ys = xs+1 = ... = xn = 0.
Рассмотрим полученную таблицу двойственной задачи. Полагая значения переменных слева (небазисных) равными нулю: v1 = ... = vs = us+1 = ... = um = 0, найдем u1 = q1 ≥ 0, …, us = qs ≥ 0, vs+1 = qs+1 ≥ 0, …, vn = qn ≥ 0.
Следовательно, получено опорное решение: u1 = q1, ... us = qs, us+1 = 0, ... un = 0.
Из последнего столбца, W = b1,n+1 . v1 + ... + bs,n+1 . vs + bs+1,n+1 . us+1 + ... + bm,n+1 . um + q0 в точке v1 = ... = vs = us+1 = ... = um = 0 будет минимальным в силу того, что bi,n+1 ≥ 0, i =1, ..., m. Следовательно, max Q = min W.
Пусть теперь линейная форма прямой задачи неограничена, т.е. для некоторой верхней
переменной, например, ys, соответствующий коэффициент qs < 0,
а все коэффициенты этого столбца симплексной таблицы неположительны:
b1,s ≤ 0,
b2,s ≤ 0, …, bm,s ≤ 0. Тогда из таблицы для двойственной задачи:
us = b1,s . v1 + ... + bs,s . vs + bs+1,s . us+1 + ... + bm,s . um + qs ≤ qs < 0,
то есть система ограничений двойственной задачи противоречива. Так как из неотрицательности v1, ..., vs, us+1, ..., um следует неположительность us (нельзя сделать ее положительной), то есть система несовместна.
Теорема доказана.
Если хотя бы одно оптимальное решение одной из двойственных задач обращает i-е ограничение этой задачи в строгое неравенство, то i-я компонента (т.е. xi или ui) каждого оптимального решения второй двойственной задачи равна нулю.
Если же i-я компонента хотя бы одного оптимального решения одной из двойственных задач положительна, то каждое оптимальное решение другой двойственной задачи обращает i-е ограничение в строгое равенство.
Т.е. оптимальные решения 
и 
пары двойственных задач удовлетворяют условиям
Доказательство: Пусть и – оптимальные решения пары
двойственных задач. Тогда для 
, 
они удовлетворяют следующим ограничениям:
.
Умножим эту систему, соответственно, на 
и 
,
и просуммируем полученные выражения:
. (*)
Из основной теоремы двойственности следует
.
И с учетом (*) получаем:
, 
.
Первое из этих выражений можем переписать в виде
,
и так как все и выражения в скобках неотрицательны, то опуская
å, получим: 
.
Аналогично получим: 
.
Теорема доказана.
Справедлива и обратная теорема.
