《消防车调度问题》ppt课件

《《消防车调度问题》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、消防车调度问题例5.6某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间(分钟)，则三处火警地点的损失分别为:6t11+4t12，7t21+3t22，9t31+8t32+5t33。目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站(可用消防车数量分别为3辆、2辆、2辆)。消防车从三个消防站到三个火警地点所需要的时间如表5-6所示。该公司应如何调度消防车，才能使总损失最小？如果三处火警地点的损失分别为:4t11+

2、6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？消防站到三个火警地点所需要的时间时间(分钟)火警地点1火警地点2火警地点3消防站1679消防站25811消防站36910问题分析本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。决策变量为了用运输问题建模求解，很自然地把3个消防站看成供应点。如果直接把3个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把

3、7辆车的需求分别看成7个需求点(分别对应于到达时间t11,t12,t21,t22,t31,t32,t33)。用xij表示消防站i是否向第j个需求点派车(1表示派车，0表示不派车)，则共有21个0-1变量。决策目标题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站1向第6个需求点派车(即消防站1向火警地点3派车但该消防车是到达火警地点3的第二辆车)，则由此引起的损失为8*9=72。同理计算，可以得到损失矩阵(元素分别记为cij)。cij火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=1

4、36244921817245消防站i=230205624998855消防站i=336246327908050于是，使总损失最小的决策目标为约束条件约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。消防站拥有的消防车的数量限制可以表示为x11+x12+x13+x14+x15+x16+x17=3x21+x22+x23+x24+x25+x26+x27=2x31+x32+x33+x34+x35+x36+x37=2各需求点对消防车的需求量限制可以表示为模型求解将如上构成的线性规划模型输入LINDO：!消防车问题Min36x11+2

5、4x12+49x13+21x14+81x15+72x16+45x17+30x21+20x22+56x23+24x24+99x25+88x26+55x27+36x31+24x32+63x33+27x34+90x35+80x36+50x37SUBJECTTOx11+x12+x13+x14+x15+x16+x17=3x21+x22+x23+x24+x25+x26+x27=2x31+x32+x33+x34+x35+x36+x37=2x11+x21+x31=1x12+x22+x32=1x13+x23+x33=1x14+x24+x34=1x15+x25+x35=1x16+

6、x26+x36=1x17+x27+x37=1END求解得到如下结果：OBJECTIVEFUNCTIONVALUE1)329.0000VARIABLEVALUEREDUCEDCOSTX110.00000010.000000X120.0000008.000000X131.0000000.000000X140.0000002.000000X151.0000000.000000X161.0000000.000000X170.0000003.000000X211.0000000.000000X221.0000000.000000X230.0000003.000000X2

7、40.0000001.000000X250.00000014.000000X260.00000012.000000X270.0000009.000000VARIABLEVALUEREDUCEDCOSTX310.0000002.000000X320.0000000.000000X330.0000006.000000X341.0000000.000000X350.0000001.000000X360.0000000.000000X371.0000000.000000也就是说，消防站1应向火警地点2派1辆车，向火警地点3派2辆车；消防站2应向火警地点1派2辆车；消防

8、站3应向火警地点2、3各派1辆车。最小