Симплекс метод - пример решения.

Z = -X1 + 8X2     max(min)

X1 – 2X2 ≤ -2,

-2X1 + 3X2 ≤ 6

2X1 + 4X2 ≤ 0,

X2≥0

Решение

Вместо переменной Х1 произвольного знака вводим переменные Х1’ и X1’’.

X1 = Х1’ - X1’’.

Запишем систему неравенств в виде:

    (Х1’ - X1’’) -  2Х2  ≤ -2

-2(Х1’ - X1’’) + 3Х2  ≤ 6                                        

                                                     2(Х1’ - X1’’) + 4Х2  ≤ 0

Получим:

  Х1’ -    X1’’-    2Х2  ≤ -2

                                                -2Х1’ + 2X1’’+ 3Х2  ≤ 6                                         (1)

                                                      2Х1’ -   2X1’’ +4Х2  ≤ 0

Условие положительности:

Х1’≥0, X1’’≥0, X2≥0.                                                          (2)

Целевая функция:

F = -(Х1’ - X1’’) + 8X2 = -Х1’ + X1’’ + 8X2    (max)                                                     (3)

Задача записана в симметричной фоме записи. Приведем задачу к канонической форме записи, для этого введем дополнительные переменные Х3, Х4, Х5. Расширенная система задачи имеет вид:

    Х1’ -    X1’’-    2Х2  +Х3  = -2

-2Х1’ + 2X1’’+ 3Х2  +Х4 = 6

2Х1’ -   2X1’’ + 4Х2 +Х5 = 0

Условия неотрицательности примут вид:

Xj≥0 (j=1,..,5).

Заполним первую симплексную таблицу (Табл. 1), в которой переменные X3, X4, X5 являются базисными, переменные Х1’, X1’’, X2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.

Таблица 1. Первая (начальная) симплексная таблица

 

 

В результате симплексного преобразования, получим вторую симплексную таблицу (Табл.2).

 

 

 

 

 

 

Таблица 2. Вторая симплексная таблица

Таблица 3. Третья симплексная таблица

Таблица 4. Четвертая симплексная таблица

 

В последней строке все элементы неотрицательные, критерий оптимальности выполнен, значит опорный план (0; 1,714; 0,857; 1,423; 0; 0) является опти­мальным, а соответствующее ему значение 8,571 целевой функции будет макси­мальным. Х1 = - 1,714.

Мы получили такое же решение, что и графическим методом.

Найдем минимальное значение целевой функции. Для этого целевую функцию запишем в виде:

-F = Х1’ - X1’’ - 8X2    (max)

Первая симплексная таблица запишется в виде табл. 5. В таблице 5 в столбце свободных членов есть отрицательный элемент, следовательно, план не является опорным.

Таблица 5.

 

 

 

Переходим ко второй симплексной таблице.

Таблица 6.

Таблица 7.

Таблица 8.