1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 14
Текст из файла (страница 14)
å. yi = 1/2 (i = 1, 2k + 1). Ïðè ýòîì z(y) = 1/2 ni=1 αi .  ñèëó åäèíñòâåííîñòèïîëó÷åííîå ðåøåíèå ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì äâîéñòâåííîé çàäà÷è. Òàê êàê âñåyi (i = 1, n) ïîëîæèòåëüíû, èç âòîðîé òåîðåìû äâîéñòâåííîñòè ïîëó÷àåì, ÷òîxj + xj+1 = αj , j = 1, n − 1,x1 + xn = αn .62PÑëîæèâ âñå ýòè ðàâåíñòâà, ïîëó÷èì, ÷òî w(x) = 1/2 ni=1 αi = z(y). Çíà÷èò, ëþáîåðåøåíèå äàííîé ñèñòåìû îïòèìàëüíî.PÏîî÷åðåäíîPñêëàäûâàÿ è âû÷èòàÿ ýòè ðàâåíñòâà,íà÷èíàÿ ñ j = 1, ïîëó÷àåì, ÷òî 2x1 = ks=0 α2s+1 − ks=1 α2s , ò. å.nx1 =1X(−1)s+1 αs .2s=1Òåïåðü ïî èíäóêöèè ìîæíî îïðåäåëèòü è îñòàëüíûå êîîðäèíàòû âåêòîðà x :xj = (−1)j−1j−1³X´(−1)s αs + x1 , j = 2, .
. . , 2k + 1.s=1Òàêèì îáðàçîì, ýòî ðåøåíèå òîæå åäèíñòâåííîå. Ïîíÿòíî, ÷òî íàéòè åãî è äîêàçàòüîïòèìàëüíîñòü, íå çíàÿ ðåøåíèÿ äâîéñòâåííîé çàäà÷è, íåïðîñòî.Ïóñòü òåïåðü n = 2k. Êàê è âûøå, èìååì ðàâåíñòâà y1 = y3 = · · · = y2k−1 è y2 = y4 =· · · = y2k . Öåëåâóþ ôóíêöèþ ìîæíî çàïèñàòü â òàêîì âèäå:z(y) =k³Xk´³X´α2s−1 y1 +α2s y2 ,s=1s=1ãäå1, y1 ≥ 0, y2 ≥ 0. Íàéòè íàèáîëüøååçíà÷åíèåPkz(y) òåïåðü íåòðóäíî. ÅñëèPkPk y1 + y2 = Pkα2s−1 > s=1 α2s , òî y1 = 1, y2 = 0.
Åñëè s=1 α2s−1 < s=1 α2s , òî y1 = 0, y2 = 1. ÏðèPkPs=1ks=1 α2s ëþáîå ðåøåíèå, óäîâëåòâîðÿþùåå óñëîâèÿì, îïòèìàëüíî. Òàêèìs=1 α2s−1 =îáðàçîì,kknXoXz(y) = maxα2s−1 ,α2s .Pks=1Pks=1Ïóñòü äëÿ îïðåäåë¼ííîñòè s=1 α2s−1 ≥ s=1 α2s . Òîãäà y2s−1 = 1, y2s = 0 (s = 1, k).Ðàññìîòðèì ðåøåíèå èñõîäíîé çàäà÷è.  ñèëó âòîðîé òåîðåìû äâîéñòâåííîñòè èìååìðàâåíñòâà(∗)x2s−1 + x2s = α2s−1 , (s = 1, k).PkPnÑëîæèâ èõ, ïîëó÷èì w(x) = j=1 xj = s=1 α2s−1 = z(y). Òàêèì îáðàçîì, ëþáîå ðåøåíèå,óäîâëåòâîðÿþùåå ðàâåíñòâàì (∗) è íåðàâåíñòâàìx2s + x2s+1 ≥ α2s , (s = 1, .
. . , k − 1),x2k + x1 ≥ α2k ,îïòèìàëüíî. Âûïèñàòü ðåøåíèå â ñëó÷àå n = 2k íå óäà¼òñÿ, íî ýòî è íå òðåáîâàëîñü.Çàäà÷è1. Íàéòè îïòèìàëüíîå ðåøåíèå çàäà÷è, èñõîäÿ èç ãåîìåòðè÷åñêîé èíòåðïðåòàöèè äâîéñòâåííîé ê íåé:1) x1 + 2x2 + 3x3 + 4x4 −→ min,x1 + x2 + x3 + x4 ≥ 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;2) x1 + x2 + x3 + x4 −→ min,x1 − x2 ≥ 0, x1 + x2 − x3 + x4 − x5 ≥ 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0;633) x1 + 5x2 + x3 + 10x4 + x5 + 3x6 −→ min,−x1 + x2 + x3 + x4 ≥ 1, x1 + 2x2 − x3 + 3x4 − x5 − x6 ≥ 1,x1 ≥ 0, x2 ≥ 0 x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0.2.
Íàéòè îïòèìàëüíîå ðåøåíèå çàäà÷è, ðåøàÿ äâîéñòâåííóþ ê íåé çàäà÷ó ñèìïëåêñìåòîäîì:1) 3x1 + 5x2 + 4x3 −→ min,x1 + 2x2 + 3x3 ≥ 1, 2x1 + 3x2 + x3 ≥ 1, 3x1 + x2 + 2x3 ≥ 1,6x1 + 6x2 + 6x3 ≥ 1, 2x1 + 4x3 ≥ 1;2) x1 − x2 + x3 −→ min,x1 − x2 + 2x3 ≥ 0, x1 + x2 − x3 ≥ 0, −x1 + 2x2 + x3 ≥ 1,x1 + x3 ≥ 2, −2x1 − 2x2 − 3x3 ≥ 3.3. Èñïîëüçóÿ òåîðèþ äâîéñòâåííîñòè, íàéòè îïòèìàëüíîå ðåøåíèå çàäà÷è:1) x1 + 2x2 + 3x3 + · · · + nxn −→ min,x1 + x2 + · · · + xi ≥ i, i = 1, n,xj ≥ 0, j = 1, n;2) x1 + x2 + x3 −→ min,λx1 + x2 + x3 ≥ µ1 , x1 + λx2 + x3 ≥ µ2 , x1 + x2 + λx3 ≥ µ3 ;3) x1 + λx2 + λ2 x3 −→ min,(1 + λ)x1 + x2 + x3 ≥ µ1 , x1 + (1 + λ)x2 + x3 ≥ µ2 , x1 + x2 + (1 + λ)x3 ≥ µ3 .4.
Èñïîëüçóÿ òåîðèþ äâîéñòâåííîñòè, äîêàçàòü, ÷òî:nP1) ñèñòåìà ëèíåéíûõ óðàâíåíèéaij xj = bi , i = 1, m íå èìååò íåîòðèöàòåëüíûõ ðåøåj=1íèé òîãäà è òîëüêî òîãäà, êîãäà ñîâìåñòíà ñèñòåìà2)ñèñòåìà ëèíåéíûõ íåðàâåíñòâmPi=1mPi=1nPj=1mPi=1bi yi > 0;aij yi ≤ cj , j = 1, n ñîâìåñòíà òîãäà è òîëüêî òîãäà,êîãäà äëÿ ëþáîãî íåîòðèöàòåëüíîãî ðåøåíèÿ ñèñòåìûóñëîâèåaij yi ≤ 0, j = 1, n,nPj=1aij xj = 0, i = 1, m âûïîëíÿåòñÿcj xj ≥ 0;3)óðàâíåíèåmPi=1bi yi = b ÿâëÿåòñÿ ñëåäñòâèåì ñèñòåìûòîëüêî òîãäà, êîãäà ñîâìåñòíà ñèñòåìà óðàâíåíèénPj=15.
Ïðè êàêèõ çíà÷åíèÿõ a ñèñòåìà íåñîâìåñòíà:64mPi=1aij yi = cj , j = 1, n òîãäà èaij xj = bi , i = 1, m,nPj=1cj xj = b.1) − 5y1 − 2y2 ≤ a 2) 9y1 + 16y2 ≥ a 3) − 3y1 − y2 ≤ a + 5−4y1 + y2 ≤ 5,7y1 − 8y2 ≤ 9,y1 − 3y2 − 4y3 ≤ 1,2y1 + y2 ≤ 2,y1 + y2 ≤ 1,y1 + y3 ≤ 1,3y1 + y2 ≤ 4;y1 + 2y2 ≤ −1;−2y1 + y2 + y3 ≤ 1,y2 + y3 ≤ −2?5.3. Äâîéñòâåííûé ñèìïëåêñìåòîä ñèëó òåîðåì äâîéñòâåííîñòè, ðåøàÿ ïðÿìóþ çàäà÷ó (1)(4), ìû îäíîâðåìåííî ñ å¼îïòèìàëüíûì ðåøåíèåì ïîëó÷àåì òàêæå è îïòèìàëüíîå ðåøåíèå äâîéñòâåííîé çàäà÷è èëèóñòàíàâëèâàåì íåðàçðåøèìîñòü îáåèõ çàäà÷. Ïðè ýòîì äëÿ çàäà÷è â êàíîíè÷åñêîé ôîðìåx∗B = B −1 b, x∗N = 0, à y ∗ = cB B −1 , ãäå x∗ è y ∗ îïòèìàëüíûå ðåøåíèÿ ñîîòâåòñòâåííîïðÿìîé è äâîéñòâåííîé çàäà÷è, à B îïòèìàëüíûé áàçèñ.
Äàííîå ñâîéñòâî ïðèâîäèò êäðóãîìó ìåòîäó ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ, à èìåííî ê äâîéñòâåííîìóñèìïëåêñìåòîäó.Äàëåå ïðåäïîëàãàåòñÿ, ÷òî èñïîëüçóåòñÿ òà æå ñàìàÿ ôîðìà ñèìïëåêñòàáëèöû è òî æåå¼ ýëåìåíòàðíîå ïðåîáðàçîâàíèå.Îïèñàíèå àëãîðèòìà:0) Íà÷àòü ñ äâîéñòâåííî äîïóñòèìîé ñèìïëåêñòàáëèöû (z0j ≥ 0, j ∈ J ).1) Åñëè ñèìïëåêñòàáëèöà ïðÿìî äîïóñòèìà, ò. å. zi0 ≥ 0, i ∈ I , òîÊÎÍÅÖ (ïîëó÷åíî îïòèìàëüíîå ðåøåíèå).2) Âûáðàòü âåäóùóþ ñòðîêó r : zr0 < 0, r ≥ 1.3) Åñëè {j | zrj < 0, j ≥ 1} 6= ∅, òî âûáðàòü âåäóùèé ñòîëáåö s:z0jz0s= min{| zrj < 0, j ≥ 1},|zrs ||zrj |èíà÷å ÊÎÍÅÖ (çàäà÷à íåðàçðåøèìà, òàê êàê X = ∅).4) Ïðåîáðàçîâàòü ñèìïëåêñòàáëèöó, ïîëîæèòü σ(r) := sè ïåðåéòè íà øàã 1. ñëó÷àå íåâûðîæäåííîé äâîéñòâåííîé çàäà÷è â êàæäîé äâîéñòâåííî äîïóñòèìîé ñèìïëåêñòàáëèöå ýëåìåíòû z0j , äëÿ íîìåðîâ j íåáàçèñíûõ ïåðåìåííûõ, ïîëîæèòåëüíû (|{j | z0j >0, j ≥ 1}| = n − m), ÷òî ãàðàíòèðóåò ñõîäèìîñòü äâîéñòâåííîãî ñèìïëåêñìåòîäà çà êîíå÷íîå ÷èñëî øàãîâ.
 ñëó÷àå âûðîæäåííîé äâîéñòâåííîé çàäà÷è ìîæíî èñïîëüçîâàòü òå æåñïîñîáû, ÷òî è â ñëó÷àå ïðÿìîãî ñèìïëåêñìåòîäà.Äâîéñòâåííûé ñèìïëåêñìåòîä óäîáíî èñïîëüçîâàòü äëÿ ðåøåíèÿ çàäà÷ ËÏ âèäàcx → minAx ≤ b,x ≥ 0,ñ íåîòðèöàòåëüíûì âåêòîðîì c. Òîãäà ïîñëå ïðèâåäåíèÿ ê êàíîíè÷åñêîé ôîðìå ïîëó÷àåòñÿäâîéñòâåííî äîïóñòèìàÿ ñèìïëåêñòàáëèöà.Ïðèìåð.
