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

Для исходной задачи

Получаем

Целевая функция выражена через свободные переменные и максимизирована .

Задача приведена к каноническому виду, причем все элементы столбца свободных членов неотрицательны

, .

2) найден начальный опорный план задачи , .

4) составим исходную симплекс-таблицу, определяем ведущий столбец и ведущую строку и выполняем шаг методаЖордана-Гаусса

5) продолжаем так же до тех пор, пока в z-строке все элементы не станут неотрицательными

, но свободной переменной соответствует нулевой элемент в z-строке, поэтому продолжаем

\Если начальный опорный план задачи находится методом искусственного базиса, то сначала надо решить симплекс-методом вспомогательную w-задачу. При этом необходимо в начальную симплексную таблицу включить и z-строку, соответствующую целевой функции исходной задачи. Для составления симплекс-таблицы из функции z исключают базисные переменные, а из функции w – искусственные базисные переменные.

Возможны следующие случаи:

1.В оптимальном решении w-задачи хотя бы одна из искусственных переменных отлична от нуля (т.е. не вышла из базиса). Тогда исходная z-задача не имеет допустимых планов (т.е. ее система ограничений не совместна).

2.В оптимальном решении новой w-задачи все искусственные переменные раны нулю (т.е. вышли из базиса), а, значит, и искусственная целевая функция равна нулю. Тогда значения оставшихся координат плана дадут начальный опорный план исходной задачи, которую можно решить симплекс-методом.

Пример 5.

Хлебозавод может выпекать хлеб в любой из трех видов печей П1, П2, П3. Трудоемкость и себестоимость выпечки 1 центнера хлеба представлены в таблице. Сколько необходимо выпечь в каждой печи, чтобы его суммарная себестоимость была минимальной при условии, что трудовые ресурсы ограничены н/ч, а общее количество горячего хлеба должно быть не менее 60 ц?