1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 8
Текст из файла (страница 8)
Ïðèâåñòè ê êàíîíè÷åñêîé ôîðìå:281) x1 − x2 + x3 −→ max,x1 − x2 = 0, x2 ≤ 1, x3 ≥ 0;2) x1 + x2 + 3x3 −→ max,2x1 + x2 + x3 ≤ 1, x2 + x3 ≥ 0, x2 ≥ 0, x3 ≥ 0;3) x1 − x2 − x3 − x4 −→ min,x1 + x2 − x4 ≤ 1, −x1 + x2 + x4 ≤ 1, x2 + x3 = 1,x1 ≥ 0, x2 ≥ 0;4) x1 − x2 − 2x3 − 3x4 −→ min,x1 − x2 + x3 + x4 = 1, −x1 − x4 ≤ 5, x2 + x3 ≥ 10,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0;5) x1 − x2 − x3 + 10x4 −→ max,x1 + x2 + x3 + x4 = 1, x2 + x3 + x4 = 1, x3 + x4 = 1.2. Çàäà÷à ËÏ â ñòàíäàðòíîé ôîðìåcx → min,Ax ≥ b,x≥0ïðèâîäèòñÿ ê êàíîíè÷åñêîé ôîðìå ïóòåì ââåäåíèÿ íåîòðèöàòåëüíûõ ïåðåìåííûõ y = (y1 , . . . , ym )> .Ïîëó÷àåòñÿ çàäà÷àcx → min,Ax − Ey = b,x ≥ 0, y ≥ 0(çäåñü E åäèíè÷íàÿ ìàòðèöà ðàçìåðà m × m).
Äîêàçàòü, ÷òî åñëè (x, y) ðåøåíèå ïîñëåäíåé çàäà÷è, òî x ðåøåíèå èñõîäíîé çàäà÷è.3. Çàäà÷à ËÏ â îáùåé ôîðìånXcj xj → min,j=1nXaij xj ≥ bi , i ∈ I1 ,j=1nXaij xj = bi , i ∈ I2 ,j=1xj ≥ 0, j ∈ J1 .ïðèâîäèòñÿ ê êàíîíè÷åñêîé ôîðìå ïóòåì äîáàâëåíèÿ íåîòðèöàòåëüíûõ ïåðåìåííûõ yi (i ∈I1 ) è çàìåíû ïåðåìåííûõ xj (j ∈ J \ J1 ) ðàçíîñòüþ äâóõ íåîòðèöàòåëüíûõ ïåðåìåííûõ:xj = x1j − x2j , j ∈ J \ J1 .29Ïîëó÷åííóþ çàäà÷ó ìîæíî çàïèñàòü â âèäåXXcj xj +cj (x1j − x2j ) → min,j∈J1Xaij xj +j∈J1Xj∈J1j∈J\J1Xaij (x1j − x2j ) − yi = bi , i ∈ I1 ,j∈J\J1aij xj +Xaij (x1j − x2j ) = bi , i ∈ I2 ,j∈J\J1xj ≥ 0, j ∈ J1 , x1j ≥ 0, x2j ≥ 0, j ∈ J \ J1 ,yi ≥ 0, i ∈ I1 .Äîêàçàòü, ÷òî åñëè xj (j ∈ J1 ), x1j , x2j (j ∈ J \ J1 ), yi (i ∈ I1 ) ðåøåíèå ïîñëåäíåé çàäà÷è, òîxj (j ∈ J1 ), xj = x1j − x2j (j ∈ J \ J1 ) ðåøåíèå èñõîäíîé çàäà÷è.4.2. Áàçèñ è áàçèñíîå ðåøåíèåÄàëåå ðàññìàòðèâàåòñÿ òîëüêî çàäà÷à ËÏ â êàíîíè÷åñêîé ôîðìå (5)(7).
Ïðåäïîëîæèì,÷òî ìàòðèöà A èìååò ðàíã m (m ≤ n). Òîãäà â A èìååòñÿ m ëèíåéíî íåçàâèñèìûõ ñòîëáöîâ.Ñèñòåìà ëèíåéíûõ óðàâíåíèé (6) ñîâìåñòíà è íåèçáûòî÷íà. Ïóñòü Aj = (a1j , . . . , amj )> , j ∈J.Îïðåäåëåíèå. Ëþáîé íàáîð Aσ(1) , . . . , Aσ(m) èç m ëèíåéíî íåçàâèñèìûõ ñòîëáöîâ íàçûâàåòñÿ áàçèñîì, êàê è ìàòðèöà B = [Aσ(1) , . . .
, Aσ(m) ], ñîñòàâëåííàÿ èç ýòèõ ñòîëáöîâ.Ïåðåñòàíîâêîé ñòîëáöîâ ìàòðèöó A ìîæíî ïðèâåñòè ê âèäó A = [B, N ], ãäå N ïîäìàòðèöà,ñîñòàâëåííàÿ èç îñòàëüíûõ ñòîëáöîâA. Ïîñòóïèâ àíàëîãè÷íûì îáðàçîì ñ âåêòî³ ìàòðèöû´x , ãäå x = (x>ðîì x, ïîëó÷èì ïðåäñòàâëåíèå x = xBBσ(1) , . . . , xσ(m) ) .NÎïðåäåëåíèå. Ïåðåìåííûå xj , ÿâëÿþùèåñÿ êîìïîíåíòàìè âåêòîðà xB (ñîîòâåòñòâåííîxN ), íàçûâàþòñÿ áàçèñíûìè (ñîîòâåòñòâåííî ³íåáàçèñíûìè´ ³ −1 ).´xBÎïðåäåëåíèå. Ðåøåíèå ñèñòåìû (6) x = xN = 0B b íàçûâàþò áàçèñíûì ðåøåíèåì(ñîîòâåòñòâóþùèì áàçèñó B ).Óòâåðæäåíèå 1.
Âåêòîð x áàçèñíîå ðåøåíèå ñèñòåìû (6) òîãäà è òîëüêî òîãäà, êîãäàìíîæåñòâî ñòîëáöîâ {Aj | xj 6= 0, j ∈ J} ìàòðèöû A ëèíåéíî íåçàâèñèìî.×èñëî áàçèñíûõ ðåøåíèé êîíå÷íî è íå ïðåâîñõîäèò ÷èñëà Cnm . Êàæäîìó áàçèñó ñîîòâåòñòâóåò îäíî áàçèñíîå ðåøåíèå, íî áàçèñíîìó ðåøåíèþ ìîæåò ñîîòâåòñòâîâàòü íåñêîëüêîáàçèñîâ.Îïðåäåëåíèå.
Áàçèñíûì äîïóñòèìûì ðåøåíèåì (á. ä. ð.) íàçûâàåòñÿ ëþáîé ýëåìåíòìíîæåñòâà X = {x | Ax = b, x ≥ 0}, ÿâëÿþùèéñÿ áàçèñíûì ðåøåíèåì ñèñòåìû Ax = b.ßñíî, ÷òî ðåøåíèå, ñîîòâåòñòâóþùåå áàçèñó B , ÿâëÿåòñÿ á. ä. ð. òîãäà è òîëüêî òîãäà,êîãäà B −1 b ≥ 0.Óòâåðæäåíèå 2. Âåêòîð x ÿâëÿåòñÿ áàçèñíûì äîïóñòèìûì ðåøåíèåì òîãäà è òîëüêîòîãäà, êîãäà x åñòü êðàéíÿÿ òî÷êà ìíîæåñòâà X .Óòâåðæäåíèå 3. Åñëè X 6= ∅, òî ñóùåñòâóåò áàçèñíîå äîïóñòèìîå ðåøåíèå.Òåîðåìà 1 (êðèòåðèé ðàçðåøèìîñòè). Çàäà÷à (5)(7) ðàçðåøèìà òîãäà è òîëüêîòîãäà, êîãäà X 6= ∅ è öåëåâàÿ ôóíêöèÿ w(x) îãðàíè÷åíà ñíèçó íà ìíîæåñòâå X .Óòâåðæäåíèå 4. Åñëè çàäà÷à ËÏ ðàçðåøèìà, òî ñóùåñòâóåò îïòèìàëüíîå áàçèñíîåäîïóñòèìîå ðåøåíèå.Ïðèìåð 1.
Íàéòè âñå áàçèñû ñèñòåìû ðàâåíñòâ è ñîîòâåòñòâóþùèå èì áàçèñíûå ðåøå-íèÿ:x1 + x2 + x3 + x4 = 1,30x1 − x2 + x3 − x4 = 1,xj ≥ 0, j = 1, 2, 3, 4.Ðåøåíèå. Ðàññìîòðèì ìíîæåñòâî{A1 , A2 } (îòìåòèì, ÷òî çäåñü m = 2). Îíè³ ñòîëáöîâ´1ëèíåéíî íåçàâèñèìû. Çíà÷èò, B = 11 − 1 áàçèñ. Íàáîð ñòîëáöîâ {A1 , A3 } áàçèñîì íåÿâëÿåòñÿ, òàê êàê î÷åâèäíî, ÷òî ýòè ñòîëáöû ëèíåéíî çàâèñèìû. Àíàëîãè÷íî óñòàíàâëèâàåì,÷òî {A1 , A4 }, {A2 , A3 }, {A3 , A4 } áàçèñû, à {A2 , A4 } íå áàçèñ. Òàê êàê â äàííîì ïðèìåðåC42 = 6, òî ðàññìîòðåíû âñå ñëó÷àè.Òàêèì îáðàçîì, {A1 , A2 }, {A1 , A4 }, {A2 , A3 }, {A3 , A4 } âñå áàçèñû äàííîé ñèñòåìûðàâåíñòâ.Íàéäåì òåïåðü âñå áàçèñíûå ðåøåíèÿ. Ñîãëàñíî ââåä¼ííûì âûøå îáîçíà÷åíèÿì ñèñòåìà(6) ïðè âûáðàííîì áàçèñå B ìîæåò áûòü çàïèñàíà â òàêîì âèäå:BxB + N xN = b.Îòêóäà, â ñèëó ñóùåñòâîâàíèÿ îáðàòíîé ìàòðèöû B −1 , ïîëó÷àåì, ÷òîxB = B −1 b − B −1 N xN .Ïîëîæèâ, ÷òî íåáàçèñíûå ïåðåìåííûå xN ðàâíû íóëþ, ïîëó÷èì áàçèñíîå ðåøåíèå xB =B −1 b, xN = 0.³ ´xÎ÷åâèäíî, ÷òî áàçèñíîå ðåøåíèå xBìîæíî íàéòè, ïîëîæèâ â (6) xN = 0, à çàòåìNðàçðåøèâ ïîëó÷èâøóþñÿ ñèñòåìóóðàâíåíèé îòíîñèòåëüíî xB ëþáûì óäîáíûì ñïîñîáîì.³´1Åñëè B = (A1 , A2 ), òî xB = 0 .
Çíà÷èò, x = (1, 0, 0, 0)> áàçèñíîå ðåøåíèå.Ïîñëåäîâàòåëüíî íàõîäèì, ÷òî âåêòîð x = (1, 0, 0, 0)> ñîîòâåòñòâóåò áàçèñó {A1 , A4 }, àâåêòîð x = (0, 0, 1, 0)> áàçèñàì {A2 , A3 } è {A3 , A4 }.Òàêèì îáðàçîì, ðàññìàòðèâàåìàÿ ñèñòåìà èìååò ÷åòûðå áàçèñà, íî òîëüêî äâà áàçèñíûõðåøåíèÿ, êàæäîìó èç êîòîðûõ ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå ïî äâà áàçèñà. Îòìåòèì,÷òî äëÿ âñåõ áàçèñíûõ ðåøåíèé âûïîëíåíî óñëîâèå x ≥ 0, ò. å. ýòî áàçèñíûå äîïóñòèìûåðåøåíèÿ.Ïðèìåð 2. Íàéòè âñå áàçèñû ñèñòåìû ðàâåíñòâ è ñîîòâåòñòâóþùèå èì áàçèñíûå äîïóñòèìûå ðåøåíèÿ:x1 + x2 + x3 + x4 = 3,x1 − x2 + x3 + 2x4 = 1,xj ≥ 0 j = 1, 2, 3, 4.B3Ðåøåíèå. Íåòðóäíî óñòàíîâèòü, ÷òî áàçèñàìè ÿâëÿþòñÿ B 1 = (A1 , A2 ), B 2 = (A1 , A4 ),= (A2 , A3 ), B 4 = (A2 , A4 ) è B 5 = (A3 , A4 ).
Èì ñîîòâåòñòâóþò áàçèñíûå ðåøåíèÿ x1 =(2, 1, 0, 0)> , x2 = (5, 0, 0, −2)> , x3 = (0, 1, 2, 0)> x4 = (0, 5/3, 0, 4/3)> , x5 = (0, 0, 5, −2)> .Áàçèñíûìè äîïóñòèìûìè ðåøåíèÿìè ÿâëÿþòñÿ x1 , x3 , x4 . Ñðåäè íèõ è íóæíî èñêàòü îïòèìàëüíîå, åñëè çàäàòü öåëåâóþ ôóíêöèþ.Ïðèìåð 3. Êàêèå áàçèñû ñîîòâåòñòâóþò áàçèñíîìó ðåøåíèþ x = (a, b, 0)> ñèñòåìûx1 + x2 + x3 = a + b,x1 − 2x2 = a − 2b,xj ≥ 0, j ∈ J = {1, 2, 3}, (a ≥ 0, b ≥ 0)?³´Ðåøåíèå. Åñëè a > 0, b > 0, òî áàçèñîì ìîæåò áûòü òîëüêî ìàòðèöà B = 11 − 12 . Åñëèa > 0, b = 0, òî {Aj | xj > 0} = {A1 } è ïåðâûé ñòîëáåö ìîæåò áûòü äîïîëíåí äî áàçèñà31äâóìÿ ñïîñîáàìè, ïðèâîäÿùèìè ê áàçèñàì, ñîîòâåòñòâóþùèõ ðåøåíèþ x = (a, 0, 0)> , ãäåa>0:B 1 = (A1 , A2 ) è B 2 = (A1 , A3 ).Çàìåòèì, ÷òî âñå ñòîëáöû ìàòðèöû A ïîïàðíî ëèíåéíî íåçàâèñèìû.
 ñëó÷àå a = 0, b > 0àíàëîãè÷íî ïîëó÷àåì, ÷òî åñëè x = (0, b, 0)> , ãäå b > 0, òîB 1 = (A1 , A2 ) è B 2 = (A2 , A3 ).È íàêîíåö, åñëè a = b = 0, ò. å. x = (0, 0, 0)> , òî èìååì òðè áàçèñà, êîòîðûì ñîîòâåòñòâóåòýòî ðåøåíèå:B 1 = (A1 , A2 ), B 2 = (A1 , A3 ) è B 3 = (A2 , A3 ).Ïðèìåð 4. Íàéòè ðåøåíèå çàäà÷è−3x1 − 2x2 − x3 → min,x1 + x2 + x3 = 1,x1 − x2 + x3 = 1,xj ≥ 0 (j = 1, 2, 3).Ðåøåíèå. Íåòðóäíî çàìåòèòü, ÷òî ìíîæåñòâî {x | x1 + x2 + x3 = 1, xj ≥ 0, j = 1, 2, 3}îãðàíè÷åííî è ñîäåðæèò â ñåáå äîïóñòèìîå ìíîæåñòâî.
