管理运筹学 第4章 整数规划.ppt

管理运筹学 第四章 整数规划 整数线性规划的类型 　 整数规划的分枝定界法 4.3 0-1整数规划及其应用 Max z= CX 0-1整数规划应用 一、投资场所的选择 例1：某公司计划在市区建立销售门市部，拟议中有10个位置 Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： A1，A2 ，A3 三个点至多选择两个； 如果选择A4 则必须选择A5 ； Aj 各点的设备投资及每年可获利润的预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大? 解：设： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 （ A1 ， A2 ，A3 三个点至多选择两个） （如果选择A4 则必须选择A5 ） xi ≥ 0 且xi 为0--1变量，i = 1，2，3，…,10 二、固定成本问题 例2：高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量、资源的限制、每种容器售出一只所得的利润 (不考虑固定费用)如下表所示，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 三、分布系统设计 例3：某企业在 A1 地已有一个工厂，其产品的生产能力为30千箱,为了扩大生产,打算在 A2、A3、A4，A5地中再选择几个地方建厂。已知在 A2 、A3、A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 问：应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? （1）甲-A 乙-D 丙-C 丁-B （2）甲-B 乙-A 丙-C 丁-D 200 150 100 固定费用 （万元/件） 6 5 4 单件利润 （万元/件） 100 3 2 1 机器设备 （台/月） 300 4 3 2 劳动力 （人/月） 500 8 4 2 金属板 （吨） 资源限制 大号容器 中号容器 小号容器 资 源 解：设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 引入约束 s.t. 最优解：x1=100 x2=0 x3=0 20 20 30 销量/千箱 500 40 2 4 10 A5 375 30 5 7 9 A4 300 20 4 3 4 A3 175 10 3 2 5 A2 30 3 4 8 A1 固定 成本 产量 B3 B2 B1 销地 运输单价 产地 解：设xij为从Ai运往Bj的运输量（单位：千箱） s.t. 关于产量 关于销量 1、解决某市消防站的布点问题.该市共有6个区,每个区都可以建消防站.市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时,消防车要在15分钟内赶到现场.据实地测定各区之间消防车行使的时间见下表,试帮助该市制定一个最节省的计划. 习题 20 10 21 25 14 0 27 17 27 15 0 14 28 32 12 0 15 25 16 24 0 12 27 21 10 0 24 32 17 10 0 10 16 28 27 20 1 2 3 4 5 6 6 5 4 3 2 1 时间 解： 建立模型： s.t. 2、篮球队需要选择5名队员组成出场阵容参加比赛，8名队员的身 高及擅长位置如下表。出场阵容应满足以下条件： （1）只能有一名中锋上场； （2）至少有一名后卫； （3）如1号和4号均上场，则6号不出场； （4）2号和8号至少有一个不出场 问应当选择哪5名队员上场，才能使出场队员平均身高最高？ 后卫 后卫 后卫 前锋 前锋 前锋 中锋 中锋 擅长位置 1.78 1.80 1.83 1.85 1.86 1.88 1.90 1.92 身高 8 7 6 5 4 3 2 1 队员 3、某大学计算机实验室聘用4名大学生（代号1、2、3、4）和两名 研究生（代号5、6）值班答疑。已知每人从周一到周五最多可安排 的值班时间及每人每小时值