暑期建模培训课(二).ppt

2011学年暑期数学建模培训 model: Title 钢管下料 - 最小化钢管根数的LINGO模型; SETS: NEEDS/1..4/:LENGTH,NUM; ! 定义基本集合NEEDS及其属性LENGTH,NUM; CUTS/1..3/:X; ! 定义基本集合CUTS及其属性X; PATTERNS(NEEDS,CUTS):R; ! 定义派生集合PATTERNS（这是一个稠密集合）及其属性R; ENDSETS DATA: LENGTH=4 5 6 8; NUM=50 10 20 15; CAPACITY=19; ENDDATA min=@SUM(CUTS(I): X(I) ); !目标函数; @FOR(NEEDS(I): @SUM(CUTS(J): X(J)*R(I,J) ) >NUM(I) ); !满足需求约束; @FOR(CUTS(J): @SUM(NEEDS(I): LENGTH(I)*R(I,J) ) <CAPACITY ); !合理切割模式约束; @FOR(CUTS(J): @SUM(NEEDS(I): LENGTH(I)*R(I,J) ) >CAPACITY -@MIN(NEEDS(I):LENGTH(I)) ); !合理切割模式约束; @SUM(CUTS(I): X(I) ) >26; @SUM(CUTS(I): X(I) ) <31; !人为增加约束; @FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1) ); !人为增加约束; @FOR(CUTS(J): @GIN(X(J)) ) ; @FOR(PATTERNS(I,J): @GIN(R(I,J)) ); end 求解这个模型，得到的结果与前面的结果完全相同。 §5.3 消防车调度问题 实例分析： 例 某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间(分钟)，则三处火警地点的损失分别为: 6t11+4t12，7t21+3t22，9t31+8t32+5t33。 目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站(可用消防车数量分别为3辆、2辆、2辆)。消防车从三个消防站到三个火警地点所需要的时间如表5-6所示。该公司应如何调度消防车，才能使总损失最小？ 如果三处火警地点的损失分别为: 4t11+6t12，3t21+7t22，5t31+8t32+9t33， 调度方案是否需要改变？ 消防站到三个火警地点所需要的时间 10 9 6 消防站3 11 8 5 消防站2 9 7 6 消防站1 火警地点3 火警地点2 火警地点1 时间(分钟) 问题分析： 本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。 决策变量： 为了用运输问题建模求解，很自然地把3个消防站看成供应点。如果直接把3个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把7辆车的需求分别看成7个需求点(分别对应于到达时间t11, t12, t21, t22, t31, t32, t33)。用xi j表示消防站i是否向第j个需求点派车(1表示派车，0表示不派车)，则共有21个0-1变量。 决策目标： 题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站1向第6个需求点派车(即消防站1向火警地点3派车但该消防车是到达火警地点3的第二辆车)，则由此引起的损失为8*9=72。同理计算，可以得到损失矩阵(元素分别记为ci j)。 50 80 90 27 63 24 36 消防站i=3 55 88 99 24 56 20 30 消防站i=2 45 72 81 21 49 24 36 消防站i=1 j=7 j=6 j=5 j=4 j=3 j=2 j=1 火警地点3 火警地点2 火警地点1 ci j 于是，使总损失最小的决策目标为 约束条件： 约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。 消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+x36+