Ñëåäîâàòåëüíî, ðàññìàòðèâàåìàÿçàäà÷à ðàçðåøèìà. Ïðè ýòîì ðàíã ìàòðèöû A ðàâåí äâóì. ñèëó ñóùåñòâîâàíèÿ îïòèìàëüíîãî áàçèñíîãî äîïóñòèìîãî ðåøåíèÿ, íàéäåì åãî, ïåðåáðàâ âñå áàçèñíûå ðåøåíèÿ.Èìååì áàçèñû B 1 = (A1 , A2 ) è B 2 = (A2 , A3 ), êîòîðûì ñîîòâåòñòâóþò áàçèñíûå ðåøåíèÿ1x = (1, 0, 0)> è x2 = (0, 0, 1)> . Ýòè ðåøåíèÿ äîïóñòèìû. Òàê êàê w(x1 ) = −3, à w(x2 ) = −1,òî îïòèìàëüíûì ÿâëÿåòñÿ ðåøåíèå x∗ = x1 .Çàäà÷è1. Íàéòè âñå áàçèñû çàäàííîãî áàçèñíîãî äîïóñòèìîãî ðåøåíèÿ x ñèñòåìû îãðàíè÷åíèé:1) x1 + x2 + x3 = 0, x1 − x2 + x3 = 0, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,x = (0, 0, 0)> ;2) x1 + x2 + x3 + x4 = 1, x1 − x2 + x3 − x4 = 1, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (1, 0, 0, 0)> .2.  äàííîé ñèñòåìå îãðàíè÷åíèé âûðàçèòü áàçèñíûå ïåðåìåííûå óêàçàííîãî áàçèñíîãîäîïóñòèìîãî ðåøåíèÿ x ÷åðåç íåáàçèñíûå:1) x1 + x2 + 2x3 = 3, −2x1 + 3x2 + x3 = 4,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,x = (1, 2, 0)> ;2) 4x1 − x2 + 2x3 = 1, 10x1 + x2 − 4x3 = −3,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,x = (0, 1, 1)> ;323) x1 − x2 − 2x4 = 1, 2x1 − x2 + x3 − x4 = 2,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (1, 0, 0, 0)> ;4) x1 + x2 + x3 + 6x4 = 3, x2 − x3 − 2x4 = 0, x1 + 2x4 = 1,x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0,x = (1, 1, 1, 0)> .4.3.
Ñèìïëåêñòàáëèöà è êðèòåðèé îïòèìàëüíîñòè. Ýëåìåíòàðíîå ïðåîáðàçîâàíèå áàçèñàÏóñòü âûáðàí áàçèñ B = (Aσ(1) , . . . , Aσ(m) ), ïî êîòîðîìó ïîñòðîåíà ýêâèâàëåíòíàÿ ñèñòåìà îãðàíè÷åíèéðàâåíñòâxB + B −1 N xN = B −1 b.Ïðåäñòàâèâ âåêòîð c â âèäå c = (cB , cN ), ãäå cB = (cσ(1) , . . . , cσ(m) ) ñîîòâåòñòâóåò áàçèñíûì,à cN íåáàçèñíûì ïåðåìåííûì, ïîëó÷èì, ÷òîw = cB B −1 b + (cN − cB B −1 N )xN .Òàêèì îáðàçîì, ïîëó÷àåì ñèñòåìó ðàâåíñòâX−w +z0j xj = z00 ,j∈S 0xσ(i) +Xzij xj = zi0 , i = 1, . . .
, m,j∈S 0ãäåS 0 = J \ {σ(1), . . . , σ(m)}, z00 = −cB B −1 b,(z10 , . . . , zm0 )> = B −1 b,z0j = cj − cB B −1 Aj , j = 1, . . . , n,(z1j , . . . , zmj )> = B −1 Aj , j = 1, . . . , n.Êîýôôèöèåíòû zij (i = 0, m, j = 0, n) è ñîñòàâëÿþò òàê íàçûâàåìóþ ñèìïëåêñòàáëèöó,êîòîðàÿ èñïîëüçóåòñÿ â ðàññìàòðèâàåìîì äàëåå ìåòîäå ðåøåíèÿ:−wxσ(1).xσ(i).xσ(m)z00z10...zi0...zm0x1z01z11...zi1...zm1.....................xjz0jz1j...zij...zmj.....................xnz0nz1n...zin...zmnÎñîáåííîñòüþ òàáëèöû ÿâëÿåòñÿ ñëåäóþùåå ñâîéñòâî: ïðè ëþáîì i = 1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
