第二章2_整数规划1

数学模型电子教案重庆邮电大学数理学院虞继敏

第二章 规划论模型1.线性规划 2.整数规划 3.非线性规划 4.动态规划

第二节 整数规划1. 整数规划问题的提出

2 . 分枝定界法3. 0-1型整数规划

4. 指派问题

1. 整数规划问题的提出在求解线性规划问题时，得到的最优解可能是 分数或小数，但许多实际问题要求得到的解为整 数才行。这种要求线性规划有整数解的问题,称 为整数规划(Integer Programming)或简称IP。例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱 的体积、重量、可获利润以及装运所受限制如下： 货物集装箱 体积(米3) 重量(百斤) 利润(百元)

甲 乙 托运限制

5 4 24

2 513

20 10

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

设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2 都要求为整数,于是可建立整数规划模型如下： Max z=20x1+10x2 (1) 5x1+4x2≤24 (2) 2x1+5x2≤13 (3) x1,x2≥0 (4) x1,x2为整数 (5) 它和线性规划问题的区别在于条件(5)。

是不是可通过把不考虑整数要求求得的最优解经过“化整” 得到满足整数要求的最优解呢？

此例可解得x1=4.8,x2=0,凑整为x1=5,x2=0,这就 破坏了条件(2),因而不是可行解；如截断小数变为 x1=4,x2=0,这当然满足所有约束条件，但不是最优解， 因为对x1=4,x2=0有z=80,而对x1=4,x2=1(也是可行 解)有z=90。因此要专门研究整数规划的解法。

2. 分枝定界法分枝定界法是20世纪60年代由LandDoig和Dakin等人提出的。这种方法既可 用于纯整数规划问题，也可用于混合整数 规划问题，而且便于用计算机求解，所以 很快成为解整数规划的最主要的方法。 设有最大化的整数规划问题R,与它 相应的线性规划问题为R0 ,分枝定界法的 做法是：

(1)用观察法求R的一个可行解，其目标值便是R的最优目标 值z*的一个下界z。 (2)求解R0,得R0的最优解x(0)和最优值z0。若x(0)符合R的整 数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个 分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。 (3)分枝。取目标函数值最大的一个枝Rs,在Rs的解中任选 一不符合整数条件的变量xj,其值为bj,构造两个约束条件 xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs,得两 个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题， 以每个后继问题为一分枝标明求解的结果。 (4)定界。在各分枝中找出目标函数值最大者作为新的上界 z;从已符合整数要求的各分枝中，找出目标函数值最大者作为 新的下界z。 (5)比较与剪枝。各分枝的最优目标函数值中如果有小于z 者，则剪掉这一枝(用打×表示),即以后不再考虑了。若已

没 有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。

例 求解问题 Max z=40x1+90x2 9x1+7x2 ≤ 56 7x1+20x2≤70 x1,x2≥0, 整数 问题R1为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x1,x2≥0 x2 ≤2 x1 ≤4

问题R0为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0

R0: z0=356 x1=4.81 x2=1.82

x1≥5问题R2为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x1,x2 ≥ 0

R1:z1=349 x1=4.00 x2=2.10 x2≥3

R1:z1=349 x1=4.00 x2=2.10

问题R11为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x2 ≤2 x1,x2≥0

问题R12为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x2 ≥3 x1,x2 ≥ 0

R0: z0=356 x1=4.81 x2=1.82x1 ≤4 R1:z1=349 x1=4.00 x2=2.10 x2 ≤2 R11: z11=340 x1=4.00 x2=2.00 x2≥3 R12: z12=327 x1=1.42 x2=3.00 x1≥5 R2:z2=341 x1=5.00 x2=1.57 x1 ≤1 R21: z21=308 x1=5.44 x2=1.00 x1≥2 R22: 无可 行解

