Задача линейного программирования методом исскуственного базиса.

         Решить методом искусственного базиса задачу линейного программирования при условии неотрицательности  всех переменных .

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 )