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

2006年8月 * 优化建模 * 优化建模 5.4 面试顺序与消防车调度问题 面试顺序问题 例5.5 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表5-5所示（单位：分钟）。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，请问他们最早何时能离开公司？ 表5-5 面试时间要求 15 10 8 同学丁 10 10 20 同学丙 18 20 10 同学乙 20 15 13 同学甲 经理面试 主管复试 秘书初试 建立模型 实际上，这个问题就是要安排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名同学前面(1表示是，0表示否)，则 xij+ tij–xkj?Tyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkj–xij?T(1–yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) 约束条件： 可以将非线性的优化目标改写为如下线性优化目标： 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+ tij–xkj?Tyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkj–xij?T(1–yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xi3+ ti3?T (i=1, 2, 3, 4) 这个问题的0-1非线性规划模型(当然所有变量还有非负约束，变量yik还有0-1约束) : Model: min =T; T = x13+ t13; T = x23+ t23; T = x33+ 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+ t12 - 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 -