第三章 運(yùn)輸問題 — 數(shù)學(xué)模型及其解法

1、13.2 運(yùn)輸問題的求解方法運(yùn)輸問題的求解方法 約束條件非常有規(guī)律，技術(shù)系數(shù)非約束條件非常有規(guī)律，技術(shù)系數(shù)非 0 即即 1 基變量的個(gè)數(shù)遠(yuǎn)小于決策變量的個(gè)數(shù)基變量的個(gè)數(shù)遠(yuǎn)小于決策變量的個(gè)數(shù) 采用表上作業(yè)法，稱為位勢法和踏石法采用表上作業(yè)法，稱為位勢法和踏石法 運(yùn)算中涉及兩個(gè)表：運(yùn)費(fèi)表和產(chǎn)銷平衡表運(yùn)算中涉及兩個(gè)表：運(yùn)費(fèi)表和產(chǎn)銷平衡表(分配表分配表)銷銷地地產(chǎn)產(chǎn)量量運(yùn)運(yùn)量量12nai產(chǎn)產(chǎn)地地1x11x12x1na12x21x22x2na2 mxm1xm2xmnam銷銷量量 bjb1b2bn銷銷 地地運(yùn)運(yùn) 費(fèi)費(fèi)12n產(chǎn)產(chǎn) 地地1w11w12w1n2w21w22w2n mwm1wm2wmn2 3.2.

