文档介绍：运筹学
讲授:毕德春
辽东学院信息技术学院信息管理系
11/11/2017
1
第4章整数规划与分配问题
11/11/2017
2
某服务部门各时段(每2小时为一时段)需要的服务员人数如下表,按规定,服务员连续工作8小时(即4个时段)为一班,现要求安排服务员的工作时间,使服务部门服务员总数最小。
时段
1
2
3
4
5
6
7
8
服务员最少数目
10
8
9
11
13
8
5
3
整数规划问题的数学模型
11/11/2017
3
解:设在第j时段开始时上班的服务员人数为xj,由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班,故决策变量只需考虑x1,x2,x3,x4,x5,此问题的数学模型为:
11/11/2017
4
此类问题数学模型的一般形式为:求一组变量X1,X2,…,Xn,使
11/11/2017
5
某单位有5个拟选择的投资项目,其所需投资额与期望收益如下表。由于各项目之间有一定联系,A、C、E之间必须选择一项且仅需选择一项;B和D之间需选择也仅需选择一项;又由于C和D两项目密切相关,C的实施必须以D的实施为前提条件,该单位共筹集资金15万元,问应该选择哪些项目投资,使期望收益最大?
项目
所需投资额(万元)
期望收益(万元)
A
6
10
B
4
8
C
2
7
D
4
6
E
5
9
11/11/2017
6
解:决策变量:设
目标函数:期望收益最大
约束条件:投资额限制条件 6x1+4x2+2x3+4x4+5x515
项目A、C、E之间必须且只需选择一项:x1+x3+x5=1
项目C的实施要以项目D的实施为前提条件: x3 x4
项目B、D之间必须且只需选择一项:x2+x4=1
归纳起来,其数学模型为:
11/11/2017
7
上面此例表明,利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为:求一组决策变量X1,X2,…,Xn,使
11/11/2017
8
根据变量取整数的情况,将整数规划分为:
(1)纯整数规划,所有变量都取整数.
(2)混合整数规划,一部分变量取整数,一部分变量取实数
(3)0-1整数规划,所有变量均取0或1
对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多经济管理的实际问题中,决策变量只有非负整数才有实际意义。对求整数最优解的问题,称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。
11/11/2017
9
考虑纯整数问题:
整数问题的松弛问题:
11/11/2017
10