第四章運 輸 問 題_第1頁
第四章運 輸 問 題_第2頁
第四章運 輸 問 題_第3頁
第四章運 輸 問 題_第4頁
第四章運 輸 問 題_第5頁
已閱讀5頁,還剩22頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、1第四章第四章 運運 輸輸 問問 題題 1 1運運 輸輸 模模 型型 2 2運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 3 3運輸問題的進一步討論運輸問題的進一步討論 4 4 運輸問題的應(yīng)用運輸問題的應(yīng)用2例例1、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最???B1B2B3產(chǎn)量A1646200A2655300銷量150150200解:解: 產(chǎn)銷平衡問題: 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量,得到下列運輸量表: B1B2B3產(chǎn)量A1x11x12x132

2、00A2x21x22x23300銷量150150200 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2;j = 1、2、3) 1 1運運 輸輸 模模 型型3 一般運輸模型:一般運輸模型:產(chǎn)銷平衡 A1、 A2、 Am 表示某物資的m個產(chǎn)地; B1、B2、Bn 表示某物質(zhì)的n個銷地;si 表示產(chǎn)地Ai的產(chǎn)量; dj 表示銷地Bj 的銷量;

3、cij 表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量,得到下列一般運輸量問題的模型: m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 42 2運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 表上作業(yè)法是一種求解運輸問題的特殊方法,其實質(zhì)是單純形法。 運輸問題都存在最優(yōu)解。 計算過程(假設(shè)產(chǎn)銷平衡): 1.找出初始基本可行解。對于有m個產(chǎn)地n個銷地的產(chǎn)銷平衡問題,則

4、有m個關(guān)于產(chǎn)量的約束方程和n個關(guān)于銷量的約束方程。由于產(chǎn)銷平衡,其模型最多只有m+n-1個獨立的約束方程,即運輸問題有m+n-1個基變量。在mn的產(chǎn)銷平衡表上給出m+n-1個數(shù)字格,其相對應(yīng)的調(diào)運量的值即為基變量的值。 2.求各非基變量的檢驗數(shù),即檢驗除了上述m+n-1個基變量以外的空格的檢驗數(shù)判別是否達到最優(yōu)解,如果已是最優(yōu),停止計算,否則轉(zhuǎn)到下一步。 3.確定入基變量和出基變量,找出新的基本可行解。在表上用閉回路法調(diào)整。 4.重復(fù)2、3直到得到最優(yōu)解。5一、確定初始基本可行解 為了把初始基本可行解與運價區(qū)分開,我們把運價放在每一欄的右上角,每一欄的中間寫上初始基本可行解(調(diào)運量)。 1.西

5、北角法:先從表的左上角(即西北角)的變量x11開始分配運輸量,并使x11取盡可能大的值,即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的產(chǎn)量都減去3填入銷量和產(chǎn)量處,劃去原來的銷量和產(chǎn)量。同理可得余下的初始基本可行解。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 47 4 0 A2 2 24 2 0 A3 3 69 6 0 銷量 3 0 6 2 0 5 3 0 6 0 202031131085102947162.最小元素法 西北角法是對西北角的變量分配運輸量,而最小元素法是就近供應(yīng),即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21,并使x2

6、1取盡可能大的值,即x21=min(4,3)=3,把A1的產(chǎn)量改為1,B1的銷量改為0,并把B1列劃去。在剩下的33矩陣中再找最小運價,同理可得其他的基本可行解。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 銷量 3 0 6 0 5 4 0 6 3 0 20203113108510294717 在求初始基本可行解時要注意的兩個問題: 1.當(dāng)我們?nèi)《▁ij的值之后,會出現(xiàn)Ai的產(chǎn)量與Bj

7、的銷量都改為零的情況,這時只能劃去Ai行或Bj列,但不能同時劃去Ai行與Bj列。 2.用最小元素法時,可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況,此時在這一行或者一列中除去已填上的數(shù)外均填上零,不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個,即保證基變量的個數(shù)為m+n-1個。8二、最優(yōu)解的判別1.閉回路法 所謂閉回路是在已給出的調(diào)運方案的運輸表上從一個代表非基變量的空格出發(fā),沿水平或垂直方向前進,只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度(當(dāng)然也可以不改變方向)繼續(xù)前進,這樣繼續(xù)下去,直至回到出發(fā)的那個空格,由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉

8、回路。 所謂閉回路法,就是對于代表非基變量的空格(其調(diào)運量為零),把它的調(diào)運量調(diào)整為1,由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零,則已求得最優(yōu)解,否則繼續(xù)迭代找出最優(yōu)解。9從非基變量x11出發(fā),找到一個閉回路如上表所示?;芈酚兴膫€頂點,除x11外,其余都為基變量?,F(xiàn)在把x11的調(diào)運量從零增加為1噸,運費也增加了3元,為了使A1產(chǎn)量平衡,x13必須減少1噸,運費減少3元。為了B3的銷量平衡,x23必須增加1噸,運費增加2元。同理把x21減

