第七讲整数规划（一）.ppt

第七讲整数规划(一)
§1 概述
§2 割平面法
§3 分枝定界法
§1 概述(1)
一、定义
规划中的变量(部分或全部)限制为整数时,称为整数规
划。若在线性规划模型中,变量限制为整数,则称为整数
线性规划。
二、整数规划分类
如不加特殊说明,一般指整数线性规划。对于整数线性规
划模型大致可分为两类:
Ÿ   变量全限制为整数的,称纯(完全)整数规划。
Ÿ   变量部分限制为整数的,称混合整数规划。
§1 概述(2)
三、整数规划特点
整数规划标准形式(实际为整数线性规划)
AX=b,X≥0,CTX=min,xj为整数(j=1,…,n) (1)
,当自变量限制为整数后, 其整数规划解出现下述情况;
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
§1 概述(3)
[例2-1] 原线性规划为:
2x1+4x2=5,X≥0,CTX=x1+x2=min
其最优实数解为:x1=0,x2=5/4,min CTX =5/4。

③有可行解(当然就存在最优解),但最优解值变差。
[例2-2] 原线性规划为:
2x1+4x2=6,X≥0,CTX=x1+x2=min
其最优实数解为:x1=0,x2=3/2,min CTX =3/2。
若限制整数则得:x1=1,x2=1,min CTX =2。
§1 概述(4)
。
[例2-3] 物品装载问题:有若干类物品需一次性装运,每件物品的价值及重量分别,为vj和wj (j=1, …,n),车辆最大载重量为,试求,每件物品应装多少件才能使总价值最大。
[解] 令xj表示第j类物品的装载件数,则可列写整数规划如下:
xj≥0且取整(2)
§1 概述(5)
若不限制为整数,其最优解的基础分量xm为:
当j≠m,则xj=0
当限制为整数时,就需仔细计算(其方法将在后面阐述)。
例如,将例[2-3]具体化为:
51x1+50x2+50x3≤100
150x1+100x2+99x3=max
xj≥0
§1 概述(6)
若不限制整数,得出m=1,比率为150/51→max,故最优实数解为:x1=100/51,x2=x3=0,总价值15000/51=。
然而,物品不能切开,故限制为整数时,其最优解为:x1=0,x2=2,x3=0;总价值为200。
从该例得出结论,整数规划最优解不能简单的从最优实实数解中4舍5入取整所得。因此,对于整数规划的求解必须开拓新技术。
§1 概述(7)
四、求解方法分类:
1. 割平面法——主要求解纯整数线性规划
2. 分枝定界法——可求纯或混合整数线性规划
3. 隐枚举法——求解“01”整数规划:
①过滤隐枚举法;
②分枝隐枚举法
4. 匈牙利法——解决指派问题(“01”规划特殊情形)。
——求解各种类型规划。
§2 割平面法
该法适于求解纯整数规划问题。其基本思路是首先去掉整数约束去求解普通线性规划问题,若获得的最优解全为整数,结束;否则,以此最优非整数变量为基准,在原约束条件下,增加割约束,再继续求解,这样反复下去,直到结束为止。
§3 分枝定界法(1)
分枝定界法目前已成功地应用于求解整数规划问题、生产进度表问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。因此,分枝定界算法是求解整数规划的最有用的算法之一。现结合例题说是该算法的思路。
[例2-5]求解下述整数规划
目标函数 min z =x1+4x2
约束条件 2x1+x2≤8
x1+2x2≥6
x1,x2≥0且为整数