消防车调度问题.ppt

。根据当前的火势,三处火警地点分别需要辆、辆和辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度:记tij为第j辆消防车到达火警地点i的时间(分钟),则三处火警地点的损失分别为:t+t,t+t,t+t+t。目前可供消防中心调度的消防车正好有辆,分别属于三个消防站(可用消防车数量分别为辆、辆、辆)。消防车从三个消防站到三个火警地点所需要的时间如表-所示。该公司应如何调度消防车,才能使总损失最小?如果三处火警地点的损失分别为:t+t,t+t,t+t+t,调度方案是否需要改变?消防站到三个火警地点所需要的时间时间(分钟)火警地点火警地点火警地点消防站消防站消防站问题分析本题考虑的是为每个火警地点分配消防车的问题,初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形,我们下面首先把它变成一个运输问题建模求解。决策变量为了用运输问题建模求解,很自然地把个消防站看成供应点。如果直接把个火警地点看成需求点,我们却不能很方便地描述消防车到达的先后次序,因此难以确定损失的大小。下面我们把辆车的需求分别看成个需求点(分别对应于到达时间t,t,t,t,t,t,t)。用xij表示消防站i是否向第j个需求点派车(表示派车,表示不派车),则共有个-变量。决策目标题目中给出的损失函数都是消防车到达时间的线性函数,所以由所给数据进行简单的计算可知,如果消防站向第个需求点派车(即消防站向火警地点派车但该消防车是到达火警地点的第二辆车),则由此引起的损失为*=。同理计算,可以得到损失矩阵(元素分别记为cij)。cij火警地点火警地点火警地点j=j=j=j=j=j=j=消防站i=消防站i=消防站i=于是,使总损失最小的决策目标为约束条件约束条件有两类:一类是消防站拥有的消防车的数量限制,另一类是各需求点对消防车的需求量限制。消防站拥有的消防车的数量限制可以表示为x+x+x+x+x+x+x=x+x+x+x+x+x+x=x+x+x+x+x+x+x=各需求点对消防车的需求量限制可以表示为模型求解将如上构成的线性规划模型输入LINDO:!消防车问题Minx+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+xSUBJECTTOx+x+x+x+x+x+x=x+x+x+x+x+x+x=x+x+x+x+x+x+x= x+x+x=x+x+x= x+x+x= x+x+x= x+x+x= x+x+x= x+x+x=END求解得到如下结果:OBJECTIVEFUNCTIONVALUE).VARIABLEVALUEREDUCEDCOSTX..X..X..X..X..X..X..X..X..X..X..X..X..X..VARIABLEVALUEREDUCEDCOSTX..X..X..X..X..X..X..也就是说,消防站应向火警地点派辆车,向火警地点派辆车;消防站应向火警地点派辆车;消防站应向火警地点、各派