koorio.com
海量文库 文档专家
当前位置:首页 >> 数学 >>

规划数学ch2-5

第五节 整数规划(简称:IP)

一、整数规划问题

要求一部分或全部决策变量取整数值的规划问题称为整数 规划。不考虑整数条件,由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛 问题是一个线性规划,则称该整数规划为整数线性规划。

1. 整数线性规划数学模型的一般形式:

n
max Z(或min Z ) = ∑ c j x j j=1

∑ ?
?

n

aij x j

= bi

(i = 1.2"m)

? j=1

?? x j ≥ 0 (j = 1.2"n) 且部分或全部为整数

P1

2. 整数线性规划问题的种类: 纯整数线性规划:指全部决策变量都必须取整数
值的整数线性规划。 混合整数线性规划:决策变量中有一部分必须取
整数值,另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划:决策变量只能取值0或1的
整数线性规划。
P2

3. 整数规划的典型例子

例1 工厂A1和A2生产某种物资。由于该种物资供不应求,故需要再 建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需 求地的单位物资运费cij,见下表:

B1

B2

B3

B4 年生产能力

A1

2

9

3

4

400

A2

8

3

5

7

600

A3

7

6

1

2

200

A4

4

5

2

5

200

年需求 量

350

400

300

150

工厂A3或A4开工后,每年的生产费用估计分别为1200万或1500万 元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用 最少。

? 解:这是一个物资运输问题,特点是事先不能 确定应该建A3还是A4中哪一个,因而不知道 新厂投产后的实际生产物资。为此,引入0-1

变量:

?1 若建工厂

yi = ??0

(i = 1,2) 若不建工厂

再设xij为由Ai运往Bj的物资数量,单位为千吨;z表示总费用, 单位万元。则该规划问题的数学模型可以表示为:

P4

数学模型:

44

∑ ∑ min z =

cij xij + [1200 y1 + 1500 y2 ]

i=1 j=1

? ? ?

x11 x12

+ +

x 21 x 22

+ +

x 31 x 32

+ +

x41 x42

= =

350 400

? ?

x13

+

x 23

+

x 33

+

x43

=

300

? x14 + x24 + x34 + x44 = 150

s.t

?? ?

?

x11 x 21

+ +

x12 x22

+ +

x13 x 23

+ +

x14 x 24

= =

400 600

? ?

x

31

+

x32

+

x 33

+

x 34

=

200 y1

? x41 + x42 + x43 + x44 = 200 y2

? ?

x

ij



0

(i, j = 1,2,3,4)

?? yi = 0,1 (i = 1,2)

混合整数规划问题

P5

例2 现有资金总额为B。可供选择的投资项目有n个 ,项目j所需投资额和预期收益分别为aj和cj(j= 1,2,..,n),此外由于种种原因,有三个附加条件:
1)若选择项目1,就必须同时选择项目2。反之 不一定; 2)项目3和4中至少选择一个; 3)项目5,6,7中恰好选择2个。 应该怎样选择投资项目,才能使总预期收益最大。
P6

? 解:对每个投资项目都有被选择和不被选择 两种可能,因此分别用0和1表示,令xj表示第 j个项目的决策选择,记为:

?1 x j = ??0

对项目j投资 ( j = 1,2,..., n) 对项目j不投资

投资问题可以表示为:

n

max ∑ z = c j x j

j =1

∑ ?
?

n

ajxj

≤B

? ?

j=1
x2



x1

s

.t

? ?

x

3

+

x4



1

?x5 + x6 + x7 = 2

? ?

x

j

=

0或者 1

