数学建模_面试最优化问题

1、C题面试时间冋题有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找 公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插 队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同， 所以每人在三个阶段的面试时间也不同，如下表所示 （单位：分钟）：秘书初试主管复试经理面试同学甲131520同学乙10 H2018同学丙20.16 -L0同学丁15这4名同学约定他们全部面试完以后一起离开公司假定现在时间是早晨 8:00问他们最早何时能离开公司？面试时间最优化问题摘要：面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试 时间有所不同，

2、这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成， 即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。 因此本问题实质上是 求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺 序下所有面试者按序完成面试所花费的时间之和， 这样的面试时间总和的所有可 能情况则取决于n位面试者的面试顺序的所有排列数根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生 间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目 标，最后利用优化软件lingo变成求解。关键词：排列排序0-1非线性规

3、划模型线性优化（一）问题的提出根据题意，本文应解决的问题有：1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8 00，求他们最早离开公司的时间；2、试着给出此类问题的一般描述，并试着分析问题的一般解法。（二）问题的分析问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入 下一阶段的面试（同一个面试者的阶段次序或时间先后次序约束），二是每个阶段 同一时间只能有一位面试者（不同面试者在同一个面试阶段只能逐一进行 ）。 对于任意两名求职者P、Q,不妨设按P在前，Q在后的顺序进行面试，可能存在 以下两情况：（一）、当P进行完一个阶段j的面试后，Q还未完成前一阶段

4、j-1的面试, 所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面 试，这样就出现了考官等待求职者的情况。 这一段等待时间必将延长最终的总时 间。（二）、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等 待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求 职者的情况。同样的，这个也会延长面试的总时间。以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起 最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求 职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最 高。他们就能以最短的时间完成面

5、试一起离开公司。这也是我们想要的结果。（三）模型的假设1. 我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关；2. 面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为0；3. 参加面试的求职者事先没有约定他们面试的先后顺序；4假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即:没有中途退出面试者；5.面试者及各考官都能在 8 00准时到达面试地点。（四）名词及符号约束1. aij（i=1,2，3, 4； j=1,2,3）为求职者i在j阶段参加面试所需的时间甲乙丙丁分别对应序号i=1，2,3，42. xij（i=1,2，3，4；

6、j=1,2,3）表示第i名同学参加j阶段面试的开始时间（不妨把早上8:00记为面试的0时刻）3. T为完成全部面试所花费的最少时间(五) 模型的建立设s1 , s2, s3, s4为4位面试者的一个面试顺序,面试者si参加第j个阶段面 试所需时间为aij根据问题的2个约束条件,可作出n位面试者在s1，s2, s3, s4)面试顺序下参加3个面试阶段的进展过程表，4位面试者按序s1 , s2, s3, s4参加3个阶段的面试进展过程表面试者T1T2T3T4T5T6s1as1,1as1,2as1,3s2as2,1as2,2as2,3s3as3,1as3,2as3,3s4as4,1as4,2as4,

7、3表中Ti (i = l , 2,?, P)表示能同时进行面试的人员所占用的时间段,如T3,表示面试者si在第3个面试场,s2在第2个面试场,s3,在第1个面试场、其余人 员在等待的那一个时间段根据顺序性可知整个面试过程的时间段数为3+4-1=6模式：以各面试者结束全部面试阶段的时间为基础(以表的行为基础)目标函数 minT =maxxi3+ai3约束条件(1) 面试阶段约束，即必须先完成上一阶段面试才能进人下一阶段面试。xij + aij xi , j+1 i = l , 2, 3, 4 ; j = 1,2, 3)(2) 同一阶段只能有一个面试者xij +aij-xki Tyikxkj +a

