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

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

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

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

f =c1x1 + c2x2 +…+ cnxn>max (1.4).

при условиях:

a11×1 + a12×2 +…+ a1nxn? b1.

a21×1 + a22×2 +…+ a2nxn? b2.

… (1.5).

am1x1 + am2x2 +…+ amnxn? bm.

xj? 0 (j = 1, 2,…m, m? n).

Задача, состоящая в нахождении минимального значения функции.

f*=b1y1 + b2y2 +…+ bmym>min (1.6).

при условиях:

a11y1 + a12y2 +…+ am1ym? c1.

a12y1 + a22y2 +…+ am2ym? c2.

… (1.7).

a1ny1 + a2ny2 +…+ amnym? cm.

yi? 0 (i = 1, 2, … k? m).

называется двойственной по отношению к задаче (1.4) — (1.5). Задачи (1.4) — (1.5) и (1.6) — (1.7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

Целевая функция исходной задачи задается на максимум, а целевая функция двойственнойна минимум.

1. Матрица.

2. составленная из коэффициентов при неизвестных в системе ограничений (1.5) исходной задачи, и аналогичная матрица.

(1.9).

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

• 3. Число переменных в двойственной задаче равно числу ограничений в системе (1.5) исходной задачи, а число ограничений в системе (1.7) двойственной задачи — числу переменных в исходной задаче.
• 4. Коэффициентами при неизвестных в целевой функции (1.6) двойственной задачи являются свободные члены в системе (1.5) исходной задачи, а правыми частями в соотношениях системы (1.7) двойственной задачи — коэффициенты при неизвестных в целевой функции (1.4) исходной задачи.
• 5. Если i-е соотношение в системе (1.5) исходной задачи является неравенством, то j-я переменная двойственной задачи yj? 0. В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (1.5) прямой задачи и соотношения (1.7) двойственной задачи являются неравенствами вида ««. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (1.5) прямой задачи и соотношения (1.7) двойственной задачи являются неравенствами вида ««. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Если одна из задач двойственной пары (1.4) — (1.5) или (1.6) — (1.7) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е. f max = f*min.

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