運籌學第三章運輸問題課件

1、2024年3月19日星期二,1,第3章 運輸問題第3節(jié) 產(chǎn)銷不平衡的運輸問 題及其求解方法第4節(jié) 應用舉例,運籌學,2024年3月19日星期二,2,第3節(jié) 產(chǎn)銷不平衡的運輸問題及其求解方法,前面一節(jié)所講的表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的，即??但是實際問題中產(chǎn)銷往往是不平衡的。因此就需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。當產(chǎn)大于銷,2024年3月19日

2、星期二,3,運輸問題的數(shù)學模型可寫成,目標函數(shù)：滿足：,從Ai到Bj的運量小于供應量,從Ai到Bj的運量等于需要量,2024年3月19日星期二,4,由于總的產(chǎn)量大于銷量，就要考慮多余的物資在哪一個產(chǎn)地就地儲存的問題。設xi, n+1是產(chǎn)地Ai的儲存量，于是有：,2024年3月19日星期二,5,令：,當 i=1,…，m，j=1,…，n時,當 i=1,…，m，j=n+1時,將其分別代入，得到,2024年3月19日星期二,6,滿足：,由于

3、這個模型中,所以這是一個產(chǎn)銷平衡的運輸問題。,2024年3月19日星期二,7,若當產(chǎn)大于銷時，只要增加一個假想的銷地j=n+1(實際上是儲存)，該銷地總需要量為,而在單位運價表中從各產(chǎn)地到假想銷地的單位運價為， ，可以理解為就地“銷售” ，就轉(zhuǎn)化成一個產(chǎn) 銷平衡的運輸問題,2024年3月19日星期二,8,當銷大于產(chǎn)時，即可以在產(chǎn)銷平衡表中增加一虛擬行，表示增加一個假想的產(chǎn)地i=m+1，該地產(chǎn)量為,在單位運

4、價表上令從該假想產(chǎn)地到各銷地的運價， ，同樣可以轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題.。,2024年3月19日星期二,9,例2 設有三個化肥廠(A，B，C)供應四個地區(qū)(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如表3-1所示。試求出總的運費最節(jié)省的化肥調(diào)撥方案。 表3-1,2024年3月19日

5、星期二,10,,解 這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第Ⅳ個地區(qū)每年最多能分配到60(160-30-70-0=60)萬噸，這樣其不限的最高需求可等價認為是60萬噸。按最高需求分析，總需求為210萬噸，大于總產(chǎn)量160萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，其年產(chǎn)量為50萬噸。由于各地區(qū)的需要量包含兩部分，如

6、地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應運價為M(任意大正數(shù))，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應運價為0。對凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)看待。這樣可以寫出這個問題的產(chǎn)銷平衡表(表3-2)和單位運價表(表3-3)。,,,2024年3月19日星期二,11,產(chǎn)銷平衡表(表3-2),單位運價表(表3-3),2024年3月19日星期二,12,利用表上作業(yè)

7、法求解步驟如下,1.首先利用最小元素法求出基可行解，步驟如下第一步見表3-4，3-5,2024年3月19日星期二,13,第二步見表3-6，3-7,2024年3月19日星期二,14,第三步，見表3-8，3-9,2024年3月19日星期二,15,第四步，見表3-10，3-11,2024年3月19日星期二,16,第五步，見表3-12，3-13,2024年3月19日星期二,17,第六步，見表3-14，3-15,2024年3月19日星期二,18

8、,第七步，在單位運價表上相應地要劃去一行和一列,因此需要添一個“0”。見表3-16，3-17,2024年3月19日星期二,19,第八步，此時基可行解就是表3-18，3-19,2024年3月19日星期二,20,2.利用位勢法求空格檢驗數(shù)，如下圖所示計算表3-20,2024年3月19日星期二,21,3.表中還有負檢驗數(shù)。說明未得最優(yōu)解，利用閉回路調(diào)整法，見表3-21,2024年3月19日星期二,22,即為表3-22,此時再利用閉回路法求各空

9、格的檢驗數(shù)，見表3-23,2024年3月19日星期二,23,2024年3月19日星期二,24,表中還有負檢驗數(shù)。說明未得最優(yōu)解，利用閉回路調(diào)整法，得到表3-24,2024年3月19日星期二,25,即為表3-25,2024年3月19日星期二,26,依次按照上述方法進行，一直到得到最優(yōu)解為止，可以求得這個問題的最優(yōu)方案如表3-26所示,2024年3月19日星期二,27,第4節(jié) 應 用 舉 例,由于在變量個數(shù)相等的情況下，表上作業(yè)法的計算遠

