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

ÊÎÍÅÖ.Åñëè σ k < 0, òî ïîëàãàåì δk+1 = δk /2, pk = pk .Øàã 2. Îïðåäåëèòü âåëè÷èíó øàãà αk (â íàïðàâëåíèè pk ).Ïóñòü αkj íàèìåíüøèé ïîëîæèòåëüíûé êîðåíü óðàâíåíèÿϕj (xk + αpk ) = 0.Îí ìîæåò áûòü íàéäåí, íàïðèìåð, ìåòîäîì äèõîòîìèè. Ïîëàãàåìαk = min{αkj | 1 ≤ j ≤ m }.Øàã 3. Îïðåäåëèòüxk+1 = xk + αk pk ,J(xk+1 , δk+1 ) = {j| − δk+1 < ϕj (xk+1 ) ≤ 0 },I(xk+1 ) = {j| ϕj (xk+1 ) = 0 }.Øàã 4. Åñëè âûïîëíåíû óñëîâèÿ îêîí÷àíèÿ ïðîöåññà âû÷èñëåíèé, òî ÊÎÍÅÖ, èíà÷åïîëàãàåì k := k + 1 è ïåðåõîäèì íà øàã 1. äàííîì îïèñàíèè àëãîðèòìà íå êîíêðåòèçèðóþòñÿ óñëîâèÿ îêîí÷àíèÿ âû÷èñëåíèé,òàê êàê îíè ìîãóò ñóùåñòâåííî çàâèñåòü îò ðàññìàòðèâàåìîé çàäà÷è.Òåîðåìà 2.

Ïóñòü ϕj (x) (j = 1, m) ãëàäêèå âûïóêëûå ôóíêöèè, âûïîëíåíî óñëîâèåÑëåéòåðà è ìíîæåñòâî X îãðàíè÷åíî. Òîãäà:1) ïîñëåäîâàòåëüíîñòü {f (xk )} ñõîäèòñÿ ê âåëè÷èíå f ∗ = minx∈X f (x), ò. å.f (xk ) =< c, xk >→ f ∗ ïðè k → ∞;2) ëþáàÿ ïðåäåëüíàÿ òî÷êà x∗ ïîñëåäîâàòåëüíîñòè {xk } åñòü òî÷êà ìèíèìóìà ôóíêöèèf (x) íà ìíîæåñòâå äîïóñòèìûõ ðåøåíèé X .Ê îïèñàííîìó ìåòîäó ðåøåíèÿ ìîæíî ñäåëàòü ñëåäóþùèå çàìå÷àíèÿ:1.

Åñëè íåîáõîäèìî íàéòè íà÷àëüíóþ òî÷êó x0 ∈ X , òî íà ïåðâîì ýòàïå ðåøàåòñÿ âñïîìîãàòåëüíàÿ çàäà÷à âûïóêëîãî ïðîãðàììèðîâàíèÿξ → minïðè îãðàíè÷åíèÿõϕj (x) ≤ ξ(j = 1, m).Ýòó çàäà÷ó ìîæíî ðåøàòü ìåòîäîì âîçìîæíûõ íàïðàâëåíèé, âçÿâ â êà÷åñòâå èñõîäíîé ëþáóþ òî÷êó (ξ 0 , x0 ) òàêóþ, ÷òî x0 ∈ En , ξ 0 ≥ max1≤j≤m ϕj (x0 ).

Ïðè âûïîëíåíèè óñëîâèÿÑëåéòåðà ÷åðåç êîíå÷íîå ÷èñëî øàãîâ ïîëó÷èì ξk ≤ 0, ÷åìó ñîîòâåòñòâóåò äîïóñòèìàÿ íà÷àëüíàÿ òî÷êà x0 := xk äëÿ çàäà÷è (1)(2).68Ïîñëå ýòîãî ïåðåõîäèì êî âòîðîìó ýòàïó: ïîèñêó îïòèìàëüíîãî ðåøåíèÿ îñíîâíîé çàäà÷è(1)(2).2. Íà øàãå 4 èòåðàöèè ìåòîäà âîçìîæíûõ íàïðàâëåíèé â êà÷åñòâå êðèòåðèÿ îñòàíîâêèìîæíî âçÿòü îöåíêó îòêëîíåíèÿ ïî öåëåâîé ôóíêöèè| min < c, x > − < c, xk > | ≤ | min < c, x > − < c, xk > |,x∈Xx∈Xkò. å.

