第五章 整数规划.ppt

浙江科技学院经济管理学院管工系 运筹学 ——管理科学与工程系 经济与管理学院 第五章 整数规划 5.1 整数规划数学模型和解的特点 5.2 割平面法和分支定界法 5.3 0-1整数规划 5.4 隐枚举法 5.5 匈牙利法 本章学习要求 熟悉分支定界法和割平面法的原理及其应用 掌握求解0-1规划问题的隐枚举法 掌握求解指派问题的匈牙利法 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量和可获得的利润及托运所受限制如表，问两种货物各托运多少箱，使得利润最大？ 设甲乙两种货物各托运X1,X2箱 Max z=20x1+10x2 5x1+4x2≤24 2x1+5x2≤13 x1,x2≥0且为整数 现有资金总额B，可供选择的投资项目有m个，项目j所需要的投资额和预期的收益分别为aj和cj，由于各种原因有3个附加条件：①若选项目1，则必选项目2，反之则不一定；②项目3和项目4必须选一个；③项目5，6，7中恰好选2个。应当如何选择投资项目才能使总预期收益为最大？ 解：每一个投资项目都有被选择和不被选择两种可能，设 xj=1 对j项目投资 0 对j项目不投资 Max z=∑cjxj ∑ajxj≤B x2≥x1 x3+x4≥2 x5+x6+x7=2 xj=0or1 5.相互排斥的约束条件 例： 3.实例 有一份英文说明书，需译成英文、日文、俄文和德文，分别记为E，J，R，G。有甲乙丙丁四人，他们将说明书翻译成不同语种所需时间如表，问应如何派人使工作所需总时间为最少？ 例: 对没有⊙的行打√ 对已打√的行中含有0元素的列打√ 再对打√的列中含有⊙的行打√ 重复2,3,直到得不到打√的行和列 划去没有打√的行和已经打√ 的列就得到覆盖所有0元素的最少的直线数. 例:有3个建筑公司A1,A2,A3，承建5个工程，所需时间见表，根据实际情况可以允许每家建筑公司承建一个或两个工程，求总时间最少的方案。 习题: 1.用分支定界法求 Max z=2x1+3x2 5x1+7x2≤35 4x1+9x2≤36 x1,x2≥0且为整数 2.用割平面法求 Max z=7x1+9x2 -x1+3x2≤6 7x1+x2≤35 x1,x2≥0且为整数 3.已知某运输问题的产销平衡表,单位运价表及给出的一个最优调运方案分别见表,试确定k的取值范围使最优解不变. 4.某玩具公司分别生产三种新型玩具,每月可供量分别为1000件,2000件和2000件,它们分别被送到甲乙丙三个百货商店,已知每月百货商店各类玩具预期销售量均为1500件,由于经营方面的原因,各商店销售不同玩具的盈利额不同,又知丙百货商店要求至少供应C玩具1000件,而拒绝进A重玩具,求满足上述条件下使各总盈利额为最大的供销方案. 5.已知某运输问题的产销平衡表与单位运价表,1)求最优调拨方案2)如产地III的产量变为130,又如B地区需要的115单位必须满足,试重新确定最优方案. 6.用隐枚举法求0-1型整数规划 Max z=3x1+2x2-5x3-2x4+3x5 x1+x2+x3+2x4+x5≤4 7x1 +3x3-4x4+3x5≤8 11x1-6x2 +3x4-3x5≥3 xj=0 or 1 7.从甲乙丙丁戊五人中选4人完成4项工作。已知每人完成各项工作的时间如表。规定每项工作只能由一个人去单独完成，每个人最多承担一项任务。又规定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务，在满足上述条件下，如何分配工作，使完成四项工作总的时间为最少。 8.已知 Max z=2x1-x2+x3 x1+x2+x3≤6 -x1+2x2 ≤4 xj≥0 1)求原问题最优解 2）求对偶问题最优解 3）当目标函数变为2x1+3x2+x3，最优解是否变化？ 4）如果右端常数项变为（3，4）T，最优解是否变化？ 5）增加一个变量C6＝3，P6＝ （1，3）T，最优解是否变化？ 6）增加一个约束条件-x1+2x3≥2,最优解是否变化？ 产量 成本 固定成本 变动成本 产量 成本 变动成本 设n种设备，第j种设备的产量为xj，设