解答运筹学整数规划作业

1、4.1 试利用0-1变量对下列各题分别表示成一般线性约束条件 x1 + x22 或 2x1 + 3x25 变量 x 只能取值0、3、5或7中的一个 若 x12，则x21，否则x2 4 以下四个约束条件中至少满足两个：a) x1 + x25，x12，x32，x3+x46 x1 + x22 或 2x1 + 3x25121122121222351,0 xxy Mxxy Myyy y或1b) 变量 x 只能取值0、3、5或7中的一个1231231233571,0 xyyyyyyy yy或1 若 x12，则x21，否则x241212212(1)4(1)01xyMxyMxy Mxy My 或d) 以下四个

2、约束条件中至少满足两个： x1 + x25，x12，x32，x3+x46121123334412341 4522620 xxy Mxy Mxy Mxxy Myyyyy或 14.2 某厂经常往外发送零部件。工厂根据长期发货情况决定专门生产一批为A1,A2,A6的6种不同规格的包装箱，其中A1最小，A2次之，A6最大。已知上述6种规格包装箱的需求量分别为Q1，Q2，Q6，生产每个箱的可变费用分别为c1,c2,c6 (c1c2c6)，生产不同规格包装箱的固定费用分别为k1,k2,k6，并且有00( )1iiiiiifor xC xkc xfor x式中xi为生产第i种规格包装箱的数量。若某种规格较小

3、的包装箱不生产或生产数量不够时，可用比其大的任一规格的包装箱代替。试为该厂建立一个生产上述6种规格包装箱各多少个的决策的数学模型，即满足该厂对6种规格包装箱的需求，又使总的费用为最小6166115511441133112211111 61 6min()1, 2.6.010iiiiiiiijijijijijijijijijijZykc xxMyfor ixQxQxQstxQxQxQyx取 或 ；且 为 整 数4.3 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小。若10个井位代号为S1,S2，S10，相应的钻探费用为c1,c2,c10，并且井位的选择上要满足下列条

4、件： 或选择S1和S7，或选择钻探S8 选择了S3或S4就不能选S5，或反过来也一样在S2、S6、S9、S10中最多只能选两个 或选择S1和S7，或选择钻探S8187811xxxx设01jx选择第 sj 个井位 不选择第 sj 个井位 选择了S3或S4就不能选S5，或反过来也一样354511xxxx 在S2、S6、S9、S10中最多只能选两个269102xxxx4.4 已知分配问题的效率矩阵如下，试用匈牙利法分别求出最优解3821038729764275842359106910第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 3821038729764275842359106

5、910222261608165075420536201334034第二步：找出矩阵每列的最小元素，再分别从每列中减去，有 16081650754205362013340341201104070530643004250002220230407053064300425000222023第三步：用最少的直线覆盖所有“0”，得覆盖所有零最少需要4条直线，表明矩阵中最多存在4个不同行不同列的零元素需要作变换04070530643004250002220232220427031042302425020200001第五步：用最少直线覆盖0427031042302425020200001即存在5个不同行不同列

6、的独立零元素。圈004270310423024250202000014.5 已知下列五名运动员各种姿势的游泳（各为50m）如表4.8所示。试问如何从中选拔一个450m混合泳的接力队，使预期的比赛成绩为最好人多事少，添加虚拟的的“事”，对应系数矩阵为：37.7 32.9 38.8 3735.443.4 33.1 42.2 34.7 41.833.3 28.5 38.9 30.4 33.629.2 26.4 29.6 28.5 31.100000标准形式，使用匈牙利法解之：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 37.732.938.837.035.443.433.14

7、2.234.741.833.328.538.930.433.629.226.429.628.531.10000032.933.128.526.404.805.94.12.510.309.11.68.74.8010.41.95.12.803.22.14.700000第二步：找出矩阵每列的最小元素，再分别从每列中减去，不变第三步：用最少的直线覆盖所有“0”，得4.805.94.12.510.309.11.68.74.8010.41.95.12.803.22.14.700000-1.6-1.6-1.6-1.6+1.63.204.32.50.98.707.507.13.208.80.33.51.201

8、.60.53.101.60003.204.32.50.98.707.507.13.208.80.33.51.201.60.53.101.6000-0.9-0.9-0.9+0.92.303.42.507.806.606.22.307.90.32.60.300.70.52.202.500.902.303.42.507.806.606.22.307.90.32.60.300.70.52.202.500.90-0.3-0.3+0.32.30.33.42.507.80.36.606.2207.602.3000.40.21.902.800.90覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零

9、元素容易看出这5个“0”的位置 第四步：圈“0”2.30.33.42.507.80.36.606.2207.602.3000.40.21.902.800.90*0000100010010001000000100X 4.6 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表4.9所示、由于任务数多于人数，故考虑： 任务E必须完成，其他4项中可任选3项完成 其中有一人完成两项，其他每人完成一项a) 试分别确定最优分配方案，使完成任务的总时间最少 任务E必须完成，其他4项中可任选3项完成由于任务数多于人数，所以需要有一名假想的人，设为戌。因为工作E必须完成，故设戌

10、完成E的时间为M，其余的假想时间为0，建立的效率矩阵如下所示：25293142373938262033342728403224423623252027234500000M046171219186013701135119130220000M50461771918608701130119130170000M-4-4-4+4+40021731914204110117011590134004M-1-1+10021831813103110118001480124005M覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素容易看出这5个“0”的位置 002183181310311011800

11、1480124005M*0100000010000011000000100X 其中有一人完成两项，其他每人完成一项由于所有任务都必须由甲、乙、丙、丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值。所以构造的效率矩阵为：252931423739382620333427284032244236234522520272320427262032046171219186013701135119130224760121504517719 18508700130119 1201747507-4-4-4400117319141041100170115801343103-1-1-1+100118318 130031100 180014701232002覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素容易看出这5个“0”的位置 00118318130031100180014701232002*0100000100000011000000010X4.8 用分枝定界法求解下列整数规划问题12121212max2516. 6