10、比單純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運輸問題的數(shù)學模型。下面介紹幾個典型的例子。,2024年3月19日星期二,28,例3 某廠按合同規(guī)定須于當年每個季度末分別提供10，15，25，20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如表3-27所示。又如果生產(chǎn)出來的柴油機當季不交貨的，每臺每積壓一個季度需儲存、維護等費用0.15萬元。要求在完成合同的情況下，作出使該廠全年生

11、產(chǎn)(包括儲存、維護)費用最小的決策,2024年3月19日星期二,29,表3-27,2024年3月19日星期二,30,解 由于每個季度生產(chǎn)出來的柴油機不一定當季交貨，所以設xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機數(shù)。根據(jù)合同要求，必須滿足,2024年3月19日星期二,31,又每季度生產(chǎn)的用于當季和以后各季交貨的柴油機數(shù)不可能超過該季度的生產(chǎn)能力，故又有：,2024年3月19日星期二,32,第i季度生產(chǎn)的用于j季度交貨的每臺柴油機的

12、實際成本cij應該是該季度單位成本加上儲存、維護等費用。cij的具體數(shù)值見 表3-28,2024年3月19日星期二,33,設用ai表示該廠第i季度的生產(chǎn)能力，bj表示第i季度的合同供應量，則問題可寫成：,目標函數(shù)：滿足,2024年3月19日星期二,34,顯然，這是一個產(chǎn)大于銷的運輸問題模型。注意到這個問題中當i＞j時，xij=0，所以應令對應的cij=M，再加上一個假想的需求D，就可以把這個問題變成產(chǎn)銷

13、平衡的運輸模型，并寫出產(chǎn)銷平衡表和單位運價表(合在一起，見表3-29)。,2024年3月19日星期二,35,利用表上作業(yè)法進行求解步驟如下,1.利用最小元素法確定基可行解第一步見表3-30，3-31,2024年3月19日星期二,36,第二步，在單位運價表上相應地要劃去一行和一列,因此需要添一個“0”。見表3-32，3-33,2024年3月19日星期二,37,第二步，以此類推，結(jié)果見表3-34，3-35,2024年3月19日星期二,38

14、,2.利用位勢法求空格檢驗數(shù)，如下圖所示計算表3-36,2024年3月19日星期二,39,表中的所有檢驗數(shù)都非負，故表3-37的解為最優(yōu)解,2024年3月19日星期二,40,經(jīng)過用表上作業(yè)法求解，可得多個最優(yōu)方案，表3-37中列出最優(yōu)方案之一。即第Ⅰ季度生產(chǎn)25臺，10臺當季交貨，15臺Ⅱ季度交貨；Ⅱ季度生產(chǎn)5臺，用于Ⅳ季度交貨；Ⅲ季度生產(chǎn)30臺，其中25臺于當季交貨，5臺于Ⅳ季度交貨。Ⅳ季度生產(chǎn)10臺，于當季交貨。按此方案生產(chǎn)，該廠總

15、的生產(chǎn)(包括儲存、維護)的費用為773萬元。,2024年3月19日星期二,41,例4 某航運公司承擔六個港口城市A、B、C、D、E、F的四條固定航線的物資運輸任務。已知各條航線的起點、終點城市及每天航班數(shù)見表3-38。,,2024年3月19日星期二,42,假定各條航線使用相同型號的船只，又各城市間的航程天數(shù)見表3-39。,2024年3月19日星期二,43,又知每條船只每次裝卸貨的時間各需1天，則該航運公司至少應配備多少條船，才能滿足

16、所有航線的運貨需求?,解 該公司所需配備船只分兩部分。(1) 載貨航程需要的周轉(zhuǎn)船只數(shù)。例如航線1，在港口E裝貨1天，E→D航程17天，在D卸貨1天，總計19天。每天3航班，故該航線周轉(zhuǎn)船只需57條。各條航線周轉(zhuǎn)所需船只數(shù)見表3-40。,2024年3月19日星期二,44,表3-40,以上累計共需周轉(zhuǎn)船只數(shù)91條 .,2024年3月19日星期二,45,(2) 各港口間調(diào)度所需船只數(shù)。有些港口每天到達船數(shù)多于需要船數(shù)，例如港口D，每天到

