运筹学第五章整数规划胡运权.ppt

运筹学 赵明霞山西大学经济与管理学院 2020 1 5 2 第五章整数规划 整数规划的数学模型割平面法分支定界法0 1整数规划指派问题应用 2020 1 5 3 3 求整数解的线性规划问题 不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的 而要用整数规划的方法加以解决 在整数规划中 如果所有的变量都为非负整数 则称为纯整数规划问题 如果只有一部分变量为非负整数 则称之为混合整数规划问题 如果所有的变量都为0 1变量 则称之为0 1规划 2020 1 5 4 4 例5 1某公司拟用集装箱托运甲 乙两种货物 这两种货物每件的体积 重量 可获利润以及托运所受限制如表所示 甲种货物至多托运4件 问两种货物各托运多少件 可使获得利润最大 第一节整数规划的数学模型 2020 1 5 5 5 解 设x1 x2分别为甲 乙两种货物托运的件数 建立模型Maxz 2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0为整数 如果去掉最后一个约束 就是一个线性规划问题 2020 1 5 6 6 得到线性规划的最优解为x1 2 44 x2 3 26 目标函数值为14 66 由图表可看出 整数规划的最优解为x1 4 x2 2 目标函数值为14 2020 1 5 7 7 性质 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值 2020 1 5 8 13 4 5 2 松弛问题 第二节割平面法 2020 1 5 9 设纯整数规划 伴随LP的最优解 若全为整数 则为IP的最优解 否则 若不全为整数 设第r行基变量非整 对应方程为 2020 1 5 10 将分离成一个整数与一个非负真分数之和 则有 等式两边都为整数并且有 2020 1 5 11 加入松弛变量 此式称为以r行为源行 来源行 的割平面 或分数切割式 或R E Gomory 高莫雷 约束方程 将Gomory约束加入到松弛问题 伴随LP 的最优表中 用对偶单纯形法计算 若最优解中还有非整数解 再继续切割 直到全部为整数解 则 2020 1 5 12 割平面法 即通过添加约束条件 逐步切割可行区域的边角余料 让其整数解逐步的露到边界或顶点上来 只要整数解能曝露到顶点上来 则就可以利用单纯形法求出来 关键是通过添加什么样的约束条件 既能让整数解往边界露 同时又不要切去整数解 这个条件就是Gomory约束条件 Gomory约束只是割去线性规划可行域的一部分 保留了全部整数解 2020 1 5 13 例5 5 2020 1 5 运筹学 线性规划 14 选择较大小数的行构造割平面 2020 1 5 运筹学 线性规划 15 2020 1 5 运筹学 线性规划 16 2020 1 5 17 分枝定界法是求解整数规划的一种常用的有效的方法 它既能解决纯整数规划的问题 又能解决混合整数规划的问题 大多数求解整数规划的商用软件就是基于分枝定界法而编制成的 先求解整数规划的线性规划问题 伴随LP 如果其最优解不符合整数条件 则求出整数规划的上下界 增加约束条件的办法 把相应的线性规划的可行域分成子区域 称为分枝 再求解这些子区域上的线性规划问题 不断缩小整数规划上下界的距离 最后得整数规划的最优解 第三节分枝定界法 2020 1 5 18 18 用分枝定界法求解目标函数值最大的整数规划的步骤 我们将求解的整数规划问题称为A 将与其相对应的线性规划问题称为B 第一步 求解问题B 可得以下情况之一 1 B没有可行解 则A也没有可行解 求解过程停止 2 B有最优解 且符合问题A的整数条件 则B的最优解即为A的最优解 求解过程停止 3 B有最优解 但不符合A的整数条件 记其目标函数值为z1 第二步 确定A的最优目标函数值z 的上下界 其上界即为 再用观察法找到A的一个整数可行解 求其目标函数值作为z 的下界 记为z 第三步 判断是否等于z 若相等 则整数规划最优解即为其目标函数值等于z的A的那个整数可行解 否则进行第四步 2020 1 5 19 第四步 在B的最优解中任选一个 或最远离整数要求的变量 不妨设此变量为xj 以 bj 表示小于bj的最大整数 构造以下两个约束条件 并加入问题B 得到B的两个分枝B1和B2 xj bj 和xj bj 1第五步 求解B1和B2 修改A问题的最优目标函数值z 的上下界 和z 第六步 比较和剪枝 各分枝的最优目标函数值中若有小于z者 则剪掉这枝 用打 表示 即以后不再考虑了 若大于 则不符合整数条件 则重复第三步至第六步 直至 z 求出最优解为止 对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似 例5 6 2020 1 5 运筹学 线性规划 20 例5 1 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0且x1 x2为整数 2020 1 5 运筹学 线性规划 21 2020 1 5 22 2020 1 5 23 0 1规划的分支定界法0 1规划的适用背景 双态变量的归一化 变量 不相容约束的归一化 约束条件 分段线性函数的归一化 目标函数 第四节0 1规划 24 双态变量的归一化 1 多个不全相容约束的归一化 25 不全相容约束的归一化 2020 1 5 26 2 约束常数项多个互斥取值的归一化 27 28 2020 1 5 29 3 多组约束的归一化 30 2020 1 5 31 31 1 固定费用的问题例5 2高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如表所示 不考虑固定费用 每种容器售出一只所得的利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人 月 机器有100台 月 此外不管每种容器制造的数量是多少 都要支付一笔固定的费用 小号是l00万元 中号为150万元 大号为200万元 现在要制定一个生产计划 使获得的利润为最大 分段线性函数的归一化 目标函数 2020 1 5 32 32 解 这是一个整数规划的问题 设x1 x2 x3分别为小号容器 中号容器和大号容器的生产数量 各种容器的固定费用只有在生产该种容器时才投入 为了说明固定费用的这种性质 设yi 1 当生产第i种容器 即xi 0时 或0 当不生产第i种容器即xi 0时 引入约束xi Myi i 1 2 3 M充分大 以保证yi 0 xi 0这样我们可建立如下的数学模型 Maxz 4x1 5x2 6x3 100y1 150y2 200y3s t 2x1 4x2 8x3 5002x1 3x2 4x3 300 x1 2x2 3x3 100 xi Myi i 1 2 3 M充分大xj 0yj为0 1变量 i 1 2 3 33 2 变动费用的问题 例5 3 2020 1 5 34 0 1规划的解法 隐枚举法 2020 1 5 35 求解思路 2020 1 5 36 2020 1 5 37 37 有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 例5 4有四个工人 要分别指派他们完成四项不同的工作 每人做各项工作所消耗的时间如下表所示 问应如何指派工作 才能使总的消耗时间为最少 第五节指派问题 2020 1 5 38 38 解 引入0 1变量xij 并令xij 1 当指派第i人去完成第j项工作时 或0 当不指派第i人去完成第j项工作时 这可以表示为一个0 1整数规划问题 Minz 15x11 18x12 21x13 24x14 19x21 23x22 22x23 18x24 26x31 17x32 16x33 19x34 19x41 21x42 23x43 17x44s t x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 A工作只能一人干 x12 x22 x32 x42 1 B工作只能一人干 x13 x23 x33 x43 1 C工作只能一人干 x14 x24 x34 x44 1 D工作只能一人干 xij为0 1变量 i j 1 2 3 4 2020 1 5 运筹学 线性规划 39 定理6 1 指派问题的匈牙利算法 如果从指派问题效率矩阵的每一行元素中分别减去 或加上 一个常数 称为该行的位势 从每一列分别减去 或加上 一个常数 称为该列的位势 得到一个新的效率矩阵 其中 则的最优解等价于的最优解 这里及均非负 41 定理6 2若矩阵A的元素可分成 0 与非 0 两部分 则覆盖零元素的最少直线数等于位于不同行不同列的零元素 称为独立元素 的最大个数 效率矩阵 在效率矩阵中找出4个不同行不同列的数使得它们的总和最小 效率矩阵的变形 找出4个不同行不同列的0元使得它们的和为最小0 令这些零元素对应的其余变量 0 得到最优解 一 算法的基本思想 基本步骤初始变换 0元获得最优性检验非优阵0元的最小直线集合非优阵变换 0元移动 43 标准化 min cij为方阵 cij为非负常数 44 2020 1 5 45 其他变异的指派问题 求最大值 人数与任务数不相等 某个人不能完成某项任务 2020 1 5 46 效率矩阵 1 求最大值 如果指派问题求最大值 用一个较大的数M去减效率矩阵中所有元素得到效率矩阵求矩阵B的最小值 矩阵B与矩阵C的最优解相同 通常令这个较大的数等于效率矩阵中的最大元素 2020 1 5 47 2020 1 5 48 当某人不能完成某项任务时 令对应的效率为一个大M即可 3 某个人不能完成某项任务 49 2020 1 5 50 第六节其它应用 投资问题选址问题人力资源分配问题工件排序问题 例5 61亿资金投资建厂 6个地址选择其中 地址1 2互斥 地址3 4互斥 地址1或2是地址3 4的前提条件 该公司应如何选址 51 1 投资问题 解 设xi为 52 2020 1 5 53 53 例5 7某公司在今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 但要求第一年投资最低金额为4万元 第二 三 四年不限 项目B 第三年初需要投资 到第五年末能回收本利128 但规定最低投资金额为3万元 最高金额为5万元 项目C 第二年初需要投资 到第五年末能回收本利140 但规定其投资额或为2万元或为4万元或为6万元或为8万元 项目D 五年内每年初可购买公债 于当年末归还 并加利息6 此项投资金额不限 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第五年末拥有的资金本利总额为最大 2020 1 5 54 54 解 1 设xiA xiB xiC xiD i 1 2 3 4 5 分别表示第i年年初给项目A B C D的投资额 元 设yiA yiB 是0 1变量 并规定取1时分别表示第i年给A B投资 否则取0 i 1 3 设yiC是非负整数变量 并规定 第2年投资C项目8万元时 取值为4 第2年投资C项目6万元时 取值3 第2年投资C项目4万元时 取值2 第2年投资C项目2万元时 取值1 第2年不投资C项目时 取值0 这样我们建立如下的决策变量 第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C 20000y2CDx1Dx2Dx3Dx4Dx5D 2020 1 5 55 55 2 约束条件 第一年 年初有100000元 D项目在年末可收回投资 故第一年年初应把全部资金投出去 于是x1A x1D 100000 第二年 A的投资第二年末才可收回 故第二年年初的资金为1 06x1D 于是x2A x2C x2D 1 06x1D 第三年 年初的资金为1 15x1A 1 06x2D 于是x3A x3B x3D 1 15x1A 1 06x2D 第四年 年初的资金为1 15x2A 1 06x3D 于是x4A x4D 1 15x2A 1 06x3D 第五年 年初的资金为1 15x3A 1 06x4D 于是x5D 1 15x3A 1 06x4D 关于项目A的投资额规定 x1A 40000y1A x1A 200000y1A 200000是足够大的数 保证当y1A 0时 x1A 0 当y1A 1时 x1A 40000 关于项目B的投资额规定 x3B 30000y3B x3B 50000y3B 保证当y3B 0时 x3B 0 当y3B 1时 50000 x3B 30000 关于项目C的投资额规定 x2C 20000y2C y2C 0 1 2 3 4 2020 1 5 56 56 3 目标函数及模型 Maxz 1 1