管理運(yùn)籌學(xué)--運(yùn)輸問(wèn)題

1、管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)華國(guó)偉華國(guó)偉Email:北京交通大學(xué)經(jīng)管學(xué)院物流管理系北京交通大學(xué)經(jīng)管學(xué)院物流管理系第三章第三章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 Transportation Problem本節(jié)內(nèi)容提要本節(jié)內(nèi)容提要3.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模運(yùn)輸問(wèn)題的數(shù)學(xué)模 3.2 表上作業(yè)法表上作業(yè)法3.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型1aiama1bjbnb11c1jc1 icijcincmncmjc1mc1nc例：某運(yùn)輸問(wèn)題的資料如下：例：某運(yùn)輸問(wèn)題的資料如下：?jiǎn)挝?銷(xiāo)地 運(yùn)價(jià)產(chǎn)地產(chǎn)量2910291342584257銷(xiāo)量38464321 BBBB321AAA一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型 )4

2、. 3 . 2 . 1, 3 . 2 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約約束束條條件件：目目標(biāo)標(biāo)函函數(shù)數(shù)：為為運(yùn)運(yùn)量量設(shè)設(shè) 數(shù)學(xué)模型的一般形式數(shù)學(xué)模型的一般形式 已知資料如下：已知資料如下：?jiǎn)?銷(xiāo) 產(chǎn) 量產(chǎn)地產(chǎn)量銷(xiāo) 量nBB 11 mAAmaa 1nbb 1mnmncccc 1111運(yùn)運(yùn)價(jià)價(jià)nijjm1iiba供需平衡供需平衡 ) ( 0m

3、in11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)銷(xiāo)平衡時(shí)，其模型如下：當(dāng)產(chǎn)銷(xiāo)平衡時(shí)，其模型如下：Ai的產(chǎn)品全部的產(chǎn)品全部供應(yīng)出去供應(yīng)出去Bj的需求全的需求全部得到滿足部得到滿足產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解.當(dāng)產(chǎn)大于銷(xiāo)時(shí)，其模型是：當(dāng)產(chǎn)大于銷(xiāo)時(shí)，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)小于銷(xiāo)時(shí)，其模型是：當(dāng)產(chǎn)小于銷(xiāo)時(shí)，其模型是：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并假設(shè)：并假設(shè)： 1112121222nm1m2mn 1 1 1 1 1 1

4、 nx xx xxxxxx 1 1 11 1 1 1 1 1 1 1 1 mnijimjPee1mn 個(gè)基變量平衡表、運(yùn)價(jià)表和二為一：平衡表、運(yùn)價(jià)表和二為一：銷(xiāo)產(chǎn)B1B2Bn產(chǎn)量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam銷(xiāo)量b1b1bn約束條件或解可用產(chǎn)銷(xiāo)平衡表表示約束條件或解可用產(chǎn)銷(xiāo)平衡表表示: minjijijxczmin11 )n,j(bx)m,i (axmijijnjiij1 1 11 )n,j;m,i (xij11 0 uivj無(wú)約束無(wú)約束 （i=1,2, ,m;j=1,2, ,n)uivj設(shè)設(shè)u ui,v,vj為對(duì)偶變量，對(duì)偶問(wèn)題模型為為對(duì)偶變量

5、，對(duì)偶問(wèn)題模型為nijjjmiiivbuaw1maxijjicvum個(gè)個(gè) n個(gè)個(gè) 特征：特征： 1 1、平衡運(yùn)輸問(wèn)題必有可行解，也、平衡運(yùn)輸問(wèn)題必有可行解，也必有最優(yōu)解；必有最優(yōu)解； 2 2、運(yùn)輸問(wèn)題的基本可行解中應(yīng)包、運(yùn)輸問(wèn)題的基本可行解中應(yīng)包括括 m+n1 個(gè)基變量。個(gè)基變量。 . .重復(fù)重復(fù). . ，直到找到最優(yōu)解為止。，直到找到最優(yōu)解為止。步驟：步驟： . .找出找出初始基本可行解初始基本可行解（初始調(diào)運(yùn)方案，一（初始調(diào)運(yùn)方案，一般般m+n-1m+n-1個(gè)數(shù)字格），用西北角法、最小元素法；個(gè)數(shù)字格），用西北角法、最小元素法； . .求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到求出各非基變量的檢

