整数规划与分配问题-运筹学.ppt

2020 4 16 1 运筹学OPERATIONSRESEARCH 2020 4 16 2 第四章整数规划与分配问题 IntegerProgramming IP 整数规划的有关概念及特点指派问题及匈牙利解法整数规划的求解方法 分枝定界法 割平面法0 1规划的求解方法 隐枚举法整数规划的应用 2020 4 16 3 纯整数规划 在整数规划中 如果所有的变量都为非负整数 则称为纯整数规划问题 混合整数规划 如果有一部分变量为非负整数 则称之为混合整数规划问题 0 1变量 在整数规划中 如果变量的取值只限于0和1 这样的变量我们称之为0 1变量 0 1规划 在整数规划问题中 如果所有的变量都为0 1变量 则称之为0 1规划 1整数规划的有关概念及特点 一 概念 整数规划 要求决策变量取整数值的规划问题 线性整数规划 非线性整数规划等 松弛问题 整数线性规划模型 整数线性规划类型 1 纯整数线性规划 2 混合整数线性规划 3 0 1型整数线性规划 人员安排问题 投资组合问题 物资运输问题 人员安排问题 医院护士24小时值班 每次值班8小时 不同时段需要的护士人数不等 据统计 最少需要多少护士 minz x1 x2 x3 x4 x5 x6x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x6 x1 60 xj 0 j 1 2 6 设x1 x2 x6为各班新上班人数 人员安排问题 证券投资 把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润 项目投资 财团或银行把资金投入到若干项目中以获得中长期的收益最大 投资组合问题 现有资金总额为B 可供选择的投资项目有n个 项目j所需投资额和预期收益分别为aj和cj j 1 2 n 此外 由于种种原因 有三个附加条件 第一 若选择项目1 就必须同时选择项目2 反之 则不一定 第二 项目3和4中至少选择一个 第三 项目5 6和7中恰好选择两个 应当怎样选择投资项目 才能使总预期收益最大 模型 变量 每个项目是否投资约束 总金额不超过限制 3个附加条件目标 总收益最大 模型 物资运输问题 工厂A1和A2生产某种物资 由于该种物资供不应求 故需要再建一家工厂 相应的建厂方案有A3和A4两个 这种物资的需求地有B1 B2 B3 B4四个 各工厂年生产能力 各地年需求量 各厂至各需求地的单位物资运费cij i j 1 2 3 4 工厂A3或A4开工后 每年的生产费用估计分别为1200万元或1500万元 现要决定应该建设工厂A3还是A4 才能使今后每年的总费用最少 再引入一个0 1变量y 特征 变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质 可行域是离散集合 模型的特点 与线性规划的关系 整数规划 放松的线性规划 可行解是松弛问题的可行解 最优值不会优于其松弛问题的最优值 注释 最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于顶点 枚举法不可取 2020 4 16 18 求整数解的线性规划问题 不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的 用枚举法又往往会计算量太大 所以要用整数规划的特定方法加以解决 例 求解下列整数规划 二 整数规划的求解特点 2020 4 16 19 分析 若当作一般线性规划求解 图解法的结果如下 1 非整数规划最优解显然不是整数规划的可行解 2 四舍五入后的结果也不是整数规划的可行解 3 可行解是阴影区域交叉点 可比较这些点对应的函数值 找出最优 2020 4 16 20 2指派问题及匈牙利解法 一 指派问题与模型 m项任务分配给m个人去完成 每人只能完成其中一项 每项任务只能分给一人完成 应如何分配使得效率最高 aij是第j个人完成第i项任务的效率 2020 4 16 21 设于是建立模型如下 2020 4 16 22 二 指派问题的匈牙利解法 该指派问题可当作运输问题解决 但匈牙利解法更有效 解法思想 效率矩阵的元素 若有一组位于不同行不同列的零元素 则令这些位置的决策变量取值为1 其余均为0 这显然就是最优解 2020 4 16 23 定理2 若矩阵A的元素可分为 0 元和 非0 元 则覆盖 0 元的最少直线数等于位于不同行 不同列的 0 元的最大个数 定理1 效率矩阵的每一行元素分别减去 加上 一个常数 每一列元素分别减去 加上 一个元素 得新效率矩阵 则的最优解等价于的最优解 2020 4 16 24 例 有一份说明书 要分别译成英 日 德 俄四种语言 交给甲 乙 丙 丁四人去完成 各人的效率不同 如何分配任务 可使总效率最高 2020 4 16 25 匈牙利解法步骤 1 在效率矩阵每行减去该行最小元素 2 在效率矩阵每列减去该列最小元素 2020 4 16 26 3 寻找独立 0 元素 不同行不同列 1 从第一行开始 若该行只有一个 0 元素 则对该 0 元素打括号 表示这一行的人只有这一个任务可指派 并划去该 0 元素所在的列 表示该项任务不能再指派给别人 若该行无 0 元素或有两个以上的 0 元素 不含划去的0 则转下一行 2 从第一列开始 若该列只有一个 0 元素 则对该 0 元素打括号 并划去该 0 元素所在的行 若该列无 0 元素或有两个以上的 0 元素 不含划去的0 则转下一列 2020 4 16 27 完成上述步骤后可能出现下列情况 效率矩阵的每一行都有一个打括号的0元素 则按照打括号的0元素位置指派任务 即是最优解 打括号的0元素个数小于m 但未被划去的0元素之间存在闭回路 则沿此闭回路 每隔一个0元打一括号 然后对打括号的0元素所在行或所在列画直线 矩阵中所有0元素或被打括号 或被划去 但打括号的0元素个数 则进入下一步 2020 4 16 28 3 设法使每一行都有一个打括号的 0 元素 按定理1继续对矩阵进行变换 从矩阵未被直线覆盖的元素中找出最小者k 对矩阵中无直线覆盖的行 令 有直线覆盖的列 令 其余为0 对矩阵的每个元素计算 得到一个新矩阵 转第三步重复进行 直至每一行都有一打括号的0元素 2020 4 16 29 根据上图 k 2 最优解 2020 4 16 30 思考 1 任务数人数时如何处理2 指派问题中目标函数变为MAX时如何处理 两点说明 1 效率矩阵不是方阵的情况 即人员与工作数不相等 处理方法 增加虚拟人或工作 使两者相等 虚拟人或工作对应的效率矩阵中元素为0 2 最大化分配问题的处理 如果给出的效率矩阵中的数字表示每个人完成各项任务的收益 则问题变成了如何分配任务才能使总收益最大 处理方法 用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵 对这个新的矩阵用匈牙利方法求解 练习1 用匈牙利方法求解下列问题 例1 设某工程有B1 B2 B3 B4四项任务 需由四个工人A1 A2 A3 A4去完成 由于任务性质和每个工人的技术水平不相同 他们完成各项任务所需的时间也不一样 见下表 问应当如何分配 即哪个人去完成哪项任务 才能使完成四项任务的总时间最少 设 效率矩阵 效率矩阵 第一步 初始变换 得解矩阵 找独立0元素 总时间为 4 4 9 11 28 练习2 用匈牙利解法解下列分配问题 效率矩阵 第一步 初始变换 第二步 寻找独立0元素 最小元素为min 10 5 7 2 6 3 6 5 2 2 2 2 它有5个独立0元 得到最优解相应的解矩阵为 最优目标值 7 6 9 6 4 32 练习3 求解下列分配问题 效率矩阵 1 1 1 第一组最优解 第二组最优解 2020 4 16 42 3分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法 它既能解决纯整数规划的问题 又能解决混合整数规划的问题 大多数求解整数规划的商用软件就是基于分枝定界法编制而成的 下面举例来说明分枝定界法的思想和步骤 2020 4 16 43 性质求MAX的问题 整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值 求MIN的问题 整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值 1 求解整数规划相应的一般线性规划问题 即先去掉整数约束 易知 整数规划的可行域 小 包含于线性规划的可行域 大 若线性规划的最优解恰是整数解 则其就是整数规划的最优解 否则该最优解 是整数规划最优解的上界或下界 2020 4 16 44 例 求解下列整数规划 解 1 解对应的线性规划 其最优解为 显然不是整数规划的可行解 L0 2020 4 16 45 2 分枝与定界 将对应的线性规划问题分解成几个子问题 每个子问题就是一分枝 而所有子问题的解集之和要包含原整数规划的解集 求解每一分枝子问题 若其最优解满足整数约束 则它就是原问题的一个可行解 不一定是最优 否则 就是该枝的上界或下界 若所有分支的最优解都不满足整数条件 即不是原问题的可行解 则选取一个边界值最优的分支继续分解 直至找到一个原问题的可行解 若在同一级分枝中同时出现两个以上的原问题可行解 则保留目标值最优的一个 其余不再考虑 从各分枝中找原问题可行解的目的是为下一步的比较与剪枝 2020 4 16 46 将上述线性规划问题分为两枝 并求解 解得 解得 L1 L2 显然两个分枝均非整数可行解 选边界值较大的L1继续分枝 2020 4 16 47 将L1分为两枝 并求解 解得 解得 L11 L12 两个分枝均是整数可行解 保留目标值较大的L12 2020 4 16 48 3 比较与剪枝将各子问题的边界值与保留下的整数可行解对应的目标值比较 将边界值劣于可行行解的分支减剪去 若比较剪枝后 只剩下所保留的整数可行解 则该解就是原整数规划的最优解 否则选取边界值最大的一个分枝继续分解 在其后的过程中出现新的整数可行解时 则与原可行解比较 保留较优的一个 重复第三步 2020 4 16 49 L0 X2 2 X2 3 X1 3 X1 4 用图表示上例的求解过程与求解结果 练习1 用分支定界法求解下列整数规划 1 2 3 1 2 3 3 2 10 3 x1 3 2 分为x1 1与x1 2 S2 S1 分别解之 先放弃 整数 要求求出一个最优解 1 2 3 1 2 3 S1 S2 解S1 求出一个最优解 2 23 9 maxz 41 9 解S2 求出一个最优解 1 7 3 maxz 10 3 2 23 9 x2 23 9 分为x2 2与x2 3 可行域为空 S12 S11 1 2 3 1 2 3 S12 33 14 2 解S12 求出一个最优解 33 14 2 maxz 61 14 可行域为空 10 3 61 14 x1 33 14 分为x1 2与x1 3 S121 S122 1 2 3 1 2 3 可行域为空 10 3 S121 S122 解S121 求出一个最优解 3 1 maxz 4 解S122 求出一个最优解 2 2 maxz 4 2 2 3 1 最优整数解为 3 1 和 2 2 最优值为4 2020 4 16 55 4割平面法 一 基本思想 在整数规划的松弛问题中 依次引进新的约束条件 割平面 使问题的可行域逐步减小 但每次割去的只是部分非整数解 直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点 这样就可以用线性规划的方法求得整数最优解 2020 4 16 56 例 求解下列整数规划 解 1 解对应的线性规划 松弛问题 并将约束条件的系数均化为整数 2020 4 16 57 加入松弛变量后求解 得最终单纯形表 如果上述求解结果是整数解 则结束 否则转下一步 2 找出非整数解中分数部分最大的一个基变量 并将该行对应的约束方程所有常数 系数及常数项 分解成一个整数与一个正分数之和 将所有分式项移到等式右端 例如上例 取第一行约束 2020 4 16 58 易知 左端为整数 要是等式成立 右端也必为整数 且 将代入上式 得 2020 4 16 59 这就是一个割平面 将其添加到原约束中 得到新的可行域如图所示 割去的只是部分非整数解 2020 4 16 60 3 将新的约束添加到原问题中 得到一个新的线性规划问题 求解此问题 可用灵敏度分析的方法 4 重复上述的1 3步 直至求出整数最优解 将反应到最终表中 得 2020 4 16 61 运用对偶单纯形法 解得 此解仍非整数解 将基变量对应的约束分解为 得到新的约束 2020 4 16 62 此时已得整数最优解 2020 4 16 63 约束 即为 用割平面法求解整数规划问题 解 增加松弛变量x3和x4 得到 LP 的初始单纯形表和最优单纯形表 割平面法练习1 将x3 6 3x1 2x2 x4 3x1 2x2 带入中 得到等价的割平面条件 x2 1见下图 现将生成的割平面条件加入松弛变量 然后加到表中 此时 X1 2 3 1 Z 1 仍不是整数解 继续以x1为源行生成割平面 其条件为 用上表的约束解出x4和s1 将它们带入上式得到等价的割平面条件 x1 x2 见图 将生成的割平面条件加入松弛变量 然后加到表中 至此得到最优表 其最优解为X 1 1 Z 1 这也是原问题的最优解 有以上解题过程可见 表中含有分数元素且算法过程中始终保持对偶可行性 因此 这个算法也称为分数对偶割平面算法 割平面法练习2 初始表 最优表 在松弛问题最优解中 x1 x2均为非整数解 由上表有 将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可 解题经验表明 考虑式子右端最大真分数的式子 往往会较快地找到所需割平面约束条件 以上两个式子右端真分数相等 可任选一个考虑 现选第二个式子 并将真分数移到右边得 引入松弛变量s1后得到下式 将此约束条件加到上表中 继续求解 得到整数最优解 即为整数规划的最优解 而且此整数规划有两个最优解 X 0 4 Z 4 或X 2 2 Z 4 第五节0 1问题 50 1规划的求解隐枚举法 解0 1规划的隐枚举法有其独特的工作程序 具体过程如下 a 模型转化为求极小的问题b 变量替换 极小问题模型的目标函数中所有变量系数为负的0 1变量 可利用变量替换xk 1 x k x k是引入的新的0 1变量 将目标函数中所有变量系数化为正数 c 目标函数中变量按系数大小排列 约束条件中变量排列顺序也相应调整 d 按目标函数值由小到大的顺序依次排列可能的解 并予以可行性检验 e 发现求极小问题的最优解并停止 f 转化为原问题的最优解 0 1整数规划是一种特殊形式的整数规划 这时的决策变量xi只取两个值0或1 一般的解法为隐枚举法 1 m个约束条件只有k个起作用 m个约束条件可表示为 增加变量定义为 又设M为任意大的数 则 表明 m个约束条件中有m k个的右端项为bi Myi 不起约束作用 6应用举例 实例 maxZ 3x1 5x2x1 8 2x2 12 三个约束中只有两个起作用3x1 4x2 36x1 0 x2 0 引入辅助变量 模型化为 maxZ 3x1 5x2x1 8 My1 2x2 12 My23x1 4x2 36 My3y1 y2 y3 1x1 0 x2 0 yi只取0或1 2 约束条件的右端可能是b1或b2 br 即 引入变量定义为 则原约束可表示为 例如 某约束为2x1 5x2 x3 2或3 引入辅助变量y1 y2 约束化为 2x1 5x2 x3 2y1 3y2 y1 y2 1 y1 y2只取0或1 3 两组条件满足其中一组 若x1 4 则x2 1 否则 即x1 4时 x2 3 引入变量定义为 又M为任意大的数 则问题可表达为 4 用以表示含固定费用的函数 用xj代表产品j的生产量 其生产费用函数通常可表示为 Kj为与生产量无关的生产准备费用 解决方法 设置一个逻辑变量yj 当xj 0时 yi 0 当xj 0时 yj 1