1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 11
Текст из файла (страница 11)
 ðåçóëüòàòå îäíîé èòåðàöèè ëåêñèêîãðàôè÷åñêîãî ñèìïëåêñìåòîäàïðîèñõîäèò ëåêñèêîãðàôè÷åñêîå âîçðàñòàíèå íóëåâîé ñòðîêè α0 = (z00 , z01 , . . . , z0n ).Óòâåðæäåíèå 13.  õîäå ðàáîòû ëåêñèêîãðàôè÷åñêîãî ñèìïëåêñ ìåòîäà áàçèñû íåïîâòîðÿþòñÿ, ÷òî ãàðàíòèðóåò åãî êîíå÷íîñòü.Ïðèìåð.  êà÷åñòâå ïðèìåðà ðàññìîòðèì ïðèìåð 3 èç ïðåäûäóùåãî ïîäðàçä.
4.4, íàêîòîðîì áûëà ïðîäåìîíñòðèðîâàíà âîçìîæíîñòü çàöèêëèâàíèÿ îáû÷íîãî ñèìïëåêñìåòîäà.Âûáðàâ áàçèñ B 0 = (A1 , A2 , A7 ), ïîëó÷èì èñõîäíóþ òàáëèöó, êîòîðàÿ ÿâëÿåòñÿ íîðìàëüíîé:−wx1x2x70001x10100x20010x3−1141x41−2−31x5−1−3−21x61411x70001Ïóñòü ïî-ïðåæíåìó s = 3. Çäåñü α1 = (0, 1, 0, 1, −2, −3, 4, 0), α2 = (0, 0, 1, 4, −3, −2, 1, 0) èα3 = (1, 0, 0, 1, 1, 1, 1, 1).Òàê êàê α3 − α1 = (1, −1, ...)  0 è α3 − α2 /z23 = (1, 0, ...)  0, òî α3  α1 è α3  1/z23 α2 .Òàêèì îáðàçîì, íóæíî ñðàâíèòü α1 è (1/z23 )α2 . Èìååìα1 −1 2α = (0, 1, .
. . )  0.4Çíà÷èò, lex min{αi /zi3 | zi3 > 0} = (1/z23 )α2 è r = 2.44Ïðåîáðàçîâàâ ñèìïëåêñòàáëèöó (ïåðåéäÿ ê áàçèñó B 1 = (A1 , A3 , A7 )), ïîëó÷èì−wx1x3x70001x10100x21/4−1/41/4−1/4x30010x41/4−5/4−3/47/4x5−6/4−10/4−2/46/4x65/415/41/43/4x70001Çäåñü âåäóùèé ýëåìåíò îïðåäåëÿåòñÿ îäíîçíà÷íî: s = 5, r = 3. Ïåðåõîäÿ ê áàçèñó B 2 =(A1 , A3 , A5 ), ïðåîáðàçóåì ñèìïëåêñ òàáëèöó.
 ðåçóëüòàòå ïåðåéäåì ê òàáëèöå (íåíóæíûåýëåìåíòû îïóùåíû):−wx1x3x515/31/32/3x10100x20x30010x42x50001x62x71Òàáëèöà ÿâëÿåòñÿ ïðÿìî è äâîéñòâåííî äîïóñòèìîé. Îïòèìàëüíîå ðåøåíèå ïîëó÷åíî çà äâåèòåðàöèè. Ïðè ýòîì x∗ = (5/3, 0, 1/3, 0, 2/3, 0, 0)> , w(x∗ ) = −1.Çàäà÷èÐåøèòü ñ ïîìîùüþ ëåêñèêîãðàôè÷åñêîãî âàðèàíòà ïðÿìîãî ñèìïëåêñìåòîäà çàäà÷ó,âûáðàâ áàçèñ B 0 â êà÷åñòâå èñõîäíîãî áàçèñà:1) −x1 − 2x2 − x3 − 2x4 − 3x5 −→ min,x1 − x2 − 2x5 = 0, x2 + x4 + 4x5 = 0, x2 + x3 + x5 = 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,B 0 = (A1 , A2 , A3 );2) −4x1 − x2 − x3 + x4 − x5 − 2x6 −→ min,3x1 + 2x2 + x3 + x4 + x5 + x6 = 1, 2x1 + 2x2 + x4 + x5 = 0, x1 + x2 + x4 = 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0,B 0 = (A4 , A5 , A6 );3) −x1 − 4x2 − x3 − x4 + 2x5 − x6 −→ min,x1 + x2 + x4 = 0, x1 + x2 + x3 + x5 = 1, x2 + x3 + x6 = 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0,B 0 = (A4 , A5 , A6 ).4.6.
