1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 13
Текст из файла (страница 13)
2). Ýòà ñèìïëåêñòàáëèöà ïîêàçûâàåò, ÷òî ñëåäóåò äâèãàòüñÿ ïî îñè x02äî ãèïåðïëîñêîñòè x6 = 0 (èëè x4 = 0, òàê êàê z10 /z12 = z30 /z32 = 1/2).  ðåçóëüòàòå ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ ñ âåäóùèì ýëåìåíòîì z32 ïðèõîäèì ê òðåòüåé ñèìïëåêñòàáëèöå, âêîòîðîé z00 = 0. Çíà÷èò, òî÷êà x = (0, 1/2, 3/2)> ïðèíàäëåæèò äîïóñòèìîìó ìíîæåñòâó X .Îäíîâðåìåííî óñòàíàâëèâàåì, ÷òî îãðàíè÷åíèÿðàâåíñòâà Ax = b ëèíåéíî çàâèñèìû. Èçðèñ. 1 âèäíî, ÷òî óäàëåíèå îäíîãî èç íèõ äîïóñòèìîãî ìíîæåñòâà X íå ìåíÿåò.
Èç ÷åòâåðòîéñèìïëåêñòàáëèöû âèäíî, ÷òî óäàëÿåòñÿ ãèïåðïëîñêîñòü x4 = 0 : x1 + x2 + x3 = 1.55Ðèñ. 2Ðàññìîòðèì ïÿòóþ ñèìïëåêñòàáëèöó è ðèñ. 3Ðèñ. 3Ñîãëàñíî ýòîé òàáëèöå èìååì äâå áàçèñíûõ ïåðåìåííûõ x2 è x3 è íåáàçèñíóþ x1 , ò. å.ïî äîïóñòèìîìó ìíîæåñòâó X ìîæíî äâèãàòüñÿ òîëüêî â îäíîì íàïðàâëåíèè âäîëü îñè x001 .Òàê êàê z01 = −3/2 < 0, òî ðàññìàòðèâàåìàÿ òî÷êà íå îïòèìàëüíà. Ïðîäâèíóâøèñü ïî îñèx001 äî ãèïåðïëîñêîñòè x3 = 0 (òîëüêî z11 > 0), ïîëó÷àåì ïîñëåäíþþ ñèìïëåêñòàáëèöó, èçêîòîðîé ñëåäóåò, ÷òî òî÷êà x = (1, 1, 0)> îïòèìàëüíàÿ. Ðåøåíèå çàâåðøåíî.56Êñòàòè, èç ðàññìîòðåííîãî ïðèìåðà âèäíî, ÷òî îí èìååò òîëüêî äâà äîïóñòèìûõ áàçèñíûõ ðåøåíèÿ x1 = (0, 1/2, 3/2)> è x2 = (1, 1, 0)> , òàê êàê äîïóñòèìîå ìíîæåñòâî ýòîîòðåçîê, ñîåäèíÿþùèé ýòè òî÷êè.5.
Äâîéñòâåííûå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ5.1. Ïîñòðîåíèå äâîéñòâåííûõ çàäà÷Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ îáû÷íî çàïèñûâàåòñÿ â ñëåäóþùåì îáùåì âèäå(ñì. ïîäðàçä. 4.1):nXw(x) =cj xj → min(1)j=1ïðè óñëîâèÿõai x − bi ≥ 0, i ∈ I1 ;(2)ai x − bi = 0, i ∈ I2 ;(3)xj ≥ 0, j ∈ J1 .(4)Ïðè ýòîì îãðàíè÷åíèÿ (2)(3) áóäåì íàçûâàòü ñóùåñòâåííûìè, à îãðàíè÷åíèÿ (4) îãðàíè÷åíèÿìè ïî çíàêó. Íàïîìíèì, ÷òî I = I1 ∪ I2 = {1, .
. . , m}, I1 ∩ I2 = ∅, J1 ⊂ J ={1, . . . , n}, à ÷åðåç J2 îáîçíà÷èì ìíîæåñòâî J \ J1 . Ïåðåìåííûå xj , j ∈ J2 íàçûâàþòñÿñâîáîäíûìè. Ñ ýòîé çàäà÷åé, êîòîðóþ íàçîâ¼ì ïðÿìîé çàäà÷åé ËÏ, òåñíî ñâÿçàíà çàäà÷à,êîòîðàÿ íàçûâàåòñÿ äâîéñòâåííîé ê íåé èëè äâîéñòâåííîé çàäà÷åé ËÏ.Äâîéñòâåííàÿ çàäà÷à ñòðîèòñÿ ñëåäóþùèì îáðàçîì:1) êàæäîìó ñóùåñòâåííîìó îãðàíè÷åíèþ (2)(3) ñòàâèòñÿ â ñîîòâåòñòâèå äâîéñòâåííàÿïåðåìåííàÿ yi (i ∈ I);2) öåëåâîé ôóíêöèåé, êîòîðóþ íåîáõîäèìî ìàêñèìèçèðîâàòü, ÿâëÿåòñÿ ïðîèçâåäåíèåâåêòîðñòðîêè y = (y1 , . . . , ym ) íà âåêòîðñòîëáåö b = (b1 , .
. . , bm )> ;3) êàæäîìó îãðàíè÷åíèþíåðàâåíñòâó (2) ñîîòâåòñòâóåò îãðàíè÷åííàÿ ïî çíàêó ïåðåìåííàÿ, ò. å. yi ≥ 0(i ∈ I1 ), à êàæäîìó îãðàíè÷åíèþðàâåíñòâó (3) ñîîòâåòñòâóåò ñâîáîäíàÿïåðåìåííàÿ yi (i ∈ I2 );4) êàæäîé îãðàíè÷åííîé ïî çíàêó ïåðåìåííîé xj (j ∈ J1 ) ñîîòâåòñòâóåò îãðàíè÷åíèåíåðàâåíñòâî äâîéñòâåííîé çàäà÷è, êîòîðîå èìååò âèämXaij yi ≤ cj (j ∈ J1 )i=1è ëåâàÿ ÷àñòü êîòîðîãî ïîëó÷àåòñÿ óìíîæåíèåì âåêòîðñòðîêè y íà j -é ñòîëáåö Aj ìàòðèöûA, à â ïðàâîé ÷àñòè íàõîäèòñÿ ñîîòâåòñòâóþùèé êîýôôèöèåíò öåëåâîé ôóíêöèè (1);5) êàæäîé ñâîáîäíîé ïåðåìåííîé xj (j ∈ J2 ) ñîîòâåòñòâóåò îãðàíè÷åíèåðàâåíñòâî, êîòîðîå ñòðîèòñÿ òàê æå, êàê ïðåäûäóùåå íåðàâåíñòâî, è èìååò âèämXaij yi = cj (j ∈ J2 ).i=1Òàêèì îáðàçîì, äâîéñòâåííîé ê çàäà÷å (1)(4) ÿâëÿåòñÿ çàäà÷àmXbi yi → max,(10 )aij yi ≤ cj , j ∈ J1 ;(20 )i=1mXi=157mXaij yi = cj , j ∈ J2 ;(30 )yi ≥ 0, i ∈ I1 .(40 )i=1 âåêòîðíîì âèäå ïàðó äâîéñòâåííûõ çàäà÷ (1)(4) è (10 )(40 ) ìîæíî ïðåäñòàâèòü òàê:Ïðÿìàÿ çàäà÷ànXcj xj → minw(x) =Äâîéñòâåííàÿ çàäà÷àmXbi yi → maxz(y) =i=1j=1ai x ≥ biai x = bixj ≥ 0xj − ñâîá.i ∈ I1i ∈ I2j ∈ J1j ∈ J2yi ≥ 0yi − ñâîá.yAj ≤ cjyAj = cj .Ñóùåñòâåííîé îñîáåííîñòüþ îòíîøåíèÿ äâîéñòâåííîñòè ÿâëÿåòñÿ òîò ôàêò, ÷òî çàäà÷à,äâîéñòâåííàÿ ê çàäà÷å (10 )(40 ), ñîâïàäàåò ñ ïðÿìîé çàäà÷åé (1)(4).
Ìîæíî ñ÷èòàòü, ÷òîâñå çàäà÷è ËÏ ðàçáèâàþòñÿ íà ïàðû âçàèìíî äâîéñòâåííûõ çàäà÷.Ïðèìåð 1. Ïîñòðîèòü çàäà÷ó, äâîéñòâåííóþ ê çàäà÷åw(x) = x1 − 10x2 + 2x3 − x4 + 7x5 → min,2x1 − x2 ≤ 1,x1 − x2 + 2x3 − x4 + x5 ≥ 4,x2 + x3 − x4 = 0,x1 − x3 + 2x5 ≥ 3,x1 , x3 ≥ 0.Ðåøåíèå. ×òîáû çàïèñàòü äâîéñòâåííóþ çàäà÷ó, ïðèâåä¼ì å¼ ñíà÷àëà ê âèäó (1)(4).Ïðè ýòîì öåëåâàÿ ôóíêöèÿ w(x) íå èçìåíèòñÿ, à îãðàíè÷åíèÿ ïðèìóò âèäy1y2y3y4−2x1 + x2 ≥ −1,x1 − x2 + 2x3 − x4 + x5 ≥ 4,x1 − x3 + 2x5 ≥ 3,x2 + x3 − x4 = 0,x1 , x3 ≥ 0.Ñëåâà óêàçàíû äâîéñòâåííûå ïåðåìåííûå yi (i = 1, 2, 3, 4). Òåïåðü âîñïîëüçóåìñÿ îïðåäåëåíèåì (10 )(40 ) äâîéñòâåííîé çàäà÷è:z(y) = −y1 + 4y2 + 3y3 → max,−2y1 + y2 + y3 ≤ 1,y1 − y2 + y4 = −10,2y2 − y3 + y4 ≤ 2,−y2 − y4 = −1,y2 + 2y3 = 7,y1 , y2 , y3 ≥ 0.58x1x2x3x4x5Ñïðàâà äëÿ íàãëÿäíîñòè óêàçàíû ñîîòâåòñòâóþùèå ïåðåìåííûå ïðÿìîé çàäà÷è. Îòìåòèì,÷òî îãðàíè÷åíèÿìðàâåíñòâàì ñîîòâåòñòâóþò ñâîáîäíûå ïåðåìåííûå, à îãðàíè÷åíèÿìíåðàâåíñòâàì íåîòðèöàòåëüíûå ïåðåìåííûå.Ïðèìåð 2.
Ïîñòðîèòü çàäà÷ó, äâîéñòâåííóþ ê çàäà÷åx1 + 10x2 − x3 → max,x1 + x2 + x3 ≥ 1,x1 − x2 − x3 ≤ 2,x2 ≤ 0.Ðåøåíèå. Ïðèâåä¼ì äàííóþ çàäà÷ó ê âèäó (1)(4):−x1 − 10x2 + x3 → min,x1 + x2 + x3 ≥ 1,−x1 + x2 + x3 ≥ −2,−x2 ≥ 0.y1y2y3Çàìåòèì, ÷òî âñå ïåðåìåííûå ïðÿìîé çàäà÷è ñâîáîäíûå. Äâîéñòâåííàÿ çàäà÷à, ñîãëàñíîîïðåäåëåíèþ (10 )(40 ), èìååò âèäy1 − 2y2 → max,y1 − y2 = −1,y1 + y2 − y3 = −10,y1 + y2 = 1,y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.Åñëè èñõîäíóþ çàäà÷ó ïðèâåñòè ê âèäó (10 ) (40 )x1 + 10x2 − x3 → max,−x1 − x2 − x3 ≤ −1,x1 − x2 − x3 ≤ 2,x2 ≤ 0,u1u2u3òî äâîéñòâåííàÿ çàäà÷à, ïðèìåò âèä−u1 + 2u2 → min,−u1 + u2 = 1,−u1 − u2 + u3 = 10,−u1 − u2 = −1,u1 ≥ 0, u2 ≥ 0, u3 ≥ 0.Âèäíî, ÷òî ìû ïîëó÷èëè òó æå ñàìóþ äâîéñòâåííóþ çàäà÷ó, ÷òî è âûøå.Òàêèì îáðàçîì, íå ñóùåñòâåííî, ê êàêîìó âèäó ïðèâîäèòñÿ èñõîäíàÿ çàäà÷à: ê âèäó (1)(4) èëè ê âèäó (10 )(40 ) â ñèëó ñèììåòðèè äâîéñòâåííîé ê íèì áóäåò îäíà è òà æå çàäà÷à,âîçìîæíî, ïî-äðóãîìó çàïèñàííàÿ.59Áîëåå òîãî, åñëè â èñõîäíîé çàäà÷å ñäåëàòü çàìåíó x02 = −x2 è ïðèâåñòè çàäà÷ó ê âèäó(1)(4), òî ïîëó÷èòñÿ çàäà÷ày1y2−x1 + 10x02 + x3 → min,x1 − x02 + x3 ≥ 1,−x1 − x02 + x3 ≥ −2,x02 ≥ 0.Äâîéñòâåííàÿ ê íåé èìååò âèäy1 − 2y2 → max,y1 − y2 = −1,−y1 − y2 ≤ 10,y1 + y2 = 1,y1 ≥ 0, y2 ≥ 0.Ìîæíî ïðîâåðèòü, ÷òî ýòà çàäà÷à ýêâèâàëåíòíà ïîëó÷åííûì ðàíåå.Çàäà÷èÏîñòðîèòü çàäà÷ó, äâîéñòâåííóþ ê äàííîé çàäà÷å:1) x1 + 2x2 + 3x3 −→ min,x1 + x2 − 4x3 ≥ 1, x1 − x2 = 2,x1 ≥ 0;2) 2x1 + x2 − x3 − x4 −→ min,x1 + x2 − x3 + x4 = 1, x1 − x2 + x3 − x4 ≥ 2, x1 − x3 ≤ 3,x1 ≥ 0, x2 ≤ 0;3) x1 + 2x2 + 3x3 + 4x4 + 5x5 −→ min,x1 + x3 + x4 + x5 ≥ 0, x1 + x4 + x5 ≤ 0, x1 − x5 = 1,x1 ≥ 0, x2 ≥ 0, x5 ≤ 0;4) x1 + 2x2 − x3 + 4x4 − x5 + 6x6 −→ min,2x1 − x2 + x3 ≤ 2, x2 − x3 − x4 ≤ 3, x3 + x4 − x5 ≥ 4, x5 + x6 = 7,x1 ≥ 0, x2 ≥ 0, x4 ≤ 0, x5 ≤ 0;5)m PnPi=1 j=1nPj=1mPi=1cij xij −→ min,xij = ai , i = 1, m,xij = bj , j = 1, n,xij ≥ 0, i = 1, m, j = 1, n;606)nm PPi=1 j=1nPj=1mPi=1cij xij −→ min,αij xij = ai , i = 1, m,βij xij = bj , j = 1, n,xij ≥ 0, i = 1, m, j = 1, n.5.2.
Òåîðåìû äâîéñòâåííîñòèÎòìåòèì ñëåäóþùèå âàæíûå ñâîéñòâà âçàèìíî äâîéñòâåííûõ çàäà÷. Äëÿ îïðåäåë¼ííîñòè áóäåì ñ÷èòàòü, ÷òî çàäà÷à íà ìèíèìóì ÿâëÿåòñÿ ïðÿìîé, à íà ìàêñèìóì äâîéñòâåííîé.Ñâîéñòâî 1. Åñëè x è y äîïóñòèìûå ðåøåíèÿ ñîîòâåòñòâåííî ïðÿìîé è äâîéñòâåííîéçàäà÷è, òî w(x) ≥ z(y).Ñâîéñòâî 2. Åñëè x è y äîïóñòèìûå ðåøåíèÿ ñîîòâåòñòâåííî ïðÿìîé è äâîéñòâåííîéçàäà÷è è w(x) = z(y), òî x è y îïòèìàëüíûå ðåøåíèÿ.Òåîðåìà 1 (ïåðâàÿ òåîðåìà äâîéñòâåííîñòè).
Ïðÿìàÿ è äâîéñòâåííàÿ ê íåé çàäà÷èëèáî îäíîâðåìåííî ðàçðåøèìû, ëèáî îäíîâðåìåííî íåðàçðåøèìû. Ïðè ýòîì â ïåðâîì ñëó÷àåîïòèìàëüíûå çíà÷åíèÿ öåëåâûõ ôóíêöèé ýòèõ çàäà÷ ñîâïàäàþò, à âî âòîðîì ñëó÷àå ïîêðàéíåé ìåðå îäíà èç çàäà÷ íåðàçðåøèìà â ñèëó íåñîâìåñòíîñòè îãðàíè÷åíèé.Îòìåòèì, ÷òî ñóùåñòâóþò ïðèìåðû âçàèìíî äâîéñòâåííûõ çàäà÷ ñ íåñîâìåñòíûìè îãðàíè÷åíèÿìè. Òàêàÿ ïàðà âçàèìíî äâîéñòâåííûõ çàäà÷ ïðèâåäåíà íèæå:Ïðÿìàÿ çàäà÷àx1 − x2 → min,x1 + x2 = 1,x1 + x2 = 2;Äâîéñòâåííàÿ çàäà÷ày1 + 2y2 → max,y1 + y2 = 1,y1 + y2 = −1.Òåîðåìà 2 (âòîðàÿ òåîðåìà äâîéñòâåííîñòè, èëè òåîðåìà î äîïîëíÿþùåéíåæ¼ñòêîñòè).
Äîïóñòèìûå ðåøåíèÿ x è y ñîîòâåòñòâåííî ïðÿìîé è äâîéñòâåííîé çàäà÷è îïòèìàëüíû òîãäà è òîëüêî òîãäà, êîãäàyi (ai x − bi ) = 0 (i ∈ I),(cj − yAj )xj = 0 (j ∈ J).Ïðèìåð 1. Ïðè êàêèõ çíà÷åíèÿõ a ñèñòåìà−5y1 + 8y2 ≤ a,y1 − y2 ≤ −3,y1 − 2y2 ≤ 3,2y1 − 3y2 ≤ 1íåñîâìåñòíà?Ðåøåíèå. Äîïîëíèì ñèñòåìó äî çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ, äîáàâèâ öåëåâóþôóíêöèþ 0 −→ max, è ïîñòðîèì äâîéñòâåííóþ ê íåé:ax1 − 3x2 + 3x3 + x4 → min−5x1 + x2 + x3 + 2x4 = 0,618x1 − x2 − 2x3 − 3x4 = 0,xi ≥ 0, i = 1, 2, 3, 4.Ðåøèì å¼ ñèìïëåêñìåòîäîì. Ïîñêîëüêó ïðàâàÿ ÷àñòü íóëåâàÿ, òî ëþáîå áàçèñíîå ðåøåíèå áóäåò äîïóñòèìûì. Âûáåðåì â êà÷åñòâå íà÷àëüíîãî áàçèñà B = (A3 , A4 ) è ïîñòðîèìñèìïëåêñòàáëèöó−wx3x4000x1a+5−1−2x2−1−11x3010x4001Òàáëèöà íå ÿâëÿåòñÿ äâîéñòâåííî äîïóñòèìîé, òàê êàê z02 < 0.
Ïåðåõîäèì ê áàçèñó(A3 , A2 ):−wx3x2000x1a+3−3−2x2001x3010x4111Åñëè a ≥ −3, òî ñèìïëåêñòàáëèöà ÿâëÿåòñÿ ïðÿìî è äâîéñòâåííî äîïóñòèìîé. Åñëè æåa < −3, òî çàäà÷à íåðàçðåøèìà ââèäó íåîãðàíè÷åííîñòè öåëåâîé ôóíêöèè. Òîãäà ïî ïåðâîéòåîðåìå äâîéñòâåííîñòè ïðè a ≥ −3 èñõîäíàÿ ñèñòåìà èìååò ðåøåíèå, à ïðè a < −3 îíàíåñîâìåñòíà.Ïðèìåð 2. Íàéòè ìèíèìàëüíîå çíà÷åíèå ëèíåéíîé ôîðìûw(x) = x1 + x2 + · · · + xnïðè îãðàíè÷åíèÿõxj + xj+1 ≥ αj , j = 1, . .
. , n − 1,x1 + xn ≥ αn .Ðåøåíèå. Âîñïîëüçóåìñÿ äëÿ ðåøåíèÿ òåîðåìàìè äâîéñòâåííîñòè. Ñíà÷àëà ïîñòðîèìäâîéñòâåííóþ çàäà÷ó:nXz(y) =αi yi → maxi=1yi + yi+1 = 1, i = 1, . . . , n − 1,y1 + yn = 1,yi ≥ 0, i = 1, . . . , n.Ïóñòü n = 2k + 1. Èç ñèñòåìû îãðàíè÷åíèéðàâåíñòâ ïðè ïîïàðíîì âû÷èòàíèè ìîæíîóñòàíîâèòü, ÷òî y1 = y3 = · · · = y2k+1 è y2 = y4 = · · · = y2k . À èç óñëîâèé y1 + y2 =1, y1 + y2k+1 = 1 ñëåäóåò, ÷òî y2 = y2k+1 . Òàêèì îáðàçîì, âñåPyi (i = 1, 2k + 1) ðàâíû ìåæäóñîáîé, ò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
