Диссертация (1149954), страница 30
Текст из файла (страница 30)
1977. 2. P.225229.[80℄Oldham J.D.Combinatorial Approximation Algorithms for Generalized Flow Problems.Department of Computer Siene, Stanford University, Stanford. 1998.[81℄S. Ovhinnikov. Max-MinRepresentation of Pieewise Linear Funtions // Contributions toAlgebra and Geometry. Vol. 43. 1. 2002. P. 297302.[82℄Radzik T.Faster algorithms for the generalized network ow problem // Mathematis ofOperations Researh.
1998. 23. P. 69100.[83℄Shen G., Gaines P.E.Hierarhially aelerated dynami programming for nite-statemahines // IEEE Trans. Automati Control. 2002. Vol. 47. 2. P. 271283.[84℄Truemper K. On max ows with gains and pure min-ost ows // SIAM J. Appl. Math.
1977.32. P. 450456.[85℄Venkatesh B., Sanjeev G.A Nonooperative Model of Network Formation // Eonometria,Vol. 68, 5. 2000. P. 11811229.[86℄Wayne K.D. Generalized Maximum Flow Algorithms: A Dissertation Presented to the Faultyof the Graduate Shool of Cornell University. 1999.[87℄Wayne K.D. A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow //Mathematis of Operations Researh, Vol. 27, 3. 2002.
P. 445459.[88℄Wolfram S.A New Kind of Siene. Champaign, IL, Wolfram Media, 2002.137Ïðèëîæåíèå AÏðèëîæåíèÿA.1Íåïðåðûâíûå êóñî÷íî-ëèíåéíûå óíêöèèA.1.1Îáùèå îïðåäåëåíèÿÁóäåì íàçûâàòüâûïóêëûì ìíîãîãðàííûì ìíîæåñòâîìñòðàíñòâ, îïðåäåëÿåìûõ ëèíåéíûìè íåðàâåíñòâàìè âèäàïåðåñå÷åíèå çàìêíóòûõ ïîëóïðî-a · x ≤ b.ìíîæåñòâî îïðåäåëÿåòñÿ ñèñòåìîé ëèíåéíûõ íåðàâåíñòâ âèäàÁóäåì íàçûâàòüîáîáùåííûì ìíîãîãðàííûì ìíîæåñòâîìÂûïóêëîå ìíîãîãðàííîåAx ≤ B .îáúåäèíåíèå êîíå÷íîãî ÷èñëàìíîãîãðàííûõ ìíîæåñòâ.Óòâåðæäåíèå A.1.1.1. Ìíîæåñòâî îáîáùåííûõ ìíîãîãðàííûõ ìíîæåñòâ â n-ìåðíîìïðîñòðàíñòâå çàìêíóòî îòíîñèòåëüíî îáúåäèíåíèé è ïåðåñå÷åíèé.2.
Äåêàðòîâî ïðîèçâåäåíèå îáîáùåííûõ ìíîãîãðàííûõ ìíîæåñòâ ÿâëÿåòñÿ îáîáøåííûììíîãîãðàííûì ìíîæåñòâîì.3. Åñëè L : Rm → R⋉ ëèíåéíûé îïåðàòîð, à A ⊆ Rm îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî, òî LA òîæå îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî.  ÷àñòíîñòè, ïðî-åêöèÿ îáîáùåííîãî ìíîãîãðàííîãî ìíîæåñòâà íà ïîäïðîñòðàíñòâî òàêæå ÿâëÿåòñÿîáîáùåííûì ìíîãîãðàííûì ìíîæåñòâîì.Äîêàçàòåëüñòâî.Î÷åâèäíî.Äàëåå ðàññìàòðèâàåì óíêöèè, îïðåäåëåííûå íà îáîáùåííûõ ìíîãîãðàííûõ ìíîæåñòâàõX ⊆ R⋉ .Îïðåäåëåíèå 62.
Êóñî÷íî-ëèíåéíàÿ óíêöèÿ (ÊË-óíêöèÿ)R, ÷òî ýòî òàêàÿ óíêöèÿf: X →åå îáëàñòü îïðåäåëåíèÿ ðàçáèâàåòñÿ íà êîíå÷íîå ÷èñëî îáëàñòåé (ìîæåò áûòü, ïåðåñå-êàþùèõñÿ)X = X1 ∪· · ·∪Xl , è â êàæäîé îáëàñòè fàèííà, òî åñòü, èìååò âèäf (x) = pi ·x+qi .138Áóäåì íàçûâàòüÒåîðåìà 19X1 , . . . , Xl çîíàìè ëèíåéíîñòè.(î çîíàõ ëèíåéíîñòè).Ïóñòü f (x), g(x) ÊË-óíêöèè, èìåþùèå çîíû ëèíåé-íîñòè ñîîòâåòñòâåííî A1 , . . . , Am è B1 , . .
. , Bn . Òîãäà:1. Ïðîèçâåäåíèå óíêöèè íà íåíóëåâóþ êîíñòàíòó cf (x) ÊË-óíêöèÿ, èìåþùàÿ òåæå çîíû ëèíåéíîñòè A1 , . . . , Am .2. Ñóììà è ðàçíîñòü óíêöèé f (x) + g(x) è f (x) − g(x) ÊË-óíêöèè, èìåþùèå çîíûëèíåéíîñòè îáúåäèíåíèÿ âñåâîçìîæíûõ ïåðåñå÷åíèé Ai ∩ Bj .3. Ìàêñèìóì max(f (x), g(x)) è ìèíèìóì min(f (x), g(x)) ÊË-óíêöèè, èìåþùèå çîíûëèíåéíîñòè, ñîñòàâëåííûå èç ìíîæåñòâ C1 ⊆ A1 , .
. . , Cm ⊆ Am , D1 ⊆ B1 , . . . , Dn ⊆Bn .4. Ñóïåðïîçèöèÿ f (g(x)) ÊË-óíêöèÿ, èìåþùàÿ çîíû ëèíåéíîñòè îáúåäèíåíèÿ âñåâîçìîæíûõ ïåðåñå÷åíèé g −1 (Ai ) ∩ Bj .Äîêàçàòåëüñòâî.g(x)Ïóñòü óíêöèÿâ çîíå ëèíåéíîñòè1. Ïðîèçâåäåíèå2. ÑóììàBjcf (x)èìååò âèäâAiai · x + bi ,â çîíå ëèíåéíîñòèbj · x + dj .èìååò âèäf (x)+g(x) â Ai ∩Bj3. Ìàêñèìóìf (x)à â ìíîæåñòâåèìååò âèäai · x + ci ,à óíêöèÿÒîãäà:cai · x + cci .èìååò âèämax(f (x), g(x))Ai(ai +bj )·x+(ci +dj ), à ðàçíîñòü (ai −bj )·x+(ci −dj ).â ìíîæåñòâåCi = {x ∈ Ai | ∀j ai · x + bi ≥ cj · x + dj }Dj = {x ∈ Bj | ∀i ai · x + bi ≤ cj · x + dj }ðàâåíðàâåícj · x + d j .Àíàëîãè÷íî ìèíèìóì.4.
Ñóïåðïîçèöèÿf (g(x))â ìíîæåñòâåg −1 (Ai ) ∩ Bjðàâíàai (bj · x + dj ) + ci .Ñëåäñòâèå 19.1. Ìíîæåñòâî ÊË-óíêöèé ëèíåéíîå ïðîñòðàíñòâî, çàìêíóòîå îòíîñè-òåëüíî îïåðàöèé âçÿòèÿ ìàêñèìóìà, ìèíèìóìà è ñóïåðïîçèöèè.Äàëåå ðàññìàòðèâàåì íåïðåðûâíûå êóñî÷íî-ëèíåéíûå óíêöèè (ÍÊË-óíêöèè). Ìîæíîäîêàçàòü, ÷òî íåïðåðûâíîñòü ÊË-óíêöèè ýêâèâàëåíòíà òîìó, ÷òî âñå åå çîíû ëèíåéíîñòè îáîáùåííûå ìíîãîãðàííûå ìíîæåñòâà [15℄.Òåîðåìà 20(ðàçíûå îïðåäåëåíèÿ ÍÊË-óíêöèè).Ñëåäóþùèå îïðåäåëåíèÿ ýêâèâàëåíòíû:1. f (x) ÍÊË-óíêöèÿ, òî åñòü ÊË-óíêöèÿ ñ îáîáùåííûìè ìíîãîãðàííûìè çîíàìèëèíåéíîñòè.1392.
Íàäãðàèê f (x) îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî.3. Ïîäãðàèê f (x) îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî.4. ðàèê f (x) îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî.5. f (x) ñîñòàâëÿåòñÿ èç àèííûõ óíêöèé ñ ïîìîùüþ îïåðàöèé max è min.Äîêàçàòåëüñòâî.• 1 ⇒ 2:íàäãðàèê îáúåäèíåíèå îáîáùåííûõ ìíîãîãðàííûõ ìíî-{(x, y) | x ∈ Ai , y ≥ ai · x + bi },æåñòâãäåAi îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî(çîíà ëèíåéíîñòè).• 1⇒3 àíàëîãè÷íî.• 2, 3 ⇒ 4: ãðàèê ïåðåñå÷åíèå äâóõ îáîáùåííûõ ìíîãîãðàííûõ ìíîæåñòâ: íàäãðàèêàè ïîäãðàèêà.• 4 ⇒ 1:çîíû ëèíåéíîñòè ýòî ïðîåêöèè ãðàíåé ãðàèêà, òî åñòü îáîáùåííûå ìíîãî-ãðàííûå ìíîæåñòâà. Êàæäàÿ ãðàíü ãðàèêà îïðåäåëÿåò àèííóþ óíêöèþ.• 5 ⇒ 2, 3.Íàäãðàèê àèííîé óíêöèè îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî (ïî-ëóïðîñòðàíñòâî). Íàäãðàèê ìàêñèìóìà ïåðåñå÷åíèå íàäãðàèêîâ, íàäãðàèê ìèíèìóìà îáúåäèíåíèå íàäãðàèêîâ.
Ïðèìåíÿÿ ê îáîáùåííûì ìíîãîãðàííûì ìíîæåñòâàì îáúåäèíåíèÿ è ïåðåñå÷åíèÿ, òàêæå ïîëó÷àåì îáîáùåííûå ìíîãîãðàííûå ìíîæåñòâà. Àíàëîãè÷íî äîêàçûâàåòñÿ óòâåðæäåíèå äëÿ ïîäãðàèêîâ.• 3 ⇒ 5:ëþáîå îáîáùåííîå ìíîãîãðàííîå ìíîæåñòâî ìîæíî ïðåäñòàâèòü êàê îáúåäèíå-íèå ïåðåñå÷åíèé ïîëóïðîñòðàíñòâ. Ïðè ýòîì, ïîñêîëüêó íàäãðàèê çàìêíóò, îí ñîîòâåòñòâóåò íåïðåðûâíîé óíêöèè, à çíà÷èò, åãî ãðàíèöà íå äîëæíà ñîäåðæàòü âåðòèêàëüíûõ ýëåìåíòîâ, ïàðàëëåëüíûõ îñèOy . òàêîì ñëó÷àå, â ïðåäñòàâëåíèè ìíîãî-ãðàííîãî ìíîæåñòâà ìîæíî îáîéòèñü áåç âåðòèêàëüíûõ ïîëóïðîñòðàíñòâ.
Êàæäîå íåâåðòèêàëüíîå ïîëóïðîñòðàíñòâî íàäãðàèê íåêîòîðîé àèííîé óíêöèè. Îòñþäàïîëó÷àåì ïðåäñòàâëåíèåf (x) = min(max(f11 (x), . . . , f1i1 (x)), . . . , max(fm1 (x), . . . , fmim (x))),ãäåfij (x) = pij · x + qij(A.1) àèííûå óíêöèè.Ñëåäñòâèå 20.1. Ìíîæåñòâî ÍÊË-óíêöèé çàìêíóòî îòíîñèòåëüíî îïåðàöèé âçÿòèÿìàêñèìóìà, ìèíèìóìà è ñóïåðïîçèöèè.140Áóäåì íàçûâàòü ïðåäñòàâëåíèå (A.1)min-ïðåäñòàâëåíèåì.Î÷åâèäíî, âûïóêëàÿ ÊË-óíêöèÿ íåïðåðûâíà, à çíà÷èò, ÿâëÿåòñÿ ÍÊË-óíêöèåé èïðåäñòàâèìà â âèäå ìàêñèìóìà èç àèííûõ óíêöèé. Àíàëîãè÷íî, âîãíóòàÿ ÊË-óíêöèÿíåïðåðûâíà, à çíà÷èò, ÿâëÿåòñÿ ÍÊË-óíêöèåé è ïðåäñòàâèìà â âèäå ìèíèìóìà èç àèííûõ óíêöèé.Ñ òî÷êè çðåíèÿ èäåìïîòåíòíîé àëãåáðû [66℄ ìíîæåñòâî âåùåñòâåííûõ ÷èñåëïîëóïîëå îòíîñèòåëüíî îïåðàöèéRîáðàçóåòmax è +. Òîãäà ëèíåéíàÿ óíêöèÿ àíàëîã îäíî÷ëåíà (ìî-íîìà) â ýòîì ïîëóïîëå, âûïóêëàÿ ÊË-óíêöèÿ àíàëîã ìíîãî÷ëåíà (ïîëèíîìà).
Îïåðàöèÿmin(x, y) = − max(−x, −y) = e ⊘ (e ⊘ x ⊕ e ⊘ y)Òåîðåìà 21ÿâëÿåòñÿ ðàöèîíàëüíîé óíêöèåé.(ñòàíäàðòíîå ïðåäñòàâëåíèå ÍÊË-óíêöèè).f ÍÊË-óíêöèÿ òîãäà è òîëü-êî òîãäà, êîãäà åå ìîæíî ïðåäñòàâèòü â âèäåf =g−h(A.2)ãäå g, h âûïóêëûå ÊË-óíêöèè.Äîêàçàòåëüñòâî.àñïèñûâàÿ ìàêñèìóì êàê ðàöèîíàëüíóþ óíêöèþ â èäåìïîòåíòíîì ïî-ëóïîëå, ïîëó÷èì ðàöèîíàëüíóþ óíêöèþ, òî åñòü ðàçíîñòü äâóõ âûïóêëûõ ÊË-óíêöèé.Î÷åâèäíî, êðîìå min-ïðåäñòàâëåíèÿ è ñòàíäàðòíîãî ïðåäñòàâëåíèÿ, âîçìîæíî åùå è maxïðåäñòàâëåíèå ÍÊË-óíêöèèf (x) = max(min(f11 (x), . . .
, f1i1 (x)), . . . , min(fm1 (x), . . . , fmim (x))),ãäåfij (x) = pij ·x+qijóíêöèè−f (x),(A.3) àèííûå óíêöèè. Åãî ëåãêî ïîëó÷èòü èç min-ïðåäñòàâëåíèÿ ÍÊË-ó÷èòûâàÿ, ÷òî− min(a1 , . . . , an ) = max(−a1 , . . . , −an )è− max(a1 , . . . , an ) =min(−a1 , . . . , −an ).A.1.2Âîãíóòûå êóñî÷íî-ëèíåéíûå óíêöèèÂîãíóòóþ êóñî÷íî-ëèíåéíóþ óíêöèþ ìîæíî ïðåäñòàâèòü â âèäåf (x) = min(pi · x + qi ).i∈I(A.4)Ïîäãðàèê âîãíóòîé ÊË-óíêöèè âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî.
Âñå çîíû ëèíåéíîñòè âîãíóòîé ÊË-óíêöèè ïðîåêöèè ãðàíåé ïîäãðàèêà, à çíà÷èò, îíè òîæå ÿâëÿþòñÿâûïóêëûìè ìíîãîãðàííûìè ìíîæåñòâàìè.141×òî ìîæíî ñêàçàòü î ïàðàìåòðàõpi , qi ?Óòâåðæäåíèå A.1.2. f (x) âîçðàñòàþùàÿ óíêöèÿ òîãäà è òîëüêî òîãäà, êîãäà ñóùå-ñòâóåò òàêîå ïðåäñòàâëåíèå÷òî âñå âåêòîðû pi ≥ 0. Ò.å. âñå îïîðíûå ëèíåéíûå(A.4),óíêöèè âîçðàñòàþùèå.Äîêàçàòåëüñòâî.âêëþ÷àþùóþÍåîáõîäèìîñòü. àññìîòðèì ïðîèçâîëüíóþ ãèïåðïëîñêîñòün-ìåðíóþíåéíîñòè âûïóêëîåáîãîj -ìãðàíü ïîäãðàèêà óíêöèè. Ïîñêîëüêó ñîîòâåòñòâóþùàÿ çîíà ëè-n-ìåðíîå ìíîãîãðàííîå ìíîæåñòâî, äëÿ äîñòàòî÷íî ìàëûõ ε1 , .
. . , εn > 0ñóùåñòâóåò òàêàÿ òî÷êàñòîèò íàx∗ ,ïðèíàäëåæàùàÿ ãðàíè, ÷òî âñåx∗j = x∗ + (0, . . . , 0, εj , 0, . . . , 0) (εjìåñòå) òîæå ïðèíàäëåæàò ýòîé ãðàíè. Ïî âîçðàñòàíèþj f (x∗ ) ≤ f (x∗j )y = pi · x + qi ,. À ýòî çíà÷èò, ÷òî âñåf (x),ïîëó÷àåì äëÿ ëþ-pij ≥ 0.Äîñòàòî÷íîñòü î÷åâèäíà: ìàêñèìóì èç âûïóêëûõ âîçðàñòàþùèõ óíêöèé âûïóêëàÿâîçðàñòàþùàÿ óíêöèÿ.Óòâåðæäåíèå A.1.3. Ïóñòü íåîòðèöàòåëüíàÿ âîãíóòàÿ óíêöèÿ f (x) îïðåäåëåíà íà âû-ïóêëîì ìíîæåñòâå A ⊆ Rn+ , âêëþ÷àþùåì â ñåáÿ íà÷àëî êîîðäèíàò 0.
Òîãäà â ïðåäñòàâëåíèè(A.4)âñå qi ≥ 0.Äîêàçàòåëüñòâî.àññìîòðèì ëþáóþ ãèïåðïëîñêîñòüãðàíü ïîäãðàèêà óíêöèè. Îíà ïåðåñåêàåò îñüóíêöèè. Ñëåäîâàòåëüíî,A.1.3Oyy = pi · x + qi ,â òî÷êåqiâêëþ÷àþùóþn-ìåðíóþè íàõîäèòñÿ íàä ïîäãðàèêîìqi ≥ f (0) ≥ 0.ÍÊË-óíêöèè îäíîé ïåðåìåííîéÎáû÷íî, ÍÊË-óíêöèÿ îäíîé ïåðåìåííîéf (x)çàäàåòñÿ â ÿâíîì âèäå ñ óêàçàíèåì çîí ëè-íåéíîñòè è àèííûõ óíêöèé â êàæäîé çîíå ëèíåéíîñòè.Àëãîðèòìfïðèâåäåíèÿçàäàíà íà îòðåçêå[a; b].fê ñòàíäàðòíîìó âèäó. Íå óìàëÿÿ îáùíîñòè, áóäåì ñ÷èòàòü, ÷òîÄåéñòâèòåëüíî, âñåãäà ìîæíî äîïîëíèòü îáúåäèíåíèå îòðåçêîâ äîîòðåçêà, äîáàâèâ äîïîëíèòåëüíûå çîíû ëèíåéíîñòè, íà êîòîðûõ áóäåò ñîõðàíÿòüñÿ íåïðåðûâíîñòü. Ïðè ýòîì, åñëè ñîîòíîøåíèå (A.2) áóäåò âûïîëíÿòüñÿ íà âñåì îòðåçêå, òî îíî òåìáîëåå áóäåò âûïîëíÿòüñÿ íà èñõîäíîé îáëàñòè îïðåäåëåíèÿ.Èòàê, îòðåçîê îïðåäåëåíèÿ· · · < an < an+1 = b,òîâp1 , . .
. , pn .[a; b]äåëèòñÿ íà çîíû ëèíåéíîñòèïðè÷åì â çîíå[ai ; ai+1 ] f (x) = pi x + qi .a = a1 < a2 < a3 <àññìîòðèì íàáîð ýëåìåí-Êàê èçâåñòíî, åãî âñåãäà ìîæíî ïðåäñòàâèòü êàê ðàçíîñòü äâóõ âîçðàñòàþùèõ142íàáîðîâ(p1 , . . . , pn ) = (p′1 , . . . , p′n ) − (p′′1 , . . . , p′′n ),íàïðèìåð, âçÿâp′1 = p1p′′1 = 0...(A.5)p′i+1 = max(p′i , p′′i + pi+1 ) = p′i + max(0, pi+1 − pi )p′′i+1 = max(p′i − pi+1 , p′′i ) = p′′i + max(pi − pi+1 , 0)...Òîãäà èñêîìîå ïðåäñòàâëåíèå ìîæíî ïîëó÷èòü, âçÿâg(x) = p′i x + qi′ , x ∈ Xih(x) = p′′i x + qi′′ , x ∈ Xiãäå ñâîáîäíûå ÷ëåíûqi′ , qi′′ îäíîçíà÷íî îïðåäåëÿþòñÿ èç óñëîâèÿ íåïðåðûâíîñòè óíêöèé g, h:q1′ = q1...′qi+1= (p′i − p′i+1 )ai+1 + qi′...q1′′ = 0...′′qi+1= (p′′i − p′′i+1 )ai+1 + qi′′...Î÷åâèäíî äëÿ óíêöèè èçn çîí ëèíåéíîñòèàëãîðèòì èìååò âðåìåííóþ ñëîæíîñòüO(n).Ñòàíäàðòíîå ïðåäñòàâëåíèå, âîîáùå ãîâîðÿ, íå åäèíñòâåííî: íàïðèìåð, ê îáåèì óíêöèÿìgèhìîæíî ïðèáàâèòü êîíñòàíòó èëè, ñêàæåì, ëèíåéíóþ óíêöèþ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
