Тема 2: симплексный метод

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

Симплексный метод является универсальным, так как позволяет решить практически любую ЗЛП, записанную в каноническом виде.

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

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

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

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

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого составляем симплексную таблицу:

Индексная строка для переменных находится по формуле и по формуле для свободного члена.

Для составления симплекс-таблицы удобно систему ограничений переписать в виде: , - базисные переменные. Целевая функция определена равенством .

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

§ если все оценки , то найденное решение оптимальное;

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

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

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

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

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

§ переписываем ключевую строку, разделив ее на ключевой элемент (на месте ключевого элемента должна получиться единица);

§ заполняем базисные столбцы (в столбец БП вместо переменной, стоящей в строке ключевого элемента, идет та переменная из строки , в столбце которой находится ключевой элемент);

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

§ получаем новое опорное решение, которое проверяем на оптимальность, и т.д. (происходит переход к пункту 2).

Дата добавления: 2014-12-27