(j =

1,2," n)

P7

? 例3 指派问题或分配问题。人事部门欲安排四 人到四个不同岗位工作,每个岗位一个人。经 考核四人在不同岗位的成绩(百分制)如表所 示,如何安排他们的工作使总成绩最好。



作人员

A

B

C

D



85

92

73

90



95

87

78

95



82

83

79

90



86

90

80

88

P8



?1

x ij

=

? ?

0

数学模型如下:

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

max Z = 85 x 11 + 92 x 12 + 73 x 13 + 90 x 14 + 95 x 21 + 87 x 22 + + 78 x 23 + 95 x 24 + 82 x 31 + 83 x 32 + 79 x 33 + 90 x 34 + + 86 x 41 + 90 x 42 + 80 x 43 + 88 x 44
要求每人做一项工作,约束条件为:

? ? ? ? ?

x11 x 21 x 31

+ + +

x12 x 22 x 32

+ + +

x13 x 23 x 33

+ + +

x14 x 24 x 34

=1 =1 =1

?? x41 + x42 + x43 + x44 = 1

P9

? 每项工作只能安排一人,约束条件为:

? ? ? ? ?

x11 x12 x13

+ + +

x 21 x 22 x 23

+ + +

x 31 x 32 x 33

+ + +

x41 x42 x43

= = =

1 1 1

?? x14 + x24 + x34 + x44 = 1

变量约束:

x ij = 0或1, i、 j = 1,2,3,4

P10

4. 整数规划问题解的特征:
整数规划问题的可行解集合是它松弛问题可行解 集合的一个子集,任意两个可行解的凸组合不一定 满足整数约束条件,因而不一定仍为可行解。
整数规划问题的可行解一定是它的松弛问题的可 行解(反之不一定),但其最优解的目标函数值不 会优于后者最优解的目标函数值。
P11

? 例4 设整数规划问题如下

max Z = x 1 + x 2

? ? ?

14 x 1 ? 6x

+ 9x2 1 + 3x

2

≤ 51 ≤1

? ?

x

1

,

x

2



0且为整数

首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。

max Z = x 1 + x 2

? ? ?

14 x 1 ? 6x

+ 9x2 1 + 3x

2

≤ 51 ≤1

?? x 1 , x 2 ≥ 0

P12

? 用图解法求出最优解为:x1=3/2, x2 = 10/3,且 有Z = 29/6

现求整数解(最优解):如用舍入取 整法可得到4个点即(1,3),(2,

x2



3),(1,4),(2,4)。显然,它们都

不可能是整数规划的最优解。

3


(3/2,10/3)

整数规划问题的求解方法:
分枝定界法和割平面法 匈牙利法(指派问题)

按整数规划约束条件,其可行解 肯定在线性规划问题的可行域内 且为整数点。故整数规划问题的 可行解集是一个有限集,如右图 所示。其中(2,2),(3,1)点的目标函 数值最大,即为Z=4。

3

x1

P13

P14

二、分枝定界法
分枝定界法的解题步骤:
1)求整数规划的松弛问题最优解; 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一 步; 2)分枝与定界: ?任意选一个非整数解的变量xi,在松弛问题中加上约束:
xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题 是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目 标值是分枝问题的下界。 ? 检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数 值大于(max)等于其它分枝的目标值,则将其它分枝剪去不再计算, 若还存在非整数解并且目标值大于(max)整数解的目标值,需要继续分枝 ,再检查,直到得到最优解。
P15

例1 用分枝定界法求解整数规划问题

max f = x1 + 5 x2

? x1 ? x2 ≥ ?2

??5 ? ?

x1 x1

+

6

x2

≤ 30 ≤4

IP

?? x1 , x 2 ≥ 0且 全 为 整 数

解:首先去掉整数约束,变成一般线性规划问题(原整数规划问题

的松驰问题)

max f = x1 + 5 x2

? x1 ? x2 ≥ ?2

?? 5 ? ?

x1 x1

+

6

x2

≤ 30 ≤4

LP

?? x1 , x 2 ≥ 0

P16

? 用图解法求松弛问题的最优解,如图所示。

x1=18/11, x2 =40/11
f=218/11≈(19.8)
即Z 也是IP最小值的下限。 对于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

⑵ x2
3 2
1

⑴ (18/11,40/11)


12 3

x1

P17

? 分枝:

max f = x1 + 5 x2

? x1 ? x2 ≥ ?2

(

I P 1)

??? 5 ?

x1 x1

+

6

x2

≤ 30 ≤4

? ?

x1

≤1

?? x1 , x 2 ≥ 0且 为 整 数

max f = x1 + 5 x2

? x1 ? x2 ≥ ?2

(

IP

2)

??? 5 ?

x1 x1

+

6

x2

≤ 30 ≤4

? ?

x1

≥2

?? x1 , x 2 ≥ 0且 为 整 数

分别求出(LP1)和(LP2)的最优解。

P18

? 先求LP1,如图所示。此 时在B点取得最优解。

? x1=1, x2 =3, f(1)=16

? 找到整数解,问题已探

明,此枝停止计算。

x2

同理求LP2,如图所示。在C 点

