管理運(yùn)籌學(xué)7運(yùn)輸問題.ppt

1、1,第七章 運(yùn) 輸 問 題,1運(yùn) 輸 模 型 2運(yùn)輸問題的計算機(jī)求解 3運(yùn)輸問題的應(yīng)用 4*運(yùn)輸問題的表上作業(yè)法,2,例1、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？,解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：,Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21

2、= 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）,1運(yùn) 輸 模 型,3,1運(yùn) 輸 模 型,一般運(yùn)輸模型：產(chǎn)銷平衡 A1、 A2、 Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個銷地；si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷地Bj 的銷量； cij 表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價。 設(shè) xij 為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m

3、 xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 變化： 1）有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當(dāng)某些運(yùn)輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)； 3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。,4,2運(yùn)輸問題的計算機(jī)求解,例2、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?解：增加一個 虛設(shè)的銷地 運(yùn)輸費(fèi)用為0,5,2運(yùn)輸問題的計算機(jī)求解,

4、例3、某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?解：增加一個 虛設(shè)的產(chǎn)地 運(yùn)輸費(fèi)用為0,6,3運(yùn)輸問題的應(yīng)用,一、產(chǎn)銷不平衡的運(yùn)輸問題 例4、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價為： 由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸，二區(qū)必須滿 足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。 解： 根據(jù)題

5、意，作出產(chǎn)銷平衡與運(yùn)價表： 這里 M 代表一個很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的 x31、 x33、 x34取值為0。,7,3運(yùn)輸問題的應(yīng)用,一、產(chǎn)銷不平衡的運(yùn)輸問題 例5、設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表： 試求總費(fèi)用為最低的化肥調(diào)撥方案。 解： 根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價表： 最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 M ，而最高要求與最低 要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 0 。對應(yīng) 4”的銷量 50 是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定 D的產(chǎn)量為 50。,8,3運(yùn)輸問題的應(yīng)用,二、生產(chǎn)與儲存

6、問題 例6、某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。,9,3運(yùn)輸問題的應(yīng)用,解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足： 交貨：x11 = 10 生產(chǎn)：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x

7、34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量；把第 j 季度交 貨的柴油機(jī)數(shù)目看作第 j 個銷售點的銷量；成本加儲存、維護(hù)等費(fèi)用看作 運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問題： 目標(biāo)函數(shù)：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,10,3運(yùn)輸問題的應(yīng)用,二、生產(chǎn)與儲存問題 例7、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生

8、產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表： 已知上年末庫存103臺繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨， 則需要運(yùn)到分廠庫房，每臺增加運(yùn)輸成本0.1萬元,每臺機(jī)器每月的平均倉 儲費(fèi)、維護(hù)費(fèi)為0.2萬元。在7-8月份銷售淡季，全廠停產(chǎn)1個月，因此在6 月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機(jī)器每臺增加成本1萬 元。問應(yīng)如何安排1-6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉 儲、維護(hù)）最少？,11,3運(yùn)輸問題的應(yīng)用,解： 這個生產(chǎn)存儲問題可化為運(yùn)輸問題來做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地 1）1-6月份合計生產(chǎn)能力（包括上年末儲存量）為743臺，銷量為707臺。設(shè)一

9、假想銷地銷量為36； 2）上年末庫存103臺，只有倉儲費(fèi)和運(yùn)輸費(fèi)，把它列為第0行； 3）6月份的需求除70臺銷量外，還要80臺庫存，其需求應(yīng)為70+80=150臺； 4）1-6表示1-6月份正常生產(chǎn)情況， 1-6表示1-6月份加班生產(chǎn)情況。 產(chǎn)銷平衡與運(yùn)價表：,12,3運(yùn)輸問題的應(yīng)用,用“管理運(yùn)籌學(xué)”軟件解得的結(jié)果是：1-6月最低生產(chǎn)費(fèi)用為8307.5萬元，每月的銷售安排如下表所示,13,3運(yùn)輸問題的應(yīng)用,三、轉(zhuǎn)運(yùn)問題： 在原運(yùn)輸問題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地 轉(zhuǎn)運(yùn)站、轉(zhuǎn) 運(yùn)站 銷地、產(chǎn)地 產(chǎn)地、產(chǎn)地 銷地、銷地 轉(zhuǎn)運(yùn)站、銷地 產(chǎn) 地等。 例8、騰飛電子儀器公司在大連和廣州 有兩個分廠

