0-1整数
决策问题与0-1变量 决策变量x,--是否做第i件事讠=1,2,…,n 做第i件事 0不做第i件事 n件事中必须做k件并只做k件事◇x+x2+…+xn=k n件事中最多做k件事令x1+x2+…+xn≤k n件事中至少做k件事令x1+x2+…+xn≥k 做第i件事的充要条件是做第j件事分>x=x 做第i件事的充要条件是不做第j件事◇>x=1-x 只在做了第i件事前提下才考虑是否做第j件事◇>x≤x
一、决策问题与0-1变量 决策变量xi − −是否做第i件事 xi = 1 0 做第i件事 不做第i件事 i =1,2, ,n n件事中必须做k件并只做k件事 x x x k 1 + 2 ++ n = n件事中最多做k件事 x x x k 1 + 2 ++ n n件事中至少做k件事 n x + x ++ x 1 2 k 做第i件事的充要条件是做第j件事 i j x = x 做第i件事的充要条件是不做第j件事 i j x = 1− x 只在做了第i件事前提下才考虑是否做第j件事 j i x x
例投资项目模型: maXZ=150x,+210x2+60x2+80x+180x 210x1+300x2+100x3+130x4+260x5≤600 x1+x,+x2≥1 X +x 0.1i=1,25 土捆足 反 方案,使投资收益最大 项目投资额投资收益 解:设x为决策变量(=12…5) (万元)(万元) 投资第讼个项目 210 150 300 0不投资第i个项目 4 130 80 Z表示投资效益 26 180
该公司只有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 x i =1,2, ,5) 解：设 i 为决策变量（ xi = 1 0 投资第i个项目 不投资第i个项目 Z表示投资效益 投资项目模型： max 150 1 210 2 60 3 80 4 180 5 Z = x + x + x + x + x s.t 210x1 + 300x2 +100x3 +130x4 + 260x5 600 x1 + x2 + x3 1 x3 + x4 =1 x5 x1 xi = 0,1 i =1,2, ,5
例2(布点问题)某城市共有6个「地 区,每个区都可以建消防站。区 市政府希望设置的消防站最少, 0|1016282720 10024321710 但必进b 发 316240122721 生 最优解 分 428321201525 钟 1,x4=1则定 527172715014 各区之间消防华行驶的时间见 620102125140 右表 个布点问题模型: 最优值 Oolgminz=x+x2+x,+x4+x+x6 Z=2 区建站 x1+x2≥1 解: 310不在第个地区建站 +x2+x≥1 Sx3+x1≥1 x2+x1+x≥1 x≤+x。≥1 Z表示全区消防站总数 0.1i=12.….6
例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 请为该市制定一个 最节省的计划 解： = 0 1 xi 在第i个地区建站 Z表示全区消防站总数 不在第i个地区建站 i=1,2, …,6 布点问题模型： min 1 2 3 4 5 6 Z = x + x + x + x + x + x xi = 0,1 i =1,2, ,6 s.t x1 + x2 1 x1 + x2 + x6 1 x3 + x4 1 x3 + x4 + x5 1 x2 + x5 + x6 1 最优解 x2=1, x4=1 最优值 Z=2
过滤隐枚举法(适合于变量个数较少的0-1规划) 例:求maxZ=3x,+5x2-2x2 运算次数: 21 x1+2x2-x2≤2 (x1x2x3)Z值 约束条件 x,+4x+x,<42 过滤条件 (1)(2)(3)(4) .t x,+x <3 (000)0 Z>0 4x1+x,<6 x,x2x3=0或 (010)5 Z (100)3 枚举法: (101)1 (110)8 × 检验可行解: (011)3 32次运算 (11)6√√√√ 计算目标 最优解:x1=1,x2=,x3=1 函数值:8次 最优值Z=6
二、过滤隐枚举法 （适合于变量个数较少的0-1规划） = + + + + + − = + − , , 0 1 4 6 3 4 42 2 2 . max 3 5 2 1 2 3 2 3 1 2 1 2 3 1 2 3 1 2 3 或 例：求 x x x x x x x x x x x x x st Z x x x （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 6 1 1 2 1 3 1 = = = = Z x x x 最优值 最优解： ， ， 运算次数： 21 计算目标 函数值：8次 √ √ √ √