Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 129
Текст из файла (страница 129)
Как и для функций одной переменной, в задачах математического программирования требуется сформулировать необходимые и достаточные условия существования оптимума. Рис. П2.5. Положение градиента »Г(х) в точке решении х и в точке х, не нвлвюшейсв решением задачи математического программировании (змакамн «+» и «-» указано иаираоление возрастании значений линий уронив) Для области Р в виде параллелепипеда, когда а, < х, < Ь, -со < а, < Ь, <+со, ) =),п данное (необходимое) условие следует понимать как =О, если а, <х, <Ь,; дг" (х ) > О, если х, = а, зс -со; < О, если х, = Ь, и + о.
дхз Если в задаче математического программирования множество Р выпукло, а функция г'(х) дифференцируема в точке х ц Р, то градиент Чг' (х ), если он отличен от нуля, составляет нетупой угол гр с вектором, направленным из х в любую точку х, ц Р. Другими словами, скалярное произведение (згу (х ),х, -х )> О (рис. П25). Для точки х, не являющейся решением задачи, всетда найдЕтСЯ такая тОЧКа хз, Чта ср, будет больше я/2. В тех случаях, когда решение х принадлежит внутренней области Р, градиент 7У(х') = О. Сформулированное условие является необходимым условием локальной оптимальности в задаче минимизации дифференцируемой функции на выпуклом множестве (для выпуклой задачи оно является и достаточным условием глобальной оптимальности).
684 П иложения Здесь градиент «смотрит» внутрь области О. Чтобы определить координаты возможной оптимальной точки, надо из необходи- мых условий составить соответствующие системы уравнений и решить их. В общем случае для задачи вида 1 (х) -+ ппп; 8,(х)>0, !'=1,т; Ь (х)=0,/=1,р, вводится функция Лагранжа т ь(х,п,Л) = 1(х)-х~' ид,(х)+ , 'Л Ь (х), (П2.7) ~=! э=! где и,(1= 1,т), Л (/=1,р) — множители Лагранжа, подлежащие определению наря- ду с координатами вектора х. Множители Лагранжа Л, для ограничений-равенств могут иметь любой знак, множители Лагранжа и, для ограничений-неравенств — не- отрицательны.
Если в задаче математического программирования (П2.4) — (П2.6) множество Р, х н Р ~ Я", выпукло, функции Г'(х), Ры (х), ! = 1, т выпуклы на Р и дифференцируемы в точке х ей, Й=(хе Р~8(х)>0, 1=1т, Ь (х)=07'=1р), функции Ь (х),7'=1,р линейны и при некоторых и,, Л выполняются условия ( ''' )- г ч,Ь(х,п,Л ),х-х )>0 при всех хи Р и и,8,(х )=О, 1=1, то х — (глобальное) решение этой задачи. Соотношения ('1г,Ь(х,п,Л ),х — х )>О (П2.
8) при всех хи Р, = О, если а» <х» <Ь»', дЬ г ° — (х, в, Л ) > О, если х» = а» и -ьь; дх» < О, если х» —— Ь» ,-» э<о; в) если Р учитывает условие пестрила»пельности части (э) переменных и имеет вид Р=(хнЯ"~х» >О, »=1,з~, и,б,(х )=О, 1=1,т, (П2.9) , для задачи выпуклого программирования являются не только необходимыми, но и достаточными условиями существованич решения ~условия Куна — Таккера): а) если х является внутренней точкой области Р; х н1п»Р, тоусловие(П2,8) эквивалентно Ч,Ь(х,п,Л )=0; б) если область Р имеет вид параллелепипеда Р = (х н К~ а» < х» < Ь», » = 1,п~, где -оь < а» < Ь» < »ьь, то соотношение (П2.8) эквива»ентно следующему условию: длялюбого А =1,т П уложение 2.
Математическое п о амму рвание основные положения 685 где 0 < 5 < п, та условие (П2.8) эквивалентно совокупности условий! — (х,в,Л )>О, х!,— (Х,ц, Л )=О, к=!,5, (П2.10) дХ!, дЬ г ° — 1хх, ц, Л ) = О, 1с = 5+ 1, и. дх!, В отличие от методов отыскания оптимальных решений в задачах без ограничений-неравенств здесь появляется дополнительное условие (П2.9), которое называют условием дополняющей нежесткасти: и, я,(х )=О, 1=1,т. Это условие разделяет ограничения-неравенства на активные, которые в точке оптимума обращаются в нуль (д,(х )=О, 1=1,1,, 1, <т), и пассивные (8,(х )кО, !'= Ц, 1, +1з = т). Для пассивных ограничений коэффициенты Лагранжа и, должны быть равны нулю, при этом пассивные ограничения не оказывают своего влияния на решение х, Рассмотрим случай, когда в функции Лагранжа присутствуют только ограничения-неравенства: 1 (х) -+ пнп, я, (х) < О, 1 = 1, т . Тогда в точке минимума Ч,1'(х )+ ) и,Чх8,(х )=О, оа т.е, антиградиент целевой функции является неотрицательной линейной комбинацией градиентов функций, образующих активные ограничения в точке х (рис.
П2.6). Ч„д (х) Рис. П2.б. Связь ваиравлеинй градиентов активных ограничений и антнгралиента нелевой функнни в точке решении х н в точке х, не анлвюшейеа точкой решении На рис. П2.6 показано множество, образованное неравенствами я! (х) < О, 8з(х)<0, 85(х)<0, Здесь же в точках х и х указаны направления градиентов активных ограничений и антиградиента целевой функции. Отсюда следует, что точкой оптимума не может быть точка х, т.к, в ней не выполняется условие того, что антиградиент 1'(х) есть положительная линейная комбинация градиентов активных ограничений.
Решением является точка х, где данное условие выполняется. П иложения 686 Мы рассмотрели некоторые условия существования решения, учтя производные первого порядка. Как и для функции одной переменной, нри анализе условий олти- мольности можно рассматривать производные высших норядков (в частности, второго). В задачах математического программирования сформулированы и доказа- ны условия оптимальности второго порядка, в которых оперируют вторыми частны- ми производными от функции Лагранжа. В общем случае задачу математического программирования можно было бы ре- шать по следующей схеме: 1) записывание задачи в канонической форме вида (П2.4) — (П2.6) и составление функции Лагранжа (П2.7); 2) составление системы условий, которые характеризуют решение (определяют точки, где возможно существование оптимального решения — стационарные точки); в развернутой форме записывают условия (П2.8), (П2.9), а также условия, накладываемые задачей на допустимые значения х и на множители Лагранжа.
Например, для условия (П2.10) полная система для определения стационарных точек имеет вид д7. дА х >О; — (х,н,ь)>0;х — (х,в,Л)=О,к=1,в; 1д, '' '"д, дЬ вЂ” (х,н,Л) =О, /с =в+1,н; дхь и,>0, д,(х)>0; и8,(х)=0,1=1,/; д,(х) =0,1=!+1,т; 3) решение полученной системы необходимых условий.
Это удается сделать в аналитическом виде лишь в редких случаях; 4) если удалось получить решение системы необходимых'условий — стационарные точки, надо провести исследование стационарных точек для отбора среди них решений. Это сделать непросто. Иногда проще провести непосредственное исследование поведения целевой функции в стационарной точке.
На последних двух этапах полезно привлечение физических и геометрических со- ображений о возможном решении задачи математического программирования. ТЕОРИЯ ДВОЙСТВЕННОСТИ И НЕДИФФЕРЕНЦИАЛЬНЫЕ УСЛОВИЯ ОПТИМАЛЬНОСТИ В ЗАДАЧЕ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ В задачах математического программирования (П2.4) — (П2.6) можно указать условия оптимальности, не прибегая к понятиям производных и градиентов, с помощью так называемой теории двойственности. Особенно плодотворен этот подход в задачах выпуклого программирования. Будем рассматривать функцию Лагранжа (П2.7). Обозначим через 7' точную нижнюю грань целевой функции задачи (П2.4) — (П2.6) на ее допустимом множестве Р: 7' = 1лТ 7'(х) .
Точка х е Р является решением задачи (П2.4) — (П2.6) в том и *чо / *'~ только том случае, если 7 = 7 (х ). Введем вектор у с координатами и,(1 =),т) и ). (7'=1,р). Вектор у называется вектором Куна — Таккера задачи (П2.4) — (П2.6), если при всех х и Р П уложение 2. Математическое п о амму рвание основные положения) 687 Г' < у(х)-~и,д,(х)+ , 'Х Ь,(х)=ь(х,у ) г=( 11 Любой задаче математического программирования можно поставить в соот- ветствие так называемую двойственную задачу оптимизации. Между прямой и двойственной задачами имеются полезные связи. Двойственной к задаче (П2.4) — (П2.б) называют задачу (р(у) — вшах; уи у, е(г)= гг(.,Ч=ьг~Г((-йва(*) Ь в ( (]: хе(Э хеп~ у = (у и д] (р(у) > -ео) Исходную задачу называют прямой.
Если целевую функцию в двойственной задаче (р(у) -ь шах заменить на -цг(у) -в ппп, то можно утверждать, что задача, двой- ственная к произвольной задаче математического программирования, всегда выпукла. Если в задаче математического программирования множество замкнугпо и выпукло, функции г (х), л,(х), 1=1,лг непрерывны и выпуклы на ах, функции гт (х),7'=!,р, линейны или отсутствуют и решение прячой задачи конечно (1 > -ео), в частно- сти, она имеет решение, то множество решений двойственной задачи непусто и сов- падает с множеством векторов Куна — Таккера прямой задачи.
При этол( справедливо соотношение двойственности 1" = (р, т.е. минимум целевой функции прямой задачи совпадает с максимумом целевой функции двойственной задачи. Учитывая, что число переменных в двойственной задаче равно числу условий-ограничений в прямой задаче, в ряде случаев двойственную задачу решить проще. Получим необходимые и достаточные условия оптимальности в задаче выпуклого программирования на основе теории двойственности. В этом случае изменится толь- ко форма необходимых и достаточных условий (не будут участвовать производные), но предпосылки в обоих случаях одинаковы. Пара (х,у )и РиЯ называется седловой точкой функции Ь(х,у) на РхД, если ь(х,у )=ш(пь(х,у ); ь(х,у )= шаль(х,у), те.
ь(х,у )> Чх,у )>А(х,у) привсех х ар, уегг. Тогда точка х и Р является решением прямой задачи в том и только тач слуг чае, всаи существует векгпор у и Д, такбй, что пара (х,у ) — седловин точка функции Лагранжа С(х,у) на Р х Я . Таким образом, если одновременно решать н прямую и двойственную задачи, то к точке минимума (к решению) мы можем при- ближаться с «двух» сторон. Пример П2.1. Раееиотрии пример. минимизировать Г(х) =( х, - 2 ( + ( х, - 2(, при ограничениях В,(х) = х, — хт > 0 х П вложении 688 Ь(х) = х, ьхе — 1=0 г з Прежде всего построим по условиям-ограничениям допустимую обласп 0 — множество точек (хнхз), удовлетворяющих ограничениям залачи. Ограничение я,(х) определяет обласзь авнугрив параболы х, = х,' (рис.
П2.7); ограничение Ь,(х) — окружность единичного радиуса с центром в начале координат (рис. П2.7). Допустимвя область 0 этой задачи — дуга окружности АВС. Чтобы найти точку, в которой функция У(х) принимает минимальное значение на допустимой области О, построим линии уровня у(х) — штриховые линии. В точке (2,2) у(х) =О; при у(х) =1 и у(х) = 2 линии уровня образуют квадраты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
