Методы оптимизации. Конспект лекций (Буряков) (2010), страница 8

Òàê êàê J(u) âûïóêëà,J(u) J(ukm ) → J(u) = J∗ ïðè m → ∞, òî åñòü áàçèñ ñëåäóåò, ÷òîà â ñèëó íåïðåðûâíîñòèòîlim J(uk ) = J∗ ,k→∞è ñõîäèìîñòü ïî ôóíêöèè äîêàçàíà.Ñõîäèìîñòü æå ïî àðãóìåíòó âûòåêàåò íåïîñðåäñòâåííî èç Òåîðåìû 1.Ðàññìîòðèì ïðèìåð, êîãäà ïåðâàÿ ïðîèçâîäíàÿ ôóíêöèèJ(u)íå ñóùåñòâóåò, âñëåä-ñòâèå ÷åãî äàííûé ìåòîä íå ñõîäèòñÿ.2Âîçüì¼ì â ïðîñòðàíñòâå R ôóíêöèþJ(u) = (x − 1)2 + (y − 1)2 + 2|x − y| − 2. Ýòàôóíêöèÿ ñèëüíî âûïóêëà, íåïðåðûâíà, íî íå äèôôåðåíöèðóåìà ïðè x = y.

Ëåãêî âèäåòü,÷òî U∗ = {(1, 1)}, J∗ = −2. Åñëè ñòàðòîâàòü èç òî÷êè u0 = (0, 0), òî ïîëó÷èì, ÷òî âñåuk = u0 = (0, 0), òî åñòü ïðè áàçèñå p1 = (1, 0), p2 = (0, 1), J(u0 +αpi ) = α2 −2α+2|α| > 0 âñå øàãè íåóäà÷íûå.Çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ýòîì ïóíêòå ìû ðàññìîòðèì çàäà÷ó ìèíèìèçàöèè ôóíêöèîíàëànnáåðòîâîì ïðîñòðàíñòâå H = R , ãäå c ôèêñèðîâàíî èç R .J(u) = hc, uiâ ãèëü-Îáùàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ ðàññìàòðèâàåòñÿ íà ìíîæåñòâåU = {u ∈ Rn | hai , ui = bi , hai , ui 6 bj ,i = 1, m, j = 1, s}(1)Åñëè ââåñòè ðÿä îáîçíà÷åíèé:a1 a2 A= ··· ,amòî ìíîæåñòâîUa1 a2 A= ··· ,asb1 b2 b= ··· ,bmb1 b2 b= ··· ,bsìîæíî îïèñàòü â áîëåå êîìïàêòíîé ìàòðè÷íîé ôîðìå:U = {u ∈ Rn |Au = b, Au 6 b}.Íàðÿäó ñ îáùåé çàäà÷åé(1)ìû áóäåì ðàññìàòðèâàòüêàíîíè÷åñêóþçàäà÷ó ëèíåéíîãîïðîãðàììèðîâàíèÿ íà ìíîæåñòâåU = {u ∈ Rn |Au = b, u > 0}.Çàìåòèì, ÷òî çàäà÷à(1)ñâîäèòñÿ ê çàäà÷åwi = max{0, ui } > 0,(2).Äåéñòâèòåëüíî, ïîëîæèì âvi = max{0, −ui } > 0,51(2)y = b − Au > 0.(1)Òîãäà ìîæíî ðàññìîòðåòü çàäà÷ó(2)îòíîñèòåëüíî íîâîé ïåðåìåííîéz:z = (y, v, w) ∈ R2n+s , z > 0J(u) = hc, ui = hc, w − vià îãðàíè÷åíèÿ çàäàþòñÿ ðàâåíñòâîìÎïðåäåëåíèå.Òî÷êàv ëèíåéíà ïîz(íå çàâèñèò îòy ),A(w − v) = b.U íàçûâàåòñÿ óãëîâîé òî÷êîé ýòîãîv = αx + (1 − α)y, ãäå x, y ∈ U, α ∈ (0, 1), ñëåäóåò, ÷òîâûïóêëîãî ìíîæåñòâàìíîæåñòâà, åñëè èç ñîîòíîøåíèÿv = x = y.U).

