文档介绍：运筹学
第4章整数规划与分配问题
第4章整数规划与分配问题
【学习内容】
一、整数线性规划问题的提出
二、整数规划问题的求解
1、分支定界解法
2、割平面解法
三、分配问题与匈牙利法
一、整数线性规划问题的提出
在前面讨论的线性规划问题中,有些最优解可能是分数或小数,但对于某些问题,常要求解必须是整数(称为整数解)。
(1)变量是人数、机器设备台数或产品件数等都要求是整数
(2) 对某一个项目要不要投资的决策问题,可选用一个逻辑变量 x,当x=1表示投资,x=0表示不投资;
(3)人员的合理安排问题,当变量xij=1表示安排第i人去做j工作,xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。
一、整数线性规划问题的提出
线性规划是运筹学的重要分枝,也是运筹学最基本的部分。整数规划是近三十年来发展起来的、规划论的一个重要的理论分支。根据对决策变量的要求不同,分为四种类型:
纯整数规划:所有决策变量均要求为离散的非负整数。
混合整数规划:部分决策变量要求为离散的非负整数。
01 整数规划:所有决策变量均要求为0或1。
混合 01 整数规划:部分决策变量要求为0或1。
一、整数线性规划问题的提出
引例:生产组织计划问题与选址问题
例4-1(生产组织计划问题)某工厂在一个计划期内拟生产甲、乙两种大型设备。除了A、B两种部件需要外部供应且供应受到严格限制之外,该厂有充分的能力来加工制造这两种设备所需的其余零件,并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表3-1-1给出。问该厂在本计划期内如何安排甲、乙设备的生产数量,才能获取最大利润?
一、整数线性规划问题的提出
部件
设备
A
B
利润
(百万)
甲
6
1
15
乙
4
3
20
部件的最大供应量
25
10
表 4-1-1
例4-1【解】
设 x1,x2 分别为该计划期内甲、乙设备的生产数量,Z 为生产这两种设备可获得的总利润。依题意,给问题的数学模型为:
max Z = 15x1 20x2
. 6x1 4x2 25
x1 3x2 10
xi {0, 1, 2, …}
这是一个纯整数规划问题。
一、整数线性规划问题的提出
引例:生产组织计划问题与选址问题
例4-2(选址问题)某商业连锁集团拟在 n 个连锁店所在城市中建立 m 个配货中心,每个城市最多建立一个配货中心。若在第 i 个城市建立配货中心,其配货能力为 Di,单位时间的固定成本为 ai,i = 1,…,n,第 j 个连锁店的需求量为 bj,j = 1,…,n。从第 i 个配货中心到第 j 个连锁店的单位运输成本为 cij。应如何选择配货中心位置和安排运输计划,才能得到经济上花费最少的方案。
例4-2【解】
设在单位时间内,从配货中心 i 运往连锁店 j 的物资数量为 xij,Z 为单位时间内的总费用。引入布尔变量
则上述问题可归结为如下的数学模型: