面试顺序与消防车调度问题.ppt

《面试顺序与消防车调度问题.ppt》由会员分享，可在线阅读，更多相关《面试顺序与消防车调度问题.ppt（36页珍藏版）》请在三一办公上搜索。

1、5.4 面试顺序与消防车调度问题,面试顺序问题,例5.5 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表5-5所示（单位：分钟）。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，请问他们最早何时能离开公司？,表5-5 面试时间要求,建立模型,实际上，这个问题就是要安排4名同学的面试顺序，使完成全部面试所花费的时间最少。,记tij为第i名同学参加第j阶段面试需要的时间

2、(已知)，令xij表示第i名同学参加第j阶段面试的开始时刻(不妨记早上8：00面试开始为0时刻)(i=1,2,3,4；j=1,2,3)，T为完成全部面试所花费的最少时间。,优化目标为,a.时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段)：xij+tij xi，j+1(i=1,2,3,4；j=1,2)b.每个阶段j同一时间只能面试1名同学：用0-1变量yik表示第k名同学是否排在第i名同学前面(1表示是，0表示否)，则 xij+tijxkjTyik(i,k=1,2,3,4;j=1,2,3;ik)xkj+tkjxijT(1yik)(i,k=1,2,3,4;j=1,2,3;ik

3、),约束条件：,可以将非线性的优化目标改写为如下线性优化目标：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+tijxkjTyik(i,k=1,2,3,4;j=1,2,3;ik)xkj+tkjxijT(1yik)(i,k=1,2,3,4;j=1,2,3;ik)xi3+ti3T(i=1,2,3,4),这个问题的0-1非线性规划模型(当然所有变量还有非负约束，变量yik还有0-1约束):,Model:min=T;T=x13+t13;T=x23+t23;T=x

4、33+t33;T=x43+t43;x11+t11=x12;x12+t12=x13;x21+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+t

5、12-x32=T*y12;x32+t32-x12=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+t3

6、3-x23=T*(1-y23);x21+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=T*(1-y34);t11=13;t12=15;t13=20;t21=10;t22=20;t23=18;t

7、31=20;t32=16;t33=10;t41=8;t42=10;t43=15;,bin(y12);bin(y13);bin(y14);bin(y23);bin(y24);bin(y34);,End,用LINGO求解得到：Local optimal solution found at iteration:4357Objective value:84.00000,Variable Value Reduced Cost T 84.00000 0.000000 X13 36.00000 0.000000 T13 20.00000 0.000000 X23 56.00000 0.000000 T23

8、18.00000 0.000000 X33 74.00000 0.000000 T33 10.00000 0.000000 X43 21.00000 0.000000 T43 15.00000 0.000000 X11 8.000000 0.000000 T11 13.00000 0.000000 X12 21.00000 0.000000 T12 15.00000 0.000000,Variable Value Reduced Cost X21 21.00000 0.000000 T21 10.00000 0.000000 X22 36.00000 0.000000 T22 20.00000

9、 0.000000 X31 37.50000 0.000000 T31 20.00000 0.000000 X32 57.75000 0.000000 T32 16.00000 0.000000 X41 0.000000 0.9999970 T41 8.000000 0.000000 X42 11.00000 0.000000 T42 10.00000 0.000000 Y12 0.000000-83.99950 Y13 0.000000 0.000000 Y14 1.000000 83.99950 Y23 0.000000-83.99950 Y24 1.000000 0.000000 Y34

10、 1.000000 0.000000,即所有面试完成至少需要84分钟，面试顺序为4-1-2-3(即丁-甲-乙-丙)。早上8:00面试开始，最早9:24面试可以全部结束。,同样，如果利用LINGO的建模语言，可以编写一个更一般的LINGO模型。先准备一个数据文件(文本文件exam0505.txt)，其中的内容如下：!被面试者集合;1 2 3 4!面试阶段的集合;1 2 3!已知的面试所需要的时间;131520 102018 201610 81015!数据结束;,LINGO模型如下：Model:Title 面试问题;SETS:!Person=被面试者集合，Stage=面试阶段的集合;Person/

