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

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

Получаем

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

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

,.

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

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

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

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

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

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

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

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

Пример 5.

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

Вид печи	П1	П2	П3
Трудоемкость, н/ч		0,9	1,2
Себестоимость, ден.ед.

Дата добавления: 2013-12-13