Понятие двойственности. С
каждой задачей линейного программирования тесно связана другая линейная задача,
называемая двойственной. Первоначальная задача называется исходной.
Связь исходной и двойственной задач состоит в том, что
коэффициенты Сj функции цели исходной задачи являются свободными членами
системы ограничений двойственной задачи,
свободные члены bi системы ограничений исходной задачи служат
коэффициентами функции цели двойственной задачи, а матрица коэффициентов
системы ограничений двойственной задачи является транспонированной матрицей
коэффициентов системы ограничений исходной задачи. Решение двойственной задачи
может быть получено из решения исходной и наоборот.
В качестве примера рассмотрим задачу использования ресурсов.
Предприятие имеет m видов ресурсов в количестве bi (i = 1, 2,…, m) единиц, из которых производится
n видов продукций. Для производства 1 ед. j-й продукции расходуется aij ед. i-го ресурса, а ее
стоимость составляет Сj ед.
Составить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Обозначим через xj (j
=1, 2, …, n) количество ед. j-й продукций. Тогда исходную
задачу сформулируем так.
Найти вектор Х = (х1, х2,
…, хn ), который удовлетворяет ограничениям
a11x 1 +
a12x2 +… + a1nxn
≤ b1,
a21x 1 + a22x2
+… + a2nxn ≤
b2, x
j
0 (j = 1, 2, …,
n),
……………………………………………………..
am1x 1 + am2x2
+…+ amnxn ≤ bm,
и доставляет максимальное значение линейной функции
Z = C1x1 + C2x2 + … + Cnxn.
Оценим ресурсы, необходимые для изготовления продукции. За
единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим
через yi
(i = 1, 2, …, m)
стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов,
идущих на изготовление единицы j-той продукции, равна
Стоимость затраченных
ресурсов не может быть меньше стоимости окончательного продукта, поэтому
должно выполняться неравенство
≥ Cj, j =1, 2, ..., n. Cтоимость всех имеющихся ресурсов выразится
величиной
. Итак, двойственную задачу можно можно сформулировать следующим образом.
Найти
вектор Y = (у1, у2,
…, уm), который удовлетворяет ограничениям
a11y1 + a21y2
+ ... + am1ym ≥ C1,
a12y1 + a22y2
+ … + am2 ym ≥ C2, yi ≥ 0 (i = 1, 2, …, m)
………………………………………………..
a1n y1 + a2ny2
+ … + amnym ≥ Cn ,
и доставляет минимальное значение линейной функции
f= b1y1+ b2y2+…+ bm ym.
Рассмотренные исходная и двойственная задачи могут быть экономически интерпретированы следующим образом.
Исходная
задача. Сколько и какой продукции xj (j = 1, 2,…, n) необходимо произвести, чтобы
при заданных стоимостях Cj (j =
1, 2,…, n) единицы продукции и размерах
имеющихся ресурсов bi (i =1, 2, …, m)
максимизировать выпуск продукции в стоимостном выражении.
Двойственная задача. Какова должна быть
цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Cj минимизировать общую
стоимость затрат?
Переменные yi называются
оценками или учетными, неявными ценами.
Многие
задачи линейного программирования первоначально ставятся в виде исходных или
двойственных задач, поэтому имеет смысл
говорить о паре двойственных задач линейного программирования.
Несимметричные двойственные задачи
Теорема двойственности. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной- в виде неравенств, причем в последней переменные могут быть и отрицательными. Для простоты доказательств постановку задачи условимся записывать в матричной форме.
Исходная задача. Найти матрицу-столбец Х = (х1, х2, …, хn), которая удовлетворяет ограничениями
АХ = А0, X ≥ 0 (2.6.1)
и минимизирует линейную функцию Z = CX.
Двойственная задача. Найти матрицу-строку Y = (у1, у2 , …, уm),
которая удовлетворяет ограничениями
YА ≤ С (2.6.2)
и максимизирует линейную функцию f = YA0.
В обеих задачах С = (с1, с2, …., сn) - матрица-строка, A0 = (b1, b2, …, bm)-матрица–столбец, А = (aij) – матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двойственных задач устанавливает следующая теорема.
Теорема 2.6.1. (теорема двойственности). Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений линейных функций выполняется соотношение
min Z = max f.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
Теорема позволяет при решении одной из двойственных задач находить оптимальный план другой.
Исходная задача. Найти минимальное значение линейной функции
Z = x2 - x4- 3x5 при ограничениях
x 1 +2х2 – х4 + х5 = 1,
-4x 1 + х3
+ 2 х4 - х5 = 2, хj ≥ 0 ( j=1, 2,…, 6).
3 x 2 +
х5 + х6 = 5,
Здесь матрица – строка С = (0; 1; 0; -1; -3; 0), матрица-столбец
А0 =
, А=
,
А¢¢
=
.
Двойственная задача. Найти максимальное значение линейной функции f = y1 + 2y2 + 5y3 при ограничениях
y1 ≤ 0,
2y1 - 4y2 + 3y3 ≤ 1,
y2 ≤ 0,
- y1 +2y2 ≤ -1,
y1 - y2 + y3 ≤ -3,
y3 ≤ 0.
Решение исходной задачи находим симплексным методом.(табл. 2.2)
Таблица 2.2
|
I |
Базис |
С базиса |
A0 |
0 |
1 |
0 |
-1 |
-3 |
0 |
||||
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
||||||||
|
1 2 3 1 |
A1 A3 A6 |
0 0 0 |
1 2 5 |
1 0 0 |
2 -4 3 |
0 1 0 |
-1 2 0 |
-1 1 |
0 0 1 |
||||
|
m+1 |
Zj - 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 0 0 |
0 0 1 |
||||
|
m+1 |
Zj - Cj |
-3 |
-3 |
-7 |
0 |
4 |
0 |
0 |
|||||
|
3 2 3 |
A5 A4 A6 |
-3 -1 0 |
4 3 1 |
2 1 -2 |
0 -2 |
1 1 -1 |
0 1 0 |
1 0 0 |
0 0 1 |
||||
|
m+1 |
Zj - 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 |
Zj - Cj |
-46/3 |
-19/3 |
0 |
-11/3 |
0 |
0 |
-1/3 |
|||||
Оптимальный план исходной задачи Х* = (0; 1/3; 0; 11/3; 4; 0) при котором Zmin = -46/3, получен в четвертой итерации табл.2.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 .
Из этой же итерации следует, C* = (-3; -1; 1). Таким образом,

