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