消防车调度问题.ppt

《消防车调度问题.ppt》由会员分享，可在线阅读，更多相关《消防车调度问题.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、消防车调度问题消防车调度问题 例例5.6 某市消防中心同时接到了三处火警报告。某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要根据当前的火势，三处火警地点分别需要2辆、辆、2辆和辆和3辆消防车前往灭火。三处火警地点的损失将依赖于辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记消防车到达的及时程度：记tij为第为第j辆消防车到达火警辆消防车到达火警地点地点i的时间的时间(分钟分钟)，则三处火警地点的损失分别为，则三处火警地点的损失分别为:6t11+4t12，7t21+3t22，9t31+8t32+5t33。目前可供消防中心调度的消防车正好有目前可供消防

2、中心调度的消防车正好有7辆，分辆，分别属于三个消防站别属于三个消防站(可用消防车数量分别为可用消防车数量分别为3辆、辆、2辆、辆、2辆辆)。消防车从三个消防站到三个火警地点所需要的。消防车从三个消防站到三个火警地点所需要的时间如表时间如表5-6所示。该公司应如何调度消防车，才能所示。该公司应如何调度消防车，才能使总损失最小？使总损失最小？如果三处火警地点的损失分别为如果三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？调度方案是否需要改变？消防站到三个火警地点所需要的时间消防站到三个火警地点所需要的时间时间时间(分钟分钟)火警

3、地点火警地点1火警地点火警地点2火警地点火警地点3消防站消防站1679消防站消防站25811消防站消防站36910 问题分析问题分析 本题考虑的是为每个火警地点分配消防车的问题，本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。我们下面首先把它变成一个运输问题建模求解。决策变量决策变量 为了用运输问题建模求解，很自然地把为了用运输问题建模求解，很自然地把3个消防个消防站看成

4、供应点。如果直接把站看成供应点。如果直接把3个火警地点看成需求点，个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把此难以确定损失的大小。下面我们把7辆车的需求分辆车的需求分别看成别看成7个需求点个需求点(分别对应于到达时间分别对应于到达时间t11,t12,t21,t22,t31,t32,t33)。用。用xi j表示消防站表示消防站i是否向第是否向第j个需求点个需求点派车派车(1表示派车，表示派车，0表示不派车表示不派车)，则共有，则共有21个个0-1变变量。量。决策目标决策目标 题目中给出的损失函

5、数都是消防车到达时间的线题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果性函数，所以由所给数据进行简单的计算可知，如果消防站消防站1向第向第6个需求点派车个需求点派车(即消防站即消防站1向火警地点向火警地点3派车但该消防车是到达火警地点派车但该消防车是到达火警地点3的第二辆车的第二辆车)，则由，则由此引起的损失为此引起的损失为8*9=72。同理计算，可以得到损失矩。同理计算，可以得到损失矩阵阵(元素分别记为元素分别记为ci j)。ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=136

6、244921817245消防站消防站i=230205624998855消防站消防站i=336246327908050于是，使总损失最小的决策目标为于是，使总损失最小的决策目标为 约束条件约束条件 约束条件有两类：一类是消防站拥有的约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需消防车的数量限制，另一类是各需求点对消防车的需求量限制。求量限制。消防站拥有的消防车的数量限制可以表示为消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27=2 x31+x32+x33+x

7、34+x35+x36+x37=2 各需求点对消防车的需求量限制可以表示为各需求点对消防车的需求量限制可以表示为 模型求解模型求解 将如上构成的线性规划模型输入将如上构成的线性规划模型输入LINDO：!消防车问题消防车问题Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30 x21+20 x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90 x35+80 x36+50 x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+

8、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.0000VARIABLE VALUE REDUCED COST X11 0.000000 10.000000 X12 0.000000 8.000000 X13 1.000000 0.000000 X1

9、4 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.000000 2.000000 X32 0.00

10、0000 0.000000 X33 0.000000 6.000000 X34 1.000000 0.000000 X35 0.000000 1.000000 X36 0.000000 0.000000 X37 1.000000 0.000000 也就是说，消防站也就是说，消防站1应向火警地点应向火警地点2派派1辆车，向辆车，向火警地点火警地点3派派2辆车；消防站辆车；消防站2应向火警地点应向火警地点1派派2辆车；辆车；消防站消防站3应向火警地点应向火警地点2、3各派各派1辆车。最小总损失为辆车。最小总损失为329。讨论讨论 1)这个问题本质上仍然和经典的运输问题类似，这个问题本质上仍然和经典

11、的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设点。在上面模型中，我们虽然假设xij为为0-1变量，但求变量，但求解时是采用线性规划求解的，也就是说没有加上解时是采用线性规划求解的，也就是说没有加上xij为为0-1变量或整数变量的限制条件，但求解得到的结果变量或整数变量的限制条件，但求解得到的结果中中xij正好是正好是0-1变量。这一结果不是偶然的，而是运输变量。这一结果不是偶然的，而是运输问题特有的一种性质。问题特有的一种性质。2)在上面模型中，我们没有考虑消防车到达各火在上面模型中，我们没有考虑消防车