取得最优解。即:

3

x1=2, x2 =10/3,

f(2)=56/3≈18.7

∵f(2)>f(1)=16

1

∴原问题有比16更大的最优 解,但 x2 不是整数,故继续 分枝。

⑵ ⑴
A(18/11,40/11) C
B


1

3

x1

P19

? 在IP2中分别再加入条件: x2≤3, x2≥4 得 下式两支:

max f = x1 + 5 x2

max f = x1 + 5 x2

(

I

P

2

1)

? ? ? ?? ? ? ? ? ??

x1 5 x1
x1 x1 x2 x1 ,

? +
x2

x2 ≥ ?2 6 x2 ≤ 30
≤4 ≥2 ≤3 ≥ 0且 为 整

( 数

I

P

2

2

)

? ? ? ?? ? ? ? ? ??

x1 5 x1
x1 x1 x2 x1 ,

? +
x2

x2 ≥ ?2 6 x2 ≤ 30
≤4 ≥2 ≥4 ≥ 0且 为 整



分别求出LP21和LP22的最优解

P20

分枝定界法

先求LP21,如图所示。此时D 在点取得最优解。 即 x1=12/5≈2.4, x2 =3,
f(21)=87/5≈17.4 > f(1)=16



x2



A

(18/11,40/11)

3

BCD

但x1=12/5不是整数,可继续



分枝。即 3≤x1≤2。

求LP22,如图所示。无可行

1

解,故不再分枝。

1

3

x1

P21

在(LP21)的基础上继续分枝。加入条件

3≤x1≤2有下式: max f = x1 + 5 x2

max f = x1 + 5 x2

?

? ?

5

x1 x1

? +

x2 6 x2

≥ ?2 ≤ 30

?

? ?

5

x1 x1

? +

x2 6 x2

≥ ?2 ≤ 30

? ?

x1

( IP 211) ? x1

≤4

? ?

x1

≥ 2( IP 212) ? x1

≤4 ≥2

? ?

x2

≤3

? ?

x2

≤3

? ?

x1

? x1, x2



≤2 0且 为 整 数

? ?

x1

? x1, x2



≥3 0且 为 整 数

分别求出(LP211)和(LP212)的最优解

P22

先求(LP211),如图所示。此时 在E点取得最优解。即
x1=2, x2 =3, f(211)=17 找到整数解,问题已探明,此枝x2 停止计算。 求(LP212),如图所示。此时 3 F在点取得最优解。即x1=3, x2 =2.5,
f(212)=31/2≈15.5 < Z(211) 1
如对LP212继续分解,其最大值 也不会大于15.5 ,问题探明,剪 枝。

⑵ ⑴

A

(18/11,40/11) B CD

E

F



1

3

x1

P23

分枝定界法
? 原整数规划 问题的最优 解为:
? x1=2, x2 =3, f* =17
? 以上的求解 过程可以用 一个树形图 表示如右:

LP

x1=18/11, x2=40/11 f(0) =19.8

x1≤1

x1≥2

LP1 x1=1, x2=3 f(1) =16


LP2

x1=2, x2=10/3 f(2) =18.5

x2≤3

x2≥4

x1≤2

LP21 x1=12/5, x2=3
f(21) =17.4

x1≥3

LP22 无可 行解


LP211 x1=2, x2=3 f(211) =17


LP212 x1=3, x2=5/2 f(212) =15.5


例2 用分枝定界法求解

m ax f = 4 x1 + 3 x2

? ? ?

1.2 x1 + 0.8 x 2 ≤ 10 2 x1 + 2.5 x 2 ≤ 25

?? x 1 , x 2 ≥ 0 , 且 均 取 整 数

解: 先求对应的松弛问题(记为LP0)

max f = 4x1 + 3x2

st ???12.2xx11++20.5.8xx22≤≤2150 ?? x1, x2 ≥ 0

(LP 0 )

用图解法得到最优解X=(3.57,7.14),f0=35.7,如下图所示。

P25

分枝定界法

x2 A
10

1.2x1 + 0.8x2 = 10
松弛问题LP0的最优解 X=(3.57,7.14),f0=35.7 B

2x1 + 2.5x2 = 25

C

o

10

P2x61

x2

增加约束x1 ≤ 3及x1 ≥ 4得到两个线性规划

A 10

LP1

o

3

max f = 4x1 + 3x2

