运筹学整数特点及应用

Chapter4整数规(IntegerProgramming本章主要内本章主要内容整数规划的特点及应整数规划（要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构题是一个线性规划，则称该整数规划为整数线性规划。n

Z(或

Z)

cjxjaa ijx

(i

1.2m)x 0(j1.2n)且部分或全部x 整数规划的特点及应整数规划的特点及应整数规划的典型例例4.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要2934835776124525整数规划的特点及应解：这是一个物资问题，特点是事先不能确定应该建A30yi0

若建工厂若不建工厂

(i整数规划的特点及应

cij

1500y2 x11

x21

x31

x41

x x

x23

x33

x43

x14

x24

x34

x44

xs.tx

x12

x13

x41

x42

x43

x44

200y2xx

(i,jyi

0,1(i整数规划的特点及应例4.2现有总额为B。可供选择的投资项目有n个，项目应该怎样选择投资项目，才能使总预 整数规划的特点及应分别用0和1表示，令xj表示第j个项目的决策选择，记为0xj0

对项目j投资对项目j不投资

(j

n

zcjxjnax jaxx2s.t

x5x6x7x 0或者1（jx

整数规划的特点及应例4.3指派问题或分配问题。人事部门欲安排四人到四个不。工ABCD甲乙丙丁整数规划的特点及应 0xij0

分配第i人做j工作时不分配i人做j工作

85x1192x1278x2395x2486x4190x42x11 x12 x24 x34

x42

x3

x44整数规划的特点及应每项工作只能安排一人，约束条件为xij

，i

整数规划的特点及应整数规整数规划问题解的特征整数规划的特点及应例4.3设整数规划问题如maxZ

x1x214x19

511 61

3x2x,xx,x

0且为整数maxZ

x1x214x19

511 6 3 12x,x 2x,x整数规划的特点及应用图解法求出最优解为：x1＝3/2,x210/3，且有Z入取整法可得到4个点即 解肯定性规划问题的可行域

⑵ 整数规划的特点及应分支定界求整数规划的松弛问题最优解若松弛问题的最优解满足整数要求，得到整数规划的最优解,一步；任意选一个非整数解的变量xi，在松弛问题中加上约束 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（a）还存在非整数解并且目标值大于a)整数解的目标值，需要继续分枝，再检查，直到得到最优解。分支定界例4.4用分枝定界法求解整数规划问

5x2 x1 x215 6 12x4x4 x1x20且全为整数

min

5x2 x1 x215 6 12x4x4 x1,x2x⑵2⑴32x⑵2⑴32⑶1123用图解法求松弛问题的最优解，如图所示x1＝18/11,即Z也是IP最小值的下限。取值x11x1对于x2=40/113.64，取值≤3，x2和（LP2）,取x11,x1分支定界分支min

5x2

min

5x2 x1 x2

x1 x215 612

30

5 6121

30(

(IP 2 2 2x 2

x 0且为整数分支定界x1＝1,x2=3,枝停止计算 同理求LP2,如图所示。在Cx1＝2,x2 ∵Z(2)<解，但x2不是整数，故继续

⑶ 分支定界在IP2中分别再加入条件：x2≤3, 得下式两支min

5x2

min

5x2 x1 x2

x1 x215 612

5 6121

30 (

4 4(IP22) 2x, 2

0且为整 x1,x20且为整分支定界在点取得最优解 即x1＝12/5≈2.4,x2Z(21)＝-87/5≈-17.4<Z(1)=- 但x1＝12/53≤x1≤2

A ⑶ 分支定界在（LP21）的基础上继续分枝。加入条件3≤x1≤2 x x ( x2

( x2 x,xx,x

0且为整

x,x x,x

0且为整分支定界 x1＝2,x2=3, F在点取得最优解。即x1＝3, Z(212)＝－31/2≈－15.5>也不会低于－15.5，问题探明,

A 分支定界x1=2,x2=3,Z* x1=1, x1=1,Z(1)

x1=18/11,x2=40/11Z(0) 右

x1=2,Z(2) 行 x1 行 x1=12/5,x2=3Z(21) x1=2,x2=3Z(211)＝－17 x1=3,x2=5/2Z(212)＝－15.5 分支定界例4.5用分枝定界法max

4

3x2 1.2x10.8

101 2 2.512

25x,xx,x

0且均取整数解:先求对应的松弛问题（记为max

4

3x2

0.8

100st2x12.5x2

(LPx, 2x,用图解法得到最优解X＝(3.57,7.14),Z0=35.7,如下图所示分支定界

松弛松弛问题LP0的最优

C 分支定界

max

4

3x2 1.2x10.8

102x12.5x2

25LP1:

x1 x1,x2

4x131.2x10.8x22x12.5x225

x1x1,x2C 分支定界 选择目标值x2

6及

7，显然

7不可行，得x27 maxZ4x1x27 1.2x10.8

102x12.5x2

25LP22:

x1

x1,x6

4

3x21.2

0.8

10LP21

2

2.5

25x 2 4，xx 2C

x1,x2分支定界 由于Z21Z1x1

，得线性规LP

3x2