1612726871-fd1970eb57207f2e4883f7549db906ce (Ларин, Плясунов - Примеры и задачи), страница 5

Âîîáùå ãîâîðÿ, íåîáõî0 + C 1 + . . . + C min(m,n) çàäà÷ ñ îãðàíè÷åíèÿìèðàâåíñòâàìè (èñïîëüçóÿäèìî ðåøèòü Cmmmìåòîä èñêëþ÷åíèÿ ïåðåìåííûõ èëè ìåòîä ìíîæèòåëåé Ëàãðàíæà). Êàæäàÿ èç íèõ èìååòâèä f (x) −→ extrx∈XI ãäå XI = {x | ϕj (x) = 0 (j ∈ I)} äëÿ íåêîòîðîãî ïîäìíîæåñòâàèíäåêñîâ I ⊂ {1, 2, . .

. , m}. Ïðè I = ∅ èìååì çàäà÷ó áåçóñëîâíîé îïòèìèçàöèè. Äëÿ ïîèñêà âñåõ ïîäîçðèòåëüíûõ òî÷åê íóæíî ïåðåáðàòü âñå ïîäìíîæåñòâà I ìîùíîñòè íå áîëåå n.Íàèáîëüøåå è íàèìåíüøåå èç çíà÷åíèé ôóíêöèè â íàéäåííûõ òî÷êàõ è áóäóò èñêîìûìèíàèáîëüøèì è íàèìåíüøèì çíà÷åíèÿìè ôóíêöèè f (x).Ê ñîæàëåíèþ, ÷èñëî ðàññìàòðèâàåìûõ ïîäçàäà÷ ìîæåò îêàçàòüñÿ î÷åíü áîëüøèì.

Ïîýòîìó ýòîò ìåòîä òðóäíî ïðèìåíÿòü â çàäà÷àõ áîëüøîé ðàçìåðíîñòè n ñ áîëüøèì ÷èñëîìîãðàíè÷åíèé m. Îäíàêî äëÿ çàäà÷ íåáîëüøîé ðàçìåðíîñòè òàêîé ïîäõîä ïðèìåíÿòü öåëåñîîáðàçíî, ïîñêîëüêó íå ñóùåñòâóåò äðóãîãî ýôôåêòèâíîãî ìåòîäà íàõîæäåíèÿ íàèìåíüøèõè íàèáîëüøèõ çíà÷åíèé öåëåâîé ôóíêöèè â çàäà÷å ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.Åñëè îáëàñòü X íå îãðàíè÷åíà, òî îáÿçàòåëüíî íàäî ðàññìàòðèâàòü ïîâåäåíèå öåëåâîéôóíêöèè ïðè óäàëåíèè òî÷åê ìíîæåñòâà â áåñêîíå÷íîñòü. Ýòà çàäà÷à â îáùåì ñëó÷àå òîæåñëîæíàÿ, íî èíîãäà å¼ óäà¼òñÿ ðåøèòü. Ïðè ýòîì åñëè óäà¼òñÿ îáíàðóæèòü òàêóþ êðèâóþxi = ψi (t) (i = 1, n), ÷òî x(t) ∈ X ïðè âñåõ t ≥ 0 è f (x(t)) → ±∞ ïðè t → +∞, òî öåëåâàÿôóíêöèÿ íåîãðàíè÷åíà ñâåðõó èëè ñíèçó.Ïðèìåð 1.

Íàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) = x21 − x1 x2 + x22íà ìíîæåñòâå X = {x | |x1 | + |x2 | ≤ 1}.Ðåøåíèå.  äàííîì ïðèìåðå ìíîæåñòâî X îãðàíè÷åíî. Âíóòðè ìíîæåñòâà X ïðîèçâîäíûå fx0 1 (x) = 2x1 −x2 è fx0 2 (x) = −x1 +2x2 îáðàùàþòñÿ â íóëü òîëüêî â òî÷êå (0, 0)> . Ãðàíèöàìíîæåñòâà X îïðåäåëÿåòñÿ ÷åòûðüìÿ îãðàíè÷åíèÿìèðàâåíñòâàìè: x1 + x2 = 1, −x1 + x2 =171, x1 − x2 = 1 è − x1 − x2 = 1. Òàê êàê ôóíêöèÿ f (x) ÷¼òíàÿ, òî äîñòàòî÷íî ðàññìîòðåòü òîëüêî ïåðâûå äâà èç íèõ. Ïðèìåíèì ìåòîä èñêëþ÷åíèÿ ïåðåìåííûõ.