Ðåøèòü çàäà÷ów(x) = x1 + 3x2 → min,x1 + x2 + x3 ≤ 4,x1 − x2 + x3 ≤ −1,xi ≥ 0, i = 1, 2, 3.65Ðåøåíèå. Òàê êàê âåêòîð c = (1, 3, 0) íåîòðèöàòåëåí, òî äàííóþ çàäà÷ó öåëåñîîáðàçíîðåøàòü äâîéñòâåííûì ñèìïëåêñìåòîäîì.Ïðåæäå âñåãî ñâåäåì çàäà÷ó ê êàíîíè÷åñêîé ôîðìå, ââåäÿ äîïîëíèòåëüíûå íåîòðèöàòåëüíûå ïåðåìåííûå:w(x) = x1 + 3x2 → min,x1 + x2 + x3 + x4 = 4,x1 − x2 + x3 + x5 = −1,xi ≥ 0, i = 1, 2, 3, 4, 5.Âîçüì¼ì â êà÷åñòâå áàçèñà äâà íîâûõ ñòîëáöà: B = (A4 , A5 ) è ïîñòðîèì ñèìïëåêñ - òàáëèöó−wx4x504−1x1111x231−1x3011x4010x5001Òàáëèöà ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé, íî íå ÿâëÿåòñÿ ïðÿìî äîïóñòèìîé (z20 =−1 < 0). Âåäóùèé ýëåìåíò âûáèðàåì îäíîçíà÷íî (r = 2, s = 2).
Ïîñëå ïðåîáðàçîâàíèÿïîëó÷èì òàáëèöóx1 x2 x3 x4 x5−w −3 40303x4320211x21 −1 1 −1 0 −1Ïîëó÷åíà ïðÿìî è äâîéñòâåííî äîïóñòèìàÿ òàáëèöà. Ñëåäîâàòåëüíî, áàçèñ B = (A2 , A4 )îïòèìàëåí, ïðè ýòîì x∗ = (0, 1, 0, 3, 0)> è w(x∗ ) = 3.Çàäà÷èÐåøèòü ñ ïîìîùüþ äâîéñòâåííîãî ñèìïëåêñìåòîäà çàäà÷ó, âûáðàâ áàçèñ B 0 â êà÷åñòâåèñõîäíîãî áàçèñà:1) −x1 − 2x2 + 4x3 −→ min,x1 + x2 − 3x3 = 0, x1 − 2x2 + x3 = 3,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,B 0 = (A1 , A2 );2) −x1 + 7x2 + 5x3 + 35x4 −→ min,2x1 + 6x2 − 8x3 − 30x4 = 6, x1 − x2 + x3 + x4 = −5,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,B 0 = (A1 , A2 );3) −x1 − x2 − x3 + x5 −→ min,x1 + x2 − 4x4 + 2x5 = −2, x2 + x3 + x4 − 2x5 = −2, x1 + x3 + 3x4 − 2x5 = −2,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,B 0 = (A1 , A2 , A3 ).66ÏðèëîæåíèåÌåòîä âîçìîæíûõ íàïðàâëåíèéËþáàÿ îñíîâíàÿ çàäà÷à âûïóêëîãî ïðîãðàììèðîâàíèÿ ñâîäèòñÿ ê çàäà÷å ñ ëèíåéíîéöåëåâîé ôóíêöèåé ââåäåíèåì äîïîëíèòåëüíîé ïåðåìåííîé xn+1 :xn+1 → min,ex∈Xe = {x = (x1 , ..., xn , xn+1 ) ∈ En+1 | ϕj (x1 , ..., xn ) ≤ 0 (j = 1, m), f (x1 , ..., xn ) − xn+1 ≤ 0}.XÇäåñü f (x1 , ..., xn ) öåëåâàÿ ôóíêöèÿ èñõîäíîé çàäà÷è.Ïîýòîìó, íå òåðÿÿ îáùíîñòè, ìîæíî ðàññìàòðèâàòü îñíîâíóþ çàäà÷ó âûïóêëîãî ïðîãðàììèðîâàíèÿ â âèäåf (x) =< c, x >→ min,(1)X = {x = (x1 , ..., xn ) ∈ En | ϕj (x) ≤ 0 (j = 1, m)},(2)x∈Xãäå c çàäàííûé âåêòîð, à ϕj (x) (j = 1, m)} äèôôåðåíöèðóåìûå âûïóêëûå ôóíêöèè.
Âäàëüíåéøåì ïðåäïîëàãàåòñÿ, ÷òî âûïîëíåíî óñëîâèå ðåãóëÿðíîñòè Ñëåéòåðà.Ïóñòü çàäàíà òî÷êà x ∈ X . ×åðåç I(x) = {j ∈ {1, ..., m}| ϕj (x) = 0 }, êàê è ðàíåå, îáîçíà÷èì ìíîæåñòâî èíäåêñîâ àêòèâíûõ îãðàíè÷åíèé, à äëÿ óñòàíîâëåíèÿ ïðåäåëà äîïóñêàåìîéïîãðåøíîñòè ïðè ÷èñëåííîì ðåøåíèè çàäà÷è (1)(2) ââåä¼ì ìíîæåñòâîJ(x, δ) = {j ∈ {1, ..., m}| − δ < ϕj (x) ≤ 0 },ãäå δ çàäàííûé ïîëîæèòåëüíûé ïàðàìåòð.Ïóñòü δ0 > 0 è x0 ∈ X íåêîòîðûå íà÷àëüíûå óñëîâèÿ è ïóñòü óæå èçâåñòíî k -åïðèáëèæåíèå δk > 0 è xk ∈ X (k ≥ 0).Ðàññìîòðèì ñëåäóþùèå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ.Çàäà÷à Aσ → min,(3)σ,p< c, p >≤ σ,< ϕ0j (xk ), p >≤ σ(j ∈ J(xk , δk )),|pi | ≤ 1 (i = 1, n),(4)(5)(6)ãäå ïîñëåäíèå óñëîâèÿ ýòî óñëîâèÿ íîðìèðîâêè âåêòîðà p, êîòîðûå ïîçâîëÿþò îãðàíè÷èòüäîïóñòèìóþ îáëàñòü ðàññìàòðèâàåìîé çàäà÷è.Îáîçíà÷èì îïòèìàëüíîå ðåøåíèå ýòîé çàäà÷è ÷åðåç (σk , pk ).
Òàê êàê íóëåâàÿ òî÷êà ÿâëÿåòñÿ äîïóñòèìîé, òî σk ≤ 0. Èç ýòîãî ôàêòà è óñëîâèé (4) è (6) ñëåäóåò ñóùåñòâîâàíèåîïòèìàëüíîãî ðåøåíèÿ.Çàäà÷à Bσ → min,σ,p< c, p >≤ σ,< ϕ0j (xk ), p >≤ σ(j ∈ I(xk )),|pi | ≤ 1 (i = 1, n).67(7)Òàê êàê I(xk ) ⊆ J(xk , δk ), òî σ k ≤ σk , ãäå ÷åðåç σ k îáîçíà÷åíî îïòèìàëüíîå çíà÷åíèåöåëåâîé ôóíêöèè çàäà÷è B .
Çàìåòèì, ÷òî ðåøåíèå ýòîé çàäà÷è òàêæå âñåãäà ñóùåñòâóåò.Òåîðåìà 1 (êðèòåðèé îïòèìàëüíîñòè). Ïóñòü (σ ∗ , p∗ ) îïòèìàëüíîå ðåøåíèå çàäà÷è B äëÿ x∗ ∈ X . Òîãäà σ ∗ = 0 â òîì è òîëüêî â òîì ñëó÷àå, êîãäà x∗ îïòèìàëüíîåðåøåíèå çàäà÷è (1)(2).Îïèøåì îäíó k -þ èòåðàöèþ ìåòîäà âîçìîæíûõ íàïðàâëåíèé. Ïðè ýòîì óæå èìååì δk > 0kè x ∈ X (k = 0, 1, ...).Øàã 1. Ðåøèòü çàäà÷ó A (çàäà÷ó (3)(6)). Ïóñòü (σk , pk ) îïòèìàëüíîå ðåøåíèå.Åñëè σk < −δk , òî ïîëàãàåì δk+1 = δk è ïåðåõîäèì íà øàã 2.Åñëè −δk ≤ σk < 0, òî ïîëàãàåì δk+1 = δk /2 è ïåðåõîäèì íà øàã 2.Åñëè σk = 0, òî ðåøàåì çàäà÷ó B è íàõîäèì ðåøåíèå σ k , pk .Åñëè σ k = 0, òî âåêòîð xk ñîãëàñíî êðèòåðèþ îïòèìàëüíîñòè ÿâëÿåòñÿ îïòèìàëüíûìðåøåíèåì èñõîäíîé çàäà÷è.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
