21.2. Алгоритм симплексного метода

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

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

Индексная строка для переменных находится по формуле

И по формуле

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

— если все оценки ΔJ ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка ΔJ ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т. е. целевая функция неограничена в области допусти­мых решений;

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

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

Если хотя бы одна оценка ΔK < 0, то K-Й столбец прини­маем за ключевой. За ключевую строку принимаем ту, кото­рой соответствует минимальное отношение свободных членов (Bi) к положительным коэффициентам K-Гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется Ключевым элементом.

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

— переписываем ключевую строку, разделив ее на ключе­вой элемент;

— заполняем базисные столбцы;

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

* Правило "прямоугольника" заключается в следующем. Пусть ключе­вым элементом 1-го шага является элемент 1-й строки (M + 1)-го столбца H1,M+1. Тогда элемент I-й строки (M + 2)-го столбца 2-го шага — обозначим его H’I,M+2 — согласно правилу "прямоугольника" выражается формулой

Где Hi,M+2, Hi,M+1, H1,M+1 — элементы 1-го шага.

Примечание. Если целевая функция L() требует нахож­дения минимального значения, то критерием оптимальности задачи является неположительность оценок ΔJ при всех J = .

< Предыдущая		Следующая >