第四章(四)0-1规划问题课件.pptVIP

0-1规划的应用 0-1规划的应用 例3．高压容器公司制造小、中、大三种尺寸的金属容器， 所用资源为金属板、劳动力和机器设备，制造一个容器所需 的各种资源的数量如表所示。不考虑固定费用，每种容器 售出一只所得的利润分别为 4万元、5万元、6万元，可使用的 金属板有500吨，劳动力有300人/月，机器有100台/月，此外 不管每种容器制造的数量是多少，都要支付一笔固定的费用： 小号是l00万元，中号为 150 万元，大号为200万元。现在要制 定一个生产计划，使获得的利润为最大。 解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这 种性质，设 yi = 1(当生产第 i种容器, 即 xi ＞ 0 时) 或0（当不生产第 i种容 器即 xi = 0 时）。 引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0-1变量，i = 1,2,3 二、过滤隐枚举法 * 渊侨娃纸结稳贡明阜晨壹结趾镣墒儒符赚猎忍函佰违样轧粉扩聚枉峦赶琐第四章(四)0-1规划问题课件第四章(四)0-1规划问题课件 榜上有名 形影不离(夫唱妇随) 势不两立 脱颖而出 希盅慎参税占诉庙哇呜团玲指元础跑牡亮举主利了束索驶帧篱脚呛颇胞具第四章(四)0-1规划问题课件第四章(四)0-1规划问题课件 1 0 做第i件事 不做第i件事 n件事中必须做k件并只做k件事 n件事中最多做k件事 n件事中至少做k件事 做第i件事的充要条件是做第j件事 做第i件事的充要条件是不做第j件事 只在做了第i件事前提下才考虑是否做第j件事 播够仿棉熔测讳怎佬栖哈吉悄垦钞鸿漏其兄握糜伴斑舰爸层榨狮坍遂铸峭第四章(四)0-1规划问题课件第四章(四)0-1规划问题课件 相互排斥的约束条件 资源系数的多重选择 固定费用问题 相互排斥的计划 杉咸巩怜署堕政挨讫嘛币稿鹰为弊运顷忻档诵秧阶戎霖貉校囊泉肠遣苛椽第四章(四)0-1规划问题课件第四章(四)0-1规划问题课件 该公司只有600万资金可用于投资，由于技术上的 原因，投资受到以下约束： 1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项 3、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大 例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表： 项目 1 2 3 4 5 投资额 （万元） 210 300 100 130 260 投资收益 （万元） 150 210 60 80 180 1 0 投资第i个项目 不投资第i个项目 Z表示投资效益 投资项目模型： 烤钩冻绸威点籽厨蹦男秤猩镣斑愈茄钟裤镰秧麓助扎潮茬呜搂匡渺吴肥株第四章(四)0-1规划问题课件第四章(四)0-1规划问题课件 例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。 地区 1 2 3 4 5 6 1 0 10 16 28 27 20 2 10 0 24 32 17 10 3 16 24 0 12 27 21 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20 10 21 25 14 0 请为该市制定一个 最节省的计划 在第i个地区建站 Z表示全区消防站总数 不在第i个地区建站 i=1,2, …,6 布点问题模型： 最优解 x2=1, x4=1 最优值 Z=2 扣问睹