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

Методискусственного базиса. Если после подготовки ЗЛПк специальному виду для решения симплекс методом, не в каждой строке системыограничений есть базисная переменная входящая в данную строку с коэффициентом1, а в остальные строки с коэффициентом 0 , то для решения данной ЗЛП надовоспользоваться методом искусственного базиса. Суть метода довольнопроста К строкам, в которых отсутствует базисная переменная добавляется по одной искусственной базисной переменной. Новая задача решается Симплекс-методом, причем все искусственные базисные переменные должны стать свободными выйти из базиса и их сумма должна равняться нулю, в обратном случае в данной системе невозможно выделить допустимый базис. Рассмотрим следующийпример min f В первом уравнении нет базисных неизвестных.

Введ м искусственную базисную неизвестную Y1 и заполним первую симплекс-таблицуДля того, чтобы избавитсяот искусственной базисной неизвестной нам предстоит решить вспомогательнуюзадачу F Y1 8594 minВыражая базиснуюнеизвестную Y1 через свободные получаем F 4X1 X2 4 8594 min Б X1 X2 X3 X4 Y1 С Y1 4 1 0 0 1 4 X4 11 3 -5 -1 0 12 F 4 1 0 0 0 4 Выбираем элемент в ячейке 3 2 и делаем шаг. Б X1 X2 X3 X4 Y1 С X2 4 1 0 0 1 4 X4 -1 0 -5 -1 -3 0 F 0 0 0 0 -1 0 min f 0,все коэффициенты в последней строке меньше или равны нулю, следовательно мыперешли к новому естественному базису.

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

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