1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 10
Текст из файла (страница 10)
Âûðàçèì áàçèñíûå ïåðåìåííûå x2 è x3 èç îãðàíè÷åíèé ðàâåíñòâ ÷åðåçíåáàçèñíûå ïåðåìåííûå x1 è x4 . Ïîëó÷èìx2 − 1/2x1 + 1/2x4 = 1,x3 + 1/2x1 + 1/2x4 = 1.Èñêëþ÷èì áàçèñíûå ïåðåìåííûå èç öåëåâîé ôóíêöèè, âûðàçèâ å¼ òîëüêî ÷åðåç íåáàçèñíûåïåðåìåííûå:w(x) = −x1 − 2(1/2x1 − 1/2x4 + 1) − 3(−1/2x1 − 1/2x4 + 1) + x4 = −5 − 1/2x1 + 7/2x4 .Ïðåäñòàâèì ýòî ðàâåíñòâî â óäîáíîì âèäå:−w − 1/2x1 + 7/2x4 = 5.Ñèìïëåêñòàáëèöà èìååò òàêîé èñõîäíûé âèä:−wx2x3x1−1/2−1/21/2511x2010x3001x47/21/21/2Áàçèñ íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìûì, òàê êàê ýëåìåíò z01 = −1/2 îòðèöàòåëåí.Ðàññìàòðèâàåìûé áàçèñ íåâûðîæäåí (z10 = 1, z20 = 1), è, ñëåäîâàòåëüíî, çíà÷åíèå öåëåâîéôóíêöèè ìîæíî óëó÷øèòü. Âçÿâ â êà÷åñòâå âåäóùåãî ïåðâûé ñòîëáåö (s = 1), íàõîäèìâåäóùóþ ñòðîêó: r = 2, òàê êàê òîëüêî z21 = 1/2 > 0. Ïðåîáðàçîâàâ èñõîäíóþ òàáëèöó ñâåäóùèì ýëåìåíòîì z21 , ïðèä¼ì ê íîâîìó áàçèñó B 1 = (A1 , A2 ) è òàáëèöå−wx2x1622x1001x201038x3112x4411Òàê êàê òàáëèöà ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé, òî áàçèñ B 1 îïòèìàëåí è â ñîîòâåòñòâèè ñ òàáëèöåé ïîëó÷àåì, ÷òî x∗ = (2, 2, 0, 0)> è w(x∗ ) = −6, òàê êàê x∗ = (z20 , z10 , 0, 0)> ,w(x∗ ) = −z00 .Ïðèìåð 2.
Ðåøèòü çàäà÷ów(x) = −x1 − 2x2 + x3 − x4 → min,x1 + x2 − 2x3 + 3x4 = 1,2x1 − x2 − x3 + 3x4 = 2,xj ≥ 0, j = 1, 2, 3, 4,>âçÿâ â êà÷åñòâå èñõîäíîãî ðåøåíèÿ òî÷êó³ ´x = (0, 0,³ 1,´ 1) .3Ðåøåíèå. Òàê êàê ñòîëáöû A3 = −2−1 , A4 = 3 ëèíåéíî íåçàâèñèìû, òî èìååì áàçèñB 0 = (A3 , A4 ) è x áàçèñíîå äîïóñòèìîå ðåøåíèå. Ñòðîèì ñèìïëåêñòàáëèöó, ñîîòâåòñòâóþùóþ íóëåâîìó øàãó àëãîðèòìà.
 ðåçóëüòàòå ïðåîáðàçîâàíèé, àíàëîãè÷íûõ ïðåîáðàçîâàíèÿì â ïðèìåðå 1, ïîëó÷èì ðàâåíñòâàx3 + x1 − 2x2 = 1,x4 + x1 − x2 = 1,−w − x1 − x2 = 0,êîòîðûì ñîîòâåòñòâóåò òàáëèöà−wx3x4011x1−111x2−1−2−1x3010x4001Òàê êàê áàçèñ íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìûì (íàïðèìåð, z01 = −1 < 0) è íåâûðîæäåí, òî çíà÷åíèå öåëåâîé ôóíêöèè ìîæíî óëó÷øèòü, âûáðàâ â êà÷åñòâå âåäóùåãîïåðâûé ñòîëáåö (s = 1).
 êà÷åñòâå âåäóùåé ñòðîêè ìîæíî âûáðàòü ëþáóþ èç ñòðîê (r = 1èëè r = 2), ïîñêîëüêó© zi0ªz20z10== 1 = min| zis > 0 .z11z21zisÏóñòü âûáðàíî r = 1, è z11 = 1 âåäóùèé ýëåìåíò. Ïðåîáðàçîâàâ áàçèñ B 0 â áàçèñB 1 = (A1 , A4 ), ïîëó÷èì òàáëèöó−wx1x4B1110x1010x2−3−21x311−1x4001Çäåñü îäíîçíà÷íî â êà÷åñòâå âåäóùåãî ýëåìåíòà âûáèðàåòñÿ z22 = 1. Ïðåîáðàçîâàâ áàçèñâ áàçèñ B 2 = (A1 , A2 ), ïðèäåì ê òàáëèöå−wx1x2110x1010x200139x3−2−1−1x4321Çàìåòèì, ÷òî ïðîèçîøëî òîëüêî èçìåíåíèå áàçèñà.
