Диссертация (1149954), страница 17
Текст из файла (страница 17)
íàõîæäåíèå îäíîãî îïòèìóìà Ïàðåòî;(b) ñî÷åòàíèå ñèìïëåêñ-ìåòîäà ñ îáõîäîì ãðàà â øèðèíó äëÿ íàõîæäåíèÿ âñåõ îïòèìóìîâ Ïàðåòî;3. Äëÿ âåùåñòâåííûõ ïîòîêîâ â ñåòè ñ íåïðåðûâíûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè àíàëîãè÷íûå ìåòîäû êóñî÷íî-ëèíåéíîãî ïðîãðàììèðîâàíèÿ äëÿ íàõîæäåíèÿ îïòèìóìîâ Ïàðåòî;Ñëîæíîñòü ýòèõ àëãîðèòìîâ òàêàÿ æå, êàê äëÿ àëãîðèòìîâ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ïîòîêîâ (ñì. ðàçäåë 2.2), òîëüêî ïðè îöåíå ñëîæíîñòè íóæíî áðàòü êîëè÷åñòâàâåðøèíN ′ = NTÒåîðåìà 11ðûøåé).è äóãM ′ = MTâ ñåòè, ðàçâåðíóòîé âî âðåìåíè.(ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ ïîòîêîâ ñ ïîëóãðóïïàìè âûèã-Ïóñòü äàíà çàäà÷à ìíîãîêðèòåðèàëüíîé ìèíèìèçàöèè îáîáùåííîé èíòåãðàëüíîéñòîèìîñòè ïîòîêà, ãäå ñòîèìîñòè ïðèíèìàþò çíà÷åíèÿ èç óïîðÿäî÷åííîé ïîëóãðóïïû R.Ïóñòü ïðèíöèï îïòèìàëüíîñòè îïòèìóì Ïàðåòî.
Òîãäà îïòèìàëüíûé äèñêðåòíûé äèíàìè÷åñêèé ïîòîê ìîæíî íàéòè ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ òî åñòüëþáîé ðåêóððåíòíûé ïîòîê îïòèìàëåí. À åñëè R óïîðÿäî÷åíà ñòðîãî ñëåâà, òî ëþáîé îïòèìàëüíûé ïîòîê ðåêóððåíòåí.Äîêàçàòåëüñòâî.ÅñëèRÏðèìåíèìîñòü äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ñëåäóåò èç òåîðåìû 9.óïîðÿäî÷åíà ñòðîãî ñëåâà, òî, ïî óòâåðæäåíèþ 8 îïòèìàëüíûé ïîòîê äèíàìè÷åñêèóñòîé÷èâ, à çíà÷èò, ïî íåçàâèñèìîñòè ïðèíöèïîâ îïòèìàëüíîñòè îò ïîñòîðîííèõ àëüòåðíàòèâè ï.4 òåîðåìû 7, îí ðåêóððåíòåí.Çàìå÷àíèå2.3.1. Ïðè ïîèñêå îïòèìóìîâ Ïàðåòî íà êàæäîì øàãå ìîæíî âîñïîëüçîâàòüñÿ ìî-äèèöèðîâàííûì ìåòîäîì ðåøåòà.
Åñëè ïîëóêîëüöî ñòîèìîñòåé óïîðÿäî÷åíî ñòðîãî ñëåâà,îí ïîçâîëèò íàéòè âñå îïòèìàëüíûå ïîòîêè. ïðèëîæåíèè ïðèâåäåíû 2 ïðèìåðà ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè äèíàìè÷åñêîãîïîòîêà.  îäíîì ïðèìåðå äèíàìè÷åñêèé ïîòîê â ñåòè ñ âîãíóòûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè îïòèìèçèðóåòñÿ ìåòîäîì ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Âî âòîðîì ïðèìåðå äèñêðåòíûé äèíàìè÷åñêèé ïîòîê îïòèìèçèðóåòñÿ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ(ñ äâèæåíèåì ïî âðåìåíè âïåðåä).752.3.2Ïðèìåð 1: ìîäåëü Ëåîíòüåâà ñ ðàçíûìè ïåðèîäàìè ïðîèçâîäñòâàÌîäåëü Ëåîíòüåâà ñ ðàçíûìè ïåðèîäàìè ïðîèçâîäñòâàÄàííûé ïðèìåð ïîñòðîåí ñîâìåñòíî ñ Æàðêîâîé À.Í.àññìîòðèì ìîäåëü Ëåîíòüåâà, â êîòîðîé ðàçíûå îòðàñëè èìåþò ðàçíóþ ïðîäîëæèòåëüíîñòü ïðîèçâîäñòâà, ïðè÷åì ïðîèçâîäñòâî îñóùåñòâëÿåòñÿ íå íåïðåðûâíî, à ëèøü â íåêîòîðûå ìîìåíòû âðåìåíè.Ïóñòü äàí íåêèéïðîèçâîäñòâåííûé ãðà (L, M),äëÿ êàæäîé äóãè(i, j) ∈ Mêîòîðîãîçàäàíû äâà íåîòðèöàòåëüíûõ âåùåñòâåííûõ ÷èñëà:• aij êîëè÷åñòâî ïðîäóêöèè îòðàñëè i, íåîáõîäèìîé äëÿ ïðîèçâîäñòâà åäèíèöû ïðîäóê-öèè îòðàñëè• tijj.
âðåìÿ ïðîèçâîäñòâà â îòðàñëèj. îáùåì ñëó÷àå,tijìîæåò çàâèñåòü òàêæå îòâðåìåíè òðàíñïîðòèðîâêè èç îäíîé îòðàñëè â äðóãóþ. Íî ìû ðàññìîòðèì ïðîñòåéøèéñëó÷àé, êîãäà âðåìÿ ïðîèçâîäñòâîtijâ îòðàñëèjçàâèñèò òîëüêî îòj.Ïðîèçâîäñòâåííûé ãðà îïèñûâàåò íàøè ïðîèçâîäñòâåííûå âîçìîæíîñòè ò.å. ïîêàçûâàåò, ÷òî ìû ìîæåì ñäåëàòü ñ èìåþùèìèñÿ ó íàñ ðåñóðñàìè. Ïóñòü âåêòîð âåùåñòâåííûõóíêöèéx(t) = (x1 (t), . . . xn (t)) êîëè÷åñòâî ïðîäóêöèèi-ãîîáîçíà÷àåò êîëè÷åñòâî ïðîäóêöèè âñåõ âèäîâ.
Òî åñòü,âèäà â ìîìåíò âðåìåíèt.Èìåÿ ïðîäóêöèþx(t),xi (t)ìû ìîæåì âêàæäûé ìîìåíò âðåìåíè îñóùåñòâèòü ïðîöåññ âëîæåíèÿ åå â ïðîèçâîäñòâî ðàçóìååòñÿ, òàê,÷òîáû ïðîäîëæàëî âûïîëíÿòüñÿ íåðàâåíñòâîx(t) ≥ 0.Òàêèì îáðàçîì, ðàñïðåäåëåíèå ïðî-äóêöèè ýòî, ïî íàøåé òåðìèíîëîãèè, äèñêðåòíûé äèíàìè÷åñêèé ïîòîê â ñåòè ñ âîãíóòûìèêóñî÷íî-ëèíåéíûìè óñèëåíèÿìè óíêöèÿìè Ëåîíòüåâà.àññìîòðèì çàäà÷ó ìàêñèìèçàöèè êîëè÷åñòâà ýêñïîðòèðóåìîé èëè ïîòðåáëÿåìîé ïðîäóêöèè â ìîäåëè Ëåîíòüåâà. Ïî íàøåé òåðìèíîëîãèè, ýòî çàäà÷à ìàêñèìèçàöèè äèíàìè÷åñêîãî äèñêðåòíîãî ïîòîêà. Ñîîòâåòñòâóþùóþ çàäà÷ó ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ìîæíîðåøèòü, ñâåäÿ äèíàìè÷åñêèé ïîòîê ê ñòàòè÷åñêîìó.
Îïòèìàëüíûé ñòàòè÷åñêèé ïîòîê äëÿâîãíóòûõ íåïðåðûâíî-ëèíåéíûõ ñâåðòîê êðèòåðèåâ ìîæíî íàéòè, ñâåäÿ çàäà÷ó ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ.  êà÷åñòâå ïðèìåðà íàéäåì êîìïðîìèññíîå ðåøåíèå îíî îïòèìàëüíî ïî Ïàðåòî.Ïðèìåð ìîäåëèÏóñòü èìååòñÿ 2 îòðàñëè, ïðè÷åì êàæäàÿ îòðàñëü çàâèñèò îò ñåáÿ ñ êîýèöèåíòîìa22 = 0.5,à 2-ÿ îòðàñëü çàâèñèò îò 1-é ñ êîýèöèåíòîìa12 = 1.a11 =Ïóñòü ïðîäîëæèòåëüíîñòü76ïðîèçâîäñòâà â 1-é îòðàñëè ðàâíà0.23,à âî 2-é îòðàñëè ðàâíà1.Ïóñòü ãîðèçîíò ïëàíèðîâà-íèÿ ñîñòàâëÿåò 2 ïåðèîäà âðåìåíè.
Óìíîæèâ ïðîäîëæèòåëüíîñòè ïðîèçâîäñòâà íàïîëó÷èì äèñêðåòíîå âðåìÿ ïðîèçâîäñòâàt1 = 23, t2 = 100100,ìûè êîëè÷åñòâî ìîìåíòîâ âðåìåíèT = 200.Ïîñêîëüêó ïðîäîëæèòåëüííîñòè ïðîèçâîäñòâà ðàçëè÷íû, ìû íå ìîæåì ñîñòàâèòü ïðîèçâîäñòâåííóþ ìàòðèöóA è îáû÷íûåíåðàâåíñòâàAx(t + 1) ≤ x(t) âìåñòî ýòîãî íóæíî îïòè-ìèçèðîâàòü äèñêðåòíûé ïîòîê â ïðîèçâîäñòâåííîì ãðàå. Âëèÿíèå îäíèõ ïðîèçâîäñòâåííûõïðîöåññîâ íà äðóãèå ýòî äóãè ãðàà. Âëèÿíèå ÷åðåçðîâàòü, ââîäÿNNìîìåíòîâ âðåìåíè ìîæíî ìîäåëè-ïðîìåæóòî÷íûõ âåðøèí íà äóãå.Äëèíû ïóòåé â ïðîèçâîäñòâåííîì ãðàå äî ìîìåíòà 2:t = 0, 23, 46, 69, 92, 100, 115, 123, 138, 146, 161, 169, 184, 192, 200.ÈòîãîN = 15 ìîìåíòîââðåìåíè, â êîòîðûå è ïðîèñõîäèò èçìåíåíèå ïåðåìåííûõx1 (t), x2 (t) êîëè÷åñòâà ïðîäóêöèè â 1-é è âî 2-é îòðàñëè.
Êîëè÷åñòâî ïðîäóêöèè â 1-é îòðàñëè ìåíÿåòñÿ â ìîìåíòû âðåìåíè, êîòîðûå ÿâëÿþòñÿ äëèíàìè ïóòåé ñ êîíöîì â 1-é âåðøèíå:t = 0, 23, 46, 69, 92, 115, 138, 161, 184.Ìåæäó ýòèìè ìîìåíòàìè êîëè÷åñòâî â 1-é îòðàñëè íå ìåíÿåòñÿ:x1 (100) = x1 (92)x1 (123) = x1 (115)x1 (146) = x1 (138)x1 (169) = x1 (161)x1 (200) = x1 (192) = x1 (184).Êîëè÷åñòâî ïðîäóêöèè âî 2-é îòðàñëè ìåíÿåòñÿ â ìîìåíòû âðåìåíè, êîòîðûå ÿâëÿþòñÿäëèíàìè ïóòåé ñ êîíöîì â 2-é âåðøèíå:t = 0, 100, 123, 146, 169, 192, 200.77Ìåæäó ýòèìè ìîìåíòàìè êîëè÷åñòâî âî 2-é îòðàñëè íå ìåíÿåòñÿ:x2 (92) = x2 (69) = x2 (46) = x2 (23) = x2 (0)x2 (115) = x2 (100)x2 (138) = x2 (123)x2 (161) = x2 (146)x2 (184) = x2 (169).Îãðàíè÷åíèÿ íà êîëè÷åñòâî ïðîäóêöèè â 1-é îòðàñëè îïðåäåëÿþò òàêèå íåðàâåíñòâà:0.5x1 (23) + x2 (100) ≤ x1 (0)0.5x1 (46) + x2 (123) ≤ x1 (23)0.5x1 (69) + x2 (146) ≤ x1 (46)0.5x1 (92) + x2 (169) ≤ x1 (69)0.5x1 (115) + x2 (192) ≤ x1 (92)0.5x1 (138) ≤ x1 (115)0.5x1 (161) ≤ x1 (138)0.5x1 (184) ≤ x1 (161).Ïåðåìåííûåx1 (t), x2 (t),ãäåt ≥ 2,â íåðàâåíñòâàõ îïóùåíû, ïîñêîëüêó èõ çíà÷åíèå çà ïðå-äåëîì ãîðèçîíòà ïëàíèðîâàíèÿ ìîæíî ñ÷èòàòü ðàâíûì 0.Îãðàíè÷åíèÿ íà êîëè÷åñòâî ïðîäóêöèè âî 2-é îòðàñëè îïðåäåëÿþò òàêèå íåðàâåíñòâà:0.5x2 (100) ≤ x2 (0)0.5x2 (123) ≤ x2 (23)0.5x2 (146) ≤ x2 (46)0.5x2 (169) ≤ x2 (69)0.5x2 (192) ≤ x2 (92)0.5x2 (200) ≤ x2 (100).Èòîãî ïîëó÷àåì 14 íåðàâåíñòâ îòíîñèòåëüíî 30 íåèçâåñòíûõ, è åùå óñëîâèÿ íåîòðèöàòåëüíîñòè.
Ýòè íåðàâåíñòâà ìîæíî ïðåäñòàâèòü â ìàòðè÷íîì âèäå, îáðàçîâàâ 4 îãðîìíûå ðàçðåæåííûå (ñ áîëüøèì êîëè÷åñòâîì íóëåé) êâàäðàòíûå íåîòðèöàòåëüíûå ìàòðèöûA11 , A12 , A21 , A22 :A11 x1 + A12 x2 ≤ x1A21 x1 + A22 x2 ≤ x2x1 , x2 ≥ 0(2.2)78ãäåx1 , x2âðåìåíè âåêòîðà ðàçìåðàt1 , . . . t15 .N = 15,ïðåäñòàâëÿþùèå êîëè÷åñòâî ïðîäóêöèè â ìîìåíòûÊ íèì åùå íóæíî äîáàâèòü óêàçàííûå âûøå ðàâåíñòâà, ïîêàçûâàþùèå,÷òî ïðîäóêöèÿ 1-é è 2-é îòðàñëè íå ìåíÿåòñÿ â òå ìîìåíòû âðåìåíè, êîòîðûå ê íåé íå èìåþòíèêàêîãî îòíîøåíèÿ.Êàæäîå íåðàâåíñòâî îïðåäåëÿåò íåîòðèöàòåëüíûé âåêòîð ïîòðåáëåíèÿ (èëè ýêñïîðòà)ïðîäóêöèè 1-é è 2-é îòðàñëèc1 (t), c2 (t):c1 = x1 − A11 x1 − A12 x2 = (E − A11 )x1 − A12 x2c2 = x2 − A21 x1 − A22 x2 = (E − A22 )x2 − A21 x1Ïóñòü ïîëåçíîñòè îò ïîòðåáëåíèÿ ïðîäóêöèè òåðìèíàëüíûå:çîì, ìû ïîëó÷àåì 2 ëèíåéíûõ îòíîñèòåëüíîxc1 (T ), c2 (T ).Òàêèì îáðà-êðèòåðèÿ, êàæäûé èç êîòîðûõ ìîæíî ìàêñè-ìèçèðîâàòü ïðè óñëîâèè âûïîëíåíèÿ íåðàâåíñòâ (A.6), ðåøèâ ñîîòâåòñòâóþùóþ ÇËÏ.Ñîñòàâëåíà ïðîãðàììà, êîòîðàÿ ñ÷èòàåò îïòèìóì äëÿ êàæäîãî âèäà ïðîäóêöèè è êîìïðîìèññíîå ðåøåíèå.
Èñõîäíûé òåêñò ïðîãðàììû ïðèâåäåí â ïðèëîæåíèè. Ïðè ìàêñèìèçàöèè1-ãî êðèòåðèÿ ïîëó÷àåì, êàê è ñëåäîâàëî îæèäàòü, òàêóþ äèíàìèêó ðàçâèòèÿ êîëè÷åñòâàïðîäóêöèè:x1 = (1, 2, 4, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 256)x2 = (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)Ýòî ïîíÿòíî: åñëè íàñ èíòåðåñóåò òîëüêî ïðîäóêöèÿ òÿæåëîé ïðîìûøëåííîñòè, òî íåâûãîäíîâêëàäûâàòü â ëåãêóþ ïðîìûøëåííîñòü íè÷åãî (äàæå ñàìóþ ìàëîñòü). Ïðè ýòîì äîñòèãàåòñÿïîëåçíîñòü, ðàâíàÿ 256.Ïðè ìàêñèìèçàöèè 2-ãî êðèòåðèÿ ïîëó÷àåì áîëåå èíòåðåñíûé ðåçóëüòàò:x1 = (1, 0.2222, 0.4444, 0.8889, 1.7778, 1.7778, 2.2198, 2.2198, 3.9627, 3.9627,6.8802, 6.8802, 11.4453, 11.4453, 11.4453)x2 = (1, 1, 1, 1, 1, 0.8889, 0.8889, 0, 0, 0, 0, 0, 0, 0.5612, 1.7778)Èíà÷å ãîâîðÿ, â ëåãêîé ïðîìûøëåííîñòè áûâàþò ïåðèîäû, êîãäà âûãîäíî íè÷åãî íå ïðîèçâîäèòü, à â íåêîòîðûå ïåðèîäû âûãîäíî ðàçâåðíóòü àêòèâíîå ïðîèçâîäñòâî, ïîëüçóÿñü òåì, êàêðàçâèëàñü òÿæåëàÿ ïðîìûøëåííîñòü.
Ïðè ýòîì äîñòèãàåòñÿ ïîëåçíîñòü, ðàâíàÿ ïðèìåðíî1.7778.Íàéäåì òåïåðü êîìïðîìèññíîå ðåøåíèå ìåòîäîì ëèíåéíîãî ïðîãðàììèðîâàíèÿ. åçóëüòàò79Òàáëèöà 2.1: Äàííûå î äîìàõÍîâûé äîìåêîíñòðóêöèÿ1.51Òåððèòîðèÿ (åä.)Âðåìÿ ñòðîèòåëüñòâà (ëåò)32Ñåáåñòîèìîñòü äîìà (ðóá.)194 000 00090 000 000Ñòîèìîñòü äîìà (ðóá.)1 620 000 000486 000 000òàêîâ:x1 = (1, 1.9862, 3.9724, 7.9449, 15.8898, 15.8898, 31.7795, 31.7795, 63.5590, 63.5590,127.1180, 127.1180, 254.2360, 254.2360, 254.2360)x2 = (1, 1, 1, 1, 1, 0.0069, 0.0069, 0, 0, 0, 0, 0, 0, 0, 0.0138)Êîìïðîìèññíîå îòêëîíåíèå îò îïòèìàëüíîãî âûèãðûøà ñîñòàâëÿåò1.7640. Äëÿ òÿæåëîé ïðî-ìûøëåííîñòè ýòî íåçíà÷èòåëüíîå çàìåäëåíèå ðàçâèòèÿ, à ëåãêàÿ ïðîìûøëåííîñòü â òàêîìêîìïðîìèññíîì ñëó÷àå ðàçâèâàåò ýåêòèâíîñòü, ðàâíóþ ëèøü îêîëî2.3.3îïòèìàëüíîé.Ïðèìåð 2: ðàñïðåäåëåíèå ðåñóðñîâ ìåæäó ïðîåêòàìèàññìîòðèì çàäà÷ó ðàñïðåäåëåíèÿ 2-õ ðåñóðñîâðàáîò8%x1 , x2 ,s, yäëÿ âûïîëíåíèÿ 2-õ ïîâòîðÿþùèõñÿêàæäàÿ èç êîòîðûõ çàíèìàåò çàäàííîå äèñêðåòíîå âðåìÿT1 , T2 .ðàáîò òðåáóåò íåêîòîðûõ çàòðàò ðåñóðñîâ è, â ñâîþ î÷åðåäü, ïðîèçâîäèò ðåñóðñÊàæäàÿ èçy,êîòîðûéìîæíî èíòåðïðåòèðîâàòü êàê äåíüãè.
Ýòî çíà÷èò, ÷òî ãðàèê ðàáîò ìîæíî ìîäåëèðîâàòüîáîáùåííûì äèíàìè÷åñêèì ïîòîêîì â ñåòè. Ïîñêîëüêó êàæäóþ ðàáîòó ìîæíî ïðîèçâåñòèöåëîå ÷èñëî ðàç, ýòîò ïîòîê äèñêðåòíûé.Ïîñòàâèì äëÿ äàííîãî äèíàìè÷åñêîãî ïîòîêà çàäà÷ó íàõîæäåíèÿ ìíîæåñòâà Ïàðåòî ïîâðåìåíè âûïîëíåíèÿ è êîíå÷íîìó êîëè÷åñòâó ðåñóðñày(äåíåã). Ïîñêîëüêó ìíîæåñòâî Ïà-ðåòî ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâî, à ïîòîê äèñêðåòíûé, çàäà÷ó ìîæíî ðåøèòü ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.Ïðèìåð: ñòðîèòåëüñòâî äîìîâÄàííûé ïðèìåð ïîñòðîåí ñîâìåñòíî ñ Ïàðøèíîé Ë..àññìîòðèìçàäà÷óñòðîèòåëüñòâàèëèðåêîíñòðóêöèèñòàðûõäîìîâ.àáîòà1ñòðîèòåëüñòâî íîâîãî äîìà íà ìåñòå ñíåñåííûõ ñòàðûõ äîìîâ, ðàáîòà 2 ðåêîíñòðóêöèÿñòàðîãî äîìà. åñóðñ 1 òåððèòîðèÿ, ðåñóðñ 2 äåíüãè. Äàííûå î äîìàõ ìîæíî ñâåñòè âòàáëèöó 2.1 (òåððèòîðèÿ èçìåðÿåòñÿ îòíîñèòåëüíî ïëîùàäè ñòàðîãî äîìà).Ïóñòü ó èðìû åñòüèy(0) = 500s(0) = 5åäèíèö òåððèòîðèè, íà êîòîðûõ ñòîÿò 5 ñòàðûõ äîìîâ,ìëí.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
