规划数学ch2-5.pdf

P1 要求一部分或全部决策变量取整数值的规划问题称为整数 规划 不考虑整数条件 由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题 若该松弛 问题是一个线性规划 则称该整数规划为整数线性规划 要求一部分或全部决策变量取整数值的规划问题称为整数 规划 不考虑整数条件 由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题 若该松弛 问题是一个线性规划 则称该整数规划为整数线性规划 1 整数线性规划数学模型的一般形式 整数线性规划数学模型的一般形式 且部分或全部为整数 或 且部分或全部为整数 或 n 1 2 j 0 2 1 min max 1 1 j n j ijij n j jj x mibxa xcZZ 第五节 整数规划 简称 IP 第五节 整数规划 简称 IP 一 整数规划问题一 整数规划问题 P2 2 2 整数线性规划问题的种类 整数线性规划问题的种类 整数线性规划问题的种类 整数线性规划问题的种类 纯整数线性规划 指全部决策变量都必须取整数 值的整数线性规划 纯整数线性规划 指全部决策变量都必须取整数 值的整数线性规划 混合整数线性规划 决策变量中有一部分必须取 整数值 另一部分可以不取整数值的整数线性规划 混合整数线性规划 决策变量中有一部分必须取 整数值 另一部分可以不取整数值的整数线性规划 0 1型整数线性规划 决策变量只能取值0或1的 整数线性规划 0 1型整数线性规划 决策变量只能取值0或1的 整数线性规划 3 3 整数规划的典型例子整数规划的典型例子整数规划的典型例子整数规划的典型例子 例例1 工厂工厂A1和和A2生产某种物资 由于该种物资供不应求 故需要再 建一家工厂 相应的建厂方案有 生产某种物资 由于该种物资供不应求 故需要再 建一家工厂 相应的建厂方案有A3和和A4两个 这种物资的需求地有两个 这种物资的需求地有 B1 B2 B3 B4四个 各工厂年生产能力 各地年需求量 各厂至各需 求地的单位物资运费 四个 各工厂年生产能力 各地年需求量 各厂至各需 求地的单位物资运费cij 见下表 见下表 150300400350 年需求 量 2005254A4 2002167A3 6007538A2 4004392A1 年生产能力B4B3B2B1 工厂工厂A3或或A4开工后 每年的生产费用估计分别为开工后 每年的生产费用估计分别为1200万或万或1500万 元 现要决定应该建设工厂 万 元 现要决定应该建设工厂A3还是还是A4 才能使今后每年的总费用 最少 才能使今后每年的总费用 最少 P4 解 这是一个物资运输问题 特点是事先不能 确定应该建 解 这是一个物资运输问题 特点是事先不能 确定应该建A3还是还是A4中哪一个 因而不知道 新厂投产后的实际生产物资 为此 引入 中哪一个 因而不知道 新厂投产后的实际生产物资 为此 引入0 1 变量 变量 2 1 0 1 iyi 若不建工厂 若建工厂 若不建工厂 若建工厂 再设x再设xij ij为由A 为由Ai i运往B运往Bj j的物资数量 单位为千吨 z表示总费用 单位万元 则该规划问题的数学模型可以表示为 的物资数量 单位为千吨 z表示总费用 单位万元 则该规划问题的数学模型可以表示为 P5 2 1 1 0 4 3 2 1 0 200 200 600 400 150 300 400 350 15001200 min 244434241 134333231 24232221 14131211 44342414 43332313 42322212 41312111 4 1 4 1 21 iy jix yxxxx yxxxx xxxx xxxx xxxx xxxx xxxx xxxx ts yyxcz i ij ij ijij 混合整数规划问题混合整数规划问题 数学模型数学模型 P6 例例2 现有资金总额为现有资金总额为B 可供选择的投资项目有 可供选择的投资项目有n个 项目 个 项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj j 1 2 n 此外由于种种原因 有三个附加条件 此外由于种种原因 有三个附加条件 1 若选择项目若选择项目1 就必须同时选择项目 就必须同时选择项目2 反之 不一定 反之 不一定 2 项目项目3和和4中至少选择一个 中至少选择一个 3 项目项目5 6 7中恰好选择中恰好选择2个 应该怎样选择投资项目 才能使总预期收益最大 个 应该怎样选择投资项目 才能使总预期收益最大 P7 解 对每个投资项目都有被选择和不被选择 两种可能 因此分别用 解 对每个投资项目都有被选择和不被选择 两种可能 因此分别用0和和1表示 令表示 令xj表示第表示第 j个项目的决策选择 记为 个项目的决策选择 记为 2 1 0 1 nj j j xj 不投资对项目 投资对项目 不投资对项目 投资对项目 投资问题可以表示为 投资问题可以表示为 或者 或者nx xxx xx xx Bxa ts xcz j n j jj n j jj 2 1j10 2 1 max 765 43 12 1 1 P8 例3例3 指派问题或分配问题 人事部门欲安排四 人到四个不同岗位工作 每个岗位一个人 经 考核四人在不同岗位的成绩 百分制 如表所 示 如何安排他们的工作使总成绩最好 88809086丁 90798382丙 95788795乙 90739285甲 DCBA 工 作人员 P9 设设 工作时人做不分配第 工作时人做分配第 工作时人做不分配第 工作时人做分配第 ji ji xij 0 1 数学模型如下 数学模型如下 44434241 343332312423 222114131211 88809086 907983829578 879590739285max xxxx xxxxxx xxxxxxZ 要求每人做一项工作 约束条件为 要求每人做一项工作 约束条件为 1 1 1 1 44434241 34333231 24232221 14131211 xxxx xxxx xxxx xxxx P10 每项工作只能安排一人 约束条件为 每项工作只能安排一人 约束条件为 1 1 1 1 44342414 43332313 42322212 41312111 xxxx xxxx xxxx xxxx 变量约束 变量约束 4 3 2 110 jixij 或 或 P11 4 4 整数规划问题解的特征 整数规划问题解的特征 整数规划问题解的特征 整数规划问题解的特征 整数规划问题的可行解集合是它松弛问题可行解 集合的一个子集 任意两个可行解的凸组合不一定 满足整数约束条件 因而不一定仍为可行解 整数规划问题的可行解一定是它的松弛问题的可 行解 反之不一定 但其最优解的目标函数值不 会优于后者最优解的目标函数值 整数规划问题的可行解集合是它松弛问题可行解 集合的一个子集 任意两个可行解的凸组合不一定 满足整数约束条件 因而不一定仍为可行解 整数规划问题的可行解一定是它的松弛问题的可 行解 反之不一定 但其最优解的目标函数值不 会优于后者最优解的目标函数值 P12 例例4 设整数规划问题如下 且为整数 且为整数0 136 51914 max 21 21 21 21 xx xx xx xxZ 首先不考虑整数约束 得到线性规划问题 一般称为松弛问题 首先不考虑整数约束 得到线性规划问题 一般称为松弛问题 0 136 51914 max 21 21 21 21 xx xx xx xxZ P13 用图解法求出最优解为 x1 3 2 x2 10 3 且 有Z 29 6 现求整数解现求整数解 最优解最优解 如用舍入取 整法可得到 如用舍入取 整法可得到4个点即个点即 1 3 2 3 1 4 2 4 显然 它们都 不可能是整数规划的最优解 显然 它们都 不可能是整数规划的最优解 x1 x2 3 3 3 2 10 3 按整数规划约束条件 其可行解 肯定在线性规划问题的可行域内 且为整数点 故整数规划问题的 可行解集是一个有限集 如右图 所示 其中 按整数规划约束条件 其可行解 肯定在线性规划问题的可行域内 且为整数点 故整数规划问题的 可行解集是一个有限集 如右图 所示 其中 2 2 3 1 点的目标函 数值最大 即为 点的目标函 数值最大 即为Z 4 P14 整数规划问题的求解方法 分枝定界法和割平面法 匈牙利法 指派问题 分枝定界法和割平面法 匈牙利法 指派问题 P15 二 分枝定界法二 分枝定界法 1 求整数规划的松弛问题最优解 若松弛问题的最优解满足整数要求 得到整数规划的最优解 求整数规划的松弛问题最优解 若松弛问题的最优解满足整数要求 得到整数规划的最优解 否则转下一 步 否则转下一 步 2 分枝与定界 分枝与定界 任意选一个非整数解的变量任意选一个非整数解的变量xi 在松弛问题中加上约束 在松弛问题中加上约束 xi xi 和和xi xi 1 组成两个新的松弛问题 称为分枝 新的松弛问题具有特征 当原问题 是求最大值时 目标值是分枝问题的上界 当原问题是求最小值时 目 标值是分枝问题的下界 组成两个新的松弛问题 称为分枝 新的松弛问题具有特征 当原问题 是求最大值时 目标值是分枝问题的上界 当原问题是求最小值时 目 标值是分枝问题的下界 检查所有分枝的解及目标函数值 若某分枝的解是整数并且目标函数 值大于 检查所有分枝的解及目标函数值 若某分枝的解是整数并且目标函数 值大于 max 等于其它分枝的目标值 则将其它分枝剪去不再计算 若还存在非整数解并且目标值大于 等于其它分枝的目标值 则将其它分枝剪去不再计算 若还存在非整数解并且目标值大于 max 整数解的目标值 需要继续分枝 再检查 直到得到最优解 整数解的目标值 需要继续分枝 再检查 直到得到最优解 分枝定界法的解题步骤 分枝定界法的解题步骤 分枝定界法的解题步骤 分枝定界法的解题步骤 P16 例例1 用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题 12 12 12 1 12 max5 2 56 30 4 0 fxx xx xx x xx 且全为整数 解 首先去掉整数约束 变成一般线性规划问题解 首先去掉整数约束 变成一般线性规划问题 原整数规划问题 的松驰问题 原整数规划问题 的松驰问题 12 12 12 1 12 max5 2 56 30 4 0 fxx xx xx x xx LP IP P17 用图解法求松弛问题的最优解 如图所示 x1 x2 3 18 11 40 11 2 1 123 x1 18 11 x2 40 11 f 218 11 19 8 即即Z 也是也是IP最小值的下限 对于 最小值的下限 对于x1 18 11 1 64 取值 取值x1 1 x1 2 对于对于x2 40 11 3 64 取值 取值 x2 3 x2 4 先将 先将 LP 划分为 划分为 LP1 和 和 LP2 取取x1 1 x1 2 P18 分枝 分枝 12 12 12 1 1 12 max5 2 56 30 1 4 1 0 fxx xx xx IPx x xx 且为整数 12 12 12 1 1 12 max5 2 56 30 2 4 2 0 fxx xx xx IPx x xx 且为整数 分别求出 分别求出 LP1 和 和 LP2 的最优解 的最优解 P19 先求LP1 如图所示 此 时在B点取得最优解 x1 1 x2 3 f 1 16 找到整数解 问题已探 明 此枝停止计算 x1 x2 3 3 18 11 40 11 1 1 B A C 同理求同理求LP2 如图所示 在如图所示 在C 点 取得最优解 即 点 取得最优解 即 x1 2 x2 10 3 f 2 56 3 18 7 f 2 f 1 16 原问题有比 原问题有比16更大的最优 解 但 更大的最优 解 但x2 不是整数 故继续 分枝 不是整数 故继续 分枝 P20 在IP2中分别再加入条件 x2 3 x2 4 得 下式两支 12 12 12 1 1 2 12 max5 2 56 30 4 21 2 3 0 fxx xx xx x IP x x xx 且为整数 12 12 12 1 1 2 12 max5 2 56 30 4 22 2 4 0 fxx xx xx x IP x x xx 且为整数 分别求出分别求出LP21和和LP22的最优解的最优解 P21 分枝定界法分枝定界法 x1 x2 3 3 18 11 40 11 1 1 B A CD 先求先求LP21 如图所示 此时如图所示 此时D 在点取得最优解 即 在点取得最优解 即x1 12 5 2 4 x2 3 f 21 87 5 17 4 f 1 16 但但x1 12 5不是整数 可继续 分枝 即 不是整数 可继续 分枝 即3 x1 2 求 求LP22 如图所示 无可行 解 故不再分枝 如图所示 无可行 解 故不再分枝 P22 在 LP21 的基础上继续分枝 加入条件 3 x1 2有下式 12 12 12 1 1 2 1 12 max5 2 56 30 4 211 2 3 2 0 fxx xx xx x IPx x x xx 且为整数 12 12 12 1 1 2 1 12 max5 2 56 30 4 212 2 3 3 0 fxx xx xx x IPx x x xx 且为整数 分别求出 分别求出 LP211 和 和 LP212 的最优解 的最优解 P23 x1 x2 3 3 18 11 40 11 1 1 B A C D E F 先求 先求 LP211 如图所示 此时 在 如图所示 此时 在E点取得最优解 即点取得最优解 即 x1 2 x2 3 f 211 17 找到整数解 问题已探明 此枝 停止计算 求 找到整数解 问题已探明 此枝 停止计算 求 LP212 如图所示 此时 如图所示 此时 F在点取得最优解 即在点取得最优解 即x1 3 x2 2 5 f 212 31 2 15 5 由于 选择进行分枝 增加约束 及 得线性规划及 6 12 12 12 12 12 max43 1 20 810 22 525 212 56 0 fxx xx xx LP xx x x LP211 X 4 6 f211 34 LP212 X 5 5 f212 35 5 LP212 P30 上述分枝过程可用下图表示 上述分枝过程可用下图表示 LP0 X 3 57 7 14 f0 35 7 LP1 X 3 7 6 f1 34 8 LP2 X 4 6 5 f2 35 5 x1 3 x1 4 LP21 X 4 33 6 f21 35 33 x2 6 LP211 X 4 6 f211 34 LP212 X 5 5 f212 35 x1 4 x1 5 LP22 无可行解无可行解 x2 7 P31 以下只讨论纯整数线性规划的情形 下面举例说明 割平面法是1958年美国学者R E Gomory提出的 所以又称为Gomory的割平面法 以下只讨论纯整数线性规划的情形 下面举例说明 割平面法是1958年美国学者R E Gomory提出的 所以又称为Gomory的割平面法 基本思想 基本思想 基本思想 基本思想 先不考虑变量的取整数约束 求解相应的线性规划 然后不断增加线性约束条件 即割平面 将原可行域割掉不含整数可行解的一部分 最终得到一个具有 先不考虑变量的取整数约束 求解相应的线性规划 然后不断增加线性约束条件 即割平面 将原可行域割掉不含整数可行解的一部分 最终得到一个具有整数坐标顶点整数坐标顶点的可行域 而该顶点恰好是原整数规划问题的最优解 的可行域 而该顶点恰好是原整数规划问题的最优解 三 割平面法三 割平面法 P32 割平面求解举例割平面求解举例 Max f x1 x2 x1 x2 1 3x1 x2 4 x1 x2 0 x1 x2为整数 为整数 松弛问题松弛问题 Max f x1 x2 x1 x2 1 3x1 x2 4 x1 x2 0 x1 x2 x3 1 3x1 x2 x4 4 x1 x2 0 例 例 例 例 P33 如不考虑条件 容易求得相应的线性规划的 最优解 如不考虑条件 容易求得相应的线性规划的 最优解 x1 3 4 x2 7 4 max f 10 4 它就是图中区域它就是图中区域R 的顶点的顶点A 但不合 于整数条件 但不合 于整数条件 P34 现设想 如能找到像现设想 如能找到像CD那样的直线去切割域那样的直线去切割域R 如图如图 去掉三角形域 去掉三角形域ACD 那么具有整数坐标的 那么具有整数坐标的C点点 1 1 就是 域 就是 域R 的一个极点 的一个极点 如在域如在域R 上求解 而得到的最优解又恰巧在 上求解 而得到的最优解又恰巧在C点点 就得到原问题的整数解 就得到原问题的整数解 所以解法的所以解法的关键关键 就是怎样构造一个这样的就是怎样构造一个这样的 割平面割平面 CD 它就是一个新的约束 尽管它可能不是唯一的 也可能不是一步能求到的 它就是一个新的约束 尽管它可能不是唯一的 也可能不是一步能求到的 下面给出本例完整的求解过程 下面给出本例完整的求解过程 P35 用单纯形表解松弛问题 见下表用单纯形表解松弛问题 见下表2 5 1 Max f x1 x2 x1 x2 1 3x1 x2 4 x1 x2 0 x1 x2 x3 1 3x1 x2 x4 4 x1 x2 0 P36 解松弛问题的最优单纯形表为 解松弛问题的最优单纯形表为 2 5 1 CBXBb 1100 x1x2x3x4 0 x31 1110 0 x443101 1100 1x13 410 1 41 4 1x27 4013 41 4 f 5 2 001 21 2 P37 从表2 5 1的最终计算表中 得到非整数的最优解 x1 3 4 x2 7 4 x3 x4 0 max f 5 2 从表2 5 1的最终计算表中 得到非整数的最优解 x1 3 4 x2 7 4 x3 x4 0 max f 5 2 4 7 x 4 1 x 4 3 x 4 3 x 4 1 x 4 1 x 432 431 可从最终计算表中得到非整数基变量对应的可从最终计算表中得到非整数基变量对应的可从最终计算表中得到非整数基变量对应的可从最终计算表中得到非整数基变量对应的 关系式 关系式 关系式 关系式 v不能满足整数最优解的要求 不能满足整数最优解的要求 v为此考虑将带有分数的最优解的可行域中分数 部分割去 再求最优解 就可以得到整数的最 优解 为此考虑将带有分数的最优解的可行域中分数 部分割去 再求最优解 就可以得到整数的最 优解 P38 为了得到整数最优解 将上式变量的系数和常数项都分解 成 为了得到整数最优解 将上式变量的系数和常数项都分解 成整数和非负真分数整数和非负真分数两部分之和两部分之和 1 0 x 1 0 x1 1 1 3 4 x 1 3 4 x3 3 1 4x 1 4x4 4 0 3 4 0 3 4 x x2 2 3 4 x 3 4 x3 3 1 4 x 1 4 x4 4 1 3 4 1 3 4 然后将整数部分与分数部分分开 移到等式左右两边 得 到 然后将整数部分与分数部分分开 移到等式左右两边 得 到 432 4331 x 4 1 x 4 3 4 3 1x x 4 1 x 4 3 4 3 xx P39 现考虑整数条件 要求现考虑整数条件 要求x1 x2x1 x2都是非负整数都是非负整数 于是由条件 可知 于是由条件 可知 x3 x4x3 x4也都是非负整 数 这一点对以下推导是 也都是非负整 数 这一点对以下推导是必要必要的 如不都是整数 则应在引入x3 x4之前乘以适当 的 如不都是整数 则应在引入x3 x4之前乘以适当调整系数和常数 使之都是整数 调整系数和常数 使之都是整数 P40 在上式在上式中 其实只考虑一式即可 从等式左边看是整数 等式右边也应是整数 中 其实只考虑一式即可 从等式左边看是整数 等式右边也应是整数 但在等式右边的 但在等式右边的 内是正数 所以等式右边必 内是正数 所以等式右边必是非正整数是非正整数 就是说 右边的整数值最大是零就是说 右边的整数值最大是零 于是整数 于是整数条件 可由下式所代替 条件 可由下式所代替 0 x 4 1 x 4 3 4 3 43 432 4331 x 4 1 x 4 3 4 3 1x x 4 1 x 4 3 4 3 xx P41 即 3x3 x4 3 这就得到一个 即 3x3 x4 3 这就得到一个切割方程 或称为切割约束 切割方程 或称为切割约束 将它作为增加约束条件 再解例3 将它作为增加约束条件 再解例3 引入松弛变量x5 得到等式引入松弛变量x5 得到等式 3x3 x4 x5 3 3x3 x4 x5 3 将这新的约束方程加到表2 5 1的最终计算表 得表2 5 2 将这新的约束方程加到表2 5 1的最终计算表 得表2 5 2 0 x 4 1 x 4 3 4 3 43 表表2 5 2 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 1 0 x1 x2 x5 3 4 7 4 3 1 0 0 0 1 0 1 4 3 4 3 1 4 1 4 1 0 0 1 zj cj 5 2 0 0 1 2 1 2 0 从表2 5 2的b列中可看到 这时得到的是非可行解 于是需要用对偶单纯形法继续进行计算 选择x5为换出变量 计算 从表2 5 2的b列中可看到 这时得到的是非可行解 于是需要用对偶单纯形法继续进行计算 选择x5为换出变量 计算 6 1 1 2 1 3 2 1 min0a a zc min lj lj jj j P43 将x3做为换入变量 再按原单纯形法进行迭代 得 下表 将x3做为换入变量 再按原单纯形法进行迭代 得 下表 c cj j 1 1 0 0 0 1 1 0 0 0 C CB B X XB B b x b x1 1 x x2 2 x x3 3 x x4 4 x x5 5 1 1 0 x1 1 0 x1 1 x x2 2 x x3 3 1 1 1 1 0 0 0 1 0 0 0 1 1 3 0 1 3 1 12 1 4 1 3 1 1 1 1 0 0 0 1 0 0 0 1 1 3 0 1 3 1 12 1 4 1 3 z zj j c cj j 2 0 0 0 1 3 1 6 2 0 0 0 1 3 1 6 x1 x2的值已都是整数 解题已完成 x1 x2的值已都是整数 解题已完成 P44 几何解释 几何解释 新得到的约束条件 3x新得到的约束条件 3x3 3 x x4 4 3 3 如用x如用x1 1 x x2 2表示 由 式得表示 由 式得 3 1 x3 1 x1 1 x x2 2 4 3x 4 3x1 1 x x2 2 3 3 x x2 2 1 1 则是 x则是 x1 1 x x2 2 平面 平面内形成新的可行域 即包括平行于x 内形成新的可行域 即包括平行于x1 1轴的直线x轴的直线x2 2 1 和这直线下的可行区域 整数点也在其中 没有切割掉 直观地表示在图5 7中 1 和这直线下的可行区域 整数点也在其中 没有切割掉 直观地表示在图5 7中 但从解题过程来看 这一步但从解题过程来看 这一步是不必要的 是不必要的 P45 割平面法的计算步骤 1 割平面法的计算步骤 1 用单纯形法求解 用单纯形法求解 IPIP 对应的松弛问题 对应的松弛问题 LPLP 若 若 LPLP 没有可行解 则 没有可行解 则 IPIP 也没有可行解 停止计算 也没有可行解 停止计算 若 若 LPLP 有最优解 并符合 有最优解 并符合 IPIP 的整数条件 则 的整数条件 则 LPLP 的最优解即为 的最优解即为 IPIP 的最优解 停止计算 的最优解 停止计算 若 若 LPLP 有最优解 但不符合 有最优解 但不符合 IPIP 的整数条件 转