 |
Случай вырожденных базисных решений
|
|
|
|
Напомним, что базисным решением системы линейных уравнений
y 1 = b 1+ a 11(– x 1) + a 12(– x 2) +…+ a 1 j (– xj) +…+ a 1 n (– xn),
…………………………………………………………...….
yi = bi + ai 1(– x 1) + ai 2(– x 2) +…+ aij (– xj) +…+ ain (– xn), (3.9)
………………………………………………………………
ym = bm + am 1(– x 1) + am 2(– x 2) +…+ amj (– xj) +…+ amn (– xn).
называется такое решение, которое получается, если все свободные переменные x 1,…, xn положить равными нулю. После шага метода жордановых исключений одна из свободных переменных превращается в базисную переменную и наоборот. Таким образом, система может иметь достаточно много базисных решений (максимальное количество базисных решений совпадает с числом сочетаний 
). Базисное решение системы (3.9) называется вырожденным, если одна или несколько базисных переменных оказываются равными нулю. Например, первоначальное базисное решение
(0,…, 0,…, 0, b 1,…, bi,…, bm) системы (3.9) является вырожденным, если один или несколько свободных членов b 1,…, bi,…, bm окажутся равными нулю.
При решении основной задачи линейного программирования мы можем столкнуться с вырожденными базисными решениями, как на этапе поиска первоначального опорного плана, так и при нахождении оптимального опорного плана. При этом выбор разрешающего элемента по принципу минимального симплексного отношения иногда приводит к появлению лишних отрицательных свободных членов. А это выводит нас из области планов задачи или удаляет от нее. Дело в том, что даже при соблюдении принципа минимального симплексного отношения ноль в столбце свободных членов может замениться не только положительным, но и отрицательным числом. Рассмотрим следующий пример:
Пример 3.8. Найти максимум функции
|
|
|
z(X) = 3 x 1 – x 2 – 5 x 3 (3.10)
при условии того, что переменные удовлетворяют следующей системе:
3 x 1 – 2 x 2 – 3 x 3 +7 ³ 0,
– 2 x 1 + x 2 – 2 x 3 – 3 ³ 0,
– 3 x 1 + x 2 – x 3 ³ 0, (3.11)
– 9 x 1 + 2 x 2 + 4 x 3 – 6 ³ 0,
x 1, x 2, x 3 ³ 0.
Решение. Нашей задаче соответствует следующая жорданова таблица:
| – x 1 | – x 2 | – x 3 | ti 2 | ti 3 | ||
| y 1 | –3 | 3,5 | 7/3 | |||
| y 2 | –1 | –3 | – | |||
| y 3 | –1 | |||||
| y 4 | –2 | –4 | –6 | |||
| z | –3 | – | – |
Табл. 3.19.
Как всегда, каждый шаг метода Штифеля мы постараемся осуществлять с соблюдением принципа минимального симплексного отношения. Так как в столбце свободных членов есть отрицательные числа b 2 = – 3 и b 4 = – 6, то соответствующее таблице 3.19 базисное решение не является опорным планом задачи. Причем данное базисное решение является вырожденным, т.к. одна из базисных переменных оказалась равной нулю
(b 3 = 0). Найдем отрицательные элементы, соответственно во второй и в четвертой стоке. Такими элементами являются числа a 22 = – 1, a 42 = – 2 и a 43 = – 4.
Вычислим минимальные симплексные отношения для второго и третьего столбца таблицы (именно в эти столбцы попадают найденные отрицательные числа). В данном случае нам повезло, и минимальные симплексные отношения достигаются как раз на отрицательных элементах. Некоторые отношения равны нулю, но симплексными отношениями, согласно нашему определению, они не являются. Во втором столбце в качестве разрешающего элемента можно выбрать или a 22 = – 1, или a 42 = – 2, т.к. симплексные отношения для них минимальны и одинаковы. В третьем столбце в качестве разрешающего элемента может быть только число
a 43 = – 4.
Несмотря на похожесть ситуаций во втором и четвертом столбце, между ними есть одна очень существенная разница. В третьей строке таблицы 3.19, содержащей нулевой свободный член, элемент второго столбца отрицателен, а третьего – положителен. Данное обстоятельство влияет на знак свободного члена, получающегося в третьей строке после одного шага метода Штифеля. Для сравнения выберем сначала разрешающий элемент в третьем столбце, а затем – во втором. Итак, пусть разрешающим элементом будет a 43 = - 4. После шага метода Штифеля мы приходим к таблице 3.20.
|
|
|
| – x 1 | – x 2 | – y 4 | ||
| y 1 | 3,75 | 0,5 | 0,75 | 2,5 |
| y 2 | 6,5 | –2 | 0,5 | –6 |
| y 3 | 5,25 | –1,5 | 0,25 | –1,5 |
| x 3 | –2,25 | 0,5 | –0,25 | 1,5 |
| z | 8,25 | –1,5 | 1,25 | –7,5 |
Табл. 3.20.
Анализируя проделанный шаг, мы приходим к выводу о том, что в столбце свободных членов появилось лишнее отрицательное число
b 3¢ = – 1,5. Таблица по-прежнему содержит два отрицательных свободных члена, и мы остаемся так же далеки от области планов задачи, как и до проделанного шага. Вспоминая схему пересчета элементов таблицы (1.12), мы приходим к выводу о том, что число b 3¢ получилось отрицательным из-за положительности элемента a 33, расположенного на пересечении выбранного 3-го столбца таблицы 3.19 и 3-ей строки, содержащей нулевой свободный член. Действительно:
(3.12)
Выражение 
как симплексное отношение. Следовательно, знак свободного члена b 3¢ противоположен знаку элемента a 33. Если взять разрешающий элемент во втором столбце, то подобной неприятности не произойдет. В этом случае на пересечении выбранного 2-го столбца таблицы 3.19 и 3-ей строки, содержащей нулевой свободный член будет отрицательное число a 32 = – 1. Пусть разрешающим элементом в исходной таблице 3.19 будет число a 22 = – 1. Тогда после шага метода Штифеля, мы получим таблицу 3.21:
| – x 1 | – y 2 | – x 3 | ti 1 | ||
| y 1 | |||||
| x 2 | –2 | –1 | –2 | – | |
| y 3 | –1 | –1 | – | ||
| y 4 | –2 | –8 | |||
| z | –1 | –3 | – |
Табл. 3.21.
В данном случае нам сразу удалось получить опорный план задачи, правда этот план является вырожденным. Аналогичная ситуация возникла бы при выборе в качестве разрешающего элемента числа a 42 = – 2. Данное обстоятельство объясняется тем, что симплексные отношения для элементов a 22 и a 42 одинаковы. Переходим ко второму этапу решения задачи – к поиску оптимального плана. Наличие отрицательной оценки у свободной переменной x 1 (см. табл. 3.21) говорит о том, что соответствующий опорный план не является оптимальным. Разрешающий элемент необходимо выбрать в первом столбце.
|
|
|
Если выбрать разрешающий элемент a 11¢ = 1 по принципу минимального симплексного отношения, то мы придем к таблице 3.22:
| – y 1 | – x 2 | – x 3 | ||
| x 1 | ||||
| y 2 | ||||
| y 3 | –1 | –3 | –8 | |
| y 4 | –5 | –12 | –43 | –5 |
| z | –2 |
Табл. 3.22.
Мы не только не улучшили функцию цели, но даже вышли из области планов задачи. Свободный член в четвертой строке стал отрицательным по той же причине, что и раньше (см. формулу 3.12). А именно из-за того, что элемент a 41¢ = 5, стоящий на пересечении разрешающего столбца и строки, содержащей нулевой свободный член, положителен. Но другого столбца, который можно было бы сделать разрешающим, у нас нет. В такой ситуации в качестве разрешающего элемента в первом столбце, вопреки принципу минимального симплексного отношения, необходимо выбрать число a 41¢.
При выборе разрешающего элемента в строке, содержащей нулевой свободный член, после одного шага метода Штифеля столбец свободных членов не изменится (включая значение функции цели). Докажите данное утверждение самостоятельно. Таким образом, нам не удалось улучшить (в плане увеличения функции цели) опорный план.
Однако при таком пересчете, изменяются знаки всех элементов (за исключением разрешающего элемента) разрешающего столбца, включая знак оценки соответствующей свободной переменной. Мы получаем новые наборы свободных и базисных переменных. Все это дает нам уверенность в том, что если не произойдет "зацикливания", то через конечное число шагов нам удастся приступить к выбору разрешающего элемента по принципу минимального симплексного отношения. При этом мы приблизимся к оптимальному плану задачи.
Итак, выберем в качестве разрешающего элемента в таблице 3.21 число a 41¢ = 5. После пересчета мы приходим к таблице 3.23:
| – y 4 | – y 2 | – x 3 | ||
| y 1 | –0,2 | 2,4 | 8,6 | |
| x 2 | 0,4 | –1,8 | –5,2 | |
| y 3 | –0,2 | –0,6 | 0,6 | |
| x 1 | 0,2 | –0,4 | –1,6 | |
| z | 0,2 | 0,6 | 5,4 | –3 |
Табл. 3.23.
|
|
|
Так как оценки всех свободных переменных неотрицательны, то, следовательно, мы получили оптимальный опорный план задачи 3.11:
Заметим, что данный набор переменных (0; 3; 0; 1; 0; 3; 0) мы нашли еще раньше (см. таблицу 3.21). Однако тогда мы не могли сделать вывод о его оптимальности. Для этого свободной переменной x 1 пришлось стать базисной.
Сформулируем основные правила решения задачи в случае вырождения:
1. При определении разрешающего столбца предпочтение отдается тем столбцам (среди возможных), в которые попадают отрицательные элементы строк, содержащих нулевые свободные члены.
2. Если в выбранном разрешающем столбце все элементы, взятые из строк, содержащих нулевые свободные члены, отрицательны, то разрешающий элемент в данном столбце выбирают по минимальному симплексному отношению.
3. Если в выбранный разрешающий столбец попадают положительные элементы из строк, содержащих нулевые свободные члены, то разрешающий элемент в данном столбце выбирают из числа этих положительных элементов.
На примере мы показали, что данными правилами необходимо пользоваться как на этапе поиска первоначального опорного плана, так и на этапе нахождения оптимального опорного плана.
ГЛАВА IV
РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ.
двойственность в ЛИНЕЙНОм ПРОГРАММИРОВАНИи
§1 Сведение общей задачи линейного программирования к
основной задаче
Общая задача линейного программирования (3.1) – (3.2) может отличаться от стандартной (основной) задачи (3.3) – (3.4) наличием уравнений в системе ограничений и отсутствием ограничений на знак для некоторых переменных. Если в каждое из неравенств системы ограничений (3.2) ввести дополнительные переменные y 1,… yk так, как мы это делали при решении основной задачи, то систему ограничений задачи можно представить в виде системы линейных уравнений. Таким образом, мы приходим к следующей задаче:
z (X) = c 1 x 1 + c 2 x 2 +…+ cjxj +…+ cnxn ® max, (4.1)
y 1 = b 1+ a 11(– x 1) + a 12(– x 2) +…+ a 1 j (– xj) +…+ a 1 n (– xn),
………………………………………………………………………
yk = bk + ak 1(– x 1) + ak 2(– x 2) +…+ akj (– xj) +…+ akn (– xn),
0 = bk +1+ ak +1;1 (– x 1) + ak +1;2 (– x 2) +…+ ak +1; j (– xj) +…+ ak +1; n (– xn), (4.2)
………………………………………………………………………
0 = bm + am 1(– x 1) + am 2(– x 2) +…+ amj (– xj) +…+ amn (– xn),
x 1; x 2; … xr; y 1; y 2; … yk ³ 0.
Решать задачу (4.1) – (4.2) методом Штифеля мы пока не можем из-за того, что не все иксы ограничены на знак. Но исправлять ситуацию мы все равно будем с помощью метода модифицированных жордановых исключений. Для этого запишем нашу задачу в виде жордановой таблицы:
| – x 1 | – x 2 | … | – xj | … | – xn | ||
| y 1 | a 11 | a 12 | … | a 1 j | … | a 1 n | b 1 |
| … | …………………………………………………..……… | … | |||||
| yk | ak 1 | ak 2 | … | akj | … | akn | bk |
| ak+ 1;1 | ak+ 1;2 | … | ak +1; j | … | ak +1; n | bk +1 | |
| … | ………………………………………………………….. | … | |||||
| am 1 | am 2 | … | amj | … | amn | bm | |
| z | -c 1 | -c 2 | … | -cj | … | -cn |
Табл. 4.1.
|
|
|
Сводя задачу к основной задаче линейного программирования, мы попутно упрощаем таблицу 4.1. Преобразуем таблицу 4.1 следующим образом. Во-первых, переместим нули из левого заглавного столбца в верхнюю заглавную строку. При этом столбцы, в которые попадают нули, можно исключать из таблицы. Нет смысла каждый раз пересчитывать элементы данных столбцов, если они все равно будут умножаться на ноль.
Во-вторых, необходимо переместить неограниченные на знак переменные xr +1,…, xn в левый заглавный столбец таблицы. После этого строки, которым будут соответствовать переменные xr +1,…, xn, можно, предварительно запомнив, исключить из таблицы. Дело в том, что в силу неограниченности на знак мы можем не следить за знаками свободных членов, соответствующих этим строкам. Следовательно, элементы этих строк не влияют на выбор разрешающих элементов. Значения переменных
xr +1,…, xn находят после того, как будут найдены остальные координаты оптимального опорного плана.
Если это возможно, то оба перечисленных выше преобразования производят одновременно. Для этого необходимо, чтобы разрешающие элементы, находящиеся на пересечении выбранных строк и выбранных столбцов, были отличны от нуля. При этом на каждом шаге жорданова таблица уменьшается на одну строку и на один столбец. После того как все нули перенесены наверх и все неограниченные на знак переменные опущены вниз, жорданова таблица будет соответствовать некоторой основной (стандартной) задаче линейного программирования. Решив данную задачу и найдя значения запомненных переменные xr +1,…, xn, мы найдем решение исходной задачи (4.1) – (4.2).
Пример 4.1. Свести общую задачу (4.3) к основной задаче линейного программирования.
z(X) = 3 x 1 – x 2 – 5 x 3 ® max,
3 x 1 – 2 x 2 – 2 x 3 + 2 x 4 – x 5 – 2 ³ 0,
3 x 1 – 4 x 2 + 8 x 3 + 2 x 4 + 9 x 5 – 6 ³ 0, (4.3)
– 4 x 1 + 4 x 2 – 4 x 3 – x 4 – 4 x 5 + 4 = 0,
7 x 1 + 2 x 2 – x 3 + 2 x 4 + 8 x 5 = 0,
x 1, x 2, x 3 ³ 0.
Обозначая левые части первого и второго неравенств соответственно через y 1 и y 2, мы можем записать нашу задачу в виде жордановой таблицы:
| – x 1 | – x 2 | – x 3 | – x 4 | – x 5 | ||
| y 1 | –3 | –2 | –2 | |||
| y 2 | –3 | –8 | –2 | –9 | –6 | |
| –4 | ||||||
| –7 | –2 | –2 | –8 | |||
| z | –2 | –4 |
Табл. 4.2.
Выберем в качестве разрешающего элемента число a 34 = 1. Тем самым мы как бы убиваем двух зайцев. С одной стороны, мы поднимаем ноль из левого заглавного столбца наверх, а с другой стороны, мы опускаем вниз переменную x 4, не имеющую ограничения на знак. После одного шага метода модифицированных жордановых исключений мы приходим к таблице 4.3:
| – x 1 | – x 2 | – x 3 | – x 5 | |||
| y 1 | –6 | |||||
| y 2 | –4 | –1 | ||||
| x 4 | –4 | |||||
| –10 | ||||||
| z | –10 | –5 | –2 | –7 | –8 |
Табл. 4.3.
Из таблицы 4.3 можно исключить четвертый столбец, содержащий ноль наверху. А также можно исключить, предварительно запомнив, третью строку x 4 = – 4 x 1 + 4 x 2 – 4 x 3 – 4 x 5 + 4. К сожалению, мы не сможем так же успешно преобразовать таблицу 4.3, как мы это проделали с таблицей 4.2. Этому мешает ноль, стоящий на пересечении предпоследней строки и предпоследнего столбца таблицы 4.3. Поэтому переносить ноль из левого заглавного столбца таблицы наверх и опускать вниз переменную x 5 нам придется последовательно.
Выберем в качестве разрешающего элемента a 41¢= 1 и сделаем еще один шаг. Мы приходим к таблице 4.4:
| – x 2 | – x 3 | – x 5 | |||
| y 1 | –5 | –35 | –34 | ||
| y 2 | –5 | –45 | –1 | –38 | |
| x 1 | –10 | ||||
| z | –96 | –7 |
Табл. 4.4.
После данного шага мы можем исключить из жордановой таблицы только первый столбец. Все строки пока соответствуют ограниченным на знак переменным. Совершим еще один шаг метода модифицированных жордановых исключений, выбрав в качестве разрешающего элемента число (-1) из предпоследнего столбца. При этом последняя неограниченная на знак переменная x 5 опускается вниз. Мы приходим к таблице 4.5:
| – x 2 | – x 3 | – y 2 | – x 2 | – x 3 | – y 2 | |||||||
| y 1 | –440 | –376 | y 1 | –440 | –376 | |||||||
| x 5 | –46 | –1 | x 1 | –10 | ||||||||
| x 1 | –10 | z | –418 | –7 | ||||||||
| z | –418 | –7 | Табл. 4.6. |
Табл. 4.5.
Запомним и исключим из таблицы 4.5 вторую строку x 5 = 46 x 2 – 45 x 3 + y 2 +38. Мы получили таблицу 4.6, которая соответствует некоторой основной задаче линейного программирования. Что и требовалось. Читателям предлагается после изучения следующего примера 4.2 самостоятельно довести решение задачи, соответствующей таблице 4.6, до конца.
|
|
|
