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