Симплексные преобразования

Правила симплексного преобразования:

1) В индексной строке симплекс-таблицы найти наибольший положительный элемент, если целевая максимизируется, (или отрицательный, в противном случае). Столбец соответствующий этому элементу – разрешающий.

2) Вычислить отношение свободных членов уравнения к положительным элементам разрешающего столбца. Данное отношение называется симплекс-отношением. Найти наименьшее из симплекс-отношений, оно соответствует разрешающей строке.

3) На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент . Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.

4) Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.

5) Переход к следующей таблице. Элементы разрешающей строки новой таблицы будут равны  и .

6) Элементы разрешающего столбца равны нулю, за исключением .

7) Все остальные элементы находятся по формулам

и  .

8) Алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности:

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

б) Опорный план  доставляет целевой функции максимальное значение , если все оценки свободных переменных внеположительны.

4.4 Симплекс-таблица

Решим разобранную выше задачу с помощью симплекс-таблицы.

Получим вторую симплексную таблицу (табл. 5.2)

Критерий оптимальности вновь не выполнен.

Новая симплексная таблица примет вид табл. 5.3.

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, а25 ⁼ 5 — разрешающий элемент.

Переходим к табл. 5.4

Критерий оптимальности выполнен, значит F_max = 24, оптимальное базисное решение (6; 4; 0; 0; 1; 3)