Kursovik_ISP (Двойственный симплекс-метод и доказательство теоремы двойственности), страница 2

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA — С  0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

Y* А – С = С* D^-1А – С = С* - С  0,

откуда находим Y*A  С.

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двой­ственной задачи f (Y*) = Y*A₀. Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y*) = Y*A₀ = C*D^-1 A₀ = C*X* = min Z(X).

Таким образом, значение линейной функции двойственной задачи от Y* численно равно минимальному значению линейной функции исходной задачи.

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA₀=f (Y), YAX  СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) f (Y)  Z (X).

Этим же соотношением связаны и экстремальные значения max f (Y)  min Z (Х). Из последнего неравенства заключаем, что максималь­ное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение [см. (1.10)] f (Y) достигает при плане Y*, следовательно, план Y* — оптимальный план двойственной задачи.

Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотно­шение max f (Y) = min Z (X).

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следу­ет, что f (Y)  - . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной за­дачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X)  +. Это выражение также лишено смысла, поэтому исходная задача не име­ет решений.

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

Исходная задача. Найти минимальное значение линейной функ­ции Z = x₂ – x₄ – 3x₅ при ограничениях

x ₁ + 2x₂ - x₄ + x₅ = 1,

- 4x₂ + x₃ + 2x₄ – x₅ = 2, x_ij  0 (j = 1, 2, …, 6)

3x₂ + x₅ + x₆ = 5,

Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец

1 1 2 0 -1 1 0

A₀ = 2 A = 0 -4 1 2 -1 0

3 0 3 0 0 1 1

1 0 0

2 -4 3

A’’ = 0 1 0

-1 2 0

1 -1 0

0 0 1

Двойственная задача. Найти максимальное значение линейной функции f = y₁ + 2y₂ +5y₃ при ограничениях

y₁  0,

2y₁ – 4y₂ + 3y₃  1,

y₂  0,

-y₁ + 2y₂  -1,

y₁ – y₂ + y₃  -3,

y₃  0.

Решение исходной задачи находим симплексным методом (табл. 1.2).

Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Z_min = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойствен­ной задачи находится из соотношения Y* = C*D^-1, где матрица D^-1 - матрица, обратная матрице, составленной из компонент векторов, вхо­дящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A₅, A₄, A₂; значит,

1 -1 2

D = (A₅, A₄, A₂) = -1 2 -4

1 0 3

Обратная матрица D^-1 образована из коэффициентов, стоящих в столбцах A₁, A₃, A₆ четвертой итерации:

2 1 0

D^-1 = -1/3 1/3 2/3

-2/3 -1/3 1/3

И з этой же итерации следует С* = (— 3; —1; 1). Таким образом

2 1 0

Y = С*D^-1 = (-3; -1; 1)  -1/3 1/3 2/3

-2/3 -1/3 1/3

Y*=(-19/3; -11/3; -1/3),

т. е. y_i = С*Х_i, где Х_i — коэффициенты разложения последней ите­рации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней приба­вить соответствующее значение коэффициента линейной функции:

у₁ = — 19/3 + 0 = — 19/3; y₂ = -11/3 + 0 = -11/3; у₃ = -1/3+0 = -1/3. При этом плане max f = -46/3.

3. Симметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец Х = (x₁, x₂, …, x_n), которая удовлетворяет системе ограничений

(1.12). АХ>А₀, Х>0

и минимизирует линейную функцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y₁, y₂, …, y_n), которая удовлетворяет системе ограничений YA  C, Y  0 и максимизирует линейную функцию f = YA₀.

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

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

Исходная задача. Найти минимальное значение линейной функции Z = x₁ + 2x₂ + 3x₃ при ограничениях

2x₁ + 2x₂ - x₃  2,

x₁ - x₂ - 4x₃  -3, x_i  0 (i=1,2,3)

x₁ + x₂ - 2x₃  6,

2x₁ + x₂ - 2x₃  3,