解答运筹学整数规划作业概要优秀PPT.ppt

《解答运筹学整数规划作业概要优秀PPT.ppt》由会员分享，可在线阅读，更多相关《解答运筹学整数规划作业概要优秀PPT.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 试利用0-1变量对下列各题分别表示成一般线性约束条件 x1+x22 或 2x1+3x25变量 x 只能取值0、3、5或7中的一个若 x12，则x21，否则x2 4以下四个约束条件中至少满足两个：x1+x25，x12，x32，x3+x46a)x1+x22 或 2x1+3x25b)变量 x 只能取值0、3、5或7中的一个c)若 x12，则x21，否则x24d)以下四个约束条件中至少满足两个：x1+x25，x12，x32，x3+x464.2 某厂常常往外发送零部件。工厂依据长期发货状况确定特地生产一批为A1,A2,A6的6种不同规格的包装箱，其中A1最小，A2次之，A6最大。已知上述6种规格

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

3、，或选择钻探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个不同行不同列的零元素须要作变换222第五步：用最少直线覆盖

4、即存在5个不同行不同列的独立零元素。圈04.5 已知下列五名运动员各种姿态的游泳（各为50m）如表4.8所示。试问如何从中选拔一个450m混合泳的接力队，使预期的竞赛成果为最好人多事少，添加虚拟的的“事”，对应系数矩阵为：标准形式，运用匈牙利法解之：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 其次步：找出矩阵每列的最小元素，再分别从每列中减去，不变第三步：用最少的直线覆盖全部“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个“0”的位置

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

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