1612726871-fd1970eb57207f2e4883f7549db906ce (Ларин, Плясунов - Примеры и задачи), страница 4
Описание файла
PDF-файл из архива "Ларин, Плясунов - Примеры и задачи", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 6 семестр, которые можно найти в файловом архиве НГУ. Не смотря на прямую связь этого архива с НГУ, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Ëàãðàíæïðåäëîæèë ìåòîä, â êîòîðîì âñå ïåðåìåííûå ñîõðàíÿþò îäèíàêîâóþ ðîëü.Ìåòîä íåîïðåäåë¼ííûõ ìíîæèòåëåé Ëàãðàíæà. Ââåä¼ì â ðàññìîòðåíèå íîâûåïåðåìåííûå yj (j = 1, m) è ôóíêöèþF (x, y) = f (x) +mXyj ϕj (x).j=1Ïåðåìåííûå yj íàçûâàþòñÿ íåîïðåäåë¼ííûìè ìíîæèòåëÿìè Ëàãðàíæà, à ôóíêöèÿ F (x, y) ôóíêöèåé Ëàãðàíæà.Ïóñòü â òî÷êå x∗ , óäîâëåòâîðÿþùåé ñèñòåìå (30 ), âûïîëíåíû óñëîâèÿ òåîðåìû î íåÿâíûõ ôóíêöèÿõ. Òîãäà, äëÿ òîãî ÷òîáû òî÷êà x∗ áûëà òî÷êîé ýêñòðåìóìà çàäà÷è (1)(2),íåîáõîäèìî ñóùåñòâîâàíèå òàêèõ ÷èñåë yj∗ (j = 1, m), ÷òî âûïîëíÿþòñÿ ðàâåíñòâà∂F (x∗ , y ∗ )= 0 (i = 1, n),∂xi(7)∂F (x∗ , y ∗ )= 0 (j = 1, m).∂yj(8)Óñëîâèÿ (8), î÷åâèäíî, ýêâèâàëåíòíû óñëîâèÿì (30 ).
Ïðè ðåøåíèè çàäà÷è (1)(2) äàííûì ìåòîäîì ñóùåñòâåííóþ ðîëü èãðàåò ïðåäïîëîæåíèå î ðàíãå ìàòðèöû (4). ×òîáû áûòüóâåðåííûì â òîì, ÷òî íå ïðîïóùåíà íè îäíà ïîäîçðèòåëüíàÿ òî÷êà, ñëåäóåò ïðåäâàðèòåëüíîóñòàíîâèòü, ÷òî ýòî ïðåäïîëîæåíèå âûïîëíÿåòñÿ âî âñåõ òî÷êàõ ìíîæåñòâà X .Ïðèìåð 1. Íàéòè ýêñòðåìóì ôóíêöèè f (x) = x1 + x2 + x3 + x4 ïðè îãðàíè÷åíèèðàâåíñòâå ϕ(x) = x1 x2 x3 x4 − a4 = 0 (a > 0) â îáëàñòè X = {xi > 0 | i = 1, n}.13Ðåøåíèå.
Ïðèìåíèì ìåòîä ìíîæèòåëåé Ëàãðàíæà (óñëîâèå íà ðàíã ìàòðèöû â îáëàñòèX î÷åâèäíî âûïîëíåíî). Ââåä¼ì ìíîæèòåëü y è ôóíêöèþ F (x, y) = f (x) + yϕ(x). Ñèñòåìàóðàâíåíèé (7)(8) ïðèíèìàåò âèä 0Fx1 (x, y) = 1 + x2 x3 x4 y = 0, Fx0 2 (x, y) = 1 + x1 x3 x4 y = 0,Fx0 3 (x, y) = 1 + x1 x2 x4 y = 0,F 0 (x, y) = 1 + x1 x2 x3 y = 0, x0 4Fy (x, y) = x1 x2 x3 x4 − a4 = 0.Î÷åâèäíî, ÷òî y 6= 0, ïîýòîìó ìîæíî çàïèñàòü ðàâåíñòâà −1/y = x1 x2 x3 = x1 x2 x4 =x1 x3 x4 = x2 x3 x4 .
Îòñþäà ñëåäóåò, ÷òî x1 = x2 = x3 = x4 . Ïîäñòàâëÿÿ â ïîñëåäíåå óðàâíåíèå,ïîëó÷àåì, ÷òî xi = a äëÿ âñåõ i = 1, 2, 3, 4.Ïðèìåð 2. Íàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ êâàäðàòè÷íîé ôîðìûf (x) =n XnXaij xi xj ,i=1 j=1Pn2ãäå aij = aji , íà ìíîæåñòâå X = {x |i=1 xi = 1}.Ðåøåíèå. Òàê êàê ìíîæåñòâî X îãðàíè÷åíî è çàìêíóòî, òî ñóùåñòâîâàíèå â í¼ì òî÷åê,ãäå ôóíêöèÿ ïðèíèìàåò íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ, âûòåêàåò èç òåîðåìû Âåéåðøòðàññà.
Î÷åâèäíî, ÷òî ðàíã ìàòðèöû (2x1 , 2x2 , . . . , 2xn ) ðàâåí íóëþ òîëüêî â òî÷êå 0,êîòîðàÿ íå ïðèíàäëåæèò ìíîæåñòâó X . Ðàññìîòðèì ôóíêöèþ ËàãðàíæàF (x, y) = f (x) + y(1 −nXx2i ).i=1Óðàâíåíèÿ (7) èìåþò âèänXaij xj − yxi = 0 (i = 1, n).(9)j=1Èç êóðñà àëãåáðû èçâåñòíî, ÷òî ñèñòåìà èç n ëèíåéíûõ óðàâíåíèé ñ n íåèçâåñòíûìè ñíóëåâîé ïðàâîé ÷àñòüþ èìååò íåíóëåâîå ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà îïðåäåëèòåëüñèñòåìû ðàâåí íóëþ, ò. å. â íàøåì ñëó÷àå èìåå쯯¯ a11 − ya12...a1n ¯¯¯¯ a21a22 − y . . .a2n ¯¯¯(10)¯ ...¯ = 0..........¯¯¯ an1an2. . .
ann − y ¯Åñëè y êîðåíü óðàâíåíèÿ (10) (ò. å. ñîáñòâåííîå ÷èñëî ìàòðèöû A), òî ñóùåñòâóåò èíåíóëåâîå x ∈ X , óäîâëåòâîðÿþùåå ñèñòåìå (9). Íî îïðåäåëåíèå ýòèõ çíà÷åíèé äëÿ íàñ èíòåðåñà íå ïðåäñòàâëÿåò, òàê êàê íàì íàäî íàéòè òîëüêî íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿöåëåâîé ôóíêöèè.Óìíîæèâ i-å óðàâíåíèå ñèñòåìû (9) íà xi è ñëîæèâ âñå óðàâíåíèÿ, ïîëó÷èì ðàâåíñòâîf (x) − ynXx2i = 0,i=1÷òî, â ñèëó óñëîâèÿ x ∈ X, ïðèâîäèò ê ðàâåíñòâó f (x) = y . Òàêèì îáðàçîì, èñêîìûå íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) íà ìíîæåñòâå X ñîâïàäàþò ñ íàèáîëüøèìè íàèìåíüøèì èç ñîáñòâåííûõ ÷èñåë ìàòðèöû A.14Ïðèìåð 3. Ïóñòü òð¼õîñíûé ýëëèïñîèä x21 /a21 + x22 /a22 + x23 /a23 = 1, ãäå a1 > a2 > a3 > 0,ïåðåñå÷¼í ïëîñêîñòüþ b1 x1 + b2 x2 + b3 x3 = 0 (ãäå âñå bi 6= 0), ïðîõîäÿùåé ÷åðåç åãî öåíòð.Òðåáóåòñÿ îïðåäåëèòü ïîëóîñè ïîëó÷àþùåãîñÿ â ñå÷åíèè ýëëèïñà.Ðåøåíèå. Ýòà çàäà÷à ýêâèâàëåíòíà íàõîæäåíèþ ýêñòðåìóìà ôóíêöèè f (x) = x21 + x22 +2x3 íà ìíîæåñòâå X = {x | x21 /a21 + x22 /a22 + x23 /a23 = 1 è b1 x1 + b2 x2 + b3 x3 = 0}Ìåòîä èñêëþ÷åíèÿ íåçàâèñèìûõ ïåðåìåííûõ ïðèâîäèò ê ñëîæíûì âûêëàäêàì, ïîýòîìó ëó÷øå ïðèìåíèòü ìåòîä ìíîæèòåëåé Ëàãðàíæà.
Ñíà÷àëà óáåäèìñÿ, ÷òî âûïîëíÿåòñÿóñëîâèå íà ðàíã ìàòðèöû (4). Äåéñòâèòåëüíî, åñë趵2x1 /a21 2x2 /a22 2x3 /a23= 1,Rangb1b2b3òî xi = ca2i bi äëÿ i = 1, 2, 3 è íåêîòîðîãî c ∈ E1 . Íî òîãäàx21 x22 x23+ 2 + 2 = c2 b21 a21 + c2 b22 a22 + c2 b23 a23 = c(b1 x1 + b2 x2 + b3 x3 ) = 0,a21a2a3ò. å.
x ∈/ X . Ôóíêöèÿ Ëàãðàíæà èìååò âèäF (x, y) = x21 + x22 + x23 + y1 (x21 x22 x23+ 2 + 2 − 1) + y2 (b1 x1 + b2 x2 + b3 x3 ).a21a2a3Ïðèðàâíÿåì íóëþ å¼ ïðîèçâîäíûå ïî x:xi +y1 xi y2 bi+= 0 (i = 1, 2, 3).2a2i(11)Óìíîæèâ ýòè óðàâíåíèÿ íà xi è ñëîæèâ (ñ ó÷¼òîì îãðàíè÷åíèé), ïîëó÷èì, ÷òî y1 = −f (x).Óáåäèìñÿ, ÷òî (1+y1 /a2i ) 6= 0 äëÿ âñåõ i. Äåéñòâèòåëüíî, åñëè, íàïðèìåð, (1+y1 /a21 ) = 0,òî y2 = 0 è, ñëåäîâàòåëüíî, x2 (1 + y1 /a22 ) = 0 è x3 (1 + y1 /a23 ) = 0. Èç óñëîâèÿ b1 x1 +b2 x2 + b3 x3 = 0 ñëåäóåò, ÷òî ïî êðàéíåé ìåðå îäíî èç ÷èñåë x2 , x3 íå ðàâíî íóëþ. Íî òîãäà(1 + y1 /a22 ) = 0 èëè (1 + y1 /a23 ) = 0, ÷òî ïðîòèâîðå÷èò óñëîâèþ a1 > a2 > a3 .Òàêèì îáðàçîì, èç ñîîòíîøåíèé (11) âûòåêàåò, ÷òîxi = −y2 bi a2i(i = 1, 2, 3).2(a2i + y1 )Îòñþäà ñëåäóåò, ÷òî3Xi=1bi xi = −y23Xi=1b2i a2i= 0.2(a2i + y1 )Ïîñêîëüêó y2 6= 0 (òàê êàê íå âñå xi ðàâíû íóëþ), ïîëó÷àåì, ÷òî3Xb2i a2i= 0.2a+y1ii=1Îòñþäà ñ ó÷¼òîì ðàíåå äîêàçàííîãî ðàâåíñòâà f (x) = −y1 íåïîñðåäñòâåííî îïðåäåëÿþòñÿèíòåðåñóþùèå íàñ çíà÷åíèÿ öåëåâîé ôóíêöèè.Ïðèìåð 4.
Íàéòè ðàññòîÿíèå ìåæäó ïàðàáîëîé y = x2 è ïðÿìîé x − y − 2 = 0.Ðåøåíèå. Ïðåæäå âñåãî ñôîðìóëèðóåì îïòèìèçàöèîííóþ çàäà÷ó. Îáîçíà÷èì ïðîèçâîëüíóþ òî÷êó, ïðèíàäëåæàùóþ ïàðàáîëå, ÷åðåç (x1 , y1 ), à ïðÿìîé ÷åðåç (x2 , y2 ). Òîãäàíàøà çàäà÷à ñâîäèòñÿ ê ìèíèìèçàöèè ôóíêöèè f (x1 , y1 , x2 , y2 ) = (x1 − x2 )2 + (y1 − y2 )2 ïðèóñëîâèÿõ y1 − x21 = 0 è x2 − y2 − 2 = 0. Ìàòðèöà (4) èìååò âèä15µ−2x1 1 0 000 1 −1¶,è å¼ ðàíã, î÷åâèäíî, ðàâåí äâóì. Âûïèøåì ôóíêöèþ Ëàãðàíæà F (x, y, z) = (x1 − x2 )2 +(y1 − y2 )2 + z1 (y1 − x21 ) + z2 (x2 − y2 − 2).
Îòñþäà ïîëó÷àåì ñèñòåìó 0F = 2(x1 − x2 ) − 2x1 z1 = 0, x0 1Fx2 = −2(x1 − x2 ) + z2 = 0,(12)Fy0 1 = 2(y1 − y2 ) + z1 = 0, 0Fy2 = −2(y1 − y2 ) − z2 = 0.Ñëîæèâ ïî÷ëåííî ïåðâîå ðàâåíñòâî ñî âòîðûì, à òðåòüå ñ ÷åòâ¼ðòûì, ïîëó÷èì óñëîâèÿz2 = 2x1 z1 è z1 = z2 . Åñëè z1 = z2 = 0, òî èç ñèñòåìû (12) ñëåäóåò, ÷òî y1 = y2 è x1 =x2 , ò. å. ïðÿìàÿ è ïàðàáîëà ïåðåñåêàþòñÿ. Îäíàêî â íàøåì ñëó÷àå ýòî íå òàê, ïîñêîëüêóñèñòåìà óðàâíåíèé y = x2 , x − y − 2 = 0 íåñîâìåñòíà.
Çíà÷èò, z1 6= 0, è x1 = 1/2. Òîãäày1 = 1/4. Ñëîæèâ â ñèñòåìå (12) âòîðîå è ÷åòâ¼ðòîå óðàâíåíèÿ è ïîäñòàâèâ íàéäåííûåçíà÷åíèÿ ïåðåìåííûõ, ïîëó÷èì ñîîòíîøåíèå x2 + y2 = x1 + y1 = 3/4. Òàê êàê x2 = y2 + 2,ïðèõîäèì ê òî÷êå px2 = 11/8, y2 = −5/8.
Òàêèì√îáðàçîì, ðàññòîÿíèå ìåæäó äàííûìè ïðÿìîéè ïàðàáîëîé åñòü f (1/2, 1/4, 11/8, −5/8) = 7 2/8.Ïðèìåð 5. Íàéòè íàèìåíüøåå çíà÷åíèå ôóíêöèè f (x) = x1 ïðè îãðàíè÷åíèè x31 −x22 = 0.Ðåøåíèå. Òàê êàê x1 = (x2 )2/3 ≥ 0, òî îïòèìàëüíîå ðåøåíèå çàäà÷è åñòü x∗ = (0, 0).Åñëè ââåñòè ôóíêöèþ Ëàãðàíæà F (x, y) = x1 +y(x31 −x22 ) è çàòåì ðåøàòü ñèñòåìó óðàâíåíèé 0 Fx1 = 1 + 3yx21 = 0,F 0 = −2yx2 = 0,(13) x0 232Fy = x1 − x2 = 0,òî íåòðóäíî óáåäèòüñÿ, ÷òî îíà íåñîâìåñòíà.
Ïðè÷èíîé ýòîãî ïðîòèâîðå÷èÿ ÿâëÿåòñÿ òî,÷òî ðàíã ìàòðèöû (3x21 , −2x2 ) ðàâåí 0 â òî÷êå x∗ = (0, 0). Ñëåäîâàòåëüíî, ìåòîä Ëàãðàíæàâ òî÷êå (0, 0) íåïðèìåíèì, òàê êàê íå âûïîëíåíû óñëîâèÿ òåîðåìû î íåÿâíûõ ôóíêöèÿõ.Çàäà÷è1. Ðåøèòü çàäà÷è óñëîâíîé îïòèìèçàöèè:1) f (x) = x1 x2 x3 −→ extrX ,X = {x | x21 + x22 + x23 = 1, x1 + x2 + x3 = 0};2) f (x) = x1 x2 x3 −→ extrX ,X = {x | x1 + x2 + x3 = 5, x1 x2 + x2 x3 + x1 x3 = 8};3) f (x) = x1 x22 x33 −→ extrX ,X = {x | x1 + 2x2 + 3x3 = a, x1 > 0, x2 > 0 x3 > 0} (a > 0);4) f (x) = x1 + x2 + x3 −→ extrX ,X = {x | x21 + x22 = 1, x1 + x2 − x3 = 0};5) f (x) = x2 −→ extrX ,X = {x | x31 + x32 − 3x1 x2 = 0};6) f (x) = x1 + x2 + x23 + 2(x1 x2 + x1 x3 + x2 x3 ) −→ extrX ,X = {x | x21 + x22 + x3 = 1}.162. Íà ñôåðå x2 + y 2 + z 2 = 1 íàéòè òî÷êó, ñóììà êâàäðàòîâ ðàññòîÿíèé îò êîòîðîé äî Näàííûõ òî÷åê (xi , yi , zi )> , i = 1, N áûëà áû ìèíèìàëüíà.3.
Äàííîå ïîëîæèòåëüíîå ÷èñëî a ðàçëîæèòü íà n ïîëîæèòåëüíûõ ñîìíîæèòåëåé òàê,÷òîáû ñóììà èõ îáðàòíûõ âåëè÷èí áûëà áû íàèìåíüøåé.4. Íàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ êàæäîé ïåðåìåííîé, äëÿ êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî (x2 + y 2 + z 2 )2 = a2 (x2 + y 2 − z 2 ) (a > 0).5. Íàéòè êðàò÷àéøåå ðàññòîÿíèå îò òî÷êè (x0 , y0 , z0 )> äî ïëîñêîñòè a1 x1 + a2 x2 + a3 x3 +a0 = 0.2.4.
Çàäà÷è ñ îãðàíè÷åíèÿìèíåðàâåíñòâàìè ýòîì ðàçäåëå ðàññìàòðèâàåòñÿ çàäà÷à f (x) −→ extrx∈X , îáëàñòü äîïóñòèìûõ çíà÷åíèéêîòîðîé îïðåäåëÿåòñÿ êàê X = {x ∈ En | ϕj (x) ≤ 0 (j = 1, m)}.Ïóñòü ôóíêöèè ϕj (x) (j = 1, m) îïðåäåëåíû, íåïðåðûâíû è èìåþò íåïðåðûâíûå ïðîèçâîäíûå â En , à ôóíêöèÿ f (x) îïðåäåëåíà, íåïðåðûâíà è èìååò íåïðåðûâíûå ïðîèçâîäíûåíà X . Åñëè ìíîæåñòâî X îãðàíè÷åíî (çàìêíóòîñòü ñëåäóåò èç íåïðåðûâíîñòè ôóíêöèéϕj ), òî ïî òåîðåìå Âåéåðøòðàññà â ìíîæåñòâå X ñóùåñòâóþò òî÷êè, â êîòîðûõ öåëåâàÿôóíêöèÿ f (x) äîñòèãàåò ñâîèõ íàèìåíüøåãî è íàèáîëüøåãî çíà÷åíèé. Åñëè èñêîìàÿ òî÷êàÿâëÿåòñÿ âíóòðåííåé òî÷êîé ìíîæåñòâà X , òî â íåé ôóíêöèÿ èìååò ëîêàëüíûé ìàêñèìóìèëè ìèíèìóì, òàê ÷òî èíòåðåñóþùàÿ íàñ òî÷êà ñîäåðæèòñÿ ñðåäè ïîäîçðèòåëüíûõ òî÷åê,â êîòîðûõ ïðîèçâîäíàÿ ðàâíà íóëþ.
Îäíàêî ñâîåãî íàèáîëüøåãî (íàèìåíüøåãî) çíà÷åíèÿôóíêöèÿ f (x) ìîæåò äîñòèãàòü è íà ãðàíèöå ìíîæåñòâà X . Ïîýòîìó, äëÿ òîãî ÷òîáû íàéòèíàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) íà ìíîæåñòâå X , íóæíî íàéòè âñå ïîäîçðèòåëüíûå âíóòðåííèå òî÷êè, âû÷èñëèòü çíà÷åíèÿ öåëåâîé ôóíêöèè â íèõ è ñðàâíèòü ñîçíà÷åíèÿìè ôóíêöèè â ïîäîçðèòåëüíûõ ãðàíè÷íûõ òî÷êàõ ìíîæåñòâà X . Çàìåòèì, ÷òî ïðèïîèñêå ïîñëåäíèõ ïðèõîäèòñÿ ðàññìàòðèâàòü àíàëîãè÷íóþ çàäà÷ó.