Âäîëü ïðÿìîéx1 + x2 = 1 èìååì ôóíêöèþ îäíîãî ïåðåìåííîãî fe(x1 ) = f (x1 , 1 − x1 ) = 3x21 − 3x1 + 1,ïðîèçâîäíàÿ êîòîðîé fe0 (x1 ) = 6x1 − 3 îáðàùàåòñÿ â íóëü ïðè x1 = 1/2. Òîãäà x2 = 1/2, è ìûïîëó÷èëè òî÷êó (1/2, 1/2)> . Àíàëîãè÷íî, f (x1 , 1 + x1 ) = x21 + x1 + 1, è, ïðèðàâíÿâ íóëþ å¼ïðîèçâîäíóþ, ïîëó÷èì òî÷êó (−1/2, 1/2)> . Èç ÷¼òíîñòè ôóíêöèè f (x) ñëåäóåò, ÷òî òî÷êè(−1/2, −1/2)> è (1/2, −1/2)> òàêæå ÿâëÿþòñÿ ïîäîçðèòåëüíûìè.Òî÷êàìè ïåðåñå÷åíèÿ âñåõ ïàð ïðÿìûõ, îïðåäåëÿþùèõ ìíîæåñòâî X , î÷åâèäíî, áóäóòòî÷êè (0, 1)> , (0, −1)> , (1, 0)> è (−1, 0)> . Âñå îíè ïðèíàäëåæàò X .Âû÷èñëèì çíà÷åíèÿ öåëåâîé ôóíêöèè â íàéäåííûõ òî÷êàõ. Èìååì f (0, 0) = 0, f (1/2, 1/2) =f (−1/2, −1/2) = 1/4, f (−1/2, 1/2) = f (1/2, −1/2) = 3/4, f (1, 0) = f (−1, 0) = f (0, 1) =f (0, −1) = 1.

Òàêèì îáðàçîì, íàèìåíüøåå çíà÷åíèå ôóíêöèÿ f äîñòèãàåò â íà÷àëå êîîðäèíàò, à íàèáîëüøåå â âåðøèíàõ ìíîæåñòâà X .Ïðèìåð 2. Íàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) = x1 x22 + x21 x2 −23x1 − 3x22 íà ìíîæåñòâå X = {x | − x1 − x2 + 1 ≤ 0, x1 + x2 − 16 ≤ 0}.Ðåøåíèå.  äàííîì ïðèìåðå ìíîæåñòâî X íåîãðàíè÷åíî (ìîæíî çàïèñàòü îãðàíè÷åíèÿçàäà÷è â âèäå 1 ≤ x1 + x2 ≤ 16 è óáåäèòüñÿ, ÷òî X ïðåäñòàâëÿåò ñîáîé ïîëîñó, çàêëþ÷¼ííóþìåæäó äâóìÿ ïðÿìûìè).Ñíà÷àëà ðàññìîòðèì çàäà÷ó áåçóñëîâíîé îïòèìèçàöèè ôóíêöèè f (x).

