IE案例分析(一)

1、IE案例分析案例分析王晓光武汉理工大学机电工程学院案例一：旅游线路规划案例一：旅游线路规划 某风景区有五个景点见图所示，S为景区入口，T为景区出口，A，B，C，D，E为五个景点。其中各个景点距离见图标。案例一：旅游线路规划案例一：旅游线路规划有如下问题需要解决：电信公司需要安装电话线路，联通各个景点和进出口，则最小线路安装是什么？现在，在入口S处有一个游览车，一游客有急事需要到出口T，问游览车如何行使可以使游客尽快到达出口？1. 现在要在以上各个地方中的某一处修建一所医务中心，问应建在何处，能使各个景点都离他最近？案例一：旅游线路规划案例一：旅游线路规划有如下问题需要解决：现在要在以上各地方中

2、的某一处修建一所会议中心，已知各个景点的员工分别是40,25,45,30,20,35,50，那么会议中心应建在何处，能使各个景点的员工走的总路程最短？4. 为了保护园区野生生态环境，现在规定每条线路上观光旅游车的数量是一定的，见下图，其中每条弧上的数字为通行车辆容量，那么如何在不违背每条线路旅游车辆数目限制下寻求最多的车辆通行？案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划电信公司需要安装电话线路，联通各个景点和进出口，则最小线路安装是什么？n显然，第一个问题属于最小树生成问题，采用避圈法。n任选点S开始，离点S最近未连通是点，连通n离点或者点A最近未连通是点

3、B（和点相连通），连通Bn离点，或点B最近未连通是点C（和点连通），连通n离点S，B或者点C最近未连通是（和点B连通），连通BE案例一：旅游线路规划案例一：旅游线路规划n离点，A，B，C或者点E最近未连通是点D（和点E连通），连通EDn未连通的只有点（和点最近连通），连通DT。如图案例一：旅游线路规划案例一：旅游线路规划软件实现软件实现n 在inQSB软件的“Network Modeling”模块中，最小树的生成就采用上面的避圈法。对于上述问题，在此模块中新建一个最小树的生成文件。如图所示案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据

4、。点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划现在，在入口S处有一个游览车，一游客有急事需要到出口T，问游览车如何行使可以使游客尽快到达出口？n根据题意知道这是一个网络最短路问题题。下面介绍采用迪克斯托标号法进行求解。基本思路是逐点求解。例如如果是从到的最短路径，那么从到这条线路的任何一点都应该是最短的，不然就还存在其他最短路。案例一：旅游线路规划案例一：旅游线路规划n具体解题步骤：首先从始点开始，令P(S)=为永久标号，其余各点赋予标号T(i)（，）n第一次迭代：计算与接近的各点的临时标号nT(A)=minT(A),P(S)+W(SA)=min,

5、2=2nT(B)=minT(B),P(S)+W(SB)=min,5=5nT(C)=minT(C),P(S)+W(SC)=min,4=4案例一：旅游线路规划案例一：旅游线路规划n在以上T标号中T(A)=2为最小，故将A的P标号改为2即P(A)=2;n第二次迭代：计算与A接近的各个点的临时标号nT(D)=minT(D),P(A)+W(AD)=min,9=9nT(B)=minT(B),P(A)+W(AB)=min5,4=4案例一：旅游线路规划案例一：旅游线路规划n在以上T标号中，T(B)=4为最小，故将B的永久标号改为P(B)=4 n第三次迭代：计算与B接近的各个点的临时标号nT(D)=minT(D

6、),P(B)+W(BD)=min9,8=8nT(E)=minT(E),P(B)+W(BE)=min,7=7nT(C)=minT(C),P(S)+W(BC)=min4,5=4案例一：旅游线路规划案例一：旅游线路规划n在以上T标号中，T(C)=4为最小，故P(C)=4；n第四次迭代：计算与C想接近的E的临时标号nT(E)=minT(E),P(C)+W(CE)=min7,8=7n所以E的永久标号为P(E)=7；案例一：旅游线路规划案例一：旅游线路规划n第五次迭代：计算与E接近的各点的临时标号nT(D)=minT(D),P(E)+W(ED)=min8,8=8nT(T)=minT(T),P(E)+W(E

7、T)=min,14=14n故以上T标号中T(D)=8为最小，故P(D)=8案例一：旅游线路规划案例一：旅游线路规划n第六次迭代：计算出口点T的标号nT(T)= minT(T),P(D)+W(DT)=min14,13=13n根据以上步骤，我们便可以知道最短路径为：nSABEDT 或者nSABDT案例一：旅游线路规划案例一：旅游线路规划软件实现软件实现n 在inQSB软件的“Net Problem Specification”模块中，新建一个最短路模型：案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据。案例一：旅游线路规划案例一：旅游线路规

8、划点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划点击“Solve” 求解。案例一：旅游线路规划案例一：旅游线路规划以上过程是一个迭代过程，也可以用程序实现。案例一：旅游线路规划案例一：旅游线路规划现在要在风景区中的某一处修建一所医务中心，问应建在何处，能使各个景点都离他最近？n第三个问题属于一个中心布点问题。一般思路是要求距离网络中最远的被服务点距离尽可能小。分别求个点的最短路： 案例一：旅游线路规划案例一：旅游线路规划点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划点击“Solve” 求解。案例一：旅游线路

