[7, с. 60].
Основные теоремы двойственности
позволяют по решению одной из двойственных
задач найти оптимальное решение другой,
не решая ее.
Если из пары двойственных задач
одна обладает оптимальным планом, то
и другая имеет решение, причем для экстремальных
значений линейных функций выполняется
соотношение: min Z = max f.
Если линейная функция одной
из задач не ограничена, то другая не имеет
решения.
Доказательство. Предположим,
что исходная задача обладает оптимальным
планом, который получен симплексным методом.
Не нарушая общности, можно считать, что
окончательный базис состоит из т первых
векторов A1, A2, ..., Am. Тогда последняя
симплексная таблица имеет вид:
Таблица 2
i |
Базис |
С базиса |
A0 |
C1 |
C2 |
… |
Cm |
Cm+1 |
… |
cn |
A1 |
A2 |
… |
Am |
Am+1 |
… |
An |
1
2
.
.
.
m |
A1
A2
.
.
.
Am |
C1
C2
.
.
.
C |
x1
x2
.
.
.
xm |
1
0
.
.
.
0 |
0
1
.
.
.
0 |
...
...
.
.
.
. |
0
0
.
.
.
1 |
x1, m+1
x2, m+1
.
.
.
xm, m+1 |
…
…
.
.
.
… |
x1n
x2n
.
.
.
xmn |
m+1 |
Zi - Cj |
Z0 |
Z1 – C1 |
Z2 – C2 |
... |
Zm – Cm |
Zm+1 – Cm+1 |
… |
Zn – Cn |
Пусть D — матрица, составленная
из компонент векторов окончательного
базиса A1, A2, ..., Am, тогда таблица
2 состоит из коэффициентов разложения
векторов A1, A2, ..., An исходной
системы по векторам базиса, т. е. каждому
вектору Aj в этой таблице
соответствует такой вектор Xj, что Aj = DXj (j= 1,2, ,.., n).
Для оптимального плана получаем
A0 = DX*, где X*
= (x*1, x*2, …, x*m). Обозначим
через
матрицу, составленную из коэффициентов
разложения векторов Аj (j = 1, 2, ..., n),
записанных в таблице 2. Тогда, учитывая
соотношения Aj = DXj (j= 1,2, ,.., n)
и An = DX*, получаем:
A = D
, D-1A =
,
A0=DX*; D-1A0 = X*,
min Z= C*X*,
= C*
-C £ 0,
где С* = (C*1, C*2, …, C*m), С = (C1, C2, …, Cm, Cm+1, …, Cn), a
= (C*X1 -C1; С*Х2 - С2, ..., C*Xn - Cn) = (Z1 – С1; Z2 - C2; ..., Zn - Cn) - вектор,
компоненты которого неположительные,
так как они совпадают с Zj - Cj £ 0, соответствующими оптимальному
плану.
Оптимальный план исходной
задачи имеет вид X* = D-1 А0, поэтому оптимальный
план двойственной задачи ищем в виде
Y* = C*D-1.
Покажем, что Y* действительно
план двойственной задачи. Для этого ограничения
YA £ С запишем в виде неравенства
YA - С £ 0, в левую часть которого подставим
Y*. Тогда на основании Y* = C*D-1, A = D
, D-1A =
и
= C*
—C £ 0 получим Y* А - С = С* D-1А – С = С*
- С £ 0, откуда находим Y*A £ С.
Так как Y* удовлетворяет ограничениям
YA £ С, то это и есть план двойственной
задачи. При этом плане значение линейной
функции двойственной задачи f (Y*) = Y*An.
Учитывая соотношения:
A0=DX*; D-1A0 = X*,
min Z= C*X*
Y* = C*D-1,
имеем f (Y*) = Y*A0 = C*D-1 A0 = C*X* = min Z(X).
Таким образом, значение линейной
функции двойственной задачи от Y* численно
равно минимальному значению линейной
функции исходной задачи.
Докажем теперь, что Y* является
оптимальным планом. Умножим AX = A0, Х ³ 0 на любой план Y двойственной
задачи, а YA £ С - на любой план X исходной
задачи: YAX=YA0=f (Y), YAX £ СХ = Z (X), отсюда следует, что
для любых планов Х и Y выполняется неравенство
f (Y) £ Z (X).
Этим же соотношением связаны
и экстремальные значения максимума функции
f (Y) £ min Z (Х). Из последнего неравенства
заключаем, что максимальное значение
линейной функции достигается только
в случае, если max f (Y) = min Z (X), но это значение
f (Y) достигает при плане Y*, следовательно,
план Y* — оптимальный план двойственной
задачи.
Также можно доказать, что если
двойственная задача имеет решение, то
исходная также обладает решением и имеет
место соотношение max f (Y) = min Z (X).
Для доказательства второй
части теоремы допустим, что линейная
функция исходной задачи не ограничена
снизу. Тогда из f (Y) £ Z (X) следует, что f (Y) £ -¥ . Это выражение лишено смысла,
следовательно, двойственная задача не
имеет решений.
Аналогично предположим, что
линейная функция двойственной задачи
не ограничена сверху. Тогда из f (Y) £ Z (X) получаем, что Z (X) ³ +¥. Это выражение также лишено
смысла, поэтому исходная задача не имеет
решений.
Доказанная теорема позволяет
при решении одной из двойственных задач
находить оптимальный план другой.
Исходная задача. Найти минимальное
значение линейной функции Z = x2 – x4 – 3x5, при ограничениях:
xij ³ 0 (j = 1, 2, …, 6)
Здесь матрица-строка С = (0;.
1; 0; -1; -3, 0), матрица-столбец:
Двойственная задача. Найти
максимум линейной функции f = y1 + 2y2 +5y3 при ограничениях:
Решение исходной задачи находим
симплексным методом (таблица 3).
Таблица 3
i |
Базис |
С базиса |
A0 |
0 |
1 |
0 |
-1 |
-3 |
0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
1
2
3 |
A1
A3
A6 |
0
0
0 |
1
2
5 |
1
0
0 |
2
-4
3 |
0
1
0 |
-1
2
0 |
1
-1
1 |
0
0
1 |
m + 1 |
Zi - Cj |
0 |
0 |
-1 |
0 |
1 |
3 |
0 |
1
2
3 |
A5
A3
A6 |
-3
0
0 |
1
3
4 |
1
1
-1 |
2
-2
1 |
0
1
0 |
-1
1
1 |
1
0
0 |
0
0
1 |
m + 1 |
Zi - Cj |
-3 |
-3 |
-7 |
0 |
4 |
0 |
0 |
1
2
3 |
A5
A4
A6 |
-3
-1
0 |
4
3
1 |
2
1
-2 |
0
-2
3 |
1
1
-1 |
0
1
0 |
1
0
0 |
0
0
1 |
m + 1 |
Zi - Cj |
-15 |
-7 |
1 |
-4 |
0 |
0 |
0 |
1
2
3 |
A5
A4
A2 |
-3
-1
1 |
4
11/3
1/3 |
3
-1/3
-2/3 |
0
0
1 |
1
1/3
-1/3 |
0
1
0 |
1
0
0 |
0
2/3
1/3 |
m + 1 |
Zi - Cj |
46/3 |
19/3 |
0 |
-11/3 |
0 |
0 |
-1/3 |
Оптимальный план исходной
задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Zmin = - 46/3. Используя
эту итерацию, найдем оптимальный план
двойственной задачи. Согласно теореме
двойственности оптимальный план двойственной
задачи находится из соотношения Y* = C*D-1, где матрица
D-1 - матрица,
обратная матрице, составленной из компонент
векторов, входящих в последний базис,
при котором получен оптимальный план
исходной задачи. В последний базис входят
векторы A5, A4, A2, значит:
D = (A5, A4, A2) =
Обратная матрица D-1 образована
из коэффициентов, стоящих в столбцах
A1, A3, A6 четвертой
итерации:
D-1 =
Из этой же итерации следует
С* = (-3; -1; 1). Таким образом:
Y = С*D-1 = (-3; -1; 1)
*
Y* = (-19/3; -11/3; -1/3),
т. е. yi = С*Хi
где Хi — коэффициенты
разложения последней итерации, стоящие
в столбцах векторов первоначального
единичного базиса.
Таким образом, i-ю двойственную
переменную можно получить из значения
оценки (m + 1)-й строки, стоящей против соответствующего
вектора, входившего в первоначальный
единичный базис, если к ней прибавить
соответствующее значение коэффициента
линейной функции:
у1 = - 19/3 + 0 = -19/3;
y2 = -11/3 + 0 = -11/3;
у3 = -1/3+0 = -1/3.
При этом плане max f = - 46/3.
4. Двойственный
симплексный метод
Переход к двойственной
задаче не обязателен, так как если рассмотреть
первую симплексную таблицу с единичным
дополнительным базисом, то легко заметить,
что в столбцах записана исходная задача,
а в строках - двойственная. Причем оценками
плана исходной задачи являются Сj а оценками плана двойственной
задачи – bi [11, с. 108]. Решим двойственную
задачу по симплексной таблице 1, в которой
записана исходная задача; найдем оптимальный
план двойственной задачи, а вместе с ним и оптимальный
план исходной задачи. Этот метод носит
название двойственного симплексного
метода.
Пусть необходимо решить исходную задачу
линейного программирования, поставленную
в общем виде: минимизировать функцию
Z =СХ при АХ = A0, Х ? 0. Тогда в двойственной задаче необходимо
максимизировать функцию f = YA0 при YA ? С. Допустим, что выбран такой базис D =
(A1, А2, ..., Аi, ..., Аm), при котором хотя бы одна
из компонент вектора Х = D-1 A0 = (x1, x2, ..., xi, ..., xm) отрицательная (например, xi < 0),
но для всех векторов Aj выполняется соотношение Zj – Cj ? 0 (i = 1,2, ..., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 -
план двойственной задачи. Этот план не
оптимальный, так как, с одной стороны,
при выбранном базисе X содержит отрицательную компоненту и
не является планом исходной задачи, а
с другой стороны, оценки оптимального
плана двойственной задачи должны быть
неотрицательными.
Таким образом, вектор Аi, соответствующий
компоненте xi < 0, следует исключить из базиса исходной
задачи, а вектор, соответствующий отрицательной
оценке,— включить в базис двойственной
задачи.
Для выбора вектора, включаемого в базис
исходной задачи, просматриваем i-ю строку:
если в ней не содержатся xij < 0, то линейная функция двойственной
задачи не ограничена на многограннике
решений, а исходная задача не имеет решений.
Если же некоторые xij < 0, то для столбцов, содержащих эти
отрицательные значения, вычисляем q0j=
min (xi/xij) ? 0 и определяем вектор, соответствующий max q0j(Zj —
Cj) при решении исходной задачи на минимум
и min q0j(Zj — Cj) при решении исходной задачи на максимум.
Этот вектор и включаем в базис исходной
задачи. Вектор, который необходимо исключить
из базиса исходной задачи, определяется
направляющей строкой.
Если q0j= min (xi/xij) = 0, то есть xi = 0, то xij берется за разрешающий элемент только
в том случае, если xij > 0. Такой выбор разрешающего элемента
на данном этапе не приводит к увеличению
количества отрицательных компонент вектора X.
Процесс продолжаем до получения Х ? 0;
при этом находим оптимальный план двойственной
задачи, следовательно, и оптимальный
план исходной задачи.
В процессе вычислений по алгоритму двойственного
симплексного метода условие Zj – Cj ? 0 можно не учитывать до исключения всех хi < 0,
затем оптимальный план находится обычным
симплексным методом. Это удобно использовать,
если все хi < 0; тогда для перехода к плану исходной,
задачи за одну итерацию необходимо q0j определить
не по минимуму, а по максимуму отношений,
то есть q0j= max (xi/xij) > 0.
Двойственным симплексным методом можно
решать задачи линейного программирования,
системы ограничений которых при положительном
базисе содержат свободные члены любого
знака. Этот метод позволяет уменьшить
количество преобразований системы ограничений,
а также размеры симплексной таблицы.
Заключение
Двойственность, в
математическом программировании, как
и вообще в математике, играет фундаментальную
роль. Она выступает в качестве краеугольного
камня соответствующих теорий, порождает
арсенал конструктивных средств анализа
математических моделей, построения эффективных
алгоритмов решения задач и формальной
оценки этой эффективности. Двойственность,
в зависимости от ее конкретного содержания,
определяемого конкретной математической
дисциплиной (алгебра, функциональный
анализ, теория оптимального управления
и т.д.), несет в себе следы специфики соответствующей
дисциплины. Но именно это обстоятельство
и превращает двойственность, в математике,
в здание, хотя в определенном смысле и
единой, но гармонически организованной
и насыщенной архитектуры.