整数规划应用案例分析

一 投资项目的选择利用线性规划可以来完成资金预算决策 决定对不同项目投资额各是多少 但实际中 一些资金预算决策不是决定投资多少 而是是否进行一些固定金额的投资 管理层必须经常面对的是 在预投入资金额度一定的情况下 是否进行一项或几项固定投资 对每个是或否的决策 1 是引入决策变量x 0 否 第四章整数规划的应用 例1投资问题 设某公司在m个时段里有n项投资计划 由于资金限制不能全部进行 已知1 第i个时段里该公司可动用的资金是bi 2 第j项投资计划所需要的资金是aij 3 能够得到的利润是cij 问该公司如何选择投资计划 使m个时段内的总利润最大 解 设xij表示在第i个时段内对第j个投资计划的决策变量 建立该投资问题的数学模型为 表示第i个时段内选中第j个投资计划 表示第i时段内未选中第j个投资计划 该公司只有600万元资金可用于投资 由于技术原因 投资受到以下约束 1 在项目1 2和3中必须有一项被选中 2 项目3和4只能选中一项 3 项目5被选中的前提是项目1必须被选中 如何在上述条件下 选择一个最好的投资方案 使收益最大 投资项目的选择例2 华美公司有5个项目被列入投资计划 各项目的投资额和期望的投资收益见下表 1选中项目i0未选中项目I i 1 5 解 令xi MaxZ 150 x1 210 x2 60 x3 80 x4 180 x5s t 210 x1 300 x2 100 x3 130 x4 260 x5 600 x1 x2 x3 1x3 x4 1x5 x1xi 1或0 i 1 5 1 2 3必须有一项选中 3 4只能选中一项 5被选中前提是1选中 解得 1 0 0 1 1 MaxZ 410即投资项目1 4 5 可以获得410万元 二 分布系统设计 选址问题 在如今的全球经济中 许多公司正在全世界各个地方建立新工厂 为的是获得低劳动力成本等好处 在为新工厂选址之前 需要分析和比较地点 每个可供选择的地点都涉及一个是或否的决策 对每个是或否的决策 1 是引入决策变量x 0 否在许多案例中 目标是地点的选择以使新建设施的总的成本最小化 且这新设施能满足生产的需要 分布系统设计 选址问题例3 某企业在A1地已有一个工厂 其产品的生产能力为30千箱 为了扩大生产 打算在A2 A3 A4 A5地中再选择几个地方建厂 已知在A2 A3 A4 A5地建厂的固定成本分别为175千元 300千元 375千元 500千元 另外 A1产量及A2 A3 A4 A5建成厂的产量 各销地的销量以及产地到销地的单位运价 每千箱运费 如下表所示 a 问应该在哪几个地方建厂 在满足销量的前提下 使得其总的固定成本和总的运输费用之和最小 解 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 10 A2厂的产量限制 x31 x32 x33 20 A3厂的产量限制 x41 x42 x43 30 A4厂的产量限制 x51 x52 x53 40 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 模型检查 是否有问题 解 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 b 如果由于政策要求必须在A2 A3地建一个厂 应在哪几个地方建厂 练习 例4 某钻井队要人以下10个可供选择的井位中确定5个钻井探油 使总的钻探费用为最小 若10个井位的代号为 相应的钻探险费用为 并且井位选择上要满足下列限制条件 或选择和 或选择 选择了或就不能选 或反过来也一样 在中最多只能选两个 试建成立这个问题的整数规划模型 解 设决策变量目标函数为约束条件 1 从10个可供选择的井位中确定5个探油 则2 或选择和 或选择可表示为 3 选择了或就不能选 反过来也一样 可表示为4 在中最多只能选两个可表示为综上所述 该问题的整数规划模型如下 例5 某部队为了完成某项特殊任务 需要昼夜24小时不间断值班 但每天不同的阶段所需要的人数不同 具体情况如下 假设值班人员分别在各时间段开始时上班 并连续工作8小时 该部队要完成这项任务至少需要配备多少名值班人员 班次时间段需要人数16 00 10 0060210 00 14 0070314 00 18 0060418 00 22 0050522 00 2 002062 00 6 0030 三 值班安排 解 设分别表示第i个班次开始上班的人数 每个人连续值班8小时 根据题意所求问题归结为如下整数规划的数学模型 MODEL Sets Num 1 6 b x EndsetsData b 60 70 60 50 20 30 Enddata OBJ min sum num i x i x 1 x 6 60 x 1 x 2 70 x 2 x 3 60 x 3 x 4 50 x 4 x 5 20 x 5 x 6 30 for num i GIN x i x i 0 END 练习 兼职值班 例6 东方大学计算机实验室聘用4名大学生 代号1 2 3 4 和2名研究生 代号5 6 值班答疑 已知每人从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下 班次报酬每天最多可安排的值班时间 元 时 周一周二周三周四周五110 060607210 00606039 94830549 855604510 830480611 306063 该实验室开放时间为上午8 00至晚上10 00 开放时间内须有且仅须一名学生值班 规定大学生每周值班不少于8小时 研究生每周不少于7小时 每名学生每周值班不超过3次 每次值班不少于2小时 每天安排的值班学生不超过3人 且其中必须有一名研究生 试为该实验室安排一张人员值班表 使总支付的报酬最少 班次报酬每天最多可安排的值班时间 元 时 周一周二周三周四周五110 060607210 00606039 94830549 855604510 830480611 306063 解 设为学生i在周j的值班时间 分析约束条件 四 固定成本问题例7 高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如表所示 不考虑固定费用 每种容器售出一只所得的利润分别为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 五 分配问题 Assignmentproblem 有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 例8 4个人完成4项工作任务 由于个人的技术专长不同 他们完成4项工作任务所获得的收益如下表所示 且规定每人只能做一项工作 一项工作任务只需一人操作 试求使收益最大的分派方案 解 引入0 1变量xij 并令xij 1 当指派第i名队员游第j种姿势 或0 当不指派第i名队员游第j种姿势 这可以表示为一个0 1整数规划问题 Minz 56x11 74x12 61x13 63x14 63x21 69x22 65x23 71x24 57x31 77x32 63x33 67x34 55x41 76x42 62x43 62x44s t x11 x12 x13 x14 1 A只能游一种姿势 x21 x22 x23 x24 1 B只能游一种姿势 x31 x32 x33 x34 1 C只能游一种姿势 x41 x42 x43 x44 1 D只能游一种姿势 x11 x21 x31 x41 1 自由泳只能一人游 x12 x22 x32 x42 1 蛙泳只能一人游 x13 x23 x33 x43 1 蝶泳只能一人游 x14 x24 x34 x44 1 仰泳只能一人泳 xij为0 1变量 i j 1 2 3 4 Model sets num i 1 4 num j 1 4 link num i num j a x endsetsdata a 56 74 61 63 63 69 65 71 57 77 63 67 55 76 62 62 enddata OBJ min sum link i j a i j x i j for num i i sum num j j x i j 1 for num j j sum num i i x i j 1 for link i j BIN x i j x i j 0 END 备用例9 某公司在今后五年内考虑给以下的项目投资 已知 项目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 设y2C是非负整数变量 并规定 第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 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 例10 电力规划问题 某地区在制定十年电力规划时 遇到这样一个问题 根据电力需求预测 该地区十年以后发电装机容量需要增加180万千瓦 到时年发电量需增加100亿度 根据调查和讨论 电力规划的备选技术方案有三个 扩建原有火电站 但最多只能安装5台10万千瓦机组 新建水电站 但最多只能安装4台25万千瓦机组 新建火电站 但最多只能安装4台30万千瓦机组 通过调研和计算 获得有关参数如下 注 负荷因子 全年满功率运行天数 全年总天数 方案1 241天 方案2 146天 方案3 255天 建立模型 设置决策变量设备选方案1 2 3的装机台数分别为x1 x2 x3 它们的年发电量分别为x6 x7 x8亿度 备选方案1无前期土建工程要求 备选方案2和3都需要前期土建工程 这两个前期土建工程是否施工用变量x4 x5代表 则x1取值0 5之间的整数 x2 x3取值0 4之间的整数 x4 x5只能取0或1 x6 x7 x8大于零 约束方程满足装机容量需求约束 10 x1 25x2 30 x3 180满足规划年发电量需求约束 x6 x7 x8 100 各电站容量与发电量平衡方程 机组年发电量等于单机容量乘全年小时数 再乘以负荷因子 换算亿度量纲 即 方案1 x6 0 66 8760 10 10000 x1方案2 x7 0 4 8760 25 10000 x2 方案3 x8 0 7 8760 30 10000 x3得三个约束方程 5 782x1 x6 08 76x2 x7 018 39x3 x8 0 每个方案最多的装机台数约束 方案1 不需前期土建工程 x1 5方案2 前期土建工程是装机的先决条件 且小于最大允许数 x2 4x4方案3 前期土建工程是装机的先决条件 且小于最大允许数 x3 4x5 变量取值限制x1 x2 x3 0且整数x6 x7 x8 0 x4或x5 1前期土建工程要求x4或x