IE案例分析(一)

IE案例分析王晓光武汉理工大学机电工程学院案例一：旅游线路规划某风景区有五个景点见图所示，S为景区入口，T为景区出口，A，B，C，D，E为五个景点。其中各个景点距离见图标。SABCDTE422154374175案例一：旅游线路规划有如下问题需要解决：1.电信公司需要安装电话线路，联通各个景点和进出口，则最小线路安装是什么？2.现在，在入口S处有一个游览车，一游客有急事需要到出口T，问游览车如何行使可以使游客尽快到达出口？3.现在要在以上各个地方中的某一处修建一所医务中心，问应建在何处，能使各个景点都离他最近？案例一：旅游线路规划有如下问题需要解决：4.现在要在以上各地方中的某一处修建一所会议中心，已知各个景点的员工分别是40,25,45,30,20,35,50，那么会议中心应建在何处，能使各个景点的员工走的总路程最短？5.为了保护园区野生生态环境，现在规定每条线路上观光旅游车的数量是一定的，见下图，其中每条弧上的数字为通行车辆容量，那么如何在不违背每条线路旅游车辆数目限制下寻求最多的车辆通行？案例一：旅游线路规划SABCDTE451274534169案例一：旅游线路规划1.电信公司需要安装电话线路，联通各个景点和进出口，则最小线路安装是什么？显然，第一个问题属于最小树生成问题，采用避圈法。任选点S开始，离点S最近未连通是点Ａ，连通ＳＡ．离点Ｓ或者点A最近未连通是点B（和点Ａ相连通），连通ＡB离点Ｓ，Ａ或点B最近未连通是点C（和点Ｂ连通），连通ＢＣ离点S，Ａ，B或者点C最近未连通是Ｅ（和点B连通），连通BE案例一：旅游线路规划离点Ｓ，A，B，C或者点E最近未连通是点D（和点E连通），连通ED未连通的只有点Ｔ（和点Ｄ最近连通），连通DT。如图案例一：旅游线路规划软件实现在ＷinQSB软件的“NetworkModeling”模块中，最小树的生成就采用上面的避圈法。对于上述问题，在此模块中新建一个最小树的生成文件。如图所示案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据。点击“SolveandAnalyze”求解。案例一：旅游线路规划2.现在，在入口S处有一个游览车，一游客有急事需要到出口T，问游览车如何行使可以使游客尽快到达出口？根据题意知道这是一个网络最短路问题题。下面介绍采用迪克斯托标号法进行求解。基本思路是逐点求解。例如如果Ｖ１→Ｖ４→Ｖ６→Ｖ７是从Ｖ１到Ｖ７的最短路径，那么从Ｖ１到这条线路的任何一点都应该是最短的，不然就还存在其他最短路。案例一：旅游线路规划具体解题步骤：首先从始点Ｓ开始，令P(S)=０为永久标号，其余各点赋予Ｔ标号T(Ｖi)＝∞（ｉ＝２，３，――――）第一次迭代：计算与Ｓ接近的各点的临时标号T(A)=min[T(A),P(S)+W(SA)]=min[∞,2]=2T(B)=min[T(B),P(S)+W(SB)]=min[∞,5]=5T(C)=min[T(C),P(S)+W(SC)]=min[∞,4]=4案例一：旅游线路规划在以上T标号中T(A)=2为最小，故将A的P标号改为2即P(A)=2;第二次迭代：计算与A接近的各个点的临时标号T(D)=min[T(D),P(A)+W(AD)]=min[∞,9]=9T(B)=min[T(B),P(A)+W(AB)]=min[5,4]=4案例一：旅游线路规划在以上T标号中，T(B)=4为最小，故将B的永久标号改为P(B)=4第三次迭代：计算与B接近的各个点的临时标号T(D)=min[T(D),P(B)+W(BD)]=min[9,8]=8T(E)=min[T(E),P(B)+W(BE)]=min[∞,7]=7T(C)=min[T(C),P(S)+W(BC)]=min[4,5]=4案例一：旅游线路规划在以上T标号中，T(C)=4为最小，故P(C)=4；第四次迭代：计算与C想接近的E的临时标号T(E)=min[T(E),P(C)+W(CE)]=min[7,8]=7所以E的永久标号为P(E)=7；案例一：旅游线路规划第五次迭代：计算与E接近的各点的临时标号T(D)=min[T(D),P(E)+W(ED)]=min[8,8]=8T(T)=min[T(T),P(E)+W(ET)]=min[∞,14]=14故以上T标号中T(D)=8为最小，故P(D)=8案例一：旅游线路规划第六次迭代：计算出口点T的标号T(T)=min[T(T),P(D)+W(DT)]=min[14,13]=13根据以上步骤，我们便可以知道最短路径为：S→A→B→E→D→T或者S→A→B→D→T案例一：旅游线路规划软件实现在ＷinQSB软件的“NetProblemSpecification”模块中，新建一个最短路模型：案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据。案例一：旅游线路规划点击“SolveandAnalyze”求解。案例一：旅游线路规划点击“Solve”求解。案例一：旅游线路规划以上过程是一个迭代过程，也可以用程序实现。案例一：旅游线路规划3.现在要在风景区中的某一处修建一所医务中心，问应建在何处，能使各个景点都离他最近？第三个问题属于一个中心布点问题。一般思路是要求距离网络中最远的被服务点距离尽可能小。分别求个点的最短路：案例一：旅游线路规划点击“SolveandAnalyze”求解。案例一：旅游线路规划点击“Solve”求解。案例一：旅游线路规划点击“SolveandAnalyze”求解。案例一：旅游线路规划点击“Solve”求解。案例一：旅游线路规划点击“SolveandAnalyze”求解。案例一：旅游线路规划点击“Solve”求解。案例一：旅游线路规划D=(dij)dij=maxSABCDETS0244871313A2023651111B42014399C4310541010D86450158E75341067(min)T131191056013案例一：旅游线路规划4.现在要在风景区中的某一处修建一所会议中心，已知各个景点的员工分别是40,25,45,30,20,35,50，那么会议中心应建在何处，能使各个景点的员工走的总路程最短？该问题属于求解网络的重心问题。设qi为vi的权重（i=1,2,--n）令h(vj)=（j=1,2,---n）若min{h（vj）}=h(vr)，则称点vr为网络的重心。ni1qidij案例一：旅游线路规划qidijSABCDETS080160160320280520A5005075150125275B18090045180135405C12090300150120300D16012080100020100E245175105140350210T6505504505002503000H(Vj)14051105875102010859801810案例一：旅游线路规划利用“MicrosoftEecel”计算。可见会议中心建在B点，所有员工走的的总距离最短。案例一：旅游线路规划5.为了保护园区生态环境，规定每条线路上观光旅游车的数量是一定的，见下图，其中每条弧上的数字为容许通行车辆的数量。SABCDTE451274534169案例一：旅游线路规划软件实现在ＷinQSB软件的“NetProblemSpecification”模块中，新建一个最大流模型：这是一个最大流的问题。案例一：旅游线路规划案例一：旅游线路规划点击“OK”后可以输入数据。案例一：旅游线路规划点击“SolveandAnalyze”求解。案例一：旅游线路规划点击“GraphicSolution”求解。案例一：旅游线路规划容许通行量与计算结果对比。SABCDTE451274534169案例二：齿轮生产一：问题提出某齿轮厂1996年生产齿轮57.6万只，完成产值507.9万元，上缴利润67.4万元，在编制1997年生产作业计划时，按传统的做法考虑齿轮的用户：汽车制造厂、拖拉机厂市场销量增加比例确定齿轮生产计划，目标拟定比1996年产量增加38.8%即生产齿轮70万只，产值增加38%，利润增加18.7%（80万元）。对此企业内部有两种不同的认识，一种认为人员、设备、生产能力没有增加，递增速度太快，完成可能性不大；另一种认为可以完成，但关键产品与工序能力潜力多大，缺乏科学分析依据。针对以上情况，企业经济分析人员提出运用运筹学相关理论来研究和进行讨论。案例二：齿轮生产一：相关数据该厂生产五种机型100多个品种的齿轮，为简化计算，归为五类生产。分别是：（1）195柴油机齿轮（2）泰山12型拖拉机齿轮（3）6160型齿轮（4）6102QA型齿轮（5）CCQ95型齿轮案例二：齿轮生产一：相关数据齿轮生产过程当中，原材料供应、劳动人数等约束条件可以充分满足，主要的约束因素是需要经过的10道加工工序。分别是：序号12345678910工序锻造车床钻床拉床滚齿剃齿花键铣磨调质共渗案例二：齿轮生产1996年关键工序工时锻造车工钻床拉床滚齿剃齿花键铣磨床调质共渗总计9825223893126796893275922156318932379611786426796案例二：齿轮生产机型利润产值总工时锻造车钻床拉床滚齿剃齿花键磨调质共渗1953.5333.64.980.461.660.120.080.720.18000.2920泰山12109.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年计划制定不考虑国家指令性计划利用现有生产条件取得最大经济效益的方案。后来国家指令性计划出台，那么考虑国家计划指令性要求和产品配套要求，利用现有生产能力重新编制了生产方案。案例二：齿轮生产分析：该问题可以用线性规划进行求解。设：X1：表示195柴油机齿轮产量X2：表示泰山12型拖拉机齿轮产量X3：表示6160型齿轮产量X4：表示6102QA型齿轮产量X5：表示CCQ95型齿轮产量案例二：齿轮生产Y1表示锻造工序生产能力（小时）Y2表示车工工序生产能力Y3表示钻床工序生产能力Y4表示拉床工序生产能力Y5表示滚齿工序生产能力Y6表示剃齿工序生产能力Y7表示花键铣削生产能力Y8表示磨床工序生产能力Y9表示调制工序生产能力Y10表示共渗工序生产能力案例二：齿轮生产设该厂最大利润S为目标函数，建立线性规划模型。MaxS=3.53X1+109.62X2+50.6X3+8X4+13.4X5案例二：齿轮生产s.t0.46X1+4.1X2+1.92X3+0.81X4+0.51X5≤982521.66X1+9.49X2+6.94X3+2.73X4+6.18X5≤2389310.12X1+0.393X2+0.273X3+0.123X4+0.212X5≤267960.08X1+0.34X2+0.282X3+0+0.133X5≤89320.72X1+3.61X2+3.742X3+1.484X4+1.62X5≤759220.18X1+0+0+0.23X4+0.35X5≤156310+0.359X2+0+0+0.85X5≤89320+0.983X2+0.739X3+0.523X4+0.775X5≤379610.292X1+0+0.359X3+0.32X4+0.15X5≤178640+2.19X2+0+0+0≤26796软件实现在ＷinQSB软件的“LinearandIntegerProgramming”模块中，建立线性规划模型：案例二：齿轮生产案例二：齿轮