Bài toán vận tải

  • Published on
    25-Jul-2015

  • View
    782

  • Download
    11

Embed Size (px)

Transcript

1Bi ton vn ti1. M hnh bi ton Mt cng ty c m kho hng, tng ng kho hng Aicha lng hng ai. C n im bn hng, tng ng vi im bn Bjbnc lng hng bj. Khi chuyn mt lng hng t kho Aisang im bnBj, chi ph vn chuyn l cij. C={cij: i=1.m, j=1.n} Theo phng n vn chuyn: xijl lng hng vnchuyn t kho Aisang Bj. X={xij:i=1.m,j=1.n} Mc tiu bi ton l chi ph vn chuyn thp nht = =minjij ij x c1 1min2 Pht biu bi ton f(x)= cijxij min (1) xij=aii=1.m (2) xij=bjj=1.n (3) xij>=0, i=1.m, j=1.n (4) xij(i=1.m, j=1.n ) Hng t Ai(i= 1.m)n Bj(j=1.n ) ai= bj (i=1.m, j=1.n) cn bng thu pht ai= bj (i=1.m, j=1.n) Khng cn bng thu phtBi ton vn ti3Bi ton vn ti S tn ti nghim cc bin ti u (cn bng thu pht)y l bi ton ti u quy hoch tuyn tnh nn c li gii sl im cc bin ti u Do cij 0, xij 0 i,j Vy hm lun b chn di1 1( ) 0m nij iji jf x cx= == >4Bi ton vn ti S tn ti nghim cc bin ti u Xy dng phng njmimii j ijinjnjj i ijijj i ijnjjmiib d a b xa d b a xj i xn j m i d b a xb a d= == = > = = == = = == == =1 11 11 1//) , ( 0) . 1 , . 1 ( /5Bi ton vn ti S tn ti nghim cc bin ti u Vy bi ton b chn di v c phng n nn bi ton c phng n ti u cc bin Do tnh c bit s th hin bi ton ny dng bng6Bi ton vn ti2. M hnh dng bngb1b2 bna1c11c12 c1na2c21c22 c2n .. .. ..amcm1cm2 cmnThuPht7Bi ton vn tiim cung Lng hngA1 10A2 5A3 5im cu Lng hngB1 13B2 7B1 B2A1 6 3A2 5 3A3 4 28Bi ton vn ti M hnh bi ton vn ti V d 113 710 6 35 5 35 4 29Bi ton vn ti M hnh bi ton vn ti V d 1: Cn bng thu pht13 7106?3?55?3?54?2?10Bi ton vn ti V d 1: Cn bng thu phtPhng n 1: hm mc tiu 9113 71061035533254 2511Bi ton vn ti V d 1: Cn bng thu phtPhng n 2: hm mc tiu 8613 710653555535432212Bi ton vn ti V d 1: Cn bng thu phtPhng n 3: hm mc tiu 8413 71063375553545213Bi ton vn ti M hnh bi ton vn ti V d 2: Khng cn bng thu pht13 7106?3?55?3?74?2?14Bi ton vn ti V d 2: Khng cn bng thu pht Phng n 1: 9113 71061035533274 2515Bi ton vn ti V d 2: Khng cn bng thu pht Phng n 1: 8913 71061035533074 2716Bi ton vn ti V d 2: Khng cn bng thu pht Phng n 2: 8413 71063375553745217Bi ton vn ti M hnh bi ton vn ti V d 3: Khng cn bng thu pht15 10106?3?55?3?54?2?18Bi ton vn ti V d 3: Khng cn bng thu pht Phng n 1: 9515 10106103555354 2519Bi ton vn ti2. M hnh dng bng chn: c gi tr x khc khng loi: L khng c hng, tc xij=0, ta c th trng Dy chuyn: l mt on thng hay mt dy lin tip ccon thng gp khc m hai u mt l hai ch nm trncng mt hng hoc mt ct vi mt chn khc thuc dychuyn ca bng vn ti Chu trnh: L dy chuyn khp kn Nh vy mt hng hoc mt ct m chu trnh i qua th ch iqua hai . Do s t nht ca mt chu trnh l 4.20Bi ton vn ti V d 2: Khng cn bng thu pht (Dy chuyn)13 71063375553745221Bi ton vn tiV d chu trnh30 25 35 4045 9251152 7550 55410635235 5 6 1 33522Bi ton vn ti2. M hnh dng bng Ma trn X = (xij)m.ntha mn h (2) - (4) c gi lmt phng n ca bi ton Phng n:X = (xij)m.ntha mn c gi l phngn cc bin ca bi ton vn ti nu tp hp cc tng ng vi cc thnh phn dng ca n khng tothnh chu trnh. Phng n X = (xij)m.n c gi l phng n cc binkhng suy bin nu s chn ca n ng bng m+n-1 Phng n X = (xij)m.nc gi l phng n cc binsuy bin nu s chn ca n nh hn m+n-1 23Bi ton vn ti M hnh dng bng Mt phng n tho mn yu cu (1) c gi lphng n ti u (nghim) ca bi ton, k hiu l Xopt24Cch chn phng n xut pht3. Phng n xut phta. Phng php xut pht gc ty bc Bc 1. Chn nm dng 1, ct 1 ca bng vn ti. Bc 2. Phn lng hng h = min{a1, b1} vo (1,1) Bc 3. nh du hng (ct), theo lng hng trm pht (trm thu) tng ng ht ( ). Bc 4. Quay tr v bc 1 thc hin cng vic nhng cn li. 25Bi ton vn tia. Phng php xut pht gc ty bc6000 4000 2000 15005000 3 2 7 66000 7 5 2 32500 2 5 4 550001000 4000 10001000 150026Bi ton vn tia. Phng php xut pht gc ty bc13 7106 355 354 21032527Bi ton vn tia. Phng php xut pht gc ty bc30 25 35 4045 9 1 2 750 5 4 6 235 5 6 1 328Bi ton vn tia. Phng php xut pht gc ty bc30 25 35 4045 9301152 750 5 4106352535 5 6 1 33529Bi ton vn tib. Phng php min- cc Bc 1. Chn c cc ph thp nht phn hnggi s l (i,j). Bc 2. Phn lng hng h = min {ai, bj} vo (i,j) Bc 3. nh du cc thuc hng i, hoc ct j nutrm pht Ai pht ht hng, hoc trm thu Bj nhn hng. Bc 4. Quay tr li bc 1 thc hin cng vic nhng cn li.30Bi ton vn tib. Phng php min- cc 6000 4000 2000 15005000 3 2 7 66000 7 5 2 32500 2 5 4 540002000250010001500 250031Bi ton vn tia. Phng php xut min cc13 7106 355 354 22531032Bi ton vn tia. Phng php xut pht min cc30 25 35 4045 9 1 2 750 5 4 6 235 5 6 1 333Bi ton vn tia. Phng php xut pht min cc30 25 35 4045 9201252 750 5104 6 24035 5 6 135334Bi ton vn ti4. Thut ton th v Tiu chun ti u Phng n cc bin khng suy bin X=(xij)m.n cgi l phng n ti u khi v ch khi tn ti cc s ui(i=1.m) cho cc hng v cc s vj(j=1.n ) cho cc ctca bng vn ti sao cho: ui+ vj= cij, xij>0 (1) ui+ vj< cij, xij=0 (2) ui(i=1.m), vj(j=1.n) gi l h thng th v hng v th vct35Bi ton vn ti Thut ton th v gii bi ton vn ti Bc 1: Tm phng n cc bin xut pht X0= (xij)mxn (S dng mt trong cc phng php trnh by trn tm phng n cc bin xut pht - trongtrng hp suy bin cho thm 0) 36Bi ton vn ti Phng n xut pht6000 4000 2000 15005000 3 2 7 66000 7 5 2 32500 2 5 4 550001000 4000 10001000 150037Bi ton vn ti Thut ton th v gii bi ton vn ti Bc 2: Kim tra tnh ti u ca phng n. Xy dng h thng th v.H (1) l h phng trnh c (n+m) n v (n + m-1) phng trnh c lp tuyn tnh nn h (1) c v snghim. Nu cho ui(i=1.m) hoc vj(j= 1.n ) mt gi tr a tu th mi gi tr khc u xc nh c mt cchduy nht theo (1).38Bi ton vn ti Tnh uiv vj6000 4000 2000 1500 ui5000 350002 7 66000 71000540002100032500 2 5 4100051500vj555000341-26-139Bi ton vn ti Thut ton th v gii bi ton vn ti Bc 2: Kim tra tnh ti u ca phng n. Tnh cc s kim tra. Da vo (2) ta t ij= ui+ vj-cij(i=1.m, j=1.n ) gi l c lng kim tra v tnh ij ng vicc loi. C hai kh nng xy ra: - Nu mi ij 0 (i = 1.m, j = 1.n ) th phng nang xt l ti u (thut ton kt thc).- Nu tn ti ij>0(i = 1.m, j = 1.n) th phngn ang xt cha ti u, chuyn sang bc 340Bi ton vn ti Tnh ij6000 4000 2000 1500 ui5000 350002 7 6 06000 7100054000210003 42500 2 5 41000515006vj3 1 -2 -1 55500-1 -9-707 241Bi ton vn ti Thut ton th v gii bi ton vn ti Bc 3: Xy dng phng n mi + Chn iu chnh: (r,s) gi l iu chnh nu:rs= max {ij> 0(i = 1.m, j = 1.n )}. + Tm chu trnh iu chnh: L chu trnh vi xut pht l iu chnh, cc cn li l chn. Gi V l tp hp cc thuc chu trnh iu chnh. + nh du cc ca chu trnh, bt u t iu chnh nh du (+) ri xen k nhau nh du (-), (+)... cho n ht chu trnh. K hiu V+l tp hp cc c du (+), V-l tp hp cc c du (-). Khi : V= V+ V-.42Bi ton vn ti Tm chu trnh6000 4000 2000 1500 ui5000 350002-17-96-706000 7100054000210003042500 275241000515006vj3 1 -2 -1 555007+-+ -43Bi ton vn ti Thut ton th v gii bi ton vn ti Bc 3: Xy dng phng n mi + Xc nh lng hng iu chnh: i lng iu chnh:q = min{xij: (i,j) e V-}, q > 0.iu chnh sang phng n mi: X1 = (x1ij)mxn vi: xij= xij, xije V xij= xij+ q, xije V+ xij= xij- q, xije V-44Bi ton vn ti Tnh phng n mi6000 4000 2000 1500 ui5000 350002-17-96-706000 7100054000210003042500 275241000515006vj3 1 -2 -1 555007+-+ -Q=1000100002000 04850045Bi ton vn ti Thc hin cho vng lp th 26000 4000 2000 1500 ui5000 350002 7 66000 7 540002200032500 210005 4 51500vj4850003-16-305 86 -2 0-72 046Bi ton vn ti Thc hin cho vng lp th 26000 4000 2000 1500 ui5000 350002 7 6 06000 7 540002200030-32500 210005 4 51500-1vj3 8 5 6 485006 -2 0-72 0+-+ -+-Q=15001500 35002500 01500 25003950047Bi ton vn ti Thc hin cho vng lp th 36000 4000 2000 1500 ui5000 33500215007-86-606000 7-152500220003150032500 225005-44-65-6-1vj3 2 -1 0 3950048Bi ton vn ti Thut ton kt thc Khng tm c th v tt hn Hm mc tiu t: 39500 Ma trn vn ti: 3500 1500 0 00 2500 2000 15002500 0 0 049Bi ton vn tiV d 1:91 4 65 -22 452 3 -13 5510 03 6107 1350Bi ton vn tiV d 1:9152 452 33 55103 6107 1306-14-210+ -+ -22 80 551Bi ton vn tiV d 1:8952 4553 552 83 6107 1306-13-1-11+-+-55 07 352Bi ton vn tiV d 1:8452 4553 557 33 6107 1306-1-23-1-1Phng n hin ti l phng n ti u53Bi ton vn tiV d 1:Phng n hin ti l phng n ti u3 75 05 054Bi ton vn tiV d 2:30 25 35 4045 9301152 750 5 4106352535 5 6 1 33564009 133 -1478 -1 61 -8+ -+-+-1055Bi ton vn tiV d 2:30 25 35 4045 9201252 750 5 4 63521535 5106 1 32554009 1-511 7-40 9-8 -1-9 6+-+ -+ -2056Bi ton vn tiV d 2:30 25 35 4045 9 125220750 5 4 61523535 5306 1 3549000 142 -25-9-1 10 6-9+ -+ -557Bi ton vn tiV d 2:30 25 35 4045 9 125220750 5 4 61024035 5306 1533350124-2-16-351-6-9-6+- +-1058Bi ton vn tiV d 2:30 25 35 4045 9 125220750 5104 6 24035 5206 1153310012-16-13-4-1-5 -4-6-359Bi ton vn ti5. Bi ton khng cn bng thu pht Tng hng d tr ln hn tng hng cn (cung ln hn cu)im c mt s im aikhng pht ht hng, cn bjs thu hng Tng hng cn ln hn tng hng d tr (cu ln hn cung)im pht ais pht ht hng, mt s im thu bjkhng thu hng60Bi ton vn tia. Cung ln hn cu A: ma trn pht B: ma trn thu C: ma trn chi ph Xij(i=1.m, j=1.n ) Hng t Ai(i= 1.m)n Bj(j=1.n ) f(x)= cijxij min (1) xijaii=1.m (2) xij=bjj=1.n (3) xij>=0, i=1.m, j=1.n (4) ai> bj, i=1.m, j=1.n61Bi ton vn ti Gii php gii bi ton Tng hng c ln hn tng hng cnTo mt im thu gi, gi vn chuyn n im ny l 0S lng thu = ai- bjTrong bi ton tm phng n u l min th xt trnghp ny cui cngBi ton quay v bi ton cn bng thu pht62Bi ton vn ti M hnh bi ton vn ti V d 2: Cung ln hn cu13 7106?3?55?3?74?2?63Bi ton vn ti M hnh bi ton vn ti V d 2: Cung ln hn cu912 50 2 472 30 3 55100 3 6102 7 1306-14-221 210+-+-+ -2285 07 064Bi ton vn ti M hnh bi ton vn ti V d 2: Cung ln hn cu8770 2 4750 3 552 0 80 3 6102 7 13060-13-11-1 -1-1+ -+ -77 07 165Bi ton vn ti M hnh bi ton vn ti V d 2: Cung ln hn cu13 7 2106 3 01 7 255 3 0574 2 07800630-1-2-1 -1-2 -1Phng n ti u66Bi ton vn tiV d 3:30 25 35 4045 9 1 2 750 5 4 6 260 5 6 1 367Bi ton vn tiV d 3:30 25 35 40 2545 9301152 7 050 5 41063525060 5 6 1 33502565009 133 -14-41 -8 -47 -18-1 6+ -+ -+ -1068Bi ton vn tiV d 2:30 25 35 40 2545 920125297004050 5-14-86352150-1-560 5106-917325025-49 1 11 7 4 570+ -+ -+ -2069Bi ton vn tiV d 3:30 25 35 40 2545 9-91252207004050 5-1416152350-1460 53060163502550 1 2 -2 -5 390+-+ -570Bi ton vn tiV d 3:30 25 35 40 2545 9-51252207-901050 554161024005460 5306-6153-6025-16 1 2 -2 1 360-++ -1071Bi ton vn tiV d 3:30 25 35 40 2545 9-31252207-401050 504-46-5240010-160 5306-61153-1015-16 1 2 3 1 300+ -- +1572Bi ton vn tiV d 2:30 25 35 40 254