zt線性規(guī)劃的運輸問題(PPT 32)作業(yè)講解

1、課題： 工學(xué)院計算機(jī)系年10月3.2 用用表表上上作作業(yè)業(yè)法法求求解解運運輸輸問問題題銷銷地地產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 銷銷量量 1 3 2 5 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷銷地地產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A3 5 7 6 2 5 銷銷量量 1 3 2 5 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷銷地地產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 9 3 8 7 3 A2 4 9 4 5 3 A

2、3 5 7 6 2 5 銷銷量量 1 3 2 5 課課堂堂內(nèi)內(nèi)容容3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 銷銷地地 產(chǎn)產(chǎn)地地 B1 B2 Bn 產(chǎn)產(chǎn)量量ai A1 C11 x11 C12 x12 C1n x1n a1 A2 C12 x21 C12 x22 C12 x23 a2 Am Cm1 xm1 Cm2 xm2 Cmn xmn am 銷銷量量 bj b1 b2 bn 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論1 1 產(chǎn)量大于銷量產(chǎn)量大于銷量目標(biāo)函數(shù)：目標(biāo)函數(shù)：stst. .3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論2 2 銷量大于產(chǎn)量銷量大于產(chǎn)量目標(biāo)函數(shù)：目標(biāo)函數(shù)：st

3、st. .3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 1 1 產(chǎn)量大于銷量產(chǎn)量大于銷量minjjiba11增加一個假想的銷地增加一個假想的銷地Bn+1，其銷量為其銷量為bn+1 ；從從Ai 運到運到Bn+1的的物品數(shù)量物品數(shù)量xi,n+1 ；（3） ci,n+1 = = 0 0 ； 因為因為Bn+1實際上不存在，所以實際上不存在，所以xi,n+1 實際上就是就實際上就是就地存儲在產(chǎn)地地存儲在產(chǎn)地Ai 的物品數(shù)量。的物品數(shù)量。（1）（2）3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論stst. .產(chǎn)量大于銷量的：產(chǎn)量大于銷量的：3.3 運運

4、輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 2 2 銷量大于產(chǎn)量銷量大于產(chǎn)量增加一個假想的產(chǎn)地增加一個假想的產(chǎn)地Am+1，其產(chǎn)量為其產(chǎn)量為am+1 ；從從Am+1 運到運到Bj的物品數(shù)量的物品數(shù)量xm+1,j ；（3） ci,n+1 = = 0 0 ； 因為因為Am+1實際上不存在，所以實際上不存在，所以xm+1,j實際上是各銷實際上是各銷地地Bj所需物品的欠缺額。所需物品的欠缺額。xm+1,jxm+1,j（1）（2）3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論stst. .銷量大于產(chǎn)量的：銷量大于產(chǎn)量的：m+1m+1m+1m+13.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷地銷地產(chǎn)地產(chǎn)地

5、B1 B2 B3 產(chǎn)量產(chǎn)量 A1 6 4 5 70 A2 8 3 2 40 A3 7 5 6 50 A4 5 1 2 20 銷量銷量 30 40 30 180 100 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷銷地地產(chǎn)產(chǎn)地地 B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 5 70 A2 8 3 2 40 A3 7 5 6 50 A4 5 1 2 20 銷銷量量 30 40 30 B43.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷銷地地產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 6 4 5 0 70 A2 8 3 2 0 40 A3 7 5 6 0 50 A4 5 1 2 0 20

6、 銷銷量量 30 40 30 80 180 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論銷銷地地 產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 6 30 4 10 5 0 30 70 A2 8 3 10 2 30 0 40 A3 7 5 6 0 50 50 A4 5 1 20 2 0 20 銷銷量量 30 40 30 80 180 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論運價 地區(qū)煤礦甲乙丙丁產(chǎn)量 A B C161419131320221923171525506050最低需求最高需求3050707003010不限設(shè)有三煤礦供應(yīng)四地區(qū)，資料如下：3.3 運運輸輸問問題題的的進(jìn)進(jìn)一

