Метод искусственного базиса для чайников

Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:

В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:

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

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

Пример 1. Найти максимум функции F(x) = -x1 + 2x2 – x3 при ограничениях:

Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи

Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x3, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R2 должна быть из базиса исключена. Ведущий элемент обведен контуром.

В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:

Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥

Пример 2 . Найти минимальное значение функции F(x) = 2x1 + 3x2 – x3 при следующих ограничениях

Читайте также:  Мораль и аморальные поступки

Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x4 , x5 и искусственную переменную R следующим образом:

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

Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения . После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.

базисные переменные Свободные члены Небазисные переменные
x1 x2 x3
x4 -6 -2 -1 3
R 4 1 -1 2
x5 5 1 1 1
F 2 3 -1
M -4 -1 1 -2
базисные переменные Свободные члены Небазисные переменные
x4 x2 x3
x1 3 -1/2 1/2 -3/2
R 1 1/2 -3/2 7/2
x5 2 1/2 1/2 5/2
F -6 1 2 2
M -1 -1/2 3/2 -7/2
базисные переменные Свободные члены Небазисные переменные
x4 x2
x1 24/7 -2/7 -1/7
x3 2/7 1/7 -3/7
x5 9/7 1/7 11/7
F -46/7 5/7 20/7
M

Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x4 = x2 = 0;

Пример . Решить задачу ЛП, найдя начальный опорный план методом искусственного базиса.
Определим максимальное значение целевой функции F(X) = 3x3 – 2x4 – x5 при следующих условиях:
2x1 + x2 + x3 + x4 + 3x5=5
3x1 + 2x3 – x4 + 6x5=7
x1 – x3 + 2x4 + x5=2

На этом первый этап (первая фаза) симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x2 = 12 /13 -2 /13x1 -12 /13x3
x5 = 1 3 /13 -7 /13x1 -3 /13x3
x4 = 5 /13 -3 /13x1+ 8 /13x3

Примечание:

  1. Число операций в симплекс-методе не превосходит n!/((n-m)!*m!)
  2. Решение х системы уравнений, в котором все небазисные переменные равны 0, называется базисным решение.
  3. Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решение или опорным планом.
Читайте также:  Моя работа здесь закончена

Необходимым условием применения симплекс-метода является наличие опорного плана, то есть допустимого базисного решения канонической системы уравнений. Для этого должны выполняться следующие условия:

  • • система должна иметь каноническую (ступенчатую) структуру;
  • • присутствуют только ограничения-равенства;
  • • правые части ограничений положительны;
  • • переменные задачи положительны.

Без этих условий нельзя получить опорный план. Однако в реальных задачах далеко не всегда выполняются перечисленные условия.

Существует специальный метод, называемый искусственным базисом, который позволяет в любой задаче линейного программирования получить начальный опорный план.

Пусть задача линейного программирования приведена к стандартному виду:

Пусть все /? > 0, но часть или все базисные переменные отрицательны, X;

В начальном опорном плане искусственные переменные являются базисными, то есть не равны нулю, а в оптимальном плане искусственные переменные должны быть равны нулю. Значит, искусственные переменные должны стать в оптимальном плане свободными. В этом переводе и состоит основная идея метода: перевод искусственных переменных из базисных переменных в свободные. Рассмотрим механизм такого перевода на примере.

Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные х>, хА, х5, х6 и запишем задачу в канонической форме.

Свободные переменные х,, х2 = 0, при этом базисные переменные примут значения х3 =-5, х4 = -5, х5 = 7, х6 =9. Так как часть базисных переменных отрицательны, следовательно опорного плана нет. Для получения начального опорного плана введем переменные х7, х8 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:

Таким образом, начальным базисом является

Симплекс-таблица с искусственным базисом

Запишем последовательности опорных планов.

Для первых трех шагов приращения Ак вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию /(х) = х7 + х8 с коэффициентом с, = 1.

Читайте также:  Лучшие проекторы для дома 2018

На третьем шаге искусственные переменные исключены, так как все Ак положительны.

Эквивалентная задача решена. Далее приращения Д* вычисляются на основе исходной целевой функции

Итак, симплекс-метод с введением искусственных переменных включает два этапа.

Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи /(х) = 0.

Оптимальный опорный план вспомогательной задачи ЛП является начальным опорным планом основной задачи ЛП. Задача решается для исходной целевой функции /(х) обычным симплекс-методом.

  • 1. Введение искусственных переменных требуется в двух случаях:
  • • ряд базисных переменных х, в канонической форме отрицательны;
  • • если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.
  • 2. Встречающиеся в практике автоматического управления задачи линейного программирования содержат от 500 до 1500 ограничений и более 1000 переменных. Ясно, что задачи такой размерности можно решать лишь с помощью ЭВМ и специального программного обеспечения. Сложность алгоритма заключается в том, что:
    • • ППП требует канонического вида;
    • • ППП для задач такой размерности требует использования больших ЭВМ (и параллельных вычислений), так как симплекс-метод хранит всю таблицу.
    • 3. Вычислительную эффективность симплекс-метода можно оценить следующими показателями:
      • • число шагов (смежных опорных планов);
      • • затраты машинного времени.
      • Существуют такие теоретические оценки для стандартной задачи линейного программирования с т ограничений и «"переменных:

        • • среднее число шагов * 2 • т и лежит в диапазоне [/и -ь 2 • (/и + .
        • • расчетное время пропорционально величине (/и 3 )-

        Читайте также:

        Добавить комментарий

        Ваш адрес email не будет опубликован. Обязательные поля помечены *

        Adblock detector