Графический метод теорема двойственности

Основы теории линейного программирования

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

1.1.
Двойственные задачи линейного
программирования
.
Линейное программирование занимается
изучением экстремальных задач, в которых
ищется максимум или минимум линейной
функции в арифметическом конечномерном
векторном пространстве на множестве
векторов, удовлетворяющих конечному
числу линейных уравнений и (или)
неравенств.

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

Задача
I.
заданы вещественные числа


,

,

,

,

и
фиксированные разбиения каждого из
множеств


,

на
два непересекающихся подмножества


,

;

,

.

Требуется
максимизировать линейную функцию


(1)

на
множестве n-мерных
векторов.


, (2)

удовлетворяющих
условиям


,

; (3)


,

; (4)


,


. (5)

Вектор
(2), удовлетворяющий условиям (3)–(5),
называется допустимым,
а искомый допустимый вектор, доставляющий
максимум функции (1) – оптимальным.

Наряду
с задачей 1 рассматривается следующая
двойственная
к ней
экстремальная задача.

Задача
I*.
При исходных данных задачи I
минимизировать
линейную функцию


(6)

на
множестве m-мерных
векторов


, (7)

удовлетворяющих
условиям


,

; (8)


,

;
(9)


,

.
(10)

Вектор
(7), удовлетворяющий условиям (8)–(10)
называется допустимым,
искомый допустимый вектор, доставляющий
минимум функции (6) – оптимальным.

Каждому
ограничению

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

,
а каждой переменной

задачи I
– ограничение с номером j
задачи I*.
При этом переменная

неотрицательная, если

.
Аналогично в задаче I*
ограничения, отвечающие неотрицательным


,
задаются в виде неравенств. Сказанное,
с учетом одинаковых исходных данных
<
>
позволяют без излишней формализации
по заданной задаче I
записать двойственную ей задачу I*.

Пример
1
. Записать
задачу, двойственную к следующей задаче
ЛП. Максимизировать линейную функцию

μ(x)=2х1
х2
+ 3х3
+ х4
– 5х5

на
множестве векторов

х=(х1,
х2,
х3,
х4,
х5),

удовлетворяющих
условиям

х1

0, х2
≥ 0, х4
≥ 0,

3х1+
х2
– 4х3+
х5
– 6 ≥ 0,

3х2+4х3
– 2х4
+1 ≥ 0,

2х1
+ х3
– 3х4
– 2х5
= 0.

В
этой задаче I={1,2,3};
I1={3};
I2={1,2};
J={1,2,3,4,5};
J1={3,5};
J2
={1,2,4}.

Тогда
в двойственной задаче требуется
минимизировать линейную функцию

ν(y)=
– 6y1
+ y2

на
множестве векторов

y=(y1,
y2,
y3),

удовлетворяющих
условиям:

у1
≥ 0, у2
≥ 0,

3у1
+ 2у2
+ 2
≤ 0,

у1
+ 3у2
– 1 ≤ 0,

–4у1
+ 4у2
+ у3
+ 3 = 0,

– 2у2
– 3у3
+ 1 ≤ 0,

у1
– 2у3
– 5=0.

Достаточный
признак оптимальности в краткой форме.
Для
оптимальности допустимого вектора (2)
в задаче I
достаточно, чтобы в задаче I*
нашелся допустимый вектор (7),
удовлетворяющий условию

μ(x)
= ν(y) (11)

при
этом допустимый вектор (7) является
оптимальным в задаче I*.

Достаточный
признак оптимальности в развернутой
форме
.
Для
оптимальности допустимого вектора (2)
в задаче I
достаточно существования m-мерного
вектора

y
= (y1,
y2,…,
ym),

удовлетворяющего
следующим условиям:

а)
yj
≥ 0,

;

б)

,

;

в)

,

;

г)

,
если xj>0,

;

д)
уi
= 0, если

,

.

При
этом вектор y = (y1y2,…, ym)
является оптимальным в задаче I*.

Заметим,
что ограничения а),б) и в) совпадают с
условиями допустимости вектора (7) в
задаче I*.

1.2.Графический
метод решения задачи линейного
программирования.

Наглядным является графический метод
решения основной задачи. Воспользуемся
им для предварительного решения и
анализа содержательной задачи ЛП. Однако
он применим, когда n≤3.

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