7、一步步討討論論虛擬產(chǎn)量的運輸費用為零虛擬產(chǎn)量的運輸費用為零,但它對于基本需求來講但它對于基本需求來講,運費為無窮大。運費為無窮大。本題產(chǎn)量本題產(chǎn)量160萬噸，最低需求萬噸，最低需求110萬噸，最高需求萬噸，最高需求無限。實質(zhì)上比較現(xiàn)實的最高需求無限。實質(zhì)上比較現(xiàn)實的最高需求210萬噸萬噸;(?)產(chǎn)量大于最小需求；小于最大需求。而標(biāo)準(zhǔn)型是：產(chǎn)量大于最小需求；小于最大需求。而標(biāo)準(zhǔn)型是：產(chǎn)量產(chǎn)量=銷量；銷量；處理辦法：設(shè)想一個虛擬煤礦處理辦法：設(shè)想一個虛擬煤礦D，生產(chǎn)生產(chǎn)50萬噸萬噸,但但這個產(chǎn)量只能供應(yīng)可有可無的最高需求部分這個產(chǎn)量只能供應(yīng)可有可無的最高需求部分,于是于是各地的需求各地的需求也應(yīng)分

8、為兩個部分：也應(yīng)分為兩個部分：基本需求基本需求、機(jī)動機(jī)動需求需求；運運價價 地地區(qū)區(qū) 煤煤礦礦 甲甲 乙乙 丙丙 丁丁 產(chǎn)產(chǎn)量量 A 16 13 22 17 50 B 14 13 19 12 60 C 19 20 23 25 50 需需求求量量 50運運價價 地地區(qū)區(qū) 煤煤礦礦 甲甲 乙乙 丙丙 丁丁 產(chǎn)產(chǎn)量量 A 16 13 22 17 50 B 14 13 19 12 60 C 19 20 23 25 50 最最 低低 需需 求求 最最 高高 需需 求求 30 50 70 70 0 30 10 不限 設(shè)想一個虛擬煤礦設(shè)想一個虛擬煤礦D,生產(chǎn)生產(chǎn)5050萬噸萬噸, , 這個產(chǎn)量只能供應(yīng)可有可

9、這個產(chǎn)量只能供應(yīng)可有可無的最高需求部分無的最高需求部分, ,于是各地的需求分為于是各地的需求分為基本需求基本需求和和機(jī)動需求機(jī)動需求；3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 產(chǎn)產(chǎn) 量量 A 16 16 13 22 17 17 50 B 14 14 13 19 12 12 60 C 19 19 20 23 25 25 50 D M 0 M 0 M 0 50 需需 求求 量量 30 20 70 30 10 50 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 ui A 16 16 13 50 22

10、17 17 B 14 14 13 19 12 10 12 50 C 19 30 19 20 20 23 25 25 D M 0 0 M 20 0 30 M 0 0 vj 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 甲甲1 甲甲2 乙乙 丙丙 丁丁1 丁丁2 ui A 16 16 13 50 22 17 17 B 14 14 13 20 19 12 10 12 30 C 19 30 19 20 20 23 25 25 D M 0 0 M 0 30 M 0 20 vj 3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論假定假定m個個產(chǎn)地產(chǎn)地A1,A2,Am和和n個銷地個銷地B1,B2,Bn都可

11、以作為中間轉(zhuǎn)都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點和接收物品的地點都有運站使用，從而發(fā)送物品的地點和接收物品的地點都有m+n個。個。例例令：令：ai第第i個產(chǎn)地的產(chǎn)量（凈供應(yīng)量）；個產(chǎn)地的產(chǎn)量（凈供應(yīng)量）；bj第第j個銷地的銷量（凈需要量）；個銷地的銷量（凈需要量）；xij由第由第i個發(fā)送地運到第個發(fā)送地運到第j個接收地的物品數(shù)量；個接收地的物品數(shù)量；cij由第由第i個發(fā)送地到第個發(fā)送地到第j個接收地的單位運價個接收地的單位運價；ci第第i個地點轉(zhuǎn)運單位物品的費用個地點轉(zhuǎn)運單位物品的費用；Q3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 產(chǎn)地 銷地 接收 發(fā)送 1 m m+1 m+n

