14.2.1. Симплексные таблицы и алгоритм решения

Приведем здесь алгоритм решения задач симплексным методом.

1. Математическая модель задачи должна оыть канонической. Если в исходной формулировке задача неканоническая, то ее надо привести к каноническому виду.

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

Симплексная таблица имеет следующий вид. и-

и по формуле

для обо бод лого члена.

Возможны следующие случаи при решении задачи на максимум:

• если нее (щенки Д,£0. то найденное решение оптимальное:

• если хотя бы одна оценка Д- о°, т. е. целевая функция не ограничена в области допустимых решений;

• если хотя бы одна оценка отрицательная, а при соотвстствутощен переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

• если отрицательных оценок в индексной проке несколько, то в столбец базисной переменной (БГ1) вводят ту переменную, которой соответствует наибольшая но абсолютной величине отрицательная оценка.

Пусть одна оценка Д( < О или наибольшая по абсолютной величине Д4 < 0, тогда А-н столбец принимаем за ключевой За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (А,) к положительным коэффициентам А го столица Элемент, находящийся на пересечении ключевых строки н столбца, называют ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

* переписываем ключевую строку, рйЭлелип сс на ключевой элемент.

* .заполняем базисные столбцы:

* остальные коэффициенты таблицы находим по правилу прямо - угольника*. Оценки можно считать по прицеленным ранее формулам или по правилу «прямоугольникам. Получаем новое опорное решение, которое проверяем на оптимальность и г. д.

Примечания:

2. Правило «прямоугольника* состоит в следующем. Пусть ключевым элементом предыдущего шага является элемент 1-й строки (т + 1)-го столбца /г, я,,. Тогда .племен г г-н строки (т + 2)ю столбца пос ледующего шага, который обозначим А) т,2, по правилу «прямоугольника* определяется по формуле

14.2.2.