Таблица
1 Таблица
2

промежуточный

продукт

выход из 1т

сырья,
кг

1

460

2

200

3

340

промежуточный

продукт

расходы п. пр. на
1т конечного продукта., кг

1

2

1

250

800

2

250

200

3

500

Технологический
процесс состоит из двух этапов. На первом
этапе поступающее сырье перерабатывается
в три промежуточных продукта, которые
на втором этапе используются для
получения конечной продукции. Выход
промежуточных продуктов из одной тонны
сырья указан в таблице 1., а расход на
производство одной тонны конечной
продукции каждого вида – в таблице 2.
При этом цена тонны конечной продукции
первого вида 50 у.е., а второго – 60 у.е.

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

μ(х1,
х2)
= 50х1
+
60х2. (12)

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

х1
≥ 0, х2
≥ 0,

250х1
+ 800х2
≤ 460,

250х1
+ 200х2

200, (13)

500х1+
0х2
≤ 340

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

Каждой
паре неотрицательных вещественных
чисел х1
и х2
сопоставим в первом квадранте плоскости
х1 0 х2
точку М(х1х2).
Точки (х1х2),
удовлетворяющие условиям (13), заполнят
пятиугольник 0АВСД
(рис. 1), ограниченный осями координат и
прямыми

250х1
+ 800х2
= 460,

250х1
+ 200х2
= 200,

500х1
+ 0 х2
= 340.

Величина
(12) пропорциональна расстоянию точки
М(х1х2)
от прямой ОЕ,
задаваемой уравнением 50х1+60х2=0.
поэтому оптимальной программе отвечает
точка пятиугольника, наиболее удаленная
от прямой ОЕ.

Рис.
1. Иллюстрация графического решения
примера 1

Таковой
в рассматриваемом случае является точка
В,
в которой пересекаются прямые

250х1
+ 800х2
= 460,

250х1
+ 200х2
= 200.

Решая
систему уравнений, находим искомую
оптимальную производственную программу
х0=(0.453;0.433),
при которой суммарная цена выпускаемой
продукции в расчете на одну тонну сырья
составляет

μ=50*0.453+60*0.433
у.е.

Используя теперь
двойственную задачу и признак оптимальности
в развернутой форме, убедимся в
правильности полученного решения.
Запишем рассматриваемую задачу в
приведенной ранее стандартной форме.

Задача
I.
максимизировать.

μ(х1,
х2)=
50х1
+ 60х2

на
множестве векторов

х=(х1,
х2),

удовлетворяющих
условиям:

х1
≥ 0, х2
≥ 0,

–250х1
– 800х2
+ 460 ≥ 0,

–250х1
– 200х2
+ 200 ≥ 0,
(14)

–500х1
+ 340 ≥ 0.

Это
случай, когда I={1,2},
I1=
Ø , I2
=I;
J={1,2,3},
J1=Ø,
J2=J,
называется симметричной канонической
формой. Двойственной к ней является
следующая

Задача
I*.
Минимизировать

ν(у)=460у1
+ 200у2
+ 340у3

на
множестве векторов

у=(у1,
у2,
у3),
у1
≥ 0, у2
≥ 0,
у3
≥ 0,

удовлетворяющих
условиям:

а)
–250у1
– 250у2
– 500у3
+ 50 ≤ 0,

(15)

– 800у1
– 200у2
+ 60 ≤ 0.

Проверим
выполнение оптимальности для полученного
графически вектора х0=(0,453;0,433).
Прежде всего, отметим, что этот вектор
допустимый и его координаты положительные,
поэтому неравенства (15), должны выполняться
как равенства, т.е. имеем

б)
– 250у1
– 250у2
– 500у3
+ 50 ≤
0, (16)

– 800у1
200у2
+ 60 = 0.

Для
исследуемого вектора х0
первые два
неравенства системы (14) выполняются как
равенства, а третье ограничение – как
строгое неравенство, следовательно
имеем

в) у3=0. (17)

Таким
образом, для оптимальности допустимого
вектора х0=(0.453; 0.433)
достаточно существования вектора
у0=(у1у2у3)
с неотрицательными компонентами,
удовлетворяющего условиям (15),
(16) и (17).
Решая систему уравнений (16), (17). находим
вектор у0=(0.033; 0.165;0)
с неотрицательными компонентами
удовлетворяющими (15). Таким образом, все
условия (а), (б) и (в) для вектора у0
выполнены.