2 1 0
Y* = C*D-1 = (-3; -1; 1)* -1/3 1/3 2/3 ,
-2 /3 -1/3 1/3
Y* = (-19/3; -11/3; -1/3),
т.е. yj = C*Xi , где Xi коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.
Итак, i-ю двойственную переменную можно получить из значения оценки (m+1)-й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:
y1 = -19/3 + 0 = -19/3; y2 = -11/3 + 0 = -11/3; y3 = -1/3 + 0 = -1/3. При этом плане
max f = -46/3.
Симметричные двойственные задачи
Разновидностью двойственных задач линейного программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Исходная задача. Найти матрицу - столбец X = (x1, x2, …, xn), которая удовлетворяет системе ограничений
АХ
≥ А0,
Х ≥ 0
(2.6.12)
и минимизирует линейную функцию Z = CX.
Двойственная задача. Найти матрицу – строку Y= (y1, y2, …,ym), которая удовлетворяет системе ограничений YА ≤ С, Y ≥ 0 и максимизирует линейную функцию f = YA0.
Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказано.
Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использования двойственности упрощает вычисление.
Исходная задача. Найти минимальное значение линейной функции.
Z = x1 + 2x2 +3x3 при ограничениях
2x1 +
2x2 - x3 ≥ 2,
x1 - x2 - 4x3 ≤ -3,
x1 + x2 - 2x3 ≥ 6, xj ≥ 0 (j = 1, 2, 3).
2x1 + x2 - 2x3 ≥ 3,
Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (2.6.12). Для этого второе неравенство следует умножить на –1.
Двойственная задача. Найти максимум линейной функции
f =2y1 + 3y2 + 6y3 +3y4 при ограничениях
2y1 - y2 + y3 + 2y4
≤ 1,
2y1 + y2
+ y3 + y4 ≥
2, yi
≥ 0 (i = 1, 2, 3, 4).
-y1 +4y2 - 2y3 - 2y4 ≥ 3,
Для решения исходной задачи, необходимо вести четыре дополнительные переменные и после преобразования системы - одну искусственную. Таким образом, исходная симплексная таблица будет состоять из шести строк и девяти столбцов, элементы которых подлежат преобразованию.
Для решения двойственной задачи необходимо вести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.
Двойственную задачу решаем симплексным с методом (табл.2.3). Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2.
Оптимальный план исходной задачи находим, используя оценки (m+1)-й строки последней итерации, стоящие в столбцах А5, А6, А7: х1 = 3/2 + 0 = 3/2;
х2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи
Х* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin=21/2.
Таблица 2.3
|
i |
Базис |
С базиса |
А0 |
2 |
3 |
6 |
3 |
0 |
0 |
0 |
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
||||
|
1 2 3 |
А5 А6 А7 |
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 |
Zj – Cj |
0 |
-2 |
-3 |
-6 |
-3 |
0 |
0 |
0 |
|
|
1 2 3 |
А3 А6 А7 |
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 |
Zj
– Cj |
6 |
10 |
-9 |
0 |
9 |
6 |
0 |
0 |
|
|
1 2 3 |
А3 А2 А7 |
6 3 0 |
3/2 ½ 2 |
2 0 3 |
0 1 0 |
1 0 0 |
3/2 -1/2 4 |
½ -1/2 5 |
1/2 1/2 3 |
0 0 1 |
|
m+1 |
Zj
– Cj |
21/2 |
10 |
0 |
0 |
9/2 |
3/2 |
9/2 |
0 |
|