Двойственный симплекс-метод и доказательство теоремы двойственности
Страница 3
Оптимальный план исходной задачи X* = (0; 1/3; 0; 11/3; 4; 0), при котором Zmin = - 46/3, получен в четвертой итерации табл. 1.2. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y* = C*D-1, где матрица D-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A5, A4, A2; значит,
1 -1 2
D = (A5, A4, A2) = -1 2 -4
1 0 3
Обратная матрица D-1 образована из коэффициентов, стоящих в столбцах A1, A3, A6 четвертой итерации:
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),
т. е. 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.
3. Симметричные двойственные задачи
Разновидностью двойственных задач линейного , программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу-столбец Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений
(1.12). АХ>А0, Х>0
и минимизирует линейную функцию Z = СХ.
Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA £ C, Y ³ 0 и максимизирует линейную функцию f = YA0.
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.
Исходная задача. Найти минимальное значение линейной функции Z = x1 + 2x2 + 3x3 при ограничениях
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 при ограничениях
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 |
0 |
0 |
0 |
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
|
1
2
3 |
A5
A3
A7 |
0
0
0 |
1
2
3 |
2
2
-1 |
-1
1
4 |
1
1
-2 |
2
-1
-2 |
1
0
0 |
0
1
0 |
0
0
1 |
|
m + 1 |
Zi - Cj |
0 |
-2 |
-3 |
-6 |
-3 |
0 |
0 |
0 |
|
1
2
3 |
A3
A6
A7 |
6
0
0 |
1
1
5 |
2
0
3 |
-1
2
6 |
1
0
0 |
2
-1
2 |
1
-1
2 |
0
1
0 |
0
0
1 |
|
m + 1 |
Zi - Cj |
6 |
10 |
-9 |
0 |
9 |
6 |
0 |
0 |
|
1
2
3 |
A3
A2
A7 |
6
3
0 |
3/2
½
2 |
2
0
3 |
0
1
0 |
1
0
0 |
3/2
-1/2
4 |
½
-1/2
5 |
½
½
3 |
0
0
1 |
|
m + 1 |
Zi - Cj |
21/2 |
10 |
0 |
0 |
9/2 |
3/2 |
9/2 |
0 |
| | | | | | | | | | | | | | | | | | | |