Ðåøåíèå îñòàëîñü ïðåæíèì x =(1, 0, 0, 0)> . Ýòî ñâÿçàíî ñ òåì, ÷òî ýòî ðåøåíèå âûðîæäåííîå (z02 = 0).  äàííîé òàáëèöåâûáðàòü âåäóùèé ýëåìåíò óæå íå óäàåòñÿ. È íà øàãå 3 àëãîðèòìà âû÷èñëåíèÿ ïðåêðàùàþòñÿ: z03 = −2 < 0 è z13 = z23 = −1 < 0. Öåëåâàÿ ôóíêöèÿ w(x) íå îãðàíè÷åíà ñíèçó íàìíîæåñòâå äîïóñòèìûõ ðåøåíèé.Äàííûé ïðèìåð ïîêàçûâàåò, ÷òî áîëåå ïîäðîáíûé àíàëèç òåêóùåé ñèìïëåêñòàáëèöûìîæåò ïðèâåñòè ê ñóùåñòâåííîìó ñîêðàùåíèþ âû÷èñëåíèé.
Åñëè áû â èñõîäíîé ñèìïëåêñòàáëèöå áûëî áû çàìå÷åíî, ÷òî âî âòîðîì ñòîëáöå íåò ïîëîæèòåëüíûõ ýëåìåíòîâ è z02 =−1 < 0, òî íå ïðèøëîñü áû äâàæäû ìåíÿòü áàçèñ.Ïðèìåð 3. Ðåøèòü çàäà÷ów(x) = −x3 + x4 − x5 + x6 → min,x1 + x3 − 2x4 − 3x5 + 4x6 = 0,x2 + 4x3 − 3x4 − 2x5 + x6 = 0,x3 + x4 + x5 + x6 + x7 = 1,xj ≥ 0, j = 1, 2, .
. . , 7.Ðåøåíèå. Íåòðóäíî çàìåòèòü, ÷òî â êà÷åñòâå èñõîäíîãî ìîæíî âûáðàòü áàçèñ B 0 =(A1 , A2 , A7 ), ïðè ýòîì èìååì áàçèñíîå äîïóñòèìîå ðåøåíèå x = (0, 0, 0, 0, 0, 0, 1)> . Äàííîåðåøåíèå, î÷åâèäíî, âûðîæäåííîå.Òàê êàê áàçèñíûå ïåðåìåííûå x1 , x2 è x7 íå ñîäåðæàòñÿ â öåëåâîé ôóíêöèè è ðàâåíñòâàèìåþò òðåáóåìûé äëÿ ïîñòðîåíèÿ ñèìïëåêñòàáëèöû âèä, òî ñðàçó ïîëó÷àåì ñèìïëåêñòàáëèöó:x1 x2 x3 x4 x5 x6 x7−w 0 00 −1 1 −1 1 0x1 0 101 −2 −3 4 0x2 0 014 −3 −2 1 0x7 1 001111 1Âûáèðàåì s = 3, r = 1 è ïåðåõîäèì ê áàçèñó B 1 = (A2 , A3 , A7 ), ïðè ýòîì áàçèñíîåðåøåíèå íå èçìåíèòñÿ, òàê êàê z01 = 0.−wx3x2x70001x111−4−1x20010x30100x4−1−253x5−4−3104x654−15−3x70001Âûáèðàåì s = 4, r = 2 è ïåðåõîäèì ê áàçèñó B 2 = (A3 , A4 , A7 ).
Áàçèñíîå ðåøåíèå âíîâüíå èçìåíèòñÿ:x1x2x3 x4 x5 x6 x7−w 0 1/51/500 −2 2 0x3 0 −3/5 2/5101 −2 0x4 0 −4/5 1/5012 −3 0x7 1 7/5 −3/5 00 −2 6 1Çäåñü ìîæíî âçÿòü s = 5, r = 1. Áàçèñó B 3 = (A4 , A5 , A7 ) ñîîòâåòñòâóåò òàáëèöà−wx5x4x70001x1−1−3/52/51/5x212/5−3/51/5x321−2240x40010x50100x6−2−212x70001ñ òåì æå áàçèñíûì ðåøåíèåì.Òåïåðü âîçüì¼ì s = 6, r = 2. Ïîëó÷èì áàçèñ B 4 = (A5 , A6 , A7 ) è òàáëèöó−wx5x6x70001x1−1/51/52/5−3/5x2−1/5−4/5−3/57/5x3−2−3−26x4221−2x50100x60010x70001Áàçèñíîå ðåøåíèå è çäåñü íå èçìåíèëîñü.Ïóñòü òåïåðü s = 1, r = 1. Íîâûé áàçèñ B 5 = (A1 , A6 , A7 ) ñ ñîîòâåòñòâóþùåé òàáëèöåé èòåì æå ðåøåíèåì:x1 x2x3x4 x5 x6 x7−w 0 0 −1 −5410 0x1 0 1 −4 −15 1050 0x6 0 014−3 −2 1 0x7 1 0 −1 −3430 1Âûáðàâ s = 2, r = 2, ïðèä¼ì ê áàçèñó B 6 = (A1 , A2 , A7 ) = B 0 , ò. å.
ïðîèçîøåë âîçâðàò êèñõîäíîìó áàçèñó.  ýòîì ñëó÷àå ãîâîðÿò, ÷òî öèêë çàìêíóëñÿ è ïðîèçîøëî çàöèêëèâàíèåàëãîðèòìà. Ðåøåíèå ïîëó÷èòü íå óäàëîñü.Ïðèìåð 4. Ðåøèòü çàäà÷ów(x) = −7x1 − x3 + x4 − x5 → min,x1 − x2 + x3 = 1,2x1 + 2x2 + x3 + x4 + 2x5 = 12,2x1 + x2 + x5 = 4,xj ≥ 0, j = 1, 2, . . . , 5,âçÿâ â êà÷åñòâå èñõîäíîãî áàçèñà B 0 = (A3 , A4 , A5 ).Ðåøåíèå. Ïîäñòàâèì x3 èç ïåðâîãî ðàâåíñòâà è x5 èç òðåòüåãî âî âòîðîå, ïîëó÷èì−3x1 + x2 + x4 = 3.Èñêëþ÷èì áàçèñíûå ïåðåìåííûå x3 , x4 è x5 èç öåëåâîé ôóíêöèè:w(x) = −7x1 − (1 − x1 + x2 ) + (3 + 3x1 − x2 ) − (4 − 2x1 − x2 ) = −2 − x1 − x2 .Ïåðåïåøåì âñå óñëîâèÿ â âèäå, óäîáíîì äëÿ çàïîëíåíèÿ ñèìïëåêñòàáëèöû:x3 + x1 − x2 = 1,x4 − 3x1 + x2 = 3,x5 + 2x1 + x2 = 4,−w − x1 − x2 = 2.Èñõîäíàÿ ñèìïëåêñòàáëèöà, ñîîòâåòñòâóþùàÿ áàçèñó B 0 è äîïóñòèìîìó áàçèñíîìó ðåøåíèþ x = (0, 0, 1, 3, 4)> , èìååò âèä−wx3x4x52134x1−11−32x2−1−11141x30100x40010x50001Òàê êàê èìåþòñÿ îòðèöàòåëüíûå ýëåìåíòû â âåðõíåé ñòðîêå: z01 = z02 = −1, òî òàáëèöàíå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé.
Ïîýòîìó âûáèðàåì âåäóùèé ñòîëáåö s. Ïóñòü s = 1.Ïîñëå ýòîãî ïåðåõîäèì íà øàã 3. Òàê êàê ìíîæåñòâî {i | zi1 > 0} íå ïóñòî, òî íàõîäèìâåäóùóþ ñòðîêó:nzon1 4oz10i0= 1 = min| zi1 > 0 = min ,.z11zi11 2Òàêèì îáðàçîì, r = 1 è âåäóùèì ÿâëÿåòñÿ ýëåìåíò z11 . Íîâûé áàçèñ B 1 = (A1 , A4 , A5 ).Ïðîâåäÿ ýëåìåíòàðíîå ïðåîáðàçîâàíèå áàçèñà, ïîëó÷èì òàáëèöó−wx1x4x53162x10100x2−2−1−23x3113−2x40010x50001Îíà òàêæå íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé.
Îäíîçíà÷íî ïîëó÷àåì s = 2, r = 3. Ïåðåõîäèì ê íîâîìó áàçèñó B 2 = (A1 , A2 , A4 ), êîòîðîìó ñîîòâåòñòâóåò òàáëèöà−wx1x4x213/35/322/32/3x10100x20001x3−1/31/35/3−2/3x40010x52/31/32/31/3 êà÷åñòâå âåäóùåãî òåïåðü âûáèðàåì ýëåìåíò z23 = 5/3, òàê êàê z03 = −1/3 < 0 èz2022z10=<= 5.z235z13 ðåçóëüòàòå ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ ïåðåõîäèì ê áàçèñó B 3 = (A1 , A2 , A3 ) è òàáëèöå−wx1x3x229/51/522/518/5x10100x20001x30010x41/5x54/5Ïðè ýòîì òàê êàê ïîëó÷èëàñü äâîéñòâåííî äîïóñòèìàÿ òàáëèöà, òî ïîñëå âû÷èñëåíèÿ íóëåâîé ñòðîêè (ýëåìåíòîâ z0j , j = 1, n) äîñòàòî÷íî âû÷èñëèòü ýëåìåíòû íóëåâîãî ñòîëáöàzi0 (i = 0, m) è íà ýòîì çàâåðøèòü ðåøåíèå çàäà÷è.Îïòèìàëüíîå ðåøåíèå ïîëó÷åíî, è îíî ëåãêî îïðåäåëÿåòñÿ èç âû÷èñëåííîé ÷àñòè òàáëèöû: xσ(i) = zi0 , i = 1, m, à âñå íåáàçèñíûå ïåðåìåííûå ðàâíû íóëþ, ïðè ýòîì w(x) = −z00 ,ò. å.
â ðàññìàòðèâàåìîì ñëó÷àå x = (1/5, 18/5, 22/5, 0, 0), w(x) = −29/5.Çàäà÷è1. Ïðèâåñòè çàäà÷ó ê êàíîíè÷åñêîìó âèäó, ðåøèòü åå ñèìïëåêñìåòîäîì è äàòü ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ êàæäîãî øàãà â ïðîñòðàíñòâå ïåðåìåííûõ:1) −x1 − x2 −→ min,x1 − x2 ≤ 1, 5x1 + x2 ≤ 1,x1 ≥ 0, x2 ≥ 0;422) −x1 + 2x2 −→ min,x1 + x2 ≤ 12, x1 − x2 ≤ 8,x1 ≥ 0, x2 ≥ 0.2. Ðåøèòü çàäà÷ó ñèìïëåêñìåòîäîì, âçÿâ â êà÷åñòâå èñõîäíîãî áàçèñíîãî äîïóñòèìîãîðåøåíèÿ òî÷êó x:1) −6x1 − x2 − 4x3 + 5x4 −→ min,3x1 + x2 − x3 + x4 = 4, 5x1 + x2 + x3 − x4 = 4,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (1, 0, 0, 1)> ;2) −x1 − 2x2 − 3x3 + x4 −→ min,x1 − 3x2 − x3 − 2x4 = −4, x1 − x2 + x3 = 0,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (0, 1, 1, 0)> ;3) −x1 − x2 − x3 − x4 −→ min,x1 + x2 + x3 + 3x4 = 3, x1 + x2 − x3 + x4 = 1, x1 − x2 + x3 + x4 = 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (0, 0, 0, 1)> ;4) −x1 − 2x2 − x3 − 3x4 − x5 −→ min,x1 + x2 + 2x4 + x5 = 5, x1 + x2 + x3 + 3x4 + 2x5 = 9, x2 + x3 + 2x4 + x5 = 6,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,x = (0, 0, 1, 2, 1)> ;5) −x1 + x2 − 2x3 + x4 − x5 −→ min,x1 + x2 + 2x3 + 3x4 − 2x5 = 3, x2 − x3 − x4 − x5 = 0, x1 + x4 − x5 = 0,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,x = (0, 2, 0, 1, 1)> ;6) −x1 − 2x2 − 2x3 − x4 − 6x5 −→ min,x1 + 3x2 + 3x3 + x4 + 9x5 = 18, x1 + 5x2 + 2x4 + 8x5 = 13, x3 + x5 = 3,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,x = (0, 1, 2, 0, 1)> ;7) −x1 − x2 − x3 − x4 − x5 −→ min,x1 + x2 + 2x3 = 4, −2x2 − 2x3 + x4 − x5 = −6, x1 − x2 + 6x3 + x4 + x5 = 12,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,x = (1, 1, 2, 0, 0)> .434.5 Ëåêñèêîãðàôè÷åñêèé âàðèàíò ïðÿìîãî ñèìïëåêñìåòîäàÝòîò ìåòîä ïîçâîëÿåò óñòðàíèòü çàöèêëèâàíèå è çà êîíå÷íîå ÷èñëî øàãîâ ïîëó÷èòüðåøåíèå.Îïðåäåëåíèå.
Íåíóëåâîé âåêòîð α = (z0 , z1 , . . . , zn ) ëåêñèêîãðàôè÷åñêè áîëüøå íóëÿ(α  0), åñëè ïåðâàÿ îòëè÷íàÿ îò íóëÿ êîìïîíåíòà ïîëîæèòåëüíà: zp > 0, ãäå p = min{i |zi 6= 0}.Åñëè α0 , α00 ∈ En+1 , òî ñ÷èòàåòñÿ, ÷òî âåêòîð α0 ëåêñèêîãðàôè÷åñêè áîëüøå âåêòîðà α000(α  α00 ), åñëè α0 − α00  0.Òåì ñàìûì íà En+1 îïðåäåëåíî îòíîøåíèå ëèíåéíîãî ïîðÿäêà, òàê ÷òî â ëþáîé êîíå÷íîéñîâîêóïíîñòè âåêòîðîâ {αi } èìååòñÿ ëåêñèêîãðàôè÷åñêè ìèíèìàëüíûé âåêòîð, îáîçíà÷àåìûé lex min{αi }.Îïðåäåëåíèå. Ñèìïëåêñòàáëèöà íàçûâàåòñÿ íîðìàëüíîé, åñëè åå ñòðîêè αi = (zi0 ,zi1 , . . . , zin ), i = 1, m, ëåêñèêîãðàôè÷åñêè ïîëîæèòåëüíû.Óòâåðæäåíèå 11. Ëþáóþ ïðÿìî äîïóñòèìóþ ñèìïëåêñòàáëèöó ìîæíî ïðåîáðàçîâàòüâ íîðìàëüíóþ ïóòåì ïåðåíóìåðàöèè ïåðåìåííûõ (ñ ñîîòâåòñòâóþùåé ïåðåñòàíîâêîé ñòîëáöîâ).Ïðè ýòîì î÷åâèäíî, ÷òî íîðìàëüíàÿ ñèìïëåêñòàáëèöà ÿâëÿåòñÿ ïðÿìî äîïóñòèìîé.Îòëè÷èÿ ëåêñèêîãðàôè÷åñêîãî âàðèàíòà ïðÿìîãî ñèìïëåêñìåòîäà îò îáû÷íîãî êàñàþòñÿ òîëüêî 0-ãî è 3-ãî øàãîâ (îñòàëüíûå øàãè îñòàþòñÿ áåç èçìåíåíèé):00 ) Íà÷àòü ñ íîðìàëüíîé ñèìïëåêñòàáëèöû.30 ) Åñëè {i | zis > 0, i ≥ 1} 6= ∅, òî âûáðàòü âåäóùóþ ñòðîêó r:n 1o1αr = lex minαi | zis > 0, i ≥ 1 ,zrszisèíà÷å ÊÎÍÅÖ (çàäà÷à íåðàçðåøèìà).Ýëåìåíòàðíîå ïðåîáðàçîâàíèå áàçèñà ïðè ýòîì ñîõðàíÿåò íîðìàëüíîñòü ñèìïëåêñòàáëèöû.Óòâåðæäåíèå 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