12、到达各火警地点的先后次序约束，但得到的结果正好满足所有警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只的先后次序约束。这一结果却并不总是必然的，而只是巧合。是巧合。如对例题后半部分的情形，结果就不是这样了。如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵显然，此时只需要修改损失矩阵(元素仍然分别记为元素仍然分别记为cij)ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=124362149457281消防站消防站i=220302456558899消防站消防站i

13、=324362763508090 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO求解求解,可以得到新的最优解可以得到新的最优解:x14=x16=x17=x21=x22=x33=x35=1其他变量为其他变量为0(最小总损失仍为最小总损失仍为329)。实际上。实际上,损失矩损失矩阵中只是阵中只是1、2列交换了位置，列交换了位置，3、4列交换了位置，列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看出列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。以上新的最优解。但是，以上新的最优解却是不符合实际情况的。但是，以上新的最优解却是不符合实际情况的。例

14、如，例如，x14=x33=1表明火警地点表明火警地点2的第一辆消防车来自的第一辆消防车来自消防站消防站3，第二辆消防车来自消防站，第二辆消防车来自消防站1，但这是不合理，但这是不合理的，因为火警地点的，因为火警地点2与消防站与消防站3有有9分钟的距离，大于分钟的距离，大于与消防站与消防站1的的7分钟的距离。分配给火警地点分钟的距离。分配给火警地点3的消防的消防车也有类似的不合理问题。车也有类似的不合理问题。为了解决这一问题，我们必须考虑消防车到达各为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增

15、加一些新的约束，以保证以上的不合输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。理问题不再出现。首先考虑火警地点首先考虑火警地点2。由于消防站。由于消防站1的消防车到达的消防车到达所需时间所需时间(7分钟分钟)小于消防站小于消防站2的消防车到达所需时间的消防车到达所需时间(8分钟分钟)，并都小于消防站，并都小于消防站3的消防车到达所需时间的消防车到达所需时间(9分钟分钟)，因此火警地点，因此火警地点2的第的第2辆消防车如果来自消防辆消防车如果来自消防站站1，则火警地点，则火警地点2的第的第1辆消防车也一定来自消防站辆消防车也一定来自消防站1；火警地点；火警地点2的第的第2辆消防车

16、如果来自消防站辆消防车如果来自消防站2，则火，则火警地点警地点2的第的第1辆消防车一定来自消防站辆消防车一定来自消防站1或或2。因此，。因此，必须增加以下约束：必须增加以下约束：x14 x13x24 x13+x23x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，对火警地点同理，对火警地点1，必须增加以下约束：，必须增加以下约束：x22 x21对火警地点对火警地点3，必须增加以下约束：，必须增加以下约束：此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO软件软件如下：如下：!消防车调度消防车调度Min 36x12+24x1

17、1+49x14+21x13+81x17+72x16+45x15 +30 x22+20 x21+56x24+24x23+99x27+88x26+55x25 +36x32+24x31+63x34+27x33+90 x37+80 x36+50 x35 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+x2

18、6+x36=1 x17+x27+x37=1 X22-X21=0X14-X13=0X24-X23-X13=0X16-X15=0X17-X16=0X36-X15-X35=02X37-X15-X16-X35-X36=0END !INT 21 求解，可以得到新的解为：求解，可以得到新的解为：OBJECTIVE FUNCTION VALUE 1)32.6667VARIABLE VALUE REDUCED COST X12 0.000000 9.333333 X11 0.000000 7.333333 X14 1.000000 0.000000 X13 1.000000 0.000000 X17 0.33

19、3333 0.000000 X16 0.333333 0.000000 X15 0.333333 0.000000 X22 1.000000 0.000000 X21 1.000000 0.000000 X24 0.000000 2.333333 X23 0.000000 1.000000 VARIABLE VALUE REDUCED COST X27 0.000000 13.000000 X26 0.000000 12.000000 X25 0.000000 9.000000 X32 0.000000 2.000000 X31 0.000000 0.000000 X34 0.000000 5

20、.333333 X33 0.000000 0.000000 X37 0.666667 0.000000 X36 0.666667 0.000000 X35 0.666667 0.000000 但是我们发现此时的解中但是我们发现此时的解中xij并不都是并不都是01变量或变量或整数变量，因此还是不符合题意。这是因为此时的模整数变量，因此还是不符合题意。这是因为此时的模型已经不再是型已经不再是“标准标准”的运输模型，所以得到的解不的运输模型，所以得到的解不一定自然地为正数解的缘故。所以我们还必须显式地一定自然地为正数解的缘故。所以我们还必须显式地加上加上xij为为01变量的约束。变量的约束。加上加上xij为为0-1变量的约束后求解可以得到：变量的约束后求解可以得到：x13=x14=x15=x21=x22=x36=x37=1，其他变量为其他变量为0(最小总损失仍为最小总损失仍为335)。也就是说，消防。也就是说，消防站站1应向火警地点应向火警地点2派派2辆车，向火警地点辆车，向火警地点3派派1辆车；辆车；消防站消防站2应向火警地点应向火警地点1派派2辆车；消防站辆车；消防站3应向火警地应向火警地点点3派派2辆车。经过检验可以发现，此时的派车方案是辆车。经过检验可以发现，此时的派车方案是合理的。合理的。