解答运筹学整数规划作业.ppt

《解答运筹学整数规划作业.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.1试利用0-1变量对下列各题分别表示成一般线性约束条件x1+x2≤2或2x1+3x2≥5变量x只能取值0、3、5或7中的一个若x1≤2，则x2≥1，否则x2≤4以下四个约束条件中至少满足两个：x1+x2≤5，x1≤2，x3≥2，x3+x4≥6x1+x2≤2或2x1+3x2≥5b)变量x只能取值0、3、5或7中的一个若x1≤2，则x2≥1，否则x2≤4d)以下四个约束条件中至少满足两个：x1+x2≤5，x1≤2，x3≥2，x3+x4≥64.2某厂经常往外发送零部件。工厂根据长期发货情况决定专门生产一批为A1,A2,…A6的6种不同规格的包装箱，其中A1最小，A2次之，…A6最大。已知上述

2、6种规格包装箱的需求量分别为Q1，Q2，…，Q6，生产每个箱的可变费用分别为c1,c2,…c6(c1

3、要满足下列条件：或选择S1和S7，或选择钻探S8选择了S3或S4就不能选S5，或反过来也一样在S2、S6、S9、S10中最多只能选两个或选择S1和S7，或选择钻探S8设选择第sj个井位不选择第sj个井位选择了S3或S4就不能选S5，或反过来也一样在S2、S6、S9、S10中最多只能选两个4.4已知分配问题的效率矩阵如下，试用匈牙利法分别求出最优解第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有第二步：找出矩阵每列的最小元素，再分别从每列中减去，有第三步：用最少的直线覆盖所有“0”，得覆盖所有零最少需要4条直线，表明矩阵中最多存在4个不同行不同列的零元素．需要作变换－2－2

4、＋2第五步：用最少直线覆盖即存在5个不同行不同列的独立零元素。圈04.5已知下列五名运动员各种姿势的游泳（各为50m）如表4.8所示。试问如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好人多事少，添加虚拟的的“事”，对应系数矩阵为：标准形式，使用匈牙利法解之：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有第二步：找出矩阵每列的最小元素，再分别从每列中减去，不变第三步：用最少的直线覆盖所有“0”，得-1.6-1.6-1.6-1.6+1.6-0.9-0.9-0.9+0.9-0.3-0.3+0.3覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元

5、素．容易看出这5个“0”的位置第四步：圈“0”4.6分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表4.9所示、由于任务数多于人数，故考虑：任务E必须完成，其他4项中可任选3项完成其中有一人完成两项，其他每人完成一项试分别确定最优分配方案，使完成任务的总时间最少任务E必须完成，其他4项中可任选3项完成由于任务数多于人数，所以需要有一名假想的人，设为戌。因为工作E必须完成，故设戌完成E的时间为M，其余的假想时间为0，建立的效率矩阵如下所示：-4-4-4+4+4-1-1+1覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素．容易看出这5个“

6、0”的位置其中有一人完成两项，其他每人完成一项由于所有任务都必须由甲、乙、丙、丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值。所以构造的效率矩阵为：-4-4-4＋4-1-1-1+1覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素．容易看出这5个“0”的位置4.8用分枝定界法求解下列整数规划问题LPx1=3.5,x2=1.8Z(0)＝5.30x1≤3x1≥4LP1x1=3,x2=2Z(1)＝5LP2x1=4,x2=1.2Z(2)＝5.2x2≤1x2≥2LP3x1=4.17,x2=1Z(3)＝5.17LP4无可行解×x1≤4x1≥5LP5

7、x1=4,x2=1Z(5)＝5LP5x1=5,x2=0Z(5)＝5