第二章運籌學運輸問題

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

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

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

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

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

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

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

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

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

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

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