运筹学___整数规划习题.docVIP

第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 表4－1 设备 材 料 甲 乙 资源限量 材料A（kg） 2 3 14 材料B（kg） 1 0.5 4.5 利润（元/件） 3 2 解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下： 4.2 割平面法求解。（下表为最优表） 7 9 0 0 b CB XB x1 x2 x3 x4 9 x2 0 1 7/22 1/22 7/2 7 x1 1 0 －1/22 3/22 9/2 cj－zj 0 0 －28/11 －15/11 解： 线性规划的最优解为： 由最终表中得： ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 移项后得： 即： 只要把增加的约束条件加到B问题的最优单纯形表中。 表4－3 7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 7/22 1/22 0 7/2 7 x1 1 0 －1/22 3/22 0 9/2 0 x5 0 0 －7/22* －1/22 1 －1/2 cj－zj 0 0 －28/11 －15/11 0 这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到： 表4－4 7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 0 0 1 3 7 x1 1 0 0 1/7 －1/7 32/7 0 x3 0 0 1 1/7 －22/7 11/7 cj－zj 0 0 0 －1 －8 由计算结果知还没有得到整数解，重新再寻找割平面方程。 由x1行得： 将系数和常数项分解成整数和非负真分数之和： 得到新的约束条件： 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 7 9 0 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 1/7 －1/7 0 32/7 0 x3 0 0 1 1/7 －22/7 0 11/7 0 x6 0 0 0 －1/7* －6/7 1 －4/7 cj－zj 0 0 0 －1 －8 0 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 0 －1 1 4 0 x3 0 0 1 0 －4 1 1 0 x4 0 0 0 1 6 －7 4 cj－zj 0 0 0 0 －2 －7 则最优解为，最优目标函数值为z*=55。 4.3 max z＝4x1＋3x2＋2x3 隐枚举法 解：（1）先用试探的方法找出一个初始可行解，如x1＝x2＝0，x3＝1。满足约束条件，选其作为初始可行解，目标函数z0＝2。 （2）附加过滤条件 以目标函数作为过滤约束： 原模型变为： max z＝4x1＋3x2＋2x3 求解过程如表所示。 点 过滤条件 约束 z值 ④ ① ② ③ 4x1＋3x2＋2x3≥2 （0，0，0）T × （0，0，1）T √ √ √ √ 2 （0，1，0）T √ √ × （0，1，1）T √ √ √ √ 5 4x1＋3x2＋2x3≥5 （1，0，0）T × （1，0，1）T √ × （1，1，0）T √ √ √ √ 7 4x1＋3x2＋2x3≥7 （1，1，1）T √ √ √ √ 9 所以该0－1规划最优解为。 4.4 某公司拟在市东、西、南三区中建立门市部，有7个点Ai（i＝1，2，…，7）可供选择，要求满足以下条件： （1）在东区，在A1，A2，A3三个点中至多选两个； （2）在西区，A4，A5两个点中至少选一个； （3）在南区，A6，A7两个点为互斥点。 （4）选A2点必选A5点。 若Ai点投资为bi万元，每年可获利润为ci万元，投资总额为B万元，试建立利润最大化的0－1规划模型。 解：设决策变量为 建立0－1规划模型如下： 4.5 某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点最少的计划。 表4－9 消防车在各区间行驶时间表