解答运筹学整数规划作业

4.1试利用0-1变量对下列各题分别表示成一般线性约束条件a)x1+x2≤2或2x1+3x2≥5b)变量x只能取值0、3、5或7中的一个c)若x1≤2，则x2≥1，否则x2≤4d)以下四个约束条件中至少满足两个：x1+x2≤5，x1≤2，x3≥2，x3+x4≥6a)x1+x2≤2或2x1+3x2≥5121122121222351,0xxyMxxyMyyyy或1b)变量x只能取值0、3、5或7中的一个1231231233571,,0xyyyyyyyyy或1c)若x1≤2，则x2≥1，否则x2≤41212212(1)4(1)01xyMxyMxyMxyMy或d)以下四个约束条件中至少满足两个：x1+x2≤5，x1≤2，x3≥2，x3+x4≥6121123334412341~4522620xxyMxyMxyMxxyMyyyyy或14.2某厂经常往外发送零部件。工厂根据长期发货情况决定专门生产一批为A1,A2,…A6的6种不同规格的包装箱，其中A1最小，A2次之，…A6最大。已知上述6种规格包装箱的需求量分别为Q1，Q2，…，Q6，生产每个箱的可变费用分别为c1,c2,…c6(c1c2…c6)，生产不同规格包装箱的固定费用分别为k1,k2,…k6，并且有00()1iiiiiiforxCxkcxforx式中xi为生产第i种规格包装箱的数量。若某种规格较小的包装箱不生产或生产数量不够时，可用比其大的任一规格的包装箱代替。试为该厂建立一个生产上述6种规格包装箱各多少个的决策的数学模型，即满足该厂对6种规格包装箱的需求，又使总的费用为最小6166115511441133112211111~61~6min()1,2...6.010iiiiiiiijijijijijijijijijijZykcxxMyforixQxQxQstxQxQxQyx取或；且为整数4.3某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小。若10个井位代号为S1,S2，…S10，相应的钻探费用为c1,c2,…,c10，并且井位的选择上要满足下列条件：①或选择S1和S7，或选择钻探S8②选择了S3或S4就不能选S5，或反过来也一样③在S2、S6、S9、S10中最多只能选两个①或选择S1和S7，或选择钻探S8187811xxxx设01jx选择第sj个井位不选择第sj个井位②选择了S3或S4就不能选S5，或反过来也一样354511xxxx③在S2、S6、S9、S10中最多只能选两个269102xxxx4.4已知分配问题的效率矩阵如下，试用匈牙利法分别求出最优解3821038729764275842359106910第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有3821038729764275842359106910222261608165075420536201334034第二步：找出矩阵每列的最小元素，再分别从每列中减去，有16081650754205362013340341201104070530643004250002220230407053064300425000222023第三步：用最少的直线覆盖所有“0”，得覆盖所有零最少需要4条直线，表明矩阵中最多存在4个不同行不同列的零元素．需要作变换0407053064300425000222023－2－2＋20427031042302425020200001第五步：用最少直线覆盖0427031042302425020200001即存在5个不同行不同列的独立零元素。圈004270310423024250202000014.5已知下列五名运动员各种姿势的游泳（各为50m）如表4.8所示。试问如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好人多事少，添加虚拟的的“事”，对应系数矩阵为：37.732.938.83735.443.433.142.234.741.833.328.538.930.433.629.226.429.628.531.100000标准形式，使用匈牙利法解之：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有37.732.938.837.035.443.433.142.234.741.833.328.538.930.433.629.226.429.628.531.10000032.933.128.526.404.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.60.53.101.60003.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.902.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个不同行不同列的零元素．容易看出这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所示、由于任务数多于人数，故考虑：a)任务E必须完成，其他4项中可任选3项完成b)其中有一人完成两项，其他每人完成一项试分别确定最优分配方案，使完成任务的总时间最少a)任务E必须完成，其他4项中可任选3项完成由于任务数多于人数，所以需要有一名假想的人，设为戌。因为工作E必须完成，故设戌完成E的时间为M，其余的假想时间为0，建立的效率矩阵如下所示：25293142373938262033342728403224423623252027234500000M046171219186013701135119130220000M50461771918608701130119130170000M-4-4-4+4+40021731914204110117011590134004M-1-1+10021831813103110118001480124005M覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素．容易看出这5个“0”的位置0021831813103110118001480124005M*0100000010000011000000100Xb)其中有一人完成两项，其他每人完成一项由于所有任务都必须由甲、乙、丙、丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人，而不能假设为0值。所以构造的效率矩阵为：252931423739382620333427284032244236234522520272320427262032046171219186013701135119130224760121504517719185087001301191201747507-4-4-4＋400117319141041100170115801343103-1-1-1+100118318130031100180014701232002覆盖所有零最少需要5条直线，表明矩阵中存在5个不同行不同列的零元素．容易看出这5个“0”的位置00118318130031100180014701232002*0100000100000011000000010X4.8用分枝定界法求解下列整数规划问题12121212max2516.6530,0,Zxxxxstxxxx且为整数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≥5LP5x1=4,x2=1Z(5)＝5LP5x1=5,x2=0Z(5)＝5