- •Скласти двоїсту задачу та визначити методи її розв’язання.
- •Привести злп до канонічної форми.
- •Знайти оптимальне рішення злп на першому етапі двохетапного симплекс-метода.
- •Визначити всі методи розв’язання злп. Знайти оптимальне рішення одним з них.
- •Метод Гомори
- •Розв’язати злп графічним методом.
- •Скласти двоїсту задачу та знайти її рішення.
-
Привести злп до канонічної форми.
min Z=5X1 +16Х2-12Х3
при X1 +5Х2+Х3 22
4Х1 + Х2 4
2Х1 + Х2-8Х3=14
X1,X3 0
Х2 – не обмежена
F(X) = 5x1 + 16x2 + 12x3 → min при ограничениях: x1 + 5x2 + x3>=22 4x1 + x2>=4 2x1 + x2 + 8x3=14 x1>=0 x3>=0 Для приведения ЗЛП к канонической форме необходимо: 1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В 1-м неравенстве смысла (>=) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (>=) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла (>=) вводим базисную переменную x6 со знаком минус. В 5-м неравенстве смысла (>=) вводим базисную переменную x7 со знаком минус. 1x1 + 5x2 + 1x3-1x4 + 0x5 + 0x6 + 0x7 = 22 4x1 + 1x2 + 0x3 + 0x4-1x5 + 0x6 + 0x7 = 4 2x1 + 1x2 + 8x3 + 0x4 + 0x5 + 0x6 + 0x7 = 14 01x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 = 0 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6-1x7 = 0 3. Так как переменная x2, произвольного знака, то она заменяется разностями неотрицательных переменных. x1 + 5(x8 - x9) + x3 - x4 = 22 4x1 + (x8 - x9) - x5 = 4 2x1 + (x8 - x9) + 8x3 = 14 x1 - x6 = 0 x3 - x7 = 0 4. Соответствующая целевая функция примет вид: F(X) = - 5x1 - 16(x8 - x9) - 12x3 или F(X) = - 5x1 - 12x3 - 16x8 + 16x9 → max при ограничениях: x1 + x3 - x4 + 5x8 - 5x9 = 22 4x1 - x5 + x8 - x9 = 4 2x1 + 8x3 + x8 - x9 = 14 x1 - x6 = 0 x3 - x7 = 0 Упростим задачу ЗЛП с заменой всех переменных (сократим их количество). x1 + x2 - x3 + 5x7 - 5x8 = 22 4x1 - x4 + x7 - x8 = 4 2x1 + 8x2 + x7 - x8 = 14 x1 - x5 = 0 x2 - x6 = 0 F(X) = - 5x1 - 12x2 - 16x7 + 16x8 → max Построим двойственную задачу по следующим правилам. 1. Количество переменных в двойственной задаче равно количеству неравенств в исходной. 2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной. 3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется. Расширенная матрица A.
|
1 |
5 |
1 |
22 |
|
4 |
1 |
0 |
4 |
|
2 |
1 |
8 |
14 |
|
01 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
5 |
16 |
12 |
0 |
Транспонированная матрица AT.
|
1 |
4 |
2 |
01 |
0 |
5 |
|
5 |
1 |
1 |
0 |
0 |
16 |
|
1 |
0 |
8 |
0 |
1 |
12 |
|
22 |
4 |
14 |
0 |
0 |
0 |
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной. Неравенства, соединенные стрелочками (↔), называются сопряженными.
|
Исходная задача I |
|
Двойственная задача II |
|
x1 >= 0 |
↔ |
y1 + 4y2 + 2y3 + y4<=5 |
|
x2 любое число 0 |
↔ |
5y1 + y2 + y3=16 |
|
x3 >= 0 |
↔ |
y1 + 8y3 + y5<=12 |
|
5x1 + 16x2 + 12x3 → min |
↔ |
22y1 + 4y2 + 14y3 → max |
|
x1 + 5x2 + x3>=22 |
↔ |
y1 >= 0 |
|
4x1 + x2>=4 |
↔ |
y2 >= 0 |
|
2x1 + x2 + 8x3=14 |
↔ |
y3 любое число |
|
x1>=0 |
↔ |
y4 >= 0 |
|
x3>=0 |
↔ |
y5 >= 0 |