ch5 運(yùn)輸問(wèn)題-2015

1、 Page 1 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 第第5章章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型 2 表上作業(yè)法表上作業(yè)法 3產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其應(yīng)用產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其應(yīng)用 4指派問(wèn)題指派問(wèn)題 Page 2 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem n5.4 分配問(wèn)題與匈牙利算法分配問(wèn)題與匈牙利算法 5.4.1 分配問(wèn)題的數(shù)學(xué)模型分配問(wèn)題的數(shù)學(xué)模型 5.4.2 匈牙利算法匈牙利算法 Page 3 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 有

2、一份說(shuō)明書(shū)有一份說(shuō)明書(shū), 要分別譯成英、要分別譯成英、日、德、俄四種文字日、德、俄四種文字, 交甲乙丙丁四交甲乙丙丁四個(gè)人去完成個(gè)人去完成. 因各人專(zhuān)長(zhǎng)不同因各人專(zhuān)長(zhǎng)不同, 他們他們完成翻譯不同文字所需的時(shí)間如表完成翻譯不同文字所需的時(shí)間如表所示所示. 應(yīng)如何分配應(yīng)如何分配, 使這四人分別完使這四人分別完成成 這四項(xiàng)任務(wù)總的時(shí)間最少這四項(xiàng)任務(wù)總的時(shí)間最少. 假定有假定有m項(xiàng)任務(wù)分配給項(xiàng)任務(wù)分配給m個(gè)人去完成個(gè)人去完成, 并指定每人完成其中一項(xiàng)并指定每人完成其中一項(xiàng), 每項(xiàng)只交給其中一個(gè)人去完成每項(xiàng)只交給其中一個(gè)人去完成, 第第 i 個(gè)人做第個(gè)人做第 j 項(xiàng)工作的效率為項(xiàng)工作的效率為cij0，應(yīng)

3、如何分配使總的應(yīng)如何分配使總的效率最高效率最高. 5.4.1 指派問(wèn)題的數(shù)學(xué)模型指派問(wèn)題的數(shù)學(xué)模型指派問(wèn)題指派問(wèn)題(分配問(wèn)題分配問(wèn)題)效率矩陣：效率矩陣： 利用不同資源完成不同計(jì)劃活動(dòng)的效率通?？捎美貌煌Y源完成不同計(jì)劃活動(dòng)的效率通?？捎帽砀裥问奖硎?，表格中的數(shù)字組成效率矩陣表格形式表示，表格中的數(shù)字組成效率矩陣.例例效率矩陣效率矩陣 譯成譯成英文英文譯成譯成日文日文譯成譯成德文德文譯城譯城俄文俄文甲甲21097乙乙154148丙丙13141611丁丁415139工工作作人人 Page 4 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 人人工作工作a1a2a

4、iamb1b2bjbmxi1 xi2 xij xi m-1 xim x1j xij x2j xm-1j xmj 指派問(wèn)題的數(shù)學(xué)模型指派問(wèn)題的數(shù)學(xué)模型: )1,(0, 1mjijijixij，項(xiàng)項(xiàng)任任務(wù)務(wù)個(gè)個(gè)人人去去完完成成第第，不不分分配配第第項(xiàng)項(xiàng)任任務(wù)務(wù)個(gè)個(gè)人人去去完完成成第第分分配配第第 ), 1,( 10mjixij 或或第第i人完成人完成一項(xiàng)工作一項(xiàng)工作第第j 項(xiàng)工作項(xiàng)工作由一人完成由一人完成 miijmjx1), 1( 1 mjijmix1), 1( 1 .ts11minmmijijijzc x Page 5 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Probl

5、em 5.4.2 匈牙利算法匈牙利算法事實(shí)：事實(shí)：若效率矩陣的所有元素若效率矩陣的所有元素0ijc , 而其中存在一組位于不同行而其中存在一組位于不同行其余的其余的邏輯變量邏輯變量xij=0, 得到的就是問(wèn)題的最優(yōu)解得到的就是問(wèn)題的最優(yōu)解(最優(yōu)分配方案最優(yōu)分配方案).例例 601024570效率矩陣為效率矩陣為令令1322311 xxx問(wèn)題：?jiǎn)栴}：如何產(chǎn)生并尋找這組位于不同行不同列的零元素？如何產(chǎn)生并尋找這組位于不同行不同列的零元素？不同列的零元素，不同列的零元素， 則只要令對(duì)應(yīng)于這些零元素位置的邏輯變量則只要令對(duì)應(yīng)于這些零元素位置的邏輯變量xij=1, ，其余，其余xij=011mmijij

6、ijzc x 最最優(yōu)優(yōu)值值 Page 6 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 匈牙利數(shù)學(xué)家克尼格匈牙利數(shù)學(xué)家克尼格(Knig)基礎(chǔ)：基礎(chǔ)：兩個(gè)基本定理兩個(gè)基本定理定理定理1 如果從分配問(wèn)題效率矩陣如果從分配問(wèn)題效率矩陣aij的每一行元素中分別的每一行元素中分別減去減去(或加上或加上)一個(gè)常數(shù)一個(gè)常數(shù)ui(被稱(chēng)為該行的位勢(shì)被稱(chēng)為該行的位勢(shì)), 從每一列分從每一列分別減去別減去(或加上或加上)一個(gè)常數(shù)一個(gè)常數(shù)vj(被稱(chēng)為該列的位勢(shì)被稱(chēng)為該列的位勢(shì)), 得到一個(gè)得到一個(gè)新的效率矩陣新的效率矩陣bij, 其中其中bij=aij-ui-vj , 則則bij的最

