1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 12
Текст из файла (страница 12)
Íà ýòîì ïåðâûé ýòàï àëãîðèòìàñèìïëåêñìåòîäà çàâåðø¼í. Ïåðåõîäèì íà øàã 7. Âûðàçèì ÷åðåç íåáàçèñíûå ïåðåìåííûåöåëåâóþ ôóíêöèþ w(x). Èç ïîñëåäíåé ñèìïëåêñòàáëèöû èìååì ðàâåíñòâàx1 + x2 − x4 = 1,−x2 + x3 = 1,ò. å.w(x) = −2(1 − x2 + x4 ) − 7x2 + (1 + x2 ) + 4x4 = −1 − 4x1 + 2x4 .49Ïîëó÷èì ïðÿìî äîïóñòèìóþ ñèìïëåêñòàáëèöó èñõîäíîé çàäà÷è ñ áàçèñîì B = (A1 , A3 ) èñîîòâåòñòâóþùèì ðåøåíèåì x = (1, 0, 1, 0)−wx1x3−111x1010x2−41−1x3001x42−10Òåïåðü ïåðåõîäèì íà øàã 8. Òàê êàê ñèìïëåêñòàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé,òî âûáèðàåì s = 2, r = 1.
Ïðåîáðàçóåì òàáëèöó ñ âåäóùèì ýëåìåíòîì z12 = 1 è îêîí÷àòåëüíîïðèõîäèì ê ïðÿìî äîïóñòèìîé òàáëèöå ñ îòðèöàòåëüíûì ïîñëåäíèì ñòîëáöîì−wx2x3312x1411x2010x3001x4−2−1−1Òàêèì îáðàçîì, öåëåâàÿ ôóíêöèÿ èñõîäíîé çàäà÷è íåîãðàíè÷åíà ñíèçó. Ñëåäîâàòåëüíî, îïòèìàëüíîãî ðåøåíèÿ íå ñóùåñòâóåò.Ïðèìåð 3. Ðåøèòü çàäà÷óx1 − x2 + x3 − x4 + 3x5 → min,x1 + x4 + 2x5 = 1,−x2 − x3 + x4 + 2x5 = 2,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 = 2,2x1 − 3x2 + x3 + x4 + x8 = 0,xj ≥ 0 (j = 1, . . . , 8),ñ áàçèñíûì äîïóñòèìûì ðåøåíèåì x = (0, 0, 0, 0, 0, 1, 2, 0)> . Èñêëþ÷èì áàçèñíûå ïåðåìåííûåèç öåëåâîé ôóíêöèè ýòîé çàäà÷è è ïîëó÷èì èñõîäíóþ ñèìïëåêñòàáëèöó−ξx6x7x8−3120x1−3102x240−1−3x300−11x4−3111x5−4220x60100x70010x80001Òàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé.
Âûáèðàåì â êà÷åñòâå âåäóùåãî ýëåìåíò z34 =1. Ïðåîáðàçîâàâ, ïîëó÷èì ñèìïëåêñòàáëèöó−ξx6x7x4−3120x13−1−22x2−532−3x33−1−21x4000150x5−4220x60100x70010x83−1−11Òåïåðü â êà÷åñòâå âåäóùåãî ýëåìåíòà âûáèðàåì z15 = 2. Ïîñëå ïðåîáðàçîâàíèÿ ïîëó÷èìñèìïëåêñòàáëèöó−ξx5x7x4−11/210x11−1/2−12x213/2−1−3x31−1/2−11x40001x50100x621/2−10x70010x81−1/201Òàáëèöà ïðÿìî è äâîéñòâåííî äîïóñòèìà. Ïîëó÷åíî îïòèìàëüíîå ðåøåíèå âñïîìîãàòåëüíîé çàäà÷è. Òàê êàê ξ ∗ = −z00 = 1 > 0, òî èñõîäíàÿ çàäà÷à íåðàçðåøèìà èç-çà íåñîâìåñòíîñòè îãðàíè÷åíèé.Ïðèìåð 4.
Ðåøèòü çàäà÷ó−x1 − 4x2 − x3 → min,x1 + x2 + x3 = 2,−2x1 + x2 − x3 = −1,3x1 + 2x3 = 3,xj ≥ 0 (j = 1, 2, 3).Ðåøåíèå. Áóäåì èñêàòü íà÷àëüíîå áàçèñíîå äîïóñòèìîå ðåøåíèå ìåòîäîì èñêóññòâåííîãî áàçèñà. Äëÿ ýòîãî äîìíîæèì âòîðîå îãðàíè÷åíèåðàâåíñòâî íà −1 è äîáàâèì èñêóññòâåííûå ïåðåìåííûå x4 , x5 è x6 . Ïîëó÷èì âñïîìîãàòåëüíóþ çàäà÷óx4 + x5 + x6 → min,x1 + x2 + x3 + x4 = 2,2x1 − x2 + x3 + x5 = 1,3x1 + 2x3 + x6 = 3,xj ≥ 0 (j = 1, 6)ñ áàçèñíûì äîïóñòèìûì ðåøåíèåì x = (0, 0, 0, 2, 1, 3)> . Èñêëþ÷èì áàçèñíûå ïåðåìåííûåx4 , x5 è x6 èç öåëåâîé ôóíêöèè ýòîé çàäà÷è:ξ = (2 − x1 − x2 − x3 ) + (1 − 2x1 + x2 − x3 ) + (3 − 3x1 − 2x3 ) = 6 − 6x1 − 4x3 .Äàííîå ðàâåíñòâî çàïèøåì â ïðèíÿòîì âèäå−ξ − 6x1 − 4x3 = −6.Ïîëó÷àåì èñõîäíóþ (ïåðâóþ) ñèìïëåêñòàáëèöó−ξx4x5x6−6213x1−6123x201−1051x3−4112x40100x50010x60001Òàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé.
Âûáèðàåì âåäóùèé ñòîëáåö s. Ïóñòü s = 3.Âûáèðàåì âåäóùóþ ñòðîêó. Ïîëó÷àåì r = 2 è, ñëåäîâàòåëüíî, âåäóùèé ýëåìåíò z23 = 1. Ïåðåõîäèì ê íîâîìó áàçèñó, êîòîðîìó ñîîòâåòñòâóåò ñëåäóþùàÿ (âòîðàÿ) ñèìïëåêñòàáëèöà:−ξx4x3x6−2111x12−12−1x2−42−12x30010x40100x54−11−2x60001Òàáëèöà âñå åù¼ íå äâîéñòâåííî äîïóñòèìà. Âûáèðàåì â êà÷åñòâå âåäóùåãî ýëåìåíò z32 .Ïðåîáðàçîâàâ, ïîëó÷èì òðåòüþ òàáëèöó−ξx4x3x2003/21/2x1003/2−1/2x20001x30010x40100x5010−1x62−11/21/2Òàáëèöà ïðÿìî è äâîéñòâåííî äîïóñòèìà. Ïîëó÷åíî îïòèìàëüíîå ðåøåíèå âñïîìîãàòåëüíîéçàäà÷è. Ïðè ýòîì ξ ∗ = −z00 = 0. Ïîýòîìó íà øàãå 2 â òàáëèöå ïðîèçîéäåò óäàëåíèå íóëåâîéñòðîêè è òð¼õ ïîñëåäíèõ ñòîëáöîâ, ñîîòâåòñòâóþùèõ èñêóññòâåííûì ïåðåìåííûì:x4x3x203/21/2x103/2−1/2x2001x3010 ÷èñëå áàçèñíûõ îñòàëàñü èñêóññòâåííàÿ ïåðåìåííàÿ x4 , ïðè ýòîì â ñòðîêå, ñîîòâåòñòâóþùåé åé, èìåþòñÿ òîëüêî íóëåâûå ýëåìåíòû. Çíà÷èò, ýòó ñòðîêó ìîæíî óäàëèòü.
Èñõîäíàÿìàòðèöà èìååò ðàíã, ðàâíûé 2. Äåéñòâèòåëüíî, åñëè âåðíóòüñÿ ê ïðåäïîñëåäíåé ñèìïëåêñòàáëèöå è ïåðåïèñàòü ñòðîêó, ñîîòâåòñòâóþùóþ áàçèñíîé ïåðåìåííîé x4 , â âèäå ðàâåíñòâàx4 + x5 = x6 , òî ñðàçó îáíàðóæèì, ÷òî òðåòüå îãðàíè÷åíèåðàâåíñòâî â èñõîäíîé çàäà÷åÿâëÿåòñÿ ñóììîé ïåðâûõ äâóõ, ò.
å. îíè ëèíåéíî çàâèñèìû.Ïîñëå óäàëåíèÿ ñòðîêè â áàçèñå îñòàëèñü òîëüêî ïåðåìåííûå èñõîäíîé çàäà÷è. Ïåðåõîäèì íà øàã 7. Âûðàçèì ÷åðåç íåáàçèñíûå ïåðåìåííûå öåëåâóþ ôóíêöèþ w(x). Èç ïîñëåäíåéñèìïëåêñòàáëèöû èìååì ðàâåíñòâà3/2x1 + x3 = 3/2,−1/2x1 + x2 = 1/2,ò. å.w(x) = −x1 − 4(1/2 + 1/2x1 ) − (3/2 − 3/2x1 ) = −7/2 − 3/2x1 .Äîáàâëÿåì íóëåâóþ ñòðîêó −w − 3/2x1 = 7/2 ê ïðåäûäóùåé òàáëèöå (ó÷òèòå, ÷òî ïåðâàÿñòðîêà âû÷åðêíóòà)x1x2 x3−w 7/2 −3/2 00x3 3/2 3/201x2 1/2 −1/2 10Ïîëó÷èì ïðÿìî äîïóñòèìóþ ñèìïëåêñòàáëèöó (ïÿòóþ)èñõîäíîé çàäà÷è ñ áàçèñîì B =(A2 , A3 ) è ñîîòâåòñòâóþùèì ðåøåíèåì x = (0, 1/2, 3/2).
Òåïåðü ïåðåõîäèì íà øàã 8 è èùåì52îïòèìàëüíîå ðåøåíèå. Òàê êàê ñèìïëåêñòàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé, òîâûáèðàåì s = 1, r = 1. Ïðåîáðàçóåì òàáëèöó ñ âåäóùèì ýëåìåíòîì z11 = 3/2 è îêîí÷àòåëüíîïðèõîäèì ê ïðÿìî è äâîéñòâåííî äîïóñòèìîé òàáëèöå−wx1x2511x1010x2001x312/31/3èç êîòîðîé ñëåäóåò, ÷òî x∗ = (1, 1, 0), w(x∗ ) = −5.Çàäà÷èÐåøèòü çàäà÷ó ñèìïëåêñìåòîäîì, íàéäÿ íà÷àëüíîå áàçèñíîå äîïóñòèìîå ðåøåíèå ìåòîäîì èêóññòâåííîãî áàçèñà:1) −x1 + 4x2 − 3x3 − 10x4 −→ min,x1 + x2 − x3 + x4 = 0, x1 + 14x2 + 10x3 − 10x4 = 11,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;2) −x1 + 5x2 + x3 − x4 −→ min,x1 + 3x2 + 3x3 + x4 ≤ 3, 2x1 + 3x3 − x4 ≤ 4,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;3) −x1 − 10x2 + x3 − 5x4 −→ min,x1 + 2x2 − x3 − x4 = 1, −x1 + 2x2 + 3x3 + x4 = 2, x1 + 5x2 + x3 − x4 = 5,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;4) −x1 − x2 − x3 − x4 −→ min,4x1 + 2x2 + 5x3 − x4 = 5, 5x1 + 3x2 + 6x3 − 2x4 = 5, 3x1 + 2x2 + 4x3 − x4 = 4,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;5) −x1 − x2 + x3 − x4 + 2x5 −→ min,3x1 +x2 +x3 +x4 −2x5 = 10, 6x1 +x2 +2x3 +3x4 −4x5 = 20, 10x1 +x2 +3x3 +6x4 −7x5 = 30,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0;6) −x1 − 2x2 − 3x3 − 4x4 − 5x5 −→ min,x2 + x3 − 2x4 + 7x5 = 2, x1 + x3 − 2x4 − 6x5 = 2, x1 + x2 − 2x4 + 7x5 = 2,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.4.7.
Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ñèìïëåêñìåòîäàÏðåäñòàâëÿåò èíòåðåñ ãåîìåòðè÷åñêàÿ èíòåðïåòàöèÿ ñèìïëåêñìåòîäà è, â ÷àñòíîñòè,ìåòîäà èñêóññòâåííîãî áàçèñà. Ïîñêîëüêó áàçèñíîå äîïóñòèìîå ðåøåíèå ýòî êðàéíÿÿ òî÷êà äîïóñòèìîãî ìíîæåñòâà X , à ëþáàÿ êðàéíÿÿ òî÷êà x ýòî áàçèñíîå äîïóñòèìîå ðåøåíèå(ñì. óòâåðæäåíèå 2), òî ñèìïëåêñìåòîä ãåîìåòðè÷åñêè ïðåäñòàâëÿåò ñîáîé íàïðàâëåííîåäâèæåíèå ïî âåðøèíàì ìíîãîãðàííîãî ìíîæåñòâà.Ïóñòü âûáðàí áàçèñ B = (A1 , . . . , Am ), òîãäà áàçèñíîå äîïóñòèìîå ðåøåíèå çàäà¼òñÿðàâåíñòâàìèxB + B −1 N xN = B −1 b, xN = 0,(∗)53ãäå B −1 b ≥ 0. Èìååì m + (n − m) = n óñëîâèé, êîòîðûå çàäàþò íåêîòîðóþ âåðøèíó ìíîãîãðàííîãî ìíîæåñòâà X , à èìåííî x = (B −1 b, 0).
Ïðè ýòîì åñëè ýòó òî÷êó ðàññìàòðèâàòü âêà÷åñòâå íà÷àëà êîîðäèíàò, òî, ïîñëåäîâàòåëüíî óáèðàÿ ïî îäíîé íåáàçèñíîé ïåðåìåííîé èçóñëîâèé xk = 0, ïîëó÷àåì n − m îñåé, ïðîõîäÿùèõ ÷åðåç òî÷êó x. Åñëè óáèðàåòñÿ óñëîâèåxs = 0, ãäå s ∈ J \ {1, . . . , m}, òî ïîëó÷àåì îñü xs , âäîëü êîòîðîé ìåíÿåòñÿ çíà÷åíèå ýòîéïåðåìåííîé. Ïîëîæèòåëüíîå íàïðàâëåíèå ñîîòâåòñòâóåò ïîëóïðîñòðàíñòâó xs ≥ 0.
Âûáîðâåäóùåãî ñòîëáöà s îçíà÷àåò, ÷òî â êà÷åñòâå îñè, ïî êîòîðîé ïðîèçîéä¼ò äâèæåíèå â íîâóþâåðøèíó, âûáðàíà îñü xs . Åñëè z0s < 0, òî ýòî ãîâîðèò î òîì, ÷òî ïðè äâèæåíèè â ïîëîæèòåëüíîì íàïðàâëåíèè îñè xs çíà÷åíèå öåëåâîé ôóíêöèè w(x) óáûâàåò. Âûáîð âåäóùåéñòðîêè r(r ∈ {1, . . . , m}) ãåîìåòðè÷åñêè îçíà÷àåò, ÷òî äâèæåíèå ïðîèçîéäåò äî âåðøèíû,îïðåäåëÿåìîé óñëîâèÿìè (∗), ãäå ðàâåíñòâî xs = 0 çàìåíåíî íà ðàâåíñòâî xr = 0, òàê êàêïåðåìåííàÿ xs ñòàíîâèòñÿ áàçèñíîé, à xr ïåðåõîäèò â íåáàçèñíûå ïåðåìåííûå. Åñëè xr áûëî óæå ðàâíî íóëþ (zr0 = 0 â áàçèñå B ), òî âåðøèíà îñòàíåòñÿ ïðåæíåé, íî ïðîèçîéäåòèçìåíåíèå ñèñòåìû êîîðäèíàò, ïðè ýòîì âìåñòî îñè xs ïîÿâèòñÿ îñü xr . Øàã 3 â àëãîðèòìåñèìïëåêñìåòîäà èç ïîäðàçä.
4.4 ðàçðåøàåò äâèæåíèå äî áëèæàéøåé â âûáðàííîì íàïðàâëåíèè ãèïåðïëîñêîñòè xr = 0, à âåëè÷èíà zr0 /zrs õàðàêòåðèçóåò âåëè÷èíó øàãà.Ðàññìîòðèì âñå ñêàçàííîå íà ïðèìåðå 4 èç ïîäðàçä. 4.6, èñïîëüçóÿ åñòåñòâåííóþ íóìåðàöèþ òàáëèö. Ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ ïðîâåä¼ì â ïðîñòðàíñòâå èñõîäíûõ ïåðåìåííûõ x1 , x2 è x3 . È, ãîâîðÿ î òî÷êå, áóäåì èìåòü â âèäó òî÷êó x = (x1 , x2 , x3 )> , à x4 , x5è x6 áóäåì íàçûâàòü âñïîìîãàòåëüíûìè ïåðåìåííûìè. Íà ðèñ. 1 óêàçàíû ãèïåðïëîñêîñòè,îïðåäåëÿåìûå ðàâåíñòâàìè:ai x = bi (i = 1, m),ãäå x ∈ En .  íàøåì ñëó÷àå i = 1, 2, 3, m = n = 3.
Æèðíàÿ ëèíèÿ, ñîåäèíÿþùàÿ òî÷êè (1, 1, 0)> è (0, 1/2, 3/2)> , ýòî äîïóñòèìîå ìíîæåñòâî X . Óêàçàí åù¼ ðÿä âñïîìîãàòåëüíûõ òî÷åê äëÿ ëó÷øåãî ïðåäñòàâëåíèÿ ñèòóàöèè. Ïðè ýòîì íóæíî ó÷èòûâàòü, ÷òîðàâåíñòâî xn+i = 0 (1 ≤ i ≤ m) ñîîòâåòñòâóåò ãèïåðïëîñêîñòè ai x = bi . Íà÷àëüíîå áàçèñíîå äîïóñòèìîå ðåøåíèå ñîîòâåòñòâóåò íà÷àëó êîîðäèíàò x1 = 0, x2 = 0, x3 = 0. Ýòàòî÷êà íå ïðèíàäëåæèò ìíîæåñòâó X , íî ÿâëÿåòñÿ äîïóñòèìîé âî âñïîìîãàòåëüíîé çàäà÷å:x4 = 2, x5 = 1, x6 = 3, ïðè÷¼ì çíà÷åíèÿ ýòèõ êîîðäèíàò õàðàêòåðèçóþò îòêëîíåíèÿ âûáðàííîé òî÷êè ñîîòâåòñòâåííî îò ïåðâîé, âòîðîé è òðåòüåé ãèïåðïëîñêîñòè, ïî îòíîøåíèþ ê êîòîðûì èñõîäíàÿ òî÷êà íàõîäèòñÿ â ïîëîæèòåëüíûõ ïîëóïðîñòðàíñòâàõ (xj ≥ 0 (j = 4, 5, 6)).Íà ïåðâîì ýòàïå íåîáõîäèìî ïîïàñòü íà ìíîæåñòâî X .54Ðèñ.
1Íåáàçèñíûìè ïåðåìåííûìè ÿâëÿþòñÿ x1 , x2 è x3 Èìååì òðè îñè, ñîîòâåòñòâóþùèå èì.Ïåðâàÿ ñèìïëåêñòàáëèöà ãîâîðèò î òîì, ÷òî íóæíî äâèãàòüñÿ ëèáî ïî îñè x1 (z01 = −6 <0), ëèáî ïî îñè x3 (z03 = −4 < 0). Âûáèðàåì äâèæåíèå ïî îñè x3 (s = 3). Äî êàêèõ ïîð ìîæíî äâèãàòüñÿ? Åñëè âûáðàòü r = 1, òî, ïðåîáðàçîâàâ ýòó òàáëèöó ñ âåäóùèì ýëåìåíòîì z13 ,ïîëó÷èì òî÷êó (0, 0, 2), â êîòîðîé âñïîìîãàòåëüíûå ïåðåìåííûå òàêîâû, ÷òî x5 = z20 = −1,x4 = 0, x6 = z30 = −1. Èíà÷å ãîâîðÿ, ìû ïîêèíóëè äîïóñòèìîå ìíîæåñòâî âñïîìîãàòåëüíîéçàäà÷è è ïîëó÷èëè íåäîïóñòèìûé áàçèñ.
Âåëè÷èíà zi0 /zis ïðè zis > 0 õàðàêòåðèçóåò ðàññòîÿíèå îò âåðøèíû, êîòîðîé ñîîòâåòñòâóåò ñèìïëåêñòàáëèöà, äî ãèïåðïëîñêîñòè xσ(i) = 0â ïîëîæèòåëüíîì íàïðàâëåíèè. Ïðèíÿòî äâèãàòüñÿ äî áëèæàéøåé ãèïåðïëîñêîñòè, ÷òî ãàðàíòèðóåò ïîïàäàíèå â äîïóñòèìóþ òî÷êó. Ïîýòîìó îïðåäåëÿåòñÿ òàêîå r, äëÿ êîòîðîãînzozr0i0= min| zis > 0 .1≤i≤m ziszrs íàøåì ñëó÷àå (ïðè s = 3) ýòî äà¼ò r = 2. Ïîñëå ïðåîáðàçîâàíèÿ óïîìÿíóòîé âûøå ñèìïëåêñòàáëèöû, ïîëó÷àåì âòîðóþ ñèìïëåêñòàáëèöó, êîòîðîé ñîîòâåòñòâóåò òî÷êà(0, 0, 1)> , ïðè ýòîì x4 = 1, x5 = 0, x6 = 1, ò. å.
ïîïàëè íà ãèïåðïëîñêîñòü 2x1 − x2 + x3 =1(x5 = 0). Ðàññìîòðèì äàííóþ òî÷êó áîëåå ïîäðîáíî.  ýòîé òî÷êå íåáàçèñíûå ïåðåìåííûåx1 , x2 è x5 . Îíè è îïðåäåëÿþò íîâóþ ñèñòåìó êîîðäèíàò, âîîáùå ãîâîðÿ, êîñîóãîëüíóþ. Îñüx1 çàäà¼òñÿ óñëîâèÿìè x2 = 0, x5 = 0, à å¼ íàïðàâëåíèå óñëîâèåì x1 ≥ 0. Àíàëîãè÷íî îïðåäåëÿþòñÿ îñòàëüíûå îñè. Ïîñêîëüêó îíè íå ñîâïàäàþò ñî ñòàðûìè îñÿìè, òî îáîçíà÷èì èõêàê x01 , x02 è x05 (ðèñ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
