(Integer Programming)

Presentation on theme: "(Integer Programming)"— Presentation transcript:

1 (Integer Programming)
整 数 规 划 (Integer Programming) 整数规划的模型 分支定界法 0－1 整数规划 指派问题

2 一、整数规划的模型 （一）、整数规划问题实例 例一、合理下料问题
设某型号圆钢可生产零件毛坯为A1, A2,…,Am 。在一根圆钢上下料的方式有B1,B2, …,Bn 种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？ 零件 方 个数 式 零件 零 件 毛坯数 用B1方法下料，能得到的零件数A1是a11个，。。。，Am是am1个

3 设：xj 表示用Bj (j=1.2…n) 种方式下料根数
模型： 例二、某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am ，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi (i=1.2…m),又有n个地点B1,B2, … Bn 需要销售这种产品，其销量分别为b1.b2…bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？

4 单 销地 厂址 价 生产 能力 建设 费用 销量

5 设： xij 表示从工厂运往销地的运量(i=1.2…m、j=1.2…n), 1 在Ai建厂
又设 Yi＝ （i=1.2…m） 0 不在Ai建厂 模型：

6 （二）、整数规划的数学模型 一般形式 依照决策变量取整要求的不同，整数规划可分为纯整数线性规划、混合整数线性规划、0－1整数线性规划。

7 纯整数线性规划：所有决策变量要求取非负整数。
混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。 0－1整数规划：所有决策变量只能取 0 或 1 两个整数。

8 （三）、整数规划与线性规划的关系 举例说明。
从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。 举例说明。

9 例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。

10 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。
用 解法求出最优解 x1＝3/2, x2 = 10/3 且有Z = 29/6 图 x2 ⑴ ⑵ (3/2,10/3) 3 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。 x1 3 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。

11 如上例：其中（2，2）（3，1）点为最大值，Z=4。
因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（2，2）（3，1）点为最大值，Z=4。 目前，常用的求解整数规划的方法有： 割平面法和分支定界法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。

12 二、分支定界法 （一）、基本思路 考虑纯整数问题： 整数问题的松弛问题：

13 1、先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一：
⑴.若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ⑵.若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ⑶.若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。为讨论方便，设( LP )的最优解为：

14 2、定界： 记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上界，记为 ＝ Z(0) 。再用观察法找的一个整数可行解 X′，并以其相应的目标函数值 Z′作为Z* 的下界，记为Z＝ Z′，也可以令Z＝－∞，则有： Z ≤ Z* ≤ 3、分枝： 在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr= （不为整数），以 表示不超过 的最大整数。构造两个约束条件 xr≤ 和xr≥ ＋1

15 ⑴.在各分枝问题中，找出目标函数值最大者作为新的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。
将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题( LP1)和( LP2) 。 4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为新的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。 5、比较与剪枝 ： 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。 如此反复进行，直到得到Z＝Z*＝ 为止，即得最优解 X* 。

16 （二）、例题 例一：用分枝定界法求解整数规划问题（用图解法计算） 记为（IP） 解：首先去掉整数约束，变成一般线性规划问题 记为（LP）

17 先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2
⑵ 用图解法求（LP）的最优解，如图所示。 x2 ⑴ (18/11,40/11) x1＝18/11, x2 =40/11 Z(0) =－218/11≈(－19.8) 即Z 也是（IP）最小值的下限。 3 ⑶ x1 对于x1＝18/11≈1.64， 取值x1 ≤1， x1 ≥2 对于x2 =40/11 ≈3.64，取值x2 ≤3 ，x2 ≥4 先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2 3

18 有下式： 现在只要求出（LP1）和（LP2）的最优解即可。

19 Z(2) ＝－56/3≈－18.7 ∵Z2 < Z1＝－16 ∴原问题有比（－16）更小的最优解，但 x2 不是整数，故利用
先求（LP1）,如图所示。此时B 在点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此枝停止计算。 ⑵ x2 ⑴ A (18/11,40/11) B C 3 ⑶ 同理求（LP2） ,如图所示。 在C 点取得最优解。 即x1＝2, x2 =10/3, Z(2) ＝－56/3≈－ ∵Z2 < Z1＝－16 ∴原问题有比（－16）更小的最优解，但 x2 不是整数，故利用 x2≤3, x2≥4 加入条件。 1 x1 1 3

20 加入条件： x2≤3, x2≥4 有下式： 只要求出（LP3）和（LP4）的最优解即可。

21 先求（LP3）,如图所示。此时D 在点取得最优解。 即 x1＝12/5≈2.4, x2 =3,
⑵ x2 ⑴ 先求（LP3）,如图所示。此时D 在点取得最优解。 即 x1＝12/5≈2.4, x2 =3, Z(3)＝-87/5≈-17.4<Z≈-19.8 但x1＝12/5不是整数，可继续分枝。即 3≤x1或x1 ≤ 2。 A (18/11,40/11) B C D 3 ⑶ 1 x1 1 3 求（LP4），如图所示。 无可行解，不再分枝。

22 在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式：
只要求出（LP5）和（LP6）的最优解即可。

23 先求（LP5）,如图所示。此时E 在点取得最优解。 即 x1＝2, x2 =3, Z(5)＝－17 找到整数解，问题已探明，此枝停止计算。
⑵ 先求（LP5）,如图所示。此时E 在点取得最优解。 即 x1＝2, x2 =3, Z(5)＝－17 找到整数解，问题已探明，此枝停止计算。 x2 ⑴ A (18/11,40/11) B C D 3 E F ⑶ 1 求（LP6），如图所示。此时 F在点取得最优解。 x1＝3, x2 =2.5, Z(6)＝－31/2≈－15.5 > Z(5) x1 1 3 如对 Z(6) 继续分解，其最小值也不会低于－15.5 ，问题探明,剪枝。