7、優(yōu)解等價(jià)于的最優(yōu)解等價(jià)于aij的最優(yōu)解。的最優(yōu)解。作用：作用： 構(gòu)造含有零元素的等價(jià)效率矩陣。構(gòu)造含有零元素的等價(jià)效率矩陣。 定理定理2 若矩陣若矩陣A的元素分成的元素分成“0”與非與非“0”兩部分，則覆蓋兩部分，則覆蓋“0”元素的元素的最少最少直線數(shù)等于位于不同行不同列的直線數(shù)等于位于不同行不同列的“0”元素元素的最大個(gè)數(shù)的最大個(gè)數(shù).作用：作用：判別效率矩陣中有多少個(gè)不同行不同列的零元素。判別效率矩陣中有多少個(gè)不同行不同列的零元素。 Page 7 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 匈牙利算法的步驟：匈牙利算法的步驟：第一步：第一步： 找出效率矩陣

8、每行的最小元素找出效率矩陣每行的最小元素, ,并分別并分別從每行中減去從每行中減去最小元素最小元素. . 913154111614138144157910241142minmin 59110053241001157800500 541100032450115280產(chǎn)生含產(chǎn)生含零的等零的等價(jià)效率價(jià)效率矩陣矩陣 每行至少一個(gè)每行至少一個(gè)0元素元素每列也至少一個(gè)每列也至少一個(gè)0元素元素第二步：第二步：再找出矩陣每列的最小元素再找出矩陣每列的最小元素, ,再分別再分別從各列中減去從各列中減去. . Page 8 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 第三步第三

9、步 判定由前兩步得到的效率矩陣中有多少個(gè)不同行不同列判定由前兩步得到的效率矩陣中有多少個(gè)不同行不同列的零元素的零元素. . 按照以下準(zhǔn)則進(jìn)行：按照以下準(zhǔn)則進(jìn)行： (1) 從第一行開(kāi)始從第一行開(kāi)始, 若該行只有一個(gè)零元素若該行只有一個(gè)零元素, 就對(duì)這個(gè)就對(duì)這個(gè)零元素打上零元素打上( )號(hào)號(hào), 對(duì)打?qū)Υ? )號(hào)零元素所在列畫(huà)一條直線號(hào)零元素所在列畫(huà)一條直線. (2) 從第一列開(kāi)始從第一列開(kāi)始, 若該列只有一個(gè)零元素就對(duì)這個(gè)零若該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上元素打上( )號(hào)號(hào)(同樣不考慮已劃去的零元素同樣不考慮已劃去的零元素), 對(duì)打?qū)Υ? )號(hào)零號(hào)零元素所在行畫(huà)一條直線元素所在行畫(huà)一條直線.

10、 若該行沒(méi)有零元素或有兩個(gè)以上零元素若該行沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)已劃去的不計(jì)在內(nèi)在內(nèi)), 則轉(zhuǎn)下一行則轉(zhuǎn)下一行, 依次進(jìn)行到最后一行依次進(jìn)行到最后一行. 若該列沒(méi)有零元素或有兩個(gè)以上零元素若該列沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不已劃去的不計(jì)在內(nèi)計(jì)在內(nèi)), 則轉(zhuǎn)下一列則轉(zhuǎn)下一列, 依次進(jìn)行到最后一行依次進(jìn)行到最后一行. (3) 重復(fù)重復(fù)(1)、(2)兩個(gè)步驟兩個(gè)步驟,直至不能進(jìn)行為止，直至不能進(jìn)行為止， 541100032450115280( )( )( ) Page 9 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 231 效率矩陣每

11、行效率矩陣每行(或每列或每列)都有一個(gè)打都有一個(gè)打( )號(hào)的零元素號(hào)的零元素, 令對(duì)應(yīng)打令對(duì)應(yīng)打( )號(hào)零元素的號(hào)零元素的xij=1, 就找到了問(wèn)題的最優(yōu)解就找到了問(wèn)題的最優(yōu)解.打打( )號(hào)的零元素個(gè)數(shù)小于號(hào)的零元素個(gè)數(shù)小于m, 但未被劃去的零元素之間存在但未被劃去的零元素之間存在閉回路閉回路, 打打( )號(hào)的零元素個(gè)數(shù)小于號(hào)的零元素個(gè)數(shù)小于m, 但矩陣中所有零元素被劃去或打但矩陣中所有零元素被劃去或打上上( )號(hào)號(hào). 541100032450115280( )( )( ) (3) 重復(fù)重復(fù)(1)、(2)兩個(gè)步驟兩個(gè)步驟,直至不能進(jìn)行為止，直至不能進(jìn)行為止， 可能出現(xiàn)三種情況可能出現(xiàn)三種情況:

12、 然后對(duì)所有打然后對(duì)所有打( )號(hào)的零元素號(hào)的零元素, 或所在行或所在行, 或所在列，或所在列，畫(huà)畫(huà)一條直線一條直線.重復(fù)重復(fù)(1)、(2)兩個(gè)步驟，直至不能進(jìn)行為止。兩個(gè)步驟，直至不能進(jìn)行為止。這時(shí)可順著閉回路的走向這時(shí)可順著閉回路的走向, 對(duì)每個(gè)間隔的零元素打?qū)γ總€(gè)間隔的零元素打( )號(hào)號(hào), 此時(shí)轉(zhuǎn)第四步。此時(shí)轉(zhuǎn)第四步。 Page 10 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 第四步：第四步：為設(shè)法使每一行都有一個(gè)為設(shè)法使每一行都有一個(gè)打打( )號(hào)的零元素，需要繼續(xù)號(hào)的零元素，需要繼續(xù)按定理按定理1 1對(duì)矩陣進(jìn)行變換：對(duì)矩陣進(jìn)行變換： (1) 從矩陣