Èìååì ñèñòåìóóðàâíåíèé½ 0fx1 = x22 + 2x1 x2 − 6x1 = 0,(14)fx0 2 = 2x1 x2 + x21 − 6x2 = 0.Âû÷òÿ îäíî ðàâåíñòâî èç äðóãîãî, ïîëó÷èì, ÷òî (x2 − x1 )(x1 + x2 + 6) = 0, ò. å. ëèáî x1 =x2 , ëèáî x1 + x2 = −6. Ïîñêîëüêó òî÷êè, óäîâëåòâîðÿþùèå âòîðîìó ðàâåíñòâó, ìíîæåñòâóX íå ïðèíàäëåæàò, òî x1 = x2 è èç ñèñòåìû (14) ñëåäóåò, ÷òî 3x21 − 6x1 = 0. Ïîëó÷àåì òî÷êèx1 = x2 = 0 è x1 = x2 = 2, èç êîòîðûõ òîëüêî âòîðàÿ ÿâëÿåòñÿ äîïóñòèìîé.Èññëåäóåì ïîâåäåíèå ôóíêöèè íà ãðàíèöå îáëàñòè X . Ôóíêöèÿ Ëàãðàíæà èìååò âèäF (x, y) = f (x) + y(x1 + x2 − t), ãäå t = 1 èëè t = 16. Ïîëó÷àåì ñèñòåìó óðàâíåíèé½ 0Fx1 = x22 + 2x1 x2 − 6x1 + y = 0,Fx0 2 = 2x1 x2 + x21 − 6x2 + y = 0.Ðåøàÿ å¼ àíàëîãè÷íî ñèñòåìå (1), ïîëó÷àåì, ÷òî x1 = x2 .

Òàêèì îáðàçîì, ïðè t = 1 èt = 16 èìååì ñîîòâåòñòâåííî òî÷êè (1/2, 1/2) è (8, 8).Ïîñêîëüêó ïðÿìûå x1 + x2 = 1 è x1 + x2 = 16 íå ïåðåñåêàþòñÿ, ìíîæåñòâî X íåèìååò âåðøèí. Ïîäñòàâëÿÿ íàéäåííûå çíà÷åíèÿ â öåëåâóþ ôóíêöèþ, ïîëó÷èì f (2, 2) =−8, f (1/2, 1/2) = −5/4, f (8, 8) = 640.Òàê êàê ìíîæåñòâî X íåîãðàíè÷åíî, íàäî èññëåäîâàòü ïîâåäåíèå ôóíêöèè f (x) íà áåñêîíå÷íîñòè.

Ðàññìîòðèì ñåìåéñòâî ïðÿìûõ x1 = t, x2 = s − t, ãäå t ∈ E1 è 1 ≤ s ≤ 16. ßñíî,÷òî ýòî ñåìåéñòâî ïðÿìûõ ïîêðûâàåò âñ¼ ìíîæåñòâî X . Òîãäà f (t, s − t) = −(s + 6)t2 + (s2 +6s)t − 3s2 . Ïîñêîëüêó −(s + 6) < 0 ïðè 1 ≤ s ≤ 16, òî f (t, s − t) → −∞ ïðè t → ∞. Òàêèìîáðàçîì, öåëåâàÿ ôóíêöèÿ íåîãðàíè÷åíà ñíèçó íà ìíîæåñòâå X , à å¼ ìàêñèìóì äîñòèãàåòñÿâ òî÷êå (8,8).Ïðèìåð 3. Íàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) = x1 x2 x3 íà ìíîæåñòâå X = {x ∈ E3 | x1 + x2 + x3 ≤ 6, x1 x2 + x2 x3 + x1 x3 ≤ 8}.Ðåøåíèå.

Ýòà ôóíêöèÿ èìååò ìíîãî ëîêàëüíûõ ýêñòðåìóìîâ, êîòîðûå ìîæíî íàéòèïîñëå äîëãèõ è óòîìèòåëüíûõ âû÷èñëåíèé ñ ïîìîùüþ ìåòîäà Ëàãðàíæà. Îäíàêî, åñëèçàìåòèòü, ÷òî ìíîæåñòâî X íåîãðàíè÷åíî, è ñðàçó ïðîàíàëèçèðîâàòü ïîâåäåíèå öåëåâîéôóíêöèè íà áåñêîíå÷íîñòè, ìîæíî ñóùåñòâåííî ñîêðàòèòü ñâîþ ðàáîòó.18Ðàññìîòðèì òî÷êè âèäà x1 (t) = 1, x2 (t) = 1, x3 (t) = −t.

Òîãäà îãðàíè÷åíèÿ çàäà÷èïðèìóò âèä −t ≤ 4 è −t ≤ 7/2. Ñëåäîâàòåëüíî, äëÿ ëþáîãî t ≥ 0 ýòè òî÷êè ÿâëÿþòñÿäîïóñòèìûìè. Ïðè ýòîì f (1, 1, −t) = −t → −∞ ïðè t → +∞. Çíà÷èò, öåëåâàÿ ôóíêöèÿíåîãðàíè÷åíà ñíèçó íà X .Ïóñòü òåïåðü x1 (t) = 1, x2 (t) = −1, x3 (t) = −t. Îãðàíè÷åíèÿ ïðèíèìàþò âèä −t ≤ 6 è−1 ≤ 8, ò. å. òî÷êè äîïóñòèìû ïðè t ≥ 0. Íî f (1, −1, −t) = t → +∞ ïðè t → +∞.Òàêèì îáðàçîì, öåëåâàÿ ôóíêöèÿ íåîãðàíè÷åíà íè ñíèçó, íè ñâåðõó íà ðàññìàòðèâàåìîììíîæåñòâå, è íåîáõîäèìîñòè â ïîèñêå ëîêàëüíûõ ýêñòðåìóìîâ (ïîäîçðèòåëüíûõ òî÷åê) íåò.Çàäà÷èÍàéòè íàèáîëüøåå è íàèìåíüøåå çíà÷åíèÿ ôóíêöèè f (x) íà ìíîæåñòâå X :1) f (x) = x1 x2 − x21 − 2x22 + x1 ,X = {x | x1 ∈ [0, 1], x2 ∈ [0, 1]};2) f (x) = x31 − 4x21 + 2x1 x2 − x22 ,X = {x | |x1 | ≤ 5, |x2 | ≤ 1};3) f (x) = x31 + x32 − 3x1 x2 ,X = {x | x1 ∈ [0, 2], x2 ∈ [−1, 2]};4) f (x) = (x1 − 5)2 + (x2 − 7)2 ,X = {x | x1 + 2x2 ≤ 12, x1 + x2 ≤ 9, x1 ≥ 0, x2 ≥ 0};5) f (x) = (x1 − 3)2 + (x2 − 5)2 ,X = {x | x21 + x22 ≤ 10, 2x1 + 2x2 = 5};6) f (x) = x1 (π − x1 ) sin x2 + x2 cos x1 ,X = {x | x1 ∈ [0, π], x2 ≥ 0};7) f (x) = x1 + x2 + x3 ,X = {x | x21 + x22 ≤ x3 , x3 ≤ 1};8) f (x) = 2x1 x2 + x3 ,X = {x | x21 + x22 = 1, 0 ≤ x3 ≤ 2x1 + 1};9) f (x) = x21 − x22 ,X = {x | x21 + x22 ≤ 16};10) f (x) = x21 + x22 − 12x1 + 16x2 ,X = {x | x21 + x22 ≤ 25};11) f (x) = arctg x1 − ln x2 ,X = {x | x21 + x22 ≤ 4, x1 ≥ 0, x2 ≥ 1};12) f (x) = x1 + x2 − x3 ,X = {x | x1 x2 x3 ≤ 1, −x1 + x2 − x3 ≤ 0};13) f (x) = x21 + x1 x2 + x22 + 3|x1 + x2 + 2|,X = E2 ;1914) f (x) = x21 + x22 + 2α|x1 + x2 − 1|, α > 0,X = E2 ;15) f (x) = x21 + x22 + 2 max{x1 , x2 },X = E2 .3.