6、驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用位勢(shì)法計(jì)算；位勢(shì)法計(jì)算； . .改進(jìn)當(dāng)前的基本可行解（確定換入、換改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；出變量），用閉合回路法調(diào)整； 二、表上作業(yè)法二、表上作業(yè)法確定確定m+n-1個(gè)基變量個(gè)基變量空格空格3.2 求解運(yùn)輸問(wèn)題的算法求解運(yùn)輸問(wèn)題的算法:表上作業(yè)法表上作業(yè)法開(kāi)開(kāi) 始始求各非基變求各非基變量的檢驗(yàn)數(shù)量的檢驗(yàn)數(shù)是否達(dá)到最優(yōu)解是否達(dá)到最優(yōu)解結(jié)束結(jié)束確定換入變量確定換入變量與換出變量與換出變量新的基可行解新的基可行解求初始基可行解求初始基可行解例一、某運(yùn)輸資料如下表

7、所示：例一、某運(yùn)輸資料如下表所示：?jiǎn)挝粏挝?銷(xiāo)地銷(xiāo)地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量311310719284741059銷(xiāo)量銷(xiāo)量36564321 BBBB321AAA1 1、求初始方案：、求初始方案：3.2.1初始基可行解的確定初始基可行解的確定西北角法 西北角發(fā)也就是從運(yùn)價(jià)表的西北角位置開(kāi)始,依次安排m個(gè)產(chǎn)地和n個(gè)銷(xiāo)地之間的運(yùn)輸業(yè)務(wù),從而得到一個(gè)初始調(diào)運(yùn)方案的方法. 西北角法應(yīng)遵循“優(yōu)先安排運(yùn)價(jià)表上編號(hào)最小的產(chǎn)地和銷(xiāo)地之間(即運(yùn)價(jià)表的西北角位置)的運(yùn)輸業(yè)務(wù)”的規(guī)則. . .西北角法西北角法( (或左上角法或左上角法):): 此法是純粹的人為的規(guī)定此法是純粹的人為的規(guī)定, ,沒(méi)有理論依據(jù)和實(shí)際背沒(méi)

8、有理論依據(jù)和實(shí)際背景景, ,但它易操作但它易操作, ,特別適合在計(jì)算機(jī)上編程計(jì)算特別適合在計(jì)算機(jī)上編程計(jì)算, ,因而受因而受歡迎歡迎. .方法如下：方法如下：總的運(yùn)費(fèi)總的運(yùn)費(fèi)(3(33)3)(4(411)11)(2(29)9)(2(22)2)(3(310)10)(6(65)5)135135元元B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷(xiāo)量銷(xiāo)量3656311310192741058341633 . .初始基可行解的確定初始基可行解的確定-最小元素法：最小元素法： 基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供基本思想是就近供應(yīng)，即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。應(yīng)（

9、調(diào)運(yùn)），然后次小，直到最后供完為止?？偟倪\(yùn)輸費(fèi)用（總的運(yùn)輸費(fèi)用（3 31 1）（）（6 64 4） （4 43 3）（）（1 12 2）（）（3 31010）（）（3 35 5）8686元元分別計(jì)算各行、各列次小、最小運(yùn)價(jià)的差值分別計(jì)算各行、各列次小、最小運(yùn)價(jià)的差值, ,優(yōu)先優(yōu)先在最大差值處進(jìn)行供需搭配在最大差值處進(jìn)行供需搭配. . 差值差值=次小次小-最小最小 步驟：步驟：10 計(jì)算未劃去行、列的差額計(jì)算未劃去行、列的差額; 20 找出最大差額對(duì)應(yīng)的最小元素找出最大差額對(duì)應(yīng)的最小元素cij進(jìn)行供需分配進(jìn)行供需分配;30 在未被劃去的行、列重新計(jì)算差額在未被劃去的行、列重新計(jì)算差額.(3)初始

10、基可行解的確定初始基可行解的確定-最大差值法最大差值法(伏格爾法伏格爾法) Vogel 6 銷(xiāo)銷(xiāo)產(chǎn)產(chǎn)B1B2B3B4供量供量A17A24A39銷(xiāo)量銷(xiāo)量 3656B1B2B3B4供量供量A13113107A219284A3741059銷(xiāo)量銷(xiāo)量3656列差值列差值2513行差值行差值 01 1 6 3 銷(xiāo)銷(xiāo)產(chǎn)產(chǎn)B1B2B3B4供量供量A17A24A3 9銷(xiāo)量銷(xiāo)量 3656B1B2B3B4行差值行差值A(chǔ)13113100A219281A3741052列差值列差值213 3 6 3 銷(xiāo)銷(xiāo)產(chǎn)產(chǎn)B1B2B3B4供量供量A17A24A3 9銷(xiāo)量銷(xiāo)量 3656B1B2B3B4行差值行差值A(chǔ)13113100A21

