第二章運(yùn)籌學(xué)運(yùn)輸問(wèn)題

1、,,第二章 運(yùn)輸問(wèn)題,產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題的數(shù)學(xué)模型表上作業(yè)法產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其應(yīng)用,教學(xué)目的與要求：使學(xué)生學(xué)會(huì)建模方法能用表上作業(yè)法及WinQSB求解運(yùn)輸問(wèn)題。重點(diǎn)與難點(diǎn)：重點(diǎn)是產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的表上作業(yè)法，難點(diǎn)是基變量個(gè)數(shù)為m+n-1的理論及操作方法.教學(xué)方法:課堂講授并輔以課件及軟件.思考題,討論題,作業(yè):教材中第三章作業(yè).參考資料:見(jiàn)前言學(xué)時(shí)分配:4學(xué)時(shí).,第二章 運(yùn)輸問(wèn)題(Transportation

2、problems),物資調(diào)運(yùn)是一個(gè)典型的線(xiàn)性規(guī)劃問(wèn)題.1939年前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出這一問(wèn)題,1941年美國(guó)數(shù)學(xué)家F.L.Hitchcock提出運(yùn)輸問(wèn)題數(shù)學(xué)模型,1951年Dantzig將此類(lèi)問(wèn)題的解法系統(tǒng)化,完善化,改為用表上作業(yè)法求解.,第一節(jié) 運(yùn)輸問(wèn)題數(shù)學(xué)模型,一.平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型,,,平衡表,建立數(shù)學(xué)模型,平衡運(yùn)輸問(wèn)題數(shù)學(xué)模型的矩陣表示法,定理1 在產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題中,其約束方程組的系數(shù)矩陣和增廣矩陣的秩相等

3、,且等于m+n-1.,定理2 方程組 有解的充要條件是,證明:必要性,充分性,定理3 平衡的運(yùn)輸問(wèn)題一定有最優(yōu)解.,證明:,1.編制初始調(diào)運(yùn)方案,方法一:最小元素法(Minimal elements method),在平衡表中,按運(yùn)價(jià)最小者優(yōu)先滿(mǎn)足的原則,找出m+n-1個(gè)有數(shù)字的格為基變量,空格為非基變量.,方法二:西北角法(Northwest corner method),注意:一般來(lái)說(shuō)用最小元素法得到的初始調(diào)運(yùn)方

4、案更接近于最優(yōu)方案.,二. 運(yùn)輸問(wèn)題的表上作業(yè)法,例1 見(jiàn)下表:,,,,,,,,,,,,,,,,,,,,2. 最優(yōu)方案的判別,方法一:閉回路法,閉回路:從非基變量格出發(fā),沿水平或垂直方向前進(jìn),碰到適當(dāng)?shù)幕兞扛褶D(zhuǎn)向,再回到原來(lái)的空格,稱(chēng)為一個(gè)閉回路.在閉回路上的基變量格稱(chēng)為轉(zhuǎn)角點(diǎn).可以證明,如果不考慮方向,則每一個(gè)空格的閉回路唯一存在.,找出上例中各空格的閉回路,,,,,,,,,,,,,,,,,,,收,每個(gè)空格即非基變量的檢驗(yàn)數(shù)的求法:

5、,注意:1.空格為第0次轉(zhuǎn)角.2.當(dāng)?shù)谝淮纬霈F(xiàn)正檢驗(yàn)數(shù)時(shí),可停止以下檢驗(yàn)數(shù)的計(jì)算.,調(diào)運(yùn)方案的判優(yōu)準(zhǔn)則:對(duì)調(diào)運(yùn)方案表中的每一空格作一條閉回路,并求出檢驗(yàn)數(shù),如果檢驗(yàn)數(shù)全部小于等于零,則該調(diào)運(yùn)方案最優(yōu).否則要調(diào)整調(diào)運(yùn)方案.,3. 方案的調(diào)整,⑴ 選取入基變量:第一個(gè)正檢驗(yàn)數(shù)的空格對(duì)應(yīng)的非基變量為入基變量.本例中 為入基變量.,⑵ 入基變量的取值為θ,θ=min{奇轉(zhuǎn)角點(diǎn)運(yùn)量}.即該非基變量的運(yùn)量為θ,同時(shí)變?yōu)榛兞?,⑶ 出基變量的