8、kj-xij T(1-yik)(i , k = l , 2, 3, 4, ixi3+ai3 ; i = l,2,3,4其中y是0-1变量.表示第k个面试者是否排在第i个面试者的前面，0表示否, l表示是由此,就将问题中的约束条件“同一面试阶段只能有一个面试者”改用“面试者的先后次序”来表示解决了问题中难于表达的约束条件， 反应的关系清 楚,而且在模型求解的，T值就是最小总面试时间，根据全部y值就可以排出所有 面试者使T最小的面试顺序。(3)(六) 模型的求解编写的lingo程序如下：model :title面试问题；sets :!person=被面试者集合,stage=面试阶段集合；perso

9、 n/1,2,3,4/;stage/1,2,3/;! a=面试所需时间,x面试开始时间；pxs(pers on, stage):a,x;!y(i,k)=1:k 排在 i 前,0:否则；pxp(person,person)|&1 #lt # &2:y;en dsetsdata :a=13 15 2010 20 1820 16 108 10 15;en ddatamin =maxa; !max a是面试最后结束时间 ；max a=max(pxs(i,j)|j#eq#size (stage):x(i,j)+a(i,j);!完成前一段才能进入下一段；for (pxs(i,j)|j#lt#size (s

10、tage):x(i,j)+a(i,j)x(i,j+1);!同一时间只能面试一位同学 ；forfor (stage(j):for (pxp(i,k):x(i,j)+a(i,j)-x(k,j)maxa*y(i,k);(pxp(i,k):x(k,j)+a(k,j)-x(i,j)maxa*(1-y(i,k););for (pxp(i,k):bin (y(i,k);endLin go结果如下：Local optimal soluti on found.Objective value:84.00000Exte nded solver steps:43Total solver iteratio ns:168

11、1Model Title:面试问题Reduced CostVariable ValueMAXA 84.000000.000000A( 1, 1)13.000000.000000(4)A( 1,2)15.000000.000000A( 1,3)20.000000.000000A( 2,1)10.000000.000000A( 2, 2)20.000000.000000A( 2, 3)18.000000.000000A( 3, 1)20.000000.000000A( 3, 2)16.000000.000000A( 3, 3)10.000000.000000A( 4, 1)8.0000000.00

12、0000A( 4, 2)10.000000.000000A( 4, 3)15.000000.000000X( 1, 1)8.0000000.000000X( 1,2)21.000000.000000X( 1,3)36.000000.000000X( 2,1)26.000000.000000X( 2, 2)36.000000.000000X( 2, 3)56.000000.000000X( 3, 1)38.000000.000000X( 3, 2)58.000000.000000X( 3, 3)74.000000.000000X( 4, 1)0.0000000.9999970X( 4, 2)11

13、.000000.000000X( 4, 3)21.000000.000000Y( 1,2)0.000000-83.99950Y( 1,3)0.0000000.000000Y( 1,4)1.00000083.99950Y( 2, 3)0.000000-83.99950Y( 2, 4)1.0000000.000000Y( 3, 4)1.0000000.000000RowSlack or SurplusDual Price184.00000-1.00000020.000000-0.999997030.0000000.999997040.0000000.999997050.0000000.000000

14、60.0000000.00000070.0000000.00000080.0000000.00000093.0000000.000000100.0000000.000000115.0000000.0000001217.000000.000000(5)1363.000000.000000142.0000000.0000001548.000000.0000001626.000000.0000001756.000000.0000001834.000000.000000190.0000000.99999702052.000000.0000002118.000000.0000002230.000000.

15、000000230.0000000.0000002422.000000.0000002559.000000.000000262.0000000.0000002739.000000.0000002821.000000.0000002949.000000.0000003031.000000.000000310.0000000.0000003246.000000.0000003315.000000.0000003437.000000.000000350.0000000.99999703618.000000.0000003749.000000.000000380.0000000.99999703931.000000.0000004021.000000.0000004146.000000.0000004236.000000.000000430.0000000.0000004456.000000.0000004520.000000.0000004638.000000.000000计算结果为：所有面试完成至少需要84min。面试序号为丁 -甲-乙-丙。早上8:00 面试，最早9:24面试可以完成.（七）模型的推广该模式是时间最优化的模型，有推广的价值。例如：车间生产的流水线作业，多个部件如何按照先后次序在不同车间进行生产等。