11、9281A374105列差值列差值212 5 1 2 6 3B1B2B3B4差值差值A(chǔ)13113107A219286A374105差值差值12 銷(xiāo)銷(xiāo)產(chǎn)產(chǎn)B1B2B3B4供量供量A17A24A3 39銷(xiāo)量銷(xiāo)量 3656 以上方法得到的初始解為基可行解 每次行(需求)或列(供應(yīng))達(dá)到飽和 每次必劃掉一行或一列 得到的元素個(gè)數(shù)必為m+n-1個(gè) 西北角法 最小元素法 最大差值法練習(xí) P97 3.1 3.2 ijij0 0 （因?yàn)槟繕?biāo)函數(shù)要求最小化）因?yàn)槟繕?biāo)函數(shù)要求最小化） 表格中有調(diào)運(yùn)量的地方為基變量表格中有調(diào)運(yùn)量的地方為基變量, ,空格處為非基變空格處為非基變 量量. .基變量的檢驗(yàn)數(shù)基變量的檢驗(yàn)數(shù)

12、ijij0,非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)ijij0. 0. ij 0 表示運(yùn)費(fèi)增加表示運(yùn)費(fèi)增加. 2 2、最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）：、最優(yōu)解的判別（檢驗(yàn)數(shù)的求法）：1jijBijcC B P01njjj mZZx 檢驗(yàn)數(shù)檢驗(yàn)數(shù)非基變量增加一個(gè)非基變量增加一個(gè)單位目標(biāo)值的變化單位目標(biāo)值的變化（1）閉回路法）閉回路法 閉回路：從空格出發(fā)順時(shí)針閉回路：從空格出發(fā)順時(shí)針(或逆時(shí)針或逆時(shí)針)畫(huà)水平畫(huà)水平(或垂直或垂直)直直線線,遇到填有運(yùn)量的方格遇到填有運(yùn)量的方格可轉(zhuǎn)可轉(zhuǎn)90,然后繼續(xù)前進(jìn)然后繼續(xù)前進(jìn),直到到達(dá)出發(fā)直到到達(dá)出發(fā)的空格所形成的閉合回路的空格所形成的閉合回路.調(diào)運(yùn)方案的任意空格存在唯

13、一閉回路調(diào)運(yùn)方案的任意空格存在唯一閉回路. 銷(xiāo)銷(xiāo)產(chǎn)產(chǎn)B1B2B3B4供量供量A1 5 27A23 14A3 6 39銷(xiāo)量銷(xiāo)量 3656差值法方案差值法方案一、最優(yōu)調(diào)運(yùn)方案的判定一、最優(yōu)調(diào)運(yùn)方案的判定銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1 B2 B3 B4 產(chǎn)產(chǎn)量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 銷(xiāo)銷(xiāo)量量 3 6 5 6 314 633最小元素法方案最小元素法方案+-+- x11為換入變量，為換入變量，x11：01，運(yùn)費(fèi)的變化為，運(yùn)費(fèi)的變化為3- -1+2- -3=1。這個(gè)變化就是。這個(gè)變化就是x11的檢驗(yàn)數(shù)，故的檢驗(yàn)數(shù)，故 11=1B1B2B3B4產(chǎn)量產(chǎn)量A17

