工学运输问题PPT学习教案

1、会计学1 工学运输问题工学运输问题 销售商销售商 供应商供应商 Boston Chicago St. Louis Lexington 生产能生产能 力力 (吨吨) Cleveland 3 2 7 6 5,000 Bedford 7 5 2 3 6,000 York 2 5 4 5 2,500 需求量需求量(吨吨) 6,000 4,000 2,000 1,500 每吨运输成本(/吨) 第1页/共40页 供应商 1 Cleveland 2 Bedford 3 York 2 Chicago 1 Boston 3 St. Louis 4 Lexington 销售商 5,000 2,500 6,000

2、6,000 1,500 2,000 4,000 3 2 7 6 2 7 5 3 4 2 5 5 第2页/共40页 Min Z= 3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34 S. t.x11+x12+x13+x14 5000 x21+x22+x23+x24 6000 x31+x32+x33+x34 2500 x11+x21+x31 = 6000 x12+x22+x32 = 4000 x13+x23+x33 = 2000 x14+x24+x34 = 1500 xij0 , 第3页/共40页 m 1i n 1j ijij c

3、=zMin x m,1,2,=i sx n 1j iij n ,1,2,=j dx m 1i jij n,1,=jm;,1,2,=i 0,xij st. 供应： 需求： 第4页/共40页 d s n 1j j m 1i i 基变量的个数=m+n-1 第5页/共40页 第6页/共40页 供应量供应量 3276 7523 2545 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland5,000 Bedford6,000 York2,500 6,0004,0002,0001,500 5000 1000 0 1000 0 5000 4000 0 10001

4、000 0 1000 1000 0 15001500 第7页/共40页 供应量供应量 3276 7523 2545 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland5,000 Bedford6,000 York2,500 6,0004,0002,0001,500 4000 0 1000 2500 20001500 3500 0 0 2500 2500 4000 00 2500 1000 第8页/共40页 检验数：非基变量增加一个单位引起的成本变化量 第9页/共40页 供应量供应量 3276 7523 2545 需求量需求量 BostonChic

5、agoSt. Louis Lexington Cleveland5,000 Bedford6,000 York2,500 6,0004,0002,0001,500 第10页/共40页 初始基本可行解： 供应量供应量 10004000 7523 250020001500 2545 2500 需求量需求量6,0004,0002,0001,500 York 6,000Bedford 2,500 65,00027Cleveland3 BostonChicagoSt. Louis Lexington 基本可行解 第11页/共40页 检验数的计算： 供应量供应量 10004000 +175-123 250

6、020001500 2545 2500 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland -1 32 +1 765,000 York 6,000Bedford 2,500 6,0004,0002,0001,500 9 闭回路 检验数 第12页/共40页 初始基本可行解与检验数： 供应量供应量 10004000 7523 250020001500 2545 2500 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland32765,000 York 6,000Bedford 2,500 6,0004,0

7、002,0001,500 74 -1 97 7 基本可行解 检验数 第13页/共40页 10004000 -7 +523 250020001500 2545 2500 BostonChicagoSt. Louis Lexington Cleveland+3-627 York Bedford -1 35001500 7523 250020001500 2545 2500 BostonChicagoSt. Louis Lexington Cleveland3627 York Bedford =2500 基本可行解的调整： 第14页/共40页 检验数的重新计算： 35001500 7523 2500

8、20001500 2545 2500 York Bedford 627Cleveland3 BostonChicagoSt. Louis Lexington 8 6 6 4 1 6 检验数均大于0，得最优解 ： 第15页/共40页 检验数：目标函数的系数减去对偶变量之和 第16页/共40页 m 1i n 1j ijij c=zMin x m,1,2,=i sx n 1j iij n ,1,2,=j dx m 1i jij n,1,=jm;,1,2,=i 0,xij st. 供应： 需求： 对偶变量 ui 对偶变量 vj 第17页/共40页 m 1i n 1j jjii vdus=Max w n

9、,1,2,j m;,1,2,=i cv u ijji n,1,=j m;,1,2,=i v,u ji 无约束 st. 对偶变量 xij 第18页/共40页 原问题检验数： ij=cij-(ui+vj) i=1,2,m; j=1,2,n 特别对于m+n-1个基变量，有 ij=cij-(ui+vj)=0 第19页/共40页 供应量供应量 3276 7523 2545 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland5,000 Bedford6,000 York2,500 6,0004,0002,0001,500 第20页/共40页 初始基本可行解：

