运筹学目标规划与整数规划.ppt

1
3
2
X
2
5
4
X
1
2
3
1
S2
对S1分枝：
构造约束：
和
形成分枝问题S11和S12，得解D
S12
S11无可行解
S
A:
x1=3/2,x2=10/3
Z=29/61
3
2
X
2
5
4
X
1
2
3
1
S2
对S1分枝：
构造约束：
和
形成分枝问题S11和S12，得解D
S12
S11无可行解
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11
无可行解
S12
D:
x1=33/14,x2=2
Z=61/14
1
3
2
X
2
5
4
X
1
2
3
1
S2
对S12分枝：
构造约束：
和
形成分枝问题S121和S122，得解E和F
S121
S122
S
A:
x1=3/2,x2=10/3
Z=29/6
S2
C:
x1=1,x2=7/3
Z=10/3
S1
B:
x1=2,x2=23/9
Z=41/9
S11
无可行解
S12
D:
x1=33/14,x2=2
Z=61/14
S122
F:
x1=2,x2=2
Z=4
S121
E:
x1=3,x2=1
Z=4
0-1整数规划
变量只能取0或1的整数线性规划
0-1规划的应用-项目投资预算
模型
变量假设:
模型:
0-1规划的应用-工厂-销售点配置问题
生产厂
顾客需求
销售点
4
5
D
C
B
A
7
II
III
2
1
3
I
工厂-销售点配置问题-问题描述
问题: 为使经营成本最低,应开设那些工厂及销售点?
工厂-销售点配置问题-模型参数
工厂-销售点配置问题-模型
0-1规划的求解—隐枚举方法
最优解（x1,x2,x3)=(1,0,1); z=8
隐枚举方法求解过程
经典指派问题
n个员工分配作n项工作，一致的i个员工作的j项工作的成本为cij，i=1,…,n; j=1,…,n。求最佳分配方案。
指派问题的数学模型
.
指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小
例
cij
指派问题的性质
定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解
指派问题的求解-匈牙利方法
成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0。如果划去这些0所需要的直线数不少于n，则此时就可以求得最优解。
例题求解
一般指派问题
最大化指派问题
人数和工作数不等的指派问题
一个人可做几项工作的指派问题
某项工作一定不能由某人做的指派问题
最大化指派问题
最大化指派问题
最大值
最小化指派问题
人数和工作数不等的指派问题
一个人可做几项工作的指派问题
A1可同时做三项工作
某项工作一定不能由某人做的指派问题
A1不能做B4;
A3不能做B3
再见