íà k -é èòåðàöèè íåîáõîäèìî ðåøèòü çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ< c, x >→ min ,x∈XkXk = {x| ϕj (xk )+ < ϕ0j (xk ), x − xk >≤ 0 (j = 1, m) }.Âû÷èñëåíèÿ ïðåêðàùàþòñÿ, åñëè ïðàâàÿ ÷àñòü âåðõíåãî íåðàâåíñòâà ñòàíåò ìåíüøå çàäàííîé âåëè÷èíû.3. Óñëîâèÿ íîðìèðîâêè âåêòîðà íàïðàâëåíèÿ p â çàäà÷àõ A è B íåîáõîäèìû äëÿ òîãî,÷òîáû îáåñïå÷èòü ñóùåñòâîâàíèå êîíå÷íîãî ðåøåíèÿ. Åñëè ñóùåñòâîâàíèå òàêîãî ðåøåíèÿñëåäóåò â êîíêðåòíîé çàäà÷å èç êàêèõ-òî äðóãèõ ñîîáðàæåíèé, òî íåêîòîðûå èç îãðàíè÷åíèé|pi | ≤ 1 (i = 1, n)ìîæíî óáðàòü, ÷òî, åñòåñòâåííî, óïðîñòèò ðåøàåìóþ çàäà÷ó.Èç ïðèâåä¼ííîãî íèæå ïðèìåðà âèäíî, ÷òî ìåòîä âîçìîæíûõ íàïðàâëåíèé äàæå äëÿñðàâíèòåëüíî ïðîñòûõ çàäà÷ òðåáóåò áîëüøîãî îáú¼ìà âû÷èñëåíèé.

Ïîýòîìó ýòîò ìåòîäíå ðàññìàòðèâàåòñÿ íà ñåìèíàðñêèõ çàíÿòèÿõ, õîòÿ â òåîðåòè÷åñêîì êóðñå îí èçëàãàåòñÿïîëíîñòüþ. Ìû ïîñ÷èòàëè íåîáõîäèìûì ïðèâåñòè õîòÿ áû îäèí èëëþñòðàòèâíûé ïðèìåðâ äàííîì ó÷åáíîì ïîñîáèè, òàê êàê íà í¼ì õîðîøî âèäíû îáùèå îñîáåííîñòè ÷èñëåííûõìåòîäîâ ðåøåíèÿ çàäà÷ âûïóêëîãî ïðîãðàììèðîâàíèÿ.Ïðèìåð. Ðåøèòü ìåòîäîì âîçìîæíûõ íàïðàâëåíèé çàäà÷óz(x) = x3 → minx1 ,x2 ,x3ïðè îãðàíè÷åíèÿõϕ1 (x) ≡ x21 + 2x1 x2 + 2x22 − 2x1 − x2 − x3 − 2 ≤ 0,ϕ2 (x) ≡ x21 + x22 − x1 + x2 − x3 − 3 ≤ 0,ϕ3 (x) ≡ x21 + x1 − 4x2 − x3 + 3 ≤ 0,âçÿâ â êà÷åñòâå íà÷àëüíîé òî÷êó x0 = (1, −1, 9)> .Ðåøåíèå.