Ìåòîä èñêóññòâåííîãî áàçèñà ïðèìåðàõ, ðàññìîòðåííûõ ðàíåå, ïðåäïîëàãàëîñü, ÷òî ëèáî çàäàí èñõîäíûé äîïóñòèìûé áàçèñ, ëèáî áûëî èçâåñòíî áàçèñíîå äîïóñòèìîå ðåøåíèå. ýòîì ïîäðàçäåëå ðàññìàòðèâàåòñÿ îáùèé ìåòîä ðåøåíèÿ çàäà÷è ËÏ â êàíîíè÷åñêîéôîðìå, ïîçâîëÿþùèé íà ïåðâîì ýòàïå íàéòè áàçèñíîå äîïóñòèìîå ðåøåíèå èëè óñòàíîâèòü,÷òî X = ∅, à íà âòîðîì îïòèìàëüíûé áàçèñ è ñîîòâåòñòâóþùåå åìó ðåøåíèå ëèáî óñòàíîâèòü íåðàçðåøèìîñòü çàäà÷è èç-çà íåîãðàíè÷åííîñòè öåëåâîé ôóíêöèè. Ïðè ýòîì íå ïðåäïîëàãàåòñÿ, ÷òî ðàíã ìàòðèöû A ðàâåí m.45Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ñèñòåìà îãðàíè÷åíèé ðàâåíñòâ Ax = bçàïèñàíà òàêèì îáðàçîì, ÷òî b ≥ 0. Ýòîãî ìîæíî äîáèòüñÿ, óìíîæàÿ íóæíûå ñòðîêè íà −1.Òîãäà ìåòîä èñêóññòâåííîãî áàçèñà ìîæíî ïðåäñòàâèòü â âèäå ñëåäóþùèõ øàãîâ.0.
Ïîñòðîèòü ñèìïëåêñòàáëèöó äëÿ çàäà÷èξ=mXxn+i → min,(8)i=1ai x + xn+i = bi , i = 1, m;(9)xj ≥ 0, j = 1, n + m,(10)âûáðàâ â êà÷åñòâå áàçèñà B = (An+i , . . . , An+m ). Çäåñü ai ýòî i-ÿ ñòðîêà ìàòðèöû A(i = 1, m). Òàê êàê ìàòðèöà B åäèíè÷íàÿ, òî äëÿ ïîñòðîåíèÿ òàáëèöû äîñòàòî÷íî â öåëåâîéôóíêöèè ξ âûðàçèòü áàçèñíûå ïåðåìåííûå (èñêóññòâåííûé áàçèñ) xn+i (i = 1, m) ÷åðåçíåáàçèñíûå ïåðåìåííûå xj (j = 1, n), èñïîëüçóÿ îãðàíè÷åíèÿ (9).  ðåçóëüòàòå ïîëó÷èì,÷òîmXξ=(bi − ai x).i=1Ñëåäîâàòåëüíî,z00 = −mXbi , à z0j =i=1mXaij , j = 1, n.i=1Ïðè ýòîì ñèìïëåêñòàáëèöà ïðÿìî äîïóñòèìà, à áàçèñíîå äîïóñòèìîå ðåøåíèå èìååò âèäxj = 0 (j = 1, n), è xn+i = bi (i = 1, m).1.
Ïðîäåëàòü øàãè 14 àëãîðèòìà ñèìïëåêñìåòîäà, îïèñàííîãî â ïîäðàçä. 4.4.Òàê êàê öåëåâàÿ ôóíêöèÿ çàäà÷è (8)(10) îãðàíè÷åíà ñíèçó íóëåì è äîïóñòèìîå ìíîæåñòâî, çàäàâàåìîå óñëîâèÿìè (9)(10), íåïóñòî, òî çàäà÷à (8)(10) âñåãäà ðàçðåøèìà èìèíèìóì íåîòðèöàòåëåí. Ïîýòîìó íà ïåðâîì ýòàïå âû÷èñëåíèÿ ìîãóò çàâåðøèòüñÿ òîëüêî ïîëó÷åíèåì ïðÿìî è äâîéñòâåííî äîïóñòèìîãî áàçèñà. Êàê òîëüêî òàêîé áàçèñ áóäåòïîëó÷åí, ïåðåéòè ê ñëåäóþùåìó ïóíêòó.2.
Åñëè îïòèìàëüíîå ðåøåíèå ξ ∗ > 0, òî ÊÎÍÅÖ (èñõîäíàÿ çàäà÷à íå èìååò äîïóñòèìûõ ðåøåíèé: X = ∅), èíà÷å óäàëèòü èç ñèìïëåêñòàáëèöû âñå ñòîëáöû, ñîîòâåòñòâóþùèåèñêóññòâåííûì ïåðåìåííûì xj (j = n + 1, n + m), è íóëåâóþ ñòðîêó.3. Åñëè áàçèñíûìè ïåðåìåííûìè ÿâëÿþòñÿ òîëüêî ïåðåìåííûå èñõîäíîé çàäà÷è xj (j ≤n), òî ïåðåéòè íà øàã 7.4. Âûáðàòü ñòðîêó, ñîîòâåòñòâóþùóþ èñêóññòâåííîé ïåðåìåííîé xr (r > n).5. Åñëè ñóùåñòâóåò zrs 6= 0 (1 ≤ s ≤ n), òî âûïîëíèòü ýëåìåíòàðíîå ïðåîáðàçîâàíèåáàçèñà ñ âåäóùèì ýëåìåíòîì zrs è ïåðåéòè íà øàã 3.6.
Åñëè zrj = 0 äëÿ âñåõ j = 1, n, òî óäàëèòü r-þ ñòðîêó èç ñèìïëåêñòàáëèöû è ïåðåéòèíà øàã 3.7. Äîáàâèòü íóëåâóþ ñòðîêó â ñèìïëåêñòàáëèöó, çàïèñàâ â íå¼ êîýôôèöèåíòû öåëåâîé ôóíêöèè îñíîâíîé çàäà÷è w(x), âûðàæåííîé ÷åðåç íåáàçèñíûå ïåðåìåííûå. Ïîëó÷åíàïðÿìî äîïóñòèìàÿ ñèìïëåêñòàáëèöà èñõîäíîé çàäà÷è.8. Ïðîäåëàòü øàãè 14 àëãîðèòìà ñèìïëåêñìåòîäà, îïèñàííîãî â ïîäðàçä. 4.4.Øàãè 07 îïèñàííîãî âûøå ñïîñîáà ïîëó÷åíèÿ áàçèñíîãî äîïóñòèìîãî ðåøåíèÿ îáû÷íîíàçûâàþò ïåðâûì ýòàïîì ñèìïëåêñìåòîäà, à ìåòîä â öåëîì äâóõýòàïíûì ñèìïëåêñìåòîäîì.Âûïîëíåíèå øàãà 6 ñâèäåòåëüñòâóåò î ëèíåéíîé çàâèñèìîñòè óðàâíåíèé Ax = b, ÷òîïîçâîëÿåò óäàëèòü ÷àñòü óðàâíåíèé.
Ïîäîáíàÿ ñèòóàöèÿ âîçíèêàåò, åñëè ðàíã ìàòðèöû Aìåíüøå ÷èñëà óðàâíåíèé m.46Ïîñëå âûïîëíåíèÿ øàãà 7 èìååì ïðÿìî äîïóñòèìóþ ñèìïëåêñòàáëèöó èñõîäíîé çàäà÷è,ò. å. çàâåðø¼í 0-é øàã àëãîðèòìà ïîäðàçä. 4.4. è ìîæíî ïåðåõîäèòü ê åãî øàãàì 14. Âðåçóëüòàòå ëèáî óñòàíîâèì, ÷òî öåëåâàÿ ôóíêöèÿ w(x) íå îãðàíè÷åíà ñíèçó, ëèáî ïîëó÷èìîïòèìàëüíîå ðåøåíèå.Ïðèìåð 1. Ðåøèòü çàäà÷óx1 − x2 + x3 − x4 + 3x5 → min,x1 + x4 + 2x5 = 1,−x2 − x3 + x4 + 2x5 = 1,2x1 − 3x2 + x3 + x4 = 0,xj ≥ 0 (j = 1, . .
. , 5).Ðåøåíèå. Áóäåì èñêàòü íà÷àëüíîå áàçèñíîå äîïóñòèìîå ðåøåíèå ìåòîäîì èñêóññòâåí-íîãî áàçèñà. Äëÿ ýòîãî äîáàâèì èñêóññòâåííûå ïåðåìåííûå x6 , x7 , x8 è ïîëó÷èì çàäà÷óx6 + x7 + x8 → min,x1 + x4 + 2x5 + x6 = 1,−x2 − x3 + x4 + 2x5 + x7 = 1,2x1 − 3x2 + x3 + x4 + x8 = 0,xj ≥ 0 (j = 1, . . . , 8),ñ áàçèñíûì äîïóñòèìûì ðåøåíèåì x = (0, 0, 0, 0, 0, 1, 1, 0)> . Èñêëþ÷èì áàçèñíûå ïåðåìåííûåx6 , x7 è x8 èç öåëåâîé ôóíêöèè ýòîé çàäà÷è:ξ = (1−x1 −x4 −2x5 )+(1+x2 +x3 −x4 −2x5 )+(−2x1 +3x2 −x3 −x4 ) = 2−3x1 +4x2 −3x4 −4x5 .Äàííîå ðàâåíñòâî çàïèøåì â ïðèíÿòîì âèäå−ξ − 3x1 + 4x2 − 3x4 − 4x5 = −2.Ïîëó÷àåì èñõîäíóþ ñèìïëåêñòàáëèöó−ξx6x7x8−2110x1−3102x240−1−3x300−11x4−3111x5−4220x60100x70010x80001Íà ýòîì íóëåâîé øàã àëãîðèòìà ìåòîäà èñêóñòâåííîãî áàçèñà çàâåðø¼í.
Ïåðåõîäèì ê ïåðâîìó øàãó. Òàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé. Âûáèðàåì âåäóùèé ñòîëáåö s.Ïóñòü s = 4. Âûáèðàåì âåäóùóþ ñòðîêó. Ïîëó÷àåì r = 3 è, ñëåäîâàòåëüíî, âåäóùèé ýëåìåíòz34 = 1. Ïåðåõîäèì ê íîâîìó áàçèñó, êîòîðîìó ñîîòâåòñòâóåò ñëåäóþùàÿ ñèìïëåêñòàáëèöà:−ξx6x7x4−2110x13−1−22x2−532−3x33−1−21x4000147x5−4220x60100x70010x83−1−11Òàáëèöà âñ¼ åù¼ íå äâîéñòâåííî äîïóñòèìà. Âûáèðàåì â êà÷åñòâå âåäóùåãî ýëåìåíò z15 .Ïðåîáðàçîâàâ, ïîëó÷èì ñèìïëåêñòàáëèöó−ξx5x7x401/200x11−1/2−12x213/2−1−3x31−1/2−11x40001x50100x621/2−10x70010x81−1/201Òàáëèöà ïðÿìî è äâîéñòâåííî äîïóñòèìà, è ξ ∗ = 0.
Íà øàãå 2 ìåòîäà èñêóññòâåííîãî áàçèñà âòàáëèöå ïðîèçîéäåò óäàëåíèå íóëåâîé ñòðîêè è òð¼õ ïîñëåäíèõ ñòîëáöîâ, ñîîòâåòñòâóþùèõèñêóññòâåííûì ïåðåìåííûì. Òàê êàê â áàçèñå èìååòñÿ èñêóññòâåííàÿ ïåðåìåííàÿ x7 è z21 =−1 6= 0, òî ìîæíî âûïîëíèòü ýëåìåíòàðíîå ïðåîáðàçîâàíèå áàçèñà ñ âåäóùèì ýëåìåíòîìz21 (øàãè 4 è 5), ïîñëå ÷åãî áàçèñå îñòàíóòñÿ òîëüêî ïåðåìåííûå èñõîäíîé çàäà÷è:x5x1x4x10101/200x221−5x301−1x4001x5100Íà ýòîì ïåðâûé ýòàï àëãîðèòìà ñèìïëåêñìåòîäà çàâåðø¼í. Ïåðåõîäèì íà øàã 7.
Âûðàçèì÷åðåç íåáàçèñíûå ïåðåìåííûå x2 è x3 öåëåâóþ ôóíêöèþ èñõîäíîé çàäà÷è. Èç ïîñëåäíåéñèìïëåêñòàáëèöû èìååì ðàâåíñòâà2x2 + x5 = 1/2,x1 + x2 + x3 = 0,−5x2 − x3 + x4 = 0.Ñëåäîâàòåëüíî,w(x) = (−x2 − x3 ) − x2 + x3 − (5x2 + x3 ) + 3(1/2 − 2x2 ) = 3/2 − 13x2 − x3 .Ïîëó÷èì ñèìïëåêñòàáëèöó èñõîäíîé çàäà÷è ñ áàçèñîì B = (A1 , A4 , A5 ) è ñîîòâåòñòâóþùèìáàçèñíûì äîïóñòèìûì ðåøåíèåì x = (0, 0, 0, 0, 1/2) :−wx5x1x4−3/21/200x10010x2−1321−5x3−101−1x40001x50100Òåïåðü ïåðåõîäèì íà øàã 8. Òàê êàê ñèìïëåêñòàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé,òî âûáèðàåì, ñîãëàñíî ïðÿìîìó àëãîðèòìó ñèìïëåêñìåòîäà, s = 2, r = 2. Ïðåîáðàçóåìòàáëèöó ñ âåäóùèì ýëåìåíòîì z22 = 1 è ïåðåõîäèì ê ïðÿìî è äâîéñòâåííî äîïóñòèìîéòàáëèöåx1 x2 x3 x4 x5−w −3/2 13 0 12 0 0x51/2 −2 0 −2 0 1x201110 0x405041 0Òàêèì îáðàçîì, ïîëó÷åíî îïòèìàëüíîå ðåøåíèå x∗ = (0, 0, 0, 0, 1/2), ïðè ýòîì w(x∗ ) = 3/2.48Ïðèìåð 2.
Ðåøèòü çàäà÷ó−2x1 − 7x2 + x3 + 4x4 → min,x1 + x2 − x4 = 1,2x1 + x2 + x3 − 2x4 = 3,xj ≥ 0 (j = 1, . . . , 4).Ðåøåíèå. Áóäåì èñêàòü íà÷àëüíîå áàçèñíîå äîïóñòèìîå ðåøåíèå ìåòîäîì èñêóññòâåííîãî áàçèñà. Äëÿ ýòîãî äîáàâèì èñêóññòâåííûå ïåðåìåííûå x5 , x6 è ïîëó÷èì çàäà÷óx5 + x6 → min,x1 + x2 − x4 + x5 = 1,2x1 + x2 + x3 − 2x4 + x6 = 3,xj ≥ 0 (j = 1, . . . , 6)ñ áàçèñíûì äîïóñòèìûì ðåøåíèåì x = (0, 0, 0, 0, 1, 3)> . Èñêëþ÷èì áàçèñíûå ïåðåìåííûåx5 , x6 èç öåëåâîé ôóíêöèè ýòîé çàäà÷è è ïîëó÷èì èñõîäíóþ ñèìïëåêñòàáëèöó−ξx5x6−413x1−312x2−211x3−101x43−1−2x5010x6001Òàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé.
Âûáèðàåì â êà÷åñòâå âåäóùåãî ýëåìåíòz11 . Ïðåîáðàçîâàâ, ïîëó÷èì ñèìïëåêñòàáëèöó−ξx1x6−111x1010x211−1x3−101x40−10x531−2x6001Òåïåðü â êà÷åñòâå âåäóùåãî ýëåìåíòà âûáèðàåì z32 . Ïîñëå ïðåîáðàçîâàíèÿ ïîëó÷èì ñèìïëåêñòàáëèöóx1 x2 x3 x4 x5 x6−ξ 0 00001 1x1 1 110 −1 1 0x3 1 0 −1 10 −2 1Òàáëèöà ïðÿìî è äâîéñòâåííî äîïóñòèìà. Ïîëó÷åíî îïòèìàëüíîå ðåøåíèå âñïîìîãàòåëüíîé çàäà÷è. Ïðè ýòîì ξ ∗ = −z00 = 0. Íà øàãå 2 â òàáëèöå ïðîèçîéäåò óäàëåíèå íóëåâîéñòðîêè è äâóõ ïîñëåäíèõ ñòîëáöîâ, ñîîòâåòñòâóþùèõ èñêóññòâåííûì ïåðåìåííûì.  áàçèñå ïðèñóòñòâóþò òîëüêî ïåðåìåííûå èñõîäíîé çàäà÷è.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