13、未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)字從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)字k; (2) 對(duì)矩陣的每行對(duì)矩陣的每行, 當(dāng)該行有直線覆蓋時(shí)令當(dāng)該行有直線覆蓋時(shí)令ui=0, 無(wú)直線覆蓋的無(wú)直線覆蓋的令令ui=k . (3) 對(duì)矩陣的每列對(duì)矩陣的每列, 當(dāng)該列有直線覆蓋時(shí)令當(dāng)該列有直線覆蓋時(shí)令vj=-k, 無(wú)直線覆蓋的無(wú)直線覆蓋的令令vj=0. (4) 從原矩陣的每個(gè)元素從原矩陣的每個(gè)元素aij中分別減去中分別減去ui和和vj ,得到一個(gè)新的矩得到一個(gè)新的矩 陣陣, 轉(zhuǎn)第五步。轉(zhuǎn)第五步。第五步：第五步： 返回到第三步返回到第三步, ,反復(fù)進(jìn)行反復(fù)進(jìn)行, ,一直到矩陣的每一行都有一個(gè)一直到矩陣的

14、每一行都有一個(gè)打號(hào)的零元素為止打號(hào)的零元素為止, ,即找到了最優(yōu)分配方案即找到了最優(yōu)分配方案. . 541100032450115280( )( )( )20220022 321100054230113080( )( )( )( ) Page 11 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 說(shuō)明：說(shuō)明：1)第三步中的第二種結(jié)果第三步中的第二種結(jié)果2打打( )號(hào)的零元素個(gè)數(shù)小于號(hào)的零元素個(gè)數(shù)小于m, 但未被劃去的零元素之間但未被劃去的零元素之間存在閉回路存在閉回路, 這時(shí)可順著閉回路的走向這時(shí)可順著閉回路的走向, 對(duì)每個(gè)間隔的對(duì)每個(gè)間隔的零元素打一零元素打一

15、( )號(hào)號(hào), 然后對(duì)所有打然后對(duì)所有打( )號(hào)的零元素號(hào)的零元素, 或所在或所在行行, 或所在列畫(huà)一條直線或所在列畫(huà)一條直線. 000000 000000( )( )( ) 000000( )( )( )或或 000000( )( )( ) 000000( )( )( ) 000000( )( )或或( ) Page 12 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 0405802304502100例例( )( )( )( ) 0405802304500100( )(1)(2) 0405802304502100( )( )( )( )( )( ) 04058

16、02304500100( )( )( )( ) 0405802304500100( )( )( )( )得到得到答案答案 0405802304500100( )( )( )( ) Page 13 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 說(shuō)明：說(shuō)明：2.分配問(wèn)題中如果人數(shù)和任務(wù)數(shù)不相等時(shí)的處理方法分配問(wèn)題中如果人數(shù)和任務(wù)數(shù)不相等時(shí)的處理方法.(2) 人數(shù)人數(shù)任務(wù)數(shù)任務(wù)數(shù) 工作工作 人人IIIIII13252746336345355652 仍規(guī)定每人完成一項(xiàng)工作仍規(guī)定每人完成一項(xiàng)工作, 每項(xiàng)工作只交給一個(gè)人去完成每項(xiàng)工作只交給一個(gè)人去完成 增添兩項(xiàng)假想的工作

17、任務(wù)增添兩項(xiàng)假想的工作任務(wù), 每每個(gè)人完成這兩項(xiàng)任務(wù)時(shí)間為零個(gè)人完成這兩項(xiàng)任務(wù)時(shí)間為零.IVV0000000000 工作工作 人人IIIIIIIV13252274633363540000 Page 14 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 0025600535003630064700523min00000min00223 0003300312001400042400300( )( )( )( )( )3.目標(biāo)函數(shù)為目標(biāo)函數(shù)為 的處理方法的處理方法. mimjijijxaz11max mimjijijxaz11max mimjijijxaz11)(mi

18、n 9131541611141381441579102min 620110523711103108min010015161510 610110423701103008 Page 15 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 人們?cè)趶氖律a(chǎn)活動(dòng)中，不人們?cè)趶氖律a(chǎn)活動(dòng)中，不可避免地要進(jìn)行物資調(diào)運(yùn)工可避免地要進(jìn)行物資調(diào)運(yùn)工作。如某時(shí)期內(nèi)將生產(chǎn)基地作。如某時(shí)期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類(lèi)物的煤、鋼鐵、糧食等各類(lèi)物資，分別運(yùn)到需要這些物資資，分別運(yùn)到需要這些物資的地區(qū)，根據(jù)各地的的地區(qū)，根據(jù)各地的生產(chǎn)量生產(chǎn)量和和需要量需要量及各地之間的及各地之間的運(yùn)輸運(yùn)輸

19、費(fèi)用費(fèi)用，如何制定一個(gè)運(yùn)輸方，如何制定一個(gè)運(yùn)輸方案，使總的運(yùn)輸費(fèi)用最小。案，使總的運(yùn)輸費(fèi)用最小。這樣的問(wèn)題稱(chēng)為這樣的問(wèn)題稱(chēng)為運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題。5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems5.1.1 數(shù)學(xué)模型數(shù)學(xué)模型產(chǎn)地銷(xiāo)地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329圖圖5.1 Page 16 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 【例【例5.1】現(xiàn)有】現(xiàn)有A1，A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng)三個(gè)產(chǎn)糧區(qū)，可供應(yīng) 糧食分別為糧食分別為10，8，5（萬(wàn)噸），現(xiàn)將糧

20、食運(yùn)往（萬(wàn)噸），現(xiàn)將糧食運(yùn)往B1，B2，B3，B4四個(gè)地區(qū)，其需四個(gè)地區(qū)，其需要量分別為要量分別為5，7，8，3（萬(wàn)噸）。產(chǎn)糧地到需求地的運(yùn)價(jià)（元（萬(wàn)噸）。產(chǎn)糧地到需求地的運(yùn)價(jià)（元/噸）如表噸）如表51所示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)所示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。用最少。地區(qū)地區(qū)產(chǎn)糧區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量產(chǎn)量A1326310A253828A341295需要量需要量578323運(yùn)價(jià)表（元運(yùn)價(jià)表（元/T）表表515.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 17 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派

