АЛГОРИТМ СИМПЛЕКС-МЕТОДА

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Шаг 1. Подготовка симплекс-матрицы.

1. Перейти к основной задаче (Основной будем называть задачу нахождения максимума целевой функции на множестве неотрицательных решений системы линейных уравнений.)

2. От основной задачи перейти к канонической задаче (метод искусственного базиса). Определение: Основная задача называется канонической, если её ограничения имеют каноническую форму, т.е. каждое уравнение содержит переменную с коэффициентом плюс единица, не входящую в остальные уравнения.

3. Каноническую задачу записать в симплекс-матрицу.

4. В индексной строке занулить элементы, соответствующие базисным переменным.

Шаг 2. Анализ симплекс-матрицы.

2.1. Если в индексной строке нет положительных коэффициентов, план оптимален, перейти на шаг 4.

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

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

Шаг 3. Улучшение плана.

3.1. Выбрать столбец с положительным коэффициентом в индексной строке (ключевой столбец). Если таких столбцов несколько, обычно выбирают тот, у которого больший коэффициент.

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

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

3.4. Перейти к шагу 2.

Шаг 4. Оформление решения.

4.1. Полагая свободные переменные равными нулю, получить значения базисных переменных и составить базисный план х*.

4.2. Из последней клетки индексной строки получить оптимальное значение целевой функции .

Т.к. число базисных планов конечно, то после конечного применения шага 2 произойдёт выход из алгоритма по п.2.1.

Таким образом, можно говорить о практической конечности симплекс-метода для канонической задачи за конечное число шагов: либо получается оптимальное решение, либо устанавливается его отсутствие.