数学建模面试最优化问题

2022-07-31 17:52:06 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《数学建模面试最优化问题》，欢迎阅读！
数学建模,最优化,面试,问题

C题面试时间问题

有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)：

这4名同学约定他们全部面试完以后一起离开公司．假定现在时间是早晨8:00问他们最早何时能离开公司?

面试时间最优化问题

摘要：

面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于 n 位面试者的面试顺序的所有排列数

根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目标，最后利用优化软件lingo变成求解。

关键词：排列排序 0-1非线性规划模型线性优化

(1)

（一）问题的提出

根据题意，本文应解决的问题有：

1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间；

2、试着给出此类问题的一般描述，并试着分析问题的一般解法。

（二）问题的分析

问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入下一阶段的面试(同一个面试者的阶段次序或时间先后次序约束)，二是每个阶段同一时间只能有一位面试者(不同面试者在同一个面试阶段只能逐一进行 )。对于任意两名求职者P、Q，不妨设按P在前，Q在后的顺序进行面试，可能存在以下两情况：

（一）、当P进行完一个阶段j的面试后，Q还未完成前一阶段j-1的面试，所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。

（二）、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。

以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。

（三）模型的假设

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，4

2. xij （i=1,2，3，4；j=1,2,3) 表示第i名同学参加j阶段面试的开始时间（不妨把早上8:00记为面试的0时刻）

(2)

3. T为完成全部面试所花费的最少时间

（五）模型的建立

