第8章 整数线性规划

管理运筹学 西北大学 经济管理学院 茹老师课件

运 筹 学西北大学经济管理学院 茹少峰 rsf00@

管理运筹学 西北大学 经济管理学院 茹老师课件

第8章整数线性规划

本章要求理解整数规划的含义；掌握两个变量的纯整数线性规划模型的图解法；掌握分枝定界 法的思想和方法；了解割平面法的原理；能够正 确引入0—1变量建立0-1线性规划模型；掌握指派 问题的求解算法；正确使用计算机软件求解整数 规划问题。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出在前面讨论的线性规划问题中，最优解可能是分数或小数，但对于某些 具体问题常要求最优解是整数。我们称这样的线性规划问题为整数线性规划 问题(Integer Linear Programming 简记为 ILP) 。 在整数规划中如果所有的变量都限制为整数，就称为纯整数规划(Pure ILP),如果仅一部分变量限制为整数，就称为混合整数规划(Mixed ILP), 整数规划的一个特例就是 0—1 规划，它的变量仅取 0 或 1。 例 8-1 投资决策问题 某部门在今后五年中可用于投资的资金总额为 B 万元，有 n ( n 2)个可 以投资的项目，假定每个项目最多投资一次，第 j ( j n )个项目所需投资 资金为 b j 万元，获得的利润为 c j 万元，问如何选择投资项目，才能使获得的 总利润最大。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出解 设投资决策变量为 1 xj 0投资第j个项目 不投资第j个项目

j 1,2, , n

设获得的总利润为 z ,则上述问题的数学模型为

max z c j x jj 1

n

b x B st. j j j 1 x j 0或1 n

(8.1)

该问题是决策变量只能取 0 或 1 的整数规划问题。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出例 8-2 某厂拟用集装箱托运甲、乙两种货物，货物的体积、重量、可获 得的利润及托运所受的限制如表 8-1 所示。表 8-1 货物的体积、重量、可获得的利润及托运所受限制表 体 货 物 积 重 量 利 润

3 每箱(米 ) 每箱(百公斤)

每箱(百元)

甲 乙 托运限制

5 4 24

2 5 13

20 10

两种货物各托运多少箱，可使得利润最大？

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出解 设 x1 , x 2 分别为甲、乙两种货物的托运箱数，设获得的总利润为 z,

则上述问题的数学模型为

max z 20 x 1 10 x 2 5x 1 4 x 2 24 st. 2 x 1 5x 2 13 x , x 0且为整数 1 2这是纯整数规划问题。 (8.2)

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出例 8-3 旅行售货员问题。有一推销员，从城市 v 0 出发，要遍访城市

v1 , v 2 , , v n 各一次，最后返回 v 0 ,已知从 v i 到 v j 的旅费为 c ij ,问他应按怎样的次序访问这些城市，才能使得总旅费最少？ 解 对每一对城市设一个变量 x ij ,令

1, 从v 直接进入v j j xij 0, 其他情况

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出则上述问题的数学模型

为：

min z

i , j 0

cij xij

n

n xij 1, j 0, 1, , n i n0 x 1, i 0, 1, , n ij st. j 0 u i u j nxij n 1, 1 i j n x 0 或 1, i, j 0, 1, , n ij u i 为连续变量, i 1, 2, , n

(8.3)

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出对于目标函数的极小而言， cii M( M 为充分大正数) 迫使 xii 0 , 令 ，

i 0,1, , n 。第一组约束条件表示各城市恰好进入一次；第二组约束条件表示各城市恰好离开一次； 第三组约束条件用以防止出现多于一个互不连通的旅 行路线图，且不排除任何可能的旅行路线。例如，对于六个城市 (n 5) 的货 郎担问题， 若令： x01 x12 x20 1 , x34 x45 x53 1 ,其它 xij 0

管理运筹学 西北大学 经济管理学院 茹老师课件

8.1 整数线性规划问题的提出v0 v5v2 v1 v4图 8-1 售货员旅行路线图示

v3

如图 8-1 中所示的两个互不连通的旅行路线图， 这样一组 x ij 满足第一、 二 组约束条件，但不满足第三组约束条件，因为其中的三个不等式为：

u3 u 4 5 4 u 4 u5 5 4 u5 u3 5 4这三个不等式相加，不论 u 3 ,u 4 ,u 5 取任何实数值均导致 5 4 的矛盾，第 三组约束所起的这个作用是可以严格证明。根据定义，旅行售货员问题是一个 混合整数线性规划问题。有许多实际应用问题的数学模型都是(8.3)的形式， 如生产顺序表问题、集成电路的布线问题等。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.2 整数规划的图解法关于两个变量的纯整数规划问题，可以用图解法进行求解，求解的方法和 线性规划的图解方法基本上相同，只是在平移目标函数等值线时有所不同。 定义 1 一个纯整数线性规划问题，去掉整数限制以后的线性规划，就称 为该纯整数线性规划问题相应的线性规划问题。 例 8-4

max z 4 x1 x 2 2 x1 2 3 1 x2 3 st. 2 3 x x 10 1 2 x1 , x 2 0, 且为整数

(8.4)

管理运筹学 西北大学 经济管理学院 茹老师课件

8.2 整数规划的图解法用图解法求解方法如下： 首先用图解法求解相应线性规划模型的最优解，求得最优解为：

A(2 2 ,2) ,最优值为 12 2 ;因最优解中含有分数，不符合整数要求，因此将 3 3目标函数线向左下方平移， 相交的第一个整数点就是符合约束条件的整数最优 解。对于本题平移目标函数线得最优解为 B(2,3) ,最优值为 11。

x243

B 2,3

2 1

2 A(2 ,2) 33

1

2

x1

图 8-2 例 8-4 图解法

管理运筹学 西北大学 经济管理学院 茹老师课件

8.2 整数规划的图解法从此题可以看到，整数线性规划有如下特点： 1.任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数 值小于等于相应的线性规划的最大目标函数值； 任何最小目标函数值的纯整数 规划或混合整数

规划的最小目标函数值大于等于相应的线性规划的最小目标 函数值。 2.相应的线性规划可行域有界时，整数可行解为有限个。

管理运筹学 西北大学 经济管理学院 茹老师课件

8.3 整数线性规划问题的求解——割平面法1. 基本思想 给出整数规划min z min CX

(P)

AX b st. X 0 x 整数( j 1,2, ,n) j

(8.5)

可先求其相应的线性规划问题

min z min CX

( P0 )

AX b st. X 0

(8.6)

管理运筹学 西北大学 经济管理学院 茹老师课件

8.3 整数线性规划问题的求解——割平面法如果 ( P0 ) 中的最优解满足 (P) 中的整数要求，则已求得 (P) 的整数最优 解。如果 ( P0 ) 的最优解的分量不全是整数，就对 ( P0 ) 增加一个约束条 …… 此处隐藏：3309字，全部文档内容请下载后查看。喜欢就下载吧 ……