Следовательно,
найденный графически вектор х0
является оптимальным в задаче I,
а вектор у0
– оптимальный
в задаче I*.
При этом

μ(x0)
= ν(y0)=48.63.

Выясним
экономический смысл для рассмотренного
примера планирования производственной
программы. Каждому ограничению (14),
несущему смысл расхода промежуточного
продукта, сопоставим оценку уi
единицы этого продукта. Тогда в задаче
I*
требуется минимизировать суммарную
оценку промежуточных продуктов на
множестве векторов у=(у1у2у3),
неотрицательные компоненты которых
имеют смысл оценки соответствующего
промежуточного продукта при условии
запрета на существование «сверх
рентабельного» конечного продукта. А
именно толкование условий (а) означает:
оценка затраченных промежуточных
продуктов на «производство единицы
конечного продукта не может быть менее
его цены». Вместе с тем условия (б)
означают «производство только
«рентабельных» конечных продуктов», а
условий (в) «равенство нулю оценки
избыточного промежуточного продукта».

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

Рассмотрим решение задач с использованием теорем двой­ственности.

Решим исходную задачу графическим методом, получим Опт = (4, 1), при этом L()Mах = 3.

На основании 1-й теоремы двойственности

Так как X1, Х2 > 0, то по 2-й теореме двойственности систе­му ограничений двойственной задачи можно записать в виде равенств:

Подставим Опт в систему ограничений исходной задачи:

Тогда система ограничений двойственной задачи примет вид

Откуда Опт = (0, 2/3, 1/3), при этом S()Min = 3.

Пусть дано решение двойственной задачи Опт = (0, 2/3, 1/3), S()Min = 3, найдем решение исходной.

По 1-й теореме двойственности L()Max = S()Min = 3. Так как У2, Y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

Откуда Опт = (4,1), при этом L()Mах = 3.

Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:

При ограничениях:

Из табл. 22.1 следует, что Опт = (0, 2/3, 1/3), S()Min = 3.

На основании 1-й теоремы двойственности получаем

Решение другой задачи найдем по соответствию между пе­ременными:

Значение Xj определяем по последней симплексной таблице в строке ΔI в соответствующем столбце, причем значения Xj ­берем по модулю:

Таким образом, решение исходной задачи:

Если исходная задача решена симплексным методом, то ре­шение двойственной задачи может быть найдено по формуле

Где С — матрица-строка коэффициентов при базисных пере­менных целевой функции в оптимальном решении исходной за­дачи; А-1 — обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы огра­ничений исходной задачи в оптимальном решении.

Решим симплексным методом исходную задачу вида

При ограничениях:

Из табл. 22.2 следует, что Опт = (4,1), L()max = 3. Мат­рицы записываются в виде

Тогда

Таким образом, решение двойственной задачи следующее:

< Предыдущая   Следующая >

Двойственная задача[1] для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом:

  • Каждая переменная в прямой задаче становится ограничением двойственной задачи;
  • Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
  • Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.

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

Теорема о сильной двойственности утверждает, что более того, если прямая задача имеет оптимальное решение, то двойственная задача имеет также оптимальное решение, и эти два оптимума равны[2].

Эти теоремы принадлежат более широкому классу теорем двойственности в оптимизации. Теорема о сильной двойственности является одним из случаев, в котором разрыв двойственности (разрыв между оптимумом прямой задачи и оптимумом двойственной) равен 0.

О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна[3]. Там же можно прочитать об экономическом смысле задачи[4].

Построение двойственной задачи[править | править код]

Если дана прямая задача линейного программирования, для построения двойственной задачи может быть использован следующий алгоритм[5].

Пусть прямая задача определена как:

