1、會(huì)計(jì)學(xué)1運(yùn)輸運(yùn)輸(ynsh)問題數(shù)學(xué)模型問題數(shù)學(xué)模型第一頁，共52頁。第1頁/共52頁第二頁，共52頁。第2頁/共52頁第三頁，共52頁。 銷地產(chǎn)地1 2 n產(chǎn)量 12m A 1A2Am銷量B1 B2 BNn 第3頁/共52頁第四頁，共52頁。 銷地 產(chǎn)地 1 2 n 1 2 m C11 c12 c1n C21 c22 c2n cm1 cm2 cmn 第4頁/共52頁第五頁，共52頁。 0)23(,2, 1)13(,2, 1.min1111ijnjijijmijijminjijijxmiaxnjbxtsxcz第5頁/共52頁第六頁，共52頁。行行nmvvvuuuxxxxxxxxxnmmnmmn

2、n1111111111111111112121212222111211第6頁/共52頁第七頁，共52頁。njminjmiimiijnjijjaxxb111111第7頁/共52頁第八頁，共52頁。第8頁/共52頁第九頁，共52頁。第9頁/共52頁第十頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 表3-3 單位(dnwi)運(yùn)價(jià)表 第10頁/共52頁第十一頁，共52頁。 銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 7 4 9 銷量 3 6 5 6 第11頁/共52頁第十二頁，共52頁。這與一般線性規(guī)劃

3、問題不同(b tn)。產(chǎn)銷平衡的運(yùn)輸問題總是存在可行解。因有minjjidba11必存在xij0，i=1，m，j=1，n這就是可行(kxng)解。又因0 xijmin(aj，bj)故運(yùn)輸問題必存在最優(yōu)解。第12頁/共52頁第十三頁，共52頁。這方法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小。一直到給出初始基可行解為止。以例1進(jìn)行討論。第一步：從表3-3中找出最小運(yùn)價(jià)為1，這表示先將A2的產(chǎn)品供應(yīng)給B1。因a2b1，A2除滿足B1的全部需要外，還可多余(duy)1噸產(chǎn)品。在表3-4的(A2，B1)的交叉格處填上3。得表3-5。并將表3-3的B1列運(yùn)價(jià)劃去。得表3-

4、6。第13頁/共52頁第十四頁，共52頁。銷地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 7 4 9 銷量 3 6 5 6 銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 第14頁/共52頁第十五頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 1 7 4 9 銷量 3 6 5 6 銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 第15頁/共52頁第十六頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1

5、A2 A3 3 6 4 1 3 3 7 4 9 銷量 3 6 5 6 第16頁/共52頁第十七頁，共52頁。第17頁/共52頁第十八頁，共52頁。1111jmijieeP因當(dāng)給定的值后，將劃去第i1行或第j1列，即其后的系數(shù)列向量中再不出現(xiàn)ei1或em+j1，因而 不可能用解中的其他(qt)向量的線性組合表示。類似地給出第二個(gè)，第(m+n-1)個(gè)。這(m+n-1)個(gè)向量都不可能用解中的其他(qt)向量的線性組合表示。故這(m+n-1)個(gè)向量是線性獨(dú)立的。 11jix11jiP第18頁/共52頁第十九頁，共52頁。第19頁/共52頁第二十頁，共52頁。第20頁/共52頁第二十一頁，共52頁。銷

6、地 加工廠 B1 B2 B3 B4 行差額 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 1 列差額 2 5 1 3 第21頁/共52頁第二十二頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 6 7 4 9 銷量 3 6 5 6 第22頁/共52頁第二十三頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 行差額 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差額 2 1 3 第23頁/共52頁第二十四頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 5

7、 2 1 3 7 4 9 銷量 3 6 5 6 第24頁/共52頁第二十五頁，共52頁。第25頁/共52頁第二十六頁，共52頁。第26頁/共52頁第二十七頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 第27頁/共52頁第二十八頁，共52頁。ujuslslkikjmusmusmlkmlkmijmuusmsmllkmkmijmiijPPPPPeeeeeeeeeeeeeeeeeeeeeeP)()()()()(第28頁/共52頁第二十九頁，共52頁。第29頁/共52頁第三十頁，共52頁。第30頁/共52頁第三十一

8、頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 3 (+1) 11 3 4(-1) 10 3 7 A2 1 3(-1) 9 2 1(+1) 8 4 A3 7 4 6 10 5 3 9 銷量 3 6 5 6 第31頁/共52頁第三十二頁，共52頁。空格 閉 回 路 檢驗(yàn)數(shù) (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12) (22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-

9、(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1 10 12 當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說明原方案不是(b shi)最優(yōu)解，要繼續(xù)改進(jìn)，改進(jìn)方法見2.3小節(jié)。第32頁/共52頁第三十三頁，共52頁。第33頁/共52頁第三十四頁，共52頁。),;,(21211nmBvvvuuuBC)(1jiijijBijijvucPBCc由單純形法得知所有基變量的檢驗(yàn)(jinyn)數(shù)等于0。即 Bjivucjiij,. 0)(第34頁/共52頁第三十五頁，共52頁。第35頁/共52頁第三十六頁，共52頁。Njivucjiijij,).( 這就可以從已知的ui

10、，vj值中求得。這些(zhxi)計(jì)算可在表格中進(jìn)行。 第36頁/共52頁第三十七頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 1 4 3 2 10 5 第37頁/共52頁第三十八頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 ui A1 A2 A3 1 4 3 2 10 5 0 -1 -5 vj 2 9 3 10 先令u1=0，然后按ui+vj=cij， i，jB相繼地確定(qudng)ui，vj。由表3-17可見，當(dāng)u1=0時(shí)，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10時(shí)，由u3+v4=5可得u3=-5，以此類推可確定(qud

11、ng)所有的ui，vj的數(shù)值。 第38頁/共52頁第三十九頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 ui A1 3 1=3-(0+2) 11 2=11-(0+9) 3 0=3-(0+3) 10 0=10-(0+10) 0 A2 1 0=1-(-1+2) 9 1=9-(-1+9) 2 0=2-(-1+3) 8 -1=8-(-1+10) -1 A3 7 10=7-(-5+2) 4 0=4-(-5+9) 10 12=10-(-5+3) 5 0=5-(-5+10) -5 vj 2 9 3 10 表3-18 中還有負(fù)檢驗(yàn)(jinyn)數(shù)。說明未得最優(yōu)解，還可以改進(jìn)。第39頁/共52頁第四十頁

12、，共52頁。第40頁/共52頁第四十一頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 4(+1) 1(-1) 3(-1) (+1) 3 7 4 9 銷量 3 6 5 6 第41頁/共52頁第四十二頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 第42頁/共52頁第四十三頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 0 9 2 2 1 12 第43頁/共52頁第四十四頁，共52頁。第44頁/共52頁第四十五頁，共52頁。第45頁/共52頁第四十六頁，共52頁。銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 2 1 6 5 3 3 7 4 9 銷量 3 6 5 6 第46頁/共52頁第四十七頁，共52頁。第47頁/共52頁第四十八頁，共52頁。