10、生產(chǎn)同一種儀器，大連分廠 每月生產(chǎn)400臺，廣州分廠每月生產(chǎn)600 臺。該公司在上海和天津有兩個銷售公 司負(fù)責(zé)對南京、濟(jì)南、南昌、青島四個 城市的儀器供應(yīng)。另外因為大連距離青 島較近，公司同意大連分廠向青島直接 供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問應(yīng)該如何調(diào)運(yùn)儀器， 可使總運(yùn)輸費(fèi)用最低？圖中 1- 廣州、2 - 大連、 3 - 上海、4 - 天津、5 - 南京、6 - 濟(jì)南、7 - 南昌、8 - 青島,14,3運(yùn)輸問題的應(yīng)用,解：設(shè) xij 為從 i 到 j 的運(yùn)輸量，可得到有下列特點的線性規(guī)劃模型： 目標(biāo)函數(shù)：Min f = 所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價與運(yùn)輸量乘積之和） 約束條件： 對產(chǎn)地（

11、發(fā)點） i ：輸出量 - 輸入量 = 產(chǎn)量 對轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點）：輸入量 - 輸出量 = 0 對銷地（收點） j ：輸入量 - 輸出量 = 銷量 例8（續(xù)） 目標(biāo)函數(shù)： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 約束條件： s.t. x13+ x14 600 (廣州分廠供應(yīng)量限制） x23+ x24+ x28 400 (大連分廠供應(yīng)量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海銷售公司，轉(zhuǎn)運(yùn)站） -x14- x24 + x45

12、 + x46+ x47 + x48 = 0 （天津銷售公司，轉(zhuǎn)運(yùn)站） x35+ x45 = 200 （南京的銷量） x36+ x46 = 150 （濟(jì)南的銷量） x37+ x47 = 350 （南昌的銷量） x38+ x48 + x28 = 300 （青島的銷量） xij 0 , i,j = 1,2,3,4,5,6,7,8,15,3運(yùn)輸問題的應(yīng)用,用“管理運(yùn)籌學(xué)”軟件求得結(jié)果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47

13、 = 0 x48 = 0 。 最小運(yùn)輸費(fèi)用為：4600百元 例9、某公司有A1、 A2、 A3三個分廠生產(chǎn)某種物資，分別供應(yīng)B1、 B2、 B3、 B4四個地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表： 試求總費(fèi)用為最少的調(diào)運(yùn)方案。 假設(shè)： 1.每個分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個產(chǎn)地集中一起運(yùn)； 2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個銷地，再轉(zhuǎn)運(yùn)給其他銷地； 3.除產(chǎn)銷地之外，還有幾個中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。,16,3運(yùn)輸問題的應(yīng)用,運(yùn)價如下表： 解：把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題： 1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時看作產(chǎn)地和銷地； 2、運(yùn)輸表

14、中不可能方案的運(yùn)費(fèi)取作M，自身對自身的運(yùn)費(fèi)為0； 3、Ai： 產(chǎn)量為 20+原產(chǎn)量， 銷量為 20； Ti ： 產(chǎn)量、銷量均為 20； Bi： 產(chǎn)量為 20， 銷量為 20 +原銷量，其中20為各點可能變化的最大流量； 4、對于最優(yōu)方案，其中 xi i 為自身對自身的運(yùn)量，實際上不進(jìn)行運(yùn)作。,17,3運(yùn)輸問題的應(yīng)用,擴(kuò)大的運(yùn)輸問題產(chǎn)銷平衡與運(yùn)價表：,18,4*運(yùn)輸問題的表上作業(yè)法,表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實質(zhì)是單純形法。 運(yùn)輸問題都存在最優(yōu)解。 計算過程（假設(shè)產(chǎn)銷平衡）： 1.找出初始基本可行解。對于有m個產(chǎn)地n個銷地的產(chǎn)銷平衡問題，則有m個關(guān)于產(chǎn)量的約束方程和n個關(guān)于銷量的

15、約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個獨立的約束方程，即運(yùn)輸問題有m+n-1個基變量。在mn的產(chǎn)銷平衡表上給出m+n-1個數(shù)字格，其相對應(yīng)的調(diào)運(yùn)量的值即為基變量的值。 2.求各非基變量的檢驗數(shù)，即檢驗除了上述m+n-1個基變量以外的空格的檢驗數(shù)判別是否達(dá)到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉(zhuǎn)到下一步。 3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調(diào)整。 4.重復(fù)2、3直到得到最優(yōu)解。,19,4*運(yùn)輸問題的表上作業(yè)法,例10.喜慶食品公司有三個生產(chǎn)面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠

16、到各銷售公司的單位運(yùn)價如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價的單位為百元/噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點的需求量的前提下總運(yùn)費(fèi)最少？ 這是一個產(chǎn)銷平衡的運(yùn)輸問題，因此不需要再設(shè)假想產(chǎn)地和銷地了。,20,4*運(yùn)輸問題的表上作業(yè)法,一、確定初始基本可行解 為了把初始基本可行解與運(yùn)價區(qū)分開，我們把運(yùn)價放在每一欄的右上角，每 一欄的中間寫上初始基本可行解（調(diào)運(yùn)量）。 1.西北角法：先從表的左上角（即西北角）的變量x11開始分配運(yùn)輸量，并使 x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的 產(chǎn)量都減去3填入銷量和產(chǎn)量處，劃去原來的銷量和產(chǎn)

17、量。同理可得余下的初始基 本可行解。,3,11,3,10,8,5,10,2,9,4,7,1,21,4*運(yùn)輸問題的表上作業(yè)法,2.最小元素法 西北角法是對西北角的變量分配運(yùn)輸量，而最小元素法是就近供應(yīng)，即對單位運(yùn)價最小的變量分配運(yùn)輸量。在表上找到單位運(yùn)價最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產(chǎn)量改為1，B1的銷量改為0，并把B1列劃去。在剩下的33矩陣中再找最小運(yùn)價，同理可得其他的基本可行解。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運(yùn)價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。,3,11,3,10,

18、8,5,10,2,9,4,7,1,22,4*運(yùn)輸問題的表上作業(yè)法,在求初始基本可行解時要注意的兩個問題： 1.當(dāng)我們?nèi)《▁ij的值之后，會出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。 2.用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個，即保證基變量的個數(shù)為m+n-1個。,23,4*運(yùn)輸問題的表上作業(yè)法,二、最優(yōu)解的判別 1.閉回路法 所謂閉回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個代表非基變量的空格出發(fā)，沿水

19、平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。 所謂閉回路法，就是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點的調(diào)運(yùn)量加上或減少1。最后我們計算出由這些變化給整個運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。,24,4*運(yùn)輸問題的表上作業(yè)法,從非基變量x11出發(fā)，找到一個閉回路如上表所示?；芈酚兴膫€頂點，除x11外，其余都為基變量?，F(xiàn)在把x11的調(diào)運(yùn)量從零增加為1噸，運(yùn)費(fèi)也增加了3元，為了使A1產(chǎn)量平衡，x13必須減少1噸，運(yùn)費(fèi)減少3元。為了B3的銷量平衡，x23必須增加1噸，運(yùn)費(fèi)增加2元。同理把x21減少1噸，運(yùn)費(fèi)減少1元。調(diào)整后，總運(yùn)費(fèi)增加了3-3+2-1=1元。說明如果讓x11為基變量，運(yùn)費(fèi)就會增加，其增加值1作為x11的檢驗數(shù)，為了區(qū)別調(diào)整量，我們把1加圈。 用同樣的方法可以找出所有空格（即非基變量）的檢驗數(shù)。,3,11,3,10,8,5,10,2,9,4,7,1,25,4*運(yùn)輸問題的表上作業(yè)法,2.位勢法 所謂位