Ïóñòü ìàòðèöà A =(A1 |A2 |· · ·|An ) (ðàñïèñàíî ïî ñòîëáöàì). Òî÷êà v ÿâëÿåòñÿ óãëîâîé òî÷êîé êàíîíè÷åñêîãî ìíîæåñòâà U òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò íàáîð ñòîëáöîâ Aj1 , Aj2 , . . . , Ajr(j1 < j2 < · · · < jr ), r = rank A, ïðè÷¼ìÒåîðåìà 22 (êðèòåðèé óãëîâîé òî÷êè äëÿ êàíîíè÷åñêîãîAj1 vj1 + Aj2 vj2 + · · · + Ajr vjr = b,(3)/ Jb = {j1 , j2 , . . . , jr } vj = 0.ãäå vji > 0 (i = 1, r), à ∀j ∈Äîêàçàòåëüñòâî.Íåîáõîäèìîñòü.Ïóñòü òî÷êàvÿâëÿåòñÿ óãëîâîé äëÿ ìíîæåñòâàëþáûå áàçèñíûå ñòîëáöû ìàòðèöûA.U.v = 0, òî â (3) ìîæíîêîãäà v 6= 0.

ÏóñòüÅñëèÐàññìîòðèì ñëó÷àé,âçÿòüvj1 > 0, vj2 > 0, . . . , vjk > 0,à îñòàëüíûåvj = 0.Ïîêàæåì, ÷òî ñòîëáöûAj1 , Aj2 , . . . , Ajkëèíåéíî íåçàâèñèìû. Íåîáõîäèìî äîêàçàòü,÷òî ðàâåíñòâîγj1 Aj1 + γj2 Aj2 + · · · + γjk Ajk = 0(∗)âûïîëíÿåòñÿ òîëüêî òîãäà, êîãäàγj1 = γj2 = · · · = γjk = 0.γ = (γ1 , .

. . , γn ) òàê, ÷òî γj = γji , åñëè j = ji , è γj = 0, åñëè j 6= ji íè äëÿ(∗) âûïîëíÿåòñÿ òîãäà è òîëüêî òîãäà, êîãäà Aγ = 0.Ðàññìîòðèì òî÷êó v±ε = v ±εγ. Äëÿ äîñòàòî÷íî ìàëûõ ε > 0 áóäåò âûïîëíåíî v±ε > 0v+ε+ v−ε,è Av±ε = Av ± εAγ = Av = b. Îòñþäà ñëåäóåò, ÷òî v±ε ∈ U.  òî æå âðåìÿ v =22à òàê êàê v óãëîâàÿ òî÷êà, òî v+ε = v−ε = v. Íî ε 6= 0 è, çíà÷èò, γ = 0, òî åñòüAj1 , Aj2 , . . . , Ajk ëèíåéíî íåçàâèñèìû.Òåïåðü äîñòàòî÷íî çàìåòèòü, ÷òî (3) âûïîëíÿåòñÿ ïîñëå äîïîëíåíèÿ Aj1 , Aj2 , .

. . , Ajkäî áàçèñíîãî íàáîðà â ñëó÷àå, êîãäà k < r. Íåîáõîäèìîñòü äîêàçàíà.Ââåä¼ì âåêòîðêàêîãîi.ÐàâåíñòâîÄîñòàòî÷íîñòü.Ïóñòü äëÿ òî÷êèvâûïîëíåíû óñëîâèÿ(3).Çíà÷èò,v > 0, Av = b,Òðåáóåòñÿ äîêàçàòü, ÷òî èç óñëîâèÿv = αx + (1 − α)y,α ∈ (0, 1), x, y ∈ U52òî åñòüv ∈ U.v = x = y.vj = 0 = αxj + (1 − α)yj , òî vj = xj = yj = 0, òàê êàê α > 0, à xj > 0 è yj > 0.Âûäåëèì âñå vj1 > 0, .

. . , vjk > 0 (îñòàëüíûå êîîðäèíàòû ðàâíû íóëþ). Òîãäà, òàê êàêv, x, y ∈ U, òî Aj1 vj1 + Aj2 vj2 + · · · + Ajk vjk = bAj xj + Aj2 xj2 + · · · + Ajk xjk = b 1 1Aj1 yj1 + Aj2 yj2 + · · · + Ajk yjk = bñëåäóåò, ÷òîÅñëèAj1 , Aj2 , . . . , Ajk ëèíåéíî íåçàâèñèìû, ïîëó÷àåì, ÷òî vji = xji = yji > 0i = 1, k. Òåîðåìà äîêàçàíà.Ó÷èòûâàÿ, ÷òîäëÿ ëþáîãîÎïðåäåëåíèå.äåííîé,Óãëîâàÿ òî÷êàvåñëè ñóùåñòâóåò òàêîé íàáîðíàçûâàþòñÿáàçèñíûìèäëÿ òî÷êèJb ,÷òîvj > 0Îïðåäåëåíèå.(2) áàçèñU âñå óãëîâûåíåâûðîæäåííîé.Åñëè ó ìíîæåñòâàíàçûâàåòñÿÓïðàæíåíèå 17 (3).äëÿ âñåõv:B = (Aj1 |Aj2 | .

. . |Ajr )ìèíèìèçàöèèU íàçûâàåòñÿ íåâûðîæj ∈ Jb . Ýòè êîîðäèíàòû (j )êàíîíè÷åñêîãî ìíîæåñòâàv.òî÷êè íåâûðîæäåííûå, òî çàäà÷àÏóñòüU = {u ∈ R4 | u > 0, Au = b}, 31 1 3 1A=, b=.1 −1 1 21Íàéòè âñå óãëîâûå òî÷êèUè èññëåäîâàòü èõ íà íåâûðîæäåííîñòü.Ñèìïëåêñ-ìåòîäÇäåñü ìû ïðèìåíèì àïïàðàò óãëîâûõ òî÷åê äëÿ ðàññìîòðåíèÿ îïòèìèçàöèîííîé çàäà÷èñëåäóþùåãî âèäà:J(u) = hc, ui → infu ∈ U = {u > 0, Au = b}Èäåÿ ìåòîäà ëåæèò â ïåðåáîðå ëèøü òîëüêî óãëîâûõ òî÷åê ìíîæåñòâà(1)U.×àñòî ýòîïîçâîëÿåò íàéòè îïòèìàëüíîå ðåøåíèå áûñòðåå ðàññìîòðåííûõ âûøå ìåòîäîâ. Ïåðåéäåìê îïèñàíèþ ñèìïëåêñ-ìåòîäà.Ïóñòü èìååòñÿ óãëîâàÿ òî÷êàvìíîæåñòâàU(êàêèì îáðàçîì îíà íàõîäèòñÿ, íàìñåé÷àñ íå âàæíî).

Áóäåì ñ÷èòàòü òàêæå, ÷òî èç ìàòðèöûAâûêèíóòû âñå ëèíåéíî çà-r = rank A = m.Íàõîäÿñü â óñëîâèÿõ Òåîðåìû 19, ìîæíî çàïèñàòü, ÷òî vb = (vj1 , . . . , vjr ) áàçèñíûåäëÿ v, vjr > 0, à îñòàëüíûå vj ðàâíû íóëþ. Îáîçíà÷èì ÷åðåç Jb ìíîæåñòâî {j1 , . . . , jr },à ÷åðåç Jf ìíîæåñòâî {1, . . .

, n}\Jb . Ïóñòü äàëåå äëÿ ñîîòâåòñòâóþùèõ Aji ìàòðèöàB = (Aj1 |Aj2 |· · ·|Ajr ), à îñòàëüíûå ñòîëáöû ìàòðèöû A îáðàçóþ íåêóþ ìàòðèöó Fr×(n−r) .−1Ïî îïðåäåëåíèþ B è Òåîðåìå 19 det B 6= 0, è ñóùåñòâóåò îáðàòíàÿ ìàòðèöà B.Ðàçîáü¼ì âåêòîð u = (u1 , . . .

, un ) íà áàçèñíûå ïåðåìåííûå ub = (uj1 , . . . , ujn ) è íàñâîáîäíûå ïåðåìåííûå uf . Òîãäà óñëîâèå Au = b ìîæíî çàïèñàòü êàê Bub + F uf = b.âèñèìûå ñòðîêè (â ñèñòåìå íåò ëèíåéíî çàâèñèìûõ óðàâíåíèé), òî åñòü53(1) ñïðàâåäëèâî ðàâåíñòâî ub = B −1 b − B −1 F uf , à òàê êàê Av = bòîãäà è òîëüêî òîãäà, êîãäà Bvb + F vf = Bvb = b, òî ýòî ðàâåíñòâî ìîæíî ïåðåïèñàòü−1êàê ub = vb − BF uf . Òåïåðü îò êàíîíè÷åñêèõ îãðàíè÷åíèé u > 0 ìîæíî ïåðåéòè ê ýòîì ñëó÷àå äëÿubâíåêàíîíè÷åñêîé ôîðìå:Äëÿ ôóíêöèèJ(u),uf > 0,B −1 F uf 6 vb .èñïîëüçóÿ òå æå ðàññóæäåíèÿ, ìîæíî íàïèñàòü:J(u) = hc, uiRn = hcb , ub iRr + hcf , uf iRn−r == hcb , vb iRn + cf − (B −1 F )T cb , uf Rn−r = J(v) − h∆, uf i ,ãäå(2)J(v) = hc, vi , −∆ = cf − (B −1 F )T cb .Ââåä¼ì îáîçíà÷åíèåg(uf ) = J(v) − h∆, uf iRn−r .Çàìåòèì, ÷òî â ýòîì ñëó÷àåJ(v) = C ≡ const.(3)Òîãäà çàäà÷à(1)ñâîäèòñÿ ê çàäà÷å ñìåíüøèì êîëè÷åñòâîì ïåðåìåííûõ, íî ñ íåêàíîíè÷åñêèìè îãðàíè÷åíèÿìè:(g(uf ) = J(v) −P∆j uj → inf,(4)j∈Jfuf ∈ Uf = {uf > 0, (B −1 F )uf 6 vb }.Îáîçíà÷èì ÷åðåçJf+ìíîæåñòâî òåõj ∈ Jf ,äëÿ êîòîðûõ∆j > 0.È ïóñòük ∈ Jf+ ,íàïðèìåð, ñàìûé ìåíüøèé:k = min+ j.(5)j∈Jf(4)uf = (0, .

. . , 0, uk , 0, . . . , 0):ÐàññìîòðèìäëÿÎáîçíà÷èì ÷åðåçγkïîäçàäà÷óìèíèìèçàöèèôóíêöèèîòîäíîéïåðåìåííîégk (uk ) = J(v) − ∆k uk → inf,uk ∈ Uk = {uk > 0, (B −1 F )k uk 6 vb }.(B −1 F )k = B −1 Ak , è ïóñòüγ1k γ2k γk =  ..  , Ik+ = {i = 1, r | γik > 0}, . γrkâåêòîð+(Ik åñòü ìíîæåñòâî ðåàëüíûõ îãðàíè÷åíèé ñâåðõó íàuk ).(6)Òîãäà â êà÷åñòâå ðåøåíèÿïîäçàäà÷è ìîæíî âçÿòüθk = min+i∈Ikvjiγik.(7)Îïèøåì òåïåðü íåïîñðåäñòâåííî ñàì ìåòîä.

Âîçìîæíû ñëåäóþùèå ñèòóàöèè.1)Jf+ = ∅. ýòîì ñëó÷àåvïðèíàäëåæèò ìíîæåñòâóëèâàåìñÿ.54U∗(îïòèìàëüíà) è ìû îñòàíàâ-2)Jf+ 6= ∅,è ñóùåñòâóåò òàêîé íîìåðîãðàíè÷åíèé íàk ∈ Jf+ ,÷òîIk+ = ∅.Íî òîãäà íåò ðåàëüíûõuk , êîòîðûå ìîãóò áåñêîíå÷íî âîçðàñòàòü. Îòêóäà J∗ = −∞, U∗ = ∅è ïðîöåññ èòåðèðîâàíèÿ ñëåäóåò îñòàíîâèòü.3) ÌíîæåñòâîJf+ íå ïóñòî è äëÿ ëþáîãî k èç Jf+ ñîîòâåòñòâóþùåå ìíîæåñòâî Ik+ òàêæåíå ïóñòî. (Ýòîò ñëó÷àé ïðåäñòàâëÿåò ñîáîé íåïîñðåäñòâåííî øàã ìåòîäà.)Áåð¼ìÂ(7)kïî ïðàâèëó(5), uk = θkïî ïðàâèëó(7).ìèíèìóì ìîæåò äîñòèãàòüñÿ íà íåñêîëüêèõ íîìåðàõ, ïîýòîìó ââåä¼ì ñóïåð-ìåãà-ìíîæåñòâîIk+ ∗vji+= θk ,= i ∈ Ik |γikè èç íåãî âûáåðåì, íàïðèìåð, íàèìåíüøèé ýëåìåíòs = min i.i∈(Ik+ )∗Ïîñëå ýòîãî ïåðåõîäèì ê ðàññìîòðåíèþ ñëåäóþùåé óãëîâîé òî÷êè w ∈ U, êîòîðàÿ−1âû÷èñëÿåòñÿ ïî ïðàâèëó wb = vb − BAk uk .

