[管理學(xué)]運(yùn)輸經(jīng)濟(jì)學(xué)第7章運(yùn)輸合理化(編輯修改稿)
2024-11-12 22:03 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 取最小五個(gè)， 下標(biāo)每個(gè)出現(xiàn) 兩次即可，否則 換稍長(zhǎng)的邊 ……。 v1 v2 v5 v4 v3 11 1 17 2 23 1 3 10 8 6 （一）旅行商問(wèn)題 匈牙利算法 ?減價(jià) :每行減去該行的最小值， ∞ 10 0 16 110 ∞ 22 0 20 22 ∞ 9 716 0 9 ∞ 50 1 6 4 ∞1∞ 10 0 16 010 ∞ 22 0 10 22 ∞ 9 616 0 9 ∞ 40 1 6 4 ∞∞ 11 1 17 2 111 ∞ 23 1 3 11 23 ∞ 10 8 117 1 10 ∞ 6 12 3 8 6 ∞ 2?再每列減去該列的最小值。 ?再?gòu)南卤碇姓页鲎钚〉奈鍌€(gè)元，檢查它們的下標(biāo)是否滿足要求？不！就調(diào)整。 ∞ 11 1 17 2 111 ∞ 23 1 3 11 23 ∞ 10 8 117 1 10 ∞ 6 12 3 8 6 ∞ 2∞ 10 0 16 110 ∞ 22 0 20 22 ∞ 9 716 0 9 ∞ 50 1 6 4 ∞1?調(diào)整兩次即得。 ∞ 10 0 16 010 ∞ 22 0 10 22 ∞ 9 616 0 9 ∞ 40 1 6 4 ∞∞ 10 0 16 010 ∞ 22 0 10 22 ∞ 9 616 0 9 ∞ 40 1 6 4 ∞?最優(yōu)路線： v1 v2 v5 v4 v3 11 1 17 2 23 1 3 10 8 6 x13 x34 x24 x25 x15 （二）旅行商問(wèn)題 最鄰近法（有向圖） ? 由于規(guī)定推銷員是從城市 1開(kāi)始的，設(shè)推銷員已走到城市 i，記 表示由城市 1到城市 i的中間城市的集合。 S表示到達(dá)城市 i之前 中途所經(jīng)過(guò)的城市集合 ， 則有： 因此，可選擇（ i， S）作為描述過(guò)程的 狀態(tài)變量 ，決策為由一個(gè)城市走到另一個(gè)城市，并定義 最優(yōu)值函數(shù) 為從城市 1開(kāi)始經(jīng)由 k個(gè)中間城市的 S集到城市 i的 最短路線的距離 。 ?? niiN i , . . . ,1,1, . . . ,3,2 ???iNS ?),( Sif k則動(dòng)態(tài)規(guī)劃的遞推關(guān)系為： 邊界條件為： 為最優(yōu)決策函數(shù) ，它表示從城市 1開(kāi)始經(jīng) k個(gè)中間城市的 S集到城市 i的最短路線上緊挨著城市 i前面的那個(gè)城市。 ),( SiPk]}{\,([m i n),( 1 jiksjkdjSjfSif ?? ??)., . . . ,3, . . . ,2,1( iNSnink ????idif 10 ),( ??? 舉例：求解 4個(gè)城市推銷員問(wèn)題 。距離矩陣如表所示。設(shè)推銷員從城市 1出發(fā)，經(jīng)過(guò)每一個(gè)城市且僅一次，最后回到城市 1。問(wèn)怎樣走行程最短？ j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 解： 由邊界條件可知： 10),2( 120 ?? df ?20),3( 130 ?? df ?30),4( 140 ?? df ?j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 當(dāng) K=1時(shí)，即從城市 1開(kāi)始，中間經(jīng)過(guò)一個(gè)城市到達(dá)城市 i的最短距離為： j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 623230),4(})4{,2( 421 ????? dff ?29920),3(})3{,2( 321 ????? dff ?281810),2(})2{,3( 231 ????? dff ?34430),4(})4{,3( 431 ????? dff ?403010),2(})2{,4( 241 ????? dff ?25520),3(})3{,4( 341 ????? dff ?當(dāng) K=2時(shí)，即從城市 1開(kāi)始，中間經(jīng)過(guò) 2個(gè)城市到達(dá)城市 i的最短距離為： j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 )43(3})4,3{,2(2 ?p決策函數(shù)： )44(4})4,2{,3(2 ?p44]440,962m i n []})2{,4(,})4{,2(m i n [}4,2{,3( 4312312 ??????? dfdff決策函數(shù)： 33]582,3029m i n []})2{,3(,})3{,2(m i n [})3,2{,4( 3412412 ??????? dfdff決策函數(shù)： )33(3})3,2{,4(2 ?p43]3225,934m i n []})3{,4(,})4{,3(m i n [})4,3{,2( 4213212 ??????? dfdff當(dāng) K=3時(shí)，即從城市 1開(kāi)始，中間經(jīng)過(guò) 3個(gè)城市到達(dá)城市 1的最短距離為： j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 55]3433,2344,1243m i n []})3,2{,4(,})4,2{,3(,})4,3{,2(m i n [}4,3,2{,1( 413122123????????? dfdfdff決策函數(shù)： )55(2})4,3,2{,1(3 ?p故，推銷員的最短旅行路線： 1—4—3—2—1， 最短總距離為 55。 j:1 2 3 4 5 i： 1 0 10 20 30 40 2 12 0 18 30 25 3 23 9 0 5 10 4 34 32 4 0 8 5 45 27 11 10 0 作業(yè)： 第三節(jié) 直達(dá)供貨系統(tǒng)的運(yùn)輸 一、運(yùn)輸規(guī)劃原理 運(yùn)輸規(guī)劃研究的是單一品種物資的典型運(yùn)輸問(wèn)題 。 運(yùn)輸問(wèn)題是一種應(yīng)用廣泛的網(wǎng)絡(luò)最優(yōu)化模型，其主要目的是為物資調(diào) 運(yùn)、車輛調(diào)度選擇最經(jīng)濟(jì)的運(yùn)輸路線。有些問(wèn)題，比如有 m臺(tái)機(jī)床加工 n種零件的問(wèn)題，工廠的合理布局問(wèn)題等，雖要求與提法不同，但經(jīng)過(guò)適當(dāng)變化也可以使用本模型求得最優(yōu)解。 運(yùn)輸問(wèn)題的一般提法是： 某種物資有 m 個(gè)產(chǎn)地 i A ，產(chǎn)量分別為 ) ,..., 2 , 1 ( m i a i ? ，有 n 個(gè)銷 地 j B ，銷量（需求最）分別為 ) ,..., 2 , 1 ( n j b j ? , 已知 i A 到 j B 的單位運(yùn) 價(jià)為 ) ,..., 2 , 1 。 ,..., 2 , 1 ( n n m i c ij ? ? 是平衡的， ，問(wèn)應(yīng)如何安排運(yùn)輸可使總運(yùn)費(fèi)最?。? 假定 ij x 表示由 i A 到 j B 的運(yùn)輸量，則平衡條件下的 如下的線性規(guī)劃模型： 運(yùn)輸問(wèn)題的一般提法和模型 ，假設(shè)產(chǎn)銷 運(yùn)輸問(wèn)題可寫出 ?????n1jjm1ii ba ) ,..., 2 , 1 ( 1 m i a x i n j ij ? ? ? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1