运筹学4(整 数规划).ppt

运筹学
Operations Research
Model of IP
Branch and Bound Method
cutting-plane Method
4. 0-1规划 Binary Integer Programming
5. 指派问题 Assignment Problem
Chapter 5 整数规划
Integer Programming
【引例】某人有一背包可以装10公斤重、。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如下表所示。问两种物品各装多少件,所装物品的总价值最大?
物品
重量
(公斤/每件)
体积
(m3/每件)
价值
(元/每件)
甲
乙




4
3
【解】设甲、乙两种物品各装x1、x2件,则数学模型为:
一个规划问题中要求部分或全部决策变量是整数,则这个规划称为整数规划。当要求全部变量取整数值的,称为纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。如果模型是线性的,称为整数线性规划。本章只讨论整数线性规划。
整数规划的数学模型
很多实际规划问题都属于整数规划问题.
例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数
2. 对某一个项目要不要投资的决策问题,可选用一个逻辑变量 x,当x=1表示投资,x=0表示不投资;
3. 人员的合理安排问题,当变量xij=1表示安排第i人去做j工作,xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。
整数规划的数学模型
【 】某人有一背包可以装10公斤重、。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如表5-1所示。问两种物品各装多少件,所装物品的总价值最大?
物品
重量
(公斤/每件)
体积
(m3/每件)
价值
(元/每件)
甲
乙




4
3
【解】设甲、乙两种物品各装x1、x2件,则数学模型为:
猜想: 能否用前述的LP方法直接求解?
如果不考虑x1、x2取整数的约束(称为()的松弛问题):
图5-1
线性规划的可行域如图5—1中的阴影部分所示。
用图解法求得点B为松弛问题最优解:X=(,),Z=。
由于x1,x2必须取整数值,整数规划问题的可行解集只是图中可行域内的那些整数点。
用凑整法来解时需要比较四种组合,但(4,7)、(4,8)(3,8)都不是可行解,(3,7)虽属可行解,但代入目标函数得Z=33, 并非最优。
实际上问题的最优解是(5,5),Z=35。即两种物品各装5件,总价值35元。
由图5-1知,点(5,5)不是可行域的顶点,直接用图解法或单纯形法都无法求出整数规划问题的最优解,因此求解整数规划问题的最优解需要采用其它特殊方法。
还有些问题用线性规划数学模型无法描述,但可以通过设置逻辑变量建立起整数规划的数学模型。
结论: 猜想不成立!
【 】,假设此人还有一只旅行箱,最大载重量为12公斤,。所装物品不变,背包和旅行箱只能选择其一,建立数学模型,使所装物品价值最大。
解:此问题可以建立两个整数规划模型,但用一个模型描述更简单。
引入0-1变量(或称逻辑变量)yi,令
i=1, 2分别是采用背包及旅行箱装载。