Âûïóêëîå ïðîãðàììèðîâàíèå3.1. Âûïóêëûå ìíîæåñòâà è ôóíêöèè; êâàçèâûïóêëûå ôóíêöèèÏîèñê íàèáîëüøèõ è íàèìåíüøèõ çíà÷åíèé ôóíêöèè íà äîïóñòèìîì ìíîæåñòâå óïðîùàåòñÿ, åñëè îãðàíè÷èòüñÿ çàäà÷åé ìèíèìèçàöèè âûïóêëûõ ôóíêöèé íà âûïóêëûõ ìíîæåñòâàõ.Ìíîæåñòâî X ⊂ En íàçûâàåòñÿ âûïóêëûì åñëè äëÿ ëþáûõ x, y ∈ X è α ∈ [0, 1] èìååì,÷òî z = αx + (1 − α)y ∈ X , ò. å. âûïóêëîå ìíîæåñòâî âìåñòå ñ ëþáûìè äâóìÿ ñâîèìèòî÷êàìè äîëæíî ñîäåðæàòü è îòðåçîê, ñîåäèíÿþùèé ýòè äâå òî÷êè. Âûïóêëîé êîìáèíàöèåéòî÷åê x1 , x2 , .

. . , xm íàçûâàåòñÿ òî÷êà z = α1 x1 + α2 x2 + . . . + αm xm , ãäå âñå αi ≥ 0 èα1 + α2 + . . . + αm = 1.Òåîðåìà 1. Âûïóêëîå ìíîæåñòâî X ñîäåðæèò âûïóêëûå êîìáèíàöèè âñåõ ñâîèõ òî÷åê.Ôóíêöèÿ f (x), îïðåäåë¼ííàÿ íà âûïóêëîì ìíîæåñòâå X , íàçûâàåòñÿ âûïóêëîé, åñëè äëÿëþáûõ x, y ∈ X è α ∈ (0, 1) âûïîëíÿåòñÿ íåðàâåíñòâî f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y).Åñëè äëÿ ëþáûõ ðàçëè÷íûõ x è y óêàçàííîå íåðàâåíñòâî ÿâëÿåòñÿ ñòðîãèì, òî ôóíêöèÿíàçûâàåòñÿ ñòðîãî âûïóêëîé. Ôóíêöèÿ f (x) íàçûâàåòñÿ (ñòðîãî) âîãíóòîé, åñëè ôóíêöèÿ−f (x) (ñòðîãî) âûïóêëà.Âûïóêëûå ôóíêöèè îáëàäàþò ñëåäóþùèìè ñâîéñòâàìè.Òåîðåìà 2.

Âûïóêëàÿ ôóíêöèÿ f (x), îïðåäåë¼ííàÿ íà âûïóêëîì ìíîæåñòâå X , íåïðåðûâíà â êàæäîé âíóòðåííåé òî÷êå ýòîãî ìíîæåñòâà.Òåîðåìà 3. Ôóíêöèÿ f (x), äèôôåðåíöèðóåìàÿ íà âûïóêëîì ìíîæåñòâå X , âûïóêëàòîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáûõ x, y ∈ X áóäåò hf 0 (x), y − xi ≤ f (y) − f (x).Òåîðåìà 4. Ôóíêöèÿ f (x), îïðåäåë¼ííàÿ è äâàæäû íåïðåðûâíî äèôôåðåíöèðóåìàÿ íàâûïóêëîì´ ìíîæåñòâå X , (ñòðîãî) âûïóêëà òîãäà è òîëüêî òîãäà, êîãäà ìàòðèöà B(x) =³ 2∂ f (x)(ñòðîãî) ïîëîæèòåëüíî îïðåäåëåíà äëÿ ëþáîãî x ∈ X .∂xi ∂xji,j=1,nÒåîðåìà 5. Äëÿ ëþáîé âûïóêëîé ôóíêöèè f (x), îïðåäåë¼ííîé íà âûïóêëîì ìíîæåñòâåX , è ëþáîãî ÷èñëà λ ìíîæåñòâî {x ∈ X | f (x) ≤ λ} âûïóêëî.Òåîðåìà 6 (íåðàâåíñòâî Éåíñåíà).