21、問(wèn)題T&A Problem 設(shè)設(shè)xij(i=1,2,3；j=1,2,3,4)為為i個(gè)產(chǎn)糧地運(yùn)往第個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)量，個(gè)需求地的運(yùn)量，這樣得到下列運(yùn)輸問(wèn)題的數(shù)學(xué)模型：這樣得到下列運(yùn)輸問(wèn)題的數(shù)學(xué)模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即 4,3,2, 13,2, 1,0jixij；5.1

22、運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 18 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 有些問(wèn)題表面上與運(yùn)輸問(wèn)題沒(méi)有多大關(guān)系，也可以建立與有些問(wèn)題表面上與運(yùn)輸問(wèn)題沒(méi)有多大關(guān)系，也可以建立與運(yùn)輸問(wèn)題形式相同的數(shù)學(xué)模型運(yùn)輸問(wèn)題形式相同的數(shù)學(xué)模型例如例如 【例【例5.2】有三臺(tái)機(jī)床加工三種零件，計(jì)劃第】有三臺(tái)機(jī)床加工三種零件，計(jì)劃第i臺(tái)的生產(chǎn)任務(wù)臺(tái)的生產(chǎn)任務(wù)為為a i (i=1,2,3)個(gè)零件，第個(gè)零件，第j種零件的需要量為種零件的需要量為bj (j=1,2,3)，第，第i臺(tái)臺(tái)機(jī)床加工第機(jī)床加工第j種零件需要

23、的時(shí)間為種零件需要的時(shí)間為cij ，如表，如表52所示。問(wèn)如何安所示。問(wèn)如何安排生產(chǎn)任務(wù)使總的加工時(shí)間最少？排生產(chǎn)任務(wù)使總的加工時(shí)間最少？ 零件零件機(jī)床機(jī)床B1B2B3生產(chǎn)任務(wù)生產(chǎn)任務(wù)A152350A264160A373440需要量需要量703050150表表525.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 19 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 【解】【解】 設(shè)設(shè) xi j (i=1,2,3；j=1,2,3,)為第為第i臺(tái)機(jī)床加工第臺(tái)機(jī)床加工第j種零件的種零件的數(shù)量，則此問(wèn)題的數(shù)學(xué)模型為數(shù)量

24、，則此問(wèn)題的數(shù)學(xué)模型為3 , 2 , 13 , 2 , 1, 050307040605043746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxZij；5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 20 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型12n1a12a2mamb1b2bn產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量表表1 產(chǎn)銷(xiāo)平

25、衡表產(chǎn)銷(xiāo)平衡表表表2 單位運(yùn)價(jià)表單位運(yùn)價(jià)表12 n1c11c12 c1n2c21c22 c2nmcm1cm2 cmn產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 Page 21 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地a1a2aiamb1b2bjbnxij :表示從第表示從第i個(gè)產(chǎn)個(gè)產(chǎn)地調(diào)運(yùn)給第地調(diào)運(yùn)給第j個(gè)銷(xiāo)地個(gè)銷(xiāo)地的物資的單位數(shù)量的物資的單位數(shù)量xi1 xi2 xij xi n-1 xin x1j xij x2j xm-1j xmj minjijijxcz11min . .tsmiaxinjij, 2 , 1,1 njbxjmiij, 2 , 1,1 0 ijx

26、1. 有有m+n個(gè)約束條件，個(gè)約束條件，mn個(gè)變量個(gè)變量2. 運(yùn)輸問(wèn)題存在可行解，也一定存在最優(yōu)解運(yùn)輸問(wèn)題存在可行解，也一定存在最優(yōu)解 3. 當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解 Page 22 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 系數(shù)矩陣系數(shù)矩陣mnmmnnxxxxxxxxx212222111211 行行m 行行n jmiijeeP 0110miaxinjij, 2 , 1,1 njbxjmiij, 2 , 1,1 111111111111111111若若系數(shù)矩陣和增廣矩陣的秩是否相等？系

27、數(shù)矩陣和增廣矩陣的秩是否相等？iminjjab 11 Page 23 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 行降秩，取第一行到行降秩，取第一行到m+n1行與行與對(duì)應(yīng)的列（共對(duì)應(yīng)的列（共m+n-1列）組成的列）組成的m+n1階子式階子式1, 1121121,nmnnnxxxxxx，m 行行n 行行5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems111212122212111111111111111111nnmmmnxxxxxxxxxA Page 24 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A

28、 Problem 0111111111故故r(A)=m+n1，所以運(yùn)輸問(wèn)題有，所以運(yùn)輸問(wèn)題有m+n1個(gè)基變量。個(gè)基變量。5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems基變量的個(gè)數(shù)基變量的個(gè)數(shù)=(m+n-1)若若系數(shù)矩陣和增廣矩陣系數(shù)矩陣和增廣矩陣的秩的秩=(m+n-1)iminjjab 11 Page 25 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 為了在為了在mn個(gè)變量中找出個(gè)變量中找出m+n1個(gè)變量作為一組基變量，就個(gè)變量作為一組基變量，就是要在是要在A中找出中找出m+n-1個(gè)線性無(wú)關(guān)的列向量，下面引用閉回個(gè)

29、線性無(wú)關(guān)的列向量，下面引用閉回路的概念尋找這些基變量。路的概念尋找這些基變量。 1 11 22 22 311212,( ,)s ssi ji ji ji ji ji jssxxxxxxi iijjj稱(chēng)稱(chēng)集集合合；互互不不相相同同為一個(gè)閉回路，集合中的變量稱(chēng)為回路的頂點(diǎn)，相鄰兩個(gè)變?yōu)橐粋€(gè)閉回路，集合中的變量稱(chēng)為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。量的連線為閉回路的邊。 Page 26 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 閉回路集合中的變量稱(chēng)為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線閉回路集合中的變量稱(chēng)為回路的頂點(diǎn)，相鄰兩個(gè)變量的連線為閉回路的邊。在表為閉