Äîêàæåì, ÷òî ïðè èñïîëüçîâàíèèòàêîãî ïðàâèëà ìû äåéñòâèòåëüíî ïîëó÷èì óãëîâóþ òî÷êó.Äëÿ òî÷êèwñîîòâåòñòâóþùàÿ åé ìàòðèöàBáóäåò èìåòü âèäB(w) = (Aj1 |· · ·|Ajs−1 |Ak |Ajs+1 |· · ·|Ajr ).Íàì íåîáõîäèìî ïîêàçàòü, ÷òî ýòî åñòü áàçèñ. Ñäåëàåì ýòî ïî îïðåäåëåíèþ. Ïóñòüα1 Aj1 + . . . + αs−1 Ajs−1 + αk Ak + αs+1 Ajs+1 + . . . + αr Ajr = 0.Ïîäñòàâèì â ýòî ðàâåíñòâîAk = Bγk = γ1k Aj1 + . .

. + γrk Ajr .Òîãäà òàê êàêB(v)åñòü áàçèñ, òî íåîáõîäèìî äîëæíî âûïîëíÿòüñÿÎòñþäà ñëåäóåò, ÷òî âñåαiαi + αk γik = 0,αk γsk = 0.∀i 6= s,ðàâíû íóëþ, òî åñòüB(w)Òàêèì îáðàçîì, ïî Òåîðåìå 19 ìû ïîëó÷àåì, ÷òîìíîæåñòâàw áàçèñ.äåéñòâèòåëüíî óãëîâàÿ òî÷êàU.Çàìå÷àíèÿ.1)  ñëó÷àå, êîãäàvâûðîæäåíà,θk = 0èv = w. Ïðè ýòîì ìîæåòk è s (ïðàâèëà Áëýíäà,öèêëèâàíèå ïðîöåññà, íî ïðàâèëà âûáîðàïðîèçîéòè çààíòèöèêëèí)ïîçâîëÿþò èçáåæàòü ýòîãî.2) Åñëè óãëîâûõ òî÷åê â ìíîæåñòâåUêîíå÷íîå ÷èñëî, òî îñòàíîâêà ïðîöåññà ïðî-èçîéä¼ò ÷åðåç êîíå÷íîå ÷èñëî øàãîâ íà ñëó÷àÿõ 1) èëè 2).55Çàìåòèì, ÷òî âñå íàøè ðàññóæäåíèÿ îñíîâûâàþòñÿ íà ïðåäïîëîæåíèè, ÷òî ó íàñåñòü ïåðâàÿ âåðøèíà, îò êîòîðîé ìîæíî çàïóñêàòü ñèïëåêñ-ìåòîä.