運(yùn)籌學(xué)第三章運(yùn)輸問題課件

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

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

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

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

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

6、地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應(yīng)運(yùn)價為M(任意大正數(shù))，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應(yīng)運(yùn)價為0。對凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個地區(qū)看待。這樣可以寫出這個問題的產(chǎn)銷平衡表(表3-2)和單位運(yùn)價表(表3-3)。,,,2024年3月19日星期二,11,產(chǎn)銷平衡表(表3-2),單位運(yùn)價表(表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、,第七步，在單位運(yùn)價表上相應(yīng)地要劃去一行和一列,因此需要添一個“0”。見表3-16，3-17,2024年3月19日星期二,19,第八步，此時基可行解就是表3-18，3-19,2024年3月19日星期二,20,2.利用位勢法求空格檢驗(yàn)數(shù)，如下圖所示計(jì)算表3-20,2024年3月19日星期二,21,3.表中還有負(fù)檢驗(yàn)數(shù)。說明未得最優(yōu)解，利用閉回路調(diào)整法，見表3-21,2024年3月19日星期二,22,即為表3-22,此時再利用閉回路法求各空

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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