運籌學(xué)運輸問題-2.ppt

1、1、回顧、運輸問題數(shù)學(xué)模型及其特征運輸問題解法表操作法(兩個表：產(chǎn)銷平衡表、單位運輸價格表)表操作法中初始化學(xué)基可行解的確定方法：最小元素法Vogel法(最大差額法)閉合回路的建立和閉合回路法檢驗數(shù)，2，1，運輸問題數(shù)學(xué)模型，3，2， 用最小元素法確定初始化學(xué)基可行解的步驟，步驟1 :確定第一個化學(xué)基變量法的方法： (1)從單位價目表中找到最小運費價；(2)在最小運費價中，用所在行的生產(chǎn)量最大限度地滿足銷售量(所在列)的需求。 (3)觀察生產(chǎn)和銷售的關(guān)系：1)如果生產(chǎn)量沒有了，刪除該行的單位運價信息如果銷售量達到滿腳丫子，就刪除該列的單位運價信息。 (注意產(chǎn)量和銷售量的變化)步驟2 :確定第二

2、個基本變量的方法：在剩馀的單位運價信息中找到最小值。 用上述方法操作。4、3、博爾格爾法(Vogel )確定了初期化學(xué)基可行解的主旨：以最大差額，優(yōu)先以最小運費價運送。 第一步：與單位價目表同行，計算同列的最小運輸費和子運輸費的差，分別列在單位價目表的最右列和最下行(行差和列差)。 步驟2 :比較行差和列差，找出最大的差。 如果相對于與最大差額值相同的列中的最小運費價格傾斜所屬行的產(chǎn)量，并且完全滿足所屬列的需求(或庫存) (或調(diào)整庫存)，則系統(tǒng)將清除該列(或行)中的所有運費價格信息。 (注意產(chǎn)量和銷售量的變化)第三步：重新計算同行的最小運輸費和子運輸費的差，對其他撥號值未確定的矩陣，重復(fù)第二步

3、的處理，直到構(gòu)成某個初始撥號計劃(初始解)。 5，4，最優(yōu)性檢驗的核心思想，1，最優(yōu)性檢驗判斷思路：在確定初始化學(xué)基可行解后，考察非化學(xué)基變量數(shù)值變化對總運輸費的影響。 2、實現(xiàn)方法：根據(jù)確定的初始化學(xué)基的可行解，當(dāng)非化學(xué)基變量取值時，考慮總運輸費的變化情況；(1)證明所有情況下總費用都增加，則最合適；(2)當(dāng)總費用出現(xiàn)減少時，代表對該非基本變量安排運輸量更好，第一個方案是3、需要解決的問題：當(dāng)非基變量取值時，為了保證生產(chǎn)銷售平衡表的生產(chǎn)銷售平衡，會引起確定的基變量的連鎖變化，導(dǎo)致相應(yīng)行和列的基變量的變動。 有必要用閉環(huán)法確定基變量的變動情況。 (1)閉合電路：調(diào)音方案中，由具有一個空格(非基

4、本變量)和幾個數(shù)字格(基本變量)的水平和垂直線構(gòu)成的電路。 (3)閉合回路的構(gòu)造方法：從選擇的空間(非基底變量)向水平或鉛直方向前進，僅以途中的有數(shù)字格(基底變量)為拐點，確實轉(zhuǎn)向直到返回到出發(fā)的空間(非基底變量)。 7、閉路形式、8、6、利用閉路法計算非化學(xué)基變量檢驗常數(shù)的方法，1 )參考產(chǎn)銷平衡表，制作非化學(xué)基變量檢驗常數(shù)表，填寫各非化學(xué)基變量檢驗常數(shù)2 )根據(jù)確定的初始(或之前可能的)運轉(zhuǎn)計劃表，查找各非基底變量的閉環(huán)3 )各非基底變量4 )利用單位運費表中與閉路對應(yīng)的運費信息，計算運費的變化狀況(非基底變量的單位運費-奇數(shù)位置的基底變量的單位運費在雙位數(shù)位置的基底變量的單位運費)是非基

5、底變量檢常數(shù)5 )將非基底變量檢常數(shù)記入檢常數(shù)表的相應(yīng)位置。 9、閉環(huán)法的非基底變量檢測數(shù)的計算方法、A1B1非基底變量： A1B1、A1B3-1、A2B3 1、A2B1-1 .運輸費的影響：3-3 2-1=10 (即該非基底變量的檢測數(shù))。、A2B2非化學(xué)基變量： A2B2 1、A2B3-1、A1B3 1、A1B4-1、A3B4 1、A3B2-1.運輸費的影響：9-2 3-10 5-4=10。 非化學(xué)基變量4:A2B4-1、a1b4-1、A1B3-1、A2B3 1。 受運輸費的影響：8-10 3-2=-10。 10、非化學(xué)基變量檢測常數(shù)表、非化學(xué)基變量A2B4的檢測常數(shù)小于0，表示通過對A2