30、回路的邊。在表53及表及表54中的變量組構(gòu)成兩個(gè)閉回中的變量組構(gòu)成兩個(gè)閉回路。路。 x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31 x42表表53表表53中閉回路的變量集中閉回路的變量集合是合是x11, x12, x42, x 43, x 23, x 25, x 35, x 31共有共有8個(gè)頂點(diǎn)，個(gè)頂點(diǎn)， 這這8個(gè)頂點(diǎn)間用水平或垂直個(gè)頂點(diǎn)間用水平或垂直線段連接起來(lái)，組成一條線段連接起來(lái)，組成一條封閉的回路。封閉的回路。 5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 27 Chapter 5 運(yùn)

31、輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem x11x12x32x33x41 B1B2B3A1 A2 A3 A4 x43表表54 一條回路中的頂點(diǎn)數(shù)一定是一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度度與另一頂點(diǎn)連接，表與另一頂點(diǎn)連接，表53中的變中的變量量x 32及及x33不是回閉路的頂點(diǎn)，不是回閉路的頂點(diǎn)，只是連線的交點(diǎn)。只是連線的交點(diǎn)。 表表54中閉回路是中閉回路是123233434111,xxxxxx;,121131352521xxxxxxA ;,2111123233xxxxxB 例如變量組例如變量組A不能組成一條閉回路，但不能組成一條閉回路

32、，但A中包含有閉回路中包含有閉回路 ;,31352521xxxxB的變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；的變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路； 5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems Page 28 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 333211122321,xxxxxxC C是一條閉回路，若把是一條閉回路，若把C重新寫(xiě)成重新寫(xiě)成 就不難看出就不難看出C仍是一條閉回路。仍是一條閉回路。 111232332321,xxxxxxC 【定理【定理5.2】 若變量組若變量組B 包含有閉

33、回路包含有閉回路 ，則，則B中的變量對(duì)應(yīng)的列向量線性相關(guān)。中的變量對(duì)應(yīng)的列向量線性相關(guān)。12111,jijijisxxxC【證】由線性代數(shù)知，向量組中部分向量組線性相關(guān)則該向量組【證】由線性代數(shù)知，向量組中部分向量組線性相關(guān)則該向量組線性相關(guān)，顯然，將線性相關(guān)，顯然，將C中列向量分別乘以正負(fù)號(hào)線性組合后等于中列向量分別乘以正負(fù)號(hào)線性組合后等于零，即零，即1 11 22 210si ji ji ji jPPPP因而因而C中的列向量線性相關(guān)，所以中的列向量線性相關(guān)，所以B中列向量線性相關(guān)。中列向量線性相關(guān)。5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems

34、Page 29 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 由定理由定理2可知，當(dāng)一個(gè)變量組中不包含有閉回路，則這些變量對(duì)應(yīng)可知，當(dāng)一個(gè)變量組中不包含有閉回路，則這些變量對(duì)應(yīng)的系數(shù)向量線性無(wú)關(guān)。的系數(shù)向量線性無(wú)關(guān)。求運(yùn)輸問(wèn)題的一組基變量，就是要找到求運(yùn)輸問(wèn)題的一組基變量，就是要找到m+n1個(gè)變量，使得它們個(gè)變量，使得它們對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)，由定理對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)，由定理2，找這樣的一組變量是很容，找這樣的一組變量是很容易的，只要易的，只要m+n1個(gè)變量中不包含閉回路，就可得到一組基變量。個(gè)變量中不包含閉回路，就可得到一組基變量。因而有：因而有：

35、【定理【定理3】m+n1個(gè)變量組構(gòu)成基變量的充要條件是它不包含個(gè)變量組構(gòu)成基變量的充要條件是它不包含任何閉回路。任何閉回路。定理定理3告訴了一個(gè)求基變量的簡(jiǎn)單方法，同時(shí)也可以判斷一組變量告訴了一個(gè)求基變量的簡(jiǎn)單方法，同時(shí)也可以判斷一組變量是否可以作為某個(gè)運(yùn)輸問(wèn)題的基變量。這種方法是直接在運(yùn)價(jià)表是否可以作為某個(gè)運(yùn)輸問(wèn)題的基變量。這種方法是直接在運(yùn)價(jià)表中進(jìn)行的，不需要在系數(shù)矩陣中進(jìn)行的，不需要在系數(shù)矩陣A中去尋找，從而給運(yùn)輸問(wèn)題求初始中去尋找，從而給運(yùn)輸問(wèn)題求初始基可行解帶來(lái)極大的方便?；尚薪鈳?lái)極大的方便。5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problem

36、s Page 30 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 表表5-5 BjAiB1B2B3B4aiA1c11 c12c13c14 a1x11x12x13x14A2c21c22 c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b45.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems例如，例如，m=3,n=4，將運(yùn)量，將運(yùn)量xij與運(yùn)價(jià)與運(yùn)價(jià)Cij放在同一張表中，如表放在同一張表中，如表5-5所示。所示。 Page 31 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)

37、輸與指派問(wèn)題T&A Problem 這個(gè)運(yùn)輸問(wèn)題的基變量數(shù)目是這個(gè)運(yùn)輸問(wèn)題的基變量數(shù)目是3+41=6。變量組中。變量組中有有7個(gè)變量，顯然不能構(gòu)成一組基變量，又如個(gè)變量，顯然不能構(gòu)成一組基變量，又如中有中有6個(gè)變量，但包含有一條閉回路個(gè)變量，但包含有一條閉回路故不能構(gòu)成一組基變量。變量組故不能構(gòu)成一組基變量。變量組有有6個(gè)變量且不含有任何閉回路，故可以構(gòu)成此問(wèn)題的個(gè)變量且不含有任何閉回路，故可以構(gòu)成此問(wèn)題的一組基變量。一組基變量。22121324323111,xxxxxxx,342413322221xxxxxx24343222,xxxx343332222111,xxxxxx5.1 運(yùn)輸

