Случай вырожденных базисных решений при решении задач линейного программирования

Курсовая работа

Напомним, что базисным решением системы линейных уравнений

y₁ = b₁  +   a₁₁(–x₁)  + a₁₂(–x₂)   +…+ a_1j(–x_j)   +…+  a_1n(–x_n),

…………………………………………………………...….

y_i  = b_i  +   a_i1(–x₁)   + a_i2(–x₂)   +…+ a_ij(–x_j)   +…+  a_in(–x_n),               (1)

………………………………………………………………

y_m = b_m + a_m1(–x₁)  + a_m2(–x₂)  +…+ a_mj(–x_j) +…+ a_mn(–x_n).

называется такое решение, которое получается, если все свободные переменные  x₁,…, x_n  положить равными нулю. После шага метода жордановых исключений одна из свободных переменных превращается в базисную переменную и наоборот. Таким образом, система может иметь достаточно много базисных решений (максимальное количество базисных решений совпадает с числом сочетаний  ). Базисное решение системы (1) называется вырожденным, если одна или несколько базисных переменных оказываются равными нулю. Например, первоначальное базисное решение
(0,…, 0,…, 0,  b₁,…, b_i,…, b_m)  системы  (1)  является вырожденным, если один или несколько свободных членов  b₁,…, b_i,…, b_m  окажутся равными нулю.

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

Рассмотрим следующий пример:

Найдем  максимум функции

z(X) = 3x₁ – x₂ – 5x₃                                                                  (2)

при условии того, что переменные удовлетворяют следующей системе:

   3x₁ – 2x₂ –  3x₃ +7 ³ 0,

– 2x₁  +  x₂ – 2x₃ – 3 ³ 0,

– 3x₁  +  x₂  –  x₃  ³ 0,                                                                (3)

– 9x₁ + 2x₂ + 4x₃ – 6 ³ 0,

x₁, x₂, x₃ ³ 0.

Нашей задаче соответствует следующая жорданова таблица:

Табл. 1.

Как всегда, каждый шаг метода Штифеля мы постараемся осуществлять с соблюдением принципа минимального симплексного отношения. Так как в столбце свободных членов есть отрицательные числа  b₂ = – 3  и   b₄ = – 6,  то соответствующее таблице  (1)  базисное решение не является опорным планом задачи. Причем данное базисное решение является вырожденным, т.к. одна из базисных переменных оказалась равной нулю 
(b₃ = 0).  Найдем отрицательные элементы, соответственно во второй и в четвертой строке. Такими элементами являются числа  a₂₂ = – 1,  a₄₂ = – 2  и  a₄₃ = – 4.

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

Во втором столбце в качестве разрешающего элемента можно выбрать или  a₂₂ = – 1,  или  a₄₂ = – 2,  т.к. симплексные отношения для них минимальны и одинаковы.

В третьем столбце в качестве разрешающего элемента может быть только число  a₄₃ = – 4.

Несмотря на похожесть ситуаций во втором и четвертом столбце, между ними есть одна очень существенная разница. В третьей строке таблицы  (1), содержащей нулевой свободный член, элемент второго столбца отрицателен, а третьего – положителен. Данное обстоятельство влияет на знак свободного члена, получающегося в третьей строке после одного шага метода Штифеля. Для сравнения выберем сначала разрешающий элемент в третьем столбце, а затем – во втором. Итак, пусть разрешающим элементом будет  a₄₃ = - 4.  После шага метода Штифеля мы приходим к таблице  (2).

Табл. 2.

Анализируя проделанный шаг, мы приходим к выводу о том, что в столбце свободных членов появилось лишнее отрицательное число 
b₃¢ = – 1,5. Таблица по-прежнему содержит два отрицательных свободных члена, и мы остаемся так же, далеки от области планов задачи, как и до проделанного шага. Используя  схему пересчета элементов таблицы

                               (4)

мы приходим к выводу о том, что число  b₃¢  получилось отрицательным из-за положительности элемента  a₃₃,  расположенного на пересечении выбранного  3-го столбца таблицы  (1)  и  3-ей  строки, содержащей нулевой свободный член. Действительно:

                           (5)

Выражение    как симплексное отношение. Следовательно, знак свободного члена  b₃¢  противоположен знаку элемента  a₃₃.  Если взять разрешающий элемент во втором столбце, то подобной неприятности не произойдет.  В этом случае на пересечении выбранного  2-го столбца таблицы  (1)  и  3-ей  строки, содержащей нулевой свободный член будет отрицательное число  a₃₂ = – 1. Пусть разрешающим элементом в исходной таблице  (1)  будет число  a₂₂ = – 1. Тогда после шага метода Штифеля, мы получим таблицу  (3):

Табл. 3.

В данном случае нам сразу удалось получить опорный план задачи, правда этот план является вырожденным. Аналогичная ситуация возникла бы при выборе в качестве разрешающего элемента числа  a₄₂ = – 2.  Данное обстоятельство объясняется тем, что симплексные отношения для элементов  a₂₂  и  a₄₂  одинаковы. Переходим ко второму этапу решения задачи – к поиску оптимального плана. Наличие отрицательной оценки у свободной переменной  x₁  (см. табл. 3) говорит о том, что соответствующий опорный план не является оптимальным. Разрешающий элемент необходимо выбрать в первом столбце.

Если выбрать разрешающий элемент  a₁₁¢ = 1  по принципу минимального симплексного отношения, то мы придем к таблице  (4):

Табл. 4.

Мы не только не улучшили функцию цели, но даже вышли из области планов задачи. Свободный член в четвертой строке стал отрицательным по той же причине, что и раньше (см. формулу 5).  А именно из-за того, что элемент  a₄₁¢ = 5,  стоящий на пересечении разрешающего столбца и строки, содержащей нулевой свободный член, положителен.  Но другого столбца, который можно было бы сделать разрешающим, у нас нет. В такой ситуации в качестве разрешающего элемента в первом столбце, вопреки принципу минимального симплексного отношения, необходимо выбрать число  a₄₁¢.

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

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

Итак, выберем в качестве разрешающего элемента в таблице  (3) число a₄₁¢ = 5. После пересчета мы приходим к таблице (5):

Табл. 5.

Так как оценки всех свободных переменных неотрицательны, то, следовательно, мы получили оптимальный опорный план задачи  (3):

Заметим, что данный набор переменных  (0; 3; 0; 1; 0; 3; 0) мы нашли еще раньше (см. таблицу 3). Однако тогда мы не могли сделать вывод о его оптимальности. Для этого свободной переменной  x₁  пришлось стать базисной.

Основные правила решения задачи в случае вырождения:

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

На примере мы показали, что данными правилами необходимо пользоваться как на этапе поиска первоначального опорного плана, так и на этапе нахождения оптимального опорного плана.

Литература:

1. Уксусов С.Н  «Метод Штифеля и его применение в линейной алгебре и математическом программировании » 2003.