运输问题模型PPT学习教案

1、会计学1设某种物资有设某种物资有m个产地个产地A1,A2,Am，和和n个销地个销地B1,B2,Bn,其中其中Ai的产量的产量为为ai,Bjai,Bj的销量为的销量为bjbj，产地产地Ai运往销地运往销地Bj的单位运价的单位运价Cij,i=1,2,m;j=1,2,n.求尽可能满足销地需求且总费用最小的求尽可能满足销地需求且总费用最小的运输方案。运输方案。第1页/共64页ijx解：设产地Ai运往销地Bj的运量为第2页/共64页jjiiba第3页/共64页njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min1111第4页/共64页

2、jjiiba第5页/共64页njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min1111第6页/共64页jjiiba第7页/共64页njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min1111第8页/共64页第9页/共64页第10页/共64页第11页/共64页第12页/共64页第13页/共64页第14页/共64页B1B2B3B4产量A13 2 9 10 7 9,6A2 1 3 4 2 5A3 8 4 2 5 7销量 3 ,0 8 4 6第15页/共64页B

3、1B2B3B4产量A13 26 9 10 7 9,6,0A2 1 3 4 2 5A3 8 4 2 5 7销量 3 ,0 8,2 4 6第16页/共64页B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 4 2 5,3A3 8 4 2 5 7销量 3 ,0 8,2,0 4 6第17页/共64页B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 4 2 5 7销量 3 ,0 8,2,0 4,1 6第18页/共64页B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 4

4、1 2 5 7,6销量 3 ,0 8,2,0 4,1,0 6第19页/共64页第20页/共64页B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 41 26 5 7,6销量 3 ,0 8,2,0 4,1,0 6第21页/共64页第22页/共64页第23页/共64页B1B2B3B4产量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 4 2 5 7销量 3 ,0 8 4 6第24页/共64页B1B2B3B4产量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 44 2 5 7，3销量 3 ,0 8 4，0 6

5、第25页/共64页B1B2B3B4产量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 8 44 2 5 7，3销量 3 ,0 8 4，0 6,4第26页/共64页B1B2B3B4产量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4第27页/共64页B1B2B3B4产量A1 2 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第28页/共64页第29页/共64页B1B2B3B4产量A1 25 9 104

6、 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第30页/共64页第31页/共64页B1B2V2=9B3B4V4=7产量A1u1=0 25 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第32页/共64页B1B2V2=9B3B4V4=7产量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第33页/共64

7、页B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第34页/共64页第35页/共64页B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0-4 25 93 104 7 9,5A2u2=-53 1-1 3 2 42 2 5,2,0A3u3=-57 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第36页/共64页目标可以减少，说明当前目标可以减少，说明当前解不是最优解解不是最优解第

8、37页/共64页第38页/共64页第39页/共64页B1B2B3B4产量A1u1=03 25 93 101 7 9,5A2 1-1 3 2 45 2 5,2,0A37 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第40页/共64页第41页/共64页B1v1=2B2v2=9B3B4v4=7产量A1u1=03 25 93 101 7 9,5A2u2=-5 1-1 3 2 45 2 5,2,0A3u3=-57 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第42页/共64页B1v1=2B2v2=9B3V3=7B4v4=7产量A1u1=03 2

9、5 93 101 7 9,5A2u2=-54 1-1 3 2 45 2 5,2,0A3u3=-511 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第43页/共64页目标可以减少，说明当前目标可以减少，说明当前解不是最优解解不是最优解第44页/共64页第45页/共64页第46页/共64页第47页/共64页B1B2B3B4产量A1u1=03 2 93 106 7 9,5A24 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第48页/共64页第49页/共64页B1v1=2B2B3B4v4=7产量A1

10、u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第50页/共64页B1v1=2B2v2=8B3B4v4=7产量A1u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A3u3=-411 83 44 23 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第51页/共64页B1v1=2B2v2=8B3V3=6B4v4=7产量A1u1=03 2 1 94 106 7 9,5A2u2=-54 15 3 3 40 2 5,2,0A

11、3u3=-410 83 44 22 5 7,3,0销量 3 ,0 8,5 4，0 6,4,0第52页/共64页第53页/共64页第54页/共64页设加班生产情况下每套设备成本设加班生产情况下每套设备成本比正常生产时高比正常生产时高70万元万元,每套设备每套设备不及时交货积压一年的维护费用不及时交货积压一年的维护费用为为40万元。该厂现库存有万元。该厂现库存有2套设备，套设备，希望第三年末完成合同要求后还希望第三年末完成合同要求后还能储存能储存1台设备，问如何安排生产，台设备，问如何安排生产，才能使总成本最低。才能使总成本最低。第55页/共64页上述生产计划问题的数学模型为：上述生产计划问题的数

12、学模型为：第56页/共64页 3,2,1,0,0,04333124322.min3333232313133222212122111113333232223221312111312113213131313131jizyxzyzyzyxzyzyxzyxzyzzyyzzzyyyxxxtszbyaxczijijjijijijijijijjjj第57页/共64页550006406000580540500)(ijaA第58页/共64页620007106700650610570)(ijbBC=（0，40 ，80）第59页/共64页第60页/共64页x(1)+y(1,1)+z(1,1)=3;x(2)+y(1,2)+z(1,2)+y(2,2)+z(2,2)=3;x(3)+y(1,3