1612726871-fd1970eb57207f2e4883f7549db906ce (828573), страница 7
Текст из файла (страница 7)
Ïîñêîëüêó ýòî ðåøåíèå ÿâëÿåòñÿ îòðèöàòåëüíûì,òî÷êà x0 íå îïòèìàëüíà.Ñèñòåìà (3) äëÿ òî÷êè x00 èìååò âèä −f 0 (x00 ) = y2 ϕ02 (x00 ) + y3 ϕ03 (x00 ), ò. å.µ √¶µ √¶µ¶−15−35−1= y2+ y3.−1−3−1Åäèíñòâåííûì ðåøåíèåì ýòîé ñèñòåìû ÿâëÿåòñÿ y2 = 1, y3 = 2. Ïîñêîëüêó ýòî ðåøåíèåíåîòðèöàòåëüíî, òî÷êà x00 ÿâëÿåòñÿ òî÷êîé ãëîáàëüíîãî ìèíèìóìà ôóíêöèè f (x) íà ìíîæåñòâå X .Ïðèìåð 2.
Ïðîâåðèòü òî÷êó x = (−1/2, 1/4) íà îïòèìàëüíîñòü â çàäà÷å f (x) = ex2 −→min ïðè îãðàíè÷åíèÿõ ϕ1 (x) ≡ (x1 + 1)2 − x2 ≤ 0, ϕ2 (x) ≡ (x1 − 1/2)2 + (x2 + 3/4)2 − 2 ≤ 0.Ðåøåíèå. Íåòðóäíî óáåäèòüñÿ, ÷òî äàííàÿ çàäà÷à ÿâëÿåòñÿ çàäà÷åé âûïóêëîãî ïðîãðàììèðîâàíèÿ. Ïîñêîëüêó ϕ1 (x) = ϕ2 (x) = 0, òî÷êà x ÿâëÿåòñÿ äîïóñòèìîé è I(x) = {1, 2}.Ñèñòåìà (3) äëÿ ýòîé òî÷êè èìååò âèä −f 0 (x) = y1 ϕ01 (x) + y2 ϕ02 (x), ò. å.
y1 − 2y2 = 0, −y1 +2y2 = −e1/4 . Î÷åâèäíî, ÷òî ýòà ñèñòåìà íåñîâìåñòíà. Îäíàêî äåëàòü âûâîä î íåîïòèìàëüíîñòè òî÷êè x ìû íå ìîæåì, ïîñêîëüêó íå áûëè ïðîâåðåíû óñëîâèÿ Ñëåéòåðà. È äåéñòâèòåëüíî, ñ ïîìîùüþ ãåîìåòðè÷åñêîãî ïîñòðîåíèÿ îáëàñòè äîïóñòèìûõ çíà÷åíèé ìîæíî óáåäèòüñÿ,÷òî îíà ñîñòîèò èç åäèíñòâåííîé òî÷êè x. Ñëåäîâàòåëüíî, óñëîâèå Ñëåéòåðà íå âûïîëíåíî,à òî÷êà x ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì (êàê åäèíñòâåííàÿ äîïóñòèìàÿ òî÷êà).Ïðèìåð 3. Ïðîâåðèòü òî÷êè x0 = (−3, 1, 2) è x00 = (−5, 3, 1) íà îïòèìàëüíîñòü â çàäà÷åf (x) = x21 +2x22 +30x1 −16x3 −→ min ïðè îãðàíè÷åíèÿõ 5x1 +3x2 −4x3 = −20, x1 −6x2 +3x3 ≤0, x3 ≥ 0.Ðåøåíèå. Öåëåâàÿ ôóíêöèÿ çàäà÷è âûïóêëà, à îãðàíè÷åíèÿ ëèíåéíû. Ñëåäîâàòåëüíî,èìååì çàäà÷ó âûïóêëîãî ïðîãðàììèðîâàíèÿ, ïðè÷¼ì ïðîâåðêà óñëîâèé ðåãóëÿðíîñòè Ñëåéòåðà íå òðåáóåòñÿ (çàìåòèì, êñòàòè, ÷òî ââèäó íàëè÷èÿ îãðàíè÷åíèÿðàâåíñòâà óñëîâèåÑëåéòåðà î÷åâèäíî íå âûïîëíÿåòñÿ).Ïðåæäå âñåãî, çàïèøåì îãðàíè÷åíèÿ çàäà÷è â ñòàíäàðòíîé ôîðìå, çàìåíèâ îãðàíè÷åíèåðàâåíñòâî íà äâà íåðàâåíñòâà.
Èìååì ϕ1 (x) ≡ 5x1 + 3x2 − 4x3 + 20 ≤ 0, ϕ2 = −ϕ1 (x) ≡−5x1 − 3x2 + 4x3 − 20 ≤ 0, ϕ3 ≡ x1 − 6x2 + 3x3 ≤ 0, ϕ4 (x) ≡ −x3 ≤ 0.Ëåãêî ïðîâåðèòü, ÷òî I(x1 ) = I(x2 ) = {1, 2}. Çíà÷èò, ñèñòåìà (3) äëÿ îáåèõ òî÷åê èìååòâèä −f 0 (x) = y1 ϕ01 (x) + y2 ϕ02 (x) = (y1 − y2 )ϕ01 (x). Ìû èñïîëüçîâàëè óñëîâèå ϕ2 (x) ≡ −ϕ1 (x),êîòîðîå âñåãäà âûïîëíÿåòñÿ ïðè çàìåíå îãðàíè÷åíèéðàâåíñòâ íà äâà íåðàâåíñòâà. Ïîñêîëüêó ðàçíîñòü äâóõ íåîòðèöàòåëüíûõ ÷èñåë ìîæåò ïðèíèìàòü çíà÷åíèÿ ëþáîãî çíàêà, à ëþáîå÷èñëî ìîæíî ïðåäñòàâèòü â âèäå ðàçíîñòè äâóõ íåîòðèöàòåëüíûõ ÷èñåë, òî, îñóùåñòâèâ çàìåíó y = y1 − y2 , ïðèõîäèì ê âûâîäó, ÷òî äëÿ îïòèìàëüíîñòè òî÷êè x∗ ∈ X â ñëó÷àåëèíåéíûõ îãðàíè÷åíèé íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâîâàíèÿ òàêèõ ÷èñåë yj ≥ 0, ñîîòâåòñòâóþùèõ îãðàíè÷åíèÿìíåðàâåíñòâàì, è ïðîèçâîëüíûõ ÷èñåë yj , ñîîòâåòñòâóþùèõîãðàíè÷åíèÿìðàâåíñòâàì, ÷òî24X−f 0 (x∗ ) =yj ϕ0j (x∗ ).j∈I(x∗ )Çàìåòèì, ÷òî îãðàíè÷åíèÿðàâåíñòâà âñåãäà ÿâëÿþòñÿ àêòèâíûìè îãðàíè÷åíèÿìè. ðàññìàòðèâàåìîì ïðèìåðå äëÿ òî÷êè x0 ïîëó÷èì ñèñòåìó −24 = 5y, −4 = 3y, 16 =−4y , êîòîðàÿ, î÷åâèäíî, íåñîâìåñòíà.
Çíà÷èò, òî÷êà x0 íå îïòèìàëüíà.Äëÿ òî÷êè x00 ñèñòåìà ïðèíèìàåò âèä −20 = 5y, −12 = 3y, 16 = −4y , ðåøåíèåì êîòîðîéÿâëÿåòñÿ y = −4. Ïîñêîëüêó ìíîæèòåëü y ñîîòâåòñòâóåò îãðàíè÷åíèþðàâåíñòâó, äëÿ íåãîíåò îãðàíè÷åíèÿ ïî çíàêó. Ñëåäîâàòåëüíî, òî÷êà x00 îïòèìàëüíà.Çàäà÷èÏðîâåðèòü óêàçàííûå òî÷êè íà îïòèìàëüíîñòü â çàäà÷àõ âûïóêëîãî ïðîãðàììèðîâàíèÿ:1) f (x) = −2x21 − 3x22 + x1 − 6 −→ maxX ,X = {x | x21 + x1 − 3 ≤ 0, 2x1 + x2 − 5 ≤ 0, x2 ≥ 0},x1 = (1, 1), x2 = (2, 1), x3 = (1/4, 0), x4 = (0, 0);2) f (x) = x21 + 3x1 −→ minX ,X = {x | x21 + x22 − 2x1 + 8x2 + 16 ≤ 0, x1 − x2 ≤ 5},x1 = (1, −4), x2 = (0, −4), x3 = (2, −4);3) f (x) = 7x21 + 2x22 − x1 x2 + x1 − x2 −→ minX ,X = {x | x1 + x2 ≤ 2, x1 − 3x2 ≤ 4, −2x1 + x2 ≤ −3},x1 = (5/2, −1/2), x2 = (1, −1), x3 = (2, 0);4) f (x) = x21 /2 + x22 − 5x1 + x2 −→ minX ,X = {x | x1 + x2 − 2x3 ≤ 3, 2x1 − x2 − 3x3 ≥ −11, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0},x1 = (1, 0, 2), x2 = (0, 0, −1), x3 = (1, 3, 0), x4 = (2, 1, 1), x5 = (5, 0, 1);5) f (x) = ex1 +x2 + x21 − 2x2 −→ minX ,X = {x | x2 ≤ ln x1 , x1 ≥ 1, x2 ≥ 0},x1 = (2, ln 2), x2 = (e, 0), x3 = (1, 0);6) f (x) = ex1 +x2 + x23 + 2x1 + 2x2 −→ minX ,X = {x | x21 + x22 + x23 ≤ 18, 2x1 + x2 − x3 + 3 ≤ 0},x1 = (−3, 3, 0), x2 = (1, −1, 4), x3 = (−3, −3, 0), x4 = (0, 0, 3);7) f (x) = −5x21 − 6x22 − x23 + 8x1 x2 + x1 −→ maxX ,X = {x | x21 − x2 + x3 ≤ 5, x1 + 5x2 ≤ 8, x1 ≥ 0, x2 ≥ 0},x1 = (0, 0, 0), x2 = (1, 0, 4), x3 = (3/14, 1/7, 0), x4 = (4, 0, −11);8) f (x) = −x21 − 2x22 + x1 x2 − 26 −→ maxX ,X = {x | x21 ≤ 25, x1 + 2x2 − 5 ≤ 0, x2 ≥ 0},x1 = (0, 0), x2 = (−1, 2), x3 = (0, −6), x4 = (3, 0);9) f (x) = 10x21 + 5x22 − x1 + 2x2 − 10 −→ minX ,X = {x | 2x21 + x2 ≤ 4, x1 + x2 ≤ 8, x1 ≥ 0},x1 = (0, 0), x2 = (1, 1), x3 = (0, −1);2510) f (x) = 4x21 + 3x22 + 4x1 x2 − x1 + 6x2 − 5 −→ minX ,X = {x | − x21 − x22 ≥ −3, 3x21 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0},x1 = (0, 0), x2 = (5, 0), x3 = (1, −1), x4 = (1, 1);11) f (x) = x21 + 5/2x22 − x1 x2 −→ minX ,X = {x | x21 − 4x1 − x2 ≤ −5, −x21 + 6x1 − x2 ≥ 7},x1 = (2, 1), x2 = (3, 2).4.
Ëèíåéíîå ïðîãðàììèðîâàíèå4.1. Ðàçëè÷íûå ôîðìû çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿÂâåä¼ì îáîçíà÷åíèÿ I = {1, . . . , m}, J = {1, . . . , n}, I1 , I2 ⊂ I, J1 ⊂ J, I1 ∪ I2 =I, I1 ∩ I2 = ∅. Ïóñòü çàäàíû âåùåñòâåííûå ÷èñëà cj , bi , aij (i ∈ I, j ∈ J).Òðåáóåòñÿ íàéòè ìèíèìóì ïî x ôóíêöèèw(x) =nXcj xj(1)j=1ïðè óñëîâèÿõai x − bi ≥ 0, i ∈ I1 ;(2)ai x − bi = 0, i ∈ I2 ;(3)xj ≥ 0, j ∈ J1 .(4)Çäåñü ai = (ai1 , . . . , ain ) i-ÿ ñòðîêà ìàòðèöû îãðàíè÷åíèé A, i ∈ I è x = (x1 , . .
. , xn )> âåêòîð ïåðåìåííûõ çàäà÷è.Çàäà÷à (1)(4) íàçûâàåòñÿ çàäà÷åé ëèíåéíîãî ïðîãðàììèðîâàíèÿ, çàäàííîé â îáùåé ôîðìå.Íàðÿäó ñ îáùåé ôîðìîé èñïîëüçóþòñÿ òàêæå êàíîíè÷åñêàÿ è ñòàíäàðòíàÿ ôîðìû. Êàêâ êàíîíè÷åñêîé, òàê è â ñòàíäàðòíîé ôîðìå âñå ïåðåìåííûå â ëþáîì äîïóñòèìîì ðåøåíèèäîëæíû ïðèíèìàòü íåîòðèöàòåëüíûå çíà÷åíèÿ, ò.
å. J1 = J . Òàêèå ïåðåìåííûå íàçûâàþòñÿíåîòðèöàòåëüíûìè â îòëè÷èå îò òàê íàçûâàåìûõ ñâîáîäíûõ ïåðåìåííûõ, íà êîòîðûå ïîäîáíîå îãðàíè÷åíèå íå íàêëàäûâàåòñÿ. Ïðè ýòîì â êàíîíè÷åñêîé ôîðìå çàäà÷è I1 = ∅, à âñòàíäàðòíîé I2 = ∅.Èñïîëüçóÿ ìàòðè÷íóþ çàïèñü, çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ â êàíîíè÷åñêîé ôîðìå ìîæíî ïðåäñòàâèòü ñëåäóþùèì îáðàçîì:w(x) = cx → min,(5)Ax = b,(6)x ≥ 0,(7)ãäå c = (c1 , . . . , cn ) âåêòîðñòðîêà, x è b = (b1 , .
. . , bm )> âåêòîðñòîëáöû, à A = (aij ) ìàòðèöà ðàçìåðíîñòè m × n.Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ â ñòàíäàðòíîé ôîðìå òîãäà çàïèøåòñÿ òàê:w(x) = cx → min,Ax ≥ b,x ≥ 0.26Çàäà÷à ËÏ â îáùåé ôîðìå ñâîäèòñÿ ê çàäà÷å ËÏ â êàíîíè÷åñêîé èëè ñòàíäàðòíîé ôîðìå. Ïîä ýòèì ïîíèìàåòñÿ ñóùåñòâîâàíèå îáùåãî ñïîñîáà ïîñòðîåíèÿ ïî èñõîäíîé çàäà÷å,çàäàííîé â îáùåé ôîðìå, íîâîé çàäà÷è ËÏ â íóæíîé íàì ôîðìå, ëþáîå îïòèìàëüíîå ðåøåíèå êîòîðîé ïðåîáðàçóåòñÿ â îïòèìàëüíîå ðåøåíèå èñõîäíîé çàäà÷è è íàîáîðîò. Òåì ñàìûì,íå òåðÿÿ îáùíîñòè, ìîæíî çàíèìàòüñÿ èçó÷åíèåì çàäà÷è ËÏ, ïðåäñòàâëåííîé, íàïðèìåð, âêàíîíè÷åñêîé ôîðìå.Ðàññìîòðèì íà ïðîñòûõ ïðèìåðàõ íåñêîëüêî ìåòîäîâ, ïîçâîëÿþùèõ ñäåëàòü òàêîå ïðåîáðàçîâàíèå çàäà÷è. Ïðåæäå âñåãî, íåñêîëüêî îáùèõ çàìå÷àíèé:1.
Ëþáàÿ çàäà÷à, â êîòîðîé òðåáóåòñÿ íàéòè ìàêñèìóì öåëåâîé ôóíêöèè, ñâîäèòñÿ êçàäà÷å íà ìèíèìóì óìíîæåíèåì öåëåâîé ôóíêöèè íà −1.2. Ëþáîå îãðàíè÷åíèåíåðàâåíñòâî âèäànXaij xj ≤ bij=1óìíîæåíèåì íà −1 ïðèâîäèòñÿ ê íåðàâåíñòâónXa0ij xj ≥ b0i ,j=1ãäå a0ij = − aij , b0i = − bi .3. Ëþáîå îãðàíè÷åíèåíåðàâåíñòâî âèäànXaij xj ≥ bij=1ñâîäèòñÿ ê ðàâåíñòâó ââåäåíèåì íîâîé íåîòðèöàòåëüíîé ïåðåìåííîé. Äëÿ ýòîãî äîñòàòî÷íîïîëîæèòünXyi =aij xj − bi ≥ 0.j=1Òîãäà ïîëó÷àåì îãðàíè÷åíèåðàâåíñòâînXaij xj − yi = bi ,j=1ïðè ýòîì, î÷åâèäíî, èñõîäíîå íåðàâåíñòâî ïðèíèìàåò âèä yi ≥ 0.4. Ëþáîå îãðàíè÷åíèåðàâåíñòâînXaij xj = bij=1ìîæíî ïðåäñòàâèòü â âèäå äâóõ íåðàâåíñòânXj=1aij xj ≥ bi ,nXaij xj ≤ bi .j=15.
Ëþáàÿ ñâîáîäíàÿ ïåðåìåííàÿ xj ìîæåò áûòü ïðåäñòàâëåíà ðàçíîñòüþ äâóõ íåîòðèöàòåëüíûõ ïåðåìåííûõ:xj = x1j − x2j , ãäå x1j ≥ 0, x2j ≥ 0.27Ïðèìåð 1. Ïðèâåñòè ê êàíîíè÷åñêîé ôîðìå (5)(7) çàäà÷óx1 + x2 → max,2x1 + x2 ≥ 1,x1 − x2 ≤ 0,x1 ≥ 0.Ðåøåíèå. Ñâîäèì èñõîäíóþ çàäà÷ó ê çàäà÷å íà ìèíèìóì, óìíîæèâ öåëåâóþ ôóíêöèþíà −1. Ïîëó÷èìw(x) = −x1 − x2 .Çàïèøåì îãðàíè÷åíèÿíåðàâåíñòâà â âèäå ðàâåíñòâ, ââåäÿ íîâûå íåîòðèöàòåëüíûå ïåðåìåííûå x3 ≥ 0, x4 ≥ 0 :2x1 + x2 − x3 = 1,x1 − x2 + x4 = 0.Çàìåíèì ñâîáîäíóþ ïåðåìåííóþ x2 ðàçíîñòüþ äâóõ íåîòðèöàòåëüíûõ ïåðåìåííûõ x5 ≥0, x6 ≥ 0 :x2 = x5 − x6 .Ïîñëå ýòèõ ïðåîáðàçîâàíèé èñõîäíàÿ çàäà÷à çàïèøåòñÿ â êàíîíè÷åñêîé ôîðìå:−x1 − x5 + x6 → min,2x1 − x3 + x5 − x6 = 1,x1 + x4 − x5 + x6 = 0,xi ≥ 0 (i = 1, 3, 4, 5, 6).Ïðèìåð 2.
Ïðèâåñòè ê ñòàíäàðòíîé ôîðìå çàïèñè çàäà÷ów(x) = 2x1 − x2 → min,x1 − x2 ≤ 1,2x1 + x2 = 2,x2 ≥ 0.Ðåøåíèå. Çàìåíèì ñâîáîäíóþ ïåðåìåííóþ x1 ðàçíîñòüþ äâóõ íåîòðèöàòåëüíûõ ïåðåìåííûõ x3 ≥ 0, x4 ≥ 0 :x1 = x3 − x4 .Çàïèøåì îãðàíè÷åíèåðàâåíñòâî â âèäå äâóõ íåðàâåíñòâ:2x1 + x2 ≤ 2,2x1 + x2 ≥ 2.Ïîñëå ýòîãî èñõîäíàÿ çàäà÷à ìîæåò áûòü çàïèñàíà â ñòàíäàðòíîé ôîðìå:−x2 + 2x3 − 2x4 → min,−x2 + x3 − x4 ≤ 1,x2 + 2x3 − 2x4 ≤ 2,−x2 − 2x3 + 2x4 ≤ −2,x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.Çàäà÷è1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