Двойственная задача строится следующим образом.

  • Каждое ограничение прямой задачи становится двойственной переменной. Таким образом, получаем m переменных: {displaystyle y_{1},ldots ,y_{m}}.
  • Знак ограничения каждой двойственной переменной «противоположен» знаку ограничения в прямой задаче. Таким образом, «{displaystyle geqslant b_{j}}» становится {displaystyle y_{j}leqslant 0}, «{displaystyle leqslant b_{j}}» превращается в {displaystyle y_{j}geqslant 0}, а «{displaystyle =b_{j}}» превращается в {displaystyle y_{j}in mathbb {R} }.
  • Целевая функция двойственной задачи равна (минимизировать) {displaystyle b_{1}y_{1}+cdots +b_{m}y_{m}}
  • Каждая переменная прямой задачи становится двойственным ограничением. Таким образом, получаем n ограничений. Коэффициент двойственной переменной в двойственных ограничениях равен коэффициенту переменной из ограничения прямой задачи. Таким образом, каждое ограничение i есть: {displaystyle a_{1i}y_{1}+cdots +a_{mi}y_{m}lesseqqgtr c_{i}}, где символ перед c_{i} аналогичен ограничению на переменную i в прямой задаче. Так, {displaystyle x_{i}leqslant 0} превращается в «{displaystyle leqslant c_{i}}», {displaystyle x_{i}geqslant 0} превращается в «{displaystyle geqslant c_{i}}», а {displaystyle x_{i}in mathbb {R} } превращается в «{displaystyle =c_{i}}».

Из этого алгоритма легко видеть, что двойственная задача двойственной задачи совпадает с прямой задачей.

Векторные формулировки[править | править код]

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

