 |
|
Построение двойственной задачи
Пример 1. Построить двойственную задачу к исходной:
Z = x1 + x2 + x3 => min
x1 + 2x2 + x3 ≥9
2x1 + x3 ≥4
х1 ≥ 0, х2 ≥ 0,х3 ≥ 0.
Последовательность решения задачи.
1. В исходной задаче целевая функция минимизируется, знаки всех неравенств « ≥ ».Поэтому можно сразу приступить к построению двойственной задачи.
В исходной задаче целевая функция минимизируется, поэтому в двойственной она будет максимизироваться.
В исходной задаче все ограничения имеют вид « ≥ », поэтому в двойственной все ограничения будут иметь вид « < ».
В исходной задаче два ограничения, поэтому в двойственной будет две переменных у1 и у2.
Объемы ограничений исходной задачи будут коэффициентами при переменных в целевой функции двойственной задачи.
Коэффициенты при переменных в целевой функции исходной задачи будут объемами ограничений двойственной задачи.
Оба ограничения исходной задачи имеют вид неравенства, поэтому на две переменные двойственной задачи будут наложены условие неотрицательности, т.е. у1 ≥ 0, у2 ≥ 0.
2. Составим расширенную матрицу системы:
1 2 1 9
A1 = 2 0 1 4
…………..
1 1 1 Z
3. Найдем матрицу Ат1, транспонированную к А1.
1 2 1
2 0 1
Ат1 = 1 1 1
---------------
9 4 F
4.Сформулируем двойственную задачу:
F = 9y1 + 4y2 => max
y1 + 2y2 < 1
2y1 < 1
y1 + y2 < 1
. у1 ≥ 0, у2 ≥ 0.
Пример 2. . Построить двойственную задачу к исходной:
Z = -x1 + 2x2 => max
2х1 - х2 ≥1
-х1 + 4х2 <24
х1 - х2 <3
х1 + х2 ≥5
х1 ≥ 0, х2 ≥ 0.
Последовательность решения задачи.
1. Так как исходная задача решается на максимум, то приведем все неравенства системы ограничений к виду «< », для чего обе части первого и четвертого неравенства умножим на -1.
Получим:
-2 х1 + х2 <-1
-х1 + 4х2 <24
х1 - х2 <3
-х1 - х2 <-5
2. Составим расширенную матрицу системы.
 | |||
 | |||
-2 1 -1
-1 4 24
A1 = 1 -1 3
-1 -1 -5
-----------------
-1 2 Z
3. Найдем матрицу Ат1, транспонированную к А1.
 |
-2 -1 1 -1 -1
1 4 -1 -1 2
Ат1 = --------------------------
-1 24 3 -5 F
4.Сформулируем двойственную задачу.
F = -у1 + 24у2 + 3у3 - 5у4 => min
 |
-2у1 - у2 + у3 - у4 ≥ -1
у1 + 4у2 - у3 - у4 ≥ 2
у1 ≥ 0, у2 ≥ 0, у3 ≥ 0, у4 ≥ 0.
Пример 3. Построить двойственную задачу к исходной:
Z = x1 - 2x2 + x3 - x4 + x5 => min
 |
х1 - 2х2 + х3 + 3х4 - 2х5 = 6
2х1 + 3х2 - 2х3 - х4 + х5 < 4
х1 + 3х3 - 4х5 ≥ 8
х1 ≥ 0, х3 ≥ 0, х5 ≥ 0;
х2 и х4 не имеют ограничения знака.
Последовательность решения задачи.
1 Умножим второе неравенство системы на -1. Так как целевая функция исходной задачи минимизируется, то все ограничения задачи должны иметь знак >.
В исходной задаче число ограничений три, поэтому в двойственной будет три переменных у1, у2, у3.
В исходной задаче пять переменных, поэтому в двойственной будет пять ограничений.
В исходной задаче на переменные х1, х3, х5 наложены условия неотрицательности, поэтому в двойственной задаче первое, третье и пятое ограничения будут неравенствами.
В исходной задаче переменные х2 и х4 не имеют ограничения знака, поэтому в двойственной задаче второе и четвертое ограничения будут уравнениями.
Второе и третье ограничения исходной задачи – неравенства, поэтому на переменные у2 и у3 в двойственной задаче будет наложено условие неотрицательности: у2 ≥ 0, у3 ≥ 0.
Первое ограничение исходной задачи – уравнение, поэтому переменная у1 в двойственной задаче – без ограничения знака.
2 Составим расширенную матрицу системы.
1 -2 1 3 -2 6
-2 -3 2 1 -1 -4
A1 =1 0 3 0 -4 8
---------------------------------------
Z
3 Найдем матрицу Ат1, транспонированную к А1.
1 -2 1 1
-2 -3 0 -2
1 2 3 1
Ат1 = 3 1 0 -1
-2 -1 -4 1
------------------------------
6 -4 8 F
4 Сформулируем двойственную задачу.
F = 6y1 - 4y2 + 8y3 => max
 |
y1 - 2y2 + y3 < 1
-2y1 - 3y2 = -2
y1 + 2y2 + 3y3 < 1
3y1 + y2 = -1
-2y1 - y2 - 4y3 < 1
у2 ≥ 0, у3 ≥ 0; у1 не имеет ограничения знака.