管理运筹学-2.ppt

第八章整数规划 1整数规划的图解法 2整数规划的计算机求解 3整数规划的应用 4整数规划的分枝定界法 1整数规划的图解法 例1 某工厂在计划期内要安排甲 乙两种仪器设备的生产 已知生产仪器设备需要A B两种材料的消耗以及资源的限制 如右表 问题 工厂应分别生产多少件甲 乙种仪器设备才能使工厂获利最多 解 目标函数 Maxz x1 x2约束条件 s t 3x1 2x2 102x2 5x1 x2 0为整数不考虑整数约束得到最优解 x1 1 667 x2 2 5 z 4 167 考虑整数约束得到最优解 x1 2 x2 2 z 4整数规划的最优目标值小于相应线性规划的最优目标值 相当于附加一个约束 2整数规划的计算机求解 例2 Maxz 15x1 10 x2 7x3s t 5x1 10 x2 7x3 86x1 4x2 8x3 12 3x1 2x2 2x3 10 x1 x2 x3 0为整数 例2 Maxz 15x1 10 x2 7x3s t 5x1 10 x2 7x3 86x1 4x2 8x3 12 3x1 2x2 2x3 10 x1 x2 x3 0 x3为整数x1为0 1变量 用 管理运筹学 软件求解得 x1 0 x2 3x3 0z 30 用 管理运筹学 软件求解得 x1 1x2 1 5x3 0z 30 3整数规划的应用 1 一 投资场所的选择例4 京成畜产品公司计划在市区的东 西 南 北四区建立销售门市部 拟议中有10个位置Aj j 1 2 3 10 可供选择 考虑到各地区居民的消费水平及居民居住密集度 规定 在东区由A1 A2 A3三个点至多选择两个 在西区由A4 A5两个点中至少选一个 在南区由A6 A7两个点中至少选一个 在北区由A8 A9 A10三个点中至少选两个 Aj各点的设备投资及每年可获利润由于地点不同都是不一样的 预测情况见右表所示 单位 万元 但投资总额不能超过720万元 问应选择哪几个销售点 可使年利润为最大 解 设 0 1变量xi 1 Ai点被选用 或0 Ai点没被选用 这样我们可建立如下的数学模型 Maxz 36x1 40 x2 50 x3 22x4 20 x5 30 x6 25x7 48x8 58x9 61x10s t 100 x1 120 x2 150 x3 80 x4 70 x5 90 x6 80 x7 140 x8 160 x9 180 x10 720 x1 x2 x3 2x4 x5 1x6 x7 1x8 x9 x10 2xj 0 xj为0 1变量 i 1 2 3 10 二 固定成本问题例5 高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如右表所示 不考虑固定费用 每种容器售出一只所得的利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人月 机器有100台月 此外不管每种容器制造的数量是多少 都要支付一笔固定的费用 小号是l00万元 中号为150万元 大号为200万元 现在要制定一个生产计划 使获得的利润为最大 解 这是一个整数规划的问题 设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 3整数规划的应用 2 例6 有四个工人 要分别指派他们完成四项不同的工作 每人做各项工作所消耗的时间如右表所示 问应如何指派工作 才能使总的消耗时间为最少 解 引入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 求解可用 管理运筹学 软件中整数规划方法 3整数规划的应用 3 三 指派问题有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 四 分布系统设计例7 某企业在A1地已有一个工厂 其产品的生产能力为30千箱 为了扩大生产 打算在A2 A3 A4 A5地中再选择几个地方建厂 已知在A2 A3 A4 A5地建厂的固定成本分别为175千元 300千元 375千元 500千元 另外 A1产量及A2 A3 A4 A5建成厂的产量 那时销地的销量以及产地到销地的单位运价 每千箱运费 如右表所示 a 问应该在哪几个地方建厂 在满足销量的前提下 使得其总的固定成本和总的运输费用之和最小 b 如果由于政策要求必须在A2 A3地建一个厂 应在哪几个地方建厂 解 a 设xij为从Ai运往Bj的运输量 单位千箱 yi 1 当Ai被选中时 或0 当Ai没被选中时 这可以表示为一个整数规划问题 Minz 175y2 300y3 375y4 500y5 8x11 4x12 3x13 5x21 2x22 3x23 4x31 3x32 4x33 9x41 7x42 5x43 10 x51 4x52 2x53其中前4项为固定投资额 后面的项为运输费用 s t x11 x12 x13 30 A1厂的产量限制 x21 x22 x23 10y2 A2厂的产量限制 b 增加约束 y2 y3 1x31 x32 x33 20y3 A3厂的产量限制 x41 x42 x43 30y4 A4厂的产量限制 x51 x52 x53 40y5 A5厂的产量限制 x11 x21 x31 x41 x51 30 B1销地的限制 x12 x22 x32 x42 x52 20 B2销地的限制 x13 x23 x33 x43 x53 20 B3销地的限制 xij 0yi为0 1变量 i 1 2 3 4 5 j 1 2 3 求解可用 管理运筹学 软件中整数规划方法 3整数规划的应用 4 3整数规划的应用 5 五 投资问题例8 某公司在今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 但要求第一年投资最低金额为4万元 第二 三 四年不限 项目B 第三年初需要投资 到第五年未能回收本利128 但规定最低投资金额为3万元 最高金额为5万元 项目C 第二年初需要投资 到第五年未能回收本利140 但规定其投资额或为2万元或为4万元或为6万元或为8万元 项目D 五年内每年初可购买公债 于当年末归还 并加利息6 此项投资金额不限 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第五年末拥有的资金本利总额为最大 解 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 2 3 4 5 设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 20000y2C Dx1Dx2Dx3Dx4Dx5D 3整数规划的应用 6 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 3 目标函数及模型 Maxz 1 15x4A 1 40 x2C 1 28x3B 1 06x5Ds t x1A x1D 100000 x2A x2C x2D 1 06x1D x3A x3B x3D 1 15x1A 1 06x2D x4A x4D 1 15x2A 1 06x3D x5D 1 15x3A 1 06x4D x1A 40000y1A x1A 200000y1A x3B 30000y3B x3B 50000y3B x2C 20000y2C yiA yiB 0或1 i 1 2 3 4 5y2C 0 1 2 3 4xiA xiB xiC xiD 0 i 1 2 3 4 5 4整数规划的分枝定界法 1 问题 A Minz c1x1 c2x2 cnxn记问题 B 为去掉整数约束的问题 A s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0为整数在分枝定界法过程中求解问题 B 应有以下情况之一 B 无可行解 则 A 亦无可行解 停止对此问题的计算 B 有最优解 并满足整数约束 即同时为 A 的最优解 那么z 同时是当前问题 A 最优目标值的上界和下界 停止对这个问题的计算 B 有最优解x及最优值z但不符合整数条件 这时得到当前问题 A 最优目标值的一个下界z z 于是通过以下判断可对此问题进一步计算 分枝定界法的计算过程 1 对原问题 A 求解松弛问题 B 根据上面分析 若出现情况 则停机 若情况 发生 得到 A 问题最优值的一个下界 我们任找 A 问题的一个可行解 那么对应的目标函数值是 A 最优值的一个上界z 即得到z z z 注 找 A 问题的可行解往往需要较大的计算量 这时可简单记z 而先不必费很大力量去求较好的上界 从以下分析可以看到 找到一个好的最优目标值上界 将对算法的快速求得目标非常有效 转2 进行以下一般步的迭代 4整数规划的分枝定界法 2 2 对当前问题进行分枝和定界 分技 无妨设当前问题为 A 其松弛问题 B 的最优解不符合整数约束 任取非整数的分量xr 构造两个附加约束 xr xr 和xr xr 1 对 A 分别加入这两个约束 可得到两个子问题 A1 和 A2 显然这两个子问题的可行解集的并是 A 的可行解集 定界 根据前面分析 对每个当前问题 A 可以通过求解松弛问题 B 以及找 A 的可行解得到当前问题的上 下界z 和z 对一般迭代步 设根据分枝定界方法得到了原问题 A 的一个同层子问题 AI i 1 2 n之和的分解 这里的同层子问题是指每个子问题 AI 都是 A 经过相同分枝次数得到的 3 比较与剪枝 对当前子问题进行考察 若不需再进行计算 则称之为剪枝 一般遇到下列情况就需剪枝 B 无可行解 B 的最优解符合整数约束 B 的最优值z z 通过比较 若子问题不剪枝则返回2 分枝定界法当所有子问题都剪枝了 即没有需要处理的子问题时 达到当前上界z 的可行解即原问题的最优解 算法结束 4整数规划的分枝定界法 3 分枝定界法是求整数规划的一种常用的有效的方法 既能解决纯整数规划的问题 也能解决混合整数规划的问题 例 Minf 5x1 4x2s t 3x1 4x2 249x1 5x2 45x1 x2 0整数 4整数规划的分枝定界法 4 隐枚举法是求解0 1规划最常用的方法之一对于n个决策变量的完全0 1规划 其可行点最多有2n个 当n较大时其计算量大得惊人 隐枚举法的基本思想是根据0 1规划的特点 进行分技逐步求解 1 用于隐枚举法的0 1规划标准形式 为了计算的方便 需要把一般的0 1规划问题等价地化成下列标准形式Minf c1x1 c2x2 cnxncj 0j 1 2 ns t ai1x1 ai2x2 ainxn bii 1 2 mx1 x2 xn 0或1下面说明一个完全的0 1规划问题可以化为等价的标准形式 1 若目标函数求最大 Maxz 可令f z 变为求最小Minf 2 若目标函数的系数有负值时 如cj 0 那么 可以令相应的yj 1 xj 3 当某个约束不等式是 时 只需两端同乘以 1 即变为 4 当某个约束是等式约束时 可得到两个方向相反的不等式 4整数规划的分枝定界法 5 隐枚举法的基本过程 1 将0 1规划问题化为标准形式 设其最优解为x 最优目标值为f 显然x 0时 目标值f 0是不考虑线性不等式约束的最小解 于是f 0 若x 0是可行解 那末f 0是该问题的最优解 结束计算 否则 置所有分量为自由变量 转2 2 任选一自由变量xk 令xk为固定变量 分别固定为xk 0与xk 1 令所有自由变量取零值 则得到两个分枝 对每个分枝的试探解进行检验 把自由变量逐次定为固定变量的顺序可以是任意的 在不进行先验考察时 常按指标变量从小到大的顺序进行 转3 3 检验当前试探解时 遇到下列4种情况就剪枝 即不必再向下分枝 在剪枝的子问题下方标记 情况一 若子问题的试探解可行 即满足所有线性不等式约束 则此问题的目标值是原问题最优目标值的一个上界记为f 即f f 把f 的值记在子问题框的旁边 并在下方标记上 4整数规划的分枝定界法 6 情况二 若试探解不可行 且存在一个线性不等式约束 将所有固定变量值代入后 所得到的不等式中所有负系数之和大于右端项或若无负系数时 最小的系数大于右端项 那么此问题的任何分枝都是不可行的问题 于是在此问题框的下方标记 情况三 若试探解不可行 且它的目标值与目标函数中对应当前自由变量的任一个系数之和大于所有已得到的上界中最小者时 说明在当前问题的基础上 固定任何自由变量都不可能对目标函数有改善 于是在该问题框的下方标记 情况四 若试探解不可行 但所有变量已被置为固定变量 也应剪枝 于是在该问题框的下方标记 把已标记 的子问题 称为已探明的枝 转4 4 进一步考察 如果所有的枝均为已探明的枝 则停机结束计算 找出所有子问题框边标记f 值的问题 比较得到其中最小者 其对应的试探解即原问题的最优解 相应值即原问题的最优目标值f 若没有标记f 值的框 则说明原问题无最优解 实际上原问题无可行解 如果仍存在尚未探明的分枝 则可任选一个未探明的分枝 转2 4整数规划的分枝定界法 7 0 1规划的隐枚举法例 Maxz 100 x1 30 x2 40 x3 45x4s