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

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

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

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

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

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

6、法，如何獲得不采用單純型法，如何獲得xij的檢驗數(shù)的檢驗數(shù) 找到原問題的基礎(chǔ)可行解，保持互補松弛條件，求出找到原問題的基礎(chǔ)可行解，保持互補松弛條件，求出對應(yīng)對偶問題的解，若該對偶問題的解非可行，則原對應(yīng)對偶問題的解，若該對偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達到最優(yōu)解問題的解不是最優(yōu)解；否則，達到最優(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 位勢法的原理位勢法的原理為滿足互補松弛條件，原問題中為滿足互補松弛條件，原問題中xij被選為基變量，即被選為基變量，即xij 0，則要求對偶問題中則要求對偶問題中ui+vj=wij，即該行的松弛變量為，即該行的松弛變量為0共有共有m+n 1個基變量個基變量xij ，因此可得，因此

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

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

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

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