運籌學(xué)第三章3.1運輸問題模型與性質(zhì).pptVIP

第三章 特殊的線性規(guī)劃 運輸問題,& 模型及其特點 & 求解思路及相關(guān)理論 & 求解方法表上作業(yè)法 & 運輸問題的推廣 產(chǎn)銷不平衡的運輸問題 轉(zhuǎn)運問題,3.1 運輸問題模型與性質(zhì) 一、運輸問題的數(shù)學(xué)模型 1、 運輸問題的一般提法： 某種物資有若干產(chǎn)地和銷地，現(xiàn)在需要把這種物資從各個產(chǎn)地運到各個銷地，產(chǎn)量總數(shù)等于銷量總數(shù)。已知各產(chǎn)地的產(chǎn)量和各銷地的銷量以及各產(chǎn)地到各銷地的單位運價（或運距），問應(yīng)如何組織調(diào)運，才能使總運費（或總運輸量）最?。?單位根據(jù)具體問題選擇確定。,表3-1 有關(guān)信息,2、運輸問題的數(shù)學(xué)模型,設(shè)xij為從產(chǎn)地Ai運往銷地Bj的物資數(shù)量（i=1，m；j=1，n），由于從Ai運出的物資總量應(yīng)等于Ai的產(chǎn)量ai，因此xij應(yīng)滿足：,同理，運到Bj的物資總量應(yīng)該等于Bj的銷量bj，所以xij還應(yīng)滿足： 總運費為：,運輸問題的數(shù)學(xué)模型,（3-1）,二、運輸問題的特點與性質(zhì) 1約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu) 寫出式（3-1）的系數(shù)矩陣A，形式如下：, 矩陣的元素均為1或0； 每一列只有兩個元素為1，其余元素均為0； 列向量Pij =(0,，0，1，0，, 0, 1, 0, 0)T，其中兩個元素1分別處于第i行和第m+j行。 將該矩陣分塊，特點是：前m行構(gòu)成m個mn階矩陣，而且第k個矩陣只有第k行元素全為1，其余元素全為0（k=1，m）；后n行構(gòu)成m個n階單位陣。,2.運輸問題的基變量總數(shù)是m + n -1 寫出增廣矩陣,證明系數(shù)矩陣A及其增廣矩陣的秩都是m+n-1,前m行相加之和減去后n行相加之和結(jié)果是零向量，說明m+n個行向量線性相關(guān)，因此 的秩小于m+n； ？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 對應(yīng)的列交叉處元素構(gòu)成m+n-1階方陣D 非奇異； ？,可以證明：m+n個約束方程中的任意m+n-1個都是線性無關(guān)的。,定義3.1 凡是能排成 (3-4) 或 (3-5) 形式的變量集合稱為一個閉回路,并稱式中變量為該閉回路的頂點；其中 互不相同, 互不相同。,3. m+n-1個變量構(gòu)成基變量的充要條件是它們不構(gòu)成閉回路。,例3-1 設(shè)m=3，n=4，決策變量xij表示從產(chǎn)地Ai到銷地Bj的調(diào)運量，列表如下，給出閉回路 在表中的表示法用折線連接起來的頂點變量。,三、運輸問題的求解方法,1、單純形法（為什么？） 2、表上作業(yè)法 由于問題的特殊形式而采用的更簡潔、更方便的方法,3.2 運輸問題的表上作業(yè)法 一、表上作業(yè)法的基本思想是:先設(shè)法給出一個初始方案,然后根據(jù)確定的判別準則對初始方案進行檢查、調(diào)整、改進，直至求出最優(yōu)方案，如圖3-1所示。 表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡捷。,圖3-1 運輸問題求解思路圖,二、 初始方案的確定 1、作業(yè)表（產(chǎn)銷平衡表） 初始方案就是初始基本可行解。 將運輸問題的有關(guān)信息表和決策變量調(diào)運量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。 表3-3是兩個產(chǎn)地、三個銷地的運輸問題作業(yè)表。,表3-3 運輸問題作業(yè)表（產(chǎn)銷平衡表）,其中xij是決策變量，表示待確定的從第i個產(chǎn)地到第j個銷地的調(diào)運量，cij為從第i個產(chǎn)地到第j個銷地的單位運價或運距。 2、確定初始方案的步驟： （1）選擇一個xij，令xij= minai，bj=,將具體數(shù)值填入xij在表中的位置；,（2）調(diào)整產(chǎn)銷剩余數(shù)量：從ai和bj中分別減去xij的值，若ai-xij=0，則劃去產(chǎn)地Ai所在的行，即該產(chǎn)地產(chǎn)量已全部運出無剩余，而銷地Bj尚有需求缺口bj-ai；若bj-xij =0，則劃去銷地Bj所在的列，說明該銷地需求已得到滿足，而產(chǎn)地Ai尚有存余量ai-bj； （3）當(dāng)作業(yè)表中所有的行或列均被劃去，說明所有的產(chǎn)量均已運到各個銷地，需求全部滿足，xij的取值構(gòu)成初始方案。否則，在作業(yè)表剩余的格子中選擇下一個決策變量，返回步驟（2）。,按照上述步驟產(chǎn)生的一組變量必定不構(gòu)成閉回路，其取值非負，且總數(shù)是m+n-1個，因此構(gòu)成運輸問題的基本可行解。 對xij的選擇采用不同的規(guī)則就形成各種不同的方法，常用的方法有最小元素法和伏格爾法。 下面通過具體實例分別介紹。,3、舉例,例3-2 甲、乙兩個煤礦供應(yīng)A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸距離見表3-4，求使總運輸量最少的調(diào)運方案。,表3-4 例3-2有關(guān)信息表,例3-2 的數(shù)學(xué)模型,使用最小元素法求出初始方案 （1） 最小元素法 基本思想是“就近供應(yīng)” ： 即從單位運價表或運距表中的最小元素開始確定供銷關(guān)系，然后次小，一直到給出初始基可行解為止。,用最小元素法確定例3-2初始調(diào)運方案,150,100,100,100,100,100,100,得到初始調(diào)運方案為： x11=100，x13=100，x22=150，x23=100,最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費(運距)。,（2）伏格爾法,它的基本思想是： 考慮次小運費(運距)，這就有一個差額。因而對差額最大處，就應(yīng)當(dāng)采用最小運費(運距)調(diào)運。,找最大差額的最小運費,用伏格爾法確定例3-2初始調(diào)運方案,200,50,15,150,50,50,50,50,最小,次小,差額,得到初始調(diào)運方案為： x11=50，x12=150，x21=50，x23=200,三、最優(yōu)性檢驗,檢查當(dāng)前調(diào)運方案是不是最優(yōu)方案的過程就是最優(yōu)性檢驗。檢查的方法： 計算非基變量的檢驗數(shù) 未填上數(shù)值的格(空格) 空格的檢驗數(shù) 若全部大于等于零，則該方案就是最優(yōu)調(diào)運方案，否則就應(yīng)進行調(diào)整。,1、閉回路法 以確定初始調(diào)運方案的作業(yè)表為基礎(chǔ)，以一個非基變量作為起始頂點，尋求閉回路。 閉回路的特點： 除了起始頂點是非基變量外，其他頂點均為基變量（對應(yīng)著填上數(shù)值的格）。 可以證明，如果對閉回路的方向不加區(qū)別，對于每一個非基變量而言，以其為起點的閉回路存在且唯一。,約定:起始頂點為非基變量，記為偶數(shù)次頂點，其它頂點從1開始順次排列，那么，該非基變量xij的檢驗數(shù)：,現(xiàn)在，用最小元素法確定例3-2初始調(diào)運方案的基礎(chǔ)上，計算非基變量X12的檢驗數(shù) ：,= (閉回路上偶數(shù)次頂點運距或運價之和) (閉回路上奇數(shù)次頂點運距或運價之和),(3-6),例3-2初始調(diào)運方案中以X12(X21)為起點的閉回路,非基變量X12的檢驗數(shù)：,非基變量X21的檢驗數(shù)：,=（c12+c23）-（c13+c22） =70+75-(100+65) = -20，,=（c21+c13）-（c11+c23） =80+100-（90+75）=15。,經(jīng)濟含義 在保持產(chǎn)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標函數(shù)值的變化量。,2、位勢法,以例3-2初始調(diào)運方案為例，設(shè)置位勢變量 和 ，在初始調(diào)運方案表的基礎(chǔ)上增加一行和一列（見下頁表格）。 然后構(gòu)造下面的方程組：,（3-7）,例3-2初始調(diào)運方案位勢變量對應(yīng)表,方程組的特點： 方程個數(shù)是m+n-1=2+3-1=4個，位勢變量共有m+n=2+3=5個，通常稱ui為第i行的位勢，稱vj為第j列的位勢； 初始方案的每一個基變量xij對應(yīng)一個方程 -所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運距（或運價）：ui+vj=cij； 方程組恰有一個自由變量，可以證明方程組中任意一個變量均可取作自由變量。,給定自由變量一個值, 解方程組式(3-7)，即可求得位勢變量的一組值，根據(jù)式(3-6)結(jié)合方程組(3-7)，則計算非基變量xij檢驗數(shù)的公式 ij=cij-（ui+vj） （3-8）,在式(3-7)中, 令u1=0, 則可解得 v1=90, v3=100, u2=-25, v2=90， 12=c12-（u1+v2）=70-（0+90）= -20 21=c21-（u2+v1）=80-（-25+90）=15 與前面用閉回路法求得的結(jié)果相同。,四、方案調(diào)整 當(dāng)至少有一個非基變量的檢驗數(shù)是負值時，說明作業(yè)表上當(dāng)前的調(diào)運方案不是最優(yōu)的，應(yīng)進行調(diào)整。 若檢驗數(shù)ij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路, 并求出調(diào)整量:,上例中12=-20 ，畫出以x12為起始變量的閉回路,計算調(diào)整量：=Min（100，150）=100。 按照下面的方法調(diào)整調(diào)運量： 閉回路上：閉回路之外的變量調(diào)運量不變。 奇數(shù)次頂點的調(diào)運量減去， 偶數(shù)次頂點的調(diào)運量加上；,得到新的調(diào)運方案：,重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運方案.,結(jié) 果 最優(yōu)調(diào)運方案是： x11=50，x12=150，x21=50，x23=200 相應(yīng)的最小總運輸量為： Zmin=9050+70150+8050+75200 =34000（噸公里）,3.3運輸問題的推廣,一、產(chǎn)銷不平衡的運輸問題,增加虛擬銷地,增加虛擬產(chǎn)地,產(chǎn)銷平衡的運輸問題,對應(yīng)的運距（或運價） ？,二、轉(zhuǎn)運問題 特點: 調(diào)運的物資不是由產(chǎn)地直接運送到銷地，而是經(jīng)過若干中轉(zhuǎn)站送達。 求解思路：轉(zhuǎn)化成一個等價的產(chǎn)銷平衡運輸問題，再用表上作業(yè)法求出最優(yōu)調(diào)運方案。,如何轉(zhuǎn)化 ？,第一步，將產(chǎn)地、