Âîçüì¼ì δ0 = 0.5. Òîãäà J(x0 , δ0 ) = I(x0 ) = {3}, òàê êàê ϕ1 (x0 ) = −11 <−δ0 , ϕ2 (x0 ) = −12 < −δ0 , ϕ3 (x0 ) = 0 > −δ0 .Ïåðâàÿ èòåðàöèÿ. 1. Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,<ϕ03 (x0 ), p> −σ ≡ 3p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Òàê êàê â çàäà÷àõ A è B íà êàæäîé èòåðàöèè ïåðâîå îãðàíè÷åíèå < c, p >≤ σ âñåãäà áóäåòèìåòü âèä p3 ≤ σ , à îïòèìàëüíîå ðåøåíèå òàêîâî, ÷òî σk ≤ 0, òî â ëþáîé òî÷êå xk èìååì69íåðàâåíñòâî pk3 ≤ 0.

 ñèëó âòîðîãî îãðàíè÷åíèÿ p3 ≥ −σ + 3p1 − 4p2 . Ïðàâàÿ ÷àñòü çäåñü,î÷åâèäíî, îãðàíè÷åíà ñíèçó. Òàêèì îáðàçîì, êîìïîíåíòà p3 îãðàíè÷åíà â ñèëó èìåþùèõñÿîãðàíè÷åíèé. Ýòî ñïðàâåäëèâî äëÿ âñåõ ðàññìàòðèâàåìûõ äàëåå çàäà÷ A è B . Ïîýòîìóîãðàíè÷åíèå |p3 | ≤ 1 ìîæíî óáðàòü.Ðåøèâ óïðîù¼ííóþ çàäà÷ó A, ïîëó÷èì p0 = (−1, 1, −3.5)> , σ0 = −3.5. Òàê êàê σ0 < −δ0 ,òî ïîëàãàåì δ1 = δ0 = 0.5.2. Îïðåäåëåíèå âåëè÷èíû øàãà α0 .Äâèãàòüñÿ ñëåäóåò âäîëü ëó÷àx1 = 1 − α, x2 = −1 + α, x3 = 9 − 3.5α (α > 0).Íàèìåíüøèì èç ïîëîæèòåëüíûõ êîðíåé óðàâíåíèéϕj (x0 + αp0 ) = 0 (j = 1, 2, 3)ÿâëÿåòñÿ α0 = 2.1, ïðè ýòîì ϕ2 (x0 + α0 p0 ) ≈ 0.3. Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ.Íîâîå ïðèáëèæåíèå x1 îïðåäåëÿåòñÿ ïî ôîðìóëåx1 = x0 + α0 p0 = (−1.1, 1.1, 1.65)> ,ïðè ýòîì ϕ1 (x1 ) = −1.34 < −δ1 , −δ1 < ϕ2 (x1 ) = −0.03, ϕ3 (x1 ) = −2.94 < −δ1 . Çíà÷èò,J(x1 , δ1 ) = {2}.Çàìåòèì, ÷òî çäåñü max1≤j≤3 ϕj (x1 ) = −0.03 6= 0, íî áîëüøå −δ1 .

Ïàðàìåòð δ ââåä¼íèìåííî äëÿ òîãî, ÷òîáû íå òðåáîâàëîñü íàõîäèòü òî÷íîå çíà÷åíèå êîðíÿ α. Ïðè ìàëûõçíà÷åíèÿõ δk äîñòàòî÷íî íàéòè òàêîå αkj > 0, ÷òî −δk < ϕj (xk + αkj pk ) ≤ 0, è âûáðàòüìèíèìàëüíîå èç íèõ ïî j . Êîíå÷íî, ÷åì òî÷íåå áóäóò íàõîäèòüñÿ êîðíè, òåì, âîîáùå ãîâîðÿ,ëó÷øå.Âòîðàÿ èòåðàöèÿ. 1. Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ02 (x1 ), p > −σ ≡ −3.2p1 + 3.2p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ðåøèâ ýòó çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ, ïîëó÷èì p1 = (1, −1, −3.2)> , σ1 = −3.2.Òàê êàê σ1 < −δ1 , òî δ2 = δ1 = 0.5.2. Îïðåäåëåíèå âåëè÷èíû øàãà α1 .

Äâèãàåìñÿ âäîëü ëó÷àx1 = −1.1 + α, x2 = −1.1 − α, x3 = 1.65 − 3.2α (α > 0).Íàèìåíüøèì èç ïîëîæèòåëüíûõ êîðíåé óðàâíåíèéϕj (x1 + αp1 ) = 0 (j = 1, 2, 3)ÿâëÿåòñÿ α1 = 0.45, ïðè ýòîì ϕ3 (x1 + α1 p1 ) ≈ 0.3. Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ.Íîâîå ïðèáëèæåíèå x2 îïðåäåëÿåòñÿ ïî ôîðìóëåx2 = x1 + α1 p1 = (−0.65, 0.65, 0.21)> .Òàê êàê ϕ1 (x2 ) = −1.14 < −δ2 , ϕ2 (x2 ) = −1.07 < −δ2 , −δ2 < ϕ3 (x2 ) = −0.04 < 0, òîJ(x2 , δ2 ) = {3}.70Òðåòüÿ èòåðàöèÿ. 1. Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ03 (x2 ), p > −σ ≡ −0.3p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ðåøèâ, ïîëó÷èì p2 = (1, 1, −2.15)> , σ2 = −2.15 < −δ2 , δ3 = δ2 = 0.5.2.

