第5章 整数规划

第四章整数规划 线性规划的扩展 整数规划IntegerProgrammingIP模糊线性规划fuzzylinearprogramming非线性规划NonlinearProgrammingNP组合优化Combinatorialoptimization图论参数规划多目标规划随机过程stochasticprogramming 线性规划的决策变量取值可以是任意非负实数 但许多实际问题中 只有当决策变量的取值为整数时才有意义 例如 产品的件数 机器的台数 装货的车数 完成工作的人数等 分数或小数解显然是不合理的 要求全部或部分决策变量的取值为整数的线性规划问题 称为整数线性规划 简称整数规划 IntegerProgramming 全部决策变量的取值都为整数 则称为全整数规划 AllIP 仅要求部分决策变量的取值为整数 则称为混合整数规划 MixedIP 要求决策变量只能取0或1值 则称为0 1规划 0 1Programming 第一节整数规划问题 为了满足整数要求 似乎可以把线性规划的小数最优解进行 舍入化整 以得到与最优解相近的整数解 舍入化整 一般是不可行的 化整后的解有可能成为非可行解 虽是可行解 却不是最优解 例如 一 问题的提出 问如何安排甲 乙两产品的产量 使利润为最大 解 设x1为甲产品的台数 x2为乙产品的台数 maxZ 6x1 5x22x1 x2 9 5x1 7x2 35x1 x2 0 x1 x2取整数不考虑整数约束则是一个LP问题 称为原整数规划的松弛问题 不考虑整数约束的最优解 x1 28 9 x2 25 9 Z 293 9舍入化整x1 3 x2 3 Z 33 不满足约束条件5x1 7x2 35 非可行解 x1 3 x2 2 Z 28 满足约束条件 是可行解 但不是最优解 x1 4 x2 1 Z 29 满足约束条件 才是最优解 步骤 在线性规划的可行域内列出所有决策变量可能取的整数值 求出这些变量所有可行的整数解 比较它们相应的目标函数值 最优的目标函数值所对应的解就是整数规划的最优解 实用性 只有两个决策变量 可行的整数解较少 3 3 二 整数规划的图解法 设备购置问题 某厂拟用M元资金购买m种设备 设备i的单价为pi 现有n个地点可装置这些设备 第j处最多可装置bj台 设备i装置在j处可获利cij元 如何购置 总利润最大 假设 购买第i种设备yi台数 将第i种设备安装在第j处的台数xij该问题的数学模型 三 整数规划问题举例 投资决策问题 某厂拟用b元资金投资n个项目 项目j需资金aj元 可获利cj元 应选择那些项目 获利最大 假设 xj 1表示投资项目j xj 0表示不投资项目j该问题的数学模型 工厂选址问题 某商品有n个销地 各销地的需求量为bj吨 天 现拟在m个地点中选址建生产厂 一个地方最多只能建一个工厂 若选i地建厂 生产能力为ai吨 天 固定费用为di元 天 已知i址至销地j的运价为cij元 吨 如何选址和安排调运 总费用最小 假设 yi 1 选择第i址建厂 yi 0 不选择第i址建厂 从厂址i至销地j运量为xij 该问题的数学模型 例1 某钻井队要从以下10个可供选择的井位中确定5个钻探 使总的钻探费用最少 若10个井的代号分别为s1 s2 s10 相应的费用为c1 c2 c10 满足下列条件 1 或选择s1和s7 或选择s82 选择了s3或s4就不能选择s5 反过来也一样3 在s5 s6 s7 s8中最多只能选择两个 试建整数规划模型 若 选择s2必须选择s6 否则都不选 第二节分枝定界法 分枝定界法 BranchandBoundMethod 基本思想 先求出整数规划相应的LP 即不考虑整数限制 的最优解 若求得的最优解符合整数要求 则是原LP的最优解 若不满足整数条件 则任选一个不满足整数条件的变量来构造新的约束 在原可行域中剔除部分非整数解 然后 再在缩小的可行域中求解新构造的线性规划的最优解 这样通过求解一系列线性规划问题 最终得到原整数规划的最优解 定界的含义 整数规划是在相应的线性规划的基础上增加变量为整数的约束条件 整数规划的最优解不会优于相应线性规划的最优解 对极大化问题来说 相应线性规划的目标函数最优值是原整数规划函数值的上界 对极小化问题来说 相应线性规划的目标函数的最优值是原整数规划目标函数值的下界 例maxZ 6x1 5x22x1 x2 9 5x1 7x2 35x1 x2 0 x1 x2取整数第一步 不考虑变量的整数约束 求相应LP 问题1 的最优解 x1 28 9 x2 25 9 Z1 293 9第二步 定界过程这个解不满足整数约束 这时目标函值Z1是整数规划的目标上界 因为x1 x2 0是整数规划问题的可行解 所以下界为0 第三步 分枝过程将不满足整数约束的变量x1进行分枝 x1称为分枝变量 构造两个新的约束条件 x1 28 9 3 x1 28 9 1 4 这样就把相应的线性规划的可行域分成两个部分 如图所示 问题2 maxZ 6x1 5x2问题3 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 4x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 求解相应的线性规划的最优解问题2相应的线性规划的最优解 x1 3 x2 20 7 Z2 226 7问题3相应的线性规划的最优解 x1 4 x2 1 Z3 29第四步 定界过程LP3的解满足整数约束 不必再分枝 它的目标函数值是29 大于原有下界0 则新的下界为29 现有上界为未分枝子问题中目标函数最大值 即为226 7 LP2的解仍不满足整数约束的要求 它的目标函数值226 7大于现有下界 则应继续分枝 第五步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 20 7 2 x2 20 7 1 3 问题4 maxZ 6x1 5x2问题5 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 2x2 3x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 求解相应的线性规划的最优解问题4相应的线性规划的最优解 x1 3 x2 2 Z4 28问题5相应的线性规划的最优解 x1 14 5 x2 3 Z5 159 5第六步 定界过程LP4的解满足整数约束 不必再分枝 它的目标函数值是28 小于原有下界29 则下界仍为29 现有上界为未分枝子问题中目标函数最大值 即为159 5 LP5的解仍不满足整数约束的要求 它的目标函数值159 5大于现有下界29 则应继续分枝 第七步 分枝过程将不满足整数约束的变量x1进行分枝 构造两个新的约束条件 x1 14 5 2 x1 14 5 1 3 问题6 maxZ 6x1 5x2问题7 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 3x2 3x1 2x1 3x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 求解相应的线性规划的最优解 问题6相应的线性规划的最优解 x1 2 x2 25 7 Z6 209 7问题7相应的线性规划的最优解 无最优解第八步 定界过程LP7的无最优解 不必再分枝 下界仍为29 现有上界为未分枝子问题中目标函数最大值 即为209 7 LP6的解仍不满足整数约束的要求 它的目标函数值209 7大于现有下界29 则应继续分枝 第九步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 3 x2 4 问题8 maxZ 6x1 5x2问题9 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 3x2 3x1 2x1 2x2 3x2 4x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 求解相应的线性规划的最优解问题8相应的线性规划的最优解 x1 2 x2 3 Z8 27问题9相应的线性规划的最优解 x1 7 5 x2 4 Z9 142 5第十步 定界过程LP8的最优解 满足整数约束 不必再分枝 下界仍为29 现有上界为未分枝子问题中目标函数最大值 即为29 虽然LP9的解仍不满足整数约束的要求 它的目标函数值142 5小于现有下界29 则不再继续分枝 上界 下界 得整数规划问题的最优解 x1 4 x2 1 Z 29 分枝定界过程 x1 3 x1 4 x2 2 x2 3 x1 2 x1 3 x2 3 x2 4 割平面法 P116 屠夫杀猪 一刀下去 又准又狠这一刀不能虚 也不能杀错位置1 原理 X1 X2 指派问题 分配问题 一 指派问题及其标准形式 指派问题的标准形式 以人和事为例 设有n个人和n件事 已知第i人做第j事的费用为 要求一个人和事之间一一对应的指派方案 使完成这n件事的总费用最少 一般称矩阵 为指派问题的系数矩阵 coefficientmatrix 为了建立标准指派问题的数学模型 引入n2个0 1变量 问题的数学模型可写成 0 1整数规划应用 指派问题 注意到 1从人来看 如果乙不作日语 损失特别大62从事来看 如果英语不分配给甲 损失特别大5 0 1整数规划应用 指派问题原理 从人的角度思考 考虑人最适合的工作从工作的角度思考 考虑工作最适合的人 各行都减去这一行的最小值 得到的0表示这个0所在的行对应的人最适合的工作是这个0所在的列对应的事 这一列有三个0 表示这一列的事有三个人适合做 行最小值 指派问题第一步 各行元素 该行行最小 各列元素 该列列最小 本题有n个独立的0元素则已得最优解 各列都减去这一列的最小值 得到的0表示这个0所在的列行对应的事最适合的人是这个0所在的行对应的人 甲俄乙日丙英丁德 列最小值 有三个人适合英文为什么确定丙英 指派问题的匈牙利法 第一步 各行元素 该行行最小 各列元素 该列列最小 若有n个独立的0元素则已得最优解 本题有n个独立的0元素 列仅一个零表示这个工作只适合一个人 行仅一个零表示这个人只适合一个工作 甲俄乙日丙英丁德 颜色表示 确定 指派问题的匈牙利法a 基本思路 修改系数矩阵的行 列至少有一个0元素 b 理论依据 若从系数矩阵的某行 或列 减去或加上一个数 则新的矩阵能得到与原问题相同的最优解 c 匈牙利法的要求 系数矩阵必须是方阵 系数矩阵所有的元素均非负 目标函数是求最小值 解题步骤 写出系数矩阵 并使每行 或列 至少有一个0元素 试求最优解 调整方案 变换矩阵 所有未划去的元素中取最小元素并减去之 然后在所划直线的交叉点加上该元素 指派问题的匈牙利法第一步 各行元素 该行行最小 各列元素 该列列最小 若有n个独立的0元素则已得最优解 否则转第二步第二步 1 从只有一个0元素的行 列 开始 把0元素记为 表示 确定 然后划去所在行 列 的其他0元素 记为0表示 不考虑 2 划去行 列 的新矩阵再回到 13 若仍有没划圈的0元素 且同行 列 至少有两个0元素 则从0元素最少的行 列 开始 试探若 确定 的数目m等于矩阵的阶n 则最优解得到第三步1对没有的行打 对应的人没找到合适的工作 2对已打的行中的所含0的列打 没找到工作的人最适合的工作 3对打的列中的所含0的行打 没有工作的人所适合的工作分给谁了 重复23对没有打的行划线 所有找到合适工作的人 对打的列划线 没找到合适工作的人最适合的工作 如直线数 任务数 转第四步 如直线数 任务数 最有解第四步 没有被直线覆盖的行找 最小元素 打的各行 最小元素 打的列 最小元素 得到的新矩阵有更多的0元素 若得到n个独立元素则求的最优解 否则回到第三步 例 华东交通大学工业工程与物流管理系 运筹学 第一步 变换系数矩阵 5 第二步 试指派 找到3个独立零元素但m 3 n 4 第三步 作最少的直线覆盖所有0元素 独立零元素的个数m等于最少直线数l 即l m 3 n 4 第四步 变换矩阵 bij 以增加0元素 没有被直线覆盖的所有元素中的最小元素为1 然后打 各行都减去1 打 各列都加上1 得如下矩阵 并转第二步进行试指派 得到4个独立零元素 所以最优解矩阵为 相关问题 非标准型的转化 1 maxZ cijxij minZ cij xij minZ M cij xij bijxijM是足够大的常数 新问题的最优解就是原问题的最优解 2 指派问题的计算机求解 练习 11 5 7 6 4 戊 6 9 6 3 7 丁 8 6 4 5 8 丙 9 11 7 12 9 乙 11 8 9 5 7 甲 E D C B A 费工作用人员 1 2 l m 4 n 5 l m 4 n 5 此问题有多个最优解 28 用匈牙利法求解下列指派问题 已知效率矩阵分别如下 0 1规划的应用 项目投资预算 变量假设 模型 0 1规划的应用 工厂 销售点配置问题 问题 为使经营成本最低 应开设那些工厂及销售点 工厂 销售点配置问题 模型参数 现实生活之中 我们也经常遇到指派人员做某项工作的情况 指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题 其他的一些应用如为一项任务指派机器 设备或者是工厂 TheAssignmentPro