运筹学 整数规划建模.ppt

第6章整数规划北京理工大学珠海学院廖爱红aihongliao 本章内容要点 整数规划相关概念整数规划问题的一般特点整数规划建模举例 引例 经济管理当中经常存在人员分派问题 企业中有4个人可以胜任4项不同工作的任意一项 但是完成工作的效率有所不同 如表所示 为了使得企业获得最好的经济效益 应该如何分派这四个人完成四项不同工作 6 1整数规划问题的提出6 1 1问题特征变量取值范围是离散的 经典连续数学中的理论和方法一般无法直接用来求解整数规划问题 不考虑整数条件 由余下的目标函数和约束条件构成的规划问题称为整数规划问题的松弛问题 若松弛问题是一个线性规划问题 则称该整数规划问题为整数线性规划问题 整数线性规划问题的分类 纯整数线性规划问题 要求全部变量均取整数混合整数线性规划问题 要求部分变量取值为整数0 1整数线性规划问题 决策变量取值为0或1 6 1 2整数规划建模中常用的处理方法 1 资本预算问题设有n个投资方案 cj为第j个投资方案的收益 投资过程共分为m个阶段 bi为第i个阶段的投资总量 aij为第i阶段第j项投资方案所需要的资金 目标是在各阶段资金限制下使整个投资的总收益最大 设决策变量xj为对第j个方案的取 xj 1 或舍 xj 0 可得到下列整数规划问题 是0 1规划 yj yj yj x xij为整数 该问题的约束反映了第i个时期资金增长量的平衡 这里aij代表第i时期内第j项投资的净资金流量 aij 0 表示需附加资金 aij0 表示有附加资金的数量 bi 0 表示要抽回资金的数量 9 例 某公司考虑今后五年内给以下项目投资 项目A 每年年初可以投资 于次年末回收本利115 投资金额必须为1万元的整数倍 项目B 每年初可购买公债 于当年末归还 并加利息6 投资金额必须为1万元的整数倍 项目C 第2年初可以投资 到第5年未能回收本利140 投资金额必须为1万元的整数倍 项目D 第3年初可以投资 到第5年未能回收本利128 如果投资金额必须大于2万元 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第5年末拥有的资金本利总额为最大 10 解 1 设xiA xiB xiC xiD i 1 2 3 4 5 分别表示第i年年初给项目A B C D的投资额 变量 第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx1Bx2Bx3Bx4Bx5BCx2CDx3D 6 1 2建模中常用的处理方法 续 2 指示变量 指示不同情况的出现P139例 有m个仓库 要决定动用哪些仓库 满足n个顾客对货物的需要 并决定从各仓库分别向不同顾客运送多少货物 6 1 2建模中常用的处理方法 续 费用 fi 动用i仓库的固定运营费 租金等 cij 从仓库i到j顾客运送单位货物的运费约束条件 i 每个顾客的需要量dj必须得到满足 ii 只能从动用的仓库运出货物 6 1 2建模中常用的处理方法 续 取足够大的数 迫使当yi 0时 xij必须为0 6 1 2建模中常用的处理方法 续 3 线性规划模型的附加条件在许多实际问题中 线性规划模型中的约束条件允许一定范围的放宽或对个别因素有进一步限制时 常可通过引入0 1变量来处理 下面介绍几种情况 作为一种建模思路的启示 不同时成立的约束条件 设某个模型问题中的约束条件不必同时成立 有m个线性不等式约束对每个约束引入一个指示变量yi 并得到每个约束左端的一个上界Mi i 1 2 n 建立下列不等式 显然 当yi 1时 两式等价 当yi 0时 第二个式子是恒成立 相当于除去了这个限制 在实际问题中 如果至少有k个约束成立时 只需附加下列约束 最优解中非零分量个数的限制 在许多实际问题中 对最优解中的非零分量个数有所限制 类似上述分析可对每个决策变量xi找到其上界Mi 并引入指示变量yi 附加下式 6 4 6 5 式 6 5 说明 非零分量至多有k个 离散的资源变化 实际问题中常出现下列情况 不等式约束表示右端的值可以有k个等级的违背 而 这里b0为最低的限制 在这个限制下 不需付出代价 其余的限制bi i 1 2 k 各需相应付出代价ci i 1 2 k 自然有 某工厂拥有A B C三种类型的设备 生产甲 乙两种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三设备可利用的时数如下表所示 问题 工厂应如何安排生产可获得最大的总利润 案例 假设上表甲乙两种产品利润中仅未去除用电成本 已知 用电500度以内总成本为0 用电1千度以内总成本为100元 1 2千度总成本为300元 2 3千度总成本为600元 3千度以上成本为1500元 在这种情况下 可以引入0 1变量yi来把上述情况模型化 用式 6 7 和式 6 8 取代式 6 6 6 7 6 8 在目标函数上需加一项 求min时 6 9 由此不难看出式 6 7 以及式 6 8 决定了式 6 6 中的一个式子成立 而式 6 9 表明把相应的代价加到目标函数中 6 2整数规划问题建模 整数规划问题的特征 变量取值范围是离散的 在经典连续数学中的理论和方法一般无法直接用来求解整数规划问题 求解时需要技巧 24 整数规划建模P305 例P305S2 1京成畜产品公司计划在市区的东 西 南 北四区建立销售门市部 拟议中有10个位置Aj j 1 2 3 10 可供选择 考虑到各地区居民的消费水平及居民居住密集度 规定 在东区A1 A2 A3 3个点至多选择2个 在西区A4 A5 2个点中至少选1个 在南区A6 A7 2个点中至少选1个 在北区A8 A9 A10 3个点中至少选2个 25 整数规划建模P305 例P305S2 1Aj各点的设备投资及每年可获利润由于地点不同都是不一样的 预测情况见下表所示 单位 万元 但投资总额不能超过720万元 问应选择哪几个销售点 可使年利润为最大 26 解 设 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 1变量 j 1 2 3 10 软件求解演示 28 例P305S2 2 高压容器公司制造小 中 大3种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如下表所示 每种容器售出所得的利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人月 机器有100台月 此外 每种容器制造都要支付一笔固定的费用 小号是l00万元 中号为150万元 大号为200万元 现在要制定一个生产计划 使获得的利润为最大 整数规划建模 29 解 设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 0且为整数yj为0 1变量 j 1 2 3 软件求解演示 31 整数规划建模 指派问题有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 例 有4个工人 要分别指派他们完成4项不同的工作 每人做各项工作所消耗的时间如下表所示 问应如何指派工作 才能使总的消耗时间为最少 32 解 令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 33 例 某企业在A1地已有工厂 其产品的生产能力为30万箱 为扩大生产 拟在A2 A3 A4 A5地中再选择若干地建厂 已知在A2 A3 A4 A5地建厂的固定成本分别为17 5 30 37 5 50万元 另外 A1产量及A2 A3 A4 A5建成厂的产量 那时销地的销量以及产地到销地的单位运价 每万箱运费 如右下表所示 问应该在哪些地方建厂 在满足销量的前提下 使得其总的固定成本和总的运输费用之和最小 整数规划建模 34 解 设xij为从Ai运往Bj的运输量 单位千箱 yi 1 当Ai被选中时 或0 当Ai没被选中时 Minz 8x11 4x12 3x13 5x21 2x22 3x23 4x31 3x32 4x33 9x41 7x42 5x43 10 x51 4x52 2x53 17 5y2 30y3 37 5y4 50y5s 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 0yi为0 1变量 i 1 2 3 4 5 j 1 2 3 35 例 某公司考虑今后五年内给以下项目投资 项目A 每年年初需要投资 于次年末回收本利115 但要求第1年投资最低金额为4万元 第2 3 4年不限 项目B 第3年初投资 到第5年未能回收本利128 但规定最低投资金额为3万元 最高金额为5万元 项目C 第2年初投资 到第5年未能回收本利140 但规定其投资额只能为2 4 6或8万元 项目D 每年初可购买公债 于当年末归还 并加利息6 此项投资金额不限 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第5年末拥有的资金本利总额为最大 36 解 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万元 6万元 4万元 2万元 不投资C项目时 分别取值为4 3 2 1 0 变量 第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C 20000y2C Dx1Dx2Dx3Dx4Dx5D 37 2 约束条件 第一年 年初有10元 D项目在年末可收回投资 故第一年年初应把全部资金投出去 于是x1A x1D 10 第二年 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 38 关于项目A的投资额规定 x1A 4y1A x1A 20y1A 20是足够大的数 保证当y1A 0时 x1A 0 当y1A 1时 x1A 4 关于项目B的投资额规定 x3B 3y3B x3B 5y3B 保证当y3B 0时 x3B 0 当y3B 1时 5 x3B 关于项目C的投资额规定 x2C 2y2C y2C 0 1 2 3 4 39 3 模型 Maxz 1 15x4A 1 40 x2C 1 28x3B 1 06x5Ds