数学建模实录（2）

作者：孤剑

今天老师于c1-305对我们所有的作品进行了评选，我们的作品也得到了老师一点赞许，说方法新意！嘿嘿！终于我们忙了一个4天的作品得到了老师的肯定，我们当然高兴了，所以我们小组决定将我们的合作一直延续下去，干出更加辉煌的成绩。
然而，我们的作品任然还有一些细节问题的考虑，今天晚上我们就准备完成，现在将我们的第一部作品放在这里鼓励鼓励自己。也希望有更多的人能一起讨论讨论。

学校名称：沈阳建筑大学<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

参赛队员：刘京城、吕小苏、邓尚俊

指导教师：

面试的时间最优化问题

摘要

本文对B题进行了研究。按照公司的要求，四名求职者的顺序一旦确定，在以下各阶段中面试的顺序将不再改变，由于每个求职者，在三个阶段面试的时间不同（且固定），所以对任意两名求职者A、B，按A在前，B在后的顺序进行面试时，可能存在两种情况：I、当A进行完一个阶段j的面试后，B还未完成前一阶段j-1的面试，所以j阶段的考官必须等待B完成j-1阶段的面试后，才可对B进行j阶段的面试，这样就出现了，考官等待求职者的情况。II、当B完成j-1的面试后，A还未完成j阶段的面试，所以，B必须等待A完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。以上两种情况，必然延长了整个面试过程。要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要是考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。

首先我们对给出的面试时间表格进行分析，用计算机编程算出任意两个求职者按照不同的顺序参加面试时，求职者等求职者的时间和考官等求职者的时间之和，然后用图论法建模，将算出的时间表达有向赋权图的权值，问题转化成求有向赋权图（图1）中连接四个顶点的路径最短问题。我们利用MATLAB编程，按从小到大的顺序依次找出n-1（n表示参加面试的人数）条权值最小边，然后用人工参与的方式，将找出的n-1条边排出最优顺序。最后，得出丁、甲、乙、丙的顺序为最优方案，共用84分钟。即：三人可在9：24一起离开公司。

想到该问题涉及时间与人数有关，若想节省时间，很值得推广。于是我们又对该模型进行了推广，给出了几个求职者如何求最优方案的方法。

一、问题的提出

四个求职者参加面试，每个求职者在每个阶段面试时间不一样，如何安排面试顺序使所用时间最短，成为我们要解决的重点问题，具体要完成以下工作：

1.??????? 通过建模求解，得出四个求职者完成面试所需时间最短的排列方案；

2.??????? 结合实际情况，找出该模型的推广方案。

二、问题的分析

?要想解决时间的最优化问题，必须满足以下条件：

1.? 任意两个求职者之间，考官等候求职者的时间与求职者等候求职者的时间之和最短；

2.? 选出一条路径，该路径无重复的经过所有顶点，且权值之和为最小。

用图论法建模求最短路径。

<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" /><shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype>

图1

三、模型假设

1.??????? 面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，我们假定该时间间隔为0；

2.??????? 我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关；

3.??????? 参加面试的求职者没有约定他们面试的先后顺序；

4.??????? 假定中途任何一位同学均能通过面试，进入下一阶段的面试。即：没有中途退出面试者；

5.??????? 面试者都能在8：00准时到达面试地点。

四、名词及符号约定

1.??????? aij(i=1,2,3…;j=1,2,3…)为求职者i在j阶段参加面试所用时间，甲乙丙丁分别对应序号i=1，2，3，4；

2.??????? tDK表示在求职者中任取两名D和K，按D在前K在后的顺序参加面试，在该指定顺序中，K等待D的时间与考官等待K的时间之和，将tDK赋给有向赋权图中由D到K的向量的权值xDK；

3.??????? cDK表示在求职者中任取两名D和K，按D在前K在后的顺序参加面试，在该指定顺序中，D完成面试到K完成面试的时间间隔；

4.??????? S为最优路径的总时间。

五、模型的建立及分析

1.??????? 由题中所给的数据构成原始时间矩阵。Aij=

a<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" /><chmetcnv w:st="on" unitname="a" sourcevalue="11" hasspace="False" negative="False" numbertype="1" tcsc="0">11<span style="mso-tab-count: 2">???????? </span>a12<span style="mso-tab-count: 2">??????? </span>a13<p></p></chmetcnv>

a21??????? a22??????? a23