6、B4安排運輸量，如何調(diào)整更低的運輸費，11、7、問題是對各個非基本變量反復(fù)搜索閉環(huán)，計算“非基本變量1”時的總運輸費檢查數(shù)為0時，原初期方案和改善方案如何證明調(diào)用基變量不是最合適的？ 用電位法一次計算所有的檢查數(shù)，分配給檢查數(shù)為0的非基底變量，越大越好。 但是，必須考慮生產(chǎn)銷售平衡的問題。 利用12、8、運輸問題的鑒定法2位電勢法、行電勢和列電勢2種數(shù)據(jù)，將檢驗數(shù)和單位運輸價格結(jié)合起來，得到13、檢驗數(shù)方程式、ij=cijavj、ui、vj行電勢列電勢、單位運輸價格、m產(chǎn)地、n據(jù)點時為m n個列電位，14，一般基變量的ij=0因此確定ui和vj可以由基變量的電位方程確定，ui vj=cij (

7、與基變量對應(yīng)的單位運費)包括總共m n-1個方程，確定m n個未知數(shù)，通常是某個、15、a、用位勢法求檢驗數(shù)的步驟，第一步驟：根據(jù)用最小元素法或Vogel法決定的初期運輸量表，將化學(xué)基變量(或運輸量)數(shù)據(jù)置換為與之對應(yīng)的單位運價表(或修正單位價目表，求出與基本變量對應(yīng)的價格信息的右側(cè)表示行電位ui (I=1，2.m )，下側(cè)表示列電位VJ (j=1，2.n )的步驟3 :在與基本變量對應(yīng)的單位運輸價格中，ui vj=cij。 步驟4 :在與非基變量對應(yīng)的空間內(nèi)計算檢索常數(shù)ij=cij-(ui vj )，其中，若自由決定任意一個電位，則可以求出所有行和列的電位。 將檢查數(shù)記入檢查表的步驟5 :判

8、斷檢查數(shù)ij是否大于0，表示如果是那樣就好。 否則，必須調(diào)整基本變量。 步驟6 :基本變量的調(diào)整用閉回路法進行。16、初始運費表、化學(xué)基變量的單位運費價目表、步驟1 :化學(xué)基變量的單位運費價目表、單位運費價目表、b，例如p88、17、步驟2 :行電勢和列電勢的值、化學(xué)基變量的單位運費價目表、1 )關(guān)于化學(xué)基變量cij=ui vj； 2 )任意決定一個電位即可。 0，10，3，- 1，2，- 5，9，18，步驟3 :根據(jù)行二進制位電勢和列二進制位電勢計算非基底變量檢測常數(shù)，使用0，10，3，- 1，2，- 5，9，1 )非基底變量檢測常數(shù)為cij-(ui vj )； 2 )通過結(jié)合與非基底變量對

9、應(yīng)的單位運費，能夠計算所有非基底變量的檢驗常數(shù)。1、2、1、10、12、-1、19、初始調(diào)整表、7、9、2、1、1、5、0、9、2、5、1、4、11、例2、20、利用所確定的ui和vj值，將非基本變量的檢測常數(shù)與cij值一起進行計算，ij=cij (ui vj 2、1、1、5、14、-1、5、3、-4、22、確定1 )出現(xiàn)多個非基底變量檢測常數(shù)0時，選擇哪個非基底變量作為置換基底變量2 )如何決定變換基底變量？ 23、建構(gòu)閉合電路，如何調(diào)整7、9、2、1、1、5、14、-1、5、5、3、-4、特異點、特異點、雙位數(shù)點、基變量、非基變量、7、2、7、2、24、1、7、2、0、基變量？ 初始化學(xué)基