6、選擇:在此閉回路上和奇轉(zhuǎn)角點(diǎn)上最小運(yùn)量對(duì)應(yīng)的基變量變?yōu)榱?該變量是出基變量,在新方案中它的位置是空格.,⑷ 在該閉回路中按奇,偶點(diǎn)進(jìn)行運(yùn)量的平衡調(diào)整,得一新的調(diào)運(yùn)方案.,⑸ 對(duì)新方案判優(yōu),調(diào)整,直到求出最優(yōu)方案.,收,,,,,,,,收,,第一次調(diào)整后的新方案,經(jīng)過(guò)四次迭代得到最優(yōu)方案如下,總運(yùn)費(fèi)為85.,收,,方法二:乘數(shù)法 (位勢(shì)法),收,,令第一,二,三行的乘數(shù)分別為,令第一,二,三,四列的乘數(shù)分別為,且有,寫(xiě)出基變量的乘數(shù)方程:,

7、該乘數(shù)方程有六個(gè)方程,七個(gè)未知數(shù),一定有解,且有無(wú)窮多解.可令 得出一組解.,由這組解按下面的公式求空格(非基變量的檢驗(yàn)數(shù):,與閉回路法求得的檢驗(yàn)數(shù)完全相同.,注意:,⒈ 要保證調(diào)運(yùn)平衡表中填有數(shù)字的格數(shù)為 m+n-1,且不構(gòu)成閉回路。,若 填上調(diào)運(yùn)量后,第i行發(fā)量及第j列銷(xiāo)量都已滿(mǎn)足,則在運(yùn)價(jià)表中只允許劃去第i行與第j列中的一個(gè),而不允許將它們?nèi)珓澣? 此后,當(dāng)運(yùn)價(jià) 或 最

8、小時(shí),要在 或 的格子上填寫(xiě)0,它表示一個(gè)基變量,這屬于LP中退化的情形.,收,,請(qǐng)看下面的例子:,,第三行,第二列任選一個(gè),,,,,,,,,,,,,,,,2. 對(duì)于有的運(yùn)輸問(wèn)題,最優(yōu)調(diào)運(yùn)方案不止一個(gè).,二.產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題,解決方法:增加一個(gè)虛擬(Dummy)庫(kù)存點(diǎn)(銷(xiāo)地), 其庫(kù)存量為,再增加m個(gè)松弛變量,表示產(chǎn)地 在 處的庫(kù)存量.在運(yùn)價(jià)表中,相應(yīng)的運(yùn)價(jià) ,

9、但這個(gè)運(yùn)價(jià)不按最小元素處理.,經(jīng)過(guò)以上的處理,可將產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題變?yōu)楫a(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題.,例3,,,,將其改為產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題,并求出初始調(diào)運(yùn)方案,,,,,,,,,,,,,,,,,,,,,,對(duì)于產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題中產(chǎn)小于銷(xiāo)的情況,可在產(chǎn)銷(xiāo)平衡表中虛設(shè)一個(gè)產(chǎn)地,其產(chǎn)量為 ,到各地的運(yùn)價(jià)是一個(gè)充分大的正數(shù)M.變?yōu)楫a(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題.,此外還有帶中間轉(zhuǎn)運(yùn)站的運(yùn)輸問(wèn)題,詳細(xì)情況見(jiàn)p98例4.,使用Wi

10、nQSB求解運(yùn)輸問(wèn)題.,產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題實(shí)例:,某研究院有 三個(gè)區(qū)。每年取暖分別需要用煤3500噸，1100噸，2400噸，這些煤都要由 煤礦 供應(yīng)，價(jià)格，質(zhì)量均相同。 煤礦的供應(yīng)能力分別為1500噸，4000噸，運(yùn)價(jià)如下表所示。由于需求大于供應(yīng)，經(jīng)研究決定：區(qū)供應(yīng)量可減少0—900噸， 區(qū)必須滿(mǎn)足需求量， 區(qū)供應(yīng)量不少于1600噸

11、，試求總費(fèi)用最低的調(diào)運(yùn)方案。,解：這是一個(gè)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題，需求量大于供應(yīng)量。處理辦法是，將 區(qū)和 區(qū)分別設(shè)為兩個(gè)區(qū)：一個(gè)是必須滿(mǎn)足需求量的區(qū)，另一個(gè)是可以調(diào)整供應(yīng)量的區(qū)。同時(shí)增加一個(gè)虛設(shè)的產(chǎn)地 ，其供應(yīng)量為1500噸，同時(shí)在運(yùn)價(jià)表中，取M表示一個(gè)很大的正數(shù)，使必須滿(mǎn)足需求量的區(qū)域的運(yùn)價(jià)取值為M，可調(diào)整需求量的區(qū)域的運(yùn)價(jià)取值為0。（為什么？）這樣，原問(wèn)題變?yōu)橛形鍌€(gè)需求點(diǎn)，三個(gè)供應(yīng)點(diǎn)的產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。新平衡表