第六章-整数规划模型

1 运筹学 大连海事大学刘巍 2 第六章整数规划模型 什么是整数规划 整数规划与线性规划有什么关系 从集装箱托运谈起 3 第1节整数规划问题 例1 某公司拟用集装箱托运甲 乙两种货物 这两种货物每件的体积 重量 可获利润以及托运所受限制如表所示 甲种货物至多托运4件 问两种货物各托运多少件 可使获得利润最大 解 设x1 x2分别为甲 乙两种货物托运的件数 建立模型目标函数 Maxz 2x1 3x2约束条件 s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0为整数 如果去掉最后一个约束 就是一个线性规划问题 4 整数规划问题 求整数解的线性规划问题 不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的 而要用整数规划的方法加以解决 在整数规划中 如果所有的变量都为非负整数 则称为纯整数规划问题 如果有一部分变量为负整数 则称之为混合整数规划问题 在整数规划中 如果变量的取值只限于0和1 这样的变量我们称之为0 1变量 在纯整数规划和混合整数规划问题中 如果所有的变量都为0 1变量 则称之为0 1规划 5 得到线性规划的最优解为x1 2 44 x2 3 26 目标函数值为14 66 由图表可看出 整数规划的最优解为x1 4 x2 2 目标函数值为14 性质1 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值 1整数规划的图解法 整数规划的图解法 6 例2 Maxz 3x1 x2 3x3s t x1 2x2 x3 44x2 3x3 2x1 3x2 2x3 3x1 x2 x3 0为整数 例3 Maxz 3x1 x2 3x3s t x1 2x2 x3 44x2 3x3 2x1 3x2 2x3 3x3 1x1 x2 x3 0 x1 x3为整数x3为0 1变量 用 管理运筹学 软件求解得 x1 5x2 2x3 2 用 管理运筹学 软件求解得 x1 4x2 1 25x3 1z 16 25 整数规划的例 7 第2节整数规划的应用 一 投资场所的选择例4 京成畜产品公司计划在市区的东 西 南 北四区建立销售门市部 拟议中有10个位置Aj j 1 2 3 10 可供选择 考虑到各地区居民的消费水平及居民居住密集度 规定 在东区由A1 A2 A3三个点至多选择两个 在西区由A4 A5两个点中至少选一个 在南区由A6 A7两个点中至少选一个 在北区由A8 A9 A10三个点中至少选两个 Aj各点的设备投资及每年可获利润由于地点不同都是不一样的 预测情况见表所示 单位 万元 但投资总额不能超过720万元 问应选择哪几个销售点 可使年利润为最大 8 整数规划的应用 解 设 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 9 整数规划的应用 二 固定成本问题例5 高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如表所示 不考虑固定费用 每种容器售出一只所得的利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人 月 机器有100台 月 此外不管每种容器制造的数量是多少 都要支付一笔固定的费用 小号是l00万元 中号为150万元 大号为200万元 现在要制定一个生产计划 使获得的利润为最大 10 整数规划的应用 解 这是一个整数规划的问题 设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 11 整数规划的应用 三 指派问题有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 例6 有四个工人 要分别指派他们完成四项不同的工作 每人做各项工作所消耗的时间如下表所示 问应如何指派工作 才能使总的消耗时间为最少 12 整数规划的应用 解 引入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 求解可用 管理运筹学 软件中整数规划方法 13 整数规划的应用 四 分布系统设计例7 某企业在A1地已有一个工厂 其产品的生产能力为30千箱 为了扩大生产 打算在A2 A3 A4 A5地中再选择几个地方建厂 已知在A2 A3 A4 A5地建厂的固定成本分别为175千元 300千元 375千元 500千元 另外 A1产量及A2 A3 A4 A5建成厂的产量 那时销地的销量以及产地到销地的单位运价 每千箱运费 如下表所示 a 问应该在哪几个地方建厂 在满足销量的前提下 使得其总的固定成本和总的运输费用之和最小 b 如果由于政策要求必须在A2 A3地建一个厂 应在哪几个地方建厂 14 整数规划的应用 解 a 设xij为从Ai运往Bj的运输量 单位千箱 yk 1 当Ak被选中时 或0 当Ak没被选中时 k 2 3 4 5 这可以表示为一个整数规划问题 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厂的产量限制 x31 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 0 i 1 2 3 4 5 j 1 2 3 yk为0 1变量 k 2 3 4 5 求解可用 管理运筹学 软件中整数规划方法 15 整数规划的应用 五 投资问题例8 某公司在今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 但要求第一年投资最低金额为4万元 第二 三 四年不限 项目B 第三年初需要投资 到第五年末能回收本利128 但规定最低投资金额为3万元 最高金额为5万元 项目C 第二年初需要投资 到第五年末能回收本利140 但规定其投资额或为2万元或为4万元或为6万元或为8万元 项目D 五年内每年初可购买公债 于当年末归还 并加利息6 此项投资金额不限 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第五年末拥有的资金本利总额为最大 16 整数规划的应用 解 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 20000y2CDx1Dx2Dx3Dx4Dx5D 17 整数规划的应用 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 18 整数规划的应用 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 19 第3节整数规划的分枝定界法 分枝定界法是求解整数规划的一种常用的有效的方法 它既能解决纯整数规划的问题 又能解决混合整数规划的问题 大多数求解整数规划的商用软件就是基于分枝定界法而编制成的 分枝定界法是先求解整数规划的线性规划问题 如果其最优解不符合整数条件 则求出整数规划的上下界 用增加约束条件的办法 把相应的线性规划的可行域分成子区域 称为分枝 再求解这些子区域上的线性规划问题 不断缩小整数规划的上下界的距离 最后得整数规划的最优解 下面以例9予以说明 20 整数规划的分枝定界法 例9用分枝定界法求解整数规划Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0且x1 x2为整数解 一 先求出以下线性规划的解 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0得z1 14 66 x1 2 44 x2 3 26 二 确定整数规划的最优目标函数值z 初始上界和下界z 分析后 知道 14 66 由观察法得下界z 13 当x1 2 x2 3时 21 3整数规划的分枝定界法 三 将一个线性规划问题分为两枝 并求解 可由x1 2或x1 3中取值 将线性规划1分解为两支 如下 线性规划2 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x2 2x1 x2 0解得z2 13 90 x1 2 x2 3 30线性规划3 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 3x1 x2 0解得z3 14 58 x1 3 x2 2 86 22 3整数规划的分枝定界法 四 修改整数规划的最优目标函数的上下界 经分析 将上界 14 66修改为 14 58 z 13 五 在线性规划2和线性规划3中选择一个上界最大的线性规划 即线性规划3 进行分枝 线性规划3分解为线性规划4和线性规划5 如下 线性规划4 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 3x2 2x1 x2 0解得z4 14 x1 4 x2 2线性规划5 Max2x1 3x2s t 195x1 273x2 13654x1 40 x2 140 x1 3x2 3x1 x2 0无可行解 23 3整数规划的分枝定界法 六 进一步修改整数规划最优目标函数值z 的上下界 从线性规划2 4 5中修改上下界 分析后 可得 14 z 14 都取线性规划2 4 5中的整数可行解的目标函数值的最大值 性质2 当整数规划的最优目标函数值z 的上界等于其下界z时 该整数规划的最优解已经被求出 这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解 24 3整数规划的分枝定界法 用图8 2表示例9的求解过程与求解结果 线性规划1Z1 14 66X1 2 44X2 3 26 z 13 14 66 线性规划2Z2 13 90X1 2X2 3 30 线性规划3Z3 14 58X1 3X