Метод искусственного базиса примеры решения. Решение задач линейного программирования методом искусственного базиса
Необходимым условием применения симплекс-метода является наличие опорного плана, то есть допустимого базисного решения канонической системы уравнений. Для этого должны выполняться следующие условия:
- система должна иметь каноническую (ступенчатую) структуру;
- присутствуют только ограничения-равенства;
- правые части ограничений положительны;
- переменные задачи положительны.
Без этих условий нельзя получить опорный план. Однако в реальных задачах далеко не всегда выполняются перечисленные условия.
Существует специальный метод, называемый искусственным базисом, который позволяет в любой задаче линейного программирования получить начальный опорный план.
Пусть задача линейного программирования приведена к стандартному виду:
Пусть все /? > 0, но часть или все базисные переменные отрицательны, X; 0. Следовательно, опорного плана нет.
Дополним уравнения-ограничения искусственными переменными (предполагаем, что все x j j - 1, п ).
Введем т переменных (по количеству уравнений): х лМ т, которые в новой системе будут базисными, а отрицательные х-
В результате получим следующую эквивалентную задачу.
Здесь переменные x n+i не имеют никакого отношения к исходной задаче линейного программирования. Они служат лишь для получения опорного плана и называются искусственными переменными. А новая
целевая функция /(.т) сформирована для полноты задачи.
В оптимальном опорном плане искусственные переменные должны быть равны нулю. В противном случае нарушится условие первоначальной задачи.
В начальном опорном плане искусственные переменные являются базисными, то есть не равны нулю, а в оптимальном плане искусственные переменные должны быть равны нулю. Значит, искусственные переменные должны стать в оптимальном плане свободными. В этом переводе и состоит основная идея метода: перевод искусственных переменных из базисных переменных в свободные. Рассмотрим механизм такого перевода на примере.
Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные х } , х А, х 5 , х 6 и запишем задачу в канонической форме.
Свободные переменные х, х 2 = 0, при этом базисные переменные примут значения х 3 =-5, х 4 = -5, х 5 = 7, х 6 =9. Так как часть базисных переменных отрицательны, следовательно опорного плана нет. Для получения начального опорного плана введем переменные х 7 , х 8 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:
Таким образом, начальным базисом является
Симплекс-таблица с искусственным базисом
|
Х 4 |
|||||||||||
Запишем последовательности опорных планов.
Для первых трех шагов приращения А к вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию /(х) = х 7 + х 8 с коэффициентом с, = 1.
На третьем шаге искусственные переменные исключены, так как все А к положительны.
Итак, симплекс-метод с введением искусственных переменных включает два этапа.
Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи /(х) = 0.
Оптимальный опорный план вспомогательной задачи ЛП является начальным опорным планом основной задачи ЛП. Задача решается для исходной целевой функции /(х) обычным симплекс-методом.
Замечания
- 1. Введение искусственных переменных требуется в двух случаях:
- ряд базисных переменных х, в канонической форме отрицательны;
- если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.
- 2. Встречающиеся в практике автоматического управления задачи линейного программирования содержат от 500 до 1500 ограничений и более 1000 переменных. Ясно, что задачи такой размерности можно решать лишь с помощью ЭВМ и специального программного обеспечения. Сложность алгоритма заключается в том, что:
- ППП требует канонического вида;
- ППП для задач такой размерности требует использования больших ЭВМ (и параллельных вычислений), так как симплекс-метод хранит всю таблицу.
- 3. Вычислительную эффективность симплекс-метода можно оценить следующими показателями:
- число шагов (смежных опорных планов);
- затраты машинного времени.
Существуют такие теоретические оценки для стандартной задачи линейного программирования с т ограничений и «"переменных:
- среднее число шагов * 2 т
и лежит в диапазоне }
