線性規(guī)劃的運(yùn)輸問題運(yùn)輸問題

課題：工學(xué)院計(jì)算機(jī)系２００４年10月線性規(guī)劃的運(yùn)輸問題第一頁，共二十八頁。1運(yùn)輸問題的類型；運(yùn)輸問題§3.1§3.21產(chǎn)銷平衡運(yùn)輸問題的求解步驟；課堂內(nèi)容2產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型；一知識(shí)點(diǎn)回顧3西北角法；2最小元素法；二新學(xué)知識(shí)點(diǎn)§3.21沃格爾法（差值法）；2解的最優(yōu)性檢驗(yàn)；3解的改進(jìn)；第二頁，共二十八頁。方法三沃格爾法（也稱差值法）一、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：從運(yùn)價(jià)表上，計(jì)算各行各列中次小單位運(yùn)價(jià)和最小單位運(yùn)價(jià)之間的差值（行罰數(shù)hi，列罰數(shù)kj）。優(yōu)先取最大差值的行或列中最小運(yùn)價(jià)位于的格來確定運(yùn)輸關(guān)系，直到求出初始方案。運(yùn)價(jià)表3.2運(yùn)輸問題的表上作業(yè)法第三頁，共二十八頁。一、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：解3231311011212hikj3.2運(yùn)輸問題的表上作業(yè)法第四頁，共二十八頁。一、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，費(fèi)用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）3.2運(yùn)輸問題的表上作業(yè)法第五頁，共二十八頁。

要判斷一個(gè)調(diào)運(yùn)方案是否已是最優(yōu)，就要判斷方案所對應(yīng)的初始可行解是否最優(yōu)。在單純形法中，根據(jù)非基變量的檢驗(yàn)數(shù)進(jìn)行判別，若檢驗(yàn)數(shù)中沒有正值，則已求得最優(yōu)，運(yùn)輸問題是特殊線性規(guī)劃問題，其也可以通過檢驗(yàn)數(shù)的判別進(jìn)行最優(yōu)解的檢驗(yàn)。3.2運(yùn)輸問題的表上作業(yè)法求解運(yùn)輸問題的表上作業(yè)法的步驟：二解的最優(yōu)性檢驗(yàn)根據(jù)初始調(diào)運(yùn)表求檢驗(yàn)數(shù)的方法：閉回路法對偶變量法（位勢法）第六頁，共二十八頁。求解運(yùn)輸問題的表上作業(yè)法的步驟：在初始調(diào)運(yùn)方案表中，從任意空格出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格90度轉(zhuǎn)彎，繼續(xù)行進(jìn)，總能回到原來空格。這個(gè)封閉的曲線稱為閉回路。閉回路的概念3.2運(yùn)輸問題的表上作業(yè)法可以證明：每個(gè)空格對應(yīng)著唯一的閉回路(略)。1閉回路法第七頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法閉回路第八頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法閉回路第九頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法閉回路第十頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法表中（x11,x12,x22,x23,x31,x33）不能構(gòu)成一條閉回路，因?yàn)閤33不是拐角點(diǎn)。X44X42非閉回路第十一頁，共二十八頁。1閉回路法空格Xij(非基變量)的檢驗(yàn)數(shù)=第奇數(shù)次拐角點(diǎn)運(yùn)價(jià)之和減去第偶數(shù)次拐角點(diǎn)運(yùn)價(jià)之和空格X21的檢驗(yàn)數(shù)=6-5+4-4=

13.2運(yùn)輸問題的表上作業(yè)法1解的最優(yōu)性檢驗(yàn)方法之一第十二頁，共二十八頁?？崭馲14的檢驗(yàn)數(shù)=閉回路法5-4+5-4=23.2運(yùn)輸問題的表上作業(yè)法2第十三頁，共二十八頁。空格X31的檢驗(yàn)數(shù)=閉回路法6-5+4-5+8-7=13.2運(yùn)輸問題的表上作業(yè)法1第十四頁，共二十八頁。檢驗(yàn)數(shù)都為正值,原方案不是最優(yōu)解(與對偶單純形法一致)教材中δij＝偶拐角點(diǎn)運(yùn)價(jià)之和減去奇拐角點(diǎn)運(yùn)價(jià)之和。3.2運(yùn)輸問題的表上作業(yè)法閉回路法111552第十五頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法