12、發(fā)送量 1 x11 x1m x1,m+1 x1,m+n Q+a1 產(chǎn)地 m xm1 xmm xm,m+1 xm,m+n Q+am m+1 xm+1,1 xm+1,m xm+1,m+1 xm+1,m+n Q 銷地 m+n xm+n,1 xm+n,m xm+n,m+1 xm+n,m+n Q 接收量 Q Q Q+bm+1 Q+bm+n 產(chǎn)銷表產(chǎn)銷表3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 產(chǎn)地 銷地 接收 發(fā)送 1 m m+1 m+n 發(fā)送量 1 -c1 c1m c1,m+1 c1,m+n Q+a1 產(chǎn)地 m cm1 -cm cm,m+1 cm,m+n Q+am m+1 cm+1,1 cm+

13、1,m -cm+1 cm+1,m+n Q 銷地 m+n cm+n,1 cm+n,m cm+n,m+1 -cm+n Q 接收量 Q Q Q+bm+1 Q+bm+n 運價表運價表3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論stst. .m+nm+n轉(zhuǎn)運模型：轉(zhuǎn)運模型：m+nm+nm+nm+n3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論左圖顯示出了一個運輸系統(tǒng)左圖顯示出了一個運輸系統(tǒng), ,它包括二個它包括二個產(chǎn)地產(chǎn)地( (和和) )二個銷地二個銷地( (和和) )及一及一個中間轉(zhuǎn)運站個中間轉(zhuǎn)運站( (),),各產(chǎn)地的產(chǎn)量和各銷各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點處箭線旁的數(shù)字表地的銷量用相應(yīng)

14、節(jié)點處箭線旁的數(shù)字表示，節(jié)點連線上的數(shù)字為該地的轉(zhuǎn)運單示，節(jié)點連線上的數(shù)字為該地的轉(zhuǎn)運單價價, ,試確定最優(yōu)運輸方案。試確定最優(yōu)運輸方案。 產(chǎn)地 轉(zhuǎn)運 銷地 接收 發(fā)送 1 2 3 4 5 發(fā)送量 1 產(chǎn)地 2 轉(zhuǎn)運 3 4 銷地 5 接收量 運價表運價表3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 產(chǎn)地 轉(zhuǎn) 運 銷地 產(chǎn)地 轉(zhuǎn) 運 銷地 接收 發(fā)送 1 1 2 2 3 3 4 4 5 5 發(fā) 量 1 2 3 4 5 1 1 60 -4 5 3 2 M 產(chǎn)地 2 2 90 5 -1 2 M 4 轉(zhuǎn) 運 3 3 50 3 2 -3 5 5 4 4 50 2 M 5 -3 6 銷地 5 5 5

15、0 M 4 5 6 -5 收量 50 50 50 80 70 一、初始調(diào)運方案一、初始調(diào)運方案解解初始調(diào)運方案：初始調(diào)運方案：x12,x22x24x25x33x34x14，,x44x55=相應(yīng)運價為：相應(yīng)運價為：c12,c22c24c25c33c34c14，,c44c5550 ,50 20 20 50010，,50 50=-4 ,-1M4-352，,-3-5 二、解的最優(yōu)性檢驗和改進(jìn)二、解的最優(yōu)性檢驗和改進(jìn)3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 產(chǎn) 地 轉(zhuǎn) 運 銷 地 接 收 發(fā) 送 1 1 2 2 3 3 4 4 5 5 ui 1 1 - -4 4 50 5 3 2 2 10 M 產(chǎn)地 2 2 5 5 - -1 1 50 2 M M 20 4 4 20 轉(zhuǎn) 運 3 3 3 3 2 - -3 3 50 5 5 0 5 4 4 2 2 M 5 - -3 3 50 6 銷地 5 5 M M 4 5 6 - -5 5 50 vj 解解3.3 運運輸輸問問題題的的進(jìn)進(jìn)一一步步討討論論 產(chǎn) 地 轉(zhuǎn) 運 銷 地 接 收 發(fā) 送 1 1 2 2