АЛГОРИТМ СИМПЛЕКС-МЕТОДА
.docАЛГОРИТМ СИМПЛЕКС-МЕТОДА
Шаг 1. Подготовка симплекс-матрицы.
-
Перейти к основной задаче (Основной будем называть задачу нахождения максимума целевой функции на множестве неотрицательных решений системы линейных уравнений.)
-
От основной задачи перейти к канонической задаче (метод искусственного базиса). Определение: Основная задача называется канонической, если её ограничения имеют каноническую форму, т.е. каждое уравнение содержит переменную с коэффициентом плюс единица, не входящую в остальные уравнения.
-
Каноническую задачу записать в симплекс-матрицу.
-
В индексной строке занулить элементы, соответствующие базисным переменным.
Шаг 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.
Таким образом, можно говорить о практической конечности симплекс-метода для канонической задачи за конечное число шагов: либо получается оптимальное решение, либо устанавливается его отсутствие.