9、规划案例一：旅游线路规划点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划点击“Solve” 求解。案例一：旅游线路规划案例一：旅游线路规划点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划点击“Solve” 求解。案例一：旅游线路规划案例一：旅游线路规划D=(dij)dij=maxSABCDETS 0244871313A2023651111B42014399C4310541010D86450158E75341067(min)T131191056013案例一：旅游线路规划案例一：旅游线路规划现在要在风景区中的某一处

10、修建一所会议中心，已知各个景点的员工分别是40,25,45,30,20,35,50，那么会议中心应建在何处，能使各个景点的员工走的总路程最短？n该问题属于求解网络的重心问题。设qi为vi的权重（i=1 , 2,-n）令h(vj)= （j=1 , 2, -n）n若minh（vj）=h(vr)，则称点vr为网络的重心。ni 1qidij案例一：旅游线路规划案例一：旅游线路规划qidijSABCDETS080160160320280520A5005075150125275B18090045180135405C12090300150120300D16012080100020100E2451751051

11、40350210T6505504505002503000H(Vj)14051105875102010859801810案例一：旅游线路规划案例一：旅游线路规划利用“Microsoft Eecel” 计算。可见会议中心建在B点，所有员工走的的总距离最短。案例一：旅游线路规划案例一：旅游线路规划为了保护园区生态环境，规定每条线路上观光旅游车的数量是一定的，见下图，其中每条弧上的数字为容许通行车辆的数量。案例一：旅游线路规划案例一：旅游线路规划软件实现软件实现n 在inQSB软件的“Net Problem Specification”模块中，新建一个最大流模型：这是一个最大流的问题。案例一：旅游线路

12、规划案例一：旅游线路规划点击“Solve and Analyze” 求解。案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据。案例一：旅游线路规划案例一：旅游线路规划点击“Graphic Solution” 求解。案例一：旅游线路规划案例一：旅游线路规划容许通行量与计算结果对比。案例二：齿轮生产案例二：齿轮生产一：问题提出n某齿轮厂1996年生产齿轮57.6万只，完成产值507.9万元，上缴利润67.4万元，在编制1997年生产作业计划时，按传统的做法考虑齿轮的用户：汽车制造厂、拖拉机厂市场销量增加比例确定齿轮生产计划，目标拟定比1996

13、年产量增加38.8%即生产齿轮70万只，产值增加38%，利润增加18.7%（80万元）。对此企业内部有两种不同的认识，一种认为人员、设备、生产能力没有增加，递增速度太快，完成可能性不大；另一种认为可以完成，但关键产品与工序能力潜力多大，缺乏科学分析依据。n针对以上情况，企业经济分析人员提出运用运筹学相关理论来研究和进行讨论。案例二：齿轮生产案例二：齿轮生产一：相关数据 n该厂生产五种机型100多个品种的齿轮，为简化计算，归为五类生产。分别是：n（1）195柴油机齿轮n（2）泰山12型拖拉机齿轮n（3）6160型齿轮n（4）6102QA型齿轮n（5）CCQ95型齿轮案例二：齿轮生产案例二：齿轮生

14、产一：相关数据 n齿轮生产过程当中，原材料供应、劳动人数等约束条件可以充分满足，主要的约束因素是需要经过的10道加工工序。分别是： 序号12345678910工序锻造车床钻床拉床滚齿剃齿花键铣磨调质共渗案例二：齿轮生产案例二：齿轮生产1996年关键工序工时 锻造车工 钻床拉床滚齿剃齿花键铣磨床调质共渗总计9825223893126796893275922156318932379611786426796案例二：齿轮生产案例二：齿轮生产机型利润产值总工时锻造车钻床拉床滚齿剃齿花键磨调质共渗1953.5333.64.980.461.660.120.080.720.18000.2920泰山12109.

15、62250.928.914.19.490.3930.343.6100.3590.98302.19616050.6139.319.941.926.940.2730.2823.742000.7390.35906102QA8669.30.812.730.12301.4840.2300.5230.320CCQ9513.4159.6516.850.516.180.2120.1331.620.350.850.7750.150案例二：齿轮生产案例二：齿轮生产依据1996年的基本数据，编制1997年计划n制定不考虑国家指令性计划利用现有生产条件取得最大经济效益的方案。n后来国家指令性计划出台，那么考虑国家计划

16、指令性要求和产品配套要求，利用现有生产能力重新编制了生产方案。 案例二：齿轮生产案例二：齿轮生产分析：该问题可以用线性规划进行求解。n设：nX1：表示195柴油机齿轮产量nX2：表示泰山12型拖拉机齿轮产量nX3：表示6160型齿轮产量nX4：表示6102QA型齿轮产量nX5：表示CCQ95型齿轮产量案例二：齿轮生产案例二：齿轮生产nY1表示锻造工序生产能力（小时）nY2表示车工工序生产能力nY3表示钻床工序生产能力nY4表示拉床工序生产能力nY5表示滚齿工序生产能力nY6表示剃齿工序生产能力nY7表示花键铣削生产能力nY8表示磨床工序生产能力nY9表示调制工序生产能力nY10表示共渗工序生产