LP1:X=(3,7.6),f1=34.8 B

?1.2x1 + 0.8x2 ≤10

LP1:

?? ? ?

2x1 + 2.5x2 x1 ≤ 3



25

?? x1, x2 ≥ 0

LP2:X=(4,6.5),f2=35.5 max f = 4x1 + 3x2

LP2

C

4



?1.2x1 + 0.8x2 ≤10

LP2

:

?? ? ?

2x1 + 2.5x2 x1 ≥ 4



25

?? x1, x2 ≥ 0



P27

x2

选择目标值最大的分枝 LP 2进行分枝,增加约束

A 10

x2 ≤ 6及x2 ≥ 7,显然 x2 ≥ 7不可行,得到线性规划

x2 ≥ 7不可行 B

max f = 4x1 + 3x2

?1.2x1 + 0.8x2 ≤10

LP22

:

?? ? ?

2x1 + 2.5x2 ≤ 25 x1 ≥ 4,x2 ≥ 7

?? x1, x2 ≥ 0

6 LP1

LP21

o

34

LP21:X=(4.33,6),f21=35.33

max f = 4x1 + 3x2

?1.2x1 + 0.8x2 ≤10

LP21:

?? ? ?

2x1 + 2.5x2 ≤ 25 x1 ≥ 4,x2 ≤ 6

C

?? x1, x2 ≥ 0

x1

P28

x2 由于 f21 > f1, 选择LP 21进行 分枝,增加 约束

A 10
6

x1 ≤ 4及x1 ≥ 5,得 线性规划LP 211及LP 212:

max f = 4x1 +3x2

LP211:X=(4,6), f211=34
LP212:X=(5,5 ),f212=35

? 1.2x1 + 0.8x2 ≤10 LP211: ????2x1x1≥+4,2.5xx22≤≤62,5x1 ≤ 4

??

x1, x2 ≥ 0

即x1 = 4,可行域是一条线段

max f = 4 x1 + 3x2

LP1
LP212
C

?1.2 x1 + 0.8x2 ≤ 10

LP 212

:

?? ? ?

2 x1 + 2.5x2 ≤ 25 x1 ≥ 5,x2 ≤ 6

?? x1, x2 ≥ 0

o

3 45

x1

P29

?上述分枝过程可用下图表示:

LP0:X=(3.57,7.14),f0=35.7

x1≤3

x1≥4

LP1:X=(3,7.6) f1=34.8

x2≤6

LP2:X=(4,6.5) f2=35.5

x2≥7

LP21:X=(4.33,6)

LP22

f21=35.33

无可行解

x1≤4

x1≥5

LP211:X=(4,6) f211=34

LP212:X=(5,5) f212=35

P30

三、割平面法
割平面法是1958年美国学者R. E. Gomory提出的, 所以又称为Gomory的割平面法。
? 基本思想: 先不考虑变量的取整数约束,求解相应的线性规划, 然后不断增加线性约束条件(即割平面), 将原可行域割掉不含整数可行解的一部分, 最终得到一个具有整数坐标顶点的可行域, 而该顶点恰好是原整数规划问题的最优解。 以下只讨论纯整数线性规划的情形, 下面举例说明。
P31

割平面求解举例 例:
Max f=x1+x2 ① -x1+x2≤1 ② 3x1+x2 ≤4 ③ 松弛问题 x1 , x2≥0 ④ x1 , x2为整数⑤

Max f=x1+x2 -x1+x2≤+x13 =1 3x1+x2 ≤+4x4=4 x1 , x2≥0

P32

如不考虑条件⑤,容易求得相应的线性规划的 最优解:x1=3/4,x2=7/4,max f=10/4
? 它就是图中区域R 的顶点A,但不合 于整数条件。
P33

现设想,如能找到像CD那样的直线去切割域R(如图), 去掉三角形域ACD,那么具有整数坐标的C点(1,1)就是 域R′的一个极点,
? 如在域R′上求解①~④, 而得到的最优解又恰巧在C点, 就得到原问题的整数解,
? 所以解法的关键: 就是怎样构造一个这样的 “割平面”CD, 它就是一个新的约束。 尽管它可能不是唯一的, 也可能不是一步能求到的。
? 下面给出本例完整的求解过程:
P34

