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

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

2、，其中A1最小，A2次之，A6最大。已知上述6种规格包装箱的需求量分别为Q1，Q2，Q6，生产每个箱的可变费用分别为c1,c2,c6 (c1c2c6)，生产不同规格包装箱的固定费用分别为k1,k2,k6，并且有,式中xi为生产第i种规格包装箱的数量。若某种规格较小的包装箱不生产或生产数量不够时，可用比其大的任一规格的包装箱代替。,4,试为该厂建立一个生产上述6种规格包装箱各多少个的决策的数学模型，即满足该厂对6种规格包装箱的需求，又使总的费用为最小,5,6,4.3 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小。若10个井位代号为S1,S2，S10，相应的钻探费

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

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

5、-1.6,-1.6,+1.6,17,-0.9,-0.9,-0.9,+0.9,18,-0.3,-0.3,+0.3,覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素容易看出这5个“0”的位置,19,第四步：圈“0”,20,4.6 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表4.9所示、由于任务数多于人数，故考虑： 任务E必须完成，其他4项中可任选3项完成 其中有一人完成两项，其他每人完成一项 试分别确定最优分配方案，使完成任务的总时间最少,21,任务E必须完成，其他4项中可任选3项完成,由于任务数多于人数，所以需要有一名假想的人，设为戌。因为工作E必须完成，故设戌完成E的时间为M，其余的假想时间为0，建立的效率矩阵如下所示：,22,-4,-4,-4,+4,+4,23,-1,-1,+1,24,覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素容易看出这5个“0”的位置,25,26,其中有一人完成两项，其他每人完成一项,由于所有任务都必须由甲、乙、丙、丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值。所以构造的效率矩阵为：,27,-4,-4,-4,4,-1,-1,-1,+1,28,覆盖所有零最少需要5条直