Теория двойственности в линейном программировании

1. Теория двойственности в линейном программировании

1. Экономическая интерпретация теории
двойственности
Допустим, что предприятие имеет в своем
распоряжении m видов ресурсов в количестве b i
(i = 1, 2,…, m) единиц, из которых производится
n видов продукции. Для производства единицы
продукции j – го вида (j = 1, 2,…, n) расходуется
aij единиц i – го ресурса. Прибыль от реализации
единицы продукции j – го вида равна cj
денежных единиц.

2.

• Требуется составить такой план выпуска
продукции, при котором предприятие
получает максимальную прибыль.
Обозначим через xj (j = 1, 2,…, n) количество
продукции j – го вида, выпускаемое на
предприятии. Тогда, с учетом принятых
обозначений, функция цели принимает
вид:
• Z = c1x1 + c2x2 + … + cnxn max (1)
• Ограничения по использованию ресурсов
записываются в виде:

3.

a11x1 + a12x2 + … + a1nxn b1
a21x1 + a22x2 + … + a2nxn b2
………………………………………
(2)
am1x1 + am2x2 + … + amnxn bm
• Переменные xj (j = 1, 2,…, n) по смыслу задачи являются
неотрицательными, т.е.
xj 0; j = 1, 2,…, n
(3)
• Предположим теперь, что при изучении вопроса об
использовании ресурсов на предприятии появилась другая
возможность – прямая реализация ресурсов на сторону.
Иначе говоря, некоторая организация решила закупить
ресурсы предприятия и необходимо установить оптимальные
цены на эти ресурсы. При определении цен на ресурсы
предприятие руководствуется следующими
принципиальными положениями:

4.

• 1. цена единицы ресурса i - го вида (p i) не может быть
ниже его себестоимости (si), т.е. pi si (i = 1, 2,…, m),
ибо в противном случае предприятие терпит прямые
убытки от реализации ресурсов;
• 2. при реализации всех ресурсов по их себестоимости
предприятие не получает никакой прибыли. Если при
оптимальном использовании ресурсов предприятие
получает некоторую (пусть даже незначительную)
прибыль, то оно никогда не будет продавать
имеющиеся в его распоряжении ресурсы по их
себестоимости. Таким образом, цена за единицу
ресурса (pi) будет складываться из его себестоимости
(si) и некоторой неотрицательной оценки (y i), т.е. pi =
si + yi; (i = 1, 2,…, m).

5.

• Покупающая организация заинтересована в том, чтобы
затраты на все ресурсы в количествах b 1, b2,…, bm ,были
минимальны, т.е.
• Первая сумма в правой части равенства представляет собой
суммарную себестоимость имеющихся на предприятии
ресурсов, т.е. является величиной постоянной и представляет
собой ту денежную сумму, которая в любом случае
взимается с покупателя. Переменной же величиной, которая
заслуживает детального изучения, является вторая сумма в
приведенном выше выражении. Она представляет собой
денежную сумму, выплачиваемую покупателем владельцу
ресурсов, сверх суммарной себестоимости имеющихся
ресурсов. Эта величина получила название суммарной
оценки ресурсов. Таким образом, покупатель заинтересован
в минимизации суммарной оценки ресурсов, т.е.

6.

• f = b1y1 + b2y2 + … + bmym min (4)
• С другой стороны, предприятие, продающее
ресурсы, заинтересовано в том, чтобы
полученная суммарная оценка ресурсов была
не менее той суммы, которую предприятие
может получить при переработке ресурсов в
готовую продукцию. Иначе говоря:
• Прямая реализация ресурсов целесообразна
только в случае, когда оценка всех ресурсов,
расходуемых на изготовление единицы
продукции каждого вида не меньше, чем
прибыль от реализации единицы продукции.

7.

• На изготовление единицы продукции j – го вида (j = 1, 2,…, n)
расходуется a1j единиц ресурса 1 – го вида, a2j единиц
ресурса 2–го вида,…, amj единиц ресурса m – го вида с
оценками соответственно y1, y2,…, ym. Поэтому, отмеченное
выше требование приобретает вид: a1jy1 + a2jy2 + … + amjym cj;
j = 1, 2,…, n:
a11y1 + a21y2 + … + am1ym c1
a12y1 + a22y2 + … + am2ym c2
………………………………………….(5)
a1ny1 + a2ny2 + … + amnym cn,
• причем, оценки ресурсов не могут быть отрицательными,
т.е.
yi 0; i = 1, 2,…, m. (6)
• Две задачи линейного программирования получили
название пары двойственных задач.