Прямая Двойственная Примечания
Максимизировать {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях {displaystyle mathbf {A} mathbf {x} leqslant mathbf {b} ,mathbf {x} geqslant 0} Минимизировать {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях {displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0} Такая задача называется «симметричной» двойственной задачей
Максимизировать {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях {displaystyle mathbf {Ax} leqslant mathbf {b} } Минимизировать {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях {displaystyle mathbf {A} ^{T}mathbf {y} =mathbf {c} ,mathbf {y} geqslant 0} Такая задача называется «асимметричной» двойственной задачей
Максимизировать {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях {displaystyle mathbf {Ax} =mathbf {b} ,mathbf {x} geqslant 0} Минимизировать {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях {displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} }

Теоремы двойственности[править | править код]

Ниже мы предполагаем, что прямая задача поставлена как «Максимизировать {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях [ограничения]», а двойственная задача поставлена как «Минимизировать {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях [ограничения]».

Слабая двойственность[править | править код]

Теорема о слабой двойственности утверждает, что для каждого допустимого решения x прямой задачи и каждого допустимого решения y двойственной задачи: {displaystyle mathbf {c} ^{T}mathbf {x} leqslant mathbf {b} ^{T}mathbf {y} }. Другими словами, значение целевой функции для каждого допустимого решения двойственной задачи является верхней границей целевой функции прямой задачи, а значение целевой функции любого допустимого решения прямой задачи является нижней границей для целевой функции двойственной задачи. Из этого следует, что

{displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} leqslant min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }

В частности, если прямая задача не ограничена (сверху), то двойственная задача не имеет допустимого решения, а если не ограничена двойственная задача (снизу), то не имеет допустимого решения прямая задача.

Теорему о слабой двойственности относительно легко доказать[6]. Предположим, что прямая задача линейного программирования звучит как «Максимизировать {displaystyle mathbf {c} ^{T}mathbf {x} } при ограничениях {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {x} geqslant 0}». Предположим, что мы создаём линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты при x не меньше {displaystyle mathbf {c} ^{T}}. Эта линейная комбинация даёт нам верхнюю грань для целевой функции. Переменные y двойственной задачи являются коэффициентами этой линейной комбинации. Двойственная задача пытается найти такие коэффициенты, которые минимизируют результирующую правую часть. Это даёт задачу линейного программирования «Минимизировать {displaystyle mathbf {b} ^{T}mathbf {y} } при ограничениях {displaystyle mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0}»[7]. См. «Простой пример» ниже.

Сильная двойственность[править | править код]

Теорема о сильной двойственности утверждает, что границы, определяемые теоремой о слабой двойственности жёсткие, то есть

{displaystyle max _{mathbf {x} }mathbf {c} ^{T}mathbf {x} =min _{mathbf {y} }mathbf {b} ^{T}mathbf {y} }

Теорему о сильной двойственности существенно труднее доказать. Обычно доказательство использует теорему о слабой двойственности в качестве леммы[8].

Одно доказательство использует симплекс-метод и опирается на доказательство того, что, при подходящем правиле выбора выводимого столбца, он даёт правильное решение. Доказательство устанавливает, что, когда симплекс-метод завершается решением прямой задачи линейного программирования, можно из конечной таблицы прочесть решение двойственной задачи. Таким образом, после прогона симплекс-алгоритма мы получим решения как прямой, так и двойственной задачи одновременно[9].

Другое доказательство использует лемму Фаркаша[10]

Теоретическое приложение[править | править код]

Слабая двойственность имеет интересное теоретическое приложение — она показывает, что нахождение отдельного допустимого решения настолько же трудно, насколько нахождение оптимального допустимого решения. Предположим, что мы имеем систему предсказывания, что данная задача линейного программирования находит произвольное допустимое решение (если оно существует). Если задача звучит как «Максимизировать {displaystyle mathbf {c} ^{mathbf {x} }} при ограничениях {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {x} geqslant 0}», мы можем построить другую задачу путём комбинирования её с двойственной ей задачей. Комбинированная задача имеет как x, так и y в качестве переменных:

Максимизировать 1

при ограничениях {displaystyle mathbf {Ax} leqslant mathbf {b} ,mathbf {A} ^{T}mathbf {y} geqslant mathbf {c} ,mathbf {c} ^{T}mathbf {x} geqslant mathbf {b} ^{T}mathbf {y} ,mathbf {x} geqslant 0,mathbf {y} geqslant 0}

Если комбинированная задача имеет допустимое решение (x,y), то по слабой двойственности {displaystyle mathbf {c} ^{T}mathbf {x} =mathbf {b} ^{T}mathbf {y} }. Таким образом, x должно быть максимальным решением прямой задачи, а y должно быть минимальным решением двойственной задачи. Если комбинированная задача не имеет допустимого решения, то и прямая задача допустимого решения не имеет.

Примеры[править | править код]

Простой пример[править | править код]

Рассмотрим прямую задачу с двумя переменными и одним ограничением:

Максимизировать {displaystyle 3x_{1}+4x_{2}}
При условиях
{displaystyle {begin{aligned}&5x_{1}+6x_{2}=7\&x_{1}geqslant 0,x_{2}geqslant 0end{aligned}}}

Применив вышеизложенный рецепт построения двойственной задачи, получим задачу с одной переменной и двумя ограничениями:

Минимизировать {displaystyle 7y_{1}}
При условиях

{displaystyle {begin{aligned}&&5y_{1}geqslant 3\&&6y_{1}geqslant 4\&&y_{1}in mathbb {R} end{aligned}}}

Легко видеть, что максимум прямой задачи достигается, когда переменная x1 минимизируется до её нижней границы (0), а переменная x2 максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен {displaystyle 4cdot 7/6=14/3}.

Аналогично, минимум двойственной задачи достигается, когда y1 минимизируется до его нижнего значения при ограничениях: первое ограничение даёт значение 3/5, в то время как второе даёт более строгую границу 4/6, так что фактический минимум равен 4/6 и минимум целевой функции равен {displaystyle 7cdot 4/6=14/3}.

Согласно теореме о сильной двойственности максимум прямой задачи равен минимуму двойственной.

Мы используем этот пример для иллюстрации доказательства теоремы о слабой двойственности. Предположим, что в прямой задаче линейного программирования мы хотим получить верхнюю границу целевой функции {displaystyle 3x_{1}+4x_{2}}. Мы можем использовать ограничение, умноженное на некоторый коэффициент, скажем, y_1. Для любого y_1 мы имеем: {displaystyle y_{1}cdot (5x_{1}+6x_{2})=7y_{1}}. Теперь, если {displaystyle y_{1}cdot 5x_{1}geqslant 3x_{1}} и {displaystyle y_{1}cdot 6x_{2}geqslant 4x_{2}}, то {displaystyle y_{1}cdot (5x_{1}+6x_{2})geqslant 3x_{1}+4x_{2}}, так что {displaystyle 7y_{1}geqslant 3x_{1}+4x_{2}}. Следовательно, целевая функция двойственной задачи является верхней границей целевой функции прямой задачи.

Пример фермера[править | править код]

Рассмотрим фермера, который может выращивать пшеницу и ячмень на площади L, используя удобрения F и пестициды P.
Чтобы вырастить одну единицу пшеницы на единице площади, нужно использовать F_{1} единиц удобрений и P_1 единиц пестицидов.

Прямой задачей будет решение фермера, сколько пшеницы (x_{1}) и ячменя (x_{2}) выращивать, если их продажные цены равны S_{1} и S_{2} за единицу.

Максимизировать:
{displaystyle S_{1}cdot x_{1}+S_{2}cdot x_{2}} (максимизировать доход от выращивания пшеницы и ячменя)
при ограничениях:
{displaystyle x_{1}+x_{2}leqslant L} (фермер не может использовать больше земли, чем у него есть)
{displaystyle F_{1}cdot x_{1}+F_{2}cdot x_{2}leqslant F} (фермер не может использовать больше удобрений, чем есть в наличии)
{displaystyle P_{1}cdot x_{1}+P_{2}cdot x_{2}leqslant P} (фермер не может использовать больше пестицидов, чем у него есть)
{displaystyle x_{1},x_{2}geqslant 0} (нельзя вырастить отрицательную величину зерна).

Для двойственной задачи предположим, что y единиц цены для каждой из этих видов продукта (входы) представлены группой планирования. Задачей группы планирования является минимизация полной стоимости производство продукции при заданных величинах потребления ресурсов с определением стоимости единицы ресурса (выход). Это соответствует следующей задаче линейного программирования:

Минимизировать
{displaystyle Lcdot y_{L}+Fcdot y_{F}+Pcdot y_{P}} (минимизировать полную стоимость производства продукции как «целевая функция»)
при ограничениях:
{displaystyle y_{L}+F_{1}cdot y_{F}+P_{1}cdot y_{P}geqslant S_{1}} (фермер должен получить не менее S1 за единицу пшеницы)
{displaystyle y_{L}+F_{2}cdot y_{F}+P_{2}cdot y_{P}geqslant S_{2}} (фермер должен получить не менее S2 за единицу ячменя)
{displaystyle y_{L},y_{F},y_{P}geqslant 0} (цены не могут быть отрицательными).

В матричной форме:

Минимизировать: {displaystyle {begin{bmatrix}L&F&Pend{bmatrix}}{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}}
при условиях: {displaystyle {begin{bmatrix}1&F_{1}&P_{1}\1&F_{2}&P_{2}end{bmatrix}}{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}geqslant {begin{bmatrix}S_{1}\S_{2}end{bmatrix}},,{begin{bmatrix}y_{L}\y_{F}\y_{P}end{bmatrix}}geqslant 0.}

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

Каждой переменной в пространстве прямой задачи соответствует неравенство в пространстве двойственной задачи. Каждому неравенству в пространстве прямой задачи соответствует переменная в пространстве двойственной задачи.

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

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

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

Недопустимая задача[править | править код]

Задача линейного программирования может также быть неограниченной или недопустимой. Теория двойственности говорит нам, что:

  • Если прямая задача является неограниченной, то двойственная задача недопустима;
  • Если двойственная задача является неограниченной, то прямая задача недопустима[11].

Однако может быть, что обе задачи, как двойственная, так и прямая, недопустимы. Вот пример:

Приложения[править | править код]

Теорема о максимальном потоке и минимальном разрезе является специальным случаем теоремы о сильной двойственности — максимизация потока является прямой задачей линейного программирования, а минимизация разреза является двойственной задачей линейного программирования. См. теорему Форда — Фалкерсона.

Другие теоремы, связанные с графами, могут быть доказаны с помощью теоремы о сильной двойственности, в частности, теорема Кёнига[12].

Теорема о минимаксе[en] для игр с нулевой суммой может быть доказана с помощью теоремы о сильной двойственности[13].

Альтернативный алгоритм[править | править код]

Иногда можно найти более интуитивный способ получить двойственную задачу без применения матрицы задачи. Рассмотрим следующую задачу линейного программирования:

Минимизировать {displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}}
при условиях
{displaystyle sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}geqslant g_{j},1leqslant jleqslant n}
{displaystyle f_{i}x_{i}+sum _{j=1}^{n}b_{ij}t_{j}geqslant h_{i},1leqslant ileqslant m}
{displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n}

Мы имеем {displaystyle m+n} условий и все переменные неотрицательны. Нам нужно определить {displaystyle m+n} двойственных переменных: yj и si. Мы получаем:

Минимизировать {displaystyle sum _{i=1}^{m}c_{i}x_{i}+sum _{j=1}^{n}d_{j}t_{j}}
при условиях
{displaystyle sum _{i=1}^{m}a_{ij}x_{i}cdot y_{j}+e_{j}t_{j}cdot y_{j}geqslant g_{j}cdot y_{j},1leqslant jleqslant n}
{displaystyle f_{i}x_{i}cdot s_{i}+sum _{j=1}^{n}b_{ij}t_{j}cdot s_{i}geqslant h_{i}cdot s_{i},1leqslant ileqslant m}
{displaystyle x_{i}geqslant 0,,t_{j}geqslant 0,1leqslant ileqslant m,1leqslant jleqslant n}
{displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}

Поскольку это задача минимизации, нам хотелось бы получить двойственную задачу, которая является нижней границей прямой задачи. Другими словами, нам хотелось бы, чтобы сумма всех правых частей ограничений была максимальной при условиях, что для каждой переменной прямой задачи сумма её коэффициентов не превосходит коэффициента в линейной функции. Например, x1 появляется в n+1 ограничениях. Если мы суммируем коэффициенты ограничения, мы получим {displaystyle a_{1,1}mathbf {y} _{1}+a_{1,2}mathbf {y} _{2}+dots +a_{1,n}mathbf {y} _{n}+f_{1}mathbf {s} _{1}}. Эта сумма должна не превосходить c1. Как результат мы получаем:

Максимизировать {displaystyle sum _{j=1}^{n}g_{j}y_{j}+sum _{i=1}^{m}h_{i}s_{i}}
при ограничениях
{displaystyle sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}leqslant c_{i},1leqslant ileqslant m}
{displaystyle e_{j}y_{j}+sum _{i=1}^{m}b_{ij}s_{i}leqslant d_{j},1leqslant jleqslant n}
{displaystyle y_{j}geqslant 0,,s_{i}geqslant 0,1leqslant jleqslant n,1leqslant ileqslant m}

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

Интерпретации в реальной жизни[править | править код]

Теорема двойственности имеет экономическую интерпретацию. Если мы интерпретируем прямую задачу линейного программирования как классическую задачу «распределения ресурсов», её двойственную задачу можно интерпретировать как задачу «оценки ресурсов»[14]. См. статью Теневая ценаruen. Об экономической интерпретации двойственной задачи можно почитать также в книге Лунгу[15].

Теорема двойственности имеет и физическую интерпретацию[16].

Примечания[править | править код]

  1. Иногда используется термин Сопряжённая задача, как, например, в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 149) или в книге Лунгу (Лунгу 2005, 67). Во второй книге прямая задача именуется также основной задачей.
  2. Gartner, Matousek, 2006, с. 81–104.
  3. Юдин, Гольштейн, 1969, с. 150-152 Пункт 5.2.
  4. Юдин, Гольштейн, 1969, с. 157-159 Пункт 5.5.
  5. Gartner, Matousek, 2006, с. 85.
  6. Доказательство очень близкого утверждения, из которого вытекает данная теорема можно найти в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 159, Лемма 5.1)
  7. Gartner, Matousek, 2006, с. 81–83.
  8. Доказательство можно найти в книге Юдина и Гольштейна, где она именуется «первой теоремой двойственности» (Юдин, Гольштейн 1969, 164, Теорема 6.1)
  9. Gartner, Matousek, 2006, с. 87–89.
  10. Gartner, Matousek, 2006, с. 81–94.
  11. Юдин, Гольштейн, 1969, с. 162, Лемма 5.3.
  12. A. A. Ahmadi Lecture 6: linear programming and matching. Princeton University (2016). Архивировано 21 сентября 2018 года.
  13. Gartner, Matousek, 2006, с. sub.8.1.
  14. В книге Юдина и Гольштейна для теневых цен используется термин предварительные оценки (факторов производства).
  15. Лунгу, 2005, с. 68 Пункт 5.4.
  16. Gartner, Matousek, 2006, с. 86–87.

Литература[править | править код]

  • Jiri Matousek, Bernd Gärtner. Understanding and Using Linear Programming. — Springer, 2006. — С. 81–104. — (Universitext).
  • Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). — Москва: «Наука», 1969.
  • Лунгу К.Н. Линейное программирование. Руководство к решению задач. — М.: ФИЗМАТЛИТ, 2005. — ISBN 5-9221-0631-7.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *