运筹学] 整数编程（整数编程问题解决方案的特点 | 整数编程问题和松弛问题示例）

文章目录

一、整数规划问题解的特征

二、整数规划问题 与 松弛问题 示例

一、整数规划问题解的特征

整数规划问题解的特征 :

① 整数规划问题 与 松弛问题 可行解集合关系 : 整数规划问题 可行解集合 , 是该整数规划问题的 松弛问题 可行解集合 的子集 , 任意两个可行解的 凸组合 , 不一定满足整数约束条件 , 不一定是可行解 ;

② 整数规划问题 与 松弛问题 最优解关系 : 整数规划问题的可行解 一定是 其 松弛问题的可行解 , 松弛问题的可行解不一定是整数规划问题的可行解 , 整数规划问题的最优解 不会优于 松弛问题的最优解 ;

松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;

二、整数规划问题 与 松弛问题 示例

假设有如下整数规划问题 :

m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0   并 且 为 整 数

maxZ=x1+x2s.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪14x1+9x2≤51−6x1+3x2≤1x1,x2≥0 并且为整数

maxZ=x1+x2s.t{14x1+9x2≤51−6x1+3x2≤1x1,x2≥0 并且为整数

maxZ=x

1

+x

2

s.t

⎩

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎧

 

14x

1

+9x

2

≤51

−6x

1

+3x

2

≤1

x

1

,x

2

≥0 并且为整数

上述整数规划问题对应的松弛问题 : 松弛问题 比 整数规划问题 条件少一些 , 整数规划问题比松弛问题变量限制多一条 " 约束变量必须都是整数 " ;

m a x Z = x 1 + x 2 s . t { 14 x 1 + 9 x 2 ≤ 51 − 6 x 1 + 3 x 2 ≤ 1 x 1 , x 2 ≥ 0

maxZ=x1+x2s.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪14x1+9x2≤51−6x1+3x2≤1x1,x2≥0

maxZ=x1+x2s.t{14x1+9x2≤51−6x1+3x2≤1x1,x2≥0

maxZ=x

1

+x

2

s.t

⎩

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎧

 

14x

1

+9x

2

≤51

−6x

1

+3x

2

≤1

x

1

,x

2

≥0

使用图解法 , 解上述 松弛问题 的最优解为 { x 1 = 3 2 x 2 = 10 3

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x1=32x2=103

{x1=32x2=103

⎩

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎧

 

x

1

=

2

3

x

2

=

3

10

此时目标函数值 m a x Z = x 1 + x 2 = 29 6 \rm maxZ = x_1 + x_2 = \cfrac{29}{6}maxZ=x

1

+x

2

=

6

29

简单的将其松弛问题最优解上下取整 , 得到的四个点 , 如上图的四个红色点 , 都不在可行域中 , 选择的整数解 , 必须在可行域中 ;

根据 整数规划问题的的松弛问题 的最优解 , 如何找其 整数规划问题 的整数最优解 , 是整数规划问题的核心问题 ;

穷举法 ( 有局限性 ) : 直接看上图中可行域内的整数点 , 然后再逐一代入目标函数 , 得到一个 整数规划问题 的最优解 , 但是这种方法无法推广应用 , 如果点的个数比较多 , 如几万个 , 变量的维数多 , 如 10 1010 个约束变量 , 这种方法肯定不适用 ;

整数规划问题的求解方法有 : ① 分支定界法 , ② 割平面法 ;

推荐使用 分支定界法 ;