廣義最大并行流問題的研究.pdf

1、Y ‘1 2 1 04 5 6編號：三冼I 鉑坤范女爹碩士學位論文題 目：廣義最大并行流問題的研究所在院專業(yè)名指導教研 究完成時系：數(shù)學與系統(tǒng)科學學院稱：管理科學與工程師：趙大宇教授生：董麗薇間：2 0 0 7 ．4 ．2 0沈陽師范大學研究生處制T h e S t u d y o fG e n e r a l i z e dM a x i m u mC o n c u r r e n tF l o wP r o b l e mA b

2、吼陽c t ：W i t ht h eq u i c kd e v e l o p m e n ta n d t h ew i d ea p p l i c a t i o n so fm o d e r nl o -g i s t i c s ，m o r e a n d m o r ep e o p l eb e g i n t oi n v e s t i g a t et h et h e o r ya b o u t i t

3、．B e c a u s en e t w o r k f l o wp r o b l e m i sa ni m p o r t a n t t h e o r y , i ta l s oh a s p r o s p e c t so f 麗d ea p -p l i c a t i o n si nm o d e r nl o g i s t i c s ．N e t w o r kf l o w i s a t r a d

4、i t i o n a ls u b j e c t i no p e r a t i o n ．G e n e r a l i z e dn e t w o r k f l o wp r o b l e mg e n e r a l i z e dt r a d i t i o n a ln e t w o r k f l o wp r o m l e mb ys p e c i f y i n ga g a i nf a c t o

5、 rf o re a c ha r c ．B o y A t u s eo ft h eg a i n f a c t o r ，g e n e r a l i z e dn e t w o r k f l o wh a s m a n y m o r e p r a c t i c a la p p l i c a t i o n s ．G e n e r a l i z e dm u l t i c o m m o d i t yf

6、 l o w p r o b l e m i s a n i m p o r t a n t f i e l d i n t h e s t u d y o f g e n e r a l i z e d n e t w o r k f l o w ，h o w t or u n t h ef u l l yp o l y n o m i a l a p p r o x i m a t i o ns c h e m e s f o r

7、g e n e r a l i z e dm u l t i c o m m o d i t yf l o wp r o b l e m f a s t e ra n d p r e c i s e ri s a n i m p o r t a n tc o n t e n tt od i s c u s s ．T h i st h e s i sm a k e s a s t u d y o f t h r e ef o r g e

8、n e r a l i z e dn e t w o r kf l o wp r o m l e m o fg e n e r a l i z e dn e t -w o r kf l o wp r o b l e m ．B a s e d O nt h es i m p l ei n t r o d u c t i o na b o u t t h en e t w o r kf l o w ，t h i sp a p e ri n

9、t r o -d u c e w h a t i sg e n e r a l i z e dn e t w o r kf l o w ．W e c l a s s i f i e dt h eg e n e r a l i z e d n e t w o r k f l o wa c c o r d i n g t ot h e d i f f e r e n tg a i nf a c t o r ．B e c a u s e e

10、x p e r td i dn o t r e f e rt oh o w t od e -t e r m i n e w h e t h 日t h e r ei sf l o w - g e n e r a t i n g c y c l ei ng e n e r a l i z e dn e t w o r k ，t h i st h e s i sp r e s e n t st h ea l g o r i t h mf o

11、rd e t e r m i n i n g w h e t h e rt h e r ei s af l o w - g e n e r a t i n gc y c l ei n d e p e n d e n t l y a c c o r d i n gt ot h ea l g o r i t h m f o rs e a r c h i n g m i n i m u m m e a n c y c l ea n dp r

12、o v e t h ea c c u r a c ya n d c o m p l e x i t yo fa l g o r i t h m ．T os o l v e g e n e r a l i z e d m a x i m u m c o n c u r r e n tf l o wp r o b l e m i nt h i sp a p e r ，w e w i l ln e e da s u b r o u t i n

13、 g t os o l v et h eg e n e r a l i z e ds h o r t e s tp a t h p r o b l e m ．8 0t h er u n n i n gt i m eo ft h ea l g o r i t h mf o rg e n e r a l i z e dm a x i m u m 0 0 n c Ⅵr e 】1 tf l o wd 印e n d s o nt h er u n

14、 n i n g t i m eo ft h ea l g o r i t h mf o rg e n e r a l i z e ds h o r t e s tp a t h ．W er e m a r k t h et h eg e n e r a l i z e d s h o r t e s tp a t h p r o b l e m ，a n d p r e s e n tt h en e w l i n e a rp r

15、 o g r a m m i n g a b o u ti t t om a k e t h ep r o m l e ms i m p l e ．A tt h e s a m et i m e ，w e 百、，ea s p e c i i ca l g o r i t h mf o rg e n e r a l i z e ds h o r t e s tp a t hf o rd i 舭n tg e n e r a l i z e

16、dn e t w o r k ．T h i s p a p e r m a i n l yi n t r o d u c eg e n e r a l i z e d m a x i m u m c o n c u r r e n t f l o wp r o b l e m ．W eg i v e i t s m a t h e m a t i c m o d e l i n l i n e a rp r o g r a m m i

17、n g a n d i t sd u a lp r o g r a m m i n gf o r m ．T h o u g ht r a n s f o r m i n g t h en e t w o r k w i t h o u t f l o w - g e n e r a t i n g c y c l ei n t oL e s s yn e t w o r k ，w ep r e s e n tp o l y n o m