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

Б

Сб

В

-1

-1

0

0

A1

A2

A3

A4

1

A3

0

1

-1

1

1

0

       +

2

A4

0

2

1

-2

0

1

(1)  (1)

3

 

0

1

1

0

0

Находим оценки небазисных столбцов А1 и А2.

1 = Сб ∙ А1 – с1 = (0, 0) ∙ (-1, 1) – (-1) = 1 > 0 , ∆2 = Сб ∙ А2 – с2 = (0, 0) ∙ (1, -2) – (-1) = 1 > 0 .

Так как ∆1 = 1 > 0, ∆2 = 1 > 0, то Х0 не оптимален. Произведем необходимые вычисления

θ1 =   , V1 = 1 ∙ 2 = 2 , θ2 =   , V2 = 1 ∙ 1 = 1 .

Так как V1 > V2, то выгоднее включить в базис столбец А1. При этом ведущий элемент будет а21 = 1.

2) Заполним вторую таблицу.

Б

Сб

В

-1

-1

0

0

A1

A2

A3

A4

1

A3

0

3

0

-1

1

1

2

A1

-1

2

1

-2

0

1

3

 

-2

0

3

0

-1

Так как ∆2 = 3 > 0 , то Х1 = (х1=2, х2=0, х3=3, х4=0) не оптимален.

Находим θ2 =  . В столбце А2 нет положительных элементов, т.е. коэффициент при неизвестном х2 в каждом из уравнений отрицателен. Поэтому оптимального решения не существует. Задача не имеет конечного оптимума min Z(X) = -∞.

Пример 9. Z(X) = x1 – x2 → max,

0x1 – x2 + x3 + x4 = 3,

x1 – 2x2 + 0x3 + x4 = 2,

xi ≥ 0, i = 1,2,3,4.

Решение. Заполним первую симплекс-таблицу.

Б

Сб

В

1

-1

0

0

A1

A2

A3

A4

1

A3

0

3

0

-1

1

1

2

A1

1

2

1

-2

0

1

3

 

2

0

-1

0

1

Так как ∆2 = -1 < 0, то Х0 = (х1 = 2, х2 = 0, х3 = 3, х4 = 0) не оптимален.

Находим  θ2 = . В столбе А2 нет положительных элементов, т.е. коэффициент при неизвестном х2 в каждом из уравнений отрицателен. Поэтому оптимального решения не существует. Задача не имеет конечного оптимума max Z(X) = +∞.

1.2.8. Метод искусственного базиса. Данный метод применяется для решения задачи ЛП симплексным методом в случае, когда задача не имеет первоначального решения с базисом из единичных векторов.

Пример 10.  Z (Х) = 7х1 – 13х2 – 8х3 + 10х4             min,               (1)

(2)

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

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

Решение.1)В левой части ограничений(2)вводим неотрицательные искусственные переменные  х5, х6.

2) Данная задача – задача на нахождение минимума, поэтому х5 и х6 в целевую функцию вводятся с коэффициентом  +М. Получаем

Z (Х) = 7х1 – 13х2 – 8х3 + 10х4 + Мх5 + Мх6 → min,                      (4)

(5)

 
 х1 – х2 – 3х3 +2х4 + х5 + 0х6 = 3,                                                    х1 –2х2 –  х3 +  х4 + 0х5 + х6 = 2,