2. Симплексный метод: переход к нехудшему опорному плану, симплексные преобразования.

Рассмотрим задачу ,

, , ,

, .

Начальный опорный план , . Если все оценки свободныхпеременных , то план Х₀ - оптимальный. Если существуют положительные оценки свободных переменных, то столбец, которому соответствует наибольшее значение ∆j называется разрешающим. Обозначим его номер j_o, а величину x_jo введем в базис.

Т.к. ∆_jо > 0, то, не изменяя нулевых значений всех свободных переменных, можно уменьшить функцию Z за счет увеличения x_jo.

.

Чтобы перейти к новому опорному плану из базиса нужно вывести одну из переменных.

Значение xj_o нужно увеличить так, чтобы ни одно из значений базисных переменных x_i не было отрицательным. Т.е.

.

Возможны два случая.

1) Все элементы разрешающего столбца j_o неположительны, т.е. a_ijo ≤ 0. Если при решении задачи на min (max) в индексной строке имеются положительные (отрицательные) оценки свободных переменных, а в столбце переменной xj_o нет ни одного положительного элемента, то целевая функция не ограниченна снизу (сверху) на множестве допустимых планов задачи.

2) Если среди элементов разрешающего столбца имеются положительные, то x_jo можно увеличивать до тех пор, пока не нарушается система неравенств:

. .

Отсюда получаем .

Пусть данное выражение выполняется при i=i_o, тогда .

Если условие выполняется при нескольких i, то в качестве i_o можно выбрать любое. Строку i_o называют разрешающей, элемент - разрешающим.

Новое значение целевой функции: .

В результате преобразований целевая функция уменьшилась. Теперь новую базисную переменную нужно выразить через свободные и подставить в систему ограничений и целевую функцию. Причем старая базисная переменная становится свободной.

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

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

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

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

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

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

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

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

8. вычисляем элементы индексной строки и . Для контроля вычислений можно вычислить и .

9. алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности.

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

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