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,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次 √ √ √ √
、指派问题与匈牙利法
三、指派问题与匈牙利法
1、指派问题的数学模型 设有n个工作,要由n个人来承12…j n 担,每个工作只能由一个人承 In 担,且每个人只能承担一个工2nc2e…c 作。c;表示第i个人做第j件事 的费用,求总费用最低的指派 方案 n 刀1C C 第个人做第j人件事指派问题模型: 角:x= 0第个人不做第j人件事 minz=∑∑cnx x1+x,2+…+x;+…+x i2 i=12 ,J- n S1x+x,+…+xn+…+x=1 Z表示总费用 x , n,y
设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。 1 2 … j … n 1 2 … i … n 指派问题模型： = j i ij ij min Z c x + + + + + = 1 . i1 i2 i j i n x x x x st i=1,2, …,n 1 1 2 + + + + + = j j i j nj x x x x j=1,2, …,n x i n j n i j = 0,1 = 1,2, , ; = 1,2, , 解： 第i个人做第j 人件事 Z表示总费用 i=1,2, …,n; j=1,2, …,n 第i个人不做第j 人件事 = 0 1 ij x n n nj n n i i ij i n j n j n c c c c c c c c c c c c c c c c 1 2 1 2 21 22 2 2 11 12 1 1 1、指派问题的数学模型
mIn Z=∑∑cx=1+212+…+n 十C,x十∴C nT2n ∴∴ nnt nn +x12+…+x;+…+x1n=1 x21+x2+…+x21+…+x2n x+x2+…+x+…+x=1 xn1+x,+…+xn+…+x .. st x1,十X;+……+x,+…+x x1+x21+…+x1+…÷心 121422 xn+x,n+…+xn+…+xn=1 当n=4时,有16变量,8个约束方程
= j i ij ij min Z c x n n n n n n n n n n n n c x c x c x c x c x c x c x c x c x + + + + + + + + + = + + + 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 + + + + + =1 . i1 i2 i j i n x x x x st 1 1 2 + + + + + = j j i j nj x x x x i=1,2, …,n j=1,2, …,n 当n=4时，有16变量，8个约束方程 + + + + + = + + + + + = + + + + + = 1 1 1 . 1 2 2 1 2 2 2 2 1 1 1 2 1 1 n n n j n n j n j n x x x x x x x x x x x x st 1 1 1 1 2 12 22 2 2 11 21 1 1 + + + + + = + + + + + = + + + + + = n n i n n n i n i n x x x x x x x x x x x x
例:现有4份工作,4个人应聘,由z表示总费用 于各人技术专长不同,他们承担mxz=3x1+5+41+53 各项工作所需费用如下表所示, +6x1,+7x2+6x,+8x 且规定每人只能做一项工作,每 +8x1+9x2+8x3+10x4 项工作只能由一人承担,试求 +10x41+10x2+9x3+11x4 使总费用最小的分派方案。 x1+x12+x13+x14= 234 x21+x22+x23+x24 x21+x2+x2+x24=1 x41+x42+x43+x4=1 6768 389810 +x21+x21+xn1=1 41010911 S.x12+x4x1 解: x13+x +x2+x12=1 第i人做第j件事 13 23 x4+x24+x34+x4=1 第人不做第j件事 0.1
例：现有4份工作，4个人应聘，由 于各人技术专长不同，他们承担 各项工作所需费用如下表所示， 且规定每人只能做一项工作，每 一项工作只能由一人承担，试求 使总费用最小的分派方案。 工作 人 1 2 3 4 1 2 3 4 3 5 4 5 6 7 6 8 8 9 8 10 10 10 9 11 解： = ij x 1 0 第i人做第j 件事 Z表示总费用 i=1,2, 3,4; j=1,2, 3,4 第i人不做第j 件事 11 12 13 14 max Z = 3x +5x + 4x +5x 21 22 23 24 + 6x + 7x + 6x +8x 31 32 33 34 +8x +9x +8x +10x 41 42 43 44 +10x +10x +9x +11x + + + = 1 . 1 1 1 2 1 3 1 4 x x x x st x21 + x22 + x23 + x24 =1 x31 + x32 + x33 + x34 =1 x41 + x42 + x43 + x44 =1 x11 + x21 + x31 + x41 =1 x12 + x22 + x32 + x42 =1 x13 + x23 + x33 + x43 =1 x14 + x24 + x34 + x44 =1 j n i n xij 1,2, , 1,2, , 0,1 = = =
2、费用矩阵 设有n个工作,要由n个人来承象12jn 担,每个工作只能由一个人承11c2…,…a 担,且每个人只能承担一个工21c2…c…c2 作。c表示第个人做第j件事 的费用,求总费用最低的指派 方案 n nIna n 取C 费用矩阵 c;表示第个人做第j件事的费用
2、费用矩阵 设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。 1 2 … j … n 1 2 … i … n n n nj n n i i ij i n j n j n c c c c c c c c c c c c c c c c 1 2 1 2 21 22 2 2 11 12 1 1 = n n n n n n c c c c c c c c c C 1 2 21 22 2 11 12 1 取 cij表示第i个人做第j件事的费用 费用矩阵