a31??????? a32??????? a33

a14??????? a43??????? a43

????????????? 为：

12????????? 15????????? 20

10????????? 20????????? 18

20????????? 16????????? 10

8??????????? 10????????? 15

2.??????? 求有向赋权图的权值，并构造该矩阵。

由题意分析，求权值tDK可分为三种情况；

1.????? 当a22-a11>=0，a23-a12>=0，说明若按顺序2—>1（乙—>甲）则1（甲）想进入第二阶段参加面试，需等候2（乙）的时间为（a22-a11），想进入第三阶段面试需等候2（乙）的时间为（a23-a12）。则：t21=(a22-a11)+(a23-a12)

此时时间差c21=a13，因为1（甲）求职者是在等候2（乙）求职者完成第三阶段的面试后才进入第三阶段进行面试，而1（甲）求职者在第三阶段面试共需时间a13，即是他俩完成各自面试的时间差值；

2.??????? 当a22-a11>0，a23-a12，说明按照顺序2—>1（乙—>甲）进行面试，1（甲）想进入第二阶段参加面试，需等候2（乙）的时间为（a22-a11），想进入第三阶段面试，第三阶段的主考官需等候1（甲）求职者的时间为（a23-a12），则：t21=（a22-a11）+|a23-a12|

此时时间差c21=| a23-a12 |+a13，因为第3阶段的主考官在给1（甲）进行面试前已经等候的时间为|a23-a12|，而1（甲）在进行第三阶段的面试时间是a13，故是两时间之和；

3.??????? 当a22-a11，按顺序2—>1（乙—>甲）进行面试，第二阶段主考官需等候1（甲）求职者的时间为|a22-a11|，而这段时间的拖延，导致了第三阶段的考官也等候1（甲）的时间为| a22-a11 |，不管a23-a12>0，还是a23-a12即不论后段是主考官在等,还是学生在等，这种顺序所用的总时间t21=|2*（ a22-a11） |+| a23 – a12 | 时间差c21=2 * | a22-a11 |+| a23 – a12 | + a13

算法总结：

?????? 通过以上假设讨论，我们总结出计算权值tDK及时间差cDK的方法：

1.??????? 当aD2-aK1>=0时

1)??????? tDK=| aD2-aK1 |+| aD3-aK2 |

2)??????? 当aD3-aK2>=0时，cDK=aK3

3)??????? 当aD3-aK3时，cDK=| aD3-aK2 | + aK3

2.??? 当aD2-aK1时

?????????????????????????????????? ?tDK=| 2*(aD2-aK1)+(aD3-aK2) |

?????????????????????????????????? ?cDK=| 2*(aD2-aK1)+(aD3-aK2) |+aK3

???????????????????? 以上算法可以通过MatLab编程实现（程序源码详见附录1）。经程序实现，得出TDK=

0??? 5?? 6?? 17

10?? 0?? 2? ?20

8?? 16?? 0?? 8

6?? 5?? 21?? 0

3.? 寻找最优路径:我们用MatLab找出TDK中的最短路径（程序源码详见附录2），经程序运行得出权值最小的边为：t41,t12,t23。即顺序为丁甲、甲乙、乙丙。可得出最优的顺序为：丁甲乙丙。

4．计算总时间S：S=丁所用总时间+c41+c12+c23=84min

六、模型的推广：

?? 该模式是时间最优化的模型，有推广的价值。例如：车间生产的流水线作业，多个部件如何按照先后顺序在不同车间进行生产等。

?

七、附录：

附录一（程序源代码）：

function rst=CrtPower(a)????????? %Find the Power of the matrix.

%**********************************************************

%? This is Help Information About Power() Function.

%?????????? Find the min number in the matrix.

%???????? Verison:1.0.0? Finish Date:27/08/2004

%?? Usage:

%?????? Power(a)????? %a is matrix .

%?????? return a rst.

%***********************************************************

?

Rows=length(a(:,1));?????? %Get the Rows of the matrix.

Col1=a(:,1);

Col2=a(:,2);

Col3=a(:,3);

rst=zeros(Rows);

for Count1=1:Rows;

??? for Count2=1:Rows;

??????? if Col2(Count1)-Col1(Count2)>=0;

??????????? rst(Count1,Count2)=abs(Col2(Count1)-Col1(Count2))+abs(Col3(Count1)-Col2(Count2));

