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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、的生產(chǎn)(包括儲(chǔ)存、維護(hù))的費(fèi)用為773萬(wàn)元。,2024年3月19日星期二,41,例4 某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)。已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見(jiàn)表3-38。,,2024年3月19日星期二,42,假定各條航線使用相同型號(hào)的船只，又各城市間的航程天數(shù)見(jiàn)表3-39。,2024年3月19日星期二,43,又知每條船只每次裝卸貨的時(shí)間各需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ù)見(jiàn)表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ì)算見(jiàn) 表3-41。,2024年3月19日星期二,46,為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少。因此建立以下運(yùn)輸問(wèn)題，其產(chǎn)銷平衡表見(jiàn)表3-42。,2024年3月19日星期二,47,單位運(yùn)價(jià)表應(yīng)為相應(yīng)各港口之間的船只航程天數(shù)，見(jiàn)表3-43。,2024年3月19日星期二,48,用表上作業(yè)法求出空船的最優(yōu)調(diào)度方案，具體步驟

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

19、進(jìn)行改進(jìn)(見(jiàn)表3-51),2024年3月19日星期二,53,4.再利用位勢(shì)法求各空格的檢驗(yàn)數(shù)見(jiàn)表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條。這樣在不考慮維修、儲(chǔ)備等情況下，該公司至少應(yīng)配備40+91=131條船。,最終的最優(yōu)調(diào)度方案見(jiàn)表3-53,2024年3月19日星期二,55

20、,例5 在本章的例1中，如果假定,①每個(gè)工廠生產(chǎn)的產(chǎn)品不一定直接發(fā)運(yùn)到銷售點(diǎn)，可以將其中幾個(gè)產(chǎn)地集中一起運(yùn)；②運(yùn)往各銷地的產(chǎn)品可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地；③除產(chǎn)、銷地之外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地間轉(zhuǎn)運(yùn)。已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站及相互之間每噸產(chǎn)品的運(yùn)價(jià)如表3-54所示，問(wèn)在考慮到產(chǎn)銷地之間直接運(yùn)輸和非直接運(yùn)輸?shù)母鞣N可能方案的情況下，如何將三個(gè)廠每天生產(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)價(jià)為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元?？梢?jiàn)這個(gè)問(wèn)題中從每個(gè)產(chǎn)地到各銷地之間的運(yùn)輸方案是很多的。為了把這個(gè)問(wèn)題仍當(dāng)作一般的運(yùn)輸問(wèn)題處理，可以這樣

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

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