运筹学习题解答(chap4-整数规划与分配问题)

整数规划与分配问题一、建立下列问题的数学模型1、P143,4.1利用0－1变量对下列各题分别表示成一般线性约束条件(a)或；(b)取值0,3,5,7中的一个；(c)变量或等于0，或；(d)若，则，否则；(e)以下四个约束条件中至少满足两个：。解：(a)设 （i=1,2）,M为任意大正数。则有(b)设，，则原条件可表示为(c)设，则原条件可表示为(d)（i=1,2）,M为任意大正数。则有(e)设，，则原条件可表示为：2、P143,4.2某钻井队要从以下10个可供选择的井位确定5个钻井探油，目的是使得总的钻探费用最小。若10个井位代号为，相应的钻探费用为，并且井位的选择要满足下列条件：（1）或选择和，或选择；（2）选择了或就不能选择，反过来也一样；（3）在中最多只能选两个。请建立该问题的数学模型。解：设，则目标函数是：约束条件：3、P145,4.10东方大学计算机实验室聘用4名大学生（代号1,2,3,4）和2名研究生（代号5,6）值班。已知各学生从周一至周五每天可安排的值班时间及每人每小时报酬见下表所示。学生代号酬金(元/h)每天可安排的值班时间(h)周一周二周三周四周五110.060607210.00606339.94830549.855640510.830460611.306244实验室每天开放时间为8:00AM—10:00PM,共14小时。开放时间内需要有一名学生值班。规定大学生每周值班时间是8—15小时，研究生是7—12小时，每次值班不小于2小时。又每名学生每周值班次数不得多于三次，每天值班人员中至少有一名研究生，每天值班人数不超过3人。试为该实验室安排一张人员值班表，使得总酬金支出为最少。请建立该问题的数学模型。解：设表示学生i在周j的值班时间。表示学生i在周j的最多可值班时间。则目标函数：每天开放14小时大学生值班8-15小时研究生值班7-12小时每周不超过3次每天不超过3人每天有一研究生值班不超过每人可安排的时间为0-1变量。4、P147,4.15需生产2000件某种产品，该种产品可利用A，B，C，D设备中的任意一种加工，已知每种设备的生产准备结束费用，产品的单件成本，每种设备限定的最大加工数量如下表所示。请建立使得生产总成本最小的优化模型。设备准备结束费用（元）生产成本（元/件）生产能力（件）A100020900B980241000C800161200D700281600解：设在A，B，C，D上加工的产品数量分别为。，，建立模型如下：二、求解下列指派问题1、P143,4.3（a）某指派问题的效率矩阵如下，请用匈牙利法求最优解。 解：所以最优解为取值为1，其他为0。最优效率21。2、P143,4.3（a）某指派问题的效率矩阵如下，请用匈牙利法求最优解。解：所以最优指派为：，其余均为0，最有效率是12。3、已知下列五名运动员各种泳姿的50米游泳成绩如下表(单位：秒)，请从中选拔出一个450m的混合泳接力队，使预期比赛成绩为最好。赵钱张王周仰泳3732383735蛙泳4333423441蝶泳3328383033自由泳2926292831解：用匈牙利法求解如下：所以最优解为，其余均为0，即仰泳-周，蛙泳-王，蝶泳-钱，自由泳-赵，张落选。最好成绩是35+34+29+28=126秒。-----13分4、P144,4.6分配甲、乙、丙、丁去完成A、B、C、D、E五项任务，每人完成任务所需的时间（单位：小时）如下表所示。现要求任务E必须完成，其它4项可任选3项完成；试确定最优分配方案，使得完成任务的总时间最少。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：