運籌學 運輸問題.ppt

1、、2.5.1運輸問題的數(shù)學模型是從m個發(fā)送點向n個接收點發(fā)送某種貨物.發(fā)送點的發(fā)送量是接收點的接收量. 運送單位貨物的運費，如何安排最節(jié)約運費，問題的提出，表1的生產(chǎn)銷售平衡表，上述數(shù)據(jù)可以匯總到表中，如下：表2的單位運費價目表，運費問題的數(shù)學模型， 將xij代表作為從第I個產(chǎn)地向第j個銷售地輸送的物資的數(shù)量的系數(shù)矩陣如下：2.5.2表作業(yè)法、表作業(yè)法的基本構(gòu)想：確定初期采購案、最佳性檢查改善案、1確定初期采購案、輸送問題確定初期基可行解、求出輸送問題的初期采購案， 確定初始基可執(zhí)行解的方法有最小要素法和伏格爾法，【例2-1】某公司銷售甲產(chǎn)品，設置3個加工工廠A1、A2、A3，產(chǎn)品分別出廠到銷

2、售點B1、B2、B3、B4， 各工廠的日產(chǎn)量和各銷售點的日需求量以及從各工廠到各銷售點的運價如下表所示，表3-3、1 .最小元素法、3、1、4、6、3、(思想：附近供給)不能同時刪除行和列。 12，76，5，2，1，表3-5，z=85，1如果相同的最大差為2個以上，則可以取任意一個。 2其馀的一行或一列有空格，不能填寫數(shù)字刪除。 修正3行差、列差時，不考慮已經(jīng)刪除的列或行。 因為用4伏特凝膠法求出的初始解是基本可執(zhí)行解，所以基本變量的個數(shù)為Mn1個。 例題用伏格爾法求初始調(diào)運方案，初始調(diào)運方案，2.2最佳解的判別，判別方法修正空格(非基本變量的檢驗數(shù))，運算問題的目標函數(shù)最小化，所以所有空格中

3、的檢驗數(shù)為零以上時，為最佳解。 調(diào)整方案的任意空間必定存在唯一的閉合回路。表3-7、5、10、4、7、a3、8、2、9、1、a2、10、3、11、3、a1(1)3(1)2(-1 )1=1，調(diào)整后的總運費的增加：空格下的檢驗數(shù)為1，表3-8、5、10、4 調(diào)整后的總運費的增加：空格中的檢查數(shù)為10，(-1 )、(1)，在表3-的1表中的下面和右面追加行和列，在列中追加ui，在行中追加vj，u1=0，因此，從表中的現(xiàn)有數(shù)字中確定所有的ui和vj。 2、對所有空格中的檢驗數(shù)進行校正.0、1、1、2、8、-3、7、檢驗表、1、2、1、-1、10、最佳方案判別標準、表3-12、2.3閉合回路調(diào)整法改善方

4、案是從(p，q )空格開始畫閉合回路，其他角點從空格向閉合回路上的點按1，表3-13，找到最小調(diào)整量后，按照閉合回路上的正、負符號，分別加上這個值進行減法運算，得到新的運算方案。用閉合回路法或電位法求出檢驗數(shù)，則得到以下表：表3-14，此時所有的檢驗數(shù)不是負，表中的解是最佳解，表3-15，例如求出該運算問題的最佳解，2.3表作業(yè)法修正運算中的問題，1 .退化33660 (1) 此時，在生產(chǎn)銷售平衡表上填寫一個數(shù)字，并相應地在單位運輸價格表上刪除一行和一列。 為了使生產(chǎn)銷售平衡表中有(m n-1 )個數(shù)字。 不能同時刪除行和列。 (2)用閉合回路法調(diào)整時，閉合回路中出現(xiàn)具有2個以上(-1 )標記

5、的相等最小值。 在這種情況下，只能選擇一個作為轉(zhuǎn)入價格。 經(jīng)調(diào)整后，后退解決了。 在這種情況下，必須在另一個數(shù)字單元格中輸入0以指示它是基本變量。 在后退解決后，在進行改善調(diào)整的情況下，在某個閉合回路中有可能存在(-1 )的值為0的數(shù)字的格子，在該情況下，應該取調(diào)整量=0。2.5.3生產(chǎn)銷售不平衡的運輸問題及其解決方法，如果銷售大于生產(chǎn)，可以在生產(chǎn)銷售平衡表中添加虛擬產(chǎn)地i=m 1。 本地的生產(chǎn)量，用單位運輸表，從這個虛擬產(chǎn)地到各銷售地的運輸價格為0銷售比生產(chǎn)小的情況下，在生產(chǎn)銷售平衡表中可以追加虛擬銷售地的單位運輸表中從產(chǎn)地到這個虛擬銷售地的運輸價格為0，例如生產(chǎn)設有3個產(chǎn)地的物資，其生產(chǎn)量

6、就是那個。 4個銷售地需要這種物資，銷售量分別為2噸、3噸、4噸、6噸，知道各銷售地之間的單位運價，生產(chǎn)大于銷售，例2 :設置3個化肥廠供應4個地區(qū)的農(nóng)用化肥。 假設同量的化肥在這些地區(qū)有同樣的效果。 各化肥廠的年產(chǎn)量、各地區(qū)的年產(chǎn)量和各化肥廠到各地區(qū)單位的化肥運價如表3-25所示。 決定一下最節(jié)約總運費的化肥供應方案。 表3-25運價：萬元/萬t，這是產(chǎn)銷不平衡的運輸問題，總產(chǎn)量160萬噸，四個地區(qū)最低需求110萬噸，最高需求210噸。 為了尋求平衡，在生產(chǎn)銷售平衡表中增加了虛擬化肥廠d，其年產(chǎn)量為50萬噸。 各地區(qū)的需求量包括兩個部分，例如地區(qū)中，30萬噸是最低需求，因此無法從虛擬化肥廠d供給，相應的運輸價格為m (任意大的正數(shù))，另一部分可以滿足或不滿足20萬噸，因此可以從虛擬化肥廠d供給關(guān)于需求分為兩種情況的地區(qū)，實際上可以分為兩個地區(qū)。 由此，能夠生成該問題的生產(chǎn)銷售平衡表(表326 )和單位運費表(表327 )。表3-27單位運輸價目表、表3-26生產(chǎn)銷售平衡表、表3-28、某商場出國購買ABCD四種規(guī)格的服裝，數(shù)量分別為1500、2000、3000、3500套。