10、變量2、初始化學(xué)基變量3、初始化學(xué)基變量1、檢測常數(shù)0的非化學(xué)基變量，一般必須在閉合電路中進行調(diào)整。25、8、化學(xué)基變量的調(diào)整方法采用閉環(huán)法調(diào)整輸入化學(xué)基和輸出化學(xué)基變量，(生產(chǎn)銷售平衡時的運輸問題)、26、化學(xué)基變量的調(diào)整方法，1 )選擇負檢驗數(shù)中絕對值最大的空格(非化學(xué)基變量)，將其作為輸入化學(xué)基變量2 )從該空格中該閉回路是唯一的3 )在閉回路中，在該空間調(diào)整閉回路中的最小基礎(chǔ)變量的取值，以使所選空間中的運輸量盡可能地增加，并且將該非基礎(chǔ)變量變?yōu)榛A(chǔ)變量(被基礎(chǔ)變量替換)。原始的最小基礎(chǔ)變量成為非基礎(chǔ)變量，在新的運輸計劃中被清除(替換基礎(chǔ)變量)。 4 )閉路上的其他基變量進行相應(yīng)的調(diào)整，

11、保證產(chǎn)銷平衡，獲得新的運輸計劃；5 )繼續(xù)用位勢法進行檢驗，觀察檢驗數(shù)是否全部大于零。 出現(xiàn)負數(shù)時，用1)4)的方法進行基底變量的調(diào)整，直到所有的檢驗常數(shù)都為正。 27、化學(xué)基變量的調(diào)整例1、1、2、1、10、12、-1、檢查數(shù)、初始調(diào)整方案、28、化學(xué)基變量的調(diào)整方法、查找以檢查數(shù)為負的非化學(xué)基變量為起點的閉環(huán)的基底變量，將非基底變量作為基底變量：將閉環(huán)電路中最小的基底變量的運輸量調(diào)整為該非基底變量，調(diào)整量為mm 在使調(diào)整后的基變量成為非基變量的閉回路中，調(diào)整其他基變量，保證生產(chǎn)銷售的平衡。 獲得新的運輸計劃。1、0、2、5、29、初始調(diào)整方案(初始化學(xué)基可行解)、調(diào)整后的調(diào)整方案(優(yōu)化后的

12、化學(xué)基可行解)、運輸費： 86、運輸費： 85、30、檢驗常數(shù)表、優(yōu)化調(diào)整方案、31、雙位數(shù)點減少、特異點加算、7、9、2、1、1、5、14、-1、5、3、-4、特異點、特異點、雙位數(shù)點、0、6、3、1、32 8，運輸問題表作業(yè)法程序，33、9，生產(chǎn)大頭針不平衡問題，核心方法：將生產(chǎn)大頭針不平衡轉(zhuǎn)換為生產(chǎn)大頭針平衡情況，用表作業(yè)法求解。 (1)關(guān)于“生產(chǎn)銷售”的狀況，生產(chǎn)量溢出，可以將一個銷售地(庫存)虛擬化，將多馀的生產(chǎn)量運送到該銷售地，如果其銷售量是“生產(chǎn)-銷售”，則可以云同步，使該虛擬銷售地的單位運價為零(虛擬的生產(chǎn)量=“銷售-生產(chǎn)”作為虛擬產(chǎn)地的同時，該虛擬產(chǎn)地的單位運輸價格為0.34

13、，例1生產(chǎn)超過銷售量，35，解法：虛擬銷售地，銷售量作為生產(chǎn)銷售量的差。 b4=ai-bj=4該列單位的運費價格為0，成為生產(chǎn)銷售平衡的問題，36、例2的生產(chǎn)比大頭針小，37，解法：在虛擬的銷售地，如果將其銷售量的差b4=bj -ai=1，則該列的運費價格為0，這是生產(chǎn)銷售、38、39、10、運輸問題應(yīng)用、資源不足分配問題、40、必須滿足、最高和最低差額未必完全滿足。問題分析、一、產(chǎn)銷量問題。 產(chǎn)量160，最低需求110，最高需求是無限的，但根據(jù)現(xiàn)狀，最高市場總需求是210 (因為銷售地最多可以獲得60 )，是生產(chǎn)銷售的不平衡問題，2，如何轉(zhuǎn)換為生產(chǎn)銷售平衡的問題？ 增加虛擬產(chǎn)地。 3、將需求量化為兩個，一部分滿足最低需求，一部分滿足差額。 41、步驟1 :轉(zhuǎn)換生產(chǎn)銷售平衡問題，解：增設(shè)產(chǎn)地丁，其供給量為最大需求量供給量50，虛擬產(chǎn)地的運價如何確定，最小需求、最高需求與最低需求之差，42，m表示無限大的正數(shù)，最低需求表示無法從d產(chǎn)地供給。 第二步：確定虛擬產(chǎn)地的單位運價，原則：銷售點的最小需求必須得到滿足，但最高需求未必得到滿足。 最小銷量的滿腳丫子表示沒有來自虛擬產(chǎn)地。 m，m，m，