38、模型運(yùn)輸模型 Model of Transportation Problems Page 32 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 本節(jié)介紹了具有本節(jié)介紹了具有m個(gè)產(chǎn)地個(gè)產(chǎn)地n個(gè)銷(xiāo)地的平衡運(yùn)輸問(wèn)題時(shí)：個(gè)銷(xiāo)地的平衡運(yùn)輸問(wèn)題時(shí)：1.具有具有m+n1個(gè)基變量個(gè)基變量2. 閉回路的概念閉回路的概念3.怎樣判斷怎樣判斷m+n1個(gè)變量是否構(gòu)成一組基變量個(gè)變量是否構(gòu)成一組基變量5.1 運(yùn)輸模型運(yùn)輸模型 Model of Transportation Problems下一節(jié)：運(yùn)輸單純形法下一節(jié)：運(yùn)輸單純形法作業(yè)：教材作業(yè)：教材P124 T 5，6 建立數(shù)學(xué)模型建立數(shù)

39、學(xué)模型 Page 33 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 5.2 運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method Page 34 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 表上作業(yè)法表上作業(yè)法表上作業(yè)法的基本思想：表上作業(yè)法的基本思想： 先找一個(gè)初始方案先找一個(gè)初始方案; 根據(jù)判斷準(zhǔn)根據(jù)判斷準(zhǔn)則判斷是否最優(yōu)則判斷是否最優(yōu), 若不是，則對(duì)初始方案進(jìn)行調(diào)整、改進(jìn)、若不是，則對(duì)初始方案進(jìn)行調(diào)整、改進(jìn)、直至找到最優(yōu)方案直至找到最優(yōu)方案.步驟：步驟：分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo)平衡表及單位運(yùn)

40、價(jià)表分析實(shí)際問(wèn)題列出產(chǎn)銷(xiāo)平衡表及單位運(yùn)價(jià)表確定初始調(diào)運(yùn)方案確定初始調(diào)運(yùn)方案(最小元素法或最小元素法或vogel法法)求檢驗(yàn)數(shù)求檢驗(yàn)數(shù)(閉回路法或位勢(shì)法閉回路法或位勢(shì)法)所有檢驗(yàn)數(shù)所有檢驗(yàn)數(shù)0得到最優(yōu)方案得到最優(yōu)方案算出總的運(yùn)價(jià)算出總的運(yùn)價(jià)找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)用找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)用閉回路調(diào)整得出新的調(diào)整方案閉回路調(diào)整得出新的調(diào)整方案是是否否運(yùn)輸單純形法也稱(chēng)為表上作業(yè)法，直接在運(yùn)價(jià)表上求最優(yōu)解運(yùn)輸單純形法也稱(chēng)為表上作業(yè)法，直接在運(yùn)價(jià)表上求最優(yōu)解 Page 35 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 5.2.1初始基可行解初始基可行解1. 最小元素

41、法最小元素法 最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)Cij對(duì)應(yīng)的變量對(duì)應(yīng)的變量xij優(yōu)先賦值優(yōu)先賦值然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對(duì)應(yīng)的變量賦值并滿足約束，然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對(duì)應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個(gè)初始基可行解。依次下去，直到最后得到一個(gè)初始基可行解。jiijbax,min5.2 運(yùn)輸單純形法運(yùn)輸單純形法 Transportation Simplex Method Page 36 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 例例1 某食品公司經(jīng)銷(xiāo)的主要產(chǎn)品之一是糖果某食品公

42、司經(jīng)銷(xiāo)的主要產(chǎn)品之一是糖果, ,已知信息如下表已知信息如下表B1B2B3B4生產(chǎn)量生產(chǎn)量A13113107A219284A3741059銷(xiāo)售量銷(xiāo)售量3656門(mén)門(mén)加加運(yùn)價(jià)運(yùn)價(jià)市市部部工工廠廠(元元/t) 問(wèn)該公司應(yīng)如何調(diào)問(wèn)該公司應(yīng)如何調(diào)運(yùn)運(yùn), ,在滿足各門(mén)市部銷(xiāo)在滿足各門(mén)市部銷(xiāo)售需要的情況下售需要的情況下, ,使總使總的運(yùn)費(fèi)支出最少？的運(yùn)費(fèi)支出最少？ 表表1 產(chǎn)銷(xiāo)平衡表產(chǎn)銷(xiāo)平衡表表表2 單位運(yùn)價(jià)表單位運(yùn)價(jià)表解：解： B1B2B3B4產(chǎn)產(chǎn)量量A17A24A39銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 B1B2B3B4A1311310A21928A374105產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地2- 初始方案的確定初始方案的確

43、定 Page 37 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 確定初始方案確定初始方案1)最小元素法最小元素法(就近供應(yīng)就近供應(yīng)) 從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)處開(kāi)始確定供銷(xiāo)關(guān)系，從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)處開(kāi)始確定供銷(xiāo)關(guān)系，依次類(lèi)推，直到給出全部方案為止。依次類(lèi)推，直到給出全部方案為止。 B1B2B3B4產(chǎn)產(chǎn)量量A17A24A39銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 B1B2B3B4A1311310A21928A374105產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 3 1 6 4 3 3說(shuō)明：說(shuō)明： 1) 在調(diào)運(yùn)方案表中在調(diào)運(yùn)方案表中, 稱(chēng)填寫(xiě)數(shù)字處為稱(chēng)填寫(xiě)數(shù)字處為有數(shù)字的格有數(shù)字的格,

44、 它對(duì)應(yīng)運(yùn)它對(duì)應(yīng)運(yùn)輸問(wèn)題解中的輸問(wèn)題解中的基變量取值基變量取值; 稱(chēng)不填數(shù)字處為稱(chēng)不填數(shù)字處為空格空格, 它對(duì)應(yīng)解中的它對(duì)應(yīng)解中的非非基變量基變量. 因運(yùn)輸問(wèn)題中基變量數(shù)一般為因運(yùn)輸問(wèn)題中基變量數(shù)一般為m+n-1,故調(diào)運(yùn)方案中有數(shù)故調(diào)運(yùn)方案中有數(shù)字的格也為字的格也為m+n-1. Page 38 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 2) 當(dāng)選定最小元素后當(dāng)選定最小元素后, , 發(fā)現(xiàn)該元素所在行的產(chǎn)地產(chǎn)量發(fā)現(xiàn)該元素所在行的產(chǎn)地產(chǎn)量等于所在列的銷(xiāo)地的銷(xiāo)量等于所在列的銷(xiāo)地的銷(xiāo)量, , 這時(shí)在產(chǎn)銷(xiāo)平衡表上填一個(gè)數(shù)這時(shí)在產(chǎn)銷(xiāo)平衡表上填一個(gè)數(shù), ,運(yùn)價(jià)表上就要同時(shí)

45、劃去一行和一列，為了使調(diào)運(yùn)方案中的運(yùn)價(jià)表上就要同時(shí)劃去一行和一列，為了使調(diào)運(yùn)方案中的有數(shù)字格仍為有數(shù)字格仍為m+n-1個(gè)個(gè)，需要在同時(shí)劃去的該行或該列的，需要在同時(shí)劃去的該行或該列的任一空格位置補(bǔ)填一個(gè)任一空格位置補(bǔ)填一個(gè)0 0。 表表1 產(chǎn)銷(xiāo)平衡表產(chǎn)銷(xiāo)平衡表表表2 單位運(yùn)價(jià)表單位運(yùn)價(jià)表 B1B2B3B4產(chǎn)產(chǎn)量量A17A24A39銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 B1B2B3B4A131145A27738A312106產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 3 60000 Page 39 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 2)Vogel法法基本步驟：基本步驟：1)從運(yùn)價(jià)

46、表上分別找出每行與每列的最小的兩個(gè)元素之差從運(yùn)價(jià)表上分別找出每行與每列的最小的兩個(gè)元素之差;2)再?gòu)脑購(gòu)牟钪底畲蟛钪底畲蟮男谢蛄兄姓页龅男谢蛄兄姓页鲎钚∵\(yùn)價(jià)最小運(yùn)價(jià)確定供需關(guān)系和供確定供需關(guān)系和供應(yīng)數(shù)量應(yīng)數(shù)量.3)當(dāng)產(chǎn)地或銷(xiāo)地中有一方數(shù)量上供應(yīng)完畢或得到滿足時(shí)，劃當(dāng)產(chǎn)地或銷(xiāo)地中有一方數(shù)量上供應(yīng)完畢或得到滿足時(shí)，劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列，在重復(fù)上述步驟去運(yùn)價(jià)表中對(duì)應(yīng)的行或列，在重復(fù)上述步驟. Page 40 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem B1B2B3B4產(chǎn)產(chǎn)量量A17A24A39銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 B1B2B3B4A1311310A

47、21928A374105產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 2 16 5 3 3兩最小元素之差兩最小元素之差(1) (2) (3) (4)011兩兩最最小小元元素素之之差差(1)(2)(3)(4)2513012213012127612108(5)(5)2 Page 41 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 2-2 最優(yōu)性檢驗(yàn)與方案的調(diào)整最優(yōu)性檢驗(yàn)與方案的調(diào)整1)閉回路法閉回路法調(diào)運(yùn)方案中由一個(gè)空格和若干個(gè)有數(shù)字格的水平調(diào)運(yùn)方案中由一個(gè)空格和若干個(gè)有數(shù)字格的水平和垂直連線包圍成的封閉回路和垂直連線包圍成的封閉回路閉回路：閉回路：1)1)構(gòu)建閉回路構(gòu)建閉回路; ;求解檢驗(yàn)

48、數(shù)的方法：求解檢驗(yàn)數(shù)的方法： 令某非基變量取值為令某非基變量取值為1 1，通過(guò)變化原基，通過(guò)變化原基變量的值找出一個(gè)新的可行解，將其同原來(lái)的基可行解目變量的值找出一個(gè)新的可行解，將其同原來(lái)的基可行解目標(biāo)函數(shù)值的變化比較。標(biāo)函數(shù)值的變化比較。基本步驟：基本步驟：2)2)求空格對(duì)應(yīng)的檢驗(yàn)數(shù)求空格對(duì)應(yīng)的檢驗(yàn)數(shù)) )根據(jù)檢驗(yàn)數(shù)判定最優(yōu)性根據(jù)檢驗(yàn)數(shù)判定最優(yōu)性, ,若不是最優(yōu)解若不是最優(yōu)解, ,改進(jìn)方案改進(jìn)方案. . Page 42 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem (A1, B1)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) B1B2B3B4A1311310A21928A374105產(chǎn)

49、地產(chǎn)地銷(xiāo)地銷(xiāo)地3-3+2-1=1 B1B2B3B4A1A2A3產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地1檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表 B1B2B3B4產(chǎn)量產(chǎn)量A1437A2314A3639銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地(-1)(+1)(-1)(+1) B1B2B3B4產(chǎn)量產(chǎn)量A1437A2314A3639銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地(-1)(+1)(-1)(+1)(A2, B2)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)(-1)(+1)9-2+3-10+5-4=12 B1B2B3B4產(chǎn)量產(chǎn)量A1437A2314A3639銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地(-1)(+1)(+1)(-1)(+1)(-1)(A3, B1)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)7-1+2-3+1

50、0-5=1010112-1單位運(yùn)價(jià)表單位運(yùn)價(jià)表 Page 43 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 根據(jù)檢驗(yàn)數(shù)判定最優(yōu)性：根據(jù)檢驗(yàn)數(shù)判定最優(yōu)性：若檢驗(yàn)數(shù)表中所有數(shù)字若檢驗(yàn)數(shù)表中所有數(shù)字0, 給定的方案是最優(yōu)方案；給定的方案是最優(yōu)方案；若檢驗(yàn)數(shù)表中有數(shù)字若檢驗(yàn)數(shù)表中有數(shù)字0, 給定的方案可改進(jìn)；給定的方案可改進(jìn)；改進(jìn)方案的方法：改進(jìn)方案的方法： 從檢驗(yàn)數(shù)為負(fù)值的格出發(fā)從檢驗(yàn)數(shù)為負(fù)值的格出發(fā)(若有兩個(gè)以上若有兩個(gè)以上負(fù)檢驗(yàn)數(shù)時(shí)負(fù)檢驗(yàn)數(shù)時(shí), 從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)出發(fā)從絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)出發(fā)), 作一條除該作一條除該空格外其余頂點(diǎn)均為有數(shù)字格組成的閉回路

51、空格外其余頂點(diǎn)均為有數(shù)字格組成的閉回路. 在這條閉回在這條閉回路上路上, 按上面講的方法對(duì)運(yùn)量作最大可能的調(diào)整按上面講的方法對(duì)運(yùn)量作最大可能的調(diào)整. B1B2B3B4產(chǎn)量產(chǎn)量A1437A2314A3639銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地(+1)(-1)(+1)(-1) B1B2B3B4產(chǎn)量產(chǎn)量A1527A2314A3639銷(xiāo)量銷(xiāo)量3656產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地后面的過(guò)程略后面的過(guò)程略 Page 44 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 說(shuō)明：說(shuō)明： 若在閉回路調(diào)整中若在閉回路調(diào)整中,在需要減少運(yùn)量的地方有兩個(gè)以在需要減少運(yùn)量的地方有兩個(gè)以上相等的最小數(shù)，這

52、樣調(diào)整時(shí)原先空格處填上了這個(gè)最小上相等的最小數(shù)，這樣調(diào)整時(shí)原先空格處填上了這個(gè)最小數(shù)，把最小數(shù)的格之一變?yōu)榭崭?，其余均補(bǔ)添數(shù)，把最小數(shù)的格之一變?yōu)榭崭?，其余均補(bǔ)添0，補(bǔ)填，補(bǔ)填0的的格當(dāng)作有數(shù)字格看待，格當(dāng)作有數(shù)字格看待，使方案中有數(shù)字的格仍為使方案中有數(shù)字的格仍為m+n-1個(gè)個(gè).缺點(diǎn)：缺點(diǎn)： 當(dāng)一個(gè)運(yùn)輸問(wèn)題的產(chǎn)地和銷(xiāo)地?cái)?shù)很多時(shí)當(dāng)一個(gè)運(yùn)輸問(wèn)題的產(chǎn)地和銷(xiāo)地?cái)?shù)很多時(shí), ,計(jì)算檢驗(yàn)數(shù)的計(jì)算檢驗(yàn)數(shù)的工作量太繁重工作量太繁重. Page 45 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 2)位勢(shì)法位勢(shì)法 B1B2B3B4A1A2A3產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地316433用最小元

53、素法確定的初始調(diào)運(yùn)方案用最小元素法確定的初始調(diào)運(yùn)方案第一步第一步單位運(yùn)價(jià)表單位運(yùn)價(jià)表 B1B2B3B4A1311310A21928A374105產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地 仿照初始調(diào)運(yùn)方案表仿照初始調(diào)運(yùn)方案表作一新表作一新表, 將初始調(diào)運(yùn)方案表將初始調(diào)運(yùn)方案表中有數(shù)字格的地方換成單位中有數(shù)字格的地方換成單位運(yùn)價(jià)表中對(duì)應(yīng)的運(yùn)價(jià)運(yùn)價(jià)表中對(duì)應(yīng)的運(yùn)價(jià). B1B2B3B4A1310A212A345產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地第二步第二步 在新表的右面和下面增在新表的右面和下面增加一行和一列加一行和一列, ,并填上一些數(shù)字并填上一些數(shù)字, ,使表中的各個(gè)數(shù)剛好等于它所使表中的各個(gè)數(shù)剛好等于它所在行和列的這些新填寫(xiě)的數(shù)字在行和列

54、的這些新填寫(xiě)的數(shù)字之和之和. B1B2B3B4A1310A212A345產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地ui10-4vj1829第第i行的位勢(shì)行的位勢(shì)第第j列的位勢(shì)列的位勢(shì) Page 46 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem B1B2B3B4A1310A212A345產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地ui10-4vj1829位勢(shì)的求法位勢(shì)的求法 可先任意決定其中的一個(gè)可先任意決定其中的一個(gè), 然后推然后推導(dǎo)出其他位勢(shì)的數(shù)值導(dǎo)出其他位勢(shì)的數(shù)值先令先令u1=1，因?yàn)橐驗(yàn)閡1+ v4 =10, 所以所以v4 =9因?yàn)橐驗(yàn)閡1+ v3 =3, 所以所以v3 =2因?yàn)橐驗(yàn)閡3+ v4 =5,

55、所以所以u(píng)3 =-4因?yàn)橐驗(yàn)閡2+ v3 =2, 所以所以u(píng)2 =0因?yàn)橐驗(yàn)閡2+ v1 =1, 所以所以v1 =1因?yàn)橐驗(yàn)閡3+ v2 =4, 所以所以v2 =8 Page 47 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem 第三步第三步 求各空格的檢驗(yàn)數(shù)求各空格的檢驗(yàn)數(shù) B1B2B3B4uiA13101A2120A345-4vj1829產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地(-1)(+1)(+1)(-1)(+1)(-1)表示表示(A3, B1)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)31 1231053131 c )()()()()(123231414331vuvuvuvuvuc )(1331vuc )(jiijijvuc 一般地一般地 Page 48 Chapter 5 運(yùn)輸與指派問(wèn)題運(yùn)輸與指派問(wèn)題T&A Problem B1B2B3B4A1310A212A345產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地ui10-4vj1829 B1B2B3B4A1311310A21928A374105產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地行列位勢(shì)行列位勢(shì)相加填入相加填入相應(yīng)空格相應(yīng)空格