1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 9
Текст из файла (страница 9)
. , m ñòîëáåöñ íîìåðîì σ(i) èìååò 1 â i-é ñòðîêå è 0 â îñòàëüíûõ ñòðîêàõ (åäèíè÷íûé âåêòîð). Êðîìåòîãî, z0σ(i) = 0 (i = 1, m).Ïåðåñòàíîâêîé ñòîëáöîâ è ñòðîê è ñîîòâåòñòâóþùåé ïåðåíóìåðàöèåé ïåðåìåííûõ ñèìïëåêñòàáëèöó ìîæíî ïðèâåñòè ê âèäó33−wx1:xi:xmz00z10:zi0:zm0x101:0:0...............xi00:1:0...............xm00:0:1xm+1z0m+1z1m+1:zim+1:zmm+1...............xnz0nz1n:zin:zmnÇäåñü σ(i) = i (i = 1, m). Áàçèñíîå ðåøåíèå, ñîîòâåòñòâóþùåå áàçèñó B , èìååò âèä xB =(z10 , z20 , . .
. , zm0 )> , xN = 0, à öåëåâàÿ ôóíêöèÿ w íà äàííîì ðåøåíèè ïðèíèìàåò çíà÷åíèåw(x) = −z00 .Îïðåäåëåíèå. Ñèìïëåêñòàáëèöà íàçûâàåòñÿ ïðÿìî äîïóñòèìîé, åñëè zi0 ≥ 0, i =1, . . . , m,. Áàçèñ B , êîòîðîìó ýòà òàáëèöà ñîîòâåòñòâóåò, òàêæå íàçûâàåòñÿ ïðÿìî äîïóñòèìûì.Îïðåäåëåíèå. Ñèìïëåêñòàáëèöà íàçûâàåòñÿ äâîéñòâåííî äîïóñòèìîé, åñëè z0j ≥0, j = 1, .
. . , n. Áàçèñ B , êîòîðîìó ýòà òàáëèöà ñîîòâåòñòâóåò, òàêæå íàçûâàåòñÿ äâîéñòâåííîäîïóñòèìûì.Óòâåðæäåíèå 5. Åñëè çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (5)(7) ðàçðåøèìà, òî óíåå ñóùåñòâóåò ïðÿìî è äâîéñòâåííî äîïóñòèìûé áàçèñ.Óòâåðæäåíèå 6 (äîñòàòî÷íîå óñëîâèå îïòèìàëüíîñòè). Åñëè ñèìïëåêñòàáëèöàïðÿìî è äâîéñòâåííî äîïóñòèìà, òî ñîîòâåòñòâóþùåå áàçèñíîå ðåøåíèå ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì çàäà÷è (5)(7).Èç ïðÿìîé äîïóñòèìîñòè ñèïëåêñòàáëèöû ñëåäóåò, ÷òî áàçèñíîå ðåøåíèå x ÿâëÿåòñÿäîïóñòèìûì ðåøåíèåì.Òàêèì îáðàçîì, ïðè ïîèñêå îïòèìàëüíîãî ðåøåíèÿ çàäà÷è (5)(7) ìîæíî îãðàíè÷èòüñÿðàññìîòðåíèåì áàçèñíûõ äîïóñòèìûõ ðåøåíèé. Äîñòàòî÷íî íàéòè áàçèñ, êîòîðîìó ñîîòâåòñòâóåò ïðÿìî è äâîéñòâåííî äîïóñòèìàÿ ñèìïëåêñòàáëèöà.Îïðåäåëåíèå.
Ïðåîáðàçîâàíèå ñèìïëåêñòàáëèöû, ïðè êîòîðîì ïðîèñõîäèò çàìåíà îäíîãî èç áàçèñíûõ ñòîëáöîâ íà äðóãîé ñòîëáåö ìàòðèöû A èç ÷èñëà íåáàçèñíûõ, íàçûâàåòñÿýëåìåíòàðíûì ïðåîáðàçîâàíèåì áàçèñà.Ïóñòü â áàçèñå B = [Aσ(1) , . . . , Aσ(m) ] ñòîëáåö Aσ(r) çàìåíÿåòñÿ íà ñòîëáåö As , s ∈J \ {σ(1), . . . , σ(m)}. Åñëè ýëåìåíò zrs íå ðàâåí 0, ãäå r ≥ 1, òî â ðåçóëüòàòå ïîëó÷èì íîâûé áàçèñ [Aσ(1) , . .
. , Aσ(r−1) , As , Aσ(r+1) , . . . , Aσ(m) ]. Ýòîìó áàçèñó áóäåò ñîîòâåòñòâîâàòüñèìïëåêñòàáëèöà, â êîòîðîé âåêòîðñòðîêè αi = (zi0 , zi1 , . . . , zin ) (i = 0, m) ïðåîáðàçóþòñÿ0 , z 0 , . . . , z 0 ) (i = 0, m) ïî ñëåäóþùåìó ïðàâèëó:â âåêòîðñòðîêè αi0 = (zi0i1inzisαr , i 6= r, αi0 = αi −zrs1 αr0 =αr .zrsÏðè ýòîì r-ÿ ñòðîêà, s-é ñòîëáåö è ýëåìåíò zrs íàçûâàþòñÿ âåäóùèìè.Ýëåìåíòû ñèìïëåêñòàáëèöû ïðè ýòîì, î÷åâèäíî, ïðèíèìàþò âèäzis zrj0 zij, i 6= r,= zij −zrszrj0 zrj.=zrsÓòâåðæäåíèå 7.
Åñëè â ïðÿìî äîïóñòèìîé ñèìïëåêñòàáëèöå ñóùåñòâóåò j = s (s ∈ J ),äëÿ êîòîðîãî z0s < 0 è zis ≤ 0 (i = 1, m), òî öåëåâàÿ ôóíêöèÿ w(x) íå îãðàíè÷åíà ñíèçó íàX.34Îïðåäåëåíèå. Áàçèñ B è ñîîòâåòñòâóþùåå åìó áàçèñíîå ðåøåíèå x íàçûâàþòñÿ âû-ðîæäåííûìè, åñëè ñóùåñòâóåò i ∈ I òàêîå, ÷òî zi0 = 0.Óòâåðæäåíèå 8. Ïóñòü áàçèñíîå äîïóñòèìîå ðåøåíèå x íå âûðîæäåíî, z0s < 0 (s ∈ J )è ñóùåñòâóåò r ∈ I òàêîå, ÷òî zrs > 0.
Òîãäà ñóùåñòâóåò áàçèñíîå äîïóñòèìîå ðåøåíèå x0 ,äëÿ êîòîðîãî w(x0 ) < w(x).Ïðèìåð 1. Èññëåäîâàòü íà îïòèìàëüíîñòü ðåøåíèå x = (0, 0, 1, 1)> çàäà÷èw(x) = x1 + x2 − 2x3 − 3x4 → min,2x1 − x2 + x3 = 1,−x1 + 2x2 + x4 = 1,xj ≥ 0, j = 1, 2, 3, 4.© ³1´ ³0´ ªìàòðèöû A0 , 1ëèíåéíî íåçàâèñèìî. Òàê êàê ìàòðèöà B åäèíè÷íàÿ, òî äëÿ ïîñòðîåíèÿ ñèìïëåêñòàáëèöû,ñîîòâåòñòâóþùåé ýòîìó áàçèñó, äîñòàòî÷íî èñêëþ÷èòü áàçèñíûå ïåðåìåííûå x3 è x4 èçöåëåâîé ôóíêöèè.
Ïîëó÷èìÐåøåíèå. Ìíîæåñòâî ñòîëáöîâ {Aj | xj > 0} = {A3 , A4 } =w = x1 + x2 − 2(1 − 2x1 + x2 ) − 3(1 + x1 − 2x2 ) = −5 + 2x1 + 5x2 .Ñëåäîâàòåëüíî, ðàâåíñòâà ïðèíèìàþò âèä−w + 2x1 + 5x2 = 5,x3 + 2x1 − x2 = 1,x4 − x1 + 2x2 = 1.È ñèìïëåêñòàáëèöà ìîæåò áûòü ïðåäñòàâëåíà òàê:−wx3x4511x122−1x25−12x3010x4001Òàê êàê òàáëèöà ÿâëÿåòñÿ ïðÿìî (z10 = 1, z20 = 1) è äâîéñòâåííî (z01 = 2, z02 = 5, z03 =0, z04 = 0) äîïóñòèìîé, òî áàçèñíîå äîïóñòèìîå ðåøåíèå x îïòèìàëüíîå ðåøåíèå. Çàìåòèì,÷òî çäåñü σ(1) = 3, σ(2) = 4.Ïðèìåð 2. Èññëåäîâàòü íà îïòèìàëüíîñòü ðåøåíèå x = (0, 1, 0, 2, 1)> çàäà÷èw(x) = −x1 − x2 → min,−x1 + x2 + x3 = 1,x1 − 2x2 + x4 = 0,−x1 + 2x2 + x5 = 3,xj ≥ 0, j = 1, 2, 3, 4, 5.Ðåøåíèå.  ýòîì ïðèìåðå ñòîëáöû (A2 , A4 , A5 ) = ((1, −2, 2)> , (0, 1, 0)> , (0, 0, 1)> ) ëè-íåéíî íåçàâèñèìû. Ñëåäîâàòåëüíî, x áàçèñíîå äîïóñòèìîå ðåøåíèå ñ áàçèñíûìè ïåðåìåííûìè x2 = 1, x4 = 2, x5 = 1.
Ïîñòðîèì ñîîòâåòñòâóþùóþ ðåøåíèþ x ñèìïëåêñòàáëèöó.Íåáàçèñíûå ïåðåìåííûå çäåñü x1 è x3 . Ñëåäîâàòåëüíî, èç ïåðâîãî îãðàíè÷åíèÿðàâåíñòâàñðàçó ïîëó÷àåìx2 = 1 + x1 − x3 .35Ïîäñòàâèâ x2 , âûðàæåííîå ÷åðåç íåáàçèñíûå ïåðåìåííûå, âî âòîðîå è òðåòüå îãðàíè÷åíèÿðàâåíñòâà, ïðèäåì ê ñîîòíîøåíèÿì−x1 + x3 + x2 = 1,−x1 + 2x3 + x4 = 2,x1 − 2x3 + x5 = 1.Îñòàëîñü èñêëþ÷èòü áàçèñíûå ïåðåìåííûå èç öåëåâîé ôóíêöèè:w(x) = −x1 − x2 = −x1 − (1 + x1 − x3 ) = −1 − 2x1 + x3 .Òàêèì îáðàçîì, ïðèõîäèì ê ðàâåíñòâó−w − 2x1 + x3 = 1.Ñèìïëåêñòàáëèöà ïðèíèìàåò âèä−wx2x4x51121x1−2−1−11x20100x3112−2x40010x50001Áàçèñ íå ÿâëÿåòñÿ âûðîæäåííûì, òàê êàê âåêòîð (z10 , z20 , z30 )> = (1, 2, 1)> íå ñîäåðæèòíóëåâûõ ýëåìåíòîâ.
Òàáëèöà ïðÿìî äîïóñòèìà, íî íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé:z01 = −2 < 0. È òàê êàê z31 = 1 > 0, òî ñîãëàñíî óòâåðæäåíèþ 8 ñóùåñòâóåò áàçèñíîåäîïóñòèìîå ðåøåíèå, êîòîðîå äàåò ìåíüøåå çíà÷åíèå öåëåâîé ôóíêöèè, ÷åì w(x) = −z00 =−1. Äåéñòâèòåëüíî, òàê êàê z31 6= 0, òî ìîæíî ïðåîáðàçîâàòü áàçèñ, âûâåäÿ èç íåãî ñòîëáåöA5 è çàìåíèâ åãî íà ñòîëáåö A1 , ò. å. ïîëó÷èòü áàçèñ (A1 , A2 , A4 ).Ñîãëàñíî ôîðìóëàì ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ áàçèñà, ïîëó÷èì òàáëèöó−wx2x4x13231x10001x20100x3−3−10−2x40010x521110 = −3, ãäå x0 = (1, 2, 0, 3, 0)> .
Òàê êàêñ ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè w(x0 ) = −z000z03 = −3 < 0 è â òðåòüåì ñòîëáöå (j = 3) íåò ïîëîæèòåëüíûõ ýëåìåíòîâ, òî èç óòâåðæäåíèÿ7 ñëåäóåò íåîãðàíè÷åííîñòü ñíèçó öåëåâîé ôóíêöèè w(x) íà ðàññìàòðèâàåìîì ìíîæåñòâåX.Çàäà÷è1. Èññëåäîâàòü íà îïòèìàëüíîñòü ðåøåíèå x:1) x1 − 2x2 − 2x3 −→ min,x1 − x2 + 2x3 = 0, x1 + x2 + 5x3 = 2,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,x = (1, 1, 0)> ;362) x1 − 2x2 − 4x3 −→ min,x1 − x2 − x3 = 1, x1 + x2 + x3 = 3,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,x = (2, 1, 0)> .2. Íàéòè áàçèñíîå äîïóñòèìîå ðåøåíèå, ñ ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè ÷åì íàðåøåíèè x:1) −x1 − x2 − 2x4 −→ min,x1 + x3 + x4 = 4, −x1 − 2x2 − 3x3 + x4 = 0,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (2, 0, 0, 2)> ;2) −x1 + x2 − x3 − 2x4 −→ min,x1 + x2 + x3 + 2x4 = 7, x2 + x3 + x4 = 5, x3 − x4 = 3,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (2, 2, 3, 0)> ;3) −x1 − x2 − x3 − 5x4 −→ min,x1 + x2 − x4 = 3, x1 − x2 + 3x4 = −1, 2x1 + x2 + x3 − x4 = 5,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (1, 2, 1, 0)> .4.4 Ïðÿìîé ñèìïëåêñìåòîäÏóñòü x íåêîòîðîå áàçèñíîå äîïóñòèìîå ðåøåíèå çàäà÷è (5)(7), ñîîòâåòñòâóþùååáàçèñó B .
 ðåçóëüòàòå èññëåäîâàíèÿ ñèìïëåêñòàáëèöû ñ áàçèñîì B âûÿâëÿåòñÿ:1) ëèáî îïòèìàëüíîñòü ðåøåíèÿ x;2) ëèáî íåðàçðåøèìîñòü çàäà÷è;3) ëèáî âîçìîæíîñòü ïåðåõîäà ê íîâîìó áàçèñó.Ïîñëåäîâàòåëüíîå ïðîäâèæåíèå ïî áàçèñàì äîïóñòèìûõ áàçèñíûõ ðåøåíèé âïëîòü äîïîëó÷åíèÿ îïòèìàëüíîãî áàçèñà èëè óñòàíîâëåíèÿ íåðàçðåøèìîñòè çàäà÷è ñîñòàâëÿåò èäåþñèìïëåêñìåòîäà.Îïèñàíèå àëãîðèòìà:0) Ïîñòðîèòü ñèìïëåêñòàáëèöó, ñîîòâåòñòâóþùóþ çàäàííîìó áàçèñíîìó äîïóñòèìîìóðåøåíèþ (òàáëèöà, åñòåñòâåííî, áóäåò ïðÿìî äîïóñòèìîé, ò.å. zi0 ≥ 0, i = 1, m).1) Åñëè ñèìïëåêñòàáëèöà äâîéñòâåííî äîïóñòèìà, ò.å. z0j ≥ 0, j = 1, n, òî ÊÎÍÅÖ(ïîëó÷åíî îïòèìàëüíîå ðåøåíèå).2) Èíà÷å, âûáðàòü âåäóùèé ñòîëáåö s : zos < 0, s ≥ 1.3) Åñëè {i | zis > 0, i ≥ 1} 6= ∅, òî âûáðàòü âåäóùóþ ñòðîêó r ïî ïðàâèëó:zr0zi0= min{| zis > 0, i ≥ 1},zrszisèíà÷å ÊÎÍÅÖ (çàäà÷à íåðàçðåøèìà èç-çà íåîãðàíè÷åííîñòè öåëåâîé ôóíêöèè).4) Ïðåîáðàçîâàòü ñèìïëåêñòàáëèöó, ïîëîæèòü σ(r) := s è ïåðåéòè íà øàã 1.Ïîä èòåðàöèåé ïîíèìàåòñÿ îäíîêðàòíîå âûïîëíåíèå øàãîâ ñ 1-ãî ïî 4-é.37Óòâåðæäåíèå 9.
