Двойственный симплекс-метод и доказательство теоремы двойственности
лан другой.
Исходная задача. Найти минимальное значение линейной функции Z = x2 –
x4 – 3x5 при ограничениях
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), матрица-столбец
1 1 2 0 -1 1
0
A0 = 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 =
y1 + 2y2 +5y3 при ограничениях
y1 ( 0,
2y1 – 4y2 + 3y3 ( 1,
y2 ( 0,
-y1 + 2y2 ( -1,
y1 – y2 + y3 ( -3,
y3 ( 0.
Решение исходной задачи находим симплексным методом (табл. 1.2).
|i |Базис |С |A0 |0 |1 |0 |-1 |-3 |0 |
| | |базиса | | | | | | | |
| | | | |A1 |A2 |A3 |A4 |A5 |A6 |
|1 |A1 |0 |1 |1 |2 |0 |-1 |1 |0 |
|2 |A3 |0 |2 |0 |-4 |1 |2 |-1 |0 |
|3 |A6 |0 |5 |0 |3 |0 |0 |1 |1 |
|m + 1 |Zi - Cj |0 |0 |-1 |0 |1 |3 |0 |
|1 |A5 |-3 |1 |1 |2 |0 |-1 |1 |0 |
|2 |A3 |0 |3 |1 |-2 |1 |1 |0 |0 |
|3 |A6 |0 |4 |-1 |1 |0 |1 |0 |1 |
|m + 1 |Zi - Cj |-3 |-3 |-7 |0 |4 |0 |0 |
|1 |A5 |-3 |4 |2 |0 |1 |0 |1 |0 |
|2 |A4 |-1 |3 |1 |-2 |1 |1 |0 |0 |
|3 |A6 |0 |1 |-2 |3 |-1 |0 |0 |1 |
|m + 1 |Zi - Cj |-15 |-7 |1 |-4 |0 |0 |0 |
|1 |A5 |-3 |4 |3 |0 |1 |0 |1 |0 |
|2 |A4 |-1 |11/3 |-1/3 |0 |1/3 |1 |0 |2/3 |
|3 |A2 |1 |1/3 |-2/3 |1 |-1/3 |0 |0 |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, получен в четвертой итерации табл. 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 |A5 |0 |1 |2 |-1 |1 |2 |1 |0 |0 |
|2 |A3 |0 |2 |2 |1 |1 |-1 |0 |1 |0 |
|3 |A7 |0 |3 |-1 |4 |-2 |-2 |0 |0 |1 |
|m + 1 |Zi - Cj |0 |-2 |-3 |-6 |-3 |0 |0 |0 |
|1 |A3 |6 |1 |2 |-1 |1 |2 |1 |0 |0 |
|2 |A6 |0 |1 |0 |2 |0 |-1 |-1 |1 |0 |
|3 |A7 |0 |5 |3 |6 |0 |2 |2 |0 |1 |
|m + 1 |Zi - Cj |6 |10 |-9 |0 |9 |6 |0 |0 |
|1 |A3 |6 |3/2 |2 |0 |1 |3/2 |Ѕ |Ѕ |0 |
|2 |A2 |3 |Ѕ |0 |1 |0 |-1/2 |-1/2 |Ѕ |0 |
|3 |A7 |0 |2 |3 |0 |0 |4 |5 |3 |1 |
|m + 1 |Zi - Cj |21/2 |10 |0 |0 |9/2 |3/2 |9/2 |0 |
4. Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных двойственных
задач можно заключить, что математические модели пары двойственных задач
могут иметь один из следующих видов.
Н е с и м м е т р и ч н ы е з а д а ч и
(1) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX = A0; YA ( С.
X ( 0.
(2) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX = A0; YA ( С.
X ( 0.
С и м м е т р и ч н ы е з а д а ч и
(3) Исходная задача Двойственная задача
Zmin = CX; fmax = YA0;
AX ( A0; YA ( С.
X ( 0. Y ( 0.
(4) Исходная задача Двойственная задача
Zmax = CX; fmin = YA0;
AX ( A0;
| |  скачать работу |
Двойственный симплекс-метод и доказательство теоремы двойственности |