3. 0-1型整数规划0-1型整数规划是整数规划的一种特殊形式，它的 变量xj仅取值0或1。这种只能取0或1的变量称为0-1 变量或二进制变量。 例: 某公司拟在市东、西、南三区建立门市部。拟议 中有7个位置Ai(i=1,2, …,7)可供选择。规定：(1)在东 区A1、A2、A3三个点中至多选两个；(2)在西区A4、A5 两个点中至少选一个；(3)在南区A6、A7两个点中至少 选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估 计为ci元，但投资总额不超过B元。问应选择哪几个点 可使年利润为最大？

引入0-1变量xi (i=1,2,…,7), 令xi=1, 当Ai点被选用, xi= 0, 当Ai点没被选用。 (i=1,2,…,7)

Max z= c1x1+c2x2+…+c7x7 b1x1+b2x2+…+b7x7≤B

x1+x2+x3≤2x4+x5≥1 x6+x7≥1

于是建立下列模型:

xi=0或1, i=1,2,…,7

求解0-1型整数规划，可使用分枝定界法。下面 用实例说明： 例 求解0-1型整数规划问题 Max z=8x1+2x2-4x3-7x4-5x5 3x1+3x2+x3+2x4+3x5≤4 5x1+3x2-2x3-x4+ x5≤4 xj=0或1,j=1,2,…,5 变成标准型，要求如下：⑴目标函数求极大化。 对于目标函数为Min z的极小化问题，令z′=-z,使其 变为目标函数为Max z′的极大化问题。⑵目标函数中 所有变量的系数都为正数。如果目标函数中变量xj的 系数为负数，令xj′=1-xj,把模型中的xj用xj′代换。⑶ 变量的排列顺序按变量在目标函数中的系数值从小到 大排列。

过滤隐枚举法举例分析 例3: max z 3 x 2 x 5 x 1 2 3

s .t

1.找出一个可行解 X 0 ( x1 , x 2 , x 3 ) 1,0,0 求出其目标函数值

x1 2 x 2 x 3 2 x 4x x 4 1 2 3 x1 x 2 3 x i 0,1 ( i 1,2,3)

z( X 0 ) 32 3

2.由于该问题是求最大值，故目标值小于3的解可以不考虑， 增加约束条件 3 x 2 x 5 x 31,

此条件称为过滤条件。

3.对其它可行解利用过滤条件进行过滤，可以减少运算 次数。如果

得到一个新解的目标值优于过滤目标值，则 可以逐步改进过滤条件。如本题中能找到一个可行解

X 1 ( x1 , x 2 , x 3 ) 0,0,1 ,其目标值 z( X 1 ) 5 ,则过滤条件可改进为 3 x1 2 x 2 5 x 3 5 。 本题中的最优解为 X 2 ( x1 , x 2 , x 3 ) 1,0,1 , 其目标值z( X 2 ) 8 。

4. 指派问题例 有一份说明书，需译成 任务 英、日、德、俄四种文字。 E J G R 现有甲、乙、丙、丁四个人， 人员 甲 2 15 13 4 他们将说明书译成不同文字 乙 10 4 14 15 所需的时间如下表。问应指 丙 9 14 16 13 派哪个人完成哪项工作，使 丁 7 8 11 9 所需的总时间最少？ 一般地，有n项任务、n个完成人，第i人完成第j 项任务的代价为cij(i,j=1,2,…,n)。为了求得总 代价最小的指派方案，引入0-1型变量xij,并令 1 指派第i人去完成第j项任务 xij= 0 不指派第i人去完成第j项任务

数学模型为 Min z=∑∑cijxij ∑xij=1i=1n n

j=1,2,…,n i=1,2,…,n

∑xij=1j=1

xij=0或1

可见指派问题是0-1 型整数规划的特例。不 难发现，指派问题也是 运输问题的特例，其产 地和销地数都为n,各 产地的产量和各销地的 销量都为1。

指派问题的求解，最简便易行的方法是匈牙利法。

匈牙利法基于下面的效率矩阵： c11 c12 … c1n (cij)= c21 c22 … c2n ………………. cn1 cn2 … cnn