Как решать симплексным методом

Содержание:

1. Инструкция 1: Запись системы ограничений
2. x1 = b1 + a1(r+1)x(r+1) + ... + a1nxn
3. x2 = b2 + a2(r+1)x(r+1) + ... + a2nxn
4. ...
5. xr = br + ar,r+1x(r+1) + ... + amxn
6. Инструкция 2: Рассчет базисных величин
7. Инструкция 3: Проверка оптимальности
8. Инструкция 4: Формирование симплекс-таблицы
9. Инструкция 5: Поиск разрешающего элемента
10. Инструкция 6: Выбор разрешающего коэффициента
11. Инструкция 7: Преобразование переменных

Решение задачи линейного программирования с помощью симплексного метода

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

Инструкция 1: Запись системы ограничений

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

x1 = b1 + a1(r+1)x(r+1) + ... + a1nxn

x2 = b2 + a2(r+1)x(r+1) + ... + a2nxn

...

xr = br + ar,r+1x(r+1) + ... + amxn

Инструкция 2: Рассчет базисных величин

После записи системы ограничений необходимо придать свободным переменным конкретные значения и рассчитать базисные величины. Значения базисных величин должны быть неотрицательными. Если за базисные величины приняты значения от X1 до Xr, то решение системы будет опорным при условии, что значения от b1 до br ≥ 0.

Инструкция 3: Проверка оптимальности

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

Инструкция 4: Формирование симплекс-таблицы

Для проведения дальнейших операций формируется симплекс-таблица. Члены с переменными во всех равенствах переносятся в левую часть таблицы, а свободные члены – в правую. В столбцах таблицы указываются базовые переменные, свободные члены, а также переменные X1...Xr и Xr+1...Xn. В строках таблицы отображаются переменные X1...Xr и функция Z.

Инструкция 5: Поиск разрешающего элемента

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

Инструкция 6: Выбор разрешающего коэффициента

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

Инструкция 7: Преобразование переменных

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