Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 14
Текст из файла (страница 14)
Доказательство симплекс-метода. Предложение 1. Допустимая в задаче (зь) точка х является крайней тонкой множества допустимых элементов тогда и толька тогда, когда столбцы матрицы А, соответствующие положительным координатам вектора х, линейно независимь!. <3 Доказательство необходимости и достаточности проведем от противного.
А) Пусть х — крайняя точка множества С. Предположим, что столбцы матрицы А, соответствующие положительным координатам вектора х, линейно зависимы. Для определенности считаем, что зто столбцы а',...,аь. Из линейной зависимости следует, что найдется ненулевой набор чисел Л!,...,Лы для которого ~ Л!а!=О, т. е. 'АЛ=О для вектора !=! Л= (Л„...,Лд, О,...,0)енК". Тогда вектор х(8) =х+ОЛ допустимый при 8 близких к нулю, что противоречит тому, что х— крайняя точка множества допустимых элементов. Б) Пусть х — допустимая точка н столбцы матрицы А, соот.
ветствующие положительным координатам вектора х, линейно независимы. Опять для определенности считаем, что зто столбцы а',..., аь, Предположим, что х не является крайней точкой множества С. Тогда найдутся отличные от х допустимые точки у и г, у~г, такие что при некотором а, 0<а<1, х=ау+ (1— — а)г.
Из последнего равенства следует, что у точек у и г ненулевыми будут те же самые координаты, что и у х, т. е. перь ь ь вые й координат. Поскольку Уу,а'=Ь, 5'г!а!=Ь, то ~~" (у,— !=- ! !=:! !=! — г!)а'=О. Отсюда следует, что векторы а',...а" линейно зависимы, что противоречит условию. Таким образом, наше предположение'неверно н точка х крайняя. (> Предложение 2. В невырожденной задаче любая допустимая точка имеет не менее и! положительных координат. <~ Доказательство проведем от противного.
Предположим, что существует допустимая точка, у которой менее п! положительных координат. Для определенности считаем, что зто первые й коордннат (я<!и). Рассмотрим множество С решений системы АУ=Ь, У)0, где У=(Уь,Уь)епК", А=(а',...,а")— матрица порядка яХп. Пусть у — крайняя точка множества С (нетрудно понять, что она существует). Тогда точка х=(у, 0)епК" — крайняя точка множества С, у которой менее пч по.ложительных координат. Это противоречит невырожденности задачи. ~> л зэк. т 65 Предложение 3.
В невырожденной задаче допустимам'; точка содержит ровно т положительных координат тогда ы,' только тогда, когда она — крайняя точка множества допусти " мых точек. <3 Необходимость докажем от противного. Пусть в невы..! рожденной задаче допустимая точка содержит т положитель ~ ных координат, для определенности первых. Предположим, что эта точка не является крайней, тогда по предложению 1 й столбцы матрицы А а',..., а~ линейно зависимы. Значит, среды~ решений системы Ау=Ь, у)0, где А=(а',...,а'), у=(уь л ...,у ) ~й'", найдется решение у, у которого менее т положи. ', тельных координат. Следовательно, вектор х=(у, 0)вне" яв-' ляется допустимой точкой (т.
е. х~С), у которой менее т по- ". ложительных координат, что противоречит предложению 2. достаточность следует из определения' невырожденности за-'а дачи. (> Теорема. Пусть х=(хь...,х, 0,...,0)енК", йг)0, 1=.;. =1,..., т,— крайняя точка в невырожденной задаче (зк) ли-'' нейного программирования в канонической форме. Тогда: а) если Л) О, то х — решение задачи; б) если для некоторого / А~<0 и хг~(0, го значение задача ' срач=+ ос~ в) если не выполнены условия п. а) и б)„то х„,— крайням точка множества допустимых элементов, значение функииона-: ла при этом возрастет на величину — Оь1>р, а разложение век::.
горов х„„а', ..., а" производится согласно симплекс-методу' :' а) Обозначим у=Аз*-'св (напомним, что де1АэФО). По- ' скольку при у=т+1,...,и л>=(св, хг> — с;=(Аз*у, хг> — с~=(у, Авхг) — с;=(у, аг) — с;)О, это означает, что Ан*уэ'сн и, следовательно, А"у)с, т. е. у— допустимый элемент в задаче (з), п. 3.2.2, двойственной к исходной задаче (зк) п.
3.1.1 в канонической форме. С другоВ стороны, так как у вектора А у — с первые т координат — ну-:„, ли, значит, (А*у — с, х>=0 -">(с, х>=(Ь, у). Таким образом, по критерию решения х — решение задачи. б) положим х(1) =х — 1хг+геь тогда х(1))0 и Ах(1) =Ах — 1Авх>+1Ае;=Ах — 1аг+1а>=Ь,, т.
е. х(1) — допустимый элемент У1ъО, при этом (с, х(1)> — (с, х>= — 1(с, хг)+Е(с, еД= — 1(г; — сг) = — 1Л;-~-+се ' ' при 1- +со. в) Предположим, что не выполнены условия и. а) и б) теоремы,. тогда для йекоторого т+1(1ь<п, Ли< 0 и Оь=ш(п(хйхи,>хш ) 0) = хс,/хчн ) О. Возьмем 1 =(1в, 1н)~ 1н =(О, ..., 1, ..., 0) 66 — Аа !Ан!н, х(0 ) = х+ О 1. Тогда Ах(0 ) =Ах+ О А1 = Ах=«Ь, ~(О )=0(и~О, хв(О )=ха+О в=ха — О Ав ~Ан(~=ха — О А~'а! =хв — О,хб)0 в сйлу выбора О„т. е. «(0,) — допустимая точка.
'Поскольку по.предложению 2 в невырожденной задаче допустимая точка содержит не менее т положительных координат, лишь одна координата х!, у вектора хз — О,х! обращается в нуль. Таким образом, допустимая точка хз(Оо) имеет ровно т положительных координат на местах 1,...,!з — 1, !»!+1,...,я!, и, следовательно, по предложению 3 точка х„«=х(Оа) крайняя.
Значение функционала при этом возрастет на величину — Оф!ч (см. доказательство ц. б)). Формулы,(х ), =х! — О,хц,=х,— х!пхь)х!л„! =1, ..., т, (х„„)и=О,=хь/х!~, означают, что в новой симплексной таблице столбец х„, выписывается согласно указанному методу нестроения новой симплексной таблицы. Покажем, что и остальные столбцы (х„,)! строятся по этому же способу. Для этого »вычислим координаты (хп)„, разложения векторов а!, 1=1,.... ...,л, по базису аг, ..., и! -!, а( а»»+! и В старом базисе а!= ~ а»х!! — — ~) а!хч+а!х!,!, /=1, ..., и, с=.! М!в »Отсюда прн т'=1, а!» = ~ а'хн,+а!»х! !,.
» ! ь»»'!» «1оскольку х!,!,-,й, то е ! «!!»»/» и!»= — '~' а! — '+— «;! х!! ' 1=! ьм. тогда и! = ~~ '(х,. — — '~ а'-(- — 'а!». «!! «!,» '». «! ! Ц ;.. 3 1=! !»й!» Таким образом, (х, )!„.= — "~ г=1, ..., а г(х„,„)!л.=1, «!»!» (х )!!=х!а — х!пх»!!хЧ!,» сань!«» !=1. ° ° ° л!» 1= 1, .... и' !(хи,), =О,'!Ф!О (> 67 З 4. КЛАССИЧЕСКОЕ ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ В этом параграфе выводятея необходимые условия первого, ' порядка для некоторых классов задач, традиционно рассматриваемых в классическом варнационном исчислении (к.в.и.): задачи Больца, простейшей задачи классического вариационного исчисления, изометрической задачи и т. п. При выводе не- ~ обходнмых условий экстремума мы пытались использовать 1 только элементарные средства классического анализа, поэтому материалы этого параграфа можно изучать независимо ог предыдущего.
4.1. Задача Больца 4.1.1. Постановка задачи. Задачей Больца называется следующая экстремальная задача без ограннченнй в пространстве непрерывно дифференцнруемых функций С'([1», 11]): с, »3 (х( )) = Б(1, х(1), х(1)) ~И+1(х(1»), х(1»)) — ». ех1г. й Здесь 1.=ь(1, х, х) — функция трех, а 1=1(хь, х~) — функция двух переменных. Отрезок [1», 1,] предполагается фиксированным н конечным, — ос<1»<11<+со. Задача Больца — элементарная задача классического варнацнонного исчисления.
Функцию Ь называют ингегрантом, функцию 1 — герминантом, а функционал Я вЂ” функционалом Больца. Скажем, что функция х( )енС'([1», Ц) доставляет (слабый) локальный минимум (максимум) задаче (з), нлн, что то же самое, функционалу М в пространстве С'([1», 11)) н пишем х(.)ея1оспппз(!остахз), есля найдется 6>0, такое, что для любой функции х( )~С'([1», 11)), для которой!!х( ) — х(.)!1,( <6 (с=»Пх( ) — х( )Псцн,нв(6, Цх( ) — х( )Пс<п,,ав(6), выполнено неравенство Щ(х( )))Я(х(.)) (Я(х( ))(йй(х( ))).
Наряду со слабым экстремумом в классическом варнацнонном исчислении традиционно изучается также сильный экстремум. При этом несколько расширяется класс функций, на которых рассматривается функционал Я. Экстремум в задаче ищется среди функций х( ), принадлежащих КС'([1», 1,1), т. е. кусочно-непрерывно дифференцируемых функций. К понятию сильного экстремума вернемся в п. 9.2.1. Прн решении задач вариационного исчисления употребляем далее термины «абсолютный экстремум» илн «глобальный экстремум». В этн термины можно вкладывать стандартный' 68 смысл, согласно которому найденная функция имеет экстремальное значение функционала среди всех допустимых функций (а у нас допустимые функции принадлежат С' или КС'). Однако, как правило, функции, доставляющие абсолютный экстремум в С' или КС', доставляют абсолютный экстремум и среди более широкого класса функций — всех абсолютно непрерывных функций, на которых функционал определен.
4.1.2. Необходимые условия экстремума. Теорема. Пусть функция х(.)~С'([1ы 1,]) доставляет слабый локальный экстремум в задаче Больца (з). Предположим, что интегрант Б непрерывен вместе со своими частными производными по х и х в некоторой окрестности множества ((1, х(1), «(1)) ]1ен[(ы 11]), а терминант 1 непрерывно диффв ренцируем в окрестности точки («(1ь), Х(11)).
Тогда Хй (; ~ С'([1„11]) (1.„„, =)-„(г, х(1), х(1))) и выполнены а) уравнение Эйлера — Ь„(1) +Е,(1) =0; б) условия трансверсальности 1 =Х„ь (х(1,), х(1,)) . Ьй(Е~)=( — 1)ьХ„„, й=о, 1. <) Доказательство теоремы разобьем на несколько этапов. А) Определение вар нации по Лагранжу. Возь- мем произвольную, но фиксированную функцию х( )анС'([гь, й]). Поскольку Х( ) ен1осех1г з, то функция одного переменного »» рР): =а(х(.)+К (.))=~7(1, (1)+Ь ®,"(1)+ с, +лх(»))й»+1(х(»ь)+й«((о) х((г)+й«((г)) имеет экстремум прн Х О. Положим Р(1, ).) Б(8, Я(1)+. +Ах(г), Я(1)+М(4)).
Из условий гладкости, наложенных на Е., Х(.), «( ), следует, что функция»р(Х) дифференцируема в ну- ле. Действительно, функции Р и Р, непрерывны в некотором прямоугольнике [Гы 11] Х [ — Ье, Хь], и, значит, по известной тео- реме из анализа можно дифференцировать под знаком инте- грала [15, т. 2, с. 107]. Но тогда по теореме Ферма <р'(0) =О. Дифференцируя функцию р н полагая ) =О, получаем ,р~ (0) Н йг(х( ) + )»х( )) — М(х(.)) вм блй (х( ), х( )) = «о ц = 1 (»'»» (») х Я+ 7йя х (1)) йт+ 1 «($0)+ 1 х(1 )= О (1) ~ «(') е= С ([»ы»1]). Таким образом, мы вычислили вариацию по Лаграннсу функционала Больца М и выяснили, что необходимое условие слабого локального экстремума этого функционала в Х( ) — ' равенство нулю его вариации по Лагранжу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
