метод искуственного базиса

a1,1x1+a1,2x2+...a1,nxn+xn+1=b1

F=a0,1x1+a0,2x2+...a0,nxn +b0 max

PПриводим задачу ЛПPPк каноническому виду

PПодготовительный этап

PАлгоритм метода искусственного базиса.

Элементы дополнительной строки M расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные Ri) взятая с противоположным знаком.

Исходная таблица для "Метода искусственного базиса" имеет следующий вид:

При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (xn+m) и искусственные (Ri)- базисными.

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна для составляющей F, а другая для составляющей M.

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

Данный метод решения применяется при наличии в системе ограничений и условий-равенств, и условий-неравенств, и является модификацией . Решение системы производится путём ввода искусственных переменных Ri со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).

Метод искусственного базиса (Симплекс-метод)

Задача коммивояжера

Задача поиска центра

Задача поиска медианы

Задачи размещения

Задачи поиска путей

Задачи линейного программирования

Задачи оптимизации

Линейное программирование/Симплекс-метод/Метод искусственного базиса