14、A24A39銷(xiāo)量銷(xiāo)量365631363124B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷(xiāo)量銷(xiāo)量36563136312-14B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷(xiāo)量銷(xiāo)量365631363121-14B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷(xiāo)量銷(xiāo)量365631363121-1124B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷(xiāo)量銷(xiāo)量365631363121-112104 檢驗(yàn)數(shù)中有負(fù)數(shù)，說(shuō)明原方案不是最優(yōu)解。檢驗(yàn)數(shù)中有負(fù)數(shù)，說(shuō)明原方案不是最優(yōu)解?？崭耖]回路檢驗(yàn)數(shù)(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32

15、)-(22)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-11012檢驗(yàn)數(shù)還存在檢驗(yàn)數(shù)還存在負(fù)數(shù)負(fù)數(shù), 原方案不是最優(yōu)方案原方案不是最優(yōu)方案. 用閉回路求解檢驗(yàn)數(shù)時(shí),需要給每一個(gè)空格找一條閉回路.當(dāng)產(chǎn)銷(xiāo)點(diǎn)較多時(shí),該方法較麻煩.ui,vj自由變量自由變量（2） 位勢(shì)法位勢(shì)法標(biāo)準(zhǔn)型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題是：標(biāo)準(zhǔn)型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題是： njjjmiiivbuamax11 )n,j;m,i (cvuijji11

16、XBXNXS0CN-CBB-1N-CBB-1-YS1-YS2-Y檢驗(yàn)數(shù)檢驗(yàn)數(shù)對(duì)偶變量值等于對(duì)偶變量值等于原問(wèn)題的檢驗(yàn)數(shù)原問(wèn)題的檢驗(yàn)數(shù)松弛變量松弛變量11212( ,.,. )()ijijBijijijijmnijijijcC B PcYPcu uuv vv Pcuvij()ijijijcuv 基變量的檢驗(yàn)數(shù)為零基變量的檢驗(yàn)數(shù)為零( 基變量基變量xij)，()0ijijijcuv得得m+n- -1個(gè)方程個(gè)方程,含含m+n個(gè)未知數(shù)個(gè)未知數(shù), 令某個(gè)令某個(gè)ui ( 或或vj)=0,可解出可解出m+n個(gè)個(gè)ui 和和vj;由此得非基變量的檢驗(yàn)由此得非基變量的檢驗(yàn)數(shù)數(shù).()ijijijcuv 1.由基變量

17、的檢驗(yàn)數(shù)為0, ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj 2. 利用 ij=cij-(ui+vj),求非基變量的檢驗(yàn)數(shù) 可令任意的行或列的位勢(shì)為可令任意的行或列的位勢(shì)為0 (任意值均任意值均可可,為為0出于計(jì)算簡(jiǎn)單考慮出于計(jì)算簡(jiǎn)單考慮)銷(xiāo)銷(xiāo) 產(chǎn)產(chǎn) B1 B2 B3 B4 產(chǎn)產(chǎn)量量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 銷(xiāo)銷(xiāo)量量 3 6 5 6 314 633位勢(shì)法位勢(shì)法 令令v1=0, 由由c21=1= u2 +v1，得得 u2=1B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2

18、0 1 1 28-3 7位勢(shì)表位勢(shì)表2989-3-2)(jiijijvuc檢驗(yàn)數(shù)檢驗(yàn)數(shù)B1B2B3B4ui311310A11928A274105A3vj 0 1 1 28-3 7檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表121-11012 24=-10，當(dāng)前方案，當(dāng)前方案 不是最優(yōu)方案。不是最優(yōu)方案。 1. 以以最小負(fù)檢驗(yàn)數(shù)最小負(fù)檢驗(yàn)數(shù)為出發(fā)點(diǎn)尋找一條閉回路為出發(fā)點(diǎn)尋找一條閉回路. 2. 確定調(diào)整量確定調(diào)整量,調(diào)出格中調(diào)出格中最小最小的運(yùn)量的運(yùn)量.2.3 改進(jìn)的方法改進(jìn)的方法閉回路調(diào)整法閉回路調(diào)整法二、二、 調(diào)運(yùn)方案的調(diào)整調(diào)運(yùn)方案的調(diào)整pqijj , i)(min 0 xpq為換入變量為換入變量從從( (p,q) )空

19、格開(kāi)始畫(huà)閉回路空格開(kāi)始畫(huà)閉回路, ,其它轉(zhuǎn)角點(diǎn)都是填有運(yùn)其它轉(zhuǎn)角點(diǎn)都是填有運(yùn)量的方格量的方格, ,并從并從( (p,q) )空格開(kāi)始給閉回路上的點(diǎn)按空格開(kāi)始給閉回路上的點(diǎn)按+1+1,-1,+1,-1,-1,+1,-1編號(hào)，編號(hào)，-1-1格的最小運(yùn)量格的最小運(yùn)量為調(diào)整量為調(diào)整量. .換出換出變量變量銷(xiāo)銷(xiāo)地地 產(chǎn)產(chǎn)地地 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 A1 A2 A3 3 6 4(+1) 1(- -1) 3(- -1) (+1) 3 7 4 9 銷(xiāo)銷(xiāo)量量 3 6 5 6 運(yùn)價(jià)運(yùn)價(jià)B1B2B3B4產(chǎn)量A1527A2314A3639銷(xiāo)量3656新的調(diào)運(yùn)方案為：新的調(diào)運(yùn)方案為：851186zz2401

20、或者直接算或者直接算 需供B1B2B3B4uiA10210A2218A39125Vj -7-1-70713491110231085運(yùn)輸問(wèn)題的求解表上作業(yè)法步驟小結(jié)運(yùn)輸問(wèn)題的求解表上作業(yè)法步驟小結(jié)第一步第一步: :確定初始基可行解（可行調(diào)運(yùn)方案）確定初始基可行解（可行調(diào)運(yùn)方案） 方法：最小元素法與伏格爾法方法：最小元素法與伏格爾法第二步第二步: :判別當(dāng)前可行方案是否最優(yōu)判別當(dāng)前可行方案是否最優(yōu) 方法：閉回路法與位勢(shì)法方法：閉回路法與位勢(shì)法第三步第三步: :對(duì)現(xiàn)有方案進(jìn)行調(diào)整對(duì)現(xiàn)有方案進(jìn)行調(diào)整 方法：閉回路法方法：閉回路法3.2.4 表表上上作業(yè)法計(jì)算中的問(wèn)題作業(yè)法計(jì)算中的問(wèn)題無(wú)窮多最優(yōu)解無(wú)窮多

21、最優(yōu)解 某非基變量某非基變量(空格空格)的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為0.退化退化方案點(diǎn)數(shù)方案點(diǎn)數(shù)=產(chǎn)地?cái)?shù)產(chǎn)地?cái)?shù)+銷(xiāo)地?cái)?shù)銷(xiāo)地?cái)?shù)1;同時(shí)去掉一行和一列時(shí)應(yīng)添加同時(shí)去掉一行和一列時(shí)應(yīng)添加0方案方案;調(diào)整時(shí)出現(xiàn)兩個(gè)或兩個(gè)以上的最小值調(diào)整時(shí)出現(xiàn)兩個(gè)或兩個(gè)以上的最小值,新方案中也要添加新方案中也要添加0方案方案. . .無(wú)窮多最優(yōu)解：無(wú)窮多最優(yōu)解：產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解優(yōu)解. .如果非基變量的如果非基變量的ij0, 則該問(wèn)題有無(wú)窮多最優(yōu)則該問(wèn)題有無(wú)窮多最優(yōu)解解. 如上例如上例: (1.1) 中的檢驗(yàn)數(shù)是中的檢驗(yàn)數(shù)是 0, 經(jīng)過(guò)調(diào)整經(jīng)過(guò)調(diào)整, 可得到另可得到另一個(gè)最優(yōu)解一個(gè)最優(yōu)解.

