《面试顺序与消防车调度问题》由会员分享，可在线阅读，更多相关《面试顺序与消防车调度问题（36页珍藏版）》请在金锄头文库上搜索。
1、 优化建模5.4 面试顺序与消防车调度问题优化建模面试顺序问题例5.5 有4名同学到一家公司参加三个阶段的面试 ：公司要求每个同学都必须首先找公司秘书初试，然 后到部门主管处复试，最后到经理处参加面试，并且 不允许插队（即在任何一个阶段4名同学的顺序是一 样的）。由于4名同学的专业背景不同，所以每人在 三个阶段的面试时间也不同，如表5-5所示（单位： 分钟）。这4名同学约定他们全部面试完以后一起离 开公司。假定现在时间是早晨8：00，请问他们最早 何时能离开公司？ 优化建模表5-5 面试时间要求秘书书初试试主管复试试经经理面试试 同学甲131520 同学乙102018同学丙201010同学丁8
2、1015优化建模建立模型实际上，这个问题就是要安排4名同学的面试顺 序，使完成全部面试所花费的时间最少。 记tij为第i名同学参加第j阶段面试需要的时间(已 知)，令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名
3、同学前面(1表示是 ，0表示否)，则 xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; i= x13+ t13; T = x23+ t23; T = x33+ t33; T = x43+ t43; x11+ t11 = 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); ! 同一时间只能面试1名同学; for(Stage(j):for(PXP(i,
4、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软件无法与之相 比的。 优化建模消防车调度问题 例5.6 某市消防中心同时接
5、到了三处火警报告。 根据当前的火势，三处火警地点分别需要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
6、2+9t33， 调度方案是否需要改变？消防站到三个火警地点所需要的时间时间时间 (分钟钟 )火警地点1火警地点2火警地点3消防站1679消防站25811消防站36910优化建模问题分析本题考虑的是为每个火警地点分配消防车的问题 ，初步看来与线性规划中经典的运输问题有些类似。 本题的问题可以看成是指派问题和运输问题的一种变 形，我们下面首先把它变成一个运输问题建模求解。 决策变量为了用运输问题建模求解，很自然地把3个消防 站看成供应点。如果直接把3个火警地点看成需求点 ，我们却不能很方便地描述消防车到达的先后次序， 因此难以确定损失的大小。下面我们把7辆车的需求 分别看成7个需求点(分别对应于到
7、达时间t11, t12, t21, t22, t31, t32, t33)。用xi j表示消防站i是否向第j个需求点派 车(1表示派车，0表示不派车)，则共有21个0-1变量。 优化建模决策目标题目中给出的损失函数都是消防车到达时间的线 性函数，所以由所给数据进行简单的计算可知，如果 消防站1向第6个需求点派车(即消防站1向火警地点3 派车但该消防车是到达火警地点3的第二辆车)，则由 此引起的损失为8*9=72。同理计算，可以得到损失矩 阵(元素分别记为ci j)。 ci j火警地点1火警地点2火警地点3 j=1j=2j=3j=4j=5j=6j=7消防站i=136244921817245消防站
8、i=230205624998855消防站i=336246327908050优化建模 于是，使总损失最小的决策目标为 约束条件 约束条件有两类：一类是消防站拥有的 消防车的数量限制，另一类是各需求点对消防车的需 求量限制。 消防站拥有的消防车的数量限制可以表示为 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：! 消防车问题 Min 36x11+24x12+49x13
9、+21x14+81x15+72x16+45x17+30x21+20x22+56x23+24x24+99x25+88x26+55x27+36x31+24x32+63x33+27x34+90x35+80x36+50x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3x21+x22+x23+x24+x25+x26+x27 = 2x31+x32+x33+x34+x35+x36+x37 = 2x11+x21+x31 =1 x12+x22+x32 =1 x13+x23+x33 = 1 x14+x24+x34 =1 x15+x25+x35 =1 x16+x26+x36
10、 = 1 x17+x27+x37 = 1 END 优化建模 求解得到如下结果： OBJECTIVE FUNCTION VALUE 1) 329.0000 VARIABLE VALUE REDUCED COSTX11 0.000000 10.000000X12 0.000000 8.000000X13 1.000000 0.000000X14 0.000000 2.000000X15 1.000000 0.000000X16 1.000000 0.000000X17 0.000000 3.000000X21 1.000000 0.000000X22 1.000000 0.000000X23 0.
11、000000 3.000000X24 0.000000 1.000000X25 0.000000 14.000000X26 0.000000 12.000000X27 0.000000 9.000000 优化建模VARIABLE VALUE REDUCED COSTX31 0.000000 2.000000X32 0.000000 0.000000X33 0.000000 6.000000X34 1.000000 0.000000X35 0.000000 1.000000X36 0.000000 0.000000X37 1.000000 0.000000 也就是说，消防站1应向火警地点2派1辆
12、车，向 火警地点3派2辆车；消防站2应向火警地点1派2辆车 ；消防站3应向火警地点2、3各派1辆车。最小总损失 为329。 优化建模讨论 1) 这个问题本质上仍然和经典的运输问题类似， 可以把每辆车到达火场看作需求点，消防站可作供应 点。在上面模型中，我们虽然假设xij为0-1变量，但求 解时是采用线性规划求解的，也就是说没有加上xij为 0-1变量或整数变量的限制条件，但求解得到的结果 中xij正好是0-1变量。这一结果不是偶然的，而是运输 问题特有的一种性质。优化建模2) 在上面模型中，我们没有考虑消防车到达各火 警地点的先后次序约束，但得到的结果正好满足所有 的先后次序约束。这一结果却并
13、不总是必然的，而只 是巧合。如对例题后半部分的情形，结果就不是这样了。 显然，此时只需要修改损失矩阵(元素仍然分别记为 cij)ci j火警地点1火警地点2火警地点3 j=1j=2j=3j=4j=5j=6j=7消防站i=124362149457281消防站i=220302456558899消防站i=324362763508090优化建模此时将重新构成的线性规划模型输入LINDO求 解, 可以得到新的最优解: x14=x16=x17=x21=x22=x33=x35=1 其他变量为0(最小总损失仍为329)。实际上, 损失矩阵 中只是1、2列交换了位置，3、4列交换了位置，5、7 列交换了位置，因
14、此不用重新求解就可以直接看出以 上新的最优解。 但是，以上新的最优解却是不符合实际情况的。 例如，x14=x33=1表明火警地点2的第一辆消防车来自 消防站3，第二辆消防车来自消防站1，但这是不合理 的，因为火警地点2与消防站3有9分钟的距离，大于 与消防站1的7分钟的距离。分配给火警地点3的消防 车也有类似的不合理问题。 优化建模为了解决这一问题，我们必须考虑消防车到达各 火警地点的先后次序约束，也就是说必须在简单的运 输问题模型中增加一些新的约束，以保证以上的不合 理问题不再出现。首先考虑火警地点2。由于消防站1的消防车到达 所需时间(7分钟)小于消防站2的消防车到达所需时间 (8分钟)，并都小于消防站3的消防车到达所需时间(9 分钟)，因此火警地点2的第2辆消防车如果来自消防 站1，则火警地点2的第1辆消防车也一定来自消防站1 ；火警地点2的第2辆消防车如果来自消防站2，则火 警地点2的第1辆消防车一定来自消防站1或2。因此， 必须增加以下约束：x14x13 x24x13 +x23优化建模x16 x15 x17 x16 x36 x15+x35 2x37 x15+x16+x35+x36 同理，对火警地点1，必须增加以下约束： x22x21对火警地点3，必须增加以下约束：优化建模此时将重新构成的线性规划模型输入L