? 用单纯形表解松弛问题,见下表2-5-1。
Max f=x1+x2 -x1+x2≤+x13 =1 ⑥ 3x1+x2 ≤+4x4=4 ⑦ x1 , x2≥0
P35

解松弛问题的最优单纯形表为(2-5-1):

1100

CB XB

b

x1 x2 x3 x4

0 x3 1 -1 1 1 0

0 x4 4 3 1 0 1

σ1 1 0 0

…………………

1 x1 3/4 1
1 x2 7/4 0 f=5/2 σ 0

0 -1/4 1/4 1 3/4 1/4 0 1/2 1/2

P36

从表2-5-1的最终计算表中,得到非整数的最优解: x1=3/4,x2=7/4,x3=x4=0,max f=5/2

v 不能满足整数最优解的要求。 v 为此考虑将带有分数的最优解的可行域中分数
部分割去,再求最优解。就可以得到整数的最

优解。

可从最终计算表中得到非整数基变量对应的

关系式:

x1

?

1 4

x3

+

1 4

x4

=

3 4

x2

+

3 4

x3

+

1 4

x4

=

7 4

P37

为了得到整数最优解。将上式变量的系数和常数项都分解 成整数和非负真分数两部分之和

? (1+0)x1+(-1+3/4)x3+1/4x4=0+3/4

?

x2+(3/4)x3+(1/4)x4=1+3/4

? 然后将整数部分与分数部分分开,移到等式左右两边,得

到:

x1

?

x3

=

3 4

?

?? ?

3 4

x3

+

1 4

x4

?? ?

x2 ?

1=

3 4

?

?? ?

3 4

x3

+

1 4

x4

?? ?

P38

现考虑整数条件⑤:要求x1、x2都是非负整数 ? 于是由条件⑥、⑦可知 , x3、x4也都是非负整
数, 这一点对以下推导是必要的,如不都是整数, 则应在引入x3、x4之前乘以适当调整系数和常数, 使之都是整数。
P39

在上式中(其实只考虑一式即可) 从等式左边看是整数; 等式右边也应是整数。 但在等式右边的(·)内是正数;
所以等式右边必是非正整数。 就是说,右边的整数值最大是零。 于是整数条件⑤可由下式所代替;

3 4

?

(3 4

x3

+

1 4

x4 )



0

x1

?

x3

=

3 4

?

?? ?

3 4

x3

+

1 4

x4

?? ?

x2 ?

1=

3 4

?

?? ?

3 4

x3

+

1 4

x4

?? ?

P40

3 4

?

(3 4

x3

+

1 4

x4 )



0

? 即 -3x3-x4≤-3



这就得到一个切割方程(或称为切割约束),

将它作为增加约束条件,再解例3。

? 引入松弛变量x5,得到等式 ? -3x3-x4+x5=-3
? 将这新的约束方程加到表2-5-1的最终计算表,

得表2-5-2。

P41

表2-5-2

cj

110

0

0

CB XB b

x1 x2 x3

x4

x5

1 x1 3/4 1 0 -1/4 1/4 0

1 x2 7/4 0 1 3/4 1/4 0

0 x5 -3

0 0 -3

-1

1

zj-cj

5/2 0 0 1/2 1/2 0

从表2-5-2的b列中可看到,这时得到的是非可行解 ,于是需要用对偶单纯形法继续进行计算。

选择x5为换出变量,计算

θ

=

min j

?? c j ? z j ?? a lj

a lj

<

0

?? ??

=

min

?? ? ???

?1
2 ?3

,

?1
2 ?1

?? ? ???

=

1 6

将x3做为换入变量,再按原单纯形法进行迭代,得 下表

CB XB 1 x1 1 x2 0 x3
zj-cj

cj b 1 1 1 2

11 0

x1 x2

x3

10 0

01

0

00

1

00 0

0

0

x4

x5

1/3 -1/12

0 1/4

1/3 -1/3

1/3 1/6

x1、x2的值已都是整数,解题已完成。

几何解释:新得到的约束条件⑧ -3x3-x4≤-3
? 如用x1、x2表示,由⑥、⑦式得 ? 3(1+x1-x2)+(4-3x1-x2)≥3 ? x2≤1
? 则是(x1,x2)平面内形成新的可行域, 即包括平行于x1轴的直线x2=1 和这直线下的可行区域,
整数点也在其中,没有切割掉。
直观地表示在图5-7中。
? 但从解题过程来看,这一步是不必要的。

P43

P44

割平面法的计算步骤: 1、用单纯形法求解( IP )对应的松弛问题( LP ):
⑴. 若( LP )没有可行解,则( IP )也没有可行解, 停止计算。
⑵. 若( LP )有最优解,并符合( IP )的整数条件, 则( LP )的最优解即为( IP )的最优解, 停止计算。
⑶.若( LP )有最优解,但不符合( IP )的整数条件, 转入下一步。
P45

2、从(LP)的最优解中,

任选一个不为整数的分量xr,, 将最优单纯形表中该行的系数arj′和 br ′分解为
整数部分和非负真分数部分之和,

并以 该行为源行,按下式作割平面方程:

n

∑ zr ?

zrj x j ≤ 0

j = m +1

b r′ 的非负真分数部分

a ′rj 的非负真分数部分

P46

3、将所得的割平面方程 作为一个新的约束条件 置于最优单纯形表中 (同时增加一个单位列向量), 用对偶单纯形法求出新的最优解,返回1。
P47

例: 用割平面法求下面整数规划问题

max f = 3x1 + 2 x2

s.t.

???2x1x+1 +03.5xx22

≤ 14 ≤ 4.5

?? x1, x2 ≥ 0,且均取整数值

P48

第一步:把问题中所有约束条件的系数均化 为整数.

max f = 3x1 + 2 x2

G0:max f = 3x1 + 2 x2

s.t.

???2x1x1++03.5xx22

≤ 14 ≤ 4.5

s.t.

?2 ??2

x1 x1

+ +

3

x2 x2

≤ 14 ≤9

?? x1, x2 ≥ 0,且均取整数值

?? x1, x2 ≥ 0

cB

xB

b

x1

2

x2

5/2

0

3

x1

13/4

1

Zj-cj

0

x2

x3

x4

1

1/2

-1/2

0

-1/4

3/4

0

1/4

5/4

P49

第二步:

x2

+

1 2

x3

?

1 2

x4

=

2

1 2

x2

+

?? 0 ?

+

1 2

?? ?

x

3

+

?? ? 1 + ?

1 2

??x ?

4

=

?? 2 + ?

1 2

?? ?

x2

?

x4

?

2

=

1 2

?

1 2

x3

?

1 2

x4

因为x3,x4≥0

x2

1 2

?

1 2

x3

?

1 2

x4



1 2

<

1

?x ??x

3 4

= =

14 ? 2x1 ? 3x2 9 ? 2x1 ? x2

1 2

?

1 2

x3

?

1 2

x4



0

2x1 + 2x2 ≤ 11

1 2

?

1 2

x3

?

1 2

x4



0

×

1 2

?

1 2

x3

?

1 2

x4

+

x5

=

0

×× ××× ××××

O

P5x01

第三步:将Gomory约束加到G0中得到新的线

性规划问题G1如下:

max f = 3x1 + 2 x2

G1:
s.t.

?2 ? ??2

x1 x1

+ +

3x2 x2

+

x3

+ x4

= 14 =9

? ? ? ?? x j ≥ 0

?

1 2

x3

?

1 2

x4

+

x5

=

?

1 2