Íà êàæäîé èòåðàöèè àëãîðèòìà ñèìïëåêñ òàáëèöà îñòàåòñÿ ïðÿìîäîïóñòèìîé.Îïðåäåëåíèå. Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ íàçûâàåòñÿ âûðîæäåííîé, åñëè óíåå ñóùåñòâóåò âûðîæäåííîå áàçèñíîå äîïóñòèìîå ðåøåíèå x, ò. å. òàêîå ðåøåíèå x, ÷òî|{j | xj 6= 0}| < m.Óòâåðæäåíèå 10.  ñëó÷àå íåâûðîæäåííîé çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ àëãîðèòì ñèìïëåêñìåòîäà êîíå÷åí. ñëó÷àå âûðîæäåííîé çàäà÷è âîçìîæíî òàê íàçûâàåìîå çàöèêëèâàíèå, êîãäà â ðåçóëüòàòå ðåàëèçàöèè íåñêîëüêèõ èòåðàöèé àëãîðèòìà ïðîèñõîäèò âîçâðàò ê áàçèñó, âñòðå÷àâøåìóñÿ ðàíåå. Ñëåäîâàòåëüíî, àëãîðèòì ìîæåò íåîãðàíè÷åíî âûïîëíÿòü îäèí è òîò æå öèêëïðåîáðàçîâàíèÿ áàçèñà.
Äëÿ èçáåæàíèÿ çàöèêëèâàíèÿ èñïîëüçóåòñÿ ëåêñèêîãðàôè÷åñêèéâàðèàíò ñèìïëåêñìåòîäà, îïèñàííûé â ñëåäóþùåì ïîäðàçäåëå.Ïðèìåð 1. Ðåøèòü çàäà÷ów(x) = −x1 − 2x2 − 3x3 + x4 → min,x1 − 3x2 − x3 − 2x4 = −4,x1 − x2 + x3 = 0,xj ≥ 0, j = 1, 2, 3, 4,âçÿâ â êà÷åñòâå èñõîäíîãî ðåøåíèÿ òî÷êó x = (0, 1, 1, 0)> .Ðåøåíèå. Òàáëèöà, ñîîòâåòñòâóþùàÿ íóëåâîìóøàãó, ìîæåò áûòü ïîñòðîåíà ñëåäóþ© ³−3´ ³−1´ ªùèì îáðàçîì. Òàê êàê ñòîëáöû {A2 , A3 } = −1 , 1ëèíåéíî íåçàâèñèìû, òî èìååìáàçèñ B 0 = (A2 , A3 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
