Диссертация (1149954), страница 10
Текст из файла (страница 10)
Ïî àíàëîãèè ñî ñòàòè÷åñêèì ïîòîêîì, êîíêðåòèçèðóåì ýòî îïðåäåëåíèå, îïðåäåëèâ äèíàìè÷åñêèé ïîòîê â ñåòè, ìîäåëèðóþùèé äåòåðìèíèðîâàííûå äèíàìè÷åñêèå ëîãèñòè÷åñêèå ñèñòåìû. Ïðè ýòîì, ïîñêîëüêó ìû ðàññìàòðèâàåì äèñêðåòíîå âðåìÿ,îïðåäåëåíûäèñêðåòíî-äèíàìè÷åñêèå ïîòîêè,ìîìåíòîâ âðåìåíèT = {1, . . . , T }.Îïðåäåëåíèå 14. Äèíàìè÷åñêàÿ ñåòü Nêîâs′ ,Fêîòîðûå ñóùåñòâóþò ëèøü â êîíå÷íîå ÷èñëî ýòî ìóëüòèãðà(L, M, s, e),äîïóñòèìûå äåèöèòûgl : F |m|e(m)=l| → F, l ∈ Lv: L → F,ñ ÷àñòè÷íî óïîðÿäî÷åííîé àáåëåâîé ãðóïïîé ïîòî-äëÿ êîòîðîãî, àíàëîãè÷íî ñòàòè÷åñêîé ñåòè, çàäàí ñòîêïðîïóñêíûå ñïîñîáíîñòèè óíêöèè ñòîèìîñòèc: M → F,pm : F → R, m ∈ M .îòëè÷èè îò ñòàòè÷åñêîé ñåòè, âîîáùå ãîâîðÿ, çàâèñÿò îò âðåìåíè:Ïðè ýòîì êàæäàÿ âåðøèíàx ýòîñóììàòîð-óñèëèòåëüóíêöèè óñèëåíèÿÏàðàìåòðûv, c, g, p,âv t , ct , g t , p t .ñ óñèëåíèåìgxt ,òî åñòü èìååòìíîæåñòâî ñîñòîÿíèéSx (f (t − 1), t) = [gx ({f (m, t − 1)}e(m)=x , t); gx ({f (m, t − 1)}e(m)=x , t) + v(x, t)].Ìíîæåñòâà ñîñòîÿíèé äóã îïðåäåëÿþòñÿ â çàâèñèìîñòè îò òèïà âåðøèíû: ðàñïðåäåëèòåëü,ðàçìíîæèòåëü èëè ðàñïðåäåëèòåëü ñ ñîõðàíåíèåì.1.àñïðåäåëèòåëü ýòî âåðøèíàUx (sx (t), t) =Ys(m)=xx,äëÿ êîòîðîé ìíîæåñòâà ñîñòîÿíèé äóã[0; c(m, t)] ∩ {(f1 , .
. . , fk ) | f1 + · · · + fk ≤ sx (t)}(ðàñïðåäåëåíèå ïîòîêà ïî èñõîäÿùèì äóãàì)442.àçìíîæèòåëü ýòî âåðøèíàx,YUx (sx (t), t) =s(m)=xäëÿ êîòîðîé ìíîæåñòâà ñîñòîÿíèé äóã[0; c(m, t)] ∩ {(sx (t), sx (t), . . . , sx (t))}(òèðàæèðîâàíèå ïîòîêà ïî èñõîäÿùèì äóãàì).3.Ñóììàòîð-óñèëèòåëü è ðàñïðåäåëèòåëü ñ ñîõðàíåíèåìíàxñ óñèëåíèåìñ ìíîæåñòâîì ñîñòîÿíèé, ñîñòîÿùèì èç äâóõ êîìïîíåíògxt ýòî âåðøè-(sx (t), sx (t)),ýòî, âîîáùå ãîâîðÿ, ñîñòîÿíèå ïåòëè, îïðåäåëÿþùåé âëèÿíèå âåðøèíûxãäåsx (t)íà ñàìó ñåáÿ.Ìíîæåñòâî ñîñòîÿíèé âåðøèíû:Sx (f (t − 1), sx (t − 1), t) = {gx ({f (m, t − 1)}e(m)=x , t) + sx (t − 1)}Ìíîæåñòâî ñîñòîÿíèé äóã:Y[0; c(m, t)] ∩ {(sx (t), f1 , .
. . , fk ) | sx (t) + f1 + · · ·+ fk ≤ sx (t)}1.3.1. Ñîäåðæàòåëüíî,sx ýòî êîëè÷åñòâî ïîòîêà, êîòîðîå ñîõðàíÿåòñÿ â âåðøèíåUx (sx (t), t) = [0; vx (t)] ×Çàìå÷àíèåxs(m)=xè ìîæåò áûòü èñïîëüçîâàíî â äàëüíåéøåì. Ôîðìàëüíî, ýòî ñîñòîÿíèå äóãè, êîòîðàÿ èäåòèç âåðøèíûxâ ñàìó æå ýòó âåðøèíó (ïåòëè).Îïðåäåëåíèå 15.
Äèíàìè÷åñêèé ïñåâäîïîòîêâ ñåòèN ýòî äèíàìè÷åñêèé ïîòîêäëÿ êîòîðîãî ñîñòîÿíèå ñóììàòîðà-óñèëèòåëÿ ïðèíàäëåæèòv(x, t)],à äëÿ ñóììàòîðà-óñèëèòåëÿ ñ ñîõðàíåíèåìpm : F × T → R, m ∈ M ,[−∞; gx ({f (m, t − 1)}e(m)=x , t) +sx (t) ∈ [−∞; v(x, t)].Åñëè çàäàíî ïîëîæèòåëüíîå ïîëóêîëüöî çíà÷åíèéñòîèìîñòè(f, s),Rè çàâèñÿùèå îò âðåìåíè óíêöèèòî ìîæíî ïîñòàâèòü çàäà÷ó îá îáùåì äèíàìè÷åñêîì(ïñåâäî)ïîòîêå ìèíèìàëüíîé ñòîèìîñòèminf,sXXptm (f (m, t))t∈T m∈M(ñóììà áåðåòñÿ ïî âñåì ìîìåíòàì âðåìåíè). Ïðè ýòîì âåëè÷èíà äèíàìè÷åñêîãî ïîòîêà âñòîêås′ðàâíà−Vf (s′ ) = −XVf (s′ , t).t∈TÄàííîå îïðåäåëåíèå îáîáùàåò êëàññè÷åñêîå îïðåäåëåíèå äèíàìè÷åñêîãî (ìíîãîïðîäóêòîâîãî) ïîòîêà [71℄ (âîçìîæíî, ñ ñîõðàíåíèåì).
Ýòî ïðîñòî äèíàìè÷åñêèé (ìíîãîïðîäóêòîâûé)45ïîòîê â ñåòè, âñå âåðøèíû êîòîðîé ñóììàòîðû áåç óñèëåíèé è ðàñïðåäåëèòåëè (âîçìîæíî,ñ ñîõðàíåíèåì).Çàìå÷àíèå1.3.2 (î ëîêàëüíîñòè è ãëîáàëüíîñòè). Äèíàìè÷åñêàÿ ñåòü ýòî ìîäåëü äèñêðåò-íîãî ïðîñòðàíñòâà-âðåìåíè, â êîòîðîì çàäàíî öåëåïîëàãàíèå (îïòèìèçàöèîííàÿ çàäà÷à).Îäíàêî â ñèñòåìå, â êîòîðîé èìååòñÿ îïòèìèçàöèîííàÿ çàäà÷à, âåðøèíû ñâÿçûâàåò ìåæäó ñîáîé íå òîëüêî âçàèìîäåéñòâèå. Èçìåíåíèå ñîñòîÿíèÿ îäíîé äóãè (íàïðèìåð, óìåíüøåíèååå ïðîïóñêíîé ñïîñîáíîñòè) ìîæåò èçìåíèòü çíà÷åíèå îïòèìàëüíîãî ïîòîêà â äðóãîé äóãå,íàõîäÿùåéñÿ ñêîëü óãîäíî äàëåêî îò ïåðâîé (ñêàæåì, âîçíèêíåò íåîáõîäèìîñòü ïåðåíàïðàâèòü ÷àñòü ïîòîêà ïî äðóãîé äóãå).
Ò.å. íàëè÷èå îïòèìèçàöèîííîé çàäà÷è êàê áû ñâÿçûâàåòâñå âåðøèíû â åäèíîå öåëîå áåç ïåðåíîñà âçàèìîäåéñòâèé ìåæäó íèìè. Òî÷íî òàê æå â îïòèìèçàöèîííîé çàäà÷å èìååòñÿ âëèÿíèå áóäóùåãî íà ïðîøëîå ÷åðåç ïðîãíîç. Ýòî çíà÷èò,÷òî íåâîçìîæíî ðåøèòü çàäà÷ó, ó÷èòûâàÿ òîëüêî ëîêàëüíîå îêðóæåíèå âåðøèíû.
Íóæíîó÷èòûâàòü ãëîáàëüíî âñþ ñåòü.1.3.2×àñòíûå ñëó÷àè. Ìîäåëü Íåéìàíà êàê óíèâåðñàëüíàÿ äèíàìè÷åñêàÿ ìîäåëüÊîìáèíèðóÿ ñóììàòîðû-ðàñïðåäåëèòåëè ñ ñîõðàíåíèåì è áåç ñîõðàíåíèÿ è ñóììàòîðûðàçìíîæèòåëèè, ìîæíî ïîëó÷àòü ðàçëè÷íûå êëàññè÷åñêèå ìîäåëè ëîãèñòè÷åñêèõ ñèñòåì.Ïðèìåð 5. Ìîäåëü Ëåîíòüåâà[3℄ ñnîòðàñëÿìè, îïèñûâàåìàÿ ñèñòåìîé ëèíåéíûõ íåðà-âåíñòâAx(t + 1) ≤ x(t)x(t) ≥ 0,ãäåA≥0 êâàäðàòíàÿ âåùåñòâåííàÿ ìàòðèöà ðàçìåðàíûé ýëåìåíò â êàæäîì ñòîëáöå,ïðåäñòàâëåíèå ñåòü ñnx(t)n-ìåðíûén,èìåþùàÿ õîòÿ áû 1 ïîëîæèòåëü-âåùåñòâåííûé âåêòîð. Åå ýêâèâàëåíòíîåâåðøèíàìè ñóììàòîðàìè-óñèëèòåëè è ðàñïðåäåëèòåëÿìè, â êî-òîðûõ óñèëåíèå â êàæäîé âåðøèíåj óíêöèÿ Ëåîíòüåâàgj (y1 , .
. . , yn ) = min(y1 /a1j , . . . , yn /anj )(åñëèaij = 0, ÷ëåí yi /aijèñêëþ÷àåòñÿ ïðè ýòîì, ïî ñâîéñòâó ìàòðèöû(1.9)A, õîòÿ áû 1 àðãóìåíòâ ìèíèìóìå åñòü), à ïðîïóñêíàÿ ñïîñîáíîñòü êàæäîé äóãè áåñêîíå÷íà. Äèíàìèêà ðàçâèòèÿîòðàñëåé äèñêðåòíî-äèíàìè÷åñêèé ïîòîê â ýòîé ñåòè.Ïðèìåð 6. Ìîäåëü Íåéìàíà(íåïðåðûâíàÿ) [3℄ ñm îòðàñëÿìè è n ïðîäóêòàìè, îïèñûâàåìàÿ46ñèñòåìîé ëèíåéíûõ íåðàâåíñòâAx(t + 1) ≤ Bx(t)(1.10)x(t) ≥ 0,ãäåA, B ≥ 0 âåùåñòâåííûå ìàòðèöû ðàçìåðà1 ïîëîæèòåëüíûé ýëåìåíò â êàæäîì ñòîëáöå,nx(t)íàm,ïðè÷åì ìàòðèöàm-ìåðíûéAèìååò õîòÿ áûâåùåñòâåííûé âåêòîð. Ååýêâèâàëåíòíîå ïðåäñòàâëåíèå ñåòü, â êîòîðîé ãðà äâóäîëüíûé.m âåðøèíïåðâîé äîëè ñóììàòîðû-óñèëèòåëè è ðàçìíîæèòåëè ñ óñèëåíèÿìè â âåðøèíàõ óíêöèÿìè Ëåîíòüåâà(1.9), îïðåäåëÿþùèìè ìàòðèöó çàòðàòA,ànâåðøèí âòîðîé äîëè ñóììàòîðû-óñèëèòåëèè ðàñïðåäåëèòåëè ñ ëèíåéíûìè óñèëåíèÿìè â äóãàõâûïóñêàB .
Äóãè, âåäóùèåg(i,j) (x) = bji x,îïðåäåëÿþùèìè ìàòðèöóâ ñóììàòîðû-ðàçìíîæèòåëè, îïðåäåëÿþò èíòåíñèâíîñòè òåõíîëî-ãè÷åñêèõ ïðîöåññîâ, à äóãè, âåäóùèå â ñóììàòîðû-ðàñïðåäåëèòåëè êîëè÷åñòâà ïðîäóêòîâ.Ïðîïóñêíàÿ ñïîñîáíîñòü êàæäîé äóãè áåñêîíå÷íà. Äèíàìèêà ðàçâèòèÿ îòðàñëåé ýòî äèíàìè÷åñêèé ïîòîê â ýòîé ñåòè.Âåðíî è îáðàòíîå:Óòâåðæäåíèå 1.3.1. Ïóñòü çàäàíà ñåòü ñ ñóììàòîðàìè-ðàñïðåäåëèòåëÿìè ñ óñèëåíèåìè ñóììàòîðàìè-ðàçìíîæèòåëÿìè ñ óñèëåíèåì, â êîòîðîé F = R, à âñå óíêöèè óñèëåíèÿ âîãíóòûå êóñî÷íî-ëèíåéíûå. Òîãäà ñóùåñòâóåò ìîäåëü Íåéìàíà (A, B) òàêàÿ, ÷òîåñòü âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ìíîæåñòâîì ïñåâäîïîòîêîâ â ýòîé ñåòèè ìíîæåñòâîì äîïóñòèìûõ ïëàíîâ â ìîäåëè Íåéìàíà.Äîêàçàòåëüñòâî.•Äëÿ íà÷àëà, ðàçäåëèì êàæäóþ âåðøèíóñóììàòîð ñ óñèëåíèåìa′ ,aíà äâå âåðøèíû:èç êîòîðîãî âûõîäèò îäíà äóãàma åãî áóäåì äëÿ óäîáñòâàñ÷èòàòü ðàçìíîæèòåëåì;•ðàñïðåäåëèòåëü èëè ðàçìíîæèòåëüa′′ ,â êîòîðûé âõîäèò îäíà äóãàma .Ïðîïóñêíóþ ñïîñîáíîñòü ýòîé äóãè áóäåì ñ÷èòàòü áåñêîíå÷íîé.Òåïåðü ïåðåíóìåðóåì äóãè, ïðè÷åì áóäåì ñ÷èòàòü, ÷òî äóãè, âûõîäÿùèå èç âåðøèíûðàçìíîæèòåëÿ, èìåþò îäèí è òîò æå íîìåð.
Òî åñòü ìíîæåñòâî äóã:çíà÷èìyi (t) = f (i, t) ïîòîê â äóãåiâ ìîìåíò âðåìåíèt.M = {1, . . . , m}.Îáî-Ïîñêîëüêó ïîòîêè âî âñåõ äóãàõ,âûõîäÿùèõ èç âåðøèíû-ðàçìíîæèòåëÿ, ðàâíû, òàêîå îïðåäåëåíèå êîððåêòíî.Òîãäà âåëè÷èíû ïñåâäîïîòîêîâ â äóãàõyi (t) ýòî íåîòðèöàòåëüíûåêîòîðûå îïðåäåëÿþòñÿ ëèáî íåðàâåíñòâîì âèäàyi (t + 1) ≤ gi (y1 (t), . . . , ym (t))âåùåñòâåííûå ÷èñëà,47yi(åñëè äóãàâûõîäèò èç ðàçìíîæèòåëÿ), ëèáî áîëåå îáùèì íåðàâåíñòâîì âèäàXj∈Ji(åñëè äóãèj, j ∈ Ji ,yj (t + 1) ≤ gi (y1 (t), . .
. , ym (t))âûõîäÿò èç ðàñïðåäåëèòåëÿ), ãäågi(1.11) íåîòðèöàòåëüíûå âîãíóòûåêóñî÷íî-ëèíåéíûå óíêöèè. Ëþáóþ òàêóþ óíêöèþ ìîæíî ïðåäñòàâèòü â âèäågi (x) = min (pik · x + qik ),k∈Kiïðè÷åì, åñëè óíêöèÿòî âåêòîðpik ≥ 0ègiíåîòðèöàòåëüíà, âîçðàñòàåò è åå îáëàñòü îïðåäåëåíèÿ ñîäåðæèò 0,qik ≥ 0(ñì. ïðèëîæåíèå A.1).
Ýêâèâàëåíòíàÿ (1.11) ñèñòåìà íåðàâåíñòâ:Xj∈Jiyj (t + 1) ≤ pik · y(t) + qik ∀k ∈ KiÝòó ñèñòåìó ìîæíî ïðåäñòàâèòü â ìàòðè÷íîì âèäåA′ y(t + 1) ≤ B ′ y(t) + q,ãäå ìàòðèöûäóãàjA, B ≥ 0, â êàæäîì ñòîëáöå ìàòðèöû A åñòü ïîëîæèòåëüíûé ýëåìåíò (ïîñêîëüêóó÷àñòâóåò â êàêîì-òî ìíîæåñòâåJi )è âåêòîðq ≥ 0.Åñëè â âåêòîðåqåñòü íåíóëåâûåýëåìåíòû, òî ýòî íåîäíîðîäíàÿ ìîäåëü Íåéìàíà, êîòîðóþ ìîæíî ñâåñòè ê îäíîðîäíîé, ââåäÿäîïîëíèòåëüíóþ ïåðåìåííóþçàäàòü íà÷àëüíîå óñëîâèåym+1 (t), çíà÷åíèå êîòîðîé âñåãäà ðàâíî 1. Äëÿ ýòîãî äîñòàòî÷íîym+1 (0) = 1è íåðàâåíñòâîym+1 (t + 1) ≤ ym+1 (t)(ïîñêîëüêó ìíîæåñòâî âîçìîæíûõ ðåøåíèé ðàñøèðÿåòñÿ ïðè óâåëè÷åíèèym+1 (t),ïðè ðå-øåíèè ëþáîé îïòèìèçàöèîííîé çàäà÷è íåðàâåíñòâî îáðàòèòñÿ â ðàâåíñòâî).
Òîãäà ïîëó÷èìîäíîðîäíóþ ìîäåëü Íåéìàíà, òî åñòü ñèñòåìó ëèíåéíûõ íåðàâåíñòâ (1.10) îòíîñèòåëüíî ðàñøèðåííûõ âåêòîðîây(t)èy(t + 1),ãäå ìàòðèöûA, B ≥ 0è â êàæäîì ñòîëáöå ìàòðèöûAåñòü ïîëîæèòåëüíûé ýëåìåíò.Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî äèíàìè÷åñêàÿ ñåòü ñ ìíîãîïðîäóêòîâûìè äèíàìè÷åñêèìèïîòîêàìè (ñëó÷àéF = Rq )è âîãíóòûìè êóñî÷íî-ëèíåéíûìè óñèëåíèÿìè òàêæå ñâîäèòñÿ êìîäåëè Íåéìàíà.Ïðèìåð 7. Äèñêðåòíàÿ ìîäåëü Íåéìàíàñòðîèòñÿ àíàëîãè÷íî íåïðåðûâíîé ìîäåëè Íåé-48ìàíà, íî ïîòîêè â äóãàõ, âåäóùèõ â ñóììàòîðû-ðàçìíîæèòåëè, òî åñòü èíòåíñèâíîñòè òåõíîëîãè÷åñêèõ ïðîöåññîâ äèñêðåòíû, òî åñòü ïðèíèìàþò òîëüêî öåëî÷èñëåííûå çíà÷åíèÿ.Äèñêðåòíàÿ ìîäåëü Íåéìàíà áîëåå àäåêâàòíî îïèñûâàåò ðàçâèòèå ðåàëüíûõ ýêîíîìè÷åñêèõñèñòåì, ÷åì íåïðåðûâíàÿ, ïîñêîëüêó ðåàëüíàÿ èíòåíñèâíîñòü òåõíîëîãè÷åñêèõ ïðîöåññîâ âñåãäà äèñêðåòíà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