Êàê è âûøå, îïðåäåëèì âåëè÷èíó øàãà α2 : α2 = 0.36, ïðè ýòîì ϕ2 (x2 + α2 p2 ) ≈ 0.3. Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ:x3 = x2 + α2 p2 = (−0.29, 1.01, −0.57)> , J(x3 , δ3 ) = {1, 2},òàê êàê ϕ1 (x3 ) = −0.32 > −δ3 , ϕ2 (x3 ) = −0.03 > −δ3 , ϕ3 (x3 ) = −0.68 < −δ3 .×åòâ¼ðòàÿ èòåðàöèÿ. 1.

Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ01 (x3 ), p > −σ ≡ −0.56p1 + 2.46p2 − p3 − σ ≤ 0,< ϕ02 (x3 ), p > −σ ≡ −1.58p1 + 3.02p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ðåøèâ, ïîëó÷èì p3 = (1, −1, −1.51)> , σ3 = −1.51 < −δ3 . Çíà÷èò, îïÿòü δ4 = δ3 = 0.5.2. Êàê è âûøå, îïðåäåëèì âåëè÷èíó øàãà α3 : α3 = 0.12, ïðè ýòîì ϕ3 (x3 + α3 p3 ) = 0(âû÷èñëåíèÿ ïðîâîäèì ñ òî÷íîñòüþ äî 0.01).3.

Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ:x4 = x3 + α3 p3 = (−0.17, 0.89, −0.75)> , J(x4 , δ4 ) = {1, 2, 3},òàê êàê ϕ1 (x4 ) = −0.49 > −δ4 , ϕ2 (x4 ) = −0.37 > −δ4 , ϕ3 (x4 ) = 0.Ïÿòàÿ èòåðàöèÿ. 1. Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ01 (x4 ), p > −σ ≡ −0.56p1 + 2.22p2 − p3 − σ ≤ 0,< ϕ02 (x4 ), p > −σ ≡ −1.34p1 + 2.78p2 − p3 − σ ≤ 0,< ϕ03 (x4 ), p > −σ ≡ 0.66p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ðåøèâ ýòó çàäà÷ó, ïîëó÷èì, ÷òî σ4 = 0. Çíà÷èò, íåîáõîäèìî ðåøèòü çàäà÷ó B . Òàê êàêI(x4 ) = {3}, òî ðåøàåì çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ03 (x4 ), p > −σ ≡ 0.66p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.71Ïîëó÷èì p4 = (−1, 1, −2.33)> , ïðè ýòîì σ 4 = −2.33 < 0.

Ñëåäîâàòåëüíî, δ5 = δ4 /2 =0.25, p4 = p4 .2. Îïðåäåëåíèå øàãà α4 . Äâèãàåìñÿ âäîëü ëó÷àx1 = −0.17 − α, x2 = 0.89 + α, x3 = −0.75 − 2.33α (α > 0).Íàèìåíüøèì èç ïîëîæèòåëüíûõ êîðíåé óðàâíåíèéϕj (x4 + αp4 ) = 0 (j = 1, 2, 3)ÿâëÿåòñÿ α1 = 0.06, ïðè ýòîì ϕ2 (x4 + α4 p4 ) = 0.3. Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ:x5 = x4 + α4 p4 = (−0.23, 0.95, −0.88)> , J(x5 , δ5 ) = {1, 2, 3},òàê êàê ϕ1 (x5 ) = −0.19 > −δ5 , ϕ2 (x5 ) = 0 > −δ5 , ϕ3 (x5 ) = −0.1 > −δ5 .Øåñòàÿ èòåðàöèÿ. 1.

Ðåøàåì çàäà÷ó A:σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,<ϕ01 (x5 ), p> −σ ≡ −0.56p1 + 2.34p2 − p3 − σ ≤ 0,<ϕ02 (x5 ), p> −σ ≡ −1.46p1 + 2.90p2 − p3 − σ ≤ 0,< ϕ03 (x5 ), p > −σ ≡ −0.54p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ðåøèâ, ïîëó÷èì p5 = (1, 0.18, −0.08)> , σ5 = −0.08 > −δ5 . Çíà÷èò, îïÿòü ïðîèñõîäèòóìåíüøåíèå ïàðàìåòðà δ : δ6 = δ5 /2 = 0.125.2. Îïðåäåëåíèå âåëè÷èíû øàãà α5 :Äâèãàåìñÿ âäîëü ëó÷àx1 = −0.23 + α, x2 = 0.95 + 0.18α, x3 = −0.88 − 0.08α (α > 0).Íàèìåíüøèì èç ïîëîæèòåëüíûõ êîðíåé óðàâíåíèéϕj (x5 + αp5 ) = 0 (j = 1, 2, 3)ÿâëÿåòñÿ α5 = 0.34, ïðè ýòîì ϕ3 (x5 + α5 p5 ) = 0.3.

