消防车调问题.pptx

会计学1消防车调问题消防车调问题 如果三处火警地点的损失分别为如果三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？调度方案是否需要改变？消防站到三个火警地点所需要的时间消防站到三个火警地点所需要的时间时间时间(分钟分钟)火警地点火警地点1火警地点火警地点2火警地点火警地点3消防站消防站1679消防站消防站25811消防站消防站36910第1页/共18页 问题分析问题分析 本题考虑的是为每个火警地点分配消防车的问本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。形，我们下面首先把它变成一个运输问题建模求解。决策变量决策变量 为了用运输问题建模求解，很自然地把为了用运输问题建模求解，很自然地把3个消防个消防站看成供应点。如果直接把站看成供应点。如果直接把3个火警地点看成需求点，个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把此难以确定损失的大小。下面我们把7辆车的需求分辆车的需求分别看成别看成7个需求点个需求点(分别对应于到达时间分别对应于到达时间t11,t12,t21,t22,t31,t32,t33)。用。用xi j表示消防站表示消防站i是否向第是否向第j个需求点派车个需求点派车(1表示派车，表示派车，0表示不派车表示不派车)，则共有，则共有21个个0-1变量。变量。第2页/共18页 决策目标决策目标 题目中给出的损失函数都是消防车到达时间的线题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果性函数，所以由所给数据进行简单的计算可知，如果消防站消防站1向第向第6个需求点派车个需求点派车(即消防站即消防站1向火警地点向火警地点3派车但该消防车是到达火警地点派车但该消防车是到达火警地点3的第二辆车的第二辆车)，则由，则由此引起的损失为此引起的损失为8*9=72。同理计算，可以得到损失矩。同理计算，可以得到损失矩阵阵(元素分别记为元素分别记为ci j)。ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=136244921817245消防站消防站i=230205624998855消防站消防站i=336246327908050第3页/共18页于是，使总损失最小的决策目标为于是，使总损失最小的决策目标为 约束条件约束条件 约束条件有两类：一类是消防站拥有约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的的消防车的数量限制，另一类是各需求点对消防车的需求量限制。需求量限制。消防站拥有的消防车的数量限制可以表示为消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27=2 x31+x32+x33+x34+x35+x36+x37=2 各需求点对消防车的需求量限制可以表示为各需求点对消防车的需求量限制可以表示为 第4页/共18页模型求解模型求解 将如上构成的线性规划模型输入将如上构成的线性规划模型输入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+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 第5页/共18页求解得到如下结果：求解得到如下结果：OBJECTIVE FUNCTION VALUE 1)329.0000VARIABLE 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 第6页/共18页VARIABLE VALUE REDUCED COST X31 0.000000 2.000000 X32 0.000000 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。第7页/共18页讨论讨论 1)这个问题本质上仍然和经典的运输问题类似，这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设点。在上面模型中，我们虽然假设xij为为0-1变量，但变量，但求解时是采用线性规划求解的，也就是说没有加上求解时是采用线性规划求解的，也就是说没有加上xij为为0-1变量或整数变量的限制条件，但求解得到的结变量或整数变量的限制条件，但求解得到的结果中果中xij正好是正好是0-1变量。这一结果不是偶然的，而是变量。这一结果不是偶然的，而是运输问题特有的一种性质。运输问题特有的一种性质。第8页/共18页 2)在上面模型中，我们没有考虑消防车到达各火在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只的先后次序约束。这一结果却并不总是必然的，而只是巧合。是巧合。如对例题后半部分的情形，结果就不是这样了。如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵显然，此时只需要修改损失矩阵(元素仍然分别记为元素仍然分别记为cij)ci j火警地点火警地点1火警地点火警地点2火警地点火警地点3j=1j=2j=3j=4j=5j=6j=7消防站消防站i=124362149457281消防站消防站i=220302456558899消防站消防站i=324362763508090第9页/共18页 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO求求解解,可以得到新的最优解可以得到新的最优解:x14=x16=x17=x21=x22=x33=x35=1其他变量为其他变量为0(最小总损失仍为最小总损失仍为329)。实际上。实际上,损失矩损失矩阵中只是阵中只是1、2列交换了位置，列交换了位置，3、4列交换了位置，列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。出以上新的最优解。但是，以上新的最优解却是不符合实际情况的。但是，以上新的最优解却是不符合实际情况的。例如，例如，x14=x33=1表明火警地点表明火警地点2的第一辆消防车来自的第一辆消防车来自消防站消防站3，第二辆消防车来自消防站，第二辆消防车来自消防站1，但这是不合理，但这是不合理的，因为火警地点的，因为火警地点2与消防站与消防站3有有9分钟的距离，大于分钟的距离，大于与消防站与消防站1的的7分钟的距离。分配给火警地点分钟的距离。分配给火警地点3的消防的消防车也有类似的不合理问题。车也有类似的不合理问题。第10页/共18页 为了解决这一问题，我们必须考虑消防车到达各为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。理问题不再出现。首先考虑火警地点首先考虑火警地点2。由于消防站。由于消防站1的消防车到的消防车到达所需时间达所需时间(7分钟分钟)小于消防站小于消防站2的消防车到达所需时的消防车到达所需时间间(8分钟分钟)，并都小于消防站，并都小于消防站3的消防车到达所需时间的消防车到达所需时间(9分钟分钟)，因此火警地点，因此火警地点2的第的第2辆消防车如果来自消辆消防车如果来自消防站防站1，则火警地点，则火警地点2的第的第1辆消防车也一定来自消防辆消防车也一定来自消防站站1；火警地点；火警地点2的第的第2辆消防车如果来自消防站辆消防车如果来自消防站2，则，则火警地点火警地点2的第的第1辆消防车一定来自消防站辆消防车一定来自消防站1或或2。因此，。因此，必须增加以下约束：必须增加以下约束：x14 x13x24 x13+x23第11页/共18页x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，对火警地点同理，对火警地点1，必须增加以下约束：，必须增加以下约束：x22 x21对火警地点对火警地点3，必须增加以下约束：，必须增加以下约束：第12页/共18页 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO软软件如下：件如下：!消防车调度消防车调度Min 36x12+24x11+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+x26+x36=1 x17+x27+x37=1 第13页/共18页X22-X21=0X14-X13=0X24-X23-X13=0X16-X15=0X17-X16=0X36-X15-X35=02X37-X15-X16-X35-X36=0END !INT 21 第14页/共18页求解，可以得到新的解为：求解，可以得到新的解为：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.333333 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 第15页/共18页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.333333 X33 0.000000 0.000000 X37 0.666667 0.000000 X36 0.666667 0.000000 X35 0.666667 0.000000 第16页/共18页 但是我们发现此时的解中但是我们发现此时的解中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辆车。经过检验可以发现，此时的派车方案是辆车。经过检验可以发现，此时的派车方案是合理的。合理的。第17页/共18页