22、 4、表上作業(yè)法計(jì)算中的問(wèn)題、表上作業(yè)法計(jì)算中的問(wèn)題 .退化退化: 表格中一般要有表格中一般要有(m+n-1)個(gè)數(shù)字格個(gè)數(shù)字格.但有時(shí)但有時(shí), 在分配運(yùn)量時(shí)則需要同時(shí)劃去一在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列行和一列, 這時(shí)需要補(bǔ)一個(gè)這時(shí)需要補(bǔ)一個(gè)0, 以保證有以保證有(m+n-1)個(gè)數(shù)字格個(gè)數(shù)字格. 一般可在劃去的行和列一般可在劃去的行和列的任意空格處加一個(gè)的任意空格處加一個(gè) 0 即可即可. 正常時(shí)一次只劃掉同時(shí)劃掉了一行和一列 此時(shí)同時(shí)劃掉一行和一列, 不要補(bǔ)零例例1：B1B2B3B4A178143A226355A31427821762 1 3 5 5 2 6 82 1 7 6 例例2：B

23、1B2B3A11221A23132A32314124B1B2B3A111A222A34412400 04 運(yùn)輸問(wèn)題的擴(kuò)展運(yùn)輸問(wèn)題的擴(kuò)展本本節(jié)節(jié)重重點(diǎn)點(diǎn)供需不平衡的運(yùn)輸問(wèn)題供需不平衡的運(yùn)輸問(wèn)題供不應(yīng)求供不應(yīng)求供過(guò)于求供過(guò)于求轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題運(yùn)輸問(wèn)題的分類(lèi)運(yùn)輸問(wèn)題的分類(lèi)產(chǎn)銷(xiāo)產(chǎn)銷(xiāo)平衡平衡問(wèn)題：?jiǎn)栴}：ai=bj產(chǎn)銷(xiāo)產(chǎn)銷(xiāo)不平衡不平衡問(wèn)題：?jiǎn)栴}：產(chǎn)大于銷(xiāo)：產(chǎn)大于銷(xiāo)：ai bj產(chǎn)小于銷(xiāo)：產(chǎn)小于銷(xiāo)：ai 產(chǎn)量產(chǎn)量二、轉(zhuǎn)運(yùn)問(wèn)題二、轉(zhuǎn)運(yùn)問(wèn)題出現(xiàn)下列問(wèn)題：出現(xiàn)下列問(wèn)題：1. 產(chǎn)地與銷(xiāo)地之間沒(méi)有直達(dá)路線，貨物由產(chǎn)地到銷(xiāo)產(chǎn)地與銷(xiāo)地之間沒(méi)有直達(dá)路線，貨物由產(chǎn)地到銷(xiāo)地必須通過(guò)中轉(zhuǎn)站轉(zhuǎn)運(yùn)；地必須通過(guò)中轉(zhuǎn)站轉(zhuǎn)運(yùn)；2. 某些產(chǎn)地