9、少1噸,運費減少1元。調(diào)整后,總運費增加了3-3+2-1=1元。說明如果讓x11為基變量,運費就會增加,其增加值1作為x11的檢驗數(shù),為了區(qū)別調(diào)整量,我們把1加圈。用同樣的方法可以找出所有空格(即非基變量)的檢驗數(shù)。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 1 4 7 A2 3 1 4 A3 9 銷量 3 6 5 6 2020311310851029471102.位勢法 所謂位勢法,我們對運輸表上的每一行賦予一個數(shù)值ui,對每一列賦予一個數(shù)值vj,它們的數(shù)值是由基變量xij的檢驗數(shù) 所決定的,則非基變量xij的檢驗數(shù)就可以用公式 求出。 我們先給u1賦個任意數(shù)值,不妨設(shè)u1=0,則從基變

10、量x13的檢驗數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10,u2=-1等等見上表。檢驗值的求法即用公式 ,如 。 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 20203113108510294710jiijijvucjiijijvucjiijijvuc1203111111vuc11三、改進運輸方案的辦法閉回路調(diào)整法 當(dāng)表中的某個檢驗數(shù)小于零時,方案不為最優(yōu),需要調(diào)整。方法是:選取所有負檢驗數(shù)最小的非基變量作為入基變量,以求盡快實現(xiàn)最優(yōu)。本例中取 ,表明增加一個單位的x24

11、運輸量,可使得總運費減少1。在以x24為出發(fā)點的閉回路中,找出所有偶數(shù)的頂點的調(diào)運量:x14=3,x23=1,x24=min(3,1)=1。把所有閉回路上為偶數(shù)頂點的運輸量都減少這個值,奇數(shù)頂點的運輸量都增加這個值(見下表)。124 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1) +1 -1 A3 6 3 -5 vj 2 9 3 10 202031131085102947112對上表用位勢法進行檢驗如下表 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 5 2 7 A2 3 1 4 A3 6 3 9 銷量 3 6 5 6 2020 銷地產(chǎn)地 B1

12、 B2 B3 B4 ui A1 0 2 5 2 0 A2 3 2 1 1 -1 A3 9 6 12 3 -5 vj 2 9 3 10 202031131085102947113四、如何找多個最優(yōu)方案 識別是否有多個最優(yōu)解的方法和單純形表法一樣,只需看最優(yōu)方案中是否存在非基變量的檢驗數(shù)為零。如在本題中給出的最優(yōu)運輸方案中x11的檢驗數(shù)為0,可知此運輸問題有多個最優(yōu)解。只要把x11作為入基變量,調(diào)整運輸方案,就可得到另一個最優(yōu)方案。 銷地產(chǎn)地 B1 B2 B3 B4A1 (+2) 5 2(-2)A2 3(-2) 1(+2)A3 6 3 銷地產(chǎn)地 B1 B2 B3 B4A1 2 5 A2 1 3A3

13、 6 3141.供需不平衡問題供需不平衡問題例例1、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最???解解:增加一個虛設(shè)的銷地運輸費用為0 B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 300 A2 6 5 5 300 銷銷量量 150 150 200 600 500 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 6 4 6 0 300 A2 6 5 5 0 300 銷銷量量 150 150 200 100 600 600 3運輸問題的進一步討論運輸問題的進一步討論15例例2、某公司從

14、兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示,問:應(yīng)如何調(diào)運可使總運輸費用最???解解:增加一個虛設(shè)的產(chǎn)地運輸費用為0 B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 200 A2 6 5 5 300 銷銷量量 250 200 200 500 650 B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 銷銷量量 250 200 200 650 650 162.轉(zhuǎn)運問題:轉(zhuǎn)運問題: 在原運輸問題上增加若干轉(zhuǎn)運站。運輸方式有:產(chǎn)地 轉(zhuǎn)運站、轉(zhuǎn)運站 銷地、產(chǎn)地 產(chǎn)地、產(chǎn)地

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

16、價與運輸量乘積之和)約束條件: 對產(chǎn)地(發(fā)點) i :輸出量 - 輸入量 = 產(chǎn)量 對轉(zhuǎn)運站(中轉(zhuǎn)點):輸入量 - 輸出量 = 0 對銷地(收點) j :輸入量 - 輸出量 = 銷量目標(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)運站) -x

