文档介绍：《工程运筹学》教学案卷
对象:交通运输、农业工程、环境工程
dae_meng
第6章
整数规划
dae_meng
6 整数规划
讲课4学时,实验2学时
6-1 整数规划数学模型
6-2 分枝定界法
6-3 “0—1型”整数规划的解法
6-4 指派问题
为本章重点内容
6-1 整数规划数学模型
前面讨论了线性规划问题,其基变量的最优解可以是整数,也可以是分数或小数。
实际生产中,很多问题的最优解必须是整数才有实际意义。
比如,农机配备模型中,农业机械及拖拉机的台数;
列车、飞机编组中的列数与架数;再如果树栽培的株数、劳动力分派的人数等等。
只允许变量取整数最优解的线性规划称为整数规划
英文 Integer Programming,简称IP为整数规划问题。
整数规划是近三十年来发展起来的规划论中的一个分支。
6-1 整数规划数学模型
我们能不能把线性规划的非整数规划最优解经过“舍入化整”就行了呢?
例1:某农场拟用甲、乙两种拖拉机运输农产品,每种拖拉机的耗油量和装卸、驾驶等用工时、油量、工人数限制量及利润见表,问两种拖拉机各用几台,才可获利最大?
显然这是一个关于拖拉机配备的整数问题
6-1 整数规划数学模型
拖拉机
用工数(人)
耗油量(公斤)
利润(百元)
甲
5
2
20
乙
4
5
10
限制量
24
13
我们首先设 x1 ,x2 分别为使用甲、乙两种拖拉机的台数,则其数学模型为:
6-1 整数规划数学模型
最后的约束条件(5)
这个模型和(LP)模型的区别仅在于?
现在不考虑(5),解(1)--(4)
显然不是整数,不符合要求。假如我们“舍入化整”
代入方程(2),就破坏了人数约数。
(以后我们称这样的问题为原问题相应的LP问题)
利用单纯形法很容易就可解得:
就满足约束条件,因而是可行解
但不是最优解
6-1 整数规划数学模型
那么如何求解整数规划问题呢?
我们首先想到的办法是穷举变量的所有可行的整数组合,再比较各组合的目标函数值,从中定出最优解。
对于简单的问题来说,上述方法是可行的,
对于复杂的大问题,显然穷举法是不合适的。
常用的整数规划解法有分枝定界法、割平面法。
解0-1整数规划还有隐枚举法、指派匈牙利法等。
下面介绍分枝定界法
6-2 分枝定界法(Branch and Bound Method)
由于整数规划是在相应的线性规划问题的基础上,增加了变量为整数的约束条件。
所以其可行域就会缩小,其最优解也就不会优越于相应的线性规划问题的最优解。
对于求极大值问题来说,相应的线性规划目标函数值就成为其整数规划目标函数值得上界。
6-2 分枝定界法(Branch and Bound Method)
分枝定界法就是利用该性质来求解的一种方法
设最大化的整数规划问题A,与它相对应的线性规划问题为B。
先解问题B,若其最优解不符合A的整数条件,那么B的最优目标函数必是A的最优目标函数 Z*
的上界,记作 ZB
A任意可行解目标函数值将是 Z*的一个下界 ZA 。