10、 供应量供应量 10004000 7523 250020001500 2545 2500 需求量需求量 BostonChicagoSt. Louis Lexington Cleveland32765,000 York 6,000Bedford 2,500 6,0004,0002,00015,000 基本可行解 第21页/共40页 位势计算： 10004000 7523 250020001500 2545 2500 u1 u2 u3 v1v2v3v4 York Bedford 627 Cleveland 3 BostonChicagoSt. Louis Lexington 3vu 2vu 2vu

11、 7vu 2vu 3vu 42 32 13 12 21 11 1v 2;v 1;u 4;u 2;v 3;v 0;u 4 3 3 2 2 1 1 第22页/共40页 10004000 7523 250020001500 2545 2500 Lexington v2=2v3=-2v4=-1 BostonChicagoSt. Louis 3276 Bedford u1=0 u2=4 u3=-1 v1=3 York Cleveland -1 97 477 检验数的计算： 第23页/共40页 保证基变量的个数为m+n-1 第24页/共40页 供应量供应量 3276 7523 2545 需求量需求量5,0

12、004,0002,0002,500 York2,500 Bedford6,000 Cleveland5,000 BostonChicagoSt. Louis Lexington 500 0 0 0 第25页/共40页 -转换为平衡问题 第26页/共40页 销售商销售商 供应商供应商 A B C D 生产能力生产能力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙丙 2 5 4 5 4,500 需求量需求量(吨吨) 6,000 4,000 2,000 1,500 销售商销售商 供应商供应商 A B C D E 生产能力生产能力 (吨吨) 甲甲 3 2 7 6 0

13、 5,000 乙乙 7 5 2 3 0 6,000 丙丙 2 5 4 5 0 4,500 需求量需求量 (吨吨) 6,000 4,000 2,000 1,500 2000 供过于求的处理 第27页/共40页 销售商销售商 供应商供应商 A B C D 生产能力生产能力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙丙 2 5 4 5 2,500 需求量需求量(吨吨) 6,000 4,000 2,000 3,500 销售商销售商 供应商供应商 A B C D 生产能力生产能力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙丙 2

14、 5 4 5 2,500 丁丁 0 0 0 0 2000 需求量需求量 (吨吨) 6,000 4,000 2,000 1,500 供不应求的处理 第28页/共40页 第29页/共40页 转运问题-例 生产厂 1 Denver 2 Atlanta 6 Miami 5 Detroit 7 Dallas 8 New Orleans 零售店 600 400 200 300 350 150 3 2 3 6 4 3 1 1 6 2 5 4 3 Kansas City 4 Louisville 6 4 批发部 第30页/共40页 MinZ=2x 13 +3x 14 +3x 23 +x 24 +2x 35 +

15、6x 36 +3x 37 +6x 38 +4x 45 +4x 46 +6x 47 +5x 48 +4x 28 +x 78 S. t. x 13 +x 14 600 x 23 +x 24 +x 28 400 -x 13 -x 23 +x 35 +x 36 +x 37 +x 38 =0 -x 14 -x 24 +x 45 +x 46 +x 47 +x 48 =0 x 35 +x 45 =200 x 36 +x 46 =150 x 37 +x 47 -x 78 =350 x 38 +x 48 +x 28 +x 78 =300 x ij 0for all i, j 供应 转运 需求 线性规划模型 第3

16、1页/共40页 转运问题分析与建模要点 纯供应节点有供应量Si，无需求量，无转运功能 生产厂 1 Denver600 3 2 供应量 Out) (Arcs ,iji Sx 第32页/共40页 纯需求节点无供应量，有需求量dj，无转运功能 5 Detroit 零售店 200 需求量 2 4 In) (Arcs ,jji dx 第33页/共40页 供应节点有供应量，无需求量，具有转运功能 生产厂 1 Denver600 3 2 供应量 4 Out) (ArcsIn) (Arcs ,ijiji Sxx 第34页/共40页 需求节点无供应量，有需求量dj，具有转运功能 7 Dallas 350 1 6 3 销售商 需求量 Out) (ArcsIn) (Arcs ,jjiji dxx 第35页/共40页 纯转运节点无供应量，无需求量，仅具有转运功能 2 3 6 3 2 3 Kansas City 6 批发部 Out) (ArcsIn) (Arcs , 0 jiji xx 第36页/共40页 一般转运节点有供应量Si，有需求量di，又具有转运功 能 26 3 3 Kansas City 5 600 200 1需求量 供应量 Out) (ArcsIn) (Arcs ,iijiji dSxx 第37页/共40页 转运问题的应用生产与库存计划 季季 度