第3章整数规划
线性规划模型: maXz=C1x1+C,X2+∴c孓 1x1+a12x2+…+a1nxn=b1 s t anx+anx2+…+amxn=bn 0 1:2 °n 实际问题要求x为整数! 如机器的台数,人数等
n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 . , , 0 x1 x2 xn 线性规划模型： 实际问题要求xi为整数！ 如机器的台数，人数等
线性整数规划 整数规划 简称整数规划 非线性整数规划
整数规划 线性整数规划 非线性整数规划 简称整数规划
3.1整数规划问题 实例
一、实例
例21胜利家具厂生产桌子和椅子两种家具。桌子售价50元/ 个,椅子售价30元/个,生产桌子和椅子需要木工和油漆工两 种工种。生产一个桌子需要木工4个小时,油漆工2小时。生 产一个椅子需要木工3个小时,油漆工1小时。该厂每月可用 木工工时为120小时,油漆工工时为50小时。问该厂如何组 织生产才能使每月的销售收入最大? 解:设x1=生产桌子的数量x2=生产椅子的数量 每月的销售收入 求maxZ=50x1+30x2 4x,+3x2<120 纯整数 s2x,+x,≤50 规划 x1,x2≥0 x1,x2为整数
例2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/ 个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两 种工种。生产一个桌子需要木工4个小时，油漆工2小时。生 产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用 木工工时为120小时，油漆工工时为50小时。问该厂如何组 织生产才能使每月的销售收入最大？ 每月的销售收入 解：设 生产桌子的数量 生产椅子的数量 = = = Z x x 1 2 , 1 2 求max Z = 50x +30x 4 + 3 120 . 1 2 x x st 2x1 + x2 50 , 0 x1 x2 x1 , x2 为整数 纯整数 规划
例(背包问题)一个旅行者,为了准备旅行的必备物品,要在 背包里装一些有用的东西,但他最多只能携带b公斤的东西, 而每件物品都只能整件携带,于是他给每件物品规定了一个 “价值”,以表示其有用程度。如果共有m 0-1规划 物品的重量为b;,价值为c;,问题就变成: 量不超过b公斤的条件下,携带哪些物品可使总价值最大 带第i件物 解:(0不带第件物 数学模型: max Z Z表示所带物品的总价值 ∑ ∑c=∑ b.x.<b 带第i 携带物品的总重量=∑bx O.1
例（背包问题）一个旅行者，为了准备旅行的必备物品，要在 背包里装一些有用的东西，但他最多只能携带b公斤的东西， 而每件物品都只能整件携带，于是他给每件物品规定了一个 “价值”，以表示其有用程度。如果共有m件物品，第i件件 物品的重量为bi，价值为ci，问题就变成：在携带的物品总重 量不超过b公斤的条件下，携带哪些物品可使总价值最大 解： = 不带第 件物品 带第 件物品 设 i i xi 0 1 Z表示所带物品的总价值 = 带第i件 i Z c = = m i i i c x 1 携带物品的总重量 = = m i i i b x 1 数学模型： = = m i i i Z c x 1 max = b x b st m i i i 1 . i m xi 1,2, 0,1 = = ， 0-1规划
例:某公司计划在几个地点建厂,可供选择的地点有A,A2,…, An它们生产同一种产品,生产能力分别是a1,a2,…,an,建设费 分别是f,∫2…,f。又有n个地点B,B2…,B,需要销售这种 品其销售量分别为b,b2…,b,。从工厂A运往销地B的单位运 费为c。试决定应在哪些地方建厂,使得既满足各地的需求,又 使总建设费和总运输费最省? 解:设,表示工厂A运往商店B的运数学模型 则总运费∑cnx min z ∑∑cx+∑ 设=1在第个地点建 0不在第个地 则总建厂费y 0y;=021 混合型整数规划
解： 设xij表示工厂Ai运往商店Bj的运量 则总运费为 = 不在第 个地点建厂 在第 个地点建厂 设 i i yi 0 1 则总建厂费为 使总建设费和总运输费最省？ 费为 。试决定应在哪些地方建厂，使得既满足各地的需求，又 品 其销售量分别为 ， ， ， 。从工厂 运往销地 的单位运 分别是 ， ， ， 。又有 个地点 ， ， ， 需要销售这种产 它们生产同一种产品，生产能力分别是 ， ， ， 建设费 例：某公司计划在几个地点建厂，可供选择的地点有 ， ， ， i j n i j m n m m c b b b A B f f f n B B B A a a a A A 1 2 1 2 1 2 1 2 1 2 , , , = n j 1 = m i 1 ij ij c x = m i i i f y 1 x b j n j m i ij 1,2 , 1 = = = = = = + m i i n j ij ij m i Z c x f 1 1 1 min = = x a i m st i n j i j 1,2 , . 1 xij 0 yi = 0,1 数学模型： 混合型整数规划
纯整数规划 整数规划0-1规划 混合型整数规划 纯整数规划的数学模型: 0-1规划的数学模型 maX2=C1X1+C2X+…+C,x maXz=C1X1+C,X十…+Cx nn n n aux,+a,2x2+.+ain,xn=6 a1x1+a12x2+…+a1nxn a21x1+a2x+…+a、孓 +…+a,nxn=b st s t aL,x,+axn+…+ax.=b a.,x,+a.x+…+a_x.=b mn n ≥0 x1,x2…xn≥0 x2…,x,取整数 M 1.x 2
整数规划 纯整数规划 0—1规划 混合型整数规划 纯整数规划的数学模型： n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 . x1 , x2 , xn 0 x1 , x2 , xn 取整数 0--1规划的数学模型： n n z = c x + c x ++ c x max 1 1 2 2 + + + = + + + = + + + = m m mn n m n n n n a x a x a x b a x a x a x b a x a x a x b st 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 . x1 , x2 , xn 0 x1 , x2 , xn = 0,1
不可行 例mx==30x+20、√取x=3,x2=3 2x1+3x,≤14 2x1+x2≤9、√取x1=3,x2=2 s t x1≥0,x,≥ x,x2为整数√√可行z=130 2 但当x1=4,x2=时可行且Z=140 对maxz=30x1+20x2 2x1+3x,≤14 2x1+x,≤9 s. t x1≥O,x 最优解为x1=3.25,x2=2.5
例 + + = + 1 2 为整数 1 2 1 2 1 21 2 , 0 , 0 2 9 2 3 14 . max 30 20 x x x x x x x x st z x x + + = + 0, 0 2 9 2 3 14 . max 30 20 1 2 1 2 1 2 1 2 x x x x x x s t 对 z x x 最优解为x 1 = 3.25，x 2 = 2.5 × 取x 1 = 3 ， x 2 = 3 取x 1 = 3 ， x 2 = 2 √√√√ Z=130 但当 x 1 = 4 ， x 2 = 1 时 √√√√ ，可行且Z=140 不可行 可行
、整数规划解的理论 对整数规划问题: max z= CX max z=CX aX=b AX=6 (IP)sX≥0 X≥0 x,为整数 (IP)问题的松弛问题
二、整数规划解的理论 = = 为整数 对整数规划问题： j x X AX b st z CX . 0 max = = 0 . max X AX b st z CX （IP） （IP）问题的松弛问题