( j = 1,",5)

P51

Cj

2

CB

XB

b

x1

2

x2

21 2

0

3

x1

31 4

1

0

x5

-1/2

0

zj-cj

0

2

x2

2

0

3

x1

31 2

1

0

x3

1

0

zj-cj

0

3

0

0

0

x2

x3

x4

x5

1

1/2 -1/2

0

0

-1/4 3/4

0

0 [-1/2] -1/2 1

0

1/4

5/4 0

1

0

-1 1/2

0

0

1 -1/2

0

1

1

-2

0

0

1

1/2

第四步:重复第一至第三步一直到找出问 题的整数最优解为止.

x1

+

x4

?

1 2

x5

=

3

1 2

P52

x1 x1 x1

+ + +

x4 x4 x4

? ? ?

1 2 x5 x5 +
x5 ?

=31 312=x5122=?312+x125

1 2

?

1 2

x5



0

1 2

?

1 2

x5

+

x6

=

0

G2:

m ax s .t .

f = 3 x1 + 2 x2

?

? ?

2

x

1

+

3 x2

+

x3

? 2 x1 + x 2

+ x4

= 14 =9

?? ? ?

?

1 2

x3

?

1 2

x4

+

x5

=?1 2

? ? ? ?? x j ≥ 0

?

1 2

x5

+

x6

=

?

1 2

( j = 1," , 6 )

P53

Cj

2

3

0

0

0

0

CB

XB

b

x1

x2

x3

x4

x5

x6

2

x2

2

0

1

0

-1 1/2

0

3

x1

1 3
2

1

0

0

1 -1/4 0

0

x3

1

0

0

1

1

-1

0

0

x6

-1/2

0

0

0

0 [-1/2] 1

zj-cj

0

0

0

1

1/2 0

2

x2

1

0

1

0

-1

0

2

3

x1

4

1

0

0

1

0

-1

0

x3

3

0

0

1

1

0

-4

0

x5

1

0

0

0

0

1

-2

zj-cj

0

0

0

1

0

1

P54

1 2

?

1 2

x5



0

G2 max :
s.t.

1 2

?

1 2

x3

?

1 2

x4

+

x5

=

0

x2

?x ??x

3 4

= =

14 ? 2x1 ? 3x2 9 ? 2x1 ? x2

f = 3 x1 + 2 x2

?

? ?

2

x1

+

3x2

+

x3

?2 x1 + x2

+ x4

= 14 =9

?? ? ?

?

1 2

x3

?

1 2

x4

+

x5

=?1 2

? ? ? ?? x j ≥ 0

?

1 2

x5

+

x6

=

?

1 2

( j = 1," , 6)

x1 + x2 ≤ 5

× ×× ××× ××××
O

x1
P55

? Gomory的切割法自1958年被提出后,即引 起人们的广泛注意,但至今完全用它解题的 仍是少数,原因就是经常遇到收敛很慢的情 形,但若和其他方法(如分枝定界法)配合 使用,也是有效的。
P56

四、0-1整数规划
1. 隐枚举法 0-1整数规划是决策变量只取0或1的整数规划问题。 除
采用前面的分枝定界法和割平面法,由问题的特殊结构, 有更有效的求解方法。
穷举法是检查变量取值为0或1的每一种组合(称为一个 状态,空间点),比较目标函数值以求得最优解。隐枚举法 是仅检查变量取值组合的一般分,就能求到最优解的一种 方法。即在某些部分取值组合上进行穷举。
下面举例说明
P57

例:求解0-1整数规划:
IP0
解:

max f = 3x1-2x2 + 5x3

s.t. x1 + 2x2 ? x3 ≤ 2

x1 + 4 x2 + x3 ≤ 4

x1 + x2

≤3

4 x2 + x3 ≤ 6

x1, x2 , x3 = 0或1

(1)通过观察、试探得一可行解 X 0 = (1, 0, 0)T ,目标函数值为 f0 = 3 。 (2)增加过滤条件:f ≥ 3, 即 3x1 ? 2x2 + 5x3 ≥ 3, 得新问题IP1
(3)求解新问题IP1。 求解过程中,先对每个状态点检验f ≥ 3是否成立,一般可减少计算量。

P58

max f = 3x1-2x2 + 5x3

s.t. x1 + 2x2 ? x3 ≤ 2

x1 + 4x2 + x3 ≤ 4

IP1

x1 + x2

≤3

4x2 + x3 ≤ 6

3x1-2x2 + 5x3 ≥ 3

x1, x2, x3 = 0或1

XT
IP1

f值
√×
× √ × × √ √ × ×

由上表可以知:最优解 X = (1, 0,1)T ,最优值 f = 8. 共计算24次(穷举法为32次)

P59

2. 隐枚举法的改进
求解过程中,若求得某个可行解的目标函数值 f1 > f0, 则将过滤条件改为f ≥ f1 。 当求到更大f 值时,继续修改过滤条件。 这样边计算边修改可减少计算次数。

max f = 3x1-2x2 + 5x3

s.t. x1 + 2x2 ? x3 ≤ 2

x1 + 4x2 + x3 ≤ 4

IP1

x1 + x2

≤3

4x2 + x3 ≤ 6

3x1-2x2 + 5x3 ≥ 3

x1, x2, x3 = 0或1

P60

表1 XT

f ≥3

表2 XT

f ≥5

表3

f值
× √
f值
× √

练习题

f值

XT

f ≥8

× × × ×

所以,最优解 X = (1, 0,1)T ,最优值 f = 8. 共计算16次(枚举法24次,穷举法为32次)

P61

P62


推荐相关:

规划数学ch2-5.pdf

规划数学ch2-5 - 第五节 整数规划(简称:IP) 一、整数规划问题 要求一


规划数学ch2-1.pdf

规划数学ch2-1 - 第二章、线性规划 ?线性规划(Linear 线性规划(L


规划数学ch1-ch2-2.pdf

规划数学ch1-ch2-2_理学_高等教育_教育专区。规划数学课后习题 《规划数学》 第一章、概论内容介绍(32学时)第一章 概论 第二章 线性规划 第三章 非线性规划...


newCh2-5导数的简单应用_图文.ppt

newCh2-5导数的简单应用 - 2.1 2.2 2.4 2.3 导数的概念


离散数学ch2 (5)_图文.ppt

离散数学ch2 (5) - 第二部分 集合论 1 第二部分 第6章 集合代数 第


Ch2 线性规划(min)_图文.ppt

Ch2 线性规划(min) - Chapter 2 线性规划 Linear Pr


ch2线性规划-signed_图文.pdf

ch2线性规划-signed - 第二章 线性规划问题的基本概念及单纯形算法 §2.1 引言 线性规划是运筹学中应用最广泛的问题之一,也是运筹学的最基本的问题之一,网络...


北邮运筹学ch2-1 线性规划的对偶模型.ppt

【解】设x1,x2,x3分别为产品A,B,C的产量,则线性规划数学模 型为: max Z...Dual model of LP Ch2 Dual Problem 2013-9-13 Page 5 of 19 min w ? ...


数学建模数学规划模型_图文.ppt

数学建模数学规划模型_其它_职业教育_教育专区。数学建模数学规划模型,gm11模型,...利用Matlab软件编程序: % 营养配餐ch21 % 文件名: ch21 m c=[5;5;8;2...


线性规划问题的数学模型_图文.ppt

线性规划问题的数学模型 - 第 1章 第 2章 第 3章 第 4章 第 5章 线性规划问题的数学模型 单纯形方法 对偶线性规划问题 运输问题 整数规划 Linear ...


6讲:ch2-5样条插值(录课)_图文.ppt

6讲:ch2-5样条插值(录课)_数学_高中教育_教育专区。文档均来自网络,如有


5--5整数规划数学模型_图文.ppt

5--5整数规划数学模型 - 第2章 整数规划 §2.1 数学模型 例1、集装箱运货 货物 甲乙 装运限制 体积(米3/箱) 5 4 24 重量(百公斤/箱) 2 5 13 ...


北邮运筹学ch5-1 整数规划数学模型_图文.ppt

运筹学 北京邮电大学 §5.1 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2018/11/5 Page 2 of 15 【例5.1 】某人有一背包可以装10...


数学建模作业5数学规划模型---供应与选址的问题.doc

数学建模作业5数学规划模型---供应与选址的问题 - 课程名称 上机项目 专业班级 一、问题提出 佛山科学技术学院 上机报告 数学建模 数学规划模型---供应与选址...


ch2第二节-表上作业法_图文.ppt

ch2第二节-表上作业法 - §3.2 运输问题求解表上作业法 由于运输问题系数矩阵的特殊性,如果直接使用线 性规划单纯形法求解计算,则无法利用这些有利条 件。...


数学建模规划模型讲解_图文.ppt

2、线性规划模型 3、线性规划的性质。 4、线性规划的主要算法。 5、用数学...是20世纪50年代至 60年代,其奠基人应是苏联数学家Cantolovch 和美国 数学家G...


离散数学ch2.ppt

离散数学ch2_数学_自然科学_专业资料。帮助进一步系统学习离散数学第...不同点是: 实施的对象不同,范围不同,结果的形式不同 2-5谓词演算的等价式...


北邮运筹学ch4-1 目标规划数学模型.ppt

北邮运筹学ch6-1 动态规划... 北邮运筹学ch5-2 分枝定界...1...与线性规划有哪些 联系和区别 目标规划数学模型的构成及其特征 目标规划的图解法...


河北师范大学数学分析习题集Ch2_5.pdf

河北师范大学数学分析习题集Ch2_5 - 1 .求下列极限。 3 x →0 2


数学物理方法姚端正CH2作业解答.pdf

数学物理方法姚端正CH2作业解答_理学_高等教育_教育专区。数学物理方法姚端正第

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com