2、1 尋找初始可行解的方法尋找初始可行解的方法 1、西北角法、西北角法 從從 x11開始分配，從西北向東南方向逐個(gè)分配開始分配，從西北向東南方向逐個(gè)分配 xij 的分配公式的分配公式列待分物資量列已分配的總量行尚余物資量行已分配的總量 ) ( ) (minjjbiiaxjiij例例3.2.1銷銷地地產(chǎn)產(chǎn)量量運(yùn)運(yùn)費(fèi)費(fèi)1234ai產(chǎn)產(chǎn)地地120113652591021031874115銷銷量量bj3312123銷地產(chǎn)量運(yùn)量1234ai產(chǎn)地15210315銷量 bj331212 例例3.2.1 西北角法西北角法銷地產(chǎn)量運(yùn)量1234ai產(chǎn)地13x125210315銷量 bj331212銷地產(chǎn)量運(yùn)量123

3、4ai產(chǎn)地13252x2210315銷量 bj331212銷地產(chǎn)量運(yùn)量1234ai產(chǎn)地132521x2310315銷量 bj331212銷地產(chǎn)量運(yùn)量1234ai產(chǎn)地1325219103x3315銷量 bj331212銷地產(chǎn)量運(yùn)量1234ai產(chǎn)3315銷量 bj331212銷地產(chǎn)量運(yùn)量1234ai產(chǎn)地132521910331215銷量 bj3312123141205)(67ijijijxwxfnm個(gè)基變量有4 2、最低費(fèi)用法、最低費(fèi)用法采用最小費(fèi)用優(yōu)先分配的原則，看一步采用最小費(fèi)用優(yōu)先分配的原則，看一步編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij2011(3)6x135

4、I5910210187411215331212編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij20113655II5910210187(4)1x331215331212編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij20113655III59(10)2334101874131215331212f(x)=121，比，比西北角法低西北角法低845 3、運(yùn)費(fèi)差額法、運(yùn)費(fèi)差額法采用最大差額費(fèi)用采用最大差額費(fèi)用(即利用每行或列中最小費(fèi)用與次最小之即利用每行或列中最小費(fèi)用與次最小之間的差額中選最大間的差額中選最大)優(yōu)先分配的原則，看兩步優(yōu)先分配的原則，看兩步編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij201136

5、35I5910233101874131513211331212f(x)=98，比，比最低費(fèi)用法最低費(fèi)用法又低了又低了23編編 號(hào)號(hào)運(yùn)運(yùn) 費(fèi)費(fèi) 表表 wij分分 配配 表表 xij20113635II59102737101874131513211331212編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij20113635III591027371018741351513415331212編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表wij分分配配表表xij201136855IV59102737101874133751513-53312126 3.2.2 利用位勢法檢驗(yàn)分配方案是否最優(yōu)利用位勢法檢驗(yàn)分配方案是否最優(yōu) 不采用單純型

6、法，如何獲得不采用單純型法，如何獲得xij的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 找到原問題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件，求出找到原問題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件，求出對(duì)應(yīng)對(duì)偶問題的解，若該對(duì)偶問題的解非可行，則原對(duì)應(yīng)對(duì)偶問題的解，若該對(duì)偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解問題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解0, 2 , 1 , 2 , 1 )(min1111ijjmiijnjiijminjijijxnjbxmiaxxwxfnjmivuwvuvbuavugjiijjinjjjmiii, 2, 1 , 2 , 1,),(max11不限7332313222212112111222322211

7、1131211232322222121131312121111vbxx vb xxvbxxuaxxxuaxxxxwxwxwxwxwxwmin 不限v,v,v,u,uwv u wvu wvu wv uwvuwvuvbvbvbuauamax 3212123322222211213311221111133221122118 位勢法的原理位勢法的原理為滿足互補(bǔ)松弛條件，原問題中為滿足互補(bǔ)松弛條件，原問題中xij被選為基變量，即被選為基變量，即xij 0，則要求對(duì)偶問題中則要求對(duì)偶問題中ui+vj=wij，即該行的松弛變量為，即該行的松弛變量為0共有共有m+n 1個(gè)基變量個(gè)基變量xij ，因此可得，因此

8、可得m+n 1個(gè)等式個(gè)等式 ui+vj=wijm+n 1個(gè)等式只能解出個(gè)等式只能解出 m+n 1個(gè)個(gè) ui 和和 vj ，而一共有，而一共有m+n個(gè)個(gè) ui 和和 vj ，但可令任一個(gè)，但可令任一個(gè)ui 或或 vj =0，從而解出其它，從而解出其它 m+n 1個(gè)個(gè)的值；這就是的值；這就是位勢法位勢法令令 zij= ui + vj ，其相當(dāng)原問題，其相當(dāng)原問題xij的的機(jī)會(huì)費(fèi)用機(jī)會(huì)費(fèi)用若對(duì)所有非基變量有若對(duì)所有非基變量有 zij wij 0，即，即 ui + vj wij，表明當(dāng)前，表明當(dāng)前ui 和和 vj 是對(duì)偶問題的可行解，由互補(bǔ)松弛定理可知當(dāng)前是對(duì)偶問題的可行解，由互補(bǔ)松弛定理可知當(dāng)前m+

9、n 1個(gè)基變量個(gè)基變量xij 是最優(yōu)解，否則是最優(yōu)解，否則從從 zij wij 0 中找最大者，對(duì)應(yīng)中找最大者，對(duì)應(yīng) xij 就是就是入變量入變量9 3.2.3 踏石法踏石法1、找入變量、找入變量 從從 zij wij 0 中找最大者，對(duì)應(yīng)中找最大者，對(duì)應(yīng) xij 就是入變量就是入變量2、以、以 xij 為起點(diǎn)，尋找由原基變量構(gòu)成的為起點(diǎn)，尋找由原基變量構(gòu)成的閉合回路閉合回路 該回路只在每個(gè)拐角各有一個(gè)基變量，中間允許穿越某些基該回路只在每個(gè)拐角各有一個(gè)基變量，中間允許穿越某些基變量；因此，閉合回路中必有偶數(shù)個(gè)變量變量；因此，閉合回路中必有偶數(shù)個(gè)變量(包括包括 xij )，且回路，且回路中每行

10、每列只有兩個(gè)變量中每行每列只有兩個(gè)變量3、求入變量、求入變量 xi*j* 的最大值及新基變量的解的最大值及新基變量的解 從從 xij出發(fā)，沿任一個(gè)方向?qū)芈饭战巧系幕兞恳来藰?biāo)出發(fā)，沿任一個(gè)方向?qū)芈饭战巧系幕兞恳来藰?biāo)“ ”和和“+”，表示，表示“ ”和和“+” xij ，從而迭代后仍滿足分配的，從而迭代后仍滿足分配的平衡平衡 標(biāo)有標(biāo)有“ ”的變量中最小者就是的變量中最小者就是出變量出變量xi*j* ，對(duì)應(yīng)，對(duì)應(yīng) xi*j*的值就的值就是所是所求入變量求入變量 xij 的最大值的最大值 標(biāo)有標(biāo)有“ ”的變量減去的變量減去 xi*j*，標(biāo)有標(biāo)有“+”的變量加上的變量加上 xi*j* 4、用位勢

11、法求新基變量的檢驗(yàn)數(shù)、用位勢法求新基變量的檢驗(yàn)數(shù) 若所有若所有 zij wij 0，則達(dá)到最優(yōu)，算法停止；否則返回，則達(dá)到最優(yōu)，算法停止；否則返回 110 例例3.2.1 踏石法，以最低費(fèi)用法所得初始解開始踏石法，以最低費(fèi)用法所得初始解開始編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表zij / wijui分分配配表表xij-2 / 20 2 / 1130 / 6355I59107 / 210334 x2410-1 / 18 3 / 74143+12 15vj 5 10 3331212編編號(hào)號(hào)運(yùn)運(yùn)費(fèi)費(fèi)表表 zij / wijui分分配配表表xij3 / 20 7 / 1130 / 6 255II595 / 102033 4+104 / 1