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

Переход к двойственной задаче удобно осуществлять с помощью табл. 6.1.

Таблица 6.1.

Таблица перехода к двойственной задаче

х₁≥0 … х_l≥0 х_l+1 … х_n

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

1) если прямая задача решается на максимум, то двойственная – на минимум, и наоборот;

2) в задаче на максимум ограничения – неравенства имеют смысл ≤, а в задаче минимизации – смысл ≥;

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;

6) если на переменную прямой задачи наложено условие не отрицательности (≥), то соответствующее ограничение двойственной задачи записывается как ограничение – неравенство, если же нет, то, как ограничение равенство;

7) 7) если i-e ограничение исходной задачи является неравенством, то i –я переменная двойственной задачи y_i ³ 0. Если же i-е ограничение есть уравнение, то переменная y_i может принимать как положительные, так и отрицательные значения, т.е. условие неотрицательности не налагается.

Сначала в таблицу заносится вся информация о прямой задаче: значения параметров a_ij, b_i, и с_j, знаки неравенств или равенств в ограничениях (справа), условия неотрицательности соответствующих переменных (сверху). Затем каждой i-й строке (i-му ограничению прямой задачи) ставится в соответствие двойственная переменнаяy_i, на которую накладывается условие неотрицательности, если справа в этой строке стоит знак неравенства. Внизу проставляются знаки неравенства или равенства в зависимости от того, наложено или не наложено условие неотрицательности на соответствующую переменную прямой задачи. После этого двойственная задача «считывается» путем умножения вектора у= (y_i) на столбцы матрицы А = (а_ij) и вектор b = (b_i).

В табл. 6.2 указаны прямая и двойственная задачи в наиболее важных частных случаях.

Таблица 6.2

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

Форма записи прямой задачи ЛП	Форма записи соответствующей двойственной задачи ЛП
Основная: <c,x> max, Ax ≤ b, x≥ 0	Каноническая: : <b,y> min, yA= c, y ≥0
Стандартная: <c,x> max, Ax ≤ b, х ≥0	Стандартная: <b,y> min, yA ≥ c, y ≥0
Каноническая:c,x> max, Ax = b, х ≥0	Основная: <b,y> min, yA ≥ c

Теорема 6.1. Задачи (6.11) и (6.12) взаимодвойственны, т. е. двойственной к задаче (6.12) является задача (6.11).

Ниже под Х и У понимаются допустимые множества задач (6.11) и (6.12) соответственно.

Теорема 6.2.Для любых хÎХ и yÎY выполняется неравенство

<с, х> £ <b, у>.

Теорема 6.3. Пусть х*Î X, у*Î Y. Тогда

1) если

<с, х*> = <b,у*>, (6.13)

то х* есть решение задачи (6.11), а у* — решение задачи (6.12);

2) равенство (6.13) равносильно совокупности условий

, (6.14)

(6.15)

Равенство (6.13) принято называть соотношением двойственности, условия (6.14), (6.15) — условиями дополняющей нежесткости.

Теорема 6.4 (теорема двойственности). Прямая задача (6.11) имеет решение в том и только том случае, если двойственная задача (6.12) имеет решение; при этом значения данных задач совпадают, т. е. для любых их решений х* и у* выполнено соотношение двойственности (6.12).

При практическом применении теории двойственности особенно полезным является следующее утверждение, непосредственно вытекающее из теорем 6.3 и 6.4.

Теорема 6.5 (о дополняющей нежесткости). Точки x*Î Х и у*Î Y являются решениями взаимодвойственных задач (6.11) и (6.12) соответственно в том и только том случае, если выполняются условия (6.14), (6.15).

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

Теорема 6.6. Если допустимые множества взаимодвойственных задач (6.11) и (6.12) непусты, то обе они имеют решение. Если же только у одной из них допустимое множество непусто, то ее значение бесконечно, т. е.

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

17х₁ - 5 х₂ + х₃+ х₄ - 8х₅ max,

3х₁ - х₂ - х₃ + 4х₄ + 7х₅ ≤11,

х₁ - 5 х₂ - 7х₃ + х₄ + 2х₅ ≥-8,

х₁ + х₂ + х₃ + 3х₄ – х₅=4,

х₁ ≥ 0, х₄ ≥ 0.

Решение. Составим таблицу перехода к двойственной задаче (табл. 6.3).

Отсюда получаем ответ:

Таблица 6.3

Таблица перехода к двойственной задаче

х₁≥0 х₂ х₃ х₄≥0 х₅

11y₁ +8y₂ + 4y₃ min,

3y₁ - y₂ + y₃ ≥17,

-y₁ + 5y₂ + y₃ = -5,

-y₁ + 7y₂ + y₃ =1,

4y₁ - y₂ + 3y₃ ≥1,

7y₁ - 2y₂ - y₃= -8,

y₁≥0, y₂ ≥0.