24、可以輸入貨物，銷(xiāo)地也可以輸出貨物，某些產(chǎn)地可以輸入貨物，銷(xiāo)地也可以輸出貨物，3. 產(chǎn)地與銷(xiāo)地之間雖然有直達(dá)運(yùn)輸線，但直達(dá)運(yùn)輸產(chǎn)地與銷(xiāo)地之間雖然有直達(dá)運(yùn)輸線，但直達(dá)運(yùn)輸?shù)馁M(fèi)用（距離）比經(jīng)過(guò)某些中轉(zhuǎn)站的還要高。的費(fèi)用（距離）比經(jīng)過(guò)某些中轉(zhuǎn)站的還要高。解法：解法：無(wú)轉(zhuǎn)運(yùn)問(wèn)題。無(wú)轉(zhuǎn)運(yùn)問(wèn)題。1. 根據(jù)問(wèn)題求出最大可能周轉(zhuǎn)量根據(jù)問(wèn)題求出最大可能周轉(zhuǎn)量Q；2. 純轉(zhuǎn)運(yùn)點(diǎn)純轉(zhuǎn)運(yùn)點(diǎn)產(chǎn)地：輸出量產(chǎn)地：輸出量Q；銷(xiāo)地：輸入量銷(xiāo)地：輸入量Q；輸入輸入=輸出輸出3. 兼中轉(zhuǎn)站的產(chǎn)地兼中轉(zhuǎn)站的產(chǎn)地Ai=銷(xiāo)銷(xiāo)地：輸入量地：輸入量Q；產(chǎn)地：輸出量產(chǎn)地：輸出量Q+ai；4. 兼中轉(zhuǎn)站的銷(xiāo)地兼中轉(zhuǎn)站的銷(xiāo)地Bj=銷(xiāo)銷(xiāo)地：輸入量地：

25、輸入量bj+Q；產(chǎn)地：輸出量產(chǎn)地：輸出量Q；列出各產(chǎn)地的輸出量和各銷(xiāo)地的輸入量及各產(chǎn)列出各產(chǎn)地的輸出量和各銷(xiāo)地的輸入量及各產(chǎn)銷(xiāo)地之間的運(yùn)價(jià)表銷(xiāo)地之間的運(yùn)價(jià)表, 用表上作業(yè)法求解用表上作業(yè)法求解.輸出：產(chǎn)地；中轉(zhuǎn)站輸出：產(chǎn)地；中轉(zhuǎn)站(純純/兼兼)輸入：銷(xiāo)地；中轉(zhuǎn)站輸入：銷(xiāo)地；中轉(zhuǎn)站(純純/兼兼)例例 某貨物某貨物, 其產(chǎn)地其產(chǎn)地A1的產(chǎn)量為的產(chǎn)量為10單位單位,A2的產(chǎn)量為的產(chǎn)量為2單位單位, 銷(xiāo)地銷(xiāo)地A3、A4、A5的銷(xiāo)量分別為的銷(xiāo)量分別為3單位、單位、1單位和單位和8單位單位, 其中產(chǎn)地其中產(chǎn)地A2、銷(xiāo)、銷(xiāo)A4又可作為中轉(zhuǎn)站又可作為中轉(zhuǎn)站. 同時(shí)同時(shí), 貨貨物可通過(guò)純中轉(zhuǎn)站物可通過(guò)純中轉(zhuǎn)站A

