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

1、課題：線性規(guī)劃的運(yùn)輸問(wèn)題11 運(yùn)輸問(wèn)題的類型；運(yùn)輸問(wèn)題3.13.21 產(chǎn)銷平衡運(yùn)輸問(wèn)題的求解步驟；課堂內(nèi)容2 產(chǎn)銷平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型；一 知識(shí)點(diǎn)回顧3 西北角法；2 最小元素法；二 新學(xué)知識(shí)點(diǎn)3.21 沃格爾法（差值法）；2 解的最優(yōu)性檢驗(yàn)；3 解的改進(jìn)；2方法三 沃格爾法（也稱差值法）一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問(wèn)題的表上作業(yè)法的步驟： 從運(yùn)價(jià)表上，計(jì)算各行各列中次小單位運(yùn)價(jià)和最小單位運(yùn)價(jià)之間的差值（行罰數(shù)hi ，列罰數(shù)kj）。優(yōu)先取最大差值的行或列中最小運(yùn)價(jià)位于的格來(lái)確定運(yùn)輸關(guān)系，直到求出初始方案。運(yùn)價(jià)表3.2 運(yùn)輸問(wèn)題的表上作業(yè)法3一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問(wèn)題的表上作業(yè)法的步

2、驟：解3231311011212hikj3.2 運(yùn)輸問(wèn)題的表上作業(yè)法4一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問(wè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)輸問(wèn)題的表上作業(yè)法5 要判斷一個(gè)調(diào)運(yùn)方案是否已是最優(yōu)，就要判斷方案所對(duì)應(yīng)的初始可行解是否最優(yōu)。在單純形法中，根據(jù)非基變量的檢驗(yàn)數(shù)進(jìn)行判別，若檢驗(yàn)數(shù)中沒(méi)有正值，則已求得最優(yōu)，運(yùn)輸問(wèn)題是特殊線性規(guī)劃問(wèn)題，其也可以通過(guò)檢驗(yàn)數(shù)的判別進(jìn)行最優(yōu)解的檢驗(yàn)。3.2 運(yùn)輸問(wèn)題的表上作業(yè)法求解運(yùn)輸問(wèn)題的表上作業(yè)法的步驟：二 解

3、的最優(yōu)性檢驗(yàn)根據(jù)初始調(diào)運(yùn)表求檢驗(yàn)數(shù)的方法：閉回路法對(duì)偶變量法（位勢(shì)法）6求解運(yùn)輸問(wèn)題的表上作業(yè)法的步驟： 在初始調(diào)運(yùn)方案表中，從任意空格出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格90度轉(zhuǎn)彎，繼續(xù)行進(jìn)，總能回到原來(lái)空格。這個(gè)封閉的曲線稱為閉回路。閉回路的概念3.2 運(yùn)輸問(wèn)題的表上作業(yè)法可以證明：每個(gè)空格對(duì)應(yīng)著唯一的閉回路(略)。1 閉回路法73.2 運(yùn)輸問(wèn)題的表上作業(yè)法閉回路83.2 運(yùn)輸問(wèn)題的表上作業(yè)法閉回路93.2 運(yùn)輸問(wèn)題的表上作業(yè)法閉回路103.2 運(yùn)輸問(wèn)題的表上作業(yè)法表中（x11,x12,x22,x23,x31,x33）不能構(gòu)成一條閉回路，因?yàn)閤33不是拐角點(diǎn)。X44X42非閉回

4、路111 閉回路法空格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)輸問(wèn)題的表上作業(yè)法1解的最優(yōu)性檢驗(yàn)方法之一12空格X14的檢驗(yàn)數(shù)=閉回路法5-4+5-4= 23.2 運(yùn)輸問(wèn)題的表上作業(yè)法213空格X31的檢驗(yàn)數(shù) =閉回路法6-5+4-5+8-7=13.2 運(yùn)輸問(wèn)題的表上作業(yè)法114檢驗(yàn)數(shù)都為正值,原方案不是最優(yōu)解(與對(duì)偶單純形法一致)教材中ij偶拐角點(diǎn)運(yùn)價(jià)之和減去奇拐角點(diǎn)運(yùn)價(jià)之和。3.2 運(yùn)輸問(wèn)題的表上作業(yè)法閉回路法111552153.2 運(yùn)輸問(wèn)題的表上作業(yè)法 對(duì)初始調(diào)運(yùn)方案,定義一組新的變量（對(duì)偶）ui和vj

5、(i=1,2,m;j=1,2,n)對(duì)于基變量Xij有： ui+vj=Cij稱ui與vj為相應(yīng)的各行與各列的位勢(shì)。對(duì)偶變量法（位勢(shì)法）163.2 運(yùn)輸問(wèn)題的表上作業(yè)法對(duì)偶變量法（位勢(shì)法）u1+v1=由上知：六個(gè)方程組成的方程組中含有七個(gè)變量。為了求出7個(gè)解，一般令u1=0。-106586286u1+v2=5u2+v2=4u2+v3=7u2+v4=5u3+v4=17對(duì)偶變量法（位勢(shì)法）3.2 運(yùn)輸問(wèn)題的表上作業(yè)法空格（非基變量）的檢驗(yàn)數(shù) =（ui+vj)-Cij與閉合回路法相同。115521183.2 運(yùn)輸問(wèn)題的表上作業(yè)法 從一個(gè)方案調(diào)整到最優(yōu)方案的過(guò)程，就是單純形法的過(guò)程。 選擇檢驗(yàn)數(shù)（一般取最

6、大）為正值的空格所對(duì)應(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)193.2 運(yùn)輸問(wèn)題的表上作業(yè)法解的改進(jìn)選擇檢驗(yàn)數(shù)最大的（A1,B3 ）或（A3,B3 ）調(diào)整最小運(yùn)量=min(2,3)=2 11152565860-12203.2 運(yùn)輸問(wè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*3213.2 運(yùn)輸問(wèn)題的表上作

7、業(yè)法解的改進(jìn)繼續(xù)求檢驗(yàn)數(shù)66515-30130674223.2 運(yùn)輸問(wè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*3233.2 運(yùn)輸問(wè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-20243.2 運(yùn)輸問(wè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 4033334014253.2 運(yùn)輸問(wè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*355(元)X21=2,X14=4,X22=4,X33=326知識(shí)