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

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

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

Алгоритм преобразования x_j ↔ y_i симплекс-таблицы сводится при этом к следующим операциям.

1. Выделить в таблице разрешающий элемент а_ij. Вычислить его обратную величину l =1/ а_ij и записать в нижней части той же ячейки (в правом нижнем углу).

2. Все элементы разрешающей строки (кроме самого а_ij) умно­жить на l; результат записать в нижней части той же ячейки.

3. Все элементы разрешающего столбца (кроме самого а_ij) умно­жить на –l, результат записать в нижней части той же ячейки.

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

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

6. Переписать таблицу, заменив:

– x_j на y_i и обратно,

– элементы разрешающей строки и столбца – числами, стоящи­ми в нижних частях тех же ячеек,

– каждый из остальных элементов – суммой чисел, стоящих в верхней и нижней части той же ячейки.

Нахождение оптимального решения задачи линейного программирования симплекс-методом распадается на два этапа:

1) Отыскание опорного решения.

2) Отыскание оптимального решения, при котором линейная функция L имеет минимальное значение.

Нахождение опорного решения

· Если все свободные члены в симплекс-таблице неотрицательны, это значит, что опорное решение уже получено.

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

v ищем в строке с отрицательным свободным членом отрицательный элемент. Если такого элемента нет, это признак того, что система уравнений ограничений несовместима с неравенствами x_k ≥ 0 (k = 1,…, n).

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

v далее рассматриваются все элементы данного столбца, имеющие одинаковый знак со свободным членом. Из них выбирается в качестве разрешающего тот, для которого отношение к нему свободного члена минимально.

Отыскание оптимального решения

· Если все свободные члены (не считая строки L) в симплекс-таблице неотрицательны, а в строке L (не считая свободного члена) нет ни одного положительного элемента, то оптимальное решение достигнуто.

· Если в строке L есть положительный элемент, а в столбце, соответствующем ему, нет ни одного положительного элемента, то линейная функция L не ограничена снизу и оптимального решения не существует.

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

Если в столбце, содержащем положительный элемент строки L, не найдется ни одного положительного элемента, чтобы сделать его разрешающим, то в этом случае функция L не ограничена снизу и задача линейного программирования не имеет оптимального решения.

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