26、6進(jìn)行運(yùn)輸進(jìn)行運(yùn)輸. 各產(chǎn)地、銷(xiāo)地及中轉(zhuǎn)各產(chǎn)地、銷(xiāo)地及中轉(zhuǎn)站之間的單位物資運(yùn)價(jià)如表所示站之間的單位物資運(yùn)價(jià)如表所示, 試求一個(gè)使總運(yùn)費(fèi)試求一個(gè)使總運(yùn)費(fèi)最省的調(diào)運(yùn)方案最省的調(diào)運(yùn)方案. 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地A2A3A4A5A6A126312A2 03M24A4M2031A613270最大可能周轉(zhuǎn)量最大可能周轉(zhuǎn)量 Q=a1+a2=10+2=12A1 純產(chǎn)地純產(chǎn)地, 輸出量輸出量10;A2產(chǎn)地兼中轉(zhuǎn)站產(chǎn)地兼中轉(zhuǎn)站,輸出量輸出量2+12=14,輸入量輸入量12;A3 純銷(xiāo)地純銷(xiāo)地, 輸入量輸入量3;A4銷(xiāo)地兼中轉(zhuǎn)站銷(xiāo)地兼中轉(zhuǎn)站,輸出量輸出量12,輸入量輸入量1+12=13;A5純銷(xiāo)地純銷(xiāo)地,輸入量輸入量8;

27、A6純中轉(zhuǎn)站純中轉(zhuǎn)站,輸出量、輸入量均為輸出量、輸入量均為12.根據(jù)以上情況列產(chǎn)銷(xiāo)平衡表根據(jù)以上情況列產(chǎn)銷(xiāo)平衡表. 銷(xiāo)地產(chǎn)地A2A3A4A5A6輸出量A12631210A203M2414A4M203112A61327012輸入量1231381248 銷(xiāo)地產(chǎn)地A2A3A4A5A6輸出量A118110A212214A41212A611112輸入量1231381248不參加實(shí)際調(diào)運(yùn)不參加實(shí)際調(diào)運(yùn)3.4 應(yīng)用舉例應(yīng)用舉例搞清搞清“產(chǎn)地、銷(xiāo)地產(chǎn)地、銷(xiāo)地”、“運(yùn)價(jià)運(yùn)價(jià)”, “產(chǎn)量、需求產(chǎn)量、需求”, 寫(xiě)出寫(xiě)出產(chǎn)銷(xiāo)平衡產(chǎn)銷(xiāo)平衡表表運(yùn)輸問(wèn)題的要素運(yùn)輸問(wèn)題的要素:未知數(shù)未知數(shù)如何設(shè)如何設(shè)虛設(shè)虛設(shè)產(chǎn)地與銷(xiāo)地產(chǎn)地與

28、銷(xiāo)地;拆分拆分產(chǎn)地與銷(xiāo)地產(chǎn)地與銷(xiāo)地例例 3. 某廠按合同規(guī)定須于每個(gè)季度末分別提供某廠按合同規(guī)定須于每個(gè)季度末分別提供10,15,25,20臺(tái)同一規(guī)格的柴油機(jī)臺(tái)同一規(guī)格的柴油機(jī).已知該廠各季度已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如下表的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如下表.如果如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨,每臺(tái)積壓一個(gè)季度每臺(tái)積壓一個(gè)季度需儲(chǔ)存、維護(hù)費(fèi)用需儲(chǔ)存、維護(hù)費(fèi)用0.15萬(wàn)元萬(wàn)元.要求在完成合同的情要求在完成合同的情況下況下,做出該廠全年費(fèi)用最小的決策做出該廠全年費(fèi)用最小的決策.季度季度生產(chǎn)能力生產(chǎn)能力單位成本單位成本IIIIIIIV25353010