24 x2 =3, Z* = Z(5) ＝－17 至此，原问题（IP）的最优解为： x1=2， 以上的求解过程可以用一个树形图表示如右： LP
x1=18/11, x2=40/11 Z(0) ＝－19.8 至此，原问题（IP）的最优解为： x1=2， x2 =3, Z* = Z(5) ＝－17 以上的求解过程可以用一个树形图表示如右： x1≤1 x1≥2 LP1 x1=1, x2=3 Z(1) ＝－16 LP2 x1=2, x2=10/3 Z(2) ＝－18.5 ＃ x2≤3 x2≥4 LP3 x1=12/5, x2=3 Z(3) ＝－17.4 LP4 无可 行解 x1≤2 x1≥3 ＃ LP5 x1=2, x2=3 Z(5) ＝－17 LP6 x1=3, x2=5/2 Z(6) ＝－15.5 ＃ ＃

25 三、0－1 整数规划 0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。
例一、求解下列0－1 规划问题

26 解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。 x1 . x2. x3 约束条件 满足条件 Z 值 (1) (2) (3) (4) 是∨ 否× ( ) ∨ ( ) － 5 ( ) －2 ( ) 3 ( ) × ( ) 8 ( ) ( )

27 由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 )
由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。 x1 . x2. x3 约束条件 满足条件 Z 值 (0) (1) (2) (3) (4) 是∨ 否× ( ) ∨ ( ) － 5 ( ) -2 × ( ) 3 ( ) ( ) 8 ( ) 1 ( ) 4

28 例二、求解下列0－1 规划问题 解：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换： 令 x1 ＝1－ x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中，但需重新调整变量编号。令 x3′ = x1′, x4′ = x2′得到下式。

29 可以从( 1.1.1.1 )开始试算， x′(3)＝( 1.1.0.1 )最优解。
∴ x(3)＝( )是原问题的最优解，Z* =－2

30 例三、求解下列0－1 规划问题 令 y1=x5, y2=x4, y3=x2, y4=x3, y5=x1 得到下式

31 y1 . y2. y3 . y4. y5 Z 值 所以， Y*= （0.0.0.1.0），原问题的最优解为：
约束条件 满足条件 Z 值 (1) (2) 是 ∨否× ( ) × ( ) ( ) ( ) ( ) ∨ 8 ( ) 所以， Y*= （ ），原问题的最优解为： X* ＝（ ），Z* =8

32 练习：用隐枚举法求解0—1规划问题 （ ）

33 四、指派问题 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 （一）、指派问题的数学模型 设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？

34 设决策变量 分配第i 个人去做第j 件工作 xij = 相反 ( I,j=1.2. …n ) 其数学模型为：

35 （二）、解题步骤： 指派问题是0-1 规划的特例，当然可用整数规划，0-1 规划的解法去求解，但是利用指派问题的特点可有更简便的解法，这就是匈牙利法。 第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。

36 第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。

37 (4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若◎ 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m < n, 则转入下一步。 第三步：作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号； (2)对已打√号的行中所有含Ø元素的列打√号； (3)再对打有√号的列中含◎ 元素的行打√号；

38 (4)重复(2)，(3)直到得不出新的打√号的行、列为止；
(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 l＝m < n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。

39 例一： 任务 人员 A B C D 甲 2 15 13 4 乙 10 14 丙 9 16 丁 7 8 11

40 2 4 9 7

41 4 2

42 Ø ◎ ◎ ◎ Ø ◎ Ø

43 第四步：变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。

44 例二、 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 丁

45 求解过程如下： 第一步，变换系数矩阵： 第二步，试指派： －5 ◎ ◎ Ø ◎ 找到 3 个独立零元素 但 m = 3 < n = 4

46 独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；
第三步，作最少的直线覆盖所有0元素： ◎ √ ◎ Ø ◎ √ Ø √ 独立零元素的个数m等于最少直线数l，即l＝m=3<n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：

47 ◎ Ø √ ◎ Ø ◎ 得到4个独立零元素， 所以最优解矩阵为： ◎ Ø ◎ ◎ Ø 15

48 练习：用分枝定界法求解整数规划问题 （图解法）
练习：用分枝定界法求解整数规划问题 （图解法）

49 LP x1=3/2, x2=10/3 Z(0) ＝29/6 x1≥2 x1≤1 LP2 x1=2, x2=23/9 Z(2) ＝41/9 LP1 x1=1, x2=7/3 Z(1) ＝10/3 x2≤2 x2≤2 x2≥3 x2≥3 LP5 x1=1, x2=2 Z(5) ＝3 LP6 无可 行解 LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 ＃ ＃ x1≥3 ＃ x1≤2 LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1 Z(8) ＝4 ＃ ＃

50 LP x1=2/3, x2=10/3 Z(0) ＝29/6 x1≥2 x1≤1 LP2 x1=2, x2=23/9 Z(2) ＝41/9 LP1 x1=1, x2=7/3 Z(1) ＝10/3 x2≤2 x2≥3 ＃ LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 x1≥3 x1≤2 ＃ LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1 Z(8) ＝4 ＃ ＃