消防车的合理调配

消防车的合理调度论文摘要三个消防站共计七辆消防车分别调度到三个火警地点，要使得损失最小。研究损失与各个因素之间的关系。我先将损失与各个站点次序到达的直接关系列出来，再根据题目中的问题将题目中的约束条件列出。使用Lingo软件对其进行求解。经过与实际情况的验证得到最小损失为335.一问题重述某市消防中心同时接到三处火警报告,根据当前火势,三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间，则三处火警地点的损失分别为6t11+4t12，7t21+3t22，9t31+8t32+5t33。目前可供消防中心调度的消防车辆正好有7辆，分别属于三个消防站（可用消防车数量分别为3辆、2辆和2辆）。消防车从三个消防站到三个火警地点所需的时间如下表所示。该中心应如何调度消防车，才能使总损失最小？消防站到三个火警地点所需要的时间时间火警地点1火警地点2火警地点3消防站1679消防站25811消防站36910 表1 如果三处火警地点的损失分别为4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？二问题分析本题考虑的是为了每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似，本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。三变量假设 为了用运输问题建模求解，我们很自然地把三个消防站看成供应点，如果直接把3个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把7辆车的需求分别看成7个需求点（分别对应于到达时间t11,t12,t21,t22,t31,t32,t33）。用Xij表示消防站i是否第j个需求点派车（1表示派车，0表示不派车），则共有21个0-1变量。四模型建立题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站1向第6个需求点派车（即消防站1向火警地点3派车但消防车是到达火警地点的第二辆车），则由此引起的损失为8*9=72。同理计算，可以得到损失矩阵如表所示（元素分别记为）。火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=136244921817245消防站i=230205624998855消防站i=336246327908050表2.1于是 ，使总损失最小的决策目标为约束条件：约束条件有两类，一类是消防站拥有的消防车数量限制，另一类是各需求点对消防车的需求两限制。消防站拥有的消防车的数量限制可以表示为+=3+=2+=2各需求点对消防车的需求量限制可以表示为=1，j=1,2,3,4,5,6,7.五模型求解1.未改变系数对上述模型使用Lingo进行求解得：火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=10010110消防站i=21100000消防站i=30001001表2.2根据表2.2，火警地点1的1、2两辆来自站点2，火警地点2的1、2两辆来自站点1、3，火警地点3的1、2、3分别来自站点1、1、3。而通过和表1数据的对比，恰符合站点到达地点时间的次序。 也就是说，消防站1应向火警点2派1辆车，向火警点3派2辆车；消防站2应向火警点1派2辆车；消防站3应向火警地点2、3各派1辆车。最小损失为=329。2.改变系数后的讨论（1）这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看做需求点，消防站看做供应点，在上面模型中，我们虽然假设为0-1变量，但求解时采用线性规划求解的，也就是说没有加上为0-1变量或整数变量的限制条件，但求解得到的结果中正好是0-1变量，这一结果不是偶然的，而是运输问题特有的一种性质。（2）在上面模型中，没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果不是必然的，而只是巧合。如果对题目后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵如下表所示（元素仍然分别记为）。损失矩阵火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=124362149457245消防站i=220362456558855消防站i=324362763508050表3.1使用Lingo程序求解：model:min=24*x11+36*x12+21*x13+49*x14+45*x15+72*x16+81*x17+20*x21+30*x22+24*x23+56*x24+55*x25+88*x26+99*x27+24*x31+36*x32+27*x33+63*x34+50*x35+80*x36+90*x37;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运行得：Global optimal solution found. Objective value: 329.0000 Total solver iterations: 7 Variable Value Reduced Cost X11 0.000000 6.000000 X12 0.000000 8.000000 X13 0.000000 2.000000 X14 1.000000 0.000000 X15 0.000000 3.000000 X16 1.000000 0.000000 X17 1.000000 0.000000 X21 1.000000 0.000000 X22 1.000000 0.000000 X23 0.000000 1.000000 X24 0.000000 5.000000 X25 0.000000 11.00000 X26 0.000000 14.00000 X27 0.000000 16.00000 X31 0.000000 0.000000 X32 0.000000 0.000000 X33 1.000000 0.000000 X34 0.000000 6.000000 X35 1.000000 0.000000 X36 0.000000 0.000000 X37 0.000000 1.000000 Row Slack or Surplus Dual Price 1 329.0000 -1.000000 2 0.000000 -16.00000 3 0.000000 -18.00000 4 0.000000 -24.00000 5 0.000000 -2.000000 6 0.000000 -12.00000 7 0.000000 -3.000000 8 0.000000 -33.00000 9 0.000000 -26.00000 10 0.000000 -56.00000 11 0.000000 -65.00000火警地点1火警地点2火警地点3j=1j=2j=3j=4j=5j=6j=7消防站i=10001011消防站i=21100000消防站i=30010100表3.2根据表3.2，火警地点1的两辆车全来自消防站2；火警地点2的1、2两辆车分别来自3、1站点。火警地点3的1、2、3辆车分别来自3、1、1。然而和表1进行对比，各站到达时间与模型求解后得出的次序矛盾。例如，x14=x33=1,表明火警地点2的第一辆消防车来自消防站3，第二辆消防车来自消防站1，而火警地点2与消防站3有9分钟距离，大于与消防站1的7分钟距离。而上一个题目中经过检验是符合题目要求的，而这种符合也是一种巧合。所以在提设的条件下对于每个变量，如Xij也就是需要增加一些约束条件，以保证以上的不合理问题不再出现。对火警地点2，如果第2辆消防车来自消防站2，则火警地点2的第1辆消防车一定来自消防站1或2。因此，必须增加以下约束：；+；同理，对火警地点1，必须增加以下约束条件：；对火警地点3，必须增加一下约束：;+;2+;将上述约束条件输入Lingo程序，完善后模型如下：model:min=24*x11+36*x12+21*x13+49*x14+45*x15+72*x16+81*x17+20*x21+30*x22+24*x23+56*x24+55*x25+88*x26+99*x27+24*x31+36*x32+27*x33+63*x34+50*x35+80*x36+90*x37;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;x22-x21=0;x14-x13=0;x24-x23-x13=0;x16-x15=0;x17-x16=0;x36-x15-x35=0;2*x37-x15-x16-x35-x36=0;endGlobal optimal solution found. Objective value: 332.6667 Total solver iterations: 11 Variable Value Reduced Cost X11 0.000000 9.000000 X12 0.000000 11.00000 X13 1.000000 0.000000 X14 1.000000 0.000000 X15 0.3333333 0.000000 X16 0.3333333 0.000000 X17 0.3333333 0.000000 X21 1.000000 0.000000 X22 1.000000 0.000000 X23 0.000000 0.000000 X24 0.000000 0.000000 X25 0.000000 7.333333 X26 0.000000 10.33333 X27 0.000000 11.33333 X31 0.000000 1.666667 X32 0.000000 3.666667 X33 0.000000 0.6666667 X34 0.000000 4.666667 X35 0.6666667 0.000000 X36 0.6666667 0.000000 X37 0.6666667 0.000000 Row Slack or Surplus Dual Price 1 332.6667 -1.000000 2 0.000000 -82.66667 3 0.000000 -87.66667 4 0.000000 -90.00000 5 0.000000 67.66667 6 0.000000 57.66667 7 0.000000 63.66667 8 0.000000 31.66667 9 0.000000 40.00000 10 0.000000 10.00000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 2.000000 14 1.000000 0.000000 15 0.000000 2.333333 16 0.000000 1.666667 17 0.3333333 0.000000 18 0.6666667 0.000000但我们发现此时的解中Xij并不都是0-1变量或整数变量，例如X15=0.333。因此还是不符合题意。这是因为此时的模型已经不再是“标准”的运输模型，所以得到的解不一定自然地为整数解的缘故。所以我们还必须显式地加上Xij为0-1变量的约束。model:min=24*x11+36*x12+21*x13+49*x14+45*x15+72*x16+81*x17+20*x21+30*x22+24*x23+56*x24+55*x25+88*x26+99*x27+24*x31+36*x32+27*x33+63*x34+50*x35+80*x36+90*x37;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;x22-x21=0;x14-x13=0;x24-x23-x13=0;x16-x15=0;x17-x16=0;x36-x15-x35=0;2*x37-x15-x16-x35-x36=0;bin(x11);bin(x12);bin(x13);bin(x14);bin(x15);bin(x16);bin(x17);bin(x21);bin(x22);bin(x23);bin(x24);bin(x25);bin(x26);bin(x27);bin(x31);bin(x32);bin(x33);bin(x34);bin(x35);bin(x36);bin(x37);end运行后结果如下：Global optimal solution found. Objective value: 335.0000 Extended solver steps: 0 Total solver iterations: 8 Variable Value Reduced Cost X11 0.000000 24.00000 X12 0.000000 36.00000 X13 1.000000 21.00000 X14 1.000000 49.00000 X15 1.000000 45.00000 X16 0.000000 72.00000 X17 0.000000 81.00000 X21 1.000000 20.00000 X22 1.000000 30.00000 X23 0.000000 24.00000 X24 0.000000 56.00000 X25 0.000000 55.00000 X26 0.000000 88.00000 X27 0.000000 99.00000 X31 0.000000 24.00000 X32 0.000000 36.00000 X33 0.000000 27.00000 X34 0.000000 63.00000 X35 0.000000 50.00000 X36 1.000