Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности
--PAGE_BREAK-- 2. Несимметричные двойственные задачи. Теорема двойственности.В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде неравенств, причем в последней переменные могутбыть и отрицательными.Для простоты доказательств постановку задачи условимсязаписывать в матричной форме.
Исходная задача.Найти матрицу-столбец X = (x1, x2, …, xn), которая удовлетворяет ограничениям
(1.1) AX = A0, Х³
и минимизирует линейную функцию Z =СХ.
Двойственная задача.Найти матрицу-строку Y = (y1, y2, …, ym), которая удовлетворяет ограничениям
(1.2) YA £
С
и максимизирует линейную функцию f = YA0
В обеих задачах C = (c1, c2, …, cn) -матрица-строка, A0= (b1, b2, …, bm)— матрица-столбец, А = (aij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема.
Теорема (теорема двойственности).Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение
min Z = max f.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
Д о к а з а т е л ь с т в о. Предположим, что исходная задача обладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис состоит из т первых векторов A1, A2, ..., Am. Тогда последняя симплексная таблица имеет вид табл. 1.1.
Т а б л и ц а 1.1
i
Базис
Сбазиса
A0
C1
C2
…
Cm
Cm+1
…
cn
A1
A2
…
Am
Am+1
…
An
1
2
.
.
.
m
A1
A2
.
.
.
Am
C1
C2
.
.
.
Cm
x1
x2
.
.
.
xm
1
.
.
.
1
.
.
.
...
...
.
.
.
.
.
.
.
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; тогда табл. 1.1 состоит из коэффициентов разложения векторов A1, A2, ..., Anисходной системы по векторам базиса, т. е. каждому вектору Ajв этой таблице соответствует такой вектор Xjчто
(1.3) Aj= DXj (j= 1,2, ,.., n).
Для оптимального плана получаем
(1.4) A0 =DX*,
где X* = (x*1
, x*2
, …, x*m
)
.
Обозначим через <img width=«17» height=«21» src=«ref-1_287527154-206.coolpic» v:shapes="_x0000_i1028"> матрицу, составленную из коэффициентов разложения векторов А
j (j = 1, 2, ..., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:
(1.5) A=D<img width=«17» height=«21» src=«ref-1_287527154-206.coolpic» v:shapes="_x0000_i1029">, D-1A = <img width=«17» height=«21» src=«ref-1_287527154-206.coolpic» v:shapes="_x0000_i1030">
,
(1.6) A
=DX*;
D
-1
A
=
X*
,
(1.7) minZ=C*X*,
(1.8) <img width=«16» height=«21» src=«ref-1_287527772-203.coolpic» v:shapes="_x0000_i1031">=
C*<img width=«17» height=«21» src=«ref-1_287527154-206.coolpic» v:shapes="_x0000_i1032">
—C
£
0,
где С* = (C*1, C*2, …, C*m),С= (C1, C2, …, Cm, Cm+1, …, Cn),a <img width=«16» height=«21» src=«ref-1_287527772-203.coolpic» v:shapes="_x0000_i1033"> = (C*X1– C1; С*Х2 — С2, ..., C*Xn– Cn)= (Z1–С1; Z2 — C2;..., Zn — Cn) — вектор, компоненты которого неположительны, так как они совпадают с Zj— Cj £0, соответствующими оптимальному плану.
Оптимальный план исходной задачи имеет видX* =D-1А,поэтому оптимальный план двойственной задачи ищем в виде
(1.9) Y*
=
C*D
-1
.
Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенстваYA — С £
, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим
Y
* А
–
С
=
С* D
-1
А
–
С
=
С* <img width=«17» height=«21» src=«ref-1_287527154-206.coolpic» v:shapes="_x0000_i1034">
—
С
£
0,
откуда находимY*A £
С.
Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двойственной задачи f (Y*) = Y*A. Учитывая соотношения (1.9), (1.6) и (1.7), имеем
(1.10) f
(Y*) = Y*A=C*D-1A=C*X*=minZ(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 = x2 – x4 – 3x5при ограничениях
<img width=«12» height=«108» src=«ref-1_287528590-410.coolpic» v:shapes="_x0000_s1028">x1 + 2x2 — x4 + x5 = 1,
— 4x2 + x3 + 2x4 – x5 = 2, xij³0 (j = 1, 2, …, 6)
3x2 + x5 + x6 = 5,
Здесь матрица-строка С = (0;. 1; 0; —1; — 3, 0), матрица-столбец
<img width=«194» height=«98» src=«ref-1_287529000-811.coolpic» v:shapes="_x0000_s1030"><img width=«60» height=«107» src=«ref-1_287529811-556.coolpic» v:shapes="_x0000_s1029"> 1 1 2 0 -1 1 0
A0= 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
<img width=«127» height=«214» src=«ref-1_287530367-1133.coolpic» v:shapes="_x0000_s1031"> 1 0 0
2 -4 3
A’’ = 0 1 0
-1 2 0
1 -1 0
0 0 1
Двойственная задача.Найти максимальное значение линейной функции f= y1 + 2y2 +5y3при ограничениях
<img width=«11» height=«239» src=«ref-1_287531500-527.coolpic» v:shapes="_x0000_s1032"> y1 £0,
2y1 – 4y2 + 3y3£1,
y2 £0,
-y1 + 2y2 £-1,
y1 – y2 + y3 £-3,
y3 £0.
Решение исходной задачи находим симплексным методом (табл. 1.2).
i
Базис
Сбазиса
A0
1
-1
-3
A1
A2
A3
A4
A5
A6
1
2
3
A1
A3
A6
1
2
5
1
2
-4
3
1
-1
2
1
-1
1
1
m + 1
Zi — Cj
-1
1
3
1
2
3
A5
A3
A6
-3
1
3
4
1
1
-1
2
-2
1
1
-1
1
1
1
1
m + 1
Zi — Cj
-3
-3
-7
4
1
2
3
A5
A4
A6
-3
-1
4
3
1
2
1
-2
-2
3
1
1
-1
1
1
1
m + 1
Zi — Cj
-15
-7
1
-4
1
2
3
A5
A4
A2
-3
-1
1
4
11/3
1/3
3
-1/3
-2/3
1
1
1/3
-1/3
1
1
2/3
1/3
m + 1
Zi — Cj
-46/3
-19/3
-11/3
-1/3
Оптимальный план исходной задачи X* =(0; 1/3; 0; 11/3; 4; 0), при котором Zmin =— 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственнойзадачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y* =C*D-1
,где матрицаD-1— матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5, A4, A2; значит,
<img width=«97» height=«77» src=«ref-1_287532027-664.coolpic» v:shapes="_x0000_s1033"> 1 -1 2
D
=
(
A5, A4, A2
)
= -1 2 -4
1 0 3
Обратная матрицаD-1образована из коэффициентов, стоящих в столбцах A1, A3, A6 четвертой итерации:
<img width=«144» height=«78» src=«ref-1_287532691-679.coolpic» v:shapes="_x0000_s1034"> 2 1 0
D-1 = -1/3 1/3 2/3
-2/3 -1/3 1/3
<img width=«144» height=«87» src=«ref-1_287533370-739.coolpic» v:shapes="_x0000_s1035">Из этой же итерации следует С* = (— 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),
т. е. yi
= С*Хi, где Хi— коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.
Итак, i-ю двойственную переменную можно получить из значения оценки (m + 1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базиc, если к ней прибавить соответствующее значение коэффициента линейной функции:
у
1= — 19/3 + 0 = — 19/3; y2= -11/3 + 0 = -11/3; у3
= -1/3+0 = -1/3. При этом плане max f= -46/3.
продолжение
--PAGE_BREAK--3. Симметричные двойственные задачи
Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача.Найти матрицу-столбец Х = (x1, x2, …, xn),которая удовлетворяет системе ограничений
(1.12). АХ>А, Х>0
и минимизирует линейнуюфункцию Z =СХ.
Двойственная задача.Найти матрицу-строку Y = (y1, y2, …, yn),которая удовлетворяет системе ограничений YA £C, Y³0 и максимизирует линейную функцию f= YA.
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Исходная задача.Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3при ограничениях
<img width=«11» height=«102» src=«ref-1_287534109-377.coolpic» v:shapes="_x0000_s1036"> 2x1 + 2x2 — x3³2,
x1 — x2 — 4x3 £-3, xi³0 (i=1,2,3)
x1 + x2 — 2x3³6,
2x1 + x2 — 2x3³3,
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.
Двойственная задача.Найти максимум линейной функции f= 2y1+ 3y2 + 6y3 + 3y4при ограничениях
<img width=«11» height=«78» src=«ref-1_287534486-344.coolpic» v:shapes="_x0000_s1037">2y1 — y2 + y3 + 2y4 £1,
2y1 + y2 + y3 + y4 ³2,
-y1+ 4y2 — 2y3 — 2y4³3,
Для решения исходной задачи необходимо ввести четыре дополнительные переменные и после преобразования системы— одну искусственную. Таким образом, исходная симплексная таблица будет состоять из шести строк и девяти столбцов, элементы которых подлежат преобразованию.
Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.
Двойственную задачу решаем симплексным методом (табл. 1.3).
Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax=21/2.
Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7: x1= 3/2 +0 = 3/2; x2= 9/2 +0 = 9/2; x3= 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2.
Т а б л и ц а 1.3
i
Базис
Сбазиса
A0
2
3
6
3
A1
A2
A3
A4
A5
A6
A7
1
2
3
A5
A3
A7
1
2
3
2
2
-1
-1
1
4
1
1
-2
2
-1
-2
1
1
1
m + 1
Zi — Cj
-2
-3
-6
-3
1
2
3
A3
A6
A7
6
1
1
5
2
3
-1
2
6
1
2
-1
2
1
-1
2
1
1
m + 1
Zi — Cj
6
10
-9
9
6
1
2
3
A3
A2
A7
6
3
3/2
½
2
2
3
1
1
3/2
-1/2
4
½
-1/2
5
½
½
3
1
m + 1
Zi — Cj
21/2
10
9/2
3/2
9/2
продолжение
--PAGE_BREAK--