8.

• 2. Симметричные и несимметричные двойственные задачи.
• Рассмотренные задачи обладают следующими свойствами
• 1. условия неотрицательности переменных имеются в обеих
задачах;
• 2. прямая задача решается на максимум, двойственная – на
минимум;
• 3. коэффициенты целевой функции прямой задачи являются
свободными членами в двойственной, и наоборот, свободные
члены прямой задачи являются коэффициентами целевой
функции в двойственной;
• 4. в прямой задаче ограничения заданы неравенствами типа
« », а в двойственной – неравенствами типа « »;
• 5. матрицы коэффициентов в системах ограничений обеих задач
являются транспонированными друг к другу;
• 6. число ограничений одной задачи совпадает с числом
переменных в другой задаче.

9.

• Две задачи линейного программирования,
обладающие указанными свойствами,
называются симметричными двойственными
задачами. Симметричная пара двойственных
задач характеризуется тем, что как в прямой, так
и в двойственной задаче, ограничения задаются
неравенствами.
• Итак, если в исходной задаче линейного
программирования ограничения заданы в виде
уравнений, то двойственная задача имеет тот же
вид, что и в случае симметричной пары, за одним
исключением: двойственные переменные могут
принимать произвольные значения.

10.

• 3. Первая основная теорема двойственности. Если
одна из задач двойственной пары имеет оптимальное
решение, то и другая имеет оптимальное решение,
причем оптимальные значения целевых функций
равны. Если функция цели одной из задач не
ограничена, то область допустимых решений другой
задачи пуста.
• Между неизвестными x1, x2,…, xn+m, исходной задачи и
неизвестными y1, y2,…, ym+n двойственной задачи
установим взаимно однозначное соответствие:
• x1 ym+1; x2 ym+2;…xn ym+n;
• xn+1 y1; xn+2 y2;…, xn+m ym,
• так что базисным неизвестным одной задачи
соответствуют свободные неизвестные другой.

11.

• 4.Решение симметричных двойственных задач.
• При доказательстве первой основной теоремы
двойственности было выяснено, что, решая одну
из задач двойственной пары задач линейного
программирования, мы автоматически решаем и
другую. Соотношения между переменными
прямой и двойственной задач определяются
формулами биекции, причем значения
переменной одной из задач являются оценками
целевой, (m + 1) – й, строки в другой задаче.
• Наиболее распространенным случаем такого рода
является приведенный в таблице

12.

Задача 1 (исходная)
Задача 2
(двойственная)
Z = CX min
F = BY max
AX B
YA C
X 0
Y 0
• При решении исходной задачи, применяется
алгоритм метода искусственного базиса, который
является довольно трудоемким. Используя
симметричность можно вместо исходной задачи
выбрать более удобную двойственную задачу,
решаемую по алгоритму симплексного метода.

13.

• Пример. Решить задачу линейного программирования
F = x1 + x2 + x3 + x4 min
3x1 + 2x2 + x3 80
x1 + 6x2 + 9x3 + 13x4 40
xj 0; j =1, 2, 3, 4.
• Построим двойственную задачу:
Z = 80y1 +40y2 max
3y1 + y2 1
2y1 + 6y2 1
y1 + 9y2 1
13y2 1
y1 0; y2 0.

14.

• Биекция в нашем случае приобретает вид:
• x1 y3; x2 y4; x3 y5; x4 y6; x5 y1; x6 y2,
• Введя в ограничения двойственной задачи
дополнительные переменные y3, y4, y5 и y6 приведем
их к уравнениям. В этом случае двойственная задача
принимает вид:
Z = 80y1 +40y2 max
3y1 + y2 + y3 = 1
2y1 + 6y2 + y4 = 1
y1 + 9y2 + y5 = 1
13y2 + y6 = 1
yi 0; i = 1, 2,…, 6.
• Полученную задачу решаем симплексным методом.
Строим первую симплекс-таблицу.

15.

