Шепеленко О

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

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

Пара двойственных задач имеет следующий вид:

Исходная задача Двойственная задача

Правила составления двойственной задачи:

Если целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в ограничениях приводят к виду “”, а в задаче на минимум – вид “”.
Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче являются транспонированными по отношению друг к другу.
Число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений двойственной задачи – числу переменных в исходной задаче.
Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.
Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи.
Предполагается, что переменные в обеих задачах являются неотрицательными.

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

Замечание.

Двойственная задача к двойственной будет исходной.
Для построения двойственной задачи следует проверить выполнение для исходной задачи следующих условий:

а) в всех ограничениях свободные члены содержатся в правой части неравенства (равенства), члены с неизвестными - в левой;

б) все ограничения неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств в них были направлены в одну и туже сторону;

в) знаки неравенств системы ограничений связаны с оптимизацией целевой функции таким образом: ;

Между взаимно двойственными ЗЛП имеет место взаимосвязь, которая следует из теорем двойственности.

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

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

Пример 2.4.1. Записать двойственную задачу для ЗЛП (2.2.1), (2.2.2). Выписать решение двойственной задачи.

Решение. Поскольку исходная задача на максимум, то во всех ограничениях системы (2.2.1) должен быть знак “”. Для этого обе части третьего неравенства на (–1) и меняем знак неравенства на противоположный. Таким образом, получим:

(2.4.1)

max z = x₁ + 4x₂ (2.4.2)

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

По полученной матрице составим новую систему ограничений, причем в неравенствах ограничений будет знак “” и в правой части этих неравенств будут стоять коэффициенты целевой функции (2.4.2), т.е. 1 и 4:

Коэффициентами новой целевой функции будут числа, стоящие в правой части ограничений исходной задачи (2.4.1), причем целевая функция уже минимизируется: min f = – 5y₁ + 6y₂– 7y₃ .

Итак, двойственная задача имеет вид (2.4.3), (2.4.4):

(2.4.3)

min f = – 5y₁ + 6y₂– 7y₃ . (2.4.4)

Исходная и двойственная ЗЛП имеют разный экономический смысл. Решая одну задачу, можно, не решая другую, выписать ее решение. Решение двойственной задачи y₁, y₂, y₃ находится в z-строке последней симплексной таблицы в дополнительных столбцах с обратным знаком (а именно, в столбцах р₃, р₄, р₅). Нужно помнить, что решение выписывается с учетом неотрицательности переменных. В нашем случае решение следующее:

y₁= 0, y₂= 9/2, y₃= 1/2.

При подстановке этого решения в целевую функцию двойственной задачи (4.4) должно получится число, стоящее в z-строке последней симплексной таблицы в столбце р₀. Проверим:

min f = max z.

Пример 2.4.2. Записать двойственную задачу для ЗЛП

min z = –7 x₁ + 3x₂ .

Решение. Поскольку исходная задача на минимум, то в системе ограничений должны быть знаки “”. Таким образом, после соответствующих преобразований система ограничений исходной задачи примет вид:

Целевая функция при этом остается прежней, а именно: min z =-7 x₁+3x₂. Выпишем матрицу, состоящую из коэффициентов при неизвестных в системе ограничений и транспонируем: .

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

max f = y₁ – 5y₂+ 6y₃ .

Содержание