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

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

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

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

и по формуле

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

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

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

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

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

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

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

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

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

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

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

где h_i,m+2, h_i,m+1, h_1,m+1— элементы 1-го шага.

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

Поиск по сайту: