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

规划数学ch2-5


第五节 整数规划(简称:IP)
一、整数规划问题
要求一部分或全部决策变量取整数值的规划问题称为整数 规划。不考虑整数条件,由余下的目标函数和约束条件构 成的规划问题称为该整数规划问题的松弛问题。若该松弛 问题是一个线性规划,则称该整数规划为整数线性规划。 1. 整数线性规划数学模型的一般形式:
max Z (或 min Z ) = ∑ c j x j
j =1 n

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

?n ?∑ a ij x j = bi ( i = 1.2" m ) ? j=1 ? x j ≥ 0 (j = 1.2"n) 且部分或全部为整数 ?
P1

P2

3. 整数规划的典型例子
例1 工厂A1和A2生产某种物资。由于该种物资供不应求,故需要再 建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需 求地的单位物资运费cij,见下表:
B1 A1 A2 A3 A4 年需求 量 2 8 7 4 350 B2 9 3 6 5 400 B3 3 5 1 2 300 B4 4 7 2 5 150 年生产能力 400 600 200 200

?

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

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

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

P4

数学模型:
min z = ∑ ∑ c ij x ij + [1200 y1 + 1500 y 2 ]
i =1 j =1 4 4

? x11 + x 21 + x 31 + x 41 = 350 ? ? x12 + x 22 + x 32 + x 42 = 400 ? x13 + x 23 + x 33 + x 43 = 300 ? ? x14 + x 24 + x 34 + x 44 = 150 ? x + x + x + x = 400 ? 11 12 13 14 s .t ? + + + x x x x 21 22 23 24 = 600 ? ? x 31 + x 32 + x 33 + x 34 = 200 y1 ? ? x 41 + x 42 + x 43 + x 44 = 200 y 2 ? x ≥ 0 ( i , j = 1,2,3,4) ? ij ? ? y i = 0,1 ( i = 1,2)

例2 现有资金总额为B。可供选择的投资项目有n个 ,项目j所需投资额和预期收益分别为aj和cj(j= 1,2,..,n),此外由于种种原因,有三个附加条件:

混合整数规划问题

1)若选择项目1,就必须同时选择项目2。反之 不一定; 2)项目3和4中至少选择一个; 3)项目5,6,7中恰好选择2个。
应该怎样选择投资项目,才能使总预期收益最大。
P5 P6

?

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

?

例3 指派问题或分配问题。人事部门欲安排四 人到四个不同岗位工作,每个岗位一个人。经 考核四人在不同岗位的成绩(百分制)如表所 示,如何安排他们的工作使总成绩最好。
工 作人员 甲 乙 丙 丁 A 85 95 82 86 B 92 87 83 90 C 73 78 79 80 D 90 95 90 88
P8

投资问题可以表示为:

max

z=

∑c
j =1

n

j

xj

? n ajxj ≤ B ?∑ j =1 ? ? x 2 ≥ x1 s .t ? x + x ≥ 1 4 ? 3 ? x5 + x6 + x7 = 2 ? x = 0或者 1 ( j = 1, 2 , " n ) ? j
P7



?1 x ij = ? ?0

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

? 每项工作只能安排一人,约束条件为:
? x11 + x 21 + x 31 + x 41 ? ? x12 + x 22 + x 32 + x 42 ? ? x13 + x 23 + x 33 + x 43 ? x14 + x 24 + x 34 + x 44 ? =1 =1 =1 =1

数学模型如下:
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 + x12 + x13 + x14 = 1 ? ? x 21 + x 22 + x 23 + x 24 = 1 ? ? x 31 + x 32 + x 33 + x 34 = 1 ? x 41 + x 42 + x 43 + x 44 = 1 ?
P9

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

P10

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

?

例4 设整数规划问题如下
max Z = x 1 + x 2 ? 14 x 1 + 9 x 2 ≤ 51 ? ?? 6 x1 + 3 x2 ≤ 1 ? x , x ≥ 0 且为整数 ? 1 2

首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。
max Z = x 1 + x 2 ? 14 x 1 + 9 x 2 ≤ 51 ? ?? 6 x1 + 3 x 2 ≤ 1 ?x , x ≥ 0 ? 1 2
P12

P11

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

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

x2
3





(3/2,10/3)

3

x1
P13 P14

二、分枝定界法
分枝定界法的解题步骤:
1)求整数规划的松弛问题最优解; 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一 步; 2)分枝与定界:
?任意选一个非整数解的变量xi,在松弛问题中加上约束:

例1 用分枝定界法求解整数规划问题
m ax f = x1 + 5 x 2 ? x1 ? x 2 ≥ ? 2 ? 5 x + 6 x ≤ 30 IP ? 1 2 ? x ≤ 4 ? 1 ? ? x1 , x 2 ≥ 0 且 全 为 整 数
解:首先去掉整数约束,变成一般线性规划问题(原整数规划问题 的松驰问题) m ax f = x 1 + 5 x 2
? x1 ? x 2 ≥ ? 2 ? 5 x + 6 x ≤ 30 ? 1 2 ? ≤4 ? x1 ? ? x1 , x 2 ≥ 0

xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题 是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目 标值是分枝问题的下界。 ? 检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数 值大于(max)等于其它分枝的目标值,则将其它分枝剪去不再计算, 若还存在非整数解并且目标值大于(max)整数解的目标值,需要继续分枝 ,再检查,直到得到最优解。
P15

LP

P16

? 用图解法求松弛问题的最优解,如图所示。
x1=18/11, x2 =40/11 f=218/11≈(19.8)

?

分枝:
m ax f = x1 + 5 x 2 m ax f = x1 + 5 x 2 ? x1 ? x 2 ≥ ? 2 ? ? 5 x1 + 6 x 2 ≤ 30 ? ( IP 2) ? x1 ≤4 ? x ≥2 ? 1 ? x , x ≥ 0 且 为整数 ? 1 2

⑵ x2 3 2 1 1 2

⑴ (18/11,40/11) ⑶

即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

? x1 ? x 2 ≥ ? 2 ? ? 5 x1 + 6 x 2 ≤ 30 ? ( IP 1) ? x1 ≤4 ? x ≤1 ? 1 ? x , x ≥ 0 且 为整数 ? 1 2

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

3

x1
P17 P18

?

? ?

先求LP1,如图所示。此 时在B点取得最优解。 x1=1, x2 =3, f(1)=16 找到整数解,问题已探 明,此枝停止计算。

? 在IP2中分别再加入条件: x2≤3, x2≥4 下式两支:
⑵ x2 3 B A ⑴ (18/11,40/11) C ⑶
m ax f = x1 + 5 x 2



同理求LP2,如图所示。在C 点 取得最优解。即:
x1=2, x2 =10/3, f(2)=56/3≈18.7

∵f(2)>f(1)=16 ∴原问题有比16更大的最优 解,但 x2 不是整数,故继续 分枝。

1 1 3 x1
P19

m ax f = x 1 + 5 x 2 ? x1 ? x 2 ≥ ? 2 ? x1 ? x 2 ≥ ? 2 ? 5 x + 6 x ≤ 30 ? 5 x + 6 x ≤ 30 2 ? 1 2 ? 1 ? x ≤ 4 ? 1 ? ≤4 ? x1 ( IP 21) ? ( IP 22) ? ≥2 ? x1 x ≥2 ? 1 ? x2 ≤3 ? x 4 ≥ ? 2 ? ? ? x1 , x 2 ≥ 0 且 为 整 数 ? x1 , x 2 ≥ 0且 为 整 数 ?
分别求出LP21和LP22的最优解

P20

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

⑵ x2



m ax f = x1 + 5 x 2

在(LP21)的基础上继续分枝。加入条件 3≤x1≤2有下式:
m ax f = x1 + 5 x 2

A B C

3

(18/11,40/11) D


但x1=12/5不是整数,可继续 分枝。即 3≤x1≤2。 求LP22,如图所示。无可行 解,故不再分枝。

1 1 3
x1
P21

? x1 ? x 2 ≥ ? 2 ? x1 ? x 2 ≥ ? 2 ? ? ? 5 x1 + 6 x 2 ≤ 30 ? 5 x1 + 6 x 2 ≤ 30 ? x1 ? x1 ≤4 ≤4 ? ? ≥2 IP x ( 212) ( IP 211) ? x1 ≥2 ? 1 ? x ? x ≤3 ≤3 ? 2 ? 2 ? ≥ x 3 ? x1 ≤2 1 ? ? ? x1 , x 2 ≥ 0 且 为 整 数 ? x1 , x 2 ≥ 0 且 为 整 数
分别求出(LP211)和(LP212)的最优解
P22

先求(LP211),如图所示。此时 在E点取得最优解。即
x1=2, x2 =3, f(211)=17

分枝定界法

A B

找到整数解,问题已探明,此枝x2 停止计算。 求(LP212),如图所示。此时 3 F在点取得最优解。即x1=3, x2 =2.5,
f(212)=31/2≈15.5 < Z(211)



?

C

E

(18/11,40/11) D F

?


?

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

LP x1=18/11, x2=40/11 (0) f =19.8 x1≤1 LP1 x1=1, x2=3 f(1) =16 # x2≤3 LP21 x1=12/5, x2=3 (21) f =17.4 x1≥3 LP212 x1=3, x2=5/2 f(212) =15.5 # x1≥2 LP2 x1=2, x2=10/3 f(2) =18.5 x2≥4 LP22 无可 行解 #

如对LP212继续分解,其最大值 也不会大于15.5 ,问题探明,剪 枝。

1
1 3 x1

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

P23

例2 用分枝定界法求解
m ax f = 4 x1 + 3 x 2 ? 1 .2 x 1 + 0 .8 x 2 ≤ 1 0 ? 2 x 1 + 2 .5 x 2 ≤ 2 5 ? ? x , x ≥ 0, 且 均 取 整 数 ? 1 2
解: 先求对应的松弛问题(记为LP0)

分枝定界法
x2

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

10

B

max f = 4 x1 + 3 x2 ?1.2 x1 + 0.8 x2 ≤ 10 ? st ? 2 x1 + 2.5 x2 ≤ 25 ? x1 , x2 ≥ 0 ? ( LP 0 )
C
P25

2x1 + 2.5x2 = 25

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

o

10

P26 1

x

x2
A

增加约束 x1 ≤ 3及x1 ≥ 4得到两个线性规划
max f = 4 x1 + 3 x2 ?1.2 x1 + 0.8 x2 ≤ 10 ? 2 x + 2.5 x ≤ 25 ? 1 2 LP1: ? ? x1 ≤ 3 ? x1 , x2 ≥ 0 ?
max f = 4 x1 + 3x2 ?1.2 x1 + 0.8 x2 ≤ 10 ? 2 x + 2.5 x ≤ 25 ? 1 2 LP 2 : ? ? x1 ≥ 4 ? x1 , x2 ≥ 0 ?

x2 A

选择目标值最大的分枝 LP 2进行分枝,增加约束 x 2 ≤ 6及 x 2 ≥ 7,显然 x 2 ≥ 7不可行,得到线性规划

10

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

10

x2 ≥ 7不可行

max f = 4 x1 + 3 x2 ?1.2 x1 + 0.8 x2 ≤ 10 ? 2 x + 2.5 x ≤ 25 ? 1 2 LP 22 : ? ? x1 ≥ 4,x2 ≥ 7 ? x1 , x2 ≥ 0 ?
max f = 4 x1 + 3 x2

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

B

6
LP1
LP21

LP21:X=(4.33,6),f21=35.33
?1.2 x1 + 0.8 x2 ≤ 10 ? 2 x + 2.5 x ≤ 25 ? 1 2 LP 21: ? ? x1 ≥ 4,x2 ≤ 6 ? x1, x2 ≥ 0 ?

LP1 LP2 o

3

4

C ①

C o


P27

3

4

x1
P28

x2
A

由于 f 21 > f1,选择 LP 21进行分枝,增加约束 x1 ≤ 4 及 x1 ≥ 5,得线性规划 LP 211及 LP 212:
max f = 4x1 + 3x2

?上述分枝过程可用下图表示:
LP0:X=(3.57,7.14),f0=35.7 x 1≤ 3 LP1:X=(3,7.6) f1=34.8 x 2≤ 6 LP21:X=(4.33,6) f21=35.33 x 1≤ 4 LP211:X=(4,6) f211=34 x 1≥ 5 LP212:X=(5,5) f212=35
P30

10

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

? 1.2x1 + 0.8x2 ≤ 10 ?2 x + 2.5x ≤ 25 ? 2 LP211: ? 1 ? x1 ≥ 4,x2 ≤ 6,x1 ≤ 4 ? x1, x2 ≥ 0 ? 即x1 = 4, 可行域是一条线段

x 1≥ 4 LP2:X=(4,6.5) f2=35.5 x 2≥ 7 LP22 无可行解

6
LP1

max f = 4 x1 + 3 x2 ?1.2 x1 + 0.8 x2 ≤ 10 ? 2 x + 2.5 x ≤ 25 ? 1 2 LP 212 : ? ? x1 ≥ 5,x2 ≤ 6 ? x1 , x2 ≥ 0 ?

LP212

C

o

3

4 5

x1
P29

三、割平面法
割平面法是1958年美国学者R. E. Gomory提出的, 所以又称为Gomory的割平面法。
?

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

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

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

P32

如不考虑条件⑤,容易求得相应的线性规划的 最优解:x1=3/4,x2=7/4,max f=10/4

现设想,如能找到像CD那样的直线去切割域R(如图), 去掉三角形域ACD,那么具有整数坐标的C点(1,1)就是 域R′的一个极点,
?

?

它就是图中区域R 的顶点A,但不合 于整数条件。

?

?

如在域R′上求解①~④, 而得到的最优解又恰巧在C点, 就得到原问题的整数解, 所以解法的关键: 就是怎样构造一个这样的 “割平面”CD, 它就是一个新的约束。 尽管它可能不是唯一的, 也可能不是一步能求到的。 下面给出本例完整的求解过程:
P34

P33

?

用单纯形表解松弛问题,见下表2-5-1。

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

Max f=x1+x2 -x1+x2≤ +x1 =1 3 4 4=4 3x1+x2 ≤ +x x1 , x2≥0
⑥ ⑦

CB 0 0

XB x3 x4

b 1 4

σ
… … 1 x1 1 x2 f=5/2
P35

… 3/4 7/4

σ

1 x1 -1 3 1 … 1 0 0

1 x2 1 1 1 … 0 1 0

0 x3 1 0 0 … -1/4 3/4 1/2

0 x4 0 1 0 … 1/4 1/4 1/2
P36

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

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

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

? ? ?

可从最终计算表中得到非整数基变量对应的 关系式:
1 x3 + 4 3 x2 + x3 + 4 x1 ? 1 3 x4 = 4 4 7 1 x4 = 4 4

(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 然后将整数部分与分数部分分开,移到等式左右两边,得 到:

x1 ? x 3 = x2 ? 1 =

3 ?3 1 ? ? ? x 3 + x4 ? 4 ?4 4 ? 3 ?3 1 ? ? ? x 3 + x4 ? 4 ?4 4 ?
P38

P37

现考虑整数条件⑤:要求x1、x2都是非负整数
?

于是由条件⑥、⑦可知 ,

x3、x4也都是非负整

数, 这一点对以下推导是必要的,如不都是整数, 则应在引入x3、x4之前乘以适当调整系数和常数, 使之都是整数。

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

3 3 1 ? ( x3 + x4 ) ≤ 0 4 4 4

x1 ? x 3 = x2 ? 1 =

3 ?3 1 ? ? ? x3 + x4 ? 4 ?4 4 ? 3 ?3 1 ? ? ? x3 + x4 ? 4 ?4 4 ?

P39

P40

3 3 1 ? ( x3 + x4 ) ≤ 0 4 4 4
即 -3x3-x4≤-3 ⑧ 这就得到一个切割方程(或称为切割约束), 将它作为增加约束条件,再解例3。 ? 引入松弛变量x5,得到等式 ? -3x3-x4+x5=-3 ? 将这新的约束方程加到表2-5-1的最终计算表, 得表2-5-2。
?

表2-5-2

CB 1 1 0 zj-cj

cj XB x1 x2 x5

b 3/4 7/4 -3 5/2

1 x1 1 0 0 0

1 x2 0 1 0 0

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

0 x4 1/4 1/4 -1 1/2

0 x5 0 0 1 0

从表2-5-2的b列中可看到,这时得到的是非可行解 ,于是需要用对偶单纯形法继续进行计算。 选择x5为换出变量,计算
? ?1 ?1 ? ? cj ? zj ? a lj < 0 ? = min ? 2 , 2 θ = min ? ? a ? j ? ?3 ?1 lj ? ? ? ? ? ? 1 ?= ? 6 ? ?

P41

将x3做为换入变量,再按原单纯形法进行迭代,得 下表
cj CB XB 1 x1 1 x2 0 x3 zj-cj b 1 1 1 2 1 x1 1 0 0 0 1 x2 0 1 0 0 0 x3 0 0 1 0 0 x4 1/3 0 1/3 1/3 0 x5 -1/12 1/4 -1/3 1/6

几何解释:新得到的约束条件⑧ -3x3-x4≤-3
?

?

?

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

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

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

2、从(LP)的最优解中, 任选一个不为整数的分量xr,, 将最优单纯形表中该行的系数arj′和 br ′分解为 整数部分和非负真分数部分之和, 并以 该行为源行,按下式作割平面方程:

zr

?

j = m +1



n

z rj x j



0

b r′ 的非负真分数部分
P45

a′ rj

的非负真分数部分
P46

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

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

max s.t .

f = 3 x1 + 2 x2 ?2 x1 + 3 x2 ≤ 14 ? ? x1 + 0.5 x2 ≤ 4.5 ? x , x ≥ 0, 且均取整数值 ? 1 2

P47

P48

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

第二步:
x2 +

max s.t .

f = 3 x1 + 2 x2

?2 x1 + 3 x2 ≤ 14 ? s.t . ? x1 + 0.5 x2 ≤ 4.5 ? x , x ≥ 0, 且均取整数值 ? 1 2
cB
2 3

G 0:

max

f = 3 x1 + 2 x2 ?2 x1 + 3 x2 ≤ 14 ? ?2 x1 + x2 ≤ 9 ?x , x ≥ 0 ? 1 2
x3 1/2 -1/4 1/4 x4 -1/2 3/4 5/4

1 1 1 x3 ? x4 = 2 2 2 2 1? 1? 1? ? ? ? x 2 + ? 0 + ?x 3 + ? ? 1 + ?x 4 = ? 2 + ? 2? 2 2 ? ? ? ? ? 1 1 1 x2 ? x4 ? 2 = ? x3 ? x4 2 2 2 因为x3,x4≥0 x2
1 1 1 1 ? x3 ? x4 ≤ < 1 2 2 2 2 1 1 1 ? x3 ? x4 ≤ 0 2 2 2 1 1 1 ? x3 ? x4 + x5 = 0 2 2 2

? x 3 = 14 ? 2x1 ? 3x 2 ? ? x 4 = 9 ? 2x 1 ? x 2
1 1 1 ? x3 ? x4 ≤ 0 2 2 2 2x 1 + 2x 2 ≤ 11
× × × × × × × × × ×

xB
x2 x1 Zj-cj

b
5/2 13/4

x1 0 1 0

x2 1 0 0

P49

O

P501

x

第三步:将Gomory约束加到G0中得到新的线 性规划问题G1如下:

CB 2 3 0 2 3 0

Cj XB x2 x1 x5 zj-cj x2 x1 x3 zj-cj

b
2 1 2

2 x1 0 1 0 0 0 1 0 0

3 x2 1 0 0 0 1 0 0 0

0 x3 1/2 -1/4 [-1/2] 1/4 0 0 1 0

0 x4 -1/2 3/4 -1/2 5/4 -1 1 1 1

0 x5 0 0 1 0 1/2 -1/2 -2 1/2

max
G 1:

f = 3 x1 + 2 x2

1 3 4

s.t .

? 2 x1 + 3 x2 + x3 = 14 ? 2 x1 + x2 + x4 =9 ? ? ? 1 1 1 ? x3 ? x 4 + x5 = ? ? 2 2 2 ? 0 ( 1, ,5) x ≥ j = " ? ? j

-1/2 2
3 1 2

1

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

?

1 x 2

5

= 3

1 2
P52

1 1 x1 + x 4 ? x 5 = 3 2 2 1 1 x1 + x 4 ? x 5 + x 5 = 3 + 2 2 1 1 x1 + x 4 ? x 5 ? 3 = ? x 5 2 2

1 1 ? x5 ≤ 0 2 2 1 1 ? x5 + x6 = 0 2 2

CB
2 3 0 0 2 3 0 0

Cj XB
x2 x1 x3 x6 zj-cj x2 x1 x3 x5 zj-cj

b
2
3 1 2

2 x1 0 1 0 0 0 0 1 0 0 0

3 x2 1 0 0 0 0 1 0 0 0 0

0 x3 0 0 1 0 0 0 0 1 0 0

0 x4 -1 1 1 0 1 -1 1 1 0 1

0 x5 1/2 -1/4 -1 [-1/2] 1/2 0 0 0 1 0

0 x6 0 0 0 1 0 2 -1 -4 -2 1

1 -1/2 1 4 3 1

G 2:

m ax

f = 3 x1 + 2 x 2 ? ? 2 x1 + 3 x 2 + x 3 = 14 ? + x4 = 9 ? 2 x1 + x 2 ? 1 1 1 ? ? x3 ? x4 + x5 = ? ? 2 2 2 ? 1 1 ? x x ? + = ? 5 6 ? 2 2 ? ? ? x j ≥ 0 ( j = 1, " , 6 )
P53

s .t .

P54

1 1 ? x5 ≤ 0 2 2

G2 :

max

f = 3 x1 + 2 x 2 ? ? 2 x1 + 3 x 2 + x 3 = 14 ? + x4 =9 ? 2 x1 + x 2 ? 1 1 1 ? ? x ? x + x =? ? 3 4 5 2 2 2 ? 1 1 ? x x ? + = ? 5 6 ? 2 2 ? ? ? x j ≥ 0 ( j = 1, " , 6)

?

s .t .

1 1 1 ? x3 ? x4 + x5 = 0 2 2 2 ? x 3 = 14 ? 2x 1 ? 3x 2 ? ? x 4 = 9 ? 2x 1 ? x 2

x2

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

x1 + x2 ≤ 5
O

× × × × × × × × × ×

x1
P55 P56

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

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

max f = 3 x1 -2 x2 + 5 x3 s.t . x1 + 2 x2 ? x3 ≤ 2 x1 + 4 x2 + x3 ≤ 4 x1 + x2 ≤3 4 x 2 + x3 ≤ 6 x1 , x2 , x3 = 0或1

IP0

解:

(1)通过观察、试探得一可行解 X 0 = (1, 0, 0)T ,目标函数值为 f 0 = 3 。

(2)增加过滤条件:f ≥ 3, 即 3 x1 ? 2 x2 + 5 x3 ≥ 3, 得新问题IP 1 (3)求解新问题IP 1。 求解过程中,先对每个状态点检验f ≥ 3是否成立,一般可减少计算量。

P57

P58

max f = 3 x1 -2 x2 + 5 x3 s.t. x1 + 2 x2 ? x3 ≤ 2 x1 + 4 x2 + x3 ≤ 4 x1 + x2 ≤3 4 x2 + x3 ≤ 6 3 x1 -2 x2 + 5 x3 ≥ 3 x1 , x2 , x3 = 0或1

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

×

IP 1

XT
IP 1

×

f 值

max f = 3 x1 -2 x2 + 5 x3
s.t. x1 + 2 x2 ? x3 ≤ 2 x1 + 4 x2 + x3 ≤ 4 x1 + x2

√ × × √ √ × ×

IP 1

≤3

4 x2 + x3 ≤ 6 3 x1 -2 x2 + 5 x3 ≥ 3
x1 , x2 , x3 = 0或1

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

表1

XT

f ≥3

f值

练习题

×

表2

f值 XT f ≥5

×

表3

XT

f ≥8

f值

× × × ×

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


推荐相关:

规划数学ch2-5.pdf

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


规划数学ch2-2.pdf

规划数学ch2-2 - 第二节 单纯形法 一、基本理论 1.基本概念 1)可行域


ch2-5线性方程组的应用_图文.pdf

ch2-5线性方程组的应用 - 实验2-5线性方程组的应用 教学目标 教学重点


规划数学ch2-3.pdf

规划数学ch2-3 - 第三节 对偶规划 一、对偶线性规划问题 ?max f =


ch5 动态规划.ppt

ch5 动态规划_数学_自然科学_专业资料。Page 1 第五章 动态规划第一节 多阶段决策过程及实例 Page 2 动态规划是运筹学的重要分支之一,它是解 决多阶段决策...


6讲:ch2-5样条函数插值_图文.ppt

6讲:ch2-5样条函数插值 - 插值法 第五节 样条插值法 样条插值的研究背景


ch5-1整数规划的数学模型_图文.ppt

ch5-1整数规划的数学模型 - 运筹学 Operations Research Chapter 5 整数规划 Integer Programming 1.整数规划数学模型Mathematic...


高等数学ch2_5_图文.ppt

高等数学ch2_5 - 2.5 函数的连续性 2.5.1 函数的改变量 2.5.


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

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


ch5 动态规划_图文.ppt

ch5 动态规划_数学_自然科学_专业资料。Page 1 第五章 动态规划第一节 多阶段决策过程及实例 Page 2 动态规划是运筹学的重要分支之一,它是解 决多阶段决策...


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

数学建模作业5数学规划模型---供应与选址的问题 - 一、问题提出 某公司有 6


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

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


运筹学 CH5动态规划_图文.ppt

运筹学 CH5动态规划 - Chapter5 动态规划 (Dynamic programming) 本章主要内容: 多阶段决策问题 动态规划的基本概念 最优性原理 建模的一般步骤 动态规划应...


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

数学物理方法姚端正CH5作业解答_理学_高等教育_教育专区。数学物理方法姚端正CH7作业解答 数理方法 CH5 作业解答 P82 习题 5.1 1. 求下列函数在指定点处的留数...


数学技巧线性规划_图文.ppt

数学技巧线性规划 - Ch13:合售作介 指老:源教授 M95


ch5-1,2(数学)_图文.ppt

ch5-1,2(数学) - 第五章 模型的建立与估计中 的问题及对策 一、误设定


CH5区组设计2(组合数学)_图文.ppt

CH5区组设计2(组合数学) - 5 区组设计简介 区组设计理论是组合数学的一个


离散数学ch5_图文.ppt

离散数学ch5 - 第章 一阶逻辑等值演算与推理 主要内容 ? 一阶逻辑等值式


数学规划模型供应与选址问题.doc

数学规划模型供应与选址问题_数学_自然科学_专业...目前有两个临时料场位于 A(5,1),B(2,7),日...新料场程序: function f=liaoch(x) a=[1.25 8...


第五章 目标规划目标规划的图解法运筹学基础及其应用胡....ppt

章 目标规划目标规划的图解法运筹学基础及其应用胡运权第五版_数学_自然科学_专业资料。§5.2目标规划的图解法 The Graphical Method of GL Ch5 Goal ...

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