11、FILE(exam0505.txt)/;Stage/FILE(exam0505.txt)/;!T=已知的面试所需要的时间，X=面试开始时间;PXS(Person,Stage):T,X;!Y(i,k)=1:k排在i前，0：否则;PXP(Person,Person)|ENDDATA,obj min=MAXT;!MAXT是面试的最后结束时间;MAXT=max(PXS(i,j)|j#EQ#size(stage):x(i,j)+t(i,j);!只有参加完前一个阶段的面试后才能进入下一个阶段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);

12、!同一时间只能面试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,求解这个模型，得到的结果与前面的完全相同。可以很清楚地看到，使用LINGO建模语言的集合和属性概念，得到的模型具有非常好的结构性，反映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是LINDO软件无法与之相比的。,消防车调度问题,例

13、5.6 某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要2辆、2辆和3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记tij为第j辆消防车到达火警地点i的时间(分钟)，则三处火警地点的损失分别为:6t11+4t12，7t21+3t22，9t31+8t32+5t33。目前可供消防中心调度的消防车正好有7辆，分别属于三个消防站(可用消防车数量分别为3辆、2辆、2辆)。消防车从三个消防站到三个火警地点所需要的时间如表5-6所示。该公司应如何调度消防车，才能使总损失最小？,如果三处火警地点的损失分别为:4t11+6t12，3t21+7t22，5t31+8t3

14、2+9t33，调度方案是否需要改变？,消防站到三个火警地点所需要的时间,问题分析 本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。,决策变量 为了用运输问题建模求解，很自然地把3个消防站看成供应点。如果直接把3个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把7辆车的需求分别看成7个需求点(分别对应于到达时间t11,t12,t21,t22,t31,t32,t33)。用xi j表示消防站i是否向第j个需求点派车(1表

15、示派车，0表示不派车)，则共有21个0-1变量。,决策目标 题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站1向第6个需求点派车(即消防站1向火警地点3派车但该消防车是到达火警地点3的第二辆车)，则由此引起的损失为8*9=72。同理计算，可以得到损失矩阵(元素分别记为ci j)。,于是，使总损失最小的决策目标为,约束条件 约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。消防站拥有的消防车的数量限制可以表示为 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+

16、x26+x27=2 x31+x32+x33+x34+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+x24+x25+x26+x27=2 x31

17、+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 X14 0.000000 2.000000 X15 1.000

18、000 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.000000 0.000000 X33 0.000000 6.

19、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)这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设xij为0-1变量，但求解时是采用线性规划求解的，也就是说没有加上xij为0-1变量或整数变量的限制条件，但求解得到的结果中xi

20、j正好是0-1变量。这一结果不是偶然的，而是运输问题特有的一种性质。,2)在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只是巧合。如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵(元素仍然分别记为cij),此时将重新构成的线性规划模型输入LINDO求解,可以得到新的最优解:x14=x16=x17=x21=x22=x33=x35=1其他变量为0(最小总损失仍为329)。实际上,损失矩阵中只是1、2列交换了位置，3、4列交换了位置，5、7列交换了位置，因此不用重新求解就可以直接看出以上新的最优

21、解。但是，以上新的最优解却是不符合实际情况的。例如，x14=x33=1表明火警地点2的第一辆消防车来自消防站3，第二辆消防车来自消防站1，但这是不合理的，因为火警地点2与消防站3有9分钟的距离，大于与消防站1的7分钟的距离。分配给火警地点3的消防车也有类似的不合理问题。,为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。首先考虑火警地点2。由于消防站1的消防车到达所需时间(7分钟)小于消防站2的消防车到达所需时间(8分钟)，并都小于消防站3的消防车到达所需时间(9分钟)，因此火警地点2的第2辆消

22、防车如果来自消防站1，则火警地点2的第1辆消防车也一定来自消防站1；火警地点2的第2辆消防车如果来自消防站2，则火警地点2的第1辆消防车一定来自消防站1或2。因此，必须增加以下约束：,x14x13x24x13+x23,x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36,同理，对火警地点1，必须增加以下约束：,x22x21,对火警地点3，必须增加以下约束：,此时将重新构成的线性规划模型输入LINDO软件如下：,!消防车调度Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15+30 x22+20 x21+56x24+24

23、x23+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,X22-X21=0X14-X13=0X24-X23-X13=0X16

24、-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.333333 0.000000 X16 0.333333 0.000000 X15 0.333333 0.000000 X22 1.0000

25、00 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.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辆车。经过检验可以发现，此时的派车方案是合理的。,