29、10.811.111.011.3搞清搞清“產(chǎn)地、銷(xiāo)地產(chǎn)地、銷(xiāo)地”、“運(yùn)價(jià)運(yùn)價(jià)”, “產(chǎn)量、需求產(chǎn)量、需求”, 寫(xiě)出寫(xiě)出產(chǎn)銷(xiāo)平衡產(chǎn)銷(xiāo)平衡表表未知數(shù)未知數(shù)如何設(shè)如何設(shè)設(shè)設(shè)xij為第為第i季度生產(chǎn)的用于第季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù)季度交貨的柴油機(jī)數(shù).合同要求：合同要求：11122213233314243444 10 15 2520 xxxxxxxxxx產(chǎn)量約束：產(chǎn)量約束：1112131422232433344425 35 30 10 xxxxxxxxxx第第i季度生產(chǎn)的用于第季度生產(chǎn)的用于第j季度交貨的柴油機(jī)的實(shí)際成本季度交貨的柴油機(jī)的實(shí)際成本cij=生產(chǎn)成本生產(chǎn)成本+儲(chǔ)存維護(hù)費(fèi)用儲(chǔ)存維護(hù)

30、費(fèi)用ijIIIIIIIVIIIIIIIV10.810.9511.1011.1011.2511.0011.2511.4011.1511.3044114141m in. .0ijijijijijijjiijzc xxas txbx ijIIIIIIIV產(chǎn)量產(chǎn)量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3025353010銷(xiāo)量銷(xiāo)量10152520ijIIIIIIIVD產(chǎn)量產(chǎn)量IIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.3000002535301

31、0銷(xiāo)量銷(xiāo)量1015252030 例: 某玩具公司分別生產(chǎn)三種新型的玩具, 每月可供應(yīng)量分別為1000件, 2000件,2000件，他們分別被送到甲乙丙三個(gè)百貨商店銷(xiāo)售, 已知每月百貨商店各類(lèi)玩具預(yù)期銷(xiāo)售量為1500件, 由于經(jīng)營(yíng)原因, 各百貨商店銷(xiāo)售不同玩具的盈利額不同, 又知丙百貨商店要求至少供應(yīng)C玩具1000件, 而拒絕進(jìn)入A種玩具, 求滿足上述條件下使總盈利額為最大的供銷(xiāo)分配方案.甲乙丙可供量ABC516124810-911100020002000C先滿足丙1000件甲乙丙丁可供量ABC516124810-91100010002000100015001500500500甲乙丙丁可供量AB

32、C11041286M7500010002000100015001500500500 已知某運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表, 最優(yōu)調(diào)運(yùn)方案及單位運(yùn)價(jià)表分別如表所示, 由于從產(chǎn)地2至銷(xiāo)地B的道路因故暫時(shí)封閉, 故需對(duì)調(diào)運(yùn)方案進(jìn)行修正,試用盡可能簡(jiǎn)單的方法重新找出最優(yōu)調(diào)運(yùn)方案.ABCDE產(chǎn)量1233414513948銷(xiāo)量35463ABCDE1231021201020510793010106410變?yōu)樽優(yōu)镸, 計(jì)算檢驗(yàn)數(shù)進(jìn)行調(diào)整計(jì)算檢驗(yàn)數(shù)進(jìn)行調(diào)整 已知某運(yùn)輸問(wèn)題的資料如下表所示已知某運(yùn)輸問(wèn)題的資料如下表所示B1B2B3B4發(fā)量發(fā)量A1265315A2132112A3327413收量收量1013125 1、表中的

33、發(fā)量、收量單位為：噸，運(yùn)價(jià)單位為：元、表中的發(fā)量、收量單位為：噸，運(yùn)價(jià)單位為：元/ /噸噸 試求出最優(yōu)運(yùn)輸方案試求出最優(yōu)運(yùn)輸方案. . 練習(xí)：練習(xí)： 2、如將、如將A2的發(fā)量改為的發(fā)量改為1717，其它資料不變，試求最優(yōu)調(diào)，其它資料不變，試求最優(yōu)調(diào) 運(yùn)方案。運(yùn)方案。13A312A2510A1B4B3B2B1最終的運(yùn)送方案最終的運(yùn)送方案總的運(yùn)費(fèi)總的運(yùn)費(fèi) 85元元/噸噸 已知資料如下表所示，問(wèn)如何供電能使總的輸電費(fèi)已知資料如下表所示，問(wèn)如何供電能使總的輸電費(fèi)用為最??？用為最??？發(fā)電廠 發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表電力供需表B1B2B3B4A110523A24312A35634單位輸電費(fèi)用單位輸電費(fèi)用作業(yè)：作業(yè)：B1B2B3B4ui A1105230A24-1-4-3-6A350-3-2-5vj 10523 (ui+vj) B1B2B3B4ui A10000A20455A30666vj ij- (ui+vj)