运输问题数学模型实用教案VIP

1、会计学1运输运输(ynsh)问题数学模型问题数学模型第一页，共52页。第1页/共52页第二页，共52页。第2页/共52页第三页，共52页。 销地产地1 2 n产量 12m A 1A2Am销量B1 B2 BNn 第3页/共52页第四页，共52页。 销地 产地 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)运价表 第10页/共52页第十一页，共52页。 销 地 加工厂 B1 B2 B3 B4 产量 A1 A2 A3 7 4 9 销量 3 6 5 6 第11页/共52页第十二页，共52页。这与一般线性规划

3、问题不同(b tn)。产销平衡的运输问题总是存在可行解。因有minjjidba11必存在xij0，i=1，m，j=1，n这就是可行(kxng)解。又因0 xijmin(aj，bj)故运输问题必存在最优解。第12页/共52页第十三页，共52页。这方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2b1，A2除满足B1的全部需要外，还可多余(duy)1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-

4、6。第13页/共52页第十四页，共52页。销地 加工厂 B1 B2 B3 B4 产量 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 产量 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 产量 A1

5、A2 A3 3 6 4 1 3 3 7 4 9 销量 3 6 5 6 第16页/共52页第十七页，共52页。第17页/共52页第十八页，共52页。1111jmijieeP因当给定的值后，将划去第i1行或第j1列，即其后的系数列向量中再不出现ei1或em+j1，因而 不可能用解中的其他(qt)向量的线性组合表示。类似地给出第二个，第(m+n-1)个。这(m+n-1)个向量都不可能用解中的其他(qt)向量的线性组合表示。故这(m+n-1)个向量是线性独立的。 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 产量 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 产量 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 产量 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 产量 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页。空格 闭 回 路 检验数 (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 当检验数还存在负数时，说明原方案不是(b shi)最优解，要继续改进，改进方法见2.3小节。第32页/共52页第三十三页，共52页。第33页/共52页第三十四页，共52页。),;,(21211nmBvvvuuuBC)(1jiijijBijijvucPBCc由单纯形法得知所有基变量的检验(jinyn)数等于0。即 Bjivucjiij,. 0)(第34页/共52页第三十五页，共52页。第35页/共52页第三十六页，共52页。Njivucjiijij,).( 这就可以从已知的ui

10、，vj值中求得。这些(zhxi)计算可在表格中进行。 第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可见，当u1=0时，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10时，由u3+v4=5可得u3=-5，以此类推可确定(qud

11、ng)所有的ui，vj的数值。 第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 中还有负检验(jinyn)数。说明未得最优解，还可以改进。第39页/共52页第四十页

12、，共52页。第40页/共52页第四十一页，共52页。销 地 加工厂 B1 B2 B3 B4 产量 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 产量 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 产量 A1 A2 A3 2 1 6 5 3 3 7 4 9 销量 3 6 5 6 第46页/共52页第四十七页，共52页。第47页/共52页第四十八页，共52页。