第四讲0-1整数线性规划祥解.pptVIP

第四讲 0-1整数规划  ·0-1整数规划 1.什么是0-1整数规划？ 2.什么时候采用0-1整数规划法？ 　　0-1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 　正如计算机只懂得0,1两个数，1代表是，0代表否。同样的，在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件事 例1：一个旅行者要到某地作两周的带包旅行,装背包时,他发现除了已装的必需物件外,他还能再装5公斤重的东西.他打算从下列4种东西中选取,使增加的重量不超过5公斤又能使使用价值最大.这4种东西的重量和使用价值(这里用打分数的办法表示价值)如下表所示,问旅行者应该选取哪些物件为好？ 解：建立模型为 max=6*x1+7*x2+3*x3+9*x4; 2*x1+3*x2+x3+4*x4=5; @bin(x1); @bin(x2); @bin(x3); @bin(x4); 该公司只有600万资金可用于投资，由于技术上的 原因，投资受到以下约束： 1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项 3、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大 例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表： 项目 投资额 （万元） 投资收益 （万元） 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180 1 0 投资第i个项目 不投资第i个项目 Z表示投资效益 投资项目模型： 该公司只有600万资金可用于投资，由于技术上的 原因，投资受到以下约束： 1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项 3、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大 例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表： 项目 投资额 （万元） 投资收益 （万元） 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180 1 0 投资第i个项目 不投资第i个项目 Z表示投资效益 投资项目模型： max=150*x1+210*x2+60*x3+80*x4+180*x5; 210*x1+300*x2+100*x3+130*x4+260*x5=600; x1+x2+x3=1; x3+x4=1; x5=x1; @bin(x1); @bin(x2); @bin(x3); @bin(x4); @bin(x5); 整数规划建模举例 某财团有 万元的资金，经过其考察选中 个投资 项目，其中第 个项目需投资金额为 万元，预 计获利 （ ）万元，由于种种原因， 有两个附加条件：第一，项目2和项目3至少选择一 个；第二项目5，6，7恰好选择两个。问应如何选 择项目使得总收益最大？ 练习1：组合投资问题。 要决策的是每个项目是否需要投资 练习1：组合投资问题。 0-1整数规划 二、过滤隐枚举法 （适合于变量个数较少的0-1规划） （x1 x2 x3) Z值 约束条件 （1）（2）（3）（4） 过滤条件 （0 0 0） （0 0 1） （0 1 0） （1 0 0） （1 0 1） （1 1 0） （0 1 1） （1 1 1） √ √ √ √ 0 Z≥0 枚举法： 检验可行解： 32次运算 -2 5 √ √ √ √ Z≥5 3 1 8 × 3 6 运算次数：21 计算目标