Задача линейного программирования. Проверка оптимальности текущего плана, страница 10

xi ≥ 0, i = 1, 2, 3, 4, 5, 6.                                                                  (6)

3)Составим симплексную таблицу

Б

Сб

В

7

-13

-8

10

М

М

A1

A2

A3

A4

A5

A6

1

A5

М

3

1

-1

-3

2

1

0

          (1/2)(1/2)

2

A6

М

2

1

-2

-1

1

0

1

                 +

3

2М-7

-3М+13

-4М+8

3М-10

0

0

Так как М – большое положительное число, то

1 = 2М – 7  > 0, ∆4 = 3М – 10  > 0. Произведем необходимые вычисления

θ1 = min       = 2,     V1 =  (2M – 7) ∙ (2) = 4M – 14 ;

θ4 = min     = ,     V4 =  (3M – 10) ∙  =;

Так как  V4 >V1 , то выгоднее включить в базис столбец А4.

 При этом ведущим элементом будет  а14 = 2.

4)Составим новую таблицу.

Б

Сб

В

7

-13

-8

10

М

М

A1

A2

A3

A4

A5

A6

1

A4

10

3/2

1/2

-1/2

-3/2

1

1/2

0

2

A6

М

1/2

1/2

-3/2

1/2

0

-1/2

1

(2)(-1)

3

М+15

М-2

М+8

М-7

0

М+5

0

Произведем необходимые вычисления

θ 1 θ3

Так как  V1 > V3 , то ведущий элемент будет  

5) Составим новую таблицу.                                        

Б

Сб

В

7

-13

-8

10

М

М

A1

A2

A3

A4

A5

A6

1

A4

10

1

0

1

-2

1

1

-1

       (1) (3)

2

A1

7

1

1

-3

 -1

0

-1

2

                +

3

17

0

2

-5

0

-М+3

-М+4

Итак, мы перешли к таблице, в которой А5 и А6 уже не являются базисными столбцами. Поэтому мы их зачеркнем. Произведем необходимые вычисления.

θ2 .Значит а12 = 1 – ведущий элемент.


6) Составим новую таблицу.

Б

Сб

В

7

-13

-8

10

A1

A2

A3

A4

1

A2

-13

1

0

1

-2

1

2

A1

7

4

1

0

 -5

3

3

15

0

0

-1

-2

Все оценки неположительные, значит текущий план Х*= (4; 1; 0; 0) оптимален, ему соответствует минимальное значение функции  Z(Х) = 15.

Пример 11. Z(X) = - 3x1 + x2 → max,                                            (1)

 х1 – 2х2 + х3 = 10 ,

-2х1 – х2 + 0х3 = 10 ,                                                                         (2)