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

Ниже приведено условие  и решение задачи. Закачка решения в формате doc  начнется автоматически через 10 секунд.

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

Z = 2X123 (max)                 

 

           - Х12 -2Х3 4,                 

            3Х1+2Х23 2,                 

 1 2   +Х3 ≥1

 

Хj  ≥0   (j=1,3)                                       

Решение:

Приводим задачу к канонической форме , введя две неотрицательные балансовые переменные Х4 и Х5 , Х6 . Имеем следующую ЗЛП .

Z = 2X123 (max)                 

 

            - Х12 -2Х3 + Х4 = 4,                 

            3Х1+2Х23 +  Х5 = 2,                  (4.1)

 1 2   +Х3 – Х = 1   

             Хj  ≥0   (j=1,6)                                       

     В задаче (4.1) отсутствует исходный допустимый базис . Однако в первом и втором  уравнениях имеется базисные переменные Х4 и Х5 , которые можно ввести в искомый базис . Для третьего уравнения вводим искусственную переменные Х7 . Приходим к следующей М-задаче (М – сколь угодно малое положительное число ).

Z = 2X123+ МХ7 (max)                 

 

             - Х12 -2Х3 + Х4 = 4,                 

            3Х1+2Х23 +  Х5 = 2,                  (4.2)

 1 2   +Х3 – Х7 = 1                       

Хj  ≥0   (j=1,7)                                       

    Прежде заполнения первой симплекс-таблицы  , выразим целевую функцию Z через свободные переменные Х1236 :

  Z = 2X123+М(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 сек, кликните по этой ссылке