怎樣掌握運輸問題的數(shù)學模型(已修改)
2025-01-07 00:10 本頁面
【正文】 OPERATIONS RESEARCH 運籌學 Ⅱ ——怎樣把事情做得最好 OR2 1 第四章 運輸問題 本章要求： 掌握運輸問題的數(shù)學模型 掌握運輸問題的求解方法 化產(chǎn)銷不平衡問題為平衡問題 學會用計算機求解 OR2 2 ?運輸問題一般表述為： 某企業(yè)有 m個產(chǎn)地（生產(chǎn)廠） Ai， 其產(chǎn)量分別為 ai, i=1,2,…m, n 個銷地 （ 銷售商）Bj， 其銷售量分別為 bj, j=1,2,…n, 從 Ai到 Bj的每單位物資的運費為 費最小的調(diào)運方案 。 OR2 3 運輸表 . 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a2 … … … … … … Am Cm1 Cm2 … Cmn am 銷量 b1 b2 … bn OR2 4 運輸問題的數(shù)學模型 設從 Ai 到 Bj的運輸量為 xij,（ 假定產(chǎn)銷平衡） 則總運費： minZ= ∑∑ Cij xij 產(chǎn)量約束： ∑xij = ai i=1,2,…m, 銷量約束： ∑xij = bj j=1,2,…n, 非負性約束： xij ≥0 n m j=1 i=1 n j=1 m i=1 OR2 5 ?計算步驟： 給出初始方案 檢驗是否最優(yōu) 調(diào)整調(diào)運方案 , Go to 2 OR2 6 例題 1 ?某建材公司有三個水泥廠 A A A3，四個經(jīng)銷商 B B B B4， 其產(chǎn)量、銷量、運費如下表： 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 8 4 2 7 7 4 3 5 9 2 1 6 1 9 4 銷量 3 2 4 5 14 OR2 7 ?用最小元素法（也可用西北角法或 vogel法）給出初始基可行解： 在運費表中找出最小元素，盡最大可能用完一個廠的產(chǎn)量，或滿足一個商家的銷量。得到滿足者用線劃去。 逐次尋找最小元素，直至分配完畢 注意：如填寫一個數(shù)字同時滿足了一廠一商，則需在同行或同列中填寫一個數(shù)字 0，以保證恰好有 m+n1個數(shù)字。 OR2 8 例 1 之初始方案（ P119） 最小元素法：圈定 C24 B1 B2 B3 B4 產(chǎn)量 A1 8 7 3 2 1 A2 4 7 5 ?/5 9 4 A3 2 4 9 6 4 銷量 3 2 4 5 OR2 9 例 1初始方案（續(xù) 1） 圈定 C31 B1 B2 B3 B4 產(chǎn)量 A1 8 7 3 2 1 A2 4 7 5 ?/5 9 4 A3 ?/3 4 9 6 4 1 銷量 3 2 4 5 OR2 10 例 1初始方案（續(xù) 2） ?圈定 C13 B1 B2 B3 B4 產(chǎn)量 A1 8 7 ?/1 2 1 A2 4 7 5 ?/5 9 4 A3 ?/3 4 9 6 4 1 銷量 3 2 4 3 5 OR2 11 例 1 初始方案（續(xù) 3） ?圈定 C32 B1 B2 B3 B4 產(chǎn)量 A1 8 7 ?/1 2 1 A2 4 7 5 ?/5 9 4 A3 ?/3 ?/ 1 9 6 4 1 銷量 3 2 1 4 3 5 OR2 12 例 1 初始方案（續(xù) 4） ?圈定 C23 B1 B2 B3 B4 產(chǎn)量 A1 8 7 ?/1 2 1 A2 4 7 ?/3 ?/5 9 4 1 A3 ?/3 ?/1 9 6 4 1 銷量 3 2 1 4 3 5 OR2 13 例 1 初始方案（續(xù) 5） ?圈定 C22 B1 B2 B3 B4 產(chǎn)量 A1 8 7 ?/1 2 1 A2 4 ?/1 ?/3 ?/5 9 4 1 A3 ?/3 ?/1 9 6 4 1 銷量 3 2 1 43 5 OR2 14 例 1初始方案 ——初始基可行解 ?中心數(shù)字為分配的運輸量 B1 B2 B3 B4 產(chǎn)量 A1 1 1 A2 1 3 5 9 A3 3 1 4 銷量 3 2 4 5 此方案費用為 40 OR2 15 最優(yōu)性檢驗 ?最優(yōu)性檢驗與單純形法原理一致，計算方法有位勢法和閉回路法，這里講位勢法。 ?位勢法是任意給出一組數(shù) ui和 vj， 稱之為位勢，有數(shù)字的格滿足： ui+vj=cij 沒數(shù)字的格計算： σij=cij(ui+vj) OR2 16 位勢計算： ui+vj ?先填寫初始方案相應的運費，任意給出一個 ui或 vj值，推出其它位勢值。 ?計算 ui+vj， 填于空格處 B1 B2 B3 B4 ui A1 （ 3） （ 5） 3 （ 1） 2 A2 （ 5） 7 5 1 4 A3 2 4 （ 2） （ 2） 1 vj 1 3 1 3 OR2 17 檢驗數(shù)計算： σij=cij(ui+vj) B1 B2 B3 B4 ui A1 8（ 3） =5 7（ 5）=2 33=0 2（ 1） =3 2 A2 4（ 5） =1 77=0 55=0 11=0 4 A3 22=0 44=0 9（ 2） =7 6（ 2） =8 1 vj 1 3 1 3 σ 21=1 OR2 18 方案調(diào)整： ?σij 0 處，增加運輸量，可節(jié)約運費。故做如下調(diào)整： B1 B2 B3 B4 產(chǎn)量 A1 1 1 A2 +1 11 3 5 9 A3 31 1+1 4 銷量 3 2 4 5 OR2 19 新方案： B1 B2 B3 B4 產(chǎn)量 A1 1 1 A2 1 3 5 9 A3 2 2 4 銷量 3 2 4 5 此方案費用為： 1?3+1 ?4+3 ?5+5?1+2 ?2+4 ? 2=39 OR2
環(huán)評公示相關推薦
鄂ICP備17016276號-1