整数规划ppt课件.ppt

整数规划 第1页 第一节整数规划问题的提出第二节分支定界法第三节割平面法第四节0 1整数规划第五节指派问题 第2页 在线性规划问题中 有些最优解可能是分数或小数 但对于某些具体问题 常有要求解答必须是整数的情况 第一节整数规划问题的提出 第3页 要求一部分或全部决策变量必须取整数值的线性规划问题称为整数线性规划 IntegerlinearProgramming 简称IP 一 整数线性规划数学模型的一般形式 第4页 整数线性规划数学模型的一般形式为 第5页 整数线性规划问题可以分为下列几种类型 1 纯整数 全整数 线性规划 pureintegerlinearprogramming 指全部决策变量都必须取整数值的整数线性规划 第6页 2 混合整数线性规划 mixedintegerlinearprogramming 指决策变量中有一部分必须取整数值 另一部份可以不取整数值的整数线性规划 3 0 1型整数线性规划 zero oneintegerlinearprogramming 指决策变量只能取值0或1的整数线性规划 第7页 二 整数线性规划的松弛问题 松弛问题 slackproblem 不考虑整数条件 由余下的目标函数和约束条件构成的线性规划问题称为该整数规划问题的松弛问题 slackproblem 第8页 第9页 maxz 2x1 3x2 maxz 2x1 3x2 整数规划 松弛问题 第10页 1 整数线性规划的可行解集合是其松弛问题可行解集合的一个子集 即 三 整数线性规划的解和其松弛问题的解之间的关系 整数规划可行域 松弛问题可行域 第11页 整数线性规划的可行解集合其松弛问题可行解集合从而可得出 整数线性规划的可行解一定也是其松弛问题的可行解 松弛问题的可行解不一定是整数线性规划的可行解 整数线性规划最优解的目标函数值 松弛问题最优解的目标函数值 极大化问题 第12页 2 松弛问题的可行解集合 凸集 任意两个可行解的凸组合仍为可行解 整数线性规划的可行解集合 不是凸集 任意两个可行解的凸组合不一定满足整数要求 因而不一定仍为可行解 第13页 产生问题 利用对松弛问题的最优解中不符合整数要求的分量简单地取整 是否能得出整数规划问题的最优解呢 第14页 3 对松弛问题的最优解中不符合整数要求的分量简单地取整 所得到的问题解 不一定是整数线性规划问题的最优解 甚至也不一定是整数线性规划问题的可行解 第15页 例 第16页 解 问题的最优解为 x1 4 8 x2 0其中分量x1不满足整数要求 从而对分量x1进行 化整 第17页 为可行解 但不是最优解 x1 4 x2 1更优 第18页 不满足约束条件1 从而为不可行解 第19页 结论 利用求解整数线性规划的松弛问题的最优解 再化整的方法无法得出整数线性规划的最优解 第20页 纯整数规划问题 可行解的数量是有限的 小型纯整数规划问题 可通过全枚举法 从中筛选最优解 大型纯整数规划问题 可行解的数量很大 无法使用全枚举法 混合整数规划问题 可行解的数量是无限的 无法使用全枚举法 第2节分支定界法 第21页 20世纪60年代由LandDoig和Dakin等人提出了一种仅检查可行域内可行的整数组合的一部分 就能定出最优整数解的方法 称为分支定界法 branchandboundmethod 一 分支定界法的提出 第22页 它是在枚举法基础上的改进 是一种隐枚举法 implicitenumeration 或部分枚举法 不是一种有效算法 第23页 特点 它比枚举法优越 因为它仅在一部分可行解的整数解中寻找最优解 计算量比枚举法要小 但若变量数目很大 则其工作量也相当可观 第24页 步骤1求解整数线性规划问题A的松弛问题B B没有可行解 A也没有可行解 停止 B有最优解 且符合整数条件 B的最优解就是A的最优解 停止 B有最优解 但不符合整数条件 转步骤2 二 分支定界法的步骤 第25页 步骤2分支和定界分支在B的最优解中任选一个不符合整数条件的变量xj bj 并构造两个约束条件 并将这两个约束条件加入问题B 得到两个分支问题B1和B2 并求解这两个分支问题B1和B2 第26页 A的下界 max max 符合整数条件的分支的目标函数值 令初始 0 定界 第27页 步骤3比较和剪枝 比较比较多个目标函数值大于且不满足整数要求的分支 选择目标函数值最大的分支继续分支 返回步骤2 第28页 剪枝目标函数值小于且不满足整数要求的分支 停止继续分支 即剪掉该枝 无可行解的分支 停止继续分支 即剪枝 满足整数要求的分支 停止分支 即剪枝 第29页 例 求解 第30页 解 1 利用单纯型法求解原问题的松弛问题B 第31页 第32页 最优解为 2 x1和x2均为分数 任选x1进行分支 第33页 问题B2 问题B1 第34页 问题B x1 x2 z x1 3 x1 4 0 第35页 问题B1 问题B 第36页 解 问题B的最终单纯形表 增加了约束条件x1 3后 第37页 将约束条件x1 x5 3加入到单纯形表最后一行 第38页 将x1的系数列向量变为单位向量 并计算检验数 第39页 旋转运算 问题B1 第40页 问题B2 问题B 第41页 解 问题B的最终单纯形表 增加了约束条件x1 4后 第42页 将约束条件x1 x5 x6 4加入到单纯形表最后一行 第43页 将x1的系数列向量变为单位向量 并计算检验数 第44页 旋转运算 问题B2 第45页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 0 x2 3 x2 4 第46页 3 比较问题B1和B2的目标函数值 选择问题B1进行分支 问题B3 最优解 x1 3 x2 3 z 33 停止分支 第47页 问题B4 最优解 继续分支 第48页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 33 问题B4 x1 x2 4 z x2 3 x2 4 问题B3 x1 3 x2 3 z 33 0 x1 2 x1 3 第49页 4 比较问题B2和B4的目标函数值 选择问题B4进行分支 问题B5 最优解 继续分支 第50页 问题B6 无可行解 停止分支 第51页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 33 问题B4 x1 x2 4 z x2 3 x2 4 问题B3 x1 3 x2 3 z 33 问题B5 x1 2 x2 z 问题B6 无可行解 x1 3 x1 3 第52页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 33 x2 3 x2 4 问题B3 x1 3x2 3z 33 问题B4 x1 x2 4 z 问题B5 x1 2x2 z 问题B6 无可行解 x1 3 x1 3 x2 3 x2 2 第53页 5 比较问题B2和B5的目标函数值 选择问题B2进行分支 问题B7 最优解 继续分支 第54页 问题B8 无可行解 停止分支 第55页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 33 x2 3 x2 4 问题B3 x1 3x2 3z 33 问题B4 x1 x2 4 z 问题B5 x1 2x2 z 问题B6 无可行解 x1 3 x1 3 问题B7 x1 x2 2z 问题B8 无可行解 x2 3 x2 2 x1 3 x1 5 第56页 6 比较问题B5和B7的目标函数值 选择问题B5进行分支 问题B9 最优解 停止分支 故 第57页 问题B10 最优解 停止分支 故 第58页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 34 x2 3 x2 4 问题B3 x1 3x2 3z 33 问题B4 x1 x2 4 z 问题B5 x1 2x2 z 问题B6 无可行解 x1 3 x1 3 问题B7 x1 x2 2z 问题B8 无可行解 x2 3 x2 2 问题B9 x1 2 x2 4 z 34 问题B10 x1 0 x2 5 z 30 x1 3 x1 5 33 第59页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 34 问题B7 x1 x2 2z 问题B8 无可行解 x2 3 x2 2 x1 4 x1 5 第60页 7 选择问题B7进行分支 问题B11 最优解 停止分支 故 第61页 问题B12 最优解 停止分支 故 第62页 问题B x1 x2 z 问题B2 x1 4 x2 z 36 问题B1 x1 3 x2 z x1 3 x1 4 34 问题B7 x1 x2 2z 问题B8 无可行解 x2 3 x2 2 问题B11 x1 4 x2 2 z 32 问题B12 x1 5 x2 z 33 x1 4 x1 5 第63页 从而问题的最优解为 x1 2 x2 4 z 34 第64页 割平面法是由高莫瑞 Gomory 于1958年提出的 所以该方法又称为Gomory法 第三节割平面法 第65页 思路 暂时不考虑整数规划的整数条件 而有规律地增加线性约束条件 在几何上称为割平面 使得原可行域被切割掉一部分 但被切割掉的这部分不包含任何整数可行解 同时缩减后的可行域凸性不变 采取这样的方法 一直到获得整数规划的最优解为止 第66页 通过举例来阐述割平面的概念 一 割平面的概念 例 第67页 可行域 ABCD 最优解 C点 其坐标为 第68页 在图中增加两个线性约束条件 PQ和MN 增加割平面的目的 将原凸可行域ABCD缩减 变成新的凸可行域ABEFGD 使得新可行域的ABEFGD顶点F x1 4 x2 3 对应着原整数线性规划问题的最优解 第69页 2 5 A D C B 7 3 M N P Q x1 x2 4 G F E 割去的部分EFGCE中不包含任何整数解 第70页 新增加的线性约束条件切割掉了原问题可行域的一部分 但该可行域内不包含任何整数可行解 所有整数可行解全部都保留在被切割之后的可行域内 第71页 故该约束条件具备如下两个基本性质 已获得的不符合整数要求的松弛问题的最优解 不满足该约束条件 所有整数可行解都满足该约束条件 第72页 具备上述两个基本性质的线性约束条件称为割平面约束或高莫瑞约束 现在面对的问题就是如何产生这样的割平面约束条件或高莫瑞约束 第73页 二 割平面约束方程 高莫瑞约束方程 整数规划问题的模型 第74页 松弛问题的模型 松弛问题可以用单纯形法求解 在最优单纯形表中可得到 第75页 其中 Q指构成基变量的号码集合 K指构成非基变量的号码集合 1 基变量 非基变量 第76页 将aik和bi都分解成整数部分N和非负真分数f之和 aik Nik fik 其中Nik aik且为整数 0 fik 1 2 bi Ni fi 其中Ni bi且为整数 0 fi 1 3 可以为负整数或0 第77页 Nik fik Ni fi 第78页 将式 2 和式 3 代入式 1 可得 4 第79页 将式 4 的整数项移到等式左端 分数项移到等式右端可得 5 第80页 对式 5 进行分析 如果xi和xk为整数解 因为Nik Ni均为整数 所以为整数 第81页 因为 所以又因为必须为整数 所以 第82页 由此可以得出整数解的必要条件为 6 第83页 将式 6 做如下变化 7 约束条件 7 就是割平面约束方程 或高莫瑞约束方程 第84页 下面来验证式 7 是否满足割平面约束的两个性质 1 设整数线性规划问题A的松弛问题B的最优解为X x1 xm 0 0 T 且x1 xm中有分数 则f1 fm不全为0 代入式 7 第85页 即已获得的不符合整数要求的松弛问题的最优解 不满足该约束条件 式 7 左端 式 7 右端 故式 7 不满足 为分数 第86页 即所有整数可行解都满足该约束条件 2 设整数线性规划问题A的松弛问题B的最优解为X x1 xm 0 0 T 且x1 xm全为整数 则f1 fm全为0 代入式 7 式 7 左端 式 7 右端 故式 7 满足 第87页 三 割平面法步骤1求解整数线性规划问题A的松弛问题B B没有可行解 A也没有可行解 停止 B有最优解 且符合整数条件 B的最优解就是A的最优解 停止 B有最优解 但不符合整数条件 转步骤2 第88页 步骤2构造割平面约束在B的最优解中 比较不符合整数条件的各基变量值xi bi Ni fi 其中Ni bi且为整数 0 fi 1 寻找fi最大 如有多个最大的fi 则任选 的构造割平面约束 第89页 步骤3求解将松弛问题的最终单纯形表中增加一行 插入高莫瑞约束方程 求解 最优解满足整数要求 停止 最优解不满足整数要求 转步骤2 构造新的割平面约束 第90页 例 第91页 解 1 利用单纯型法求解原问题的松弛问题B 第92页 2 构造割平面约束 x1 9 2 4 1 2x2 7 2 3 1 2 选择x2构造割平面约束 等价于约束条件x2 3 第93页 3 求解 第94页 最优解不满足最优解要求 需要构造新的割平面约束 第95页 4 构造割平面约束 x1 32 7 4 4 7x3 11 7 1 4 7 选择x1构造割平面约束 等价于约束条件x1 x2 7 第96页 5 求解 第97页 第98页 割平面约束的几何意义 等价于约束条件x2 3 1 证明 用原问题的决策变量x1和x2表示割平面约束 将原问题的线性规划模型转化为标准型 第99页 第100页 将上式代入割平面约束 第101页 等价于约束条件x1 x2 7 2 证明 用原问题的决策变量x1和x2表示割平面约束 第102页 将上式代入割平面约束 x1 x2 7 第103页 例 第104页 解 1 利用单纯型法求解原问题的松弛问题B 人工变量 第105页 第106页 第107页 2 构造割平面约束 选择x1构造割平面约束 x1 13 7 1 6 7x2 9 7 1 2 7x4 31 7 4 3 7 第108页 3 求解 第109页 第110页 第111页 4 构造割平面约束 选择x5构造割平面约束 x2 5 4 1 1 4x3 5 2 2 1 2x5 7 4 1 3 4 第112页 第113页 第114页 由此可以看出 在求解整数规划的松弛问题时 如果有人工变量引入 在最终单纯形表中必然会出现人工变量 该人工变量在最终单纯形表中必然是非基变量 否则松弛问题无解 则整数规划也无解 但人工变量的出现不会对其后处理整数规划时 加入割平面约束造成任何影响 第115页 因为人工变量的出现不会对其后处理整数规划时 加入割平面约束造成任何影响 故也可采用在松弛问题的最终单纯形表中 将人工变量列删去 再加入割平面约束的方法 这样还简化了计算量 第116页 例 第117页 解 利用单纯型法求解原问题的松弛问题B 第118页 选择x1构造割平面约束 x1 5 3 1 2 3x2 8 3 2 2 3 第119页 第120页 选择x3构造割平面约束 x2 16 5 3 1 5x3 4 5 0 4 5 第121页 第122页 选择x2构造割平面约束 x1 5 3 1 2 3x2 8 3 2 2 3 第123页 第124页 由此可以看出 在松弛问题的最优解中 比较不符合整数条件的各基变量值xi bi Ni fi 当有多个基变量对应的fi均为最大值时 可任选一个基变量构造割平面 但选择不同的基变量在跌代次数上可能存在较大差别 第125页 课后习题5 7 2 第126页 解 1 利用单纯型法求解原问题的松弛问题B 第127页 第128页 第129页 2 因松弛问题B得最优解就是整数解 也即其整数规划的最优解 注 松弛问题如果利用对偶单纯形法求出的最优解不是整数解 则直接在其最终单纯形表基础上 加入割平面约束 求出整数解 第130页 第4节0 1型整数规划 若整数规划中变量只能取0或1 则称这样的整数规划为0 1整数规划 第131页 0 1整数线性规划数学模型的一般形式为 第132页 一 0 1整数规划的隐枚举法穷举法 检查变量取值为0或1的每一种组合 比较目标函数值 以求得最优解 如果问题的决策变量数为n个 则组合数为2n个 当n大时 这几乎是不可能的 隐枚举法 implicitEnumeration 只检查组合中的一部分 第133页 例1 第134页 解 将变量按照目标函数系数从小到大的顺序依次排列 第135页 为可行解 z 0 从而问题产生过滤条件 FilteringConstraint 第136页 改进过滤条件 FilteringConstraint 第137页 改进过滤条件 FilteringConstraint 第138页 变量的所有组合已经全部被检查 目标函数z不能进一步改进 从而得到问题的最优解 x2 x1 x3 0 1 1 第139页 总结 问题有3个变量 共有23 8个解 问题有4个约束条件 每个解需要运算4次 则利用穷举法需要运算8 4 32次 实际只运算了19次 第140页 例2 第141页 解 将变量按照目标函数系数从大到小的顺序依次排列 第142页 第143页 为可行解 z 4 从而问题产生过滤条件 FilteringConstraint 第144页 第145页 变量的所有组合已经全部被检查 目标函数z不能进一步改进 从而得到问题的最优解 x2 x4 x3 x1 0 1 0 0 第146页 总结 问题有4个变量 共有24 16个解 问题有3个约束条件 每个解需要运算3次 则利用穷举法需要运算16 3 48次 实际只运算了20次 第147页 总结 对于最大化问题 按目标函数系数从小到大排列 对于最小化问题 按目标函数从大到小排列 目的是使得最优解尽早出现 第148页 二 0 1整数规划的应用 1 投资场所的选定 相互排斥的计划 某公司拟在市区的东 西 南三区投资建立门市部 拟建的位置有7处 分别为Ai i 1 2 7 在Ai处投资额为bi元 每年获得利润为ci元 总投资不能超过B元 第149页 拟建门市部的具体要求如下 东区 A1 A2 A3中至多选两个 西区 A4 A5中至少选一个 南区 A6 A7中至少选一个 问 应选择哪几个点建设门市部可使得年利润为最大 第150页 解 引入0 1变量xi i 1 2 7 第151页 2 含有相互排斥的约束条件的问题 用集装箱托运甲 乙两种货物 可选择的运输方式 每箱体积 可获得利润 不同运输方式的体积限制如下表所示 问采取哪种运输方式 两种货物各托运多少箱 可使得利润最大 第152页 解 设运输货物甲x1箱 运输货物乙x2箱 选择卡车运输的体积限制 选择船舶运输的体积限制 第153页 卡车和船舶两种运输方式只能选择一种 故为了统一问题 需引入0 1变量y 第154页 选择卡车运输的体积限制 选择船舶运输的体积限制 第155页 建立问题的模型 第156页 推广 存在m个相互排斥的约束条件 为了保证这m个相互排斥的约束条件只有一个起作用 第157页 1 引入m个0 1变量yi i 1 2 m 2 引入一个充分大的常数M 第158页 m个yi中只能有一个取0 其余均取1 yi取0的约束条件起作用 yi取1的约束条件不起作用 为多余约束 第159页 某工厂生产某种产品 有m种生产方式可供选择 采取不同生产方式 所能生产的产品产量 成本 收入都不相同 设 3 关于固定费用的问题 第160页 采取第i种生产方式生产时的产量 xi i 1 2 m 采取第i种生产方式生产时的成本 ki i 1 2 m 采取第i种生产方式生产时每件产品的收入 ci i 1 2 m 问 如何安排生产 才能使生产创造的收益最大 第161页 解 设采取第i种生产方式进行生产的产品产量为 xi xi为整数采取第i种生产方式进行生产的成本为 ki采取第i种生产方式进行生产的产品收入为 cixi 第162页 采取第i种生产方式进行生产的产品总收益为 cixi ki当不采取第i种生产方式进行生产的产品总收益为 cixi 0 ki 0 第163页 为了统一上述两种情况 第i种生产方式的产品总收益应表示为 cixi kiyi 第164页 问题的数学模型可表示为 对上述数学模型进行修正 第165页 修正后的问题的数学模型可表示为 第166页 模型分析 xi 0时 yi 1约束才成立 xi 0时 yi 0约束才成立 第167页 指派问题的标准形式 有n个人和n件事情 已知第i人做第j件事情的费用为cij i j 1 2 n 要求确定人和事之间的 第五节指派问题 一 指派问题的标准形式 第168页 一一对应的指派方案 使完成这n件事情的总费用最少 这类问题称为指派问题或分派问题 assignmentproblem 第169页 引入n2个0 1变量 二 指派问题的数学模型及其特点 cij第表示第i人做第j件事情的费用 第170页 建立问题的数学模型 约束 1 每件事情必须有且只能有一个人去做 约束 2 每个人必须且只能去做一件事情 第171页 三 指派问题的特点 1 系数矩阵 一般称矩阵 为指派问题的系数矩阵 coefficientmatrix 第172页 第i行中各元素表示第i人做各事的费用 第j列各元素表示第j事由各人做的费用 2 解矩阵 对于问题的每一个可行解 可用解矩阵的形式表示 第173页 解矩阵的特点 每行各元素都有且只有一个1 每列各元素都有且只有一个1 指派问题共有 n 个可行解 第174页 标准指派问题是一类整数规划问题 又是一个特殊的0 1规划问题 同时又是一个特殊的运输问题 可用整数规划的分支定界法 割平面法 0 1规划的隐枚举法 运输问题解法来求解 但效率低下 没有充分利用指派问题自身的特点 第175页 四 标准指派问题的匈牙利法1955年 库恩 W W Kuhn 引用了匈牙利数学家康尼格 D K nig 的关于矩阵中0元素的定理 定理 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 提出了指派问题的一种算法 习惯上称之为匈牙利法 第176页 1 指派问题最优解的特性指派问题最优解的特性 从指派问题的系数矩阵C cij n n的某行 某列 中的各元素分别减去该行 该列 的最小元素 得到新的系数矩阵 那么以C和为系数矩阵的两个指派问题有相同的最优解 第177页 证明 由于系数矩阵的这种变化并不影响数学模型的约束方程组 而只是使目标函数值减少了常数k 所以最优解并不发生改变 第178页 2 匈牙利法的思路思路 利用指派问题最优解的特性 使原系数矩阵C cij n n变换成含有很多0元素的新系数矩阵 而最优解保持不变 第179页 如果能在新系数矩阵中找到n个位于不同行不同列的0元素 并令其对应的变量xij 1 其余变量取值为0 将这样的一组解X代入目标函数中可得z 0 它一定是使问题目标函数值最小的解 即指派问题的最优解 独立0元素 位于不同行不同列的0元素 第180页 3 匈牙利法的步骤第一步 变换系数矩阵C 使其各行各列中都出现0 1 对系数矩阵C的每行元素分别减去该行的最小元素 2 对系数矩阵C的每列元素分别减去该列的最小元素 第181页 例 每行减去最小元素 每列减去最小元素 第182页 第二步 确定独立0元素 1 选择只有一个0元素的行 给这个0元素加圈 记作0 然后划去0所在列的其他0元素 记作0 2 选择只有一个0元素的列 给这个0元素加圈 记作0 然后划去0所在行的其他0元素 记作0 第183页 3 反复进行 1 和 2 直到所有0元素都被圈出和划掉为止 4 在 1 和 2 过程中 如不存在只有一个0元素的行和列 从0元素最少的行 列 开始 选择0元素最少的那列 行 的这个0元素加圈 然后划掉同行同列的其他0元素 此时问题有多重最优解 第184页 5 若0元素数目等于系数矩阵的阶数 那么得出问题的最优解 否则转入步骤三 第185页 例 每行和每列中0元素数量都不只一个 说明问题有多个最优解 第186页 0元素数目为4 等于系数矩阵阶数4 故得出问题最优解 问题有多个最优解 第187页 第三步 确定覆盖所有0元素的最少直线 1 对没有0的行打 2 在已打 的行中 对0所在的列打 3 在已打 的列中 对0所在的行打 4 重复 2 和 3 直到再也找不到可以打 的行或列为止 5 对没有打 的行画一横线 对打 的列画一垂线 从而得到覆盖所有0元素的最少直线 第188页 例 解 第一步 第189页 第二步 0元素数目为4 不等