西北农林科技大学运筹学课件第五章 整数规划

6 2 1 x x 7 3 7 5 7 6 2 1 x x x 6 7 3 7 5 7
二、解纯整数规划的割平面法
Cj 3 -1 0 0 0 0
第五章
CB
3 -1 0
XB
x1 x2 x4
b
13/7 9/7 31/7
x1
1 0 0
x2
0 1 0
x3
1/7
x4
0
x5
2/7 3/7 22/7
三、 分枝定界法
求解步骤：
第五章
1）设有最大整数规划问题A ，相应的松弛问题为B 。以Zb 表示问题A的目标函数的初始界。（下界） 2）解 B a） B没有可行解，则A也没有可行解. b） B有最优解且为整数解，则A的最优解即得。 c） B有最优解但非整数解，B的最优值 Za为z*的上界
3）分枝 : 在B的最优解中取xi(=bi) bi不为整数。
原问题的最优解z * :
x1 4 x1 5
0 z * 356
1 ） x1非整数，在原约束问题中分别添加两个子约束：
三、 分枝定界法
得到两个子问题：B1 ; B2
第五章
同样不考虑整数条件其最优解为： B1 B2 z1 349 x1 4.00 x2 2.10 z 341 x1 5.00 x2 1.57
-1/2 1/4 -1/4
x5 0 0
0 1 0
x6 1 -5/4
-11/2 -3/4 -17/4
x5 7/4 σj=cj-zj
增加约束条件：
3 1 1 x x 4 4 4 6 4
3 1 1 x x x 7 4 4 4 6 4
二、解纯整数规划的割平面法
Cj XB x1 x2 3 x1 1 0 -1 x2 0 1 0 x3 0 0 0 x4 0 -1/4 0 x5 0 0 0 x6 1 -5/4
例
某厂拟用集装箱托运甲.乙两种货物。
甲 乙 托运限制 V m3 5 4 24 G 2 5 13 100kg 利润 20 10
问：如何托运才能使利润最大？
一、数学模型及解的特点
第五章
松弛问题的解：甲 4.8 调整 ： 1 ） “ 凑整” 甲 5 2 ） “ 舍尾” 甲 4 最优解 ： 甲 4 乙 1
第五章
CB 3 -1
b 1 5/4
0 x7 0 0
0
0
x3
x5
5/2
7/4
0
0
0
0
1
0
-1/2
1/4
0
1
-11/2
-3/4
0
0
0
x7 -3/4 σj=cj-zj
0 0
0 0
0 0
-1/4 -1/4
0 0
-1/4 -17/4
1 0
二、解纯整数规划的割平面法
Cj XB 3 x1 -1 x2 0 x3 0 x4 0 x5 0 x6
第五章
CB
b
0 x7
3 -1
0 0 0
x1 x2
x3 x5
1 2
4 1
1 0
0 0 0 0
0 1
0 0 0 0
0 0
1 0 0 0
0 0
0 0 1 0
0 0
0 1 0 0
1 -1
-5 -1 1 -4
0 -1
-2 1 -4 -1
x4 3 σj=cj-zj
原问题的最优解为：x1=1,x2=2
三、 分枝定界法
二、解纯整数规划的割平面法
割平面法求解步骤：
第五章
1.
2.
求解原问题的松驰问题；
若最优解全为整数，则达到最优；否则转3；
3.
从最优单纯形表中选择具有最大小数部分的非整
分量所在行构造割平面约束条件；
4. 5.
将新约束条件加入原问题最优单纯形表，求解； 返2。
二、解纯整数规划的割平面法
例：以课本例6为例说明。 Cj 3 -1 0 0 0
获得整数规划问题的一个可行解，那么，它的目标函数 值就是一个“界限”，可作为衡量处理其他分支的一个
依据。
线性规划问题当约束区域缩小后，所得到的目标函数
最优值不会更优于原来的约束区域所得到的最优值。
对于那些相应松弛问题最优解的目标函数值比上述 “界限”值差的后继问题，就可以剔除而不再考虑了。 如果出现更好的“界限”，则以它来取代原来的界限。
第五章
目前求解纯整数规划和混和整数规划最常用的方法。 分支概念： maxZ=CX AX=b (A)
maxZ=CX
X0
X为整数
(B)
AX=b
X0
(B)为(A)的松弛问题。
三、 分枝定界法
第五章
i+1
Xj*
i
X*
(C)
(B)
Xj i+1
(D)
(B) Xj i
三、 分枝定界法
第五章
定界概念：是在分支过程中，若某个后继问题恰巧
x5
0 0 0
x6
1 3/2 11
0
x5
3
0
0
0
0
1/2
0
1
0
-7/2
-3/2
σj=cj-zj
-1/14 0
二、解纯整数规划的割平面法
Cj 3 -1 0 0 0 0
第五章
CB 3 -1
0 0
XB x1 x2
x3
b 1 5/4
5/2
x1 1 0
0 0 0
x2 0 1
0 0 0
x3 0 0
1 0 0
x4 0 -1/4
乙 0
乙 0 乙 0
二、解纯整数规划的割平面法
纯整数规划问题
第五章
二、解纯整数规划的割平面法
第五章
在松弛问题的最优单纯形表中，记Q为m个基变量的下 标集合，K为n-m个非基变量的下标集合。
Cj CB XB b
9.5
26 14.5
3 x1
-2
3 -2 -10
5 x2
0
1 0 0
0 x3
1
0 0 0
1 x4
0
0 1 0
0 x5
0.5
0.5 0.5 -3
0 x6
-0.5
0.5 -0.5 -2
0 x7
-0.5
0.5 0.5 -3
θ
0
5 1
x3
x2 x4
σj=cj-zj
则m个约束方程可表示为：
二、解纯整数规划的割平面法
对应的最优解：
第五章
其中：
全为整数时，为纯整数规划的最优解。 bj不全为整数时，则不是纯整数规划的可行解，也 不是原整数规划的最优解。
混合整数规划
一、数学模型及解的特点
第五章
整数规线性划数学模型的一般形式：
,部分或全部为整数
一、数学模型及解的特点
几个概念：
第五章
1、整数规划（IP）---要求一部分或全部决策变量必须 取整数值的规划问题。 2、松弛问题---不考虑整数条件，由余下的目标函数和 约束条件构成的规划问题，称为该整数规划问题的松弛 问题。
第五章 整数规划
一、整数规划数学模型及解的特点
二、解纯整数规划的割平面法
三、分支定界法
四、0－1型整数规划
五、指派问题
一、数学模型及解的特点
例1、集装箱运货 货物 甲 体积(米3/箱) 重量(百公斤/箱) 5 2
第五章
利润(千元/箱) 20
乙
装运限制
4
24
5
13
10
一、数学模型及解的特点
解：设x1 , x2 为甲、乙两货物各托运箱数
第五章
CB 3
-1 0
XB x1
x2
b 13/7
9/7
x1 1
0 0 0
1 7
x2 0
1 0 0
x3 x4 1/7 0
-2/7 0 -3/7 1 -5/7 0
x5 2/7
3/7 22/7 -3/7
x4 31/7 σj=cj-zj
增加约束条件：
6 2 x3 (0 7 ) x5 13 1 7 7
LP1
LP1
X2 3 无解 LP121
X1 3 (3,1) max z=4 下界zb=4
三、 分枝定界法
例： max z 40 x1 90 x2 7 x2 20 x2 为非负整数 56 70 9 x1 7 x1 x , x 1 2
第五章
解：相应的松弛问题的最优解为： x1 4.81, x2 1.82 z0 356
x6
0 0 0
-2/7 0 -3/7 1
0
x6
-6/7
0
0
0
0
-1/7 0
-5/7 0
-2/7
-3/7
1
0
σj=cj-zj
二、解纯整数规划的割平面法
Cj 3 -1 0 0 0 0
第五章
CB
3 -1 0
XB
x1 x2 x4
b
1 0 -5
x1
1 0 0
x2
0 1 0
x3
0 -1/2 -2
x4
0 0 1
标函数值比界Zb更优的后继问题为待检查的后继问题。
若不存在待检查的后继问题。当C存在时，C最优解 为A最优解。当C不存在时，与界Zb对应的可行解为A的 最优解。 若存在待检查的后继问题，则选择其中目标函数值最 优的一个后继问题，改称其为问题B。回3）。
三、 分枝定界法
例7 用分支定界法求解下列整数规划问题 maxZ=X1 + X2
解：设xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=1…4)由 i仓库向 j商店运货量
min Z bi xi Cij yij
i 1 i 1 j 1 3 3 4
第五章
s.t.
y11 + y21 = d1 y12 + y22 + y32 = d2 y23+ y33 = d3 y14 + y24 + y34 = d4 x 1 + x2 + x3 = 2 y11 + y12 + y14 a1x1 y21 + y22 + y23 + y24a2x2 y32 + y33 + y34 a3x3 xi 为0－1， yij 0
二、解纯整数规划的割平面法
第五章
Xi0 ＋ A Xj = bi0 分解A ,b为两部分。
A=Na+Fa
则上式变为：
b=Nb+Fb
F为不超过该数的最大整数。
Xi0＋（ Na+Fa ）Xj＝Nb+Fb
Xi0＋ Na Xj－ Nb ＝ Fb － Fa Xj
Fb － Fa Xj 0 －Fa Xj -Fb 可以证明此条件满足上述两个基本性质。可以作 为增加的约束条件。
构造二约束条件 xi≤[bi] xi≥ [bi] +1 将此二约束条件分别加入B后得到二后继规划问题B1,B2
三、 分枝定界法
4）解后继问题。
第五章
若有最优解，且满足A的整数要求。则以其目标函数
值Zb’与Zb比较。 若Zb’优于Zb，则称此后继问题为问题 C，以Zb’作为下界。否则， Zb不变。
5）不属于C的后继问题中，称存在最优解，且其目
第五章
X1+9/14 X2 51/14
-2X1+X2 1/3 X1 , X2 0 整数
三、 分枝定界法
第五章
解：记整数规划问题为IP，其松驰问题为LP。 解LP，得最优解为（3／2，10／3），MAXZ＝29／6 以X1＝3／2进行分支。(下界zb=0,上界za=29/6)
LP1 (2,23/9) LP11 LP X1 2 max z=41/9 X2 2 (33/14,2) max z=61/14 LP12 LP1 LP122 X1 2 (2,2) max z=4 LP12 X1 1 (1,7/3) max z=10/3 LP2 LP
0 z * 349
三、 分枝定界法
二、解纯整数规划的割平面法
第五章
割平面法的思路：若松弛问题的最优解不全为整数， 则从X的非整分量中选取一个，用以构造一个线性约束 条件，将其加入原松弛问题中，形成一个新的线性规划， 然后求解之。直到全为最优解为止。 增加的约束条件具备的两个基本性质： 其一：原松弛问题最优解不满足该条件； 其二：凡整数可行解均满足该条件。
摄像机
枕头 休闲食品 衣服
3
1 2 4
1
4 3 5
30
10 18 15
一、数学模型及解的特点
解：xi为是否带第 i 种物品
第五章
maxZ=20x1 + 30x2 +10xห้องสมุดไป่ตู้+18x4 +15x5
5x1+3x2 +x3 +2x4 +4x5 8 2x1+x2 +4x3 +3x4 +5xX5 10 xi为0, 1 0－1型整数线性规划
一、数学模型及解的特点
例3、选址问题 A1 A2 B2 B1 B4 B3
第五章
Ai: 可建仓库地点，容量ai , 投资费用bi ，建2个 Bj: 商店，需求dj ( j=1…4 ) Cij: 仓库 i 到商店 j 的单位 运费
A3
问：选择适当地点建仓库，在满足商店需求条件 下，总费用最小。
一、数学模型及解的特点
第五章
maxZ = 20 x1 + 10 x2
5x1+4x2 24
2x1+5x2 13
x1 , x2 0 x1 , x2为整数 纯整数线性规划
一、数学模型及解的特点
例2、背包问题 背包可再装入8单位重量，10单位体积物品 物品 1 名称 书 重量 5 体积 2 价值 20
第五章
2
3 4 5
3、整数线性规划—若松弛问题是一个线性规划，则称该
整数规划为整数线性规划。
一、数学模型及解的特点
分类 纯整数规划 整数规划
…….
第五章
0 – 1 规划
混合整数规划
常用问题 ： 1．背包问题 2．指派问题 整数规划的常用解法： 1．分枝定界法 2．割平面法
一、数学模型及解的特点
第五章
解的特点 1 整数规划问题的可行解一定也是它的松弛问题的可 行解（反之则不一定）。前者最优解的目标函数值不会优 于后者最优解的目标函数值。 2 松弛问题的最优解的简单取整，不一定是最优解。