17、達3條，需求1條；而有些港口到達數(shù)少于需求數(shù)，例如港口B。各港口每天余缺船只數(shù)的計算見 表3-41。,2024年3月19日星期二,46,為使配備船只數(shù)最少，應做到周轉(zhuǎn)的空船數(shù)為最少。因此建立以下運輸問題，其產(chǎn)銷平衡表見表3-42。,2024年3月19日星期二,47,單位運價表應為相應各港口之間的船只航程天數(shù)，見表3-43。,2024年3月19日星期二,48,用表上作業(yè)法求出空船的最優(yōu)調(diào)度方案，具體步驟

18、如下。1.利用最小元素法確定基可行解 第一步(見表3-44，3-45),2024年3月19日星期二,49,第二步，不過本步要注意在單位運價表上相應地要劃去一行和一列,因此需要添一個“0”。(見表3-46，3-47),2024年3月19日星期二,50,第三步(見表3-48，3-49),2024年3月19日星期二,51,2.利用位勢法求空格檢驗數(shù)，如下圖所示計算表(見表3-50),2024年3月19日星期二,52,3.利用閉回路調(diào)整法

19、進行改進(見表3-51),2024年3月19日星期二,53,4.再利用位勢法求各空格的檢驗數(shù)見表3-52，表中所有檢驗數(shù)都非負,2024年3月19日星期二,54,由表3-53知最少需周轉(zhuǎn)的空船數(shù)為2×1+13×1+5×1+17×1+3×1=40條。這樣在不考慮維修、儲備等情況下，該公司至少應配備40+91=131條船。,最終的最優(yōu)調(diào)度方案見表3-53,2024年3月19日星期二,55

20、,例5 在本章的例1中，如果假定,①每個工廠生產(chǎn)的產(chǎn)品不一定直接發(fā)運到銷售點，可以將其中幾個產(chǎn)地集中一起運；②運往各銷地的產(chǎn)品可以先運給其中幾個銷地，再轉(zhuǎn)運給其他銷地；③除產(chǎn)、銷地之外，中間還可以有幾個轉(zhuǎn)運站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地間轉(zhuǎn)運。已知各產(chǎn)地、銷地、中間轉(zhuǎn)運站及相互之間每噸產(chǎn)品的運價如表3-54所示，問在考慮到產(chǎn)銷地之間直接運輸和非直接運輸?shù)母鞣N可能方案的情況下，如何將三個廠每天生產(chǎn)的產(chǎn)品運往銷售地，使總的運費

21、最少。,2024年3月19日星期二,56,表 3-54,2024年3月19日星期二,57,解 從表3-54中看出，從A1到B2每噸產(chǎn)品的直接運費為11元，如從A1經(jīng)A3運往B2，每噸運價為3+4=7元，從A1經(jīng)T2運往B2只需1+5=6元，而從A1到B2運費最少的路徑是從A1經(jīng)A2，B1到B2，每噸產(chǎn)品的運費只需1+1+1=3元?？梢娺@個問題中從每個產(chǎn)地到各銷地之間的運輸方案是很多的。為了把這個問題仍當作一般的運輸問題處理，可以這樣

22、做：,2024年3月19日星期二,58,(1) 由于問題中所有產(chǎn)地、中間轉(zhuǎn)運站、銷地都可以看作產(chǎn)地，又可看作銷地。因此把整個問題當作有11個產(chǎn)地和11個銷地的擴大的運輸問題。(2) 對擴大的運輸問題建立單位運價表。方法將表3-54中不可能的運輸方案的運價用任意大的正數(shù)M代替。,2024年3月19日星期二,59,,(3) 所有中間轉(zhuǎn)運站的產(chǎn)量等于銷量。由于運費最少時不可能出現(xiàn)一批物資來回倒運的現(xiàn)象，所以每個轉(zhuǎn)運站的轉(zhuǎn)運數(shù)不超過20噸。可

23、以規(guī)定T1，T2，T3，T4的產(chǎn)量和銷量均為20噸。由于實際的轉(zhuǎn)運量,可以在每個約束條件中增加一個松弛變量xii，xii相當于一個虛構(gòu)的轉(zhuǎn)運站，意義就是自己運給自己。(20-xii)就是每個轉(zhuǎn)運站的實際轉(zhuǎn)運量，xii的對應運價cii=0。,2024年3月19日星期二,60,(4) 擴大的運輸問題中原來的產(chǎn)地與銷地因為也有轉(zhuǎn)運站的作用，所以同樣在原來產(chǎn)量與銷量的數(shù)字上加20噸，即三個廠每天糖果產(chǎn)量改成27，24，29噸，銷量均為20噸；