[运筹学] 整数编程 ( 整数编程示例 | 整数编程解决的核心问题 )

文章目录

一、整数规划示例

二、整数规划解决的核心问题

一、整数规划示例

资金总额 B \rm BB , 有 n nn 个投资项目 , 项目 j jj 所需的投资金额 是 a j a_ja

j

 , 预期收益是 c j c_jc

j

 , j = 1 , 2 , ⋯   , n j = 1,2,\cdots,nj=1,2,⋯,n ;

投资还有以下附加条件 :

① 如果投资项目 1 11 , 必须投资项目 2 22 ; 反之如果投资项目 2 22 , 没有限制 ;

② 项目 3 33 和 项目 4 44 必须至少选 1 11 个 ;

③ 项目 5 , 6 , 7 5,6,75,6,7 只能选择 2 22 个 ;

决策变量分析 : 选择合适的 决策变量 与 决策变量取值 ;

选取变量 , 使得变量的一组取值 , 能更好对应线性规划问题的解决方案 ;

每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用 1 11 和 0 00 表示 ;

令 x j x_jx

j

 表示第 j jj 个项目的投资选择 , 投资 1 11 , 不投资 0 00 ; ( j = 1 , 2 , ⋯   , n j = 1,2, \cdots, nj=1,2,⋯,n )

投资额约束条件 : 所有的投资总额不能超过 B \rm BB , ∑ j = 1 n a j x j ≤ B \sum_{j = 1}^{n} a_{j} x_j \leq B∑

j=1

n

a

j

x

j

≤B ;

分析条件 ① : 投资项目 1 11 , 必须投资项目 2 22 , 此时 x 1 = x 2 = 1 x_1 = x_2 = 1x

1

=x

2

=1 ; 投资项目 2 22 可以投资项目 1 11 , 可以不投资项目 1 11 , 同时投资的情况上面已经分析过 , 分析后者 x 1 = 1 , x 2 = 0 , 此 时 x 1 > x 2 x_1 = 1, x_2 = 0 , 此时 x_1 > x_2x

1

=1,x

2

=0,此时x

1

>x

2

 ; 综合上述两种情况就有 x 2 ≥ x 1 x_2 \geq x_1x

2

≥x

1

 ;

分析条件 ② : 项目 3 33 和 项目 4 44 必须至少选 1 11 个 , 两者选择一个 , 或者都选择 , 二者相加之和是 1 11 或 2 22 ; 有约束方程 x 3 + x 4 ≥ 1 x_3 + x_4 \geq 1x

3

+x

4

≥1 ;

分析条件 ③ : 项目 5 , 6 , 7 5,6,75,6,7 只能选择 2 22 个 , 则三者相加等于 2 22 即可 ; 约束方程 x 5 + x 6 + x 7 = 2 x_5 + x_6 + x_7 = 2x

5

+x

6

+x

7

=2 ;

投资问题可以表示为以下线性规划 :

m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a j x j ≤ B x 2 ≥ x 1 x 3 + x 4 ≥ 1 x 5 + x 6 + x 7 = 2 x j = 0 , 1     (   j = 1 , 2 , ⋯   , n   )

maxZ=∑nj=1cjxjs.t⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∑nj=1ajxj≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=0,1   ( j=1,2,⋯,n )

maxZ=∑j=1ncjxjs.t{∑j=1najxj≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=0,1   ( j=1,2,⋯,n )

maxZ=∑

j=1

n

c

j

x

j

s.t

⎩

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎧

 

∑

j=1

n

a

j

x

j

≤B

x

2

≥x

1

x

3

+x

4

≥1

x

5

+x

6

+x

7

=2

x

j

=0,1   ( j=1,2,⋯,n )

根据 【运筹学】整数规划 ( 相关概念 | 整数规划 | 整数线性规划 | 整数线性规划分类 ) 博客中的整数线性规划概念 , 上述线性规划是 整数线性规划 ;

上述整数线性规划 的 松弛问题 是一个线性规划 , 可以使用单纯形法对其进行求解 , 求出最优解后 , 可能是小数 , 那么如何得到整数问题的最优解 , 不能进行简单的四舍五入 ;

二、整数规划解决的核心问题

给出 整数规划问题 ,

先求该 整数规划的松弛问题 的解 ,

松弛问题就是不考虑整数约束 , 将整数线性规划当做普通的线性规划 , 使用单纯形法求出其最优解 ;

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

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