Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 38
Текст из файла (страница 38)
Систему Су = и + Ах = Ь перепйшем в покоординатной форме: Ь'= и' +апх' +...+а,,х' +...+а,„х", 7! = 1„А, = А„ ..., у„ = 1 А„ = А„. Элементы строки !з,легко вычисляются по формулам (3.30), которые прйменительно к задаче (4) дадут: величины Ь'„..., ~Х, соответствующие базисным переменным и',..., и" равны нулю, а велич™ины !!«а, «2 „..., с«.
равны сумме элементов соответствующих а а столбцов Ъ', х',..., х": !!« = 2„6! = д(ха), !1т = 2 , 'ае. Привлекательно так- «1 же и то, что симплекс-таблица 19 лексикографически положительна и поэтому здесь удобно применять симплекс-метод с антициклином (3.48). Таблица !9 Поскольку д(у) > 0 при всех у Е 1', то д = !п1д(у) > 0 и 'случай д— = -оо здесь невозможен.
Поэтому, взяв в качестве начальной точку га, с помощью симплекс-метода с антициклином за конечное число шагов найдем угловую точку х, = (и„и„) множества 1', являющуюся решением задачи (2): д(х,) = д„> О. Имеются две возможности: или д(х,) > 0 или д(х„) = О. Если д(х„) =и,'+...+и„>0, то и,фО и, оказывается, множество Х в (1) будет пустым. В самом деле, если бы существовала хотя бы одна точка х е Х, то точка у = (О, х ) принадлежала бы множеству 1' и, кроме того, тогда д(у ) = = О, что противоречит неравенствам д(ц,) > д(х,) = д, > О. Таким образом, при д(х„) = д„) 0 множество Х пусто, и задача (1) не имеет смысла.
Пусть теперь д(х,) = и,'+... + и, =О. Тогда и„=О и х, =(О, и,). Кроме того, по построению х, = (О, е„) угловая точка множества Х.'Покажем, что тогда и„— угловая точка множества Х. Прежде всего ясно, что из х„> 0 следует и„> О, а из Сх„= Ь имеем Ае, = Ь. Это значит, что и. Е Х. Далее, рассмотрйм представление о„=ах«+(1 — о)хз, 0< са <1; х„хаЕХ, (4) и покажем, что оно возможно лишь при и, = х, = х. Точки у, = (О, х,), у, =(О, х,), очевидно, принадлежат У.
Тогда (4) можно переписать в виде х, = ау,+(1 — «х)у„О< о <1. Но и„— угловая точка множества г'. Поэтому последнее равенство для г„возможно лишь при г„= у, = уа. Отсюда следует, что и, = х, = х,. Таким образом, и„— угловая точка множества Х, Тем самым доказана важная Т е о р е м а 1. Если множество Х = Тх Е Е™: х > О, Ах = 6) непусто, то оно имеет хотя бы одну угловую точку.
, Таким образом, с помощью изложенного метода искусственного базиса, составной частью которого является симплекс-метод с антициклином, мы получили возможность узнать, пусто множество Х задачи (1) или непусто, а в случае непустого Х определили одну из его угловых точек и,. Найденная точка е, вполне может быть использована как начальная угловая точка для 4 4. ПОИСК НАЧАЛЬНОЙ УГЛОВОЙ ТОЧКИ 135 134 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ организации симплекс-процесса для исходной канонической задачи (1).
Зная координаты точки о„с помощью теоремы 2.1 можно определить но- мера базисных переменных и ранг матрицы А. В самом деле, положи- тельные координаты (о.'Ч..., оь) точки о, заведомо являются базисными (см, доказательство теоремы 2,1). Остается добавить к линейно независи- мым столбцам А,,, Аз матрицы А другие ее столбцы и получить ба- зис (А.... А. )=В линейной оболочки векторов, натянутых на столбцы А„..., А„матрицы А. Номера у'„,.'., ~'„будут базисными для точки о. и г=гапдА. Далее, с помощью процесса Гаусса — )Кордана можем выразйть базисные переменные через небазисные и, попутно исключая линейно зави- симые уравнения из системы Ах=6, придем к приведенной системе угловой точки о, с базисом В.
Остается применить симплекс-метод с антициклином и получить решение задачи (1) или узнать, что эта задача не имеет решения, 2. Таким образом, доказана принципиальная возможность использования симплекс-метода, оснащенного антициклином, для решения произвольной канонической задачи. Более того, с помощью симплекс-метода мы доказали важную для теории и методов линейного программирования теорему 1. При- ведем еще две теоремы, касающиеся канонической задачи, в доказательстве которых симплекс-метод также играет существенную роль.
Теорема 2. Если задача (1) разрешима, то среди ее решений найдется хотя бы одна угловая точка множества Х. Доказательство. По условию теоремы Х фо и существует точка Р„Е Х такая, что (с, е„) = ?'„> -оо. По теореме 1 тогда множество Х имеет хотя бы одну угловую точку. Отправляясь от одной из этих угловых точек, с помощью симплекс-метода с антициклином за конечное число шагов при- дем к угловой точке х„ являющейся решением задачи (!)-(3).
Теорема 2 доказана. П Т е о р е м а 3. Для того, чтобы каноническая задача (1) была раз- решима, т. е. еуицестеоеала точка х, Е Х такая, что (с, х„) = 1п((С х) = = Л„) — оо, необходимо и достаточно, чтобы: 1) множество Х было непустым; 2) функция 7(х) = (с, х) была ограничена снизу на Х, Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь очевидна., Докажем достаточность. Из того, что Х фЯ, по теореме 1 следует суще- ствование угловой точки множества Х, Принимая эту точку за начальную, будем решать задачу (1) с помощью симплекс'-метода, снабженного анти- циклином.
Так как по условию 7", > — оо, то случай (3.33) здесь невозмо- жен, и симплекс-процесс завершится за конечное число шагов реализацией случая (3.32) и отысканием точки х„ являющейся решением задачи (1). Теорема 3 доказана. П Применение симплекс-метода для доказательства других важных теорем теории линейного программирования изложим в следующем параграфе.
3. На этом заканчиваем изложение симплекс-метода для канонической задачи (1). Учитывая возможность сведения общей задачи линейного про- граммирования к канонической задаче (теорема 1.1), можно сказать, что симплекс-метод является универсальным методом решения задач линейно- го программирования. Конечно, компьютерная реализация описанной вы- ше схемы симплекс-метода требует огромной дополнительной работы: надо выбрать подходящую модификацию метода, изучить влияние погрешности на симплекс-процесс, организовать хранение исходной и текущей информации о задаче и т. п. — эти практические проблемы обсуждаются, например, в [116; 516; 586; 620]. Симплекс-метод относится к так называемым конечным методам, позволяющим найти решение задачи линейного программирования или обнаружить ее нерешаемость за конечное число арифметических действий.
Это число, конечно, зависит от размерностей гп, п задачи (1). Известен пример задачи линейного программирования с п переменными и «и = 2п ограничениями (этот пример приведен в [586], стр. 360), для решения которого требуется не менее 2" — 1 шагов симплекс-метода, и, следовательно, число арифметических операций, необходимых для получения решения, не меньше 2 . Отсюда следует, что количество вычислений для решения «плохих» задач линейного программирования симплекс-методом оценивается экспоненциальной функцией параметров т,п размерности задачи, и уже при не очень больших т,п решение таких задач симплекс-методом невозможно за обозримое время даже на самых мощных компьютерах.
Как принято говорить, на классе задач линейного программирования симплекс-метод имеет энспоненциальную сложность. Однако вопреки такому пессимистическому выводу в практических задачах симплекс-метод показывает высокую эффективность, причем в абсолютном большинстве реальных задач количество необходимых арифметических операций имеет порядок п'и» [52].
Причина этого удивительного явления пока еще не выяснена. В последнее время появились методы, имеющие полиномиальную сложность. Так называются конечные методы, для которых число элементарных операций, необходимых для получения решения задачи линейного программирования с нужной точностью, не превышает некоторого полинома от размерностей гп, и задачи— более точные формулировки см.
в [525; 676;?36], Эти методы в самом деле эффективнее симплекс-метода на «плохих» искусственно придуманных задачах линейного программирования, но на реальных задачах пока не могут успешно конкурировать с ним. На практике симплекс-метод по-прежнему остается основным методом линейного программировании. Кроме симплекс-метода имеется множество других (конечных, итерационных) методов решения задач линейного программирования [52; 76; 77; 116; 203; 259; 586; 620; 685; 719; 775; 776].
Для специальных классов задач линейного программирования таких, как, например, транспортная задача, существуют методы, лучше учитывающие конкретные особенности этих задач [52; 203; 232; 259; 4?1; 493; 620; 685; 725; 743]. Содержательный обзор многих существующих методов линейного программирования дан в [586].
В заключении подчеркнем, что всюду выше предполагалось, что исходные данные задачи линейного программирования — матрица А, векторы 6, с— известны точно и, кроме того, все промежуточные вычисления в симплекс- методе проводятся без погрешностей. Такая идеализация позволила нам дать строгое обоснование симплекс-метода, доказать ряд важных теорем линейного программирования. Однако на практике исходные данные задаются, как правило, неточно, промежуточные вычисления проводятся с округлениями.
Поэтому применение симплекс-метода или других методов в конкретных задачах линейного программирования может привести к большим погрешностям, неверным выводам из-за возможной неустойчивости решения по отношению к возмущениям исходных данных таких задач, и для получения их решения с нужной точностью могут понадобиться специальные методы регуляризации, которые будут рассмотрены в главе 9. 136 !37 Упражнения (2) (3) г, =шахТО; — х ), х,= х, — г„х! =птах(0; х,), е = Ь, — Апх, ' — Аих д б' и '„ Гл. 3.
ЭЛЕМЕНТЪ| ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1. С помощью метода искусственного базиса найдите какую-нибудь угловую точку следую- щих множеств: а) х=(х1,. 4)>0, в!4 хз+ 3 — 4 х! 3 х4 ! 2 4 б) х=(х1,, 'х4)>0 х!+хз+2хз 4 ! х! хз+ З+ 4 2 х!+3*2 Зхз-3 4=0; в) х=(х',..., х4) >О, х'+хз+хз+хб= ! х!42х2-2хзбх4=0, 2х1+зх2-хз+2х4=2 г) х = (х1,..., хб) > О, х1+ 2хз+ 2хэ — х4+ хз '= |, 2х| — хз + хв 4. хб 4.
2хб = 2, ' бхз+ .!. Зхз — Зх4 = О, хг — Зхз — хз + 2хб + хз = !' д~ х= (х1,..., х ) >О, в! +2хз-1-хз+х4-1-2хб= 5, х!' — зхз — 2х! — хб = 2, 2х1.1-яз-- в х +х +х =|; 4 5 ) (.1 6)>0 11 2! 31 4! б!хб 2 1122! 3!24 5! б 3 х! -1-хз-1-Зх]+х4 |-х5 хб 2, х1+2хз-1-хЗ+4х — х 4 5 6 2. С помощью симплекс. метода решите следующие канонические задачи: а) 1(х)=х'-хз — хз-х4+2хб-+!и![зцр], х=(х',..., хз)>0, х|+Зхз+хз+х4 — 2хб=|0, 2х +6хз+ хз+Зхб — 4х =20, Зх + |Охз+ ха+ бх4 — 7х6= 30; б~ 1(х) =х'+2хз+хз+2х4+хб-~|п![бпр], х=(х',... хб) >О, х' — хз+2хз4-хб-Зхб— 1 2 3 4 5 6 — х =3, в! +хз+2хб хб+2хз 2 2х!+хз+хз х +2хб+хб 3.
в) 1(х! — х! 1. 2хз 2хз.!.5х4 ~ щ|[зцр1 х (х| х4) > 0 х! .! 2хз — хз — х4 -х'+2х +Зхз+х4=2 х'+5хз+хз — х =5; г) 1~х)=х!+2хз+Зх +4х4+бхб- |в|[бар], х=(х',..., хб) >О, х! 4-хз — 2х4-бхб = 2, х24-х -2х4+ух'=2 '+хз-2х4+7х6=2 д) 1(х)=я|+ха+х +хт — ~ |и|[бар], х= (х|,..., хт))0, х|+Зх +хз+2ха+х +х = |О, 2х +хз — хз+бх4-1-Зхб хт= 20 х!+ |Зх2+ 7хз ! 5х5 хб 1 2хт |О 3. С помощью приемов, описанных в $ 1, запишите задачу линейного программирования в каноническом виде и решите ее с помощью симплекс-метода: а) 1(х)=2хг-ьхз-хз+хз — ~ |пцзцр], х=(х',..., хб)>0, 0<в!-х4<2, х'+хз+хз-х4-хб>|; б) 1(х) =Зх'+ !Охз+8хз — бх4 — ~ |и|[бар], х=(х',..., х4) ) О, Зх'+2х2+ ха — х4 ) -|, я!+зхз+3 З 2х4 ! х! <4, в) 1(х)=х 43х — х — ~|п([зцр], х |>мО, х >О, -! < х — х +х > |, х|+хз+хз <4; г) 1(х)=6х'-|2хз+5хз+2х +Зяб-~|п!]бар~, х=(х',..., хб))0, Зх' — бхз+бх344х4 <3, х — 2х +4х +х =2, -х +2х — Зх — 2х — х >-7; 1 2 4 5 1 2 3 5 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