??????? else

rst(Count1,Count2)=2*abs(Col2(Count1)-Col1(Count2))+abs(Col3(Count1)-Col2(Count2));

??????? end;

??????? if Count1==Count2

??????????? rst(Count1,Count2)=inf;

??????? end;

??? end;

end;

?

a=[13,15,20;10,20,18;20,16,10;8,10,15;];

CrtPower(a)

?

function rst=FindMinParam(a,iCount,Diff)

%**********************************************************

%? This is Help Information About FindMinParam() Function.

%? Find the min number in defferent Rows and Cols the matrix.

%?????????? Verison:1.1.2? Finish Date:28/08/2004????

%?? Usage:

%?????? FindMinParam(a,iCount,Diff)

%?? a is matrix .

%?? iCount is Counter.

%?? Diff is the parame to Find the mininum in Different Row.???????

%***********************************************************

?

if nargout>1

??? error('Too many output arguments!');

else

????? if (nargin==0 | nargin>3)

??????? error('Too many input arguments!');

????? else

??????? Cols=length(a(1,:));

???????????? Rows=length(a(:,1));

??????? if nargin==1

??????????? iCount=Rows * Cols;

??????????? Diff=0;

??????? end;

??????? if nargin==2 | nargin==3

??? ????????if iCount>Rows * Cols

??????????????? error('The search number is too big!');

??????????????? iCount=Rows * Cols;

??????????? elseif iCount

??????????????? error('The mininum is 1');

??????????????? iCount=1;

??????????? else

??????????????? iCount=iCount;

??????????? end;

??????????? if nargin==3

??????????????? if Diff==1

??????????????????? Diff=1;

??????????????? else

??????????????????? Diff=0;

??????????????? end;

??????????? else

??????????????? Diff=0;

??????????? end;

??????? end;

?????? ?

??????? rst=zeros(iCount,3);

???????????? for Count=1:iCount

??????????? Succ=0;

??????????? for RowCount=1:Rows;

??????????????? for ColCount=1:Cols;

??????????????????? ??????? if (min(min(a))==a(RowCount,ColCount));???

??????????????????????? tmpMin=min(min(a));??????????????? ?????

?????????????????????????? ??????? tmpRow=RowCount;???????????????????????

?????????????????????????? ??????? tmpCol=ColCount;

??????????????????????? if Diff==1

??????????????????????????? a(RowCount,:)=inf;????????????????????

?????????????????????????? ??????????? a(:,ColCount)=inf;

??????????????????????? else

??????????????????????????? a(RowCount,ColCount)=inf;

??????????????????????? end;

??????????????????????? Succ=1;????????????????????????????????

??????????????????????? break;?????????????????????????????????

??????????????????? end;

??????????????? end???? %End For

??????????????? if Succ==1?????????????????????????????????????

??????????????????? break;

??????????????? end;

??????????? end;

??????????? if Succ==1?????????????????????????????????????????

??????????????? rst(Count,1)=tmpMin;

????????? ??????rst(Count,2)=tmpRow;

??????????????? rst(Count,3)=tmpCol;

??????????? end;

???????????? end;

???????????? disp(rst);

????? end;

end;

?

a=[13,15,20;10,20,18;20,16,10;8,10,15;];

FindMinParam(CrtPower(a),3,1)；

?

?

八、主要参考文献

作者	书名	出版地	出版社	出版年份
赵静 但琦	数学建模与数学实验	北京	高等教育出版社	2002年

?

?

目前所存在的问题：

1.论文中没有写关键字；

2.论文中对模型的推广没有进行详细的叙述；

3.虽然此文中的方法对于此题目可以解决，但是如果是推广之后，不知道还能不能实现！(知道CrtPower()函数是没有考虑到推广问题的。）

4.格式问题。论文最后没有“英文摘要”，需要补充。

?

ps：附录本题目的原体：

沈阳建筑大学数学建模选拔题:
有四名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不容许插队（即：在任何一个阶段4名同学的顺序是一样的），由于4名同学的专业背景不同，所以没人再三个阶段的面试时间也不同，如下表所示：
这四名同学约定他们全部面试完成以后一起离开公司，假定现在时间食早晨8：00，问他们最早何时能离开公司？
（单位：分钟）
秘书面试 主管复试 经理面试
甲 13 15 20
乙 10 20 18
丙 20 16 10
丁 8 10 15

?

?