整数线性规划.pdfVIP

第三章整数线性规划

【教学内容】

整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整

数线性规划问题、求解整数线性规划问题的Gomory割平面法、求解整数线性规划问题的分

枝定界方法、0－1规划问题举例、0－1规划问题的解法、整数线性规划问题的一些例子、

用LINGO软件包求解整数线性规划问题。

【教学要求】

要求学生熟悉整数线性规划模型，能熟练地掌握求解整数线性规划问题的Gomory割平

面法和分枝定界方法；熟悉并会求解0－1规划问题，能够建立整数线性规划模型并用软件

求解整数线性规划问题。

【教学重点】

整数线性规划模型，Gomory割平面法，分枝定界方法，0－1规划问题。

【教学难点】

Gomory割平面法，分枝定界方法，0－1规划问题的求解。

【教材内容及教学过程】

整数线性规划(IntegerLinearProgramming，简记为ILP)问题研究的是要求变量取整数

值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要

分支。其中变量只取0或1的整数线性规划问题称为0－1规划。只要求部分变量取整数值

的线性规划称为混合整数线性规划。

整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应

的线性规划的最优解为出发点的。但是变量取整数值的要求本质上是一种非线性约束，因此

解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规

划问题。

本章主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。

第一节整数线性规划模型

§1．1整数线性规划问题举例

[2]l,l,,lb,b,,bl

例3.1.1工地上需要长度为12m的钢材数分别为12m根，取长为的

n

原材料进行截取。已知有种截取方案：

Aia1ia2iami，i1,2,,n

aili1,2,,n

其中，表示一根原料用第种方案可截得长为的钢材的根数（，

jij

-65-2018-11-4

j1,2,,m），因此

lalalal，i1,2,,n

11i22immi

下料问题就是在满足要求：截取长度为l,l,,l的钢材数分别为b,b,,b根时，

12m12m

用的原料材根数最少的方案。假定表示按方案截取用的原钢材数目，于是问题表示为：

xA

ii

minzxxx

12n

axaxaxb