【运筹学】整数规划 ( 整数规划示例 | 整数规划解决的核心问题 )

2023-03-28 20:49:45 浏览数 (1)

文章目录

  • 一、整数规划示例
  • 二、整数规划解决的核心问题

一、整数规划示例

资金总额

rm B

, 有

n

个投资项目 , 项目

j

所需的投资金额 是

a_j

, 预期收益是

c_j

,

j = 1,2,cdots,n

;

投资还有以下附加条件 :

① 如果投资项目

1

, 必须投资项目

2

; 反之如果投资项目

2

, 没有限制 ;

② 项目

3

和 项目

4

必须至少选

1

个 ;

③ 项目

5,6,7

只能选择

2

个 ;

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

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

每个项目有对应的两个选择 , 投资 / 不投资 , 分别使用

1

和

0

表示 ;

令

x_j

表示第

j

个项目的投资选择 , 投资

1

, 不投资

0

; (

j = 1,2, cdots, n

)

投资额约束条件 : 所有的投资总额不能超过

rm B

,

sum_{j = 1}^{n} a_{j} x_j leq B

;

分析条件 ① : 投资项目

1

, 必须投资项目

2

, 此时

x_1 = x_2 = 1

; 投资项目

2

可以投资项目

1

, 可以不投资项目

1

, 同时投资的情况上面已经分析过 , 分析后者

x_1 = 1, x_2 = 0 , 此时 x_1 > x_2

; 综合上述两种情况就有

x_2 geq x_1

;

分析条件 ② : 项目

3

和 项目

4

必须至少选

1

个 , 两者选择一个 , 或者都选择 , 二者相加之和是

1

或

2

; 有约束方程

x_3 x_4 geq 1

;

分析条件 ③ : 项目

5,6,7

只能选择

2

个 , 则三者相加等于

2

即可 ; 约束方程

x_5 x_6 x_7 = 2

;

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

begin{array}{lcl} rm maxZ = sum_{j = 1}^{n} c_j x_j \\ rm s.tbegin{cases} rm sum_{j = 1}^{n} a_{j} x_j leq B \\ rm x_2 geq x_1 \\ rm x_3 x_4 geq 1 \\ rm x_5 x_6 x_7 = 2 \\ rm x_j = 0 , 1 ( j = 1, 2, cdots , n ) end{cases}end{array}

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

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

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

给出 整数规划问题 ,

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

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

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

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

变量 博客 解决方案

0 人点赞