设{s1，s2，s3，s4}为4位面试者的一个面试顺序,面试者si参加第j个阶段面试所需时间为aij 根据问题的2个约束条件,可作出n位面试者在{s1，s2，s3，s4）面试顺序下参加3个面试阶段的进展过程表，

4位面试者按序 {s1，s2，s3，s4} 参加 3个阶段的面试进展过程表

面试者 s1 s2 s3 s4

T1 T2 T3 as1,1 as1,2 as1,3

as2,1 as2,2

as3,1

T4

as2,3 as3,2 as4,1

T5 as3,3 as4,2

T6 as4,3

表中Ti (i = l，2,⋯，P)表示能同时进行面试的人员所占用的时间段,如T3，表示面试者s1在第3个面试场,s2在第2个面试场,s3,在第1个面试场、其余人员在等待的那一个时间段.根据顺序性可知整个面试过程的时间段数为3+4-1=6

模式：以各面试者结束全部面试阶段的时间为基础(以表的行为基础) 目标函数 minT =max{xi3+ai3} 约束条件

(1)面试阶段约束，即必须先完成上一阶段面试才能进人下一阶段面试。 xij + aij ≤ xi，j+1 i = l，2，3, 4； j = 1,2，3） (2) 同一阶段只能有一个面试者 xij +aij-xki ≤Tyik xkj +akj-xij≤T(1-yik)

（i，k = l，2, 3, 4， i； j = l，2，3 ） yik = {O，l}

(3)整个面试总和时间大于等于各面试者结束全部阶段面试的时间 T≥xi3+ai3； i = l,2,3,4

其中y是O-1变量.表示第k个面试者是否排在第i个面试者的前面,O表示否， l表示是.由此,就将问题中的约束条件“同一面试阶段只能有一个面试者”改用“面试者的先后次序”来表示解决了问题中难于表达的约束条件，反应的关系清楚,而且在模型求解的,T值就是最小总面试时间,根据全部y值就可以排出所有面试者使T最小的面试顺序。

(3)

（六）模型的求解

编写的lingo程序如下：

model:

title 面试问题; sets:

!person=被面试者集合,stage=面试阶段集合; person/1,2,3,4/; stage/1,2,3/;

!a=面试所需时间,x面试开始时间; pxs(person,stage):a,x; !y(i,k)=1:k排在i前,0:否则;

pxp(person,person)|&1 #lt# &2:y; endsets data: a=13 15 20 10 20 18 20 16 10 8 10 15; enddata

min=maxa;!maxa是面试最后结束时间;

maxa>=@max(pxs(i,j)|j#eq#@size(stage):x(i,j)+a(i,j)); !完成前一段才能进入下一段;

@for(pxs(i,j)|j#lt#@size(stage):x(i,j)+a(i,j) !同一时间只能面试一位同学;

@for(stage(j):@for(pxp(i,k):x(i,j)+a(i,j)-x(k,j)a*y(i,k));@for(pxp(i,k):x(k,j)+a(k,j)-x(i,j)a*(1-y(i,k)));); @for(pxp(i,k):@bin(y(i,k))); end

Lingo结果如下：

Local optimal solution found.

Objective value: 84.00000 Extended solver steps: 43 Total solver iterations: 1681

Model Title: 面试问题

Variable Value Reduced Cost MAXA 84.00000 0.000000

A( 1, 1) 13.00000 0.000000 （4）

A( 1, 2) 15.00000 0.000000 A( 1, 3) 20.00000 0.000000

A( 2, 1) 10.00000 0.000000 A( 2, 2) 20.00000 0.000000 A( 2, 3) 18.00000 0.000000 A( 3, 1) 20.00000 0.000000 A( 3, 2) 16.00000 0.000000 A( 3, 3) 10.00000 0.000000 A( 4, 1) 8.000000 0.000000 A( 4, 2) 10.00000 0.000000 A( 4, 3) 15.00000 0.000000 X( 1, 1) 8.000000 0.000000 X( 1, 2) 21.00000 0.000000 X( 1, 3) 36.00000 0.000000 X( 2, 1) 26.00000 0.000000 X( 2, 2) 36.00000 0.000000 X( 2, 3) 56.00000 0.000000 X( 3, 1) 38.00000 0.000000 X( 3, 2) 58.00000 0.000000 X( 3, 3) 74.00000 0.000000 X( 4, 1) 0.000000 0.9999970 X( 4, 2) 11.00000 0.000000 X( 4, 3) 21.00000 0.000000 Y( 1, 2) 0.000000 -83.99950 Y( 1, 3) 0.000000 0.000000 Y( 1, 4) 1.000000 83.99950 Y( 2, 3) 0.000000 -83.99950 Y( 2, 4) 1.000000 0.000000 Y( 3, 4) 1.000000 0.000000

Row Slack or Surplus Dual Price 1 84.00000 -1.000000 2 0.000000 -0.9999970 3 0.000000 0.9999970 4 0.000000 0.9999970 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 3.000000 0.000000 10 0.000000 0.000000 11 5.000000 0.000000 12 17.00000 0.000000

(5)

13 63.00000 0.000000 14 2.000000 0.000000 15 48.00000 0.000000 16 26.00000 0.000000 17 56.00000 0.000000 18 34.00000 0.000000 19 0.000000 0.9999970 20 52.00000 0.000000 21 18.00000 0.000000 22 30.00000 0.000000 23 0.000000 0.000000 24 22.00000 0.000000 25 59.00000 0.000000 26 2.000000 0.000000 27 39.00000 0.000000 28 21.00000 0.000000 29 49.00000 0.000000 30 31.00000 0.000000 31 0.000000 0.000000 32 46.00000 0.000000 33 15.00000 0.000000 34 37.00000 0.000000 35 0.000000 0.9999970 36 18.00000 0.000000 37 49.00000 0.000000 38 0.000000 0.9999970 39 31.00000 0.000000 40 21.00000 0.000000 41 46.00000 0.000000 42 36.00000 0.000000 43 0.000000 0.000000 44 56.00000 0.000000 45 20.00000 0.000000 46 38.00000 0.000000

计算结果为：所有面试完成至少需要84min。面试序号为丁-甲-乙-丙。早上8:00面试，最早9:24面试可以完成.

（七）模型的推广

该模式是时间最优化的模型，有推广的价值。例如：车间生产的流水线作业，多

(6)

个部件如何按照先后次序在不同车间进行生产等。

(八）主要参考文献

[1] 文章编号：1672-612x(2007)08- 0017-05 作者：谭代伦，刘益，张世禄

论文名：多阶段有序面试问题的数学模型与算法研究

出版报：绵阳师范学院学报出版时间：2007年8月第26卷第8期

[2] 谢金星,薛毅,优化建模 Lingo／Lindo软件[ M]．北京:清华大学出版社, 2005．

[3]姜启源,谢金星,叶俊.数学模型(第三版)[M].北京:高等教育出版社,2003． [4]姜启源,谢金星,叶俊.数学模型(第三版)习题参考解答[M].北京:高等教育出版社,2003.

(7）

本文来源：https://www.dywdw.cn/a52cbb6bbd1e650e52ea551810a6f524ccbfcb0b.html