Как решать задачи симплекс-методом
- Решение задач с N-неизвестными с помощью симплекс-метода
- Шаг 1: Отображение системы ограничений
- Шаг 2: Расчет базисных величин
- Шаг 3: Проверка оптимальности базисного решения
- Шаг 4: Составление симплекс таблицы
- Шаг 5: Поиск оптимального решения
- Шаг 6: Поиск положительных величин
- Шаг 7: Выбор разрешающего коэффициента
- Шаг 8: Построение новой таблицы
- Шаг 9: Преобразование элементов таблицы
- Шаг 10: Поиск оптимального решения
Решение задач с N-неизвестными с помощью симплекс-метода
В задачах, где имеется N-неизвестных, область допустимых решений представляет собой выпуклый многогранник в N-мерном пространстве. Графическое решение таких задач становится невозможным, поэтому требуется применение симплекс-метода линейного программирования.
Шаг 1: Отображение системы ограничений
Первым шагом необходимо отобразить систему ограничений в виде системы линейных уравнений, где количество неизвестных превышает количество уравнений. При этом выбирается R неизвестных при ранге системы R.
Шаг 2: Расчет базисных величин
Далее следует назначать конкретные значения свободным переменным и расчитывать базисные величины, значения которых должны быть неотрицательными. Если базисными величинами являются значения от X1 до Xr, то решение системы будет опорным при условии, что значения от b1 до br ≥ 0.
Шаг 3: Проверка оптимальности базисного решения
После проверки допустимости базисного решения, следует проверить его на оптимальность. Если решение не является оптимальным, требуется перейти к следующему опорному решению. При каждом новом решении линейная форма будет приближаться к оптимуму.
Шаг 4: Составление симплекс таблицы
Для составления симплекс таблицы, необходимо перенести члены с переменными в левую часть и оставить свободные от переменных члены в правой части. Таблица представляет собой табличную форму, где в столбцах указываются базовые переменные, свободные члены, X1....Xr, Xr+1...Xn, а в строках отображаются X1....Xr, Z.
Шаг 5: Поиск оптимального решения
Проанализировав последнюю строку таблицы, выбирается либо минимальное отрицательное число при поиске максимума, либо максимальное положительное при поиске минимума. Если таких значений нет, то найденное базисное решение можно считать оптимальным.
Шаг 6: Поиск положительных величин
Исследуя столбец таблицы, который соответствует выбранному положительному или отрицательному значению в последней строке, выбираются положительные величины. Если такие величины не обнаруживаются, задача не имеет решения.
Шаг 7: Выбор разрешающего коэффициента
Среди оставшихся коэффициентов столбца выбирается тот, для которого соотношение свободного члена к этому элементу минимально. Этот коэффициент становится разрешающим, а строка, в которой он находится, становится ключевой.
Шаг 8: Построение новой таблицы
Базисная переменная, соответствующая строке разрешающего элемента, переводится в разряд свободных переменных, а свободная переменная, соответствующая столбцу разрешающего элемента, становится базисной. Строится новая таблица с другими названиями базисных переменных.
Шаг 9: Преобразование элементов таблицы
Все элементы ключевой строки, кроме столбца свободных членов, делятся на разрешающие элементы и вносятся в строку с откорректированной базисной переменной в новой таблице. Элементы ключевого столбца, равные нулю, всегда остаются единицей. Столбец, где в ключевой строке есть ноль, и строка, где в ключевом столбце есть ноль, сохраняются в новой таблице. Результаты преобразования элементов из старой таблицы записываются в другие ячейки новой таблицы.
Шаг 10: Поиск оптимального решения
Исследуются варианты до тех пор, пока не будет найдено оптимальное решение. При этом следует обратить внимание на условия для одной из вершин многогранника при поиске максимума. Если эта вершина не соответствует минимуму или максимуму, следует перейти к соседней вершине. Переход от одной вершины к другой позволит улучшить значение функции цели.
Симплекс-метод применим к любым задачам линейного программирования, представленным в канонической форме. При наличии небольшого числа переменных и условий ограничений, задачи могут быть решены вручную. Однако, при значительном количестве переменных, рекомендуется использовать симплекс таблицы для более эффективного решения.