17、14- x24 + x45 + x46+ x47 + x48 = 0 (天津銷售公司,轉(zhuǎn)運站) x35+ x45 = 200 (南京的銷量) x36+ x46 = 150 (濟南的銷量) x37+ x47 = 350 (南昌的銷量) x38+ x48 + x28 = 300 (青島的銷量) xij 0 , i,j = 1,2,3,4,5,6,7,818用用“運籌學(xué)運籌學(xué)”軟件求得結(jié)果:軟件求得結(jié)果: x13 = 550 x14 =50 ; x23 = 0 x24 = 100 x28 = 300 ; x35 = 200 x36 = 0 x37 = 350 x38 = 0 ; x45 = 0 x4

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

19、:解:解:把此轉(zhuǎn)運問題轉(zhuǎn)化為一般運輸問題: 1、把所有產(chǎn)地、銷地、轉(zhuǎn)運站都同時看作產(chǎn)地和銷地; 2、運輸表中不可能方案的運費取作M,自身對自身的運費為0; 3、Ai: 產(chǎn)量為 20+原產(chǎn)量, 銷量為 20; Ti : 產(chǎn)量、銷量均為 20; Bi: 產(chǎn)量為 20, 銷量為 20 +原銷量,其中20為各點可能變化的最大流量; 4、對于最優(yōu)方案,其中 xi i 為自身對自身的運量,實際上不進行運作。A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21-35-21928A33-1-2374105T12311322846T215-1114527T34-23121824T432

20、32121-2621194858-121B332104222423B41085674621320 擴大的運輸問題產(chǎn)銷平衡與運價表: A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 產(chǎn)量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2

21、 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 銷量 20 20 20 20 20 20 20 23 26 25 26 240 214 4運輸問題的應(yīng)用運輸問題的應(yīng)用一、產(chǎn)銷不平衡的運輸問題一、產(chǎn)銷不平衡的運輸問題例例1、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸,由河北臨城、山西盂縣兩處煤礦負責(zé)供應(yīng),價格、質(zhì)量相同。供應(yīng)能力分別為1500、400

22、0噸,運價為: 由于需大于供,經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸,二區(qū)必須滿足需求量,三區(qū)供應(yīng)量不少于1500噸,試求總費用為最低的調(diào)運方案。解:解: 根據(jù)題意,作出產(chǎn)銷平衡與運價表:這里 M 代表一個很大的正數(shù),其作用是強迫相應(yīng)的 x31、 x33、 x34取值為0。22一、產(chǎn)銷不平衡的運輸問題一、產(chǎn)銷不平衡的運輸問題例例2、設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同,有關(guān)數(shù)據(jù)如下表: 試求總費用為最低的化肥調(diào)撥方案。解:解: 根據(jù)題意,作出產(chǎn)銷平衡與運價表: 最低要求必須滿足,因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 M ,而最高要求與最低要求的差允許按需要安排,

23、因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 0 。對應(yīng) 4”的銷量 50 是考慮問題本身適當(dāng)取的數(shù)據(jù),根據(jù)產(chǎn)銷平衡要求確定 D的產(chǎn)量為 50。 1234產(chǎn)量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限 1 1” 2 3 4 4” 產(chǎn)量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 銷量 30 20 70 30 10 50 210 210 23二、生產(chǎn)與儲存問題二、生產(chǎn)與儲存問題例例3、某廠按合同規(guī)定須于當(dāng)年每個季度末分

24、別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當(dāng)季不交貨,每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下,使該廠全年生產(chǎn)總費用為最小的決策方案。生產(chǎn)能力(臺) 單位成本(萬元)一季度2510.8二季度3511.1三季度3011.0四季度1011.324解:解: 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機數(shù)目,那么應(yīng)滿足: 交貨:x11 = 10 生產(chǎn):x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x

25、23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生產(chǎn)的柴油機數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量;把第 j 季度交貨的柴油機數(shù)目看作第 j 個銷售點的銷量;成本加儲存、維護等費用看作運費??蓸?gòu)造下列產(chǎn)銷平衡問題:目標(biāo)函數(shù):目標(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 第一季度 第二季度 第三季度 第四季度 D 產(chǎn)量 第一季度 10

26、.80 10.95 11.10 11.25 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 銷量 10 15 25 20 30 100 100 25二、生產(chǎn)與儲存問題二、生產(chǎn)與儲存問題例例4、光明儀器廠生產(chǎn)電腦繡花機是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機平均生產(chǎn)費用見下表: 已知上年末庫存103臺繡花機,如果當(dāng)月生產(chǎn)出來的機器當(dāng)月不交貨,則需要運到分廠庫房,每臺增加運輸成本0.1萬元,每臺機器每月的平均倉儲費、維護費為0.2萬元。在7-8月份銷售淡季,全廠停產(chǎn)1個月,因此在6月份完成銷售合同后還要留出庫存80臺。加班生產(chǎn)機器每臺增加成本1萬元。問應(yīng)如何安排1-6月份的生產(chǎn)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論