Задача линейного программирования методом исскуственного базиса.
Ниже приведено условие и решение задачи. Закачка решения в формате doc начнется автоматически через 10 секунд.
Решить методом искусственного базиса задачу линейного программирования при условии неотрицательности всех переменных .
Z = 2X1 +Х2 +Х3 (max)
- Х1+Х2 -2Х3 4,
3Х1+2Х2 +Х3 2,
2Х1 -Х2 +Х3 ≥1
Хj ≥0 (j=1,3)
Решение:
Приводим задачу к канонической форме , введя две неотрицательные балансовые переменные Х4 и Х5 , Х6 . Имеем следующую ЗЛП .
Z = 2X1 +Х2 +Х3 (max)
- Х1+Х2 -2Х3 + Х4 = 4,
3Х1+2Х2 +Х3 + Х5 = 2, (4.1)
2Х1 -Х2 +Х3 – Х6 = 1
Хj ≥0 (j=1,6)
В задаче (4.1) отсутствует исходный допустимый базис . Однако в первом и втором уравнениях имеется базисные переменные Х4 и Х5 , которые можно ввести в искомый базис . Для третьего уравнения вводим искусственную переменные Х7 . Приходим к следующей М-задаче (М – сколь угодно малое положительное число ).
Z = 2X1 +Х2 +Х3+ МХ7 (max)
- Х1+Х2 -2Х3 + Х4 = 4,
3Х1+2Х2 +Х3 + Х5 = 2, (4.2)
2Х1 -Х2 +Х3 – Х6 +Х7 = 1
Хj ≥0 (j=1,7)
Прежде заполнения первой симплекс-таблицы , выразим целевую функцию Z через свободные переменные Х1,Х2,Х3,Х6 :
Z = 2X1 +Х2 +Х3+М(1 -2Х1 + Х2 – Х3 + Х6) =
=М + (-2М +2)Х1 + (1 + М)Х2 + (1 – М)Х3 + МХ6
Откуда имеем
Z + (2М -2)Х1 + (-1 - М)Х2 + (-1 + М)Х3 – МХ6= М
Заполняем первую симплекс таблицу .
Симплексная таблица №1
Б
|
К
|
Х1 |
Х2 |
Х3 |
Х6 |
Х4 |
Х5 |
Х7 |
Х4 |
4 |
-1 |
1 |
-2 |
0 |
1 |
0 |
0 |
Х5 |
2 |
3 |
2 |
1 |
0 |
0 |
1 |
0 |
Х7 |
1 |
2 |
-1 |
1 |
-1 |
0 |
0 |
1 |
Z
|
М
|
2М-2 |
-1 – М |
-1+М |
-М |
0 |
0 |
0 |
Переходим к таблице №2.
Симплексная таблица №2.
Б
|
К
|
Х1 |
Х2 |
Х3 |
Х6 |
Х4 |
Х5 |
Х7 |
Х4 |
4,5 |
0 |
0,5 |
-1,5 |
-0,5 |
1 |
0 |
0,5 |
Х5 |
0,5 |
0 |
3,5 |
-0,5 |
1,5 |
0 |
1 |
-1,5 |
Х1 |
0,5 |
1 |
-0,5 |
0,5 |
-0,5 |
0 |
0 |
0,5 |
Z
|
1
|
0 |
-2 |
0 |
-1 |
0 |
0 |
-М+1 |
Переходим к таблице №3.
Симплексная таблица №3.
Б
|
К
|
Х1 |
Х2 |
Х3 |
Х6 |
Х4 |
Х5 |
Х7 |
Х4 |
4,4286 |
0 |
0 |
-1,4286 |
-0,7143 |
1 |
-0,1429 |
0,7143 |
Х2 |
0,1429 |
0 |
1 |
-0,1429 |
0,4286 |
0 |
0,2857 |
-0,4286 |
Х1 |
0,5714 |
1 |
0 |
0,4286 |
-0,2857 |
0 |
0,1429 |
0,2857 |
Z
|
1,2857 |
0 |
0 |
-0,2857 |
-0,1429 |
0 |
0,5714 |
0,1429-М |
Переходим к таблице №4.
Симплексная таблица №4.
Б
|
К
|
Х1 |
Х2 |
Х3 |
Х6 |
Х4 |
Х5 |
Х7 |
Х4 |
6,3333 |
3,3333 |
0 |
0
|
-1,6667 |
1 |
0,3333 |
1,6667 |
Х2 |
0,3333 |
0,3333 |
1 |
0 |
0,3333 |
0 |
0,3333 |
-0,3333 |
Х3 |
1,3333 |
2,3333 |
0 |
1 |
-0,6667 |
0 |
0,3333 |
0,6667 |
Z
|
1,6667 |
0,6667 |
0 |
0 |
-0,3333 |
0 |
0,6667 |
0,3333-М |
Переходим к таблице №5.
Симплексная таблица №5.
Б
|
К
|
Х1 |
Х2 |
Х3 |
Х6 |
Х4 |
Х5 |
Х7 |
Х4 |
8 |
5 |
5 |
0
|
0 |
1 |
2 |
0 |
Х6 |
1 |
1 |
3 |
0 |
1 |
0 |
1 |
-1 |
Х3 |
2 |
3 |
2 |
1 |
0 |
0 |
1 |
0 |
Z
|
2 |
1 |
1 |
0 |
0 |
0 |
1 |
0-М |
В строке для целевой функции нет отрицательных чисел , что свидетельствует о достижении оптимального решения М-задачи .
Zmax = 2 , X* = ( 0 ; 0 ; 2 )
Имя файла: mathprog8.doc
Размер файла: 64 Kb
Если закачивание файла не начнется через 10 сек, кликните по этой ссылке