第4章 整数线性规划

第4章 整数规划与分配问题整数规划是数学规划的一个重要分支, 可分为: 纯整数 规划(所有变量都限制为整数)、混合整数规划(一部分变量 限制为整数)、0-1规划(所有变量都限制取0或1). 本章讨论纯整数线性规划(ILP)及解此规划的割平面法 和分枝定界法；分配问题与匈牙利算法.

4.1 整数规划的特点及作用 4.2 分配问题与匈牙利算法 4.3 分枝定界法 4.4 割平面法

第1页

§4.1 整数规划的特点及作用

4.1.1 整数规划的模型分类 纯整数规划模型 0-1整数规划模型 混合整数规划模型 4.1.2 实例 投资决策问题 背包问题 4.1.3 解整数线性规划的困难性 4.1.4 逻辑变量在建模中的作用

第2页

4.1.1 整数规划的模型分类 纯整数规划模型 0-1整数规划模型

max c x Ax b s . t . x 0, x为 整 数

max c x Ax b s . t . x i 0或1; i 1,2,..., n

混合整数规划模型max c x Ax b s .t . x 0, i 1,2,..., n x 为整数, i 1,2,..., p i第3页

4.1.2 实例 (1)投资组合问题 1.问题 某财团有B万元的资金, 经出其考察选中n个投资项目, 每个项目只能投资一个. 其中第j 个项目需投资金额为bj万元, 预计 5年后获利cj万元, 问应如何选择项目使得5年后总收益最大？

2.分析

变量

j 0, 不 投 资 第 个 项 目 xj , j 1,2, , n , j 1 投 资 第个 项 目

约束—总金额不超过限制 目标 —总收益最大 略

bj 1

n

j

xj B

max

cj 1

n

j

xj

3. 数学模型

第4页

(2)背包问题 1.背景

邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品

2.问题 某人出国留学打点行李, 现有三个旅行包, 容积大小分别为

1000毫升、1500毫升和2000毫升, 根据需要列出需带物品清单, 其 中一些物品是必带物品共有7件, 其体积大小分别为400、300、150、 250、450、760、190、(单位毫升). 尚有10件可带可不带物品, 如 果不带将在目的地购买, 通过网络查询可以得知其在目的地的价 格(单位美元). 这些物品的容量及价格分别见下表, 试给出一个合 理的安排方案把物品放在三个旅行包里.物品 价格 1 15 2 45 3 4 5 6 7 8 9 10

体积 200 350

500100

43070

32050

12075

700200

42090

25020

10030第5页

3.问题分析

变量—对每个物品要确定是否带同时要确定放在哪个包裹里，设变量xij为第i个物品是否放在第j个包裹中xij 1,0; i 1,2...,17, j 1,2,3

约束 包裹容量限制

目标函数未带物品购买费用最小

c xi 1 i3

17

ij

r j ; j 1,2,3

必带物品限制

xij 1; i 1,2..., 7j 1

p (1 xi i 8 j

1

17

3

ij

)

选带物品限制

xj 1

3

ij

1; i 8,9,...,17第6页

模 型

min

p (1 xi i 817

17

3

ij

)

j 1

c xi

ij

r j ; j 1,2,3

xj 13

i 1 3

ij

1; i 1,2...,7 1; i 8,2...,17

xj 1

ij

xij 1,0; i 1,2...,17, j 1,2,3

第7页

4.1.3 解整数线性规划的困难性

特征—变量整数性要求 来源—问题本身的要求; 引入的逻辑变量的需要 性质—可行域是离散集合

与线性规划的关系：整数规划 松弛的线性规划问题

min z c x Ax b s . t . x 0, x为 整 数

min z c x Ax b s . t . x 0

可行解是松弛问题的可行解 最优值大于等于松弛问题的最优值第8页

结论

最优解不一定在顶点上达到. 最优解不一定是松弛问题最优解的邻近整数解. 整数可行解远多于松弛问题的顶点,枚举法不可取. 解ILP问题要远难于解松弛的LP问题. 若松弛的LP问题无解,则原ILP问题无解.反之,不一定成立. 如果松弛的LP问题无界呢? 可以证明原ILP问题也无界.

第9页

4.1.4 逻辑变量在建模中的作用1. m个约束条件中只有k个起作用 m个约束条件可表为

aj 1

n

ij

x j bi , i 1,2, , m

1, 假 定第i个 约束 条件 不起 作用 , i 1,2, , m 定义 yi i 0, 假 定第 个 约束 条件 起作 用

又M为任意大的正数，则

n a ij x j bi Myi , i 1,2, , m j 1 y1 y2 ym m k

第10页

2. 约束条件的右端项可能是r个值(b1,b2,…,br)中的某一个, 即

aj 1

n

ij

x j b1或b2或 或br

( )

定义

b 1, 假定约束右端项为k yk , k 1,2, , r 0,否则

上述约束条件(*)可表示为r n a ij x j bk yk , j 1 k 1 y y y 1 2 r 1

第11页

3. 两组条件中满足其中一组若x1 4, 则x2 1; 否则(即x1 4时), x2 3 1, 第i组条件不起作用 ( i 1,2) 定义 yi 0,第i组条件起作用

又M为任意大的正数，则问题可表述为

x1 4 y1 M x 1 y M 1 2 x1 4 y 2 M x2 3 y2 M y1 y 2 1

第12页

4. 用以表示含有固定费用的函数用x j 表示产品 j 的生产数量，其生产费 用函数通常表示为：

K j c j x j ( x j 0), C j(xj ) ( x j 0), 0即 min z C j ( x j )j 1 n

(1)

生产费用最小， 其中K j 是同产量无关的生产准 , 目标是使所有产品的总 备费

( 2)

为了表达 1)、 )两式，需设置一个逻辑 ( (2 变量

为此引入一个特殊的约 束条件：

1, 当x j 0 yi 0, 当x j 0

x j My jmin z (c j x j K j y j )j 1 n

( 3)

在( 3)式中显然当 j 0时，y j 1, 若将( 2)、 )式表达为 x (3

0 x j My j s .t . ( 4) y j 0或1 由(4)看出当x j 0时，为使 极小化，应有 j 0. z y

第13页

§4.2 分配问题与匈牙利算法

4.2.1 分配问题的数学模型 4.2.2 匈牙利算法

第14页

4.2.1 分配问题的数学模型分配问题(指派问题) 假定有m项任务分配给m个人去完成, 并指定每人完成其中一项, 每项只交给其中一个人去完成, 应如何分配使总的效率最高.

举例有一份说明书, 要分别译成英、 日、德、俄四种文字, 交甲乙丙丁四 个人去完成. 因各人专长不同, 他们 完成翻译不同文字所需的时间如表 所示. 应如何分配, 使这四人分别完 成 这四项任务总的时间最小.人 甲 乙 丙 丁

效率矩阵工 作 译成英文 译成 日文 译成 德文 译城 俄文

2 15 13

10 4 14

9 14 16

7 8 11

4

15

13

9

效率矩阵： 利用不同资源完成不同计划活动的效率通常用表 格形式表示，表格中的数字组成效率矩阵.第15页

分配问题的数学模型:

min z a ij x iji 1 j 1

m

m

人

工作x1j xi …… 此处隐藏：2920字，全部文档内容请下载后查看。喜欢就下载吧 ……