對初始調(diào)運(yùn)方案,定義一組新的變量（對偶）ui和vj(i=1,2,…m;j=1,2,…n)對于基變量Xij有：ui+vj=Cij稱ui與vj為相應(yīng)的各行與各列的位勢。對偶變量法（位勢法）第十六頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法對偶變量法（位勢法）u1+v1=由上知：六個(gè)方程組成的方程組中含有七個(gè)變量。為了求出7個(gè)解，一般令u1=0。-106586286u1+v2=5u2+v2=4u2+v3=7u2+v4=5u3+v4=第十七頁，共二十八頁。對偶變量法（位勢法）3.2運(yùn)輸問題的表上作業(yè)法空格（非基變量）的檢驗(yàn)數(shù)=（ui+vj)-Cij與閉合回路法相同。115521第十八頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法從一個(gè)方案調(diào)整到最優(yōu)方案的過程，就是單純形法的過程。選擇檢驗(yàn)數(shù)（一般取最大）為正值的空格所對應(yīng)的變量為進(jìn)基變量，在進(jìn)基變量的回路中，比較奇數(shù)拐角點(diǎn)的運(yùn)量，選擇一個(gè)具有最小運(yùn)量的基變量作為出基變量，進(jìn)基變量的運(yùn)量=min(奇數(shù)拐角點(diǎn)的運(yùn)量)。調(diào)整方案解的改進(jìn)第十九頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法解的改進(jìn)選擇檢驗(yàn)數(shù)最大的（A1,B3）或（A3,B3）調(diào)整最小運(yùn)量=min(2,3)=2√

√

11152565860-12第二十頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法解的改進(jìn)最小運(yùn)量=2,奇拐點(diǎn)減2,偶拐點(diǎn)加2,得到新的方案。原總運(yùn)費(fèi)=241新總運(yùn)費(fèi)=+5*2+4*2+7*3=80（元）+3*2+4*4+7*1=70（元）6*2+5*1+8*36*2+5*1+8*3第二十一頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法解的改進(jìn)繼續(xù)求檢驗(yàn)數(shù)66515-30130674第二十二頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法解的改進(jìn)繼續(xù)調(diào)整運(yùn)量131選擇（A2，B1）（檢驗(yàn)數(shù)最大）調(diào)整最小運(yùn)量=min(1,2)=1√

√

新總運(yùn)費(fèi)=+3*3+6*1+4*1=64（元）4*4+5*1+8*3原總運(yùn)費(fèi)=+3*2+6*2+4*6=70（元）4*4+5*1+8*3第二十三頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法解的改進(jìn)選擇（A1，B4）（檢驗(yàn)數(shù)最大）調(diào)整最小運(yùn)量=min(1,1)=1新總運(yùn)費(fèi)=+4*1+4*2+5*0=61（元）3*3+4*4+8*3原總運(yùn)費(fèi)=+6*1+4*2+5*1=64（元）3*3+4*4+8*3√

√

120011-1-6366371-20第二十四頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法-3-2-3012解的改進(jìn)選擇（A3，B3）（檢驗(yàn)數(shù)最大）調(diào)整最小運(yùn)量=min(3,3)=3新總運(yùn)費(fèi)=+3*0+4*4+5*3=55（元）4*2+4*4+5*0原總運(yùn)費(fèi)=+3*3+4*1+8*3=61（元）4*2+4*4+5*0√

√

4033334014第二十五頁，共二十八頁。3.2運(yùn)輸問題的表上作業(yè)法計(jì)算檢驗(yàn)數(shù):空格的檢驗(yàn)數(shù)全為非正，此時(shí)是最優(yōu)解。-2-3-2-1-3-2解的改進(jìn)3334012最優(yōu)調(diào)運(yùn)方案:最小運(yùn)費(fèi)＝4*4+4*2+4*4+5*3＝55(元)X21=2,X14=4,X22=4,X33=3第二十六頁，共二十八頁。知識(shí)點(diǎn)回顧3.2運(yùn)輸問題的表上作業(yè)法產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法沃格爾法2解的最優(yōu)性檢驗(yàn)3解的改進(jìn)閉回路法對偶變量法（位勢法）確定換入的非基變量；確定換出的基變量；GOTO21編制初始調(diào)運(yùn)方案（運(yùn)輸問題的初始基可行解）最小元素法西北角法第二十七頁，共二十八頁。內(nèi)容總結(jié)課題：。1沃格爾法（差值法）。方法三沃格爾法（也稱差值法）。求解運(yùn)輸問題的表上作業(yè)法的步驟：。求解運(yùn)輸問題的表上作業(yè)法的步驟：。從運(yùn)價(jià)表上，計(jì)算各行各列中次小單位運(yùn)價(jià)和最小單位運(yùn)價(jià)之間的差值（行罰數(shù)hi，列罰數(shù)kj）。優(yōu)先取最大差值的行或列中最小運(yùn)價(jià)位于的格來確定運(yùn)輸關(guān)系，直到求出