1.Линейное программирование
1.1Решение задачи 1.1
Максимизировать целевую функцию:
Y=-x1+9x2-3x3 → max
При ограничениях:
-x1-2x2-x3 ≥ -5
-x1+x2-2x3 ≤ -5
x1+2x2+x3 ≤ 7
x1,2,3,4 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6.
x1+2x2+x3 +x4+0x5+0x6=5
x1-x2+2x3 +0x4-x5+0x6=5
x1+2x2+x3 +0x4+0x5+1x6=7
Выразим допустимый базис в форме Таккера:
X4=5-( x1+2x2+x3)
X5=-5-(-x1+x2-2x3)
X6=7-( x1+2x2+x3)
Целевая функция в форме Таккера:
Y=0-(1x1-9x2+3x3)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.1).
Таблица 1.1
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X4 |
5 |
1 |
2 |
1 |
1 |
0 |
0 |
|
X5 |
-5 |
-1 |
1 |
-2 |
0 |
1 |
0 |
|
X6 |
7 |
1 |
2 |
1 |
0 |
0 |
1 |
|
Y |
0 |
1 |
-9 |
3 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X5. Результат отображен в таблице 1.2.
Таблица 1.2
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X4 |
0 |
0 |
3 |
-1 |
1 |
1 |
0 |
|
X1 |
5 |
1 |
-1 |
2 |
0 |
-1 |
0 |
|
X6 |
2 |
0 |
3 |
-1 |
0 |
1 |
1 |
|
Y |
-5 |
0 |
-8 |
1 |
0 |
1 |
0 |
Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X4. Результат отображен в таблице 1.3.
Таблица 1.3
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
|
X2 |
0 |
0 |
1 |
-1/3 |
1/3 |
1/3 |
0 |
|
X1 |
5 |
1 |
0 |
5/3 |
1/3 |
-2/3 |
0 |