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