17、能力案例二：齿轮生产案例二：齿轮生产n设该厂最大利润S为目标函数，建立线性规划模型。nMax S =3.53X1+109.62X2+50.6X3+8X4+13.4X5案例二：齿轮生产案例二：齿轮生产ns.tn 0.46X1+4.1X2+1.92X3+0.81X4+0.51X598252n 1.66X1+9.49X2+6.94X3+2.73X4+6.18X5238931n 0.12X1+0.393X2+0.273X3+0.123X4+0.212X526796n 0.08X1+0.34X2+0.282X3+0+0.133X58932n 0.72X1+3.61X2+3.742X3+1.484X4+1

18、.62X575922n 0.18X1+0+0+0.23X4+0.35X515631n 0+0.359X2+0+0+0.85X58932n 0+0.983X2+0.739X3+0.523X4+0.775X537961n 0.292X1+0+0.359X3+0.32X4+0.15X517864n 0+2.19X2+0+0+026796软件实现软件实现n 在inQSB软件的“Linear and Integer Programming”模块中，建立线性规划模型：案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮

19、生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产nX1=0： 195柴油机齿轮产量nX2=12240 ： 泰山12型拖拉机齿轮产量nX3=8485 ： 6160型齿轮产量nX4=0 ： 6102QA型齿轮产量nX5=0 ： CCQ95型齿轮产量nS=1770617元： 最大利润 案例二：齿轮生产案例二：齿轮生产n什么原因导致这个结果？n企业内部人员认为肯定某一些工序生产能力的制约导致这个结果。n但是在十个工序里面哪一个工序或者哪一些工序是关键制约因素呢？ 案例二：齿轮生产案例二：齿轮生产n什么原因约束了生产能力 案例二：齿轮生产案例二：齿轮生产n当影子价格为0时，说明该工序加工能力的变化对

20、利润没有影响，也就是该工序加工能力有富余。n当影子价格大于0时，说明该工序加工能力的变化能增加利润，也就是该工序加工能力不足。n本例中与影子价格相等的数值就是该工序每增加一个单位（工时）带来的经济效益（利润）。案例二：齿轮生产案例二：齿轮生产nY5（滚齿）Y10（共渗）两道工序的影子价格均大于0。说明这两到工序是关键工序，它们加工能力的变化会直接导致利润的变化。n其直接经济效益是：滚齿工序每增加一个工时，能增加13.552元的利润，共渗工序每增加一个工时，能增加27.76元的利润。n为什么结论和上图显示的不一样呢？案例二：齿轮生产案例二：齿轮生产n通过以上计算和分析，如果要增加利润就必须增加滚

21、齿、共渗两道工序的生产能力，针对这两种情况，企业做出如下调整：n把新买的滚齿机迅速安装调试，争取早日投产；n增加上述工序的部分班次；n购进一台新的共渗炉，尽快交付使用案例二：齿轮生产案例二：齿轮生产n齿轮生产只能是整数案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产n滚齿C5、共渗C10各增加1000生产能力案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产nX1=0： 195柴油机齿轮产量nX2=12692（12240） ： 泰山12型拖拉机齿轮产量nX3=8312（8485） ： 6160型齿轮产量nX4=0 ： 6102QA型齿轮产量nX5=0 ： CCQ9

22、5型齿轮产量nS=1811884（1770559）万元： 最大利润 n1811884-1770559 =4132513522+27764案例二：齿轮生产案例二：齿轮生产n考虑到国家计划指令的出台，国家指令量是必须完成的，即195柴油机齿轮安排6.4万台。那么这个时候的关键工序又是怎么样的呢？采用同样的方法是建立模型进行分析。案例二：齿轮生产案例二：齿轮生产n软件实现软件实现案例二：齿轮生产案例二：齿轮生产n软件实现软件实现案例二：齿轮生产案例二：齿轮生产n软件实现软件实现案例二：齿轮生产案例二：齿轮生产n软件实现软件实现案例二：齿轮生产案例二：齿轮生产n软件实现软件实现案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产案例二：齿轮生产n同样重新建立模型后采用其对偶解得到要满足国家计划指令时，拉床、车床和调质是关键工序。企业采用以下措施：案例二：齿轮生产案例二：齿轮生产 企业采用以下措施：n将一台旧拉床（多年不用）修复投入使用，将拉床两班生产改为三班生产；n调质工序再增加一台中频电炉以减轻压力，同时扩大作业面积；n把新进厂的车床及时安装使用。案例二：齿轮生产案例二：齿轮生产n采取了以上措施，使得企业生产工序生产能力基本平衡。调整后的工序能力见表。n与生产线平衡方法有什么不同？案例二：齿轮生产案例二：齿轮生产n调整后的工序能力见表 工序名称原有能力新增能力车工