運(yùn)籌學(xué)運(yùn)輸問題(補(bǔ)充)

1、運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research1 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題（TP，Transportation Problem）： 11.mnijijab其中2022-5-101運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research供需-運(yùn)費(fèi)表： 問：應(yīng)如何組織運(yùn)輸，才能既滿足供需關(guān)系，又使得運(yùn)費(fèi)最??？2022-5-102運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research的貨物的數(shù)量，運(yùn)往收點(diǎn)從發(fā)點(diǎn)解：令jiijBAx njmi, 2 , 1, 2 , 11111() min,1,2,. .,1,2,0,1,2,;1,2,mnijijijnijijmijjiijTPfc

2、xxa imstxbjnxim jn2022-5-103運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations ResearchTmnmmnnxxxxxxxxxx),(212222111211令mnmmnncccccccccc212222111211Tnmbbbaaad),(21212022-5-104運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research1001001000100100100010010011110000000001110000000001112121212222111211nmmmmDxxxxxxxxxmnmmnn則()min. .0TTPfc xDxdstx2022-5-105運(yùn)運(yùn) 籌

3、籌 學(xué)學(xué) Operations Research基：.1)(BnmDmnnm階非奇異子矩陣的任一基的構(gòu)造：.1得一個(gè)基個(gè)線性無關(guān)的列向量即下的矩陣中選取中刪去任一行，再從剩從 nmD結(jié)論結(jié)論：運(yùn)輸問題總有最優(yōu)解：運(yùn)輸問題總有最優(yōu)解.2022-5-106運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research在實(shí)際計(jì)算時(shí)，鑒于運(yùn)輸問題的特殊性質(zhì)，其求解過程并不借助于單純形表，而是借助于運(yùn)輸表來實(shí)現(xiàn). 2022-5-107運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research格子格子表（集）： 對應(yīng)關(guān)系：ijijijPDxt的列向量變量格子令,TS .|StPDijijS規(guī)定：.)()(關(guān)相中的

4、各列向量線性無關(guān)相線性無格子集SDS2022-5-108運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research.1|記作：稱為基本格子集，的線性無關(guān)的格子集定義SnmS).()()(1|ijijijijijijtxtxBTPnmtPD非基變量為，且基變量為的一個(gè)基即得矩陣去掉一個(gè)多余的行個(gè)列向量作成的中的是基本格子集時(shí)，當(dāng)令ijijtxdDx, 0即得基解01dBx2022-5-109運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research2 初始基可行解 運(yùn)輸問題的求解過程并不象一般線性規(guī)劃問題一樣借助運(yùn)輸問題的求解過程并不象一般線性規(guī)劃問題一樣借助于單純形表，而是借助于運(yùn)輸表來實(shí)現(xiàn)；但于

5、單純形表，而是借助于運(yùn)輸表來實(shí)現(xiàn)；但其算法在理論基其算法在理論基礎(chǔ)、基本思想、算法步驟等各方面都和單純形法是一致的礎(chǔ)、基本思想、算法步驟等各方面都和單純形法是一致的. 供需平衡型運(yùn)輸問題：njjmiiba112022-5-1010運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research一.西北角法基本思想：優(yōu)先安排運(yùn)輸表中的西北角處的格子（即編號小的格子）對應(yīng)的發(fā)點(diǎn)與收點(diǎn)之間的運(yùn)輸業(yè)務(wù).使用條件：已知d2022-5-1011運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research2022-5-1012運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research1()3,4,(15,25,5,5,1

6、5,15,10) ,().TTPmndTP例 設(shè)中，求的一個(gè)基可行解解：基本格子集為,342423221211tttttt2022-5-1013運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research相應(yīng)的基本可行解為, 5, 5,15, 5,10, 5342423221211xxxxxx0ijx其它二 最小元素法基本思想：優(yōu)先安排運(yùn)輸表中的單位運(yùn)費(fèi)最小的格子對應(yīng)的發(fā)點(diǎn)與收點(diǎn)之間的運(yùn)輸業(yè)務(wù)（當(dāng)最小單位運(yùn)費(fèi)不唯一時(shí)，可任選其一）.使用條件：已知dc,2022-5-1014運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research2022-5-1015運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Rese

7、arch例2 求（TP）的一個(gè)基本可行解，其中 , 4, 3nm,)10,15,15, 5 , 5 ,25,15(Td 18161462097121120610c解：基本格子集為,312423141211tttttt2022-5-1016運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research相應(yīng)的基可行解為, 5,10,15, 0,15, 0312423141211xxxxxx0ijx其它Ex: 求平衡型運(yùn)輸問題：5183,(12,14,4,9,10,11) ,241367Tmndc的基初始可行解（用兩種方法）.2022-5-1017運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research三

8、 沃格爾（Vogel）法基本思想：基本思想：若若罰數(shù)罰數(shù)的值不大，當(dāng)不能按最小單位運(yùn)價(jià)安排的值不大，當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大；反之，如果罰數(shù)的值很大，運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大；反之，如果罰數(shù)的值很大，不按最小運(yùn)價(jià)組織運(yùn)輸就會造成很大損失，故應(yīng)盡量按不按最小運(yùn)價(jià)組織運(yùn)輸就會造成很大損失，故應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸。最小單位運(yùn)價(jià)安排運(yùn)輸。使用條件：使用條件：dc,步驟2022-5-1018運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research1. 分別計(jì)算運(yùn)輸表中運(yùn)價(jià)的行罰數(shù)和列罰數(shù)，并分別填入分別計(jì)算運(yùn)輸表中運(yùn)價(jià)的行罰數(shù)和列罰數(shù)，并分別填入2. 運(yùn)輸表右邊和下邊的罰

9、數(shù)欄里；運(yùn)輸表右邊和下邊的罰數(shù)欄里；3. 2. 從所有罰數(shù)中找出最大者，選中罰數(shù)所在行（或列）中從所有罰數(shù)中找出最大者，選中罰數(shù)所在行（或列）中4. 運(yùn)價(jià)最小對應(yīng)的格，填入盡可能大的運(yùn)輸量；運(yùn)價(jià)最小對應(yīng)的格，填入盡可能大的運(yùn)輸量；5. 3. 當(dāng)供應(yīng)量已用完（或需求量已滿足），劃去相應(yīng)行（或當(dāng)供應(yīng)量已用完（或需求量已滿足），劃去相應(yīng)行（或6. 列）；列）；7. 4. 重復(fù)上述步驟，直到所有行和列都被劃掉重復(fù)上述步驟，直到所有行和列都被劃掉.2022-5-1019運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research3 最優(yōu)性的檢驗(yàn)對運(yùn)輸問題njmixnjbxmiaxtsxcfTPijmijij

10、injijminjijij, 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 1,. .min: )(11112022-5-1020運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research,1,2,;1,2,iju v imjn引入對偶變量，得對偶問題為11() max. .,1,2,;1,2,mniijjijijijDPhaub vstuvc imjn2022-5-1021運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research()TPB的一個(gè)基本格子集 ，對應(yīng)一個(gè)基 ，相應(yīng)的檢驗(yàn)數(shù)為ijijijTijijTBijtcPycPBcr,1TTBnmBcvvuuy)(111其中2022

11、-5-1022運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research.),(),(,00,212111vuyvvvvuuuutcvuuuvuTmTmijijjiji，即，得，解可令是自由變量，定義().uTPv 稱為關(guān)于基本子集 的位勢格2022-5-1023運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations ResearchijijjiijnmijijTTijijTijijTijijTBijtcvucjivvvuuucPvucPvucPycPBcr,00100100),(),(21211于是，檢驗(yàn)數(shù)為2022-5-1024運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research小結(jié)小結(jié)先求位勢：iji

12、jjitcvuu,01再求檢驗(yàn)數(shù)：ijijjiijtcvur,2022-5-1025運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research例1 求（TP）的一個(gè)基本可行解，其中 , 4, 3nm,)10,15,15, 5 , 5 ,25,15(Td 18161462097121120610c解：基本格子集為,312423141211tttttt2022-5-1026運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research相應(yīng)的基可行解為, 5,10,15, 0,15, 0312423141211xxxxxx0ijx其它求位勢：求檢驗(yàn)數(shù)： 2022-5-1027運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operati

13、ons Research 同單純形法一樣，若所有檢驗(yàn)數(shù)均非負(fù)，則當(dāng)前的基可行解即為最優(yōu)解；否則，應(yīng)改進(jìn)之（轉(zhuǎn)軸），以使之更優(yōu).,2121132222111是一個(gè)閉回路則稱互異，互異，其中中的諸格子排列為，若可將設(shè)定義kkjijijijijijijjjiiittttttTkkk閉回路的特點(diǎn)：任意兩個(gè)相鄰的格子的行指標(biāo)相同時(shí)，閉回路的特點(diǎn)：任意兩個(gè)相鄰的格子的行指標(biāo)相同時(shí)，其列指標(biāo)必不相同；列指標(biāo)相同時(shí)，其行指標(biāo)必不相其列指標(biāo)必不相同；列指標(biāo)相同時(shí)，其行指標(biāo)必不相同同. .即任意兩個(gè)相鄰格子的行（列）指標(biāo)不能同時(shí)相即任意兩個(gè)相鄰格子的行（列）指標(biāo)不能同時(shí)相同，也不能同時(shí)不同同，也不能同時(shí)不同. .

14、 2022-5-1028運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research如.)(emmapqpqpqtttTPL，且唯一一個(gè)閉回路中必存在，則的一個(gè)基本格子集，是設(shè),333124211413tttttt2022-5-1029運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research例1（續(xù)）,312423141211tttttt取33ttpq取32ttpq2022-5-1030運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research.,)(1h和個(gè)格子應(yīng)分屬的處在同一行，列的兩；：和劃分為按如下規(guī)則將中的閉回路為，相應(yīng)的基本開行解為的一個(gè)基本格子集為設(shè)pqpqpqtttxTPT令ijij

15、tx |minrkx)(rkpqtt().TPx則仍是的一個(gè)基本格子集，且 是相應(yīng)的基本可行解2022-5-1031運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research例1（續(xù)）,312423141211tttttt取32ttpq劃分:2022-5-1032運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research3155,15minx修正：2022-5-1033運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research4 算法步驟max2022-5-1034運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research例 求解運(yùn)輸問題：4, 3nmTd)10,15,15, 5 , 5 ,25,15(18161462097121120610c解：作運(yùn)輸表，并利用最小元素法解之.2022-5-1035運(yùn)運(yùn) 籌籌 學(xué)學(xué) Operations Research基本格子集為,343124231412tttttt基本可行解為, 0, 5,10,15, 0,15343124231412xxxxxx0ijx其余求位勢和