Îïðåäåëåíèå íîâîé òî÷êè è ìíîæåñòâ èíäåêñîâ:x6 = x5 + α5 p5 = (0.11, 1.01, −0.91)> , J(x6 , δ6 ) = {1, 3},òàê êàê ϕ1 (x6 ) = −0.05 > −δ5 , ϕ2 (x6 ) = −0.16 < −δ5 , ϕ3 (x6 ) = 0 > −δ5 .Ñåäüìàÿ èòåðàöèÿ. Ïîñëåäîâàòåëüíî, êàê è âûøå, íàõîäèì p6 = (−1, −0.15, −0.26)> ,δ7 = δ6 = 0.125, α6 = 0.2, x7 = (−0.09, 0.98, −0.96)> .Âîñüìàÿ èòåðàöèÿ. Íàõîäèì p7 = (0.3, −0.03, −0.18)> , δ8 = δ7 = 0.125, α7 = 0.09,8x = (−0.06, 0.98, −0.98)> .Ïðèìåíåíèå êðèòåðèÿ îïòèìàëüíîñòè ðåøåíèÿ.

Ðàññìîòðèì òî÷êó x∗ = (0, 1, −1)> ,ê êîòîðîé, âèäèìî, ñõîäèòñÿ ïîñëåäîâàòåëüíîñòü òî÷åê {xk }. Èìååì ðàâåíñòâàϕ1 (x∗ ) = 0,ϕ2 (x∗ ) = 0,ò. å. òî÷êà x∗ ïðèíàäëåæèò âñåì ïîâåðõíîñòÿì.72ϕ3 (x∗ ) = 0,Ðåøèì â ýòîé òî÷êå çàäà÷ó B :σ → min,< c, p > −σ ≡ p3 − σ ≤ 0,< ϕ01 (x∗ ), p > −σ ≡ 3p2 − p3 − σ ≤ 0,< ϕ02 (x∗ ), p > −σ ≡ −p1 + 3p2 − p3 − σ ≤ 0,< ϕ03 (x∗ ), p > −σ ≡ p1 − 4p2 − p3 − σ ≤ 0,−p1 − 1 ≤ 0, p1 − 1 ≤ 0, −p2 − 1 ≤ 0, p2 − 1 ≤ 0.Ïîëó÷èì minσ,p σ = σ ∗ = 0.

 ñèëó êðèòåðèÿ îïòèìàëüíîñòè òî÷êà x∗ ÿâëÿåòñÿ ðåøåíèåìçàäà÷è.73Áèáëèîãðàôè÷åñêèé ñïèñîêÊàðìàíîâ Â. Ã. Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå. Ì.: Íàóêà, 1986.Ôèõòåíãîëüö Ã. Ì. Êóðñ äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ. Ì.; Ë.:Ãîñ. èçäâî ôèç.ìàò. ëèò., 1958. Ò. 1.Äåìèäîâè÷ Á. Ï. Ñáîðíèê çàäà÷ è óïðàæíåíèé ïî ìàòåìàòè÷åñêîìó àíàëèçó. Ì.:Íàóêà, 1972.Êàïóñòèí Â. Ô.

Ïðàêòè÷åñêèå çàíÿòèå ïî êóðñó ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.Ë.: ËÃÓ, 1976.Çàñëàâñêèé Þ. Ë. Ñáîðíèê çàäà÷ ïî ëèíåéíîìó ïðîãðàììèðîâàíèþ. Ì.: Íàóêà, 1969.Ãëåáîâ Í. È. è äð. Ìåòîäû îïòèìèçàöèè. Ó÷åá. ïîñîáèå / Í. È. Ãëåáîâ, Þ. À. Êî÷åòîâ,À. Â.

Ïëÿñóíîâ. Íîâîñèáèðñê: ÍÃÓ, 2000.74.