《面试顺序与消防车调度问题.ppt》由会员分享，可在线阅读，更多相关《面试顺序与消防车调度问题.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 优化建模优化建模5.4 面试顺序与消防车调度问题面试顺序与消防车调度问题 优化建模优化建模面试顺序问题面试顺序问题 例例5.5 有有4名同学到一家公司参加三个阶段的面试：名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段允许插队（即在任何一个阶段4名同学的顺序是一样名同学的顺序是一样的）。由于的）。由于4名同学的专业背景不同，所以每人在三名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表
2、个阶段的面试时间也不同，如表5-5所示（单位：分所示（单位：分钟）。这钟）。这4名同学约定他们全部面试完以后一起离开名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨公司。假定现在时间是早晨8：00，请问他们最早何，请问他们最早何时能离开公司？时能离开公司？优化建模优化建模表表5-5 5-5 面试时间要求面试时间要求秘书初试秘书初试秘书初试秘书初试主管复试主管复试主管复试主管复试经理面试经理面试经理面试经理面试同学甲同学甲同学甲同学甲131315152020同学乙同学乙同学乙同学乙101020201818同学丙同学丙同学丙同学丙202010101010同学丁同学丁同学丁同学丁8 81
3、0101515 优化建模优化建模建立模型建立模型 实际上，这个问题就是要安排实际上，这个问题就是要安排4名同学的面试顺名同学的面试顺序，使完成全部面试所花费的时间最少。序，使完成全部面试所花费的时间最少。记记tij为第为第i名同学参加第名同学参加第j阶段面试需要的时间阶段面试需要的时间(已已知知)，令，令xij表示第表示第i名同学参加第名同学参加第j阶段面试的开始时刻阶段面试的开始时刻(不妨记早上不妨记早上8：00面试开始为面试开始为0时刻时刻)(i=1,2,3,4；j=1,2,3)，T为完成全部面试所花费的最少时间。为完成全部面试所花费的最少时间。优化目标为优化目标为 优化建模优化建模 a.
4、时间先后次序约束时间先后次序约束(每人只有参加完前一个阶每人只有参加完前一个阶段的面试后才能进入下一个阶段段的面试后才能进入下一个阶段)：xij+tij xi，j+1 (i=1,2,3,4；j=1,2)b.每个阶段每个阶段j同一时间只能面试同一时间只能面试1名同学：用名同学：用0-1变变量量yik表示第表示第k名同学是否排在第名同学是否排在第i名同学前面名同学前面(1表示是，表示是，0表示否表示否)，则，则 xij+tijxkj Tyik (i,k=1,2,3,4;j=1,2,3;ik)xkj+tkjxij T(1yik)(i,k=1,2,3,4;j=1,2,3;ik)约束条件：约束条件：优化
5、建模优化建模可以将非线性的优化目标改写为如下线性优化目标：可以将非线性的优化目标改写为如下线性优化目标：Min T s.t.T x13+t13 T x23+t23 T x33+t33 T x43+t43 优化建模优化建模 Min T s.t.xij+tij xi,j+1 (i=1,2,3,4；j=1,2)xij+tijxkj Tyik (i,k=1,2,3,4;j=1,2,3;ik)xkj+tkjxij T(1yik)(i,k=1,2,3,4;j=1,2,3;i=x13+t13;T=x23+t23;T=x33+t33;T=x43+t43;x11+t11=x12;x12+t12=x13;x21+
6、t21=x22;x22+t22=x23;x31+t31=x32;x32+t32=x33;x41+t41=x42;x42+t42=x43;求解模型求解模型这个模型可以如下输入这个模型可以如下输入LINGO：优化建模优化建模x11+t11-x21=T*y12;x21+t21-x11=T*(1-y12);x12+t12-x22=T*y12;x22+t22-x12=T*(1-y12);x13+t13-x23=T*y12;x23+t23-x13=T*(1-y12);x11+t11-x31=T*y13;x31+t31-x11=T*(1-y13);x12+t12-x32=T*y12;x32+t32-x12=
7、T*(1-y13);x13+t13-x33=T*y13;x33+t33-x13=T*(1-y13);x11+t11-x41=T*y14;x41+t41-x11=T*(1-y14);x12+t12-x42=T*y14;x42+t42-x12=T*(1-y14);优化建模优化建模x13+t13-x43=T*y14;x43+t43-x13=T*(1-y14);x21+t21-x31=T*y23;x31+t31-x21=T*(1-y23);x22+t22-x32=T*y23;x32+t32-x32=T*(1-y23);x23+t23-x33=T*y23;x33+t33-x23=T*(1-y23);x2
8、1+t21-x41=T*y24;x41+t41-x21=T*(1-y24);x22+t22-x42=T*y24;x42+t42-x22=T*(1-y24);x23+t23-x43=T*y24;x43+t43-x23=T*(1-y24);x31+t31-x41=T*y34;x41+t41-x31=T*(1-y34);优化建模优化建模x32+t32-x42=T*y34;x42+t42-x32=T*(1-y34);x33+t33-x43=T*y34;x43+t43-x33=max(PXS(i,j)|j#EQ#size(stage):x(i,j)+t(i,j);!只有参加完前一个阶段的面试后才能进入下
9、一个阶段只有参加完前一个阶段的面试后才能进入下一个阶段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);!同一时间只能面试同一时间只能面试1名同学名同学;for(Stage(j):for(PXP(i,k):SORT1x(i,j)+t(i,j)-x(k,j)MAXT*Y(i,k);for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i,j)MAXT*(1-Y(i,k););for(PXP:bin(y);End 优化建模优化建模 求解这个模型，得到的结果与前面的完全相同。求解这个模型，得到的结果与前面的完全相同。可以
10、很清楚地看到，使用可以很清楚地看到，使用LINGO建模语言的集建模语言的集合和属性概念，得到的模型具有非常好的结构性，反合和属性概念，得到的模型具有非常好的结构性，反映了相应的优化模型的本质，目标、决策变量、约束映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是序完全分离，这种优越性是LINDO软件无法与之相比软件无法与之相比的。的。优化建模优化建模消防车调度问题消防车调度问题 例例5.6 某市消防中心同时接到了三处火警报告。某市消防中心同时接到了三处火警报告。根据当前的火势，三处火
11、警地点分别需要根据当前的火势，三处火警地点分别需要2辆、辆、2辆和辆和3辆消防车前往灭火。三处火警地点的损失将依赖于辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记消防车到达的及时程度：记tij为第为第j辆消防车到达火警辆消防车到达火警地点地点i的时间的时间(分钟分钟)，则三处火警地点的损失分别为，则三处火警地点的损失分别为:6t11+4t12，7t21+3t22，9t31+8t32+5t33。目前可供消防中心调度的消防车正好有目前可供消防中心调度的消防车正好有7辆，分辆，分别属于三个消防站别属于三个消防站(可用消防车数量分别为可用消防车数量分别为3辆、辆、2辆、辆、2辆辆
12、)。消防车从三个消防站到三个火警地点所需要的。消防车从三个消防站到三个火警地点所需要的时间如表时间如表5-6所示。该公司应如何调度消防车，才能所示。该公司应如何调度消防车，才能使总损失最小？使总损失最小？优化建模优化建模 如果三处火警地点的损失分别为如果三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t32+9t33，调度方案是否需要改变？调度方案是否需要改变？消防站到三个火警地点所需要的时间消防站到三个火警地点所需要的时间时间时间时间时间(分钟分钟分钟分钟)火警地点火警地点火警地点火警地点1 1 火警地点火警地点火警地点火警地点2 2火警地点火警地点火警地点火警
13、地点3 3消防站消防站消防站消防站1 16 67 79 9消防站消防站消防站消防站2 25 58 81111消防站消防站消防站消防站3 36 69 91010 优化建模优化建模 问题分析问题分析 本题考虑的是为每个火警地点分配消防车的问题，本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。我们下面首先把它变成一个运输问题建模求解。决策变量决策变量 为了用运输问题建模求解，很
14、自然地把为了用运输问题建模求解，很自然地把3个消防个消防站看成供应点。如果直接把站看成供应点。如果直接把3个火警地点看成需求点，个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把此难以确定损失的大小。下面我们把7辆车的需求分辆车的需求分别看成别看成7个需求点个需求点(分别对应于到达时间分别对应于到达时间t11,t12,t21,t22,t31,t32,t33)。用。用xi j表示消防站表示消防站i是否向第是否向第j个需求点个需求点派车派车(1表示派车，表示派车，0表示不派车表示不派车)，则共有，则共有
15、21个个0-1变变量。量。优化建模优化建模 决策目标决策目标 题目中给出的损失函数都是消防车到达时间的线题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果性函数，所以由所给数据进行简单的计算可知，如果消防站消防站1向第向第6个需求点派车个需求点派车(即消防站即消防站1向火警地点向火警地点3派车但该消防车是到达火警地点派车但该消防车是到达火警地点3的第二辆车的第二辆车)，则由，则由此引起的损失为此引起的损失为8*9=72。同理计算，可以得到损失矩。同理计算，可以得到损失矩阵阵(元素分别记为元素分别记为ci j)。c ci i j j火警地点火警地点火警地点火
16、警地点1 1火警地点火警地点火警地点火警地点2 2火警地点火警地点火警地点火警地点3 3j j=1=1j j=2=2j j=3=3j j=4=4j j=5=5j j=6=6j j=7=7消防站消防站消防站消防站i i=1=13636242449492121818172724545消防站消防站消防站消防站i i=2=23030202056562424999988885555消防站消防站消防站消防站i i=3=33636242463632727909080805050 优化建模优化建模于是，使总损失最小的决策目标为于是，使总损失最小的决策目标为 约束条件约束条件 约束条件有两类：一类是消防站拥有的
17、约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需消防车的数量限制，另一类是各需求点对消防车的需求量限制。求量限制。消防站拥有的消防车的数量限制可以表示为消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27=2 x31+x32+x33+x34+x35+x36+x37=2 各需求点对消防车的需求量限制可以表示为各需求点对消防车的需求量限制可以表示为 优化建模优化建模模型求解模型求解 将如上构成的线性规划模型输入将如上构成的线性规划模型输入LINDO：!消防车问题消防
18、车问题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
19、+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 X14 0.000000 2.000000 X15 1.000000 0.000000 X16 1.000000 0.000000 X17 0.000000 3.000000 X21 1.000000
20、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.000000 0.000000 X33 0.000000 6.000000 X34 1.000000 0.000000 X35 0.000000 1.000000 X36 0.00000
21、0 0.000000 X37 1.000000 0.000000 也就是说，消防站也就是说，消防站1应向火警地点应向火警地点2派派1辆车，向辆车，向火警地点火警地点3派派2辆车；消防站辆车；消防站2应向火警地点应向火警地点1派派2辆车；辆车；消防站消防站3应向火警地点应向火警地点2、3各派各派1辆车。最小总损失为辆车。最小总损失为329。优化建模优化建模讨论讨论 1)这个问题本质上仍然和经典的运输问题类似，这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设点。在上面模型中，我们虽然假
22、设xij为为0-1变量，但求变量，但求解时是采用线性规划求解的，也就是说没有加上解时是采用线性规划求解的，也就是说没有加上xij为为0-1变量或整数变量的限制条件，但求解得到的结果变量或整数变量的限制条件，但求解得到的结果中中xij正好是正好是0-1变量。这一结果不是偶然的，而是运输变量。这一结果不是偶然的，而是运输问题特有的一种性质。问题特有的一种性质。优化建模优化建模 2)在上面模型中，我们没有考虑消防车到达各火在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只的
23、先后次序约束。这一结果却并不总是必然的，而只是巧合。是巧合。如对例题后半部分的情形，结果就不是这样了。如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵显然，此时只需要修改损失矩阵(元素仍然分别记为元素仍然分别记为cij)c ci i j j火警地点火警地点火警地点火警地点1 1火警地点火警地点火警地点火警地点2 2火警地点火警地点火警地点火警地点3 3j j=1=1j j=2=2j j=3=3j j=4=4j j=5=5j j=6=6j j=7=7消防站消防站消防站消防站i i=1=12424363621214949454572728181消防站消防站消防站消防站i i=
24、2=22020303024245656555588889999消防站消防站消防站消防站i i=3=32424363627276363505080809090 优化建模优化建模 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入LINDO求解求解,可以得到新的最优解可以得到新的最优解:x14=x16=x17=x21=x22=x33=x35=1其他变量为其他变量为0(最小总损失仍为最小总损失仍为329)。实际上。实际上,损失矩损失矩阵中只是阵中只是1、2列交换了位置，列交换了位置，3、4列交换了位置，列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看出列交换了位置，因此不
25、用重新求解就可以直接看出以上新的最优解。以上新的最优解。但是，以上新的最优解却是不符合实际情况的。但是，以上新的最优解却是不符合实际情况的。例如，例如，x14=x33=1表明火警地点表明火警地点2的第一辆消防车来自的第一辆消防车来自消防站消防站3，第二辆消防车来自消防站，第二辆消防车来自消防站1，但这是不合理，但这是不合理的，因为火警地点的，因为火警地点2与消防站与消防站3有有9分钟的距离，大于分钟的距离，大于与消防站与消防站1的的7分钟的距离。分配给火警地点分钟的距离。分配给火警地点3的消防的消防车也有类似的不合理问题。车也有类似的不合理问题。优化建模优化建模 为了解决这一问题，我们必须考虑
26、消防车到达各为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。理问题不再出现。首先考虑火警地点首先考虑火警地点2。由于消防站。由于消防站1的消防车到达的消防车到达所需时间所需时间(7分钟分钟)小于消防站小于消防站2的消防车到达所需时间的消防车到达所需时间(8分钟分钟)，并都小于消防站，并都小于消防站3的消防车到达所需时间的消防车到达所需时间(9分钟分钟)，因此火警地点，因此火警地点2的第的第2辆消防车如果
27、来自消防辆消防车如果来自消防站站1，则火警地点，则火警地点2的第的第1辆消防车也一定来自消防站辆消防车也一定来自消防站1；火警地点；火警地点2的第的第2辆消防车如果来自消防站辆消防车如果来自消防站2，则火，则火警地点警地点2的第的第1辆消防车一定来自消防站辆消防车一定来自消防站1或或2。因此，。因此，必须增加以下约束：必须增加以下约束：x14 x13x24 x13+x23 优化建模优化建模x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，对火警地点同理，对火警地点1，必须增加以下约束：，必须增加以下约束：x22 x21对火警地点对火警地点3，必须
28、增加以下约束：，必须增加以下约束：优化建模优化建模 此时将重新构成的线性规划模型输入此时将重新构成的线性规划模型输入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+
29、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=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 V
30、ALUE 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 优化建模优化建模VARIABLE VALUE REDUCED COST X27
31、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 优化建模优化建模 但是我们发现此时的解中但是我们发现此时的解中xij并不都是并不都是01变量或变量或整数变量，因此还是不符合题意。这是因为此时的模整数变量，因此还是
32、不符合题意。这是因为此时的模型已经不再是型已经不再是“标准标准”的运输模型，所以得到的解不的运输模型，所以得到的解不一定自然地为正数解的缘故。所以我们还必须显式地一定自然地为正数解的缘故。所以我们还必须显式地加上加上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辆车。经过检验可以发现，此时的派车方案是辆车。经过检验可以发现，此时的派车方案是合理的。合理的。