運籌學-最大流-案例

1、案例BMZ公司的最大流問背景BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商。它因為提供優(yōu)質(zhì)的服 務而獲得很好的聲譽，保持這個聲譽一個很重要的秘訣就是它有著充裕的 汽車配件供應，從而能夠隨時供貨給公司眾多的經(jīng)銷商合授權(quán)維修店。這些供應件主要存放在公司的配送中心里，這樣一有需求就可以立即 送貨?？枺˙MZ公司的供應鏈的經(jīng)理）優(yōu)先考慮的是改進這些配送中 心的不足之處。該公司在美國有幾個配送中心。但是，離洛杉機中心最近的一個配送 中心卻坐落離洛杉機1000多英里的西雅圖。保證洛杉機中心良好的供 應是尤為重要的。因此，現(xiàn)在那里的供應不斷減少的現(xiàn)狀成為了公司高層 管理真正關(guān)心的問題。大部分的汽車配件以及新車是

2、在該公司坐落于徳國的斯圖加特的總 廠和新車一起生產(chǎn)的。也就是這家工廠向洛杉機中心供應汽車配件。每月 有超過300000立方英尺的配件需要運到?，F(xiàn)在，下個月需要多得多的 數(shù)量以補充正在減少的庫存。問題卡爾需要盡快制定一個方案，使得下個月從總廠運送到洛杉機配送中 心的供應件盡可能多。他認識到了這是個最大流的問題一一 一個使得 從總廠運送到洛杉機配送中心的配件流最大的問題。因為總廠生產(chǎn)的配件 量遠遠要大于能夠運送到配送中心的量，所以，可以運送多少配件的限制 條件就是公司配送網(wǎng)絡的容量。這個配送網(wǎng)絡如下圖1。在圖中，標有ST和LA的節(jié)點分別代表 斯圖加特的工廠和洛杉機的配送中心。由于工廠所在地有一個鐵

3、路運轉(zhuǎn) 點，所以首先通過鐵路把配件運輸?shù)綒W洲的三個港口：鹿特丹（R0 ） 波爾多（B0 ）和里斯本（LI）；然后通過船運到美國的港口紐約（NY ） 或新奧爾良（NO ）：最后用卡車送到洛杉機的配送中心。圖1網(wǎng)絡模型八4經(jīng)營這些鐵路、船舶和卡車的組織是獨立所有的公司，這些公司為很 多的公司運輸貨物。由于對這些老主顧原有的承諾，這些公司不可以在短 時間內(nèi)為任何一個客戶大量增加運輸空間配額。因此，BMZ公司只能夠保 證獲得下個月每條運輸航線有限的運輸空間。圖1已經(jīng)給岀可以獲得的空 間數(shù)量，以100立方米為1個單位（由于每100立方米比3500立方英尺 大一點，所以，需要運送的這批貨物體積是很大的）。

4、模型描述和求解這是一個最大流問題，每一條弧下方括號里的數(shù)字代表了該弧的 容量。通過標號法求得最大流，在各線路上的運輸方案如表1所 示。最大流量為150單位。表1最大流分配方案出發(fā)點目的地運輸址斯圖加特鹿持丹50斯圖加特波爾圖70斯圖加特里斯木30鹿特丹紐約50波爾圖紐約30波爾圖新奧爾良40里斯木新奧爾良30紐約洛杉磯80新奧爾良洛杉磯70進一步改善的方案在柏林，即斯圖加特的工廠的北面，公司有一家較小一點的工廠也生 產(chǎn)汽車配件。雖然通常這家工廠用來協(xié)助供應給北歐、加拿大和美國北部 地區(qū)的配送中心（包括在西雅圖的一個），但是它也同樣可以運輸配件到 洛杉磯的配送中心去。而且，當洛杉磯配送中心出現(xiàn)庫

5、存短缺時，西雅圖 的配送中心有能力供應配件給洛杉磯配送中心的客戶。受到這一點的啟發(fā)，卡爾為解決當前洛杉磯存貨短缺的問題開發(fā)了一 個更好的方案。他決泄與其僅僅使得從斯圖加特的工廠到洛杉磯配送中心 的運輸量最大，不如使得兩個工廠到洛杉磯和西雅圖這兩個配送中心的運 輸量最大。圖2顯示的網(wǎng)絡模型代表擴展后的配送網(wǎng)絡。這個經(jīng)過擴展的網(wǎng)絡包 括了兩個工廠和兩個配送中心。除了圖1的節(jié)點以外，節(jié)點BE代表了 位于柏林的較小的工廠，節(jié)點HA和節(jié)點BN分別代表為這家工廠提供 服務的漢堡和波士頓別外兩大港口。SE代表了西雅圖。和以前一樣，弧 代表了運輸路線，每一條弧下方括號里的數(shù)字代表了該弧的容量，即下個月可以通過這條運輸路線的最大運輸單位數(shù)。將經(jīng)過擴展的BMZ問題看作是最大流問題的網(wǎng)絡模型。重新求解， 得到改善的最大流分配方案如表2所示。最大流量為220單位。苴中，運 送到洛杉磯的單位數(shù)由150增長到160 ,期外的新加60單位到西雅 圖作為洛杉磯庫存短缺的備份，這個方案不但解決了洛杉磯的危機，而且表2改善的最大流分配方秦出發(fā)點目的地運輸雖斯圖加特鹿特丹60斯圖加特波爾圖10斯圖加特里斯木50鹿特丹紐約70波爾圖紐約30波爾圖新奧爾良30里斯木新奧爾良