Алгоритм.

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

(1)

матрица

2. Строим начальный базисный план. Для этого исходную задачу преобразуем к виду (2)

(2)

где

Вектор – начальный базисный план задачи (1). Вычисляем на нём значение целевой функции и оценки:

и переходим к пункту 3.

3. Строим начальную симплексную таблицу, задающую базисный план .

4. Проверяем выполнение критерия оптимальности плана. Если все оценки , то базисный план (2) оптимален. Задача решена. Если то идём к пункту 5.

5. Проверяем достаточные условия неограниченности целевой функции. Если

(3)

то задача (1) не имеет решения, так как целевая функция не ограничена на множестве планов. Если условие (3) не имеет места, то переходим к пункту 6.

6. Совершаем симплекс-итерацию – переход к новому базисному плану

а) строим новый базис с индексным множеством

где p b q находят из соотношений:

(p-ый столбец-разрешающий);

(q-ая строка-разрешающая);

элемент таблицы – разрешающий.

б) строим новую симплексную таблицу, совершая основное симплексное преобразование по элементу :

7. К новой таблице применяем п.4 алгоритма. И т.д.

Замечание 1. Расчет новой симплексной таблицы нужно начинать с определения значений столбца и строки , так как если для некоторого базисного плана выполняется критерий оптимальности (см. п.4), то нет необходимости вычислять оставшуюся часть таблицы.

Замечание 2. Для проверки правильности вычисления симплексных таблиц можно ввести столбец , который равен сумме всех столбцов таблицы и также вычисляется по правилу прямоугольника.

 

Пример. Симплекс-методом решить следующую задачу

(4)

Решение:

1. Приводим задачу (4) к каноническому виду

(5)

2. Из системы ограничений задачи (5) определяем начальный базисный план.

3. Составляем для задачи (5) начальную симплекс-таблицу и применяем симплекс-метод:

 

    -1    
Базис
-1 1/1
-4 -1
5/1
  -1 -3 -3  
-1
-2 3/1
-1 4/1
-4  
-2
-2 -1 1/3
-1  
               
11/3                
1/3                
15 6 3 25  
                           

 

Таблица 3 задаёт оптимальный план: задачи (4), так как все оценки и

.

Ответ. Задача (3) имеет решение

Задание. Симплекс-методом решить следующие задачи: