《運輸問題》PPT課件

《《運輸問題》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、運籌學(xué)OPERATIONALRESEARCH第三章運輸問題1課件第一節(jié)運輸問題及其數(shù)學(xué)模型一、運輸問題的典型形式及其數(shù)學(xué)模型1.引例2課件求最小運費的運輸方案銷地產(chǎn)地B1B2B3產(chǎn)量A1645300A2655200銷量1501502003課件minZ=6x11+4x12+5x13+6x21+5x22+5x23x11+x12+x13=300x21+x22+x23=200x11+x21=150x12+x22=150x13+x23=200xij?04課件A1AmB1B2Bna1……cijA2a2ambnb2b1……求最

2、小運費的運輸方案2.典型的運輸問題：5課件銷地產(chǎn)地B1B2…Bn產(chǎn)量A1a1A2a2……Amam銷量b1b2…bnc11c12cm1c21c22c2nc1ncmncm26課件銷地產(chǎn)地B1B2…Bn產(chǎn)量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam銷量b1b2…bnc11c12cm1c21c22c2nc1ncmncm27課件minZ=6x11+4x12+5x13+6x21+5x22+5x23x11+x12+x13=300x21+x22+x23=200x11+x21=

3、150x12+x22=150x13+x23=200xij?03.運輸問題的數(shù)學(xué)模型8課件i=1,2j=1,2,3xij?09課件i=1,2,…,mj=1,2,…,nxij?0典型運輸問題的數(shù)學(xué)模型10課件二、運輸問題數(shù)學(xué)模型的特點：運輸問題一定有最優(yōu)解；運輸問題約束條件的系數(shù)矩陣：x11+x12+x13=300x21+x22+x23=200x11+x21=150x12+x22=150x13+x23=200xij?011課件x11x12x13x21x22x23111111111112個3個12課件x11+x12+…

4、+x1n=a1x21+x22+…+x2n=a2………………………………xm1+xm2+…+xmn=amx11+x21+xm1=b1x12+x22+xm2=b2………………………………x1n+x2n+xmn=bnxij?013課件x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1………………………………11…11…111…1………………………………11…1mn14課件系數(shù)矩陣的特點：（1）約束條件的系數(shù)矩陣的元素只有兩個：0、1。（2）元素xij對應(yīng)于每一個變量在前m個約束方程中(第i個

5、方程中)出現(xiàn)一次，在后n個約束方程中（第m+j個方程中）也出現(xiàn)一次。（3）產(chǎn)銷平衡問題為等式約束。（4）產(chǎn)銷平衡問題中各產(chǎn)地產(chǎn)量之和與各銷售地點的銷量之和相等。15課件3.運輸問題基變量的個數(shù)：m+n-1個16課件第二節(jié)表上作業(yè)法一、表上作業(yè)法的基本思想和步驟：1.基本思想：同單純形法的基本思想基本可行解是否為最優(yōu)解換基結(jié)束YN17課件2.表上作業(yè)法的步驟（1）尋找初始基可行解；最小元素法、西北角法、沃格爾法（2）求出非基變量檢驗數(shù)（空格檢驗數(shù)），判斷是否為最優(yōu)解；閉回路法、位勢法（3）換基改進(jìn)，找到新的基可行解

6、閉回路調(diào)整法（4）重復(fù)（2）（3）18課件二、確定初始基可行解（一）最小元素法：19課件銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量8141214484125210391146811求運費最小的運輸方案。例題（P82例1）20課件412521039114681102銷地產(chǎn)地B1B2B3B4產(chǎn)量A110616A28210A314822銷量81412144800600621課件4125210391146811銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量814121448（二）西北角法22課件4

7、125210391146811銷地產(chǎn)地B1B2B3B4產(chǎn)量A18816A26410A381422銷量814121448（二）西北角法23課件（三）沃格爾法伏格爾法思路：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而，對差額最大處，就應(yīng)當(dāng)采用最小運費調(diào)運24課件罰數(shù)=次小費用-最小費用1、在運價表中分別計算出各行、列的行罰數(shù)和列罰數(shù)，并填入該表的最右列和最下行。2、從行或列差額中選出最大者，選擇它所在行或列的最小元素。按類似于最小元素法

8、優(yōu)先供應(yīng)，劃去相應(yīng)的行或列。3、對表中未劃去的元素重復(fù)1，2步，直至所有的行和列被劃掉為止。沃格爾法基本步驟：25課件4125210391146811銷地產(chǎn)地B1B2B3B4產(chǎn)量行罰數(shù)A1124160A282101A3148221銷量814121448列罰數(shù)251326課件三、最優(yōu)解的判別(一)閉回路法閉回路：從空格出發(fā)，遇到數(shù)字格可以旋轉(zhuǎn)90度，最后回到空格所構(gòu)成的回路