Ф.П. Васильев - Методы оптимизации (1125241), страница 38
Текст из файла (страница 38)
5 1 2 — 3 4 — хз гхз=о, ж' — 4х2.1. 2хз-1-2х4 — 4жз = 1, 2ж' — 2жз+ из-! 4х .1-хз — 2х = 3; оо — — (1,О, 0 О, 1, 0); б) 1(х)=х1+хзч-хз+гх4+Зхзчгхз-~!п(~зпр]! ж=(х',..., х ) >О, х'+хз+4хх-ь2жз=б, в) 1(ж)=ж' +гхзчзхз+хзьхз — ~!пЦзор]! х=(х',..., х ) >О, х1-ьгх244хз-х4+ха =1, х1-хз-гхз-Ьх4+х5=1, -"+х2-бх +х4+*'=1; о,=(1,1,О, 1,О). 3. Найти начальную угловую точку ьо, ее базис, приведенную систему и решить следующие а) 1(х) =-ж'+Зхз-1-5хз+ х4 4 !и![зпр]; х=(х,...,х ) > О, х .1-4х + х -1- ж З 4 б) 1(ж)=хз — хз+хь-4!пЦзпр]! х=(ж',,х )>О, х -Ьх — ж =1, ж +х + х =3; 3 4 в~ 1(х)=4х — хз — Зхз — !Ох ч!пЦзир]! х=(ж,...,х )>О, х -1-х — х +ж =О, 4х 4 х + 1Ожз — 10х = 11, 4, С помощью приемов, описанных в $1, записать задачи линейного программирования в каноническом виде и оешить их с помощью симплекс-метода: а~ 1(ж) = -х! + 4х — 5хз -ь !п1[звр]; ж = (х1, жз, хз) > О, 2ж! -ь хз+ хз = 4 [< 4; > 4], ж'— — х — х < 2 [< 2'= 211 б) 1(ж)=ж14-хЬ+ж !пцзпр]; х=(х1, хз, хз) > О, — 1 <ж1-1-жз-Ьхз < 1, -х1.1-хзэхз <1, х — х -1-х <1; в) 1(*) =*у+ 2+ 3+ 4 ~ 1пцзпр]! х =(х1,..., хз) В О, х' — хз ВО, х1-ьхз — 3+ 4 5 > ! б.
при каких значениях параметра а задача 1(ж)= ж142хз ! зхз 54хз — ~!и! [зир]; ж=(ж',... ..., х4) > О, х'+ хз+ жз+ ах4 < 1, [> 1; = 1] имеет решение? Не имеет решення? Единственнре решение? 6. С помощью симплекс-метода с знтициклином (48) решить задачу [216): 1'(х) = — -ж + 150х — Ебх 4 бх — ~!п1; х = (х , ,ху) > О, 3 1 2 1 3 4 . 1 7 — х — бох — — х +9х + х 1 1 2 1 3 4 5 4 25 =0 — ж — 90х — 5- х + Зх + х 1 1 2 1 3 4 5 2 Бо хз =0 -1.х =1, взяв в качестве начальной угловую точку оо — — (О, О, О, О, О, 0,,1) с базисом В =,(Аз, Ав, Ау). Показать, что если разрешающий элемент оу, выбирать по правилу (34), (35) так, что Ь— наименьший иа номеров, для которых хьь — — шах 431, 3 — наименьший из номеров, удов1<1<7 летворяющих условию (35), то придем к циклическому перебору базисов точки ео по схеме: (Аз, Аз, Ау) - (А1, Аз, Ау) - (А1, Аз, Ау) - (Аз, Аз, Ау) - (Аз, А4, Ау) - (Аз, А4 Ау).
-4 (Аз, Аз, Ау) 4... 7. Пусть о — угловая точка множества Х = (х > 0: Ах = Ь) с базисом В = (А,, А ), л' где А — матрица размера ги х и, г = гапяА = ги < и. Пусть некоторая система уравнений хл+ ], м, ! „, 1(„) (у 1) (5!) ь Фг("! равносильна системе Ах = Ь, Доказать, что система (51) является приведенной системой для точки о с базисом В.
Указание; сначала покажите, что системы (51) и (28) равносильны, затем подставьте в (51) следующие решения системы (28): жо —— о; хр — — (хр~, х„) р б Ци) где жд = ол -"14, 5 = 1,, и, хя = 1, хг = 0 У 41(о), Ур р и убедитесь что рг = от, ры — — ум, Ь 41(о), 4 =1,.;,,г, 8. Пусть задача (1) имеет своим решением угловую точку о с симплекс-таблицей 3, Можно ли утверждать, что тогда А < 0 для всех у = 1, 2,..., и? (см.
табл. 3, 4). 1' 9. Для того, чтобы задача (1) имела своим решением угловую точку о, необходимо и до- статочно, чтобы для какого-либо базиса В точки о соответствующая симплекс-таблица удов- летворяла условиям (32), Доказать. 10. Пусть угловая точка о с базисом В = (А , , А,) является решением задачи (1) и Л 1 пусть ее симплекс-таблица (см, табл, 3) удовлетворяет условиям (32), Пусть при некотором Ь ((1(и) = (11,..., Д'„) ВЕЛИЧИНа ььз — -0 и в столбце х" имеется величина тз„> О. Пусть раз.
решающий элемент Т,ь определен по правилам (35) или (48), и получена угловая точка ю с координатами (36) й с базисом (37) (см. замечание 2). Доказать, что тогда ю — решение задачи (!). Можно ли таким способом получить все угловые точки множества Х, являющиеся решением задачи (1)? И. Пусть о — угловая точка множества Х =(х > 0: Ах = Ь), В =(А,..., А ) — ее завис, А — матрица размера г х и, г = гапяА < и; пусть в матрице Г = ( уо, уг,..., у„) (см. обозна- чения (27)) один из столбцов Ть < О, Ь 4 1(о) = (у,,у,). Доказать, что тогда мнохгест. во Х неограничено, и найдется такой вектор с=(с,...,с ), для которого !и! (с,х) =-оо. 1 ''' ь' ьсх Указание; взять сг =О, 4 Е1(в), с =-1, остальные сз — проиавольные числа, составить симплекс-таблицу точки р для задачи (1) с выбранным с.
Можно ли утверждать обратное; если множество Х неограничено, то в матрице Г найдется столбец уь < О, Ь б 1(о)? Ь 4. ПОИСК НАЧАЛЬНОЙ УГЛОВОЙ ТОЧКИ 133 Гл. 3, ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 132 9 4. Поиск начальной угловой точки 1. Будем рассматривать каноническую задачу 1(х)=(с,х) — ~!п1, хЕХ=(х=(х',...,х')>О, Ах= Ь), '(1) где А — матрица размера т х и, с Е Е", Ь Е Е™, в самом общем виде, отказавшись от ограничительных требований гапяА = т < и, принятых в паедыдущем параграфе.
Можем считать, что А ф О, так как при А = 0 либо .ть = Е," = (х >0) (случай Ь =0), либо Х =О (Ь ~0), и задача (1) становится малосодержательной. Нас будут интересовать вопросы, как узнать, не пусто ли множество Х, и если оно непусто, то имеет ли оно хотя бы одну угловую точку? Как найти эту угловую точку, ее базис, ее симплекс-таблицу? Ниже будут даны ответы на все эти вопросы. Здесь замечательно то, что для ответа на них может быть использован изложенный выше симплекс-метод с антициклином. Оказывается, по задаче (1) легко можно составить новую вспомогательную каноническую задачу, к которой очень удобно применять симплекс-метод, и в зависимости от того, чем закончится симплекс-процесс для вспомогательной задачи, можно будет сказать, пусто нли непусто множество Х, найти ее угловую точку.
Этот метод поиска начальной угловой точки в литературе часто называют методом искусственного базиса. Можем считать, что в (1) вектор Ь > О, так как если Ь' < 0 при некотором 1, 1 < ч' < т, то соответствующее чче уравнение (Ах)' = Ь* системы Ах = Ь можно умножить на ( — 1). Наряду с основными переменными х =(х',, х") введем вспомогательные (искусственные) переменные и = (и',..., и ) и в пространстве Е" ~ переменных д = (и, х) = (и',...
...,и , х',...,х") рассмотрим следующую каноническую задачу линейного программирования: (2) У= (у=(и, х] Е Е"+: у >О, Су= и+ Ах = Ь), где 1 =(1,..., 1) е Е, С = (1„, А), Х вЂ” единичная матрица размера т х х т. Систему Су = и + Ах = Ь перепишем в покоординатной форме: Ь'= и' +апх' +...+а„х' +...+а,„х", Ь'= и' +а,,х' +...+анхг +...+а,„х", Ь = и +а,х'+...+а зх'+...+а „х". При и' =... = и = 0 система (3) превращается в систему Ах = Ь, Множество У непусто: оно содержит, например, точку г, = (Ь,О) > О. Более того, с помощью теоремы 2.1 легко убедиться, чта точка г„является угловой точкой множества У с базисом (е„..., е ) = 1 .
Система (3) является приведенной системой этой точки, гапяС = т. Для целевой функции приведенная форма равна д(д) = (1, Ь вЂ” Ах) = д(л ) — (Ат1, х), где Ат — транспонированная матрица А. Теперь симплекс-таблица точки г составляется просто (см, табл. 19): в столбце Б — базисные координаты и' ... и, в столбце У вЂ” Т = Ь, в столбцах и',..., и" вспомогательных пе- 1 и ременных Т,' = е„..., Т' = е„, в столбцах х,..., х" основных переменных 7, =1 А, =А,,..., 7„=Х А„= А„. Элементы строки Хь легко вычисляются по формулам (3.30)„которые прйменительно к задаче (4) дадут: величины лз'„..., лх'„, соответствующие базисным переменным и',..., и" равны нулю, а величины Ьл,.л „...,.л „равны сумме элементов соответствующих столбцов У, х',, х": ь! = Х, Ь'=д(лб), да = Х; ав.
ПРивлекательно такю=1 же и то, что симплекс-таблица 19 лексикографически положительна и поэтому здесь удобно применять симплекс-метод с антициклином (3.48). Таблица !9 Поскольку д(д) > 0 при всех у Е У, то д, = !п1 д(у) > 0 и учай д, = = — аа здесь невозможен. Поэтому, взяв в качестве начальной точку г,, с помощью симплекс-метода с антициклином за конечное числа шагов найдем угловую точку г, = (и„, е,) множества 1', являющуюся решением задачи (2): д(з„) = д, > О. Имеются две возможности: или д(л,) > 0 или д(г„) = О.
Если д(л„) =и.'+...+и." >О, то е,~О и, оказывается, множество Х в(1) будет пустым. В самом деле, если бы существовала хотя бы одна точка х е Х, то точка тЬ =(О, хц) принадлежала бы множеству У и, кроме того, тогда д(ул) = = О, что противоречит неравенствам д(у ) > д(з,) = д, > О, Таким образом, при д(з,) = д„> 0 множество Х пусто, и задача (1) не имеет смысла. Пусть теперь д(г„) = и,'+... + и„=О. Тогда и„= 0 и г, = (О, е.).
Кроме того, по построению г, = (О, е,) угловая точка множества Х; Покажем, что тогда е„— угловая точка множества Х. Прежде всего ясно, что из з„>0 следует е, > О, а из Сг„= Ь имеем Ае, = Ь. Это значит, что е. Е Х. Далее, рассмотрйм представление е, =ах, +(1 — а)х„О< а <1; х„х, ЕХ, (4) и покажем, что оно возмо1кно лишь при е, = х, = х,. Точки у, = (О, х,), у, = (О, х ), очевидно, принадлежат У. Тогда (4) можно переписать в виде г, = ад+(1 — а)у,, 0< а <1. Но з„— угловая точка множества У. Поэтому последнее равенство для з, возможно лишь при г„= д, = 1Ь. Отсюда следует, что е„=х, = х,. Таким образом, е„— угловая точка множества Х. Тем самым доказана важная Теорема 1. ЕслимножгствоХ=(хЕЕ": х>0, Ах=6) непусто, то оно имеет хотя бы одну угловую точку, Таким образом, с помощью изложенного метода искусственного базиса, составной частью которого является симплекс-метод с антициклином, мы получили возможность узнать, пусто множество Х задачи (1) или непусто, а в случае непустого Х определили одну из его угловых точек е,.
Найденная точка е„вполне может быть использована как начальная угловая точка для 134 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ организации симплекс-процесса для исходной канонической задачи (1). Зная координаты точки е„с помощью теоремы 2.! можно определнть номера базисных переменнйх и ранг матрицы А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
