Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 33
Текст из файла (страница 33)
7. Нижняя строка симплекс-таблицы 7, содержащая величины Л, > О, Х,(зз) = О, характеризующие решение зз задачи (3), опущена — это обстоятельство не повлияет на дальнейшие преобразования табл. 7. Рассмотрим возможные здесь случаи. Случай 1.
В табл. 7 отсутствуют строки, соответствующие вспомогательным переменным и"+', ..., и"+", т. е. г= и( п и столбцы А„ ..., А, составляют базис точки зз = (и„ О). Тогда согласно правилу составления симплекс-таблиц 1-й строке табл. 7 З 11 ВЫБОР НАЧАЛЬНОЙ УГЛОВОЙ ТОЧКИ таз будет соответствовать уравнение г+1 и и+1 «+т .3 и + 7;,,+1и + ... + 7Зпи + 7;,п+1и + ... +76~+~и =и1, (6) Таблица 7 и з + и Свобоввые влепи „и+гп-г+1 и11 > О ',>О 71,и+т-г+1 71,и+т 7ьа+ег — г-~-1 7г,и+ге — г+1 тг,а+ге и'>О оп+1 = О 1 7п+1,и+ -г+1 7и+1,п+т 7 и+1,и+ т — г+ 1 7п+1,и+ге ии+г = О "1 „а+ге 1 7и+т — г,и ~-т — г+1 1 1,..иг т. Пользуясь этим уравнением, исключим вспомогательные переменные й+1, ..., и"+" из дальнейших рассмотрений.
Для етого заметим, что система (6) является другой равносильной формой записи системы (4) — система (6) может быть получена из Ап+ цг = Ь умножением слева на матрицу В-', обратную матрице В =(А„.. и А,). Поэтому, положив в уравнении (6) и +' ...= й+ О, придем к системе иг + 7пг+1иг+~,+ ... + 7ягй = и(, 1= 11 ...,г = т (7) которая также может быть получена из Аи = Ь умножением слева на В ' и позтому равносильна системе Ап Ь.
Это значит, что угловая точка и, имеет своим базисом столбцы А„... ..., А, (г = ганя А = т), а система Ап Ь уже записана в виде (7), удобном для применения симплекс-метода. Резюмируя, можно сказать, что если в табл. 7 отсутствуют строки, соответствующие вспомогательным переменным, то для получения симплекс-таблицы угловой точки и, нужно вычеркнуть из табл. 7 все столбцы для й+', ..., й+" и добавить нижнюю 3' СТРОКУ ИЗ 111 = ... = Ог = 0» П1 = .~~ Сеуг1 С11 1 = Г+ 11 г ° ° е 1 „„я,.7(и ), 140 элементы линеинОГО пРОГРАммиРОВАния ~ГЛ.
3 С л у ч а й П. В табл. 7 имеются строки, соответствующие вспомогательным переменным, т, е. Т(/и, и среди коэффициентов 7+ д (р=1, ..., /и — г, 7-г+1, ..., П) имеются положительные. Пусть, например, 7„+/л>0 (1(1</и — г, г+1~ < Й < п). Тогда 1а = (!: 1 ~ ~1 ~ ~Г ИЛИ П + 1 ~~ 1 < П + ТИ вЂ” Т, 7у, > 0) Ф Ы. Поскольку Р(/7/и) О для всех 7 ен Х„, а Р,"+~/у„+; „=О, то /' / в-14 / шш Р,/ум = Р, /у„т/ А = О. зя/„ Это значит, что любой коэффициент 7зми > 0 (1 (1~ /и — г, г+1 ( я ( и) можно взять за разрешающий элемент симплекс- таблицы 7 и с его помощью вывести вспомогательную переменную й+' из базисных и вместо нее ввести в базисные основную переменную и".
Из формул преобразования, аналогичных формулам (3.17), (3.24), (3.25), нетрудно увидеть, что из-за и~+ = =0 в результате такого преобразования симплекс-таблицы мы останемся в той же угловой точке ге, но ее базис А„..., А„ ео ..., е„, ааменится новым базисом А„..., А„е„..., е, „ е;+„..., е „А,.
Коли и в новой симплекс-таблице, соответствующей новому базису точки г„, на пересечении столбцов и'+', ..., й ', и'+', ..., й со строками, отвечающими вспомогательным переменным, еще останутся положительные коэффициенты, то, взяв любой из них за раарешающий элемент, можно вывести из базиса еще один из вспомогательных столбцов е„..., е, О е/+О ..., е, и заменить его столбцом исходной матрицы А и т.
д. Может оказаться, что за конечное число таких операций нам удастся вывести иа базиса точки зэ все вспомогательные столбцы е„..., е„, — это будет оаначать, что после упомянутых операций мы пришли к симплекс-таблице, соответствующей рассмотренному выше первому случаю при /и = гапяА. Может, однако, получиться и так (при гапяА (/и так это и будет), что в очередной симплекс-таблице на пересечении столбцов основных переменных, не являющихся базисными для точки зе, со строками, соответствующими вспомогательным базисным переменным, не найдется ни одного положительного коэффициента, к тогда описанный процесс вывода столбцов (е,) из базиса оборвется.
Это будет означать, что реалиаовался случай П1, к рассмотрению которого мы сейчас переходим. Случай П1. В табл. 7 имеются строки, соответствующие вспомогательным переменным, т. е. г < и, но 7„+„,/ ~ 0 при всех р = 1, ..., /и — г, у — г+1, ..., и. Согласно правилу составления симплекс-таблиц строке переменной и' (/ 1, ..., г) ВЫБОР нАчАльнОЙ уГлОВОЙ точки в табл. 7 соответствует уравнение 1 + ~+1 () «+ +, и«+м-«+1 ...
+ у;,«+,„й+ =Р»„7'=1,...,г, (8) а строке переменной и"+' — уравнение »+1 ««+» «+м-»+1 у„».1,„».1и + ... + у„т»„и + и + у«».1«.»„» „»,1и + В »»+»««+1 ...+у+;,„+ и =Р1 =О, 1=1,...,т — г. (9) Заметим, что система (8), (9) может быть получена из Аи+ и» = Ь умножением слева на матрицу, обратную матрице (Ао ..., А, е„..., е„,), где А„..., А„е„..., е,— базис точки г«, поэтому системы (4) и (8), (9) равносильны, С другой стороны, напоминаем, что при и"+' =... = и"+" = 0 система (4) превращается в систему Аи = Ь. Поэтому, полагая в (8), (9) и"+' —... = и"'"' = О, получаем систему и + у,. „+ и + ...
+ у»ии + ... + у;„и («т»,г+»и + + 1«+»,»и + + 1«+»,«и О~ (И) которая также равносильна системе Аи = Ь. Заметим, что в рассматриваемом случае в (И) все 7„+»л~ 0 () г+1, ..., и, 1=1, ..., т — г). Возможно, что в некотором из уравнений (11), например, в и+1-м уравнении 7„+»1 0 при всех 1 = г + 1, ..., п. Ясно, что такие уравнения будут тривиально удовлетворяться при всех и »и Е" и их можно без ущерба вычеркнуть из системы (10), (И). Поэтому можем считать, что в каждом из уравнений (И) имеется хотя бы один отрицательный коэффициент.
ПУсть в и+ 1-м УРавнении (И) У +с. (О, ..., 7„+»,,э<0, а остальные коэффициенты равны нулю. Тогда это уравнение запишется в виде » ° т у„+»л и'+ ... + 7«+»* и = О. Поскольку й')0 для всех иеньГ, а у +;,,(О (1 1, ..., Д), '1 то последнее уравнение будет удовлетворяться только при и = О,..., и ч = О.
Координату и" (г+ 1 ~ й < п) назовем отмеченной, если у.+»л (0 хотя бы для одного номера 1 (1 ~1< т — г). Таким образом, показано, что у системы (10), (И) и, следовательно, у равносильной ей исходной системы Аи Ь возможны лишь такие неотрицательные решения, у которых отмеченные координаты равны нулю. Поскольку отмеченные координаты уже од- 142 элементы линеинОГО пРОГРАммиРОВАния [ГЛ.
З Г ~ с;и + ~~'., с;и (12) при ограничениях и' > О, ..., и' ~ О; и' > О, 1 ш 1, и + .с., угли'= Р'„/= 1,...,г, АМУ (13) (14) где 1 — множество номеров тех из координат и'+', ..., и", которые не являются отмеченными. Задача (12) — (14) уже приведена к виду, удобному для использования симплекс-метода: исходная угловая точка (и'„..., РМ Р*, = 0 (1 си 1)) известна, г— ранг матрицы ограничений (14), базисные переменные и',...,и' легко выражаются из (14) через небазисные. Решая задачу (12) — (14) симплекс-методом, можно найти ее решение и'„..., и"„и,' (1вн 1).
Добавив сюда нулевые значения отмеченных координат, получим решение исходной задачи (1). Рассмотрение всех трех возможных случаев закончено. Заметим лишь, что хотя каждый из этих случаев формально охватывает возможность г = и ( Гп, следует ее выделить особо. Из симплекс-таблицы 7 при г=п, полагая и"+'=...=и"+" О, 1 ГГ ГГ ПОЛУЧаЕМ И' = ип..., И = РЫ ЭТО ЗиаЧИт, ЧтО ПРИ Г = П МНОжвство У состоит из одной точки и = и, и задача (1) становится малосодержательной.
Из приведенного анализа вытекает следующее полезное правило заполнения симплекс-таблиц задачи (3): если в процессе применения симплекс-метода к этой задаче какая-либо вспомогательная переменная и"ГГ перешла в небазисные, то в дальнейшем из столбца и"+Г разрешающий элемент брать не следует; более того, поскольку в дальнейшем все равно будет принято и"+'= О, то ясно, что столбец для и"+' не окажет никакого влияния на окончательную таблицу с основными переменными и поэтому его можно сразу же вычеркнуть из симплекс-таблицы. Кстати, в табл.
7 столбцы для вспомогательных переменных и"+"-"+', ..., и"+" приведены лишь для пояснения дальнейших нозначно определены (они равны нулю), то их можно исключить из дальнейшего рассмотрения. Для этого в (10), (11), а также в (1) нужно вычеркнуть все коэффициенты сь ас, 7,„ которые умножаются на отмеченные координаты.
Кстати, после исключения отмеченных координат все уравнения (11) в рассматриваемом случае превратятся в тривиальные тождества, и их также следует вычеркнуть. В результате вместо исходной задачи (1) получим новую каноническую задачу линейного программирования: минимизировать функцию Вывог ИАчАльнои уГлОВОЙ точки на множестве 5', определяемом условиями й>0, ..., и'>О; й+ и' — 4й+ й — Зй = 3 й — 4й+ 2й — 5й 6, — 2й — 5и'+8й+ и' =3.
(16) (17) Для определения начальной угловой точки множества 0 введем вспомогательные переменные и', и', и' и в пространстве Е' переменных з=(и', ..., и') рассмотрим задачу: минимизировать функцию У (з) пе + и1 + й (18) на множестве Я, определяемом условиями йР-О, ..., и'3-0; й + и' — 4и' + и' — Зи' + и' 3, и' — 4и'+ 2и' — 5й+ й 6, — 2й — 5и'+ 8й+ и' + и'= 3.
(19) (20) Заполним симплекс-таблицу 8 для угловой точки з, (О, О, О, О, О, 3, 6, 3) множества Я; в этой таблице столбцы, соответствующие базисным переменным и', й, й, опущены; в нижней строке выписаны коэффициенты функции (18) после замены базисных переменных й, и', й через небазисные согласно равенствам (20) — эти коэффициенты, очевидно, получаются суммированием величин в соответствующих столбцах не- базисных переменных й, ..., и' точки з,. В табл. 8 в качестве разрешающего элемента возьмем величину 2 из столбца й и совершим симплекс-преобразование (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
