2015-04-06
1132
Теория двойственности находит широкое практическое применение. Сформулированные теоремы двойственности позволяют получить решение одной задачи, процесс решения которой по той или иной причине затруднителен, по оптимальному решению двойственной к ней. К такой причине относится значительное превышение числа ограничений над числом переменных задачи, так как объем вычислений при решении задач линейного программирования симплекс-методом определяется, в основном, числом ограничений. Также при необходимости решения задачи с ограничениями вида «>=» можно перейти к решению двойственной, которая будет иметь ограничения вида «<=», что позволяет избежать ввода искусственных переменных.
Рассмотрим процесс получения решения двойственной задачи на основании оптимального решения исходной. Подставим в ограничения исходной задачи значения переменных x1* = 2, x2* = 4 в оптимальном плане:
6*2 +6*4 <= 36
4*2 + 8*4 <= 40
4*2 + 2*4<= 20
На основании второй основной теоремы двойственности переменная двойственной задачи y2, соответствующая второму ограничению исходной, которое обратилось при подстановки оптимального плана в строгое неравенство, равна нулю (y2* = 0).
|
|
|
Поскольку переменные x1, x2 в оптимальном плане имеют положительные значения, то соответствующие им ограничения двойственной задачи при подстановке в них ее оптимального плана обращаются в равенство. Учитывая, что y2* = 0, получим
6y1 + 4y3 = 12,
6y1 + 8y3 = 15.
Решив полученную систему двух линейных уравнений с двумя переменными, найдем оптимальный план двойственной задачи: y1* = 3/2, y2* = 0, y3* = ¾. Согласно первой основной теореме двойственности fmax = zmin = 84.
Контрольные вопросы и упражнения
1. Какая задача называется двойственной?
2. Сформулируйте правило построения двойственной задачи.
3. В чем отличие симметричных задач двойственной пары от несимметричных?
4. Как по решению исходной задачи можно найти решение двойственной?
5. Постройте задачи, двойственные к данным:
а) f = x1 – 2x2 + 3x3 – xi → max;
2x1 – x2 + 2x3 – 3x4 ≤ 5,
x1 + 2x2 – x3 + x4 ≤ 3,
__
xj ≥ 0 (j = 1,4);
б) f = 3x2 – x4 → max;
 |
x1 - 2x2 + x4 = 8,
x2 + x3 – 3x4 = 6,
__
xj ≥ 0 (j = 1,4);
в) f = 5x1 + x2 → max;
x1 – x2 ≤ 2,
x1 – 3x2 ≤ 3,
x1 ≥ 0, x2 ≤ 0;
г) f = x1 – 2x2 → min;
 |
x1 – x2 ≥ 5,
-x1 + x2 ≥ 1,
x1 ≥ 0, x2 ≥ 0.