• Таблица 1
i
Бази
с
С
бази
B
80 40
0
0
0
0
A1
A2
A3
A4
A5
A6
са
1
A3
0
1
3
1
1
0
0
0
2
A4
0
1
2
6
0
1
0
0
3
A5
0
1
1
9
0
0
1
0
4
A6
0
1
0
13
0
0
0
1
–80 –40
0
0
0
0
m+1
Zj – Cj
0

16.

• Таблица 2.
i
Бази
с
С
бази
B
80
40
0
0
0
0
A1
A2
A3
A4
A5
A6
1/3
са
1
A1
80
1/3
1
1/3
0
0
0
2
A4
0
1/3
0
16/3 –2/3 1
0
0
3
A5
0
2/3
0
26/3 –1/3 0
1
0
4
A6
0
1
0
0
0
1
–40/3 80/3 0
0
0
m+1
Zj – Cj
80/3 0
13
0

17.

• Таблица 3.
С
i
Базис базис
B
80
40
0
0
0
0
A1
A2
A3
A4
A5 A6
а
1
A1
80
5/16
1
0
3/8
–1/16
0
0
2
A2
40
1/16
0
1
–1/8
3/16
0
0
3
A5
0
1/8
0
0
3/4
–13/8
1
0
4
A6
0
3/16
0
0
13/8 –39/16 0
1
55/2
0
0
m+1
Zj – Cj
25
5/2
0
0

18.

• Полученный план является оптимальным,
т.к. среди оценок (m+1) –й строки нет
отрицательных. Итак, оптимальный план
двойственной задачи: y1 = 5/16; y2 = 1/16; y3
= y4 = 0; y5 = 1/8; y6 = 3/16; Fmin = Zmax = 55/2.
• Значения переменных исходной задачи
находим из (m + 1) – й строки последней
симплексной таблицы двойственной задачи
по правилу: xj = qj. Итак: x1 = 25; x2 = 5/2;
• x3 = x4 = x5 = x6 = 0.

19.

• 5. Двойственный симплексный метод.
• Для решения задачи линейного
программирования применяется алгоритм
двойственного симплексного метода, если
система ограничений задачи задана в виде
уравнений, содержит единичный базис, но среди
свободных членов имеются отрицательные числа.
• Пусть bk < 0, тогда k – е ограничение имеет вид:
• ak1x1 + ak2x2 + … + aknxn = bk
• Если все akj 0 (j = 1, 2,…, n), то задача линейного
программирования не имеет решения из-за
пустоты области допустимых решений.

20.

• Если же некоторые akj < 0, то для столбцов,
содержащих эти отрицательные значения,
вычисляем j = min{bi/aij} 0. Отметим, что
разрешающим элементом в данном случае может
быть и отрицательное число, важно чтобы
отношение bi /aij было неотрицательным.
• Процесс решения задачи разбивается на два
этапа. На первом этапе необходимо избавиться от
отрицательности в столбце свободных членов, на
втором – полученную задачу решаем
симплексным методом.

21.

• Решить задачу линейного
программирования двойственным
симплексным методом:
• Z = x1+ x2 min
• x1 + 2x2 + x3 = 14
• – 5x1 + 3x2 + x4 = 15
• – 4x1 – 6x2 + x5 = – 24
• xj 0; j = 1, 2,…,5.
• Составим первую симплексную таблицу.

22.

• Таблица 1.
С
1
1
0
0
0
A1
A2
A3
A4
A5
i
Базис
1
A3
0
14
1
2
1
0
0
2
A4
0
15
–5
3
0
1
0
3
A5
0
–24
–4
–6
0
0
1
0
–1
–1
0
0
0
m+1
базиса
Zj – Cj
B

23.

• Таблица 2.
С
1
1
0
0
0
A1
A2
A3
A4
A5
i
Базис
1
A3
0
6
–1/3
0
1
0
1/3
2
A4
0
3
–7
0
0
1
1/2
3
A2
1
4
2/3
1
0
0
–1/6
4
–1/3
0
0
0
–1/6
m+1
базиса
Zj – Cj
B

24.

• 7. Вторая основная теорема
двойственности и ее экономическое
содержание. Для того чтобы решения
X =(x1 , x2 ,…, xn ) и Y = (y1 , y2 , …, ym )
пары двойственных задач являлись
оптимальными, необходимо и достаточно
выполнение условий: