文档介绍：运筹帷幄之中
决胜千里之外
运筹学课件
整数规划
第五章
Dynamic Programming
第一节整数规划数学模型及解的特点
一、线性规划的数学模型的表示
max(min) z =
xj ≥ 0 (j=1,2, ……,n)
st.
cjxj
aijxj ≤(或=,≥) bi (i=1,2, ……,m)
线性规划问题的特征:
(1)目标函数是决策变量的线性函数
(2)约束条件是含决策变量的线性等式或不等式
第一节整数规划数学模型及解的特点
二、整数规划的数学模型的表示
max(min) z =
xj ≥ 0,xj部分或全部取整数(j=1,2, ……,n)
st.
cjxj
aijxj ≤(或=,≥) bi (i=1,2, ……,m)
整数规划的矩阵表示:
整数规划的松弛问题:
整数规划与其松弛问题最优解和最优值的关系
整数规划的可行解一定是其松弛问题的可行解。
整数规划的最优值不优于其松弛问题的最优值。
三、整数规划数学模型举例
解设:xi 为服务员在 i 时段开始上班人数
min z= x1 + x2 + x3 + x4 + x5+ x6 + x7 + x8
约束条件
x1≥10
st .
例1
时段(2h)
1
2
3
4
5
6
7
8
服务员最少数目
10
8
9
11
13
8
5
3
要求:服务员要连续工作4个时段目标:人数最少
目标
x1 + x2 ≥8
x1 + x2 + x3 ≥9
x1 + x2 + x3 + x4 ≥11
x2 + x3 + x4 + x5 ≥13
x4 + x5 ≥5
x3 + x4 + x5 ≥8
x5 ≥3
且xj为整数
xj≥0
(j=1,2,3,4,5)
例2、例3见书P124,125
例1
时段(2h)
1
2
3
4
5
6
7
8
服务员最少数目
10
8
9
11
13
8
5
3
要求:服务员要连续工作4个时段目标:人数最少
四、整数线性规划的数学模型及解的特点
max(min) z =
xj ≥ 0 且取整数(j=1,2, ……,n)
st.
cjxj
aijxj ≤(或=,≥) bi (i=1,2, ……,m)
整数线性规划问题与一般线性规划最大区别是:
(1) 整数规划中决策变量必须为整数
(2) 设两组可行解X1、X2,(aX1+bX2)不一定是整数规划的解
(其中,a,b>0 且 a+b=1)
(3) 一般线性问题的可行域为一个凸集,而整数规划的可行域
是一些离散点
取整数
全部决策变量都取整数时称全(纯)整数规划
部分决策变量取整数时称混合整数规划
决策变量只能取0或1时称0-1型整数规划
五、整数线性规划的求解方法
max z= x1 + 4x2
例2
-2x1 + 3x2 ≤ 3
x1 + 2x2 ≤ 8
x1 ,x2 ≥ 0 且取整数
St.
x1=18/7 x2=19/7 Z=94/7
x1=3 x2=3 Z=15
x1=2 x2=3 Z=14
x1=2 x2=2 Z=10
x1=3 x2=2 Z=11
X1*=4 x2*=2 Z*=12
一种最简单的方法:枚举法
这种思路为:找出所有整数可行解,并分别算出其目标值,通过比较求得问题
的最优解
第二节整数规划的割平面法
红色区域与原区域区别:
这种方法的思路:
把原区域割去不含原问题可行解的那部分区域,从而可以求得原问题的最优解。
我们称这种思路为割平面法
第一步:先不考虑整数约束,利用单纯形法进行求解
割平面法——如何割?
1958年,高莫瑞提出一种每次增加一个约束——割平面
约束,来割除一些多余的可行域。
Cj
1 4 0 0
CB
基
b
x1 x2 x3 x4
0 0
x3 x4
3
8
-2 3 1 0
1 2 0 1
δ
1 4 0 0
……………….
4
1
x2
x1
19/7
18/7
0 1 1/7 2/7
1 0 -2/7 3/7
δ
0 0 -2/7 -11/7
第二节整数规划的割平面法