2011高新数模3.ppt

* * 消防车调度问题 某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间 分钟 ，则三处火警地点的损失分别为: 6t11+4t12，7t21+3t22，9t31+8t32+5t33。 目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站 可用消防车数量分别为3辆、2辆、2辆 。消防车从三个消防站到三个火警地点所需要的时间如下表所示。该公司应如何调度消防车，才能使总损失最小？ 如果三处火警地点的损失分别为: 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+x37 2 各需求点对消防车的需求量限制可以表示为 模型求解 将如上构成的线性规划模型输入LINDO： ! 消防车问题 Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30x21+20x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90x35+80x36+50x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 3 x21+x22+x23+x24+x25+x26+x27 2 x31+x32+x33+x34+x35+x36+x37 2 x11+x21+x31 1 x12+x22+x32 1 x13+x23+x33 1 x14+x24+x34 1 x15+x25+x35 1 x16+x26+x36 1 x17+x27+x37 1 END 求解得到如下结果： OBJECTIVE FUNCTION VALUE 1 329.0000 VARIABLE VALUE REDUCED COST X11 0.000000 10.000000 X12 0.000000 8.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X15 1.000000 0.000000 X16 1.000000 0.000000 X17 0.000000 3.000000 X21 1.000000 0.000000 X22 1.000000 0.000000 X23 0.000000 3.000000 X24 0.000000 1.000000 X25 0.000000 14.000000 X26 0.000000 12.000000 X27 0.000000 9.000000 VARIABLE VALUE REDUCED COST X31 0.00000