数学建模算法与应用第二章：整数规划

杨利霞

数学建模算法与应用第二章：整数规划
* d  C! w- u$ g! ~, g( s+ k! D+ u
2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
. M1 r" n8 Q+ B目前只能求解整数线性规划
整数规划的解有如下三种情况：
5 p2 S7 w  o. S
没有可行解（最优解不是整数）
: q# G8 q+ |3 m存在最优解（最优解为整数）
+ m3 V' S0 T# z& o' B3 f4 `$ A有可行解（最优解值变差）
2.2 0-1整数规划
1 M* m0 U! r) y7 a- Q7 ~
定义：变量x仅取值0或1，即0-1变量
1 D3 I$ F. f9 `9 X+ f& ?
- s/ s" Z. S; c! W6 y2 X- [5 E2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
  }0 B5 u, }1 o- `( o( {* N, a改为普通的约束条件（不常用）
3 y1 t# H" F0 l% @2 H+ u$ m# V) Z若有m个互相排斥的约束条件

1 \8 q  F  B: V9 W
需保证只有一个起作用，则引进m个0-1变量：


% f6 ~' ^2 Z+ X5 U, S6 }" G; D; _和一个充分大的常数M，则有：
  h( y, i2 s5 s" ]% `: v
2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
可用约束条件：

7 E5 S( f, G6 a7 K0 \6 d, P% W
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

# K" M* H. W) B9 G( k: b  {
1 G* I$ l6 n( n6 d) v" m. v
2.2.3 指派问题

关键：给出系数矩阵C
9 `2 ?7 G2 R) C2 P) G. k规划模型为：（x为引入的0-1变量）

( i/ f3 J& g" B* v. A

9 x7 e8 Y* ^* q( X2 E1 ?2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
- c! o. u6 c% gmatlab程序如下：
  定义目标函数 f 和约束向量函数 g

9 y3 \# X% Y  V  u2 l+ }6 w求解问题


) C) D( B2 D8 @5 p8 C) l3 p) T- T2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
6 ^, G5 o# V# C/ F  标准形式为：

4 B; g5 W1 k, y6 Q0 D+ }; k
————————————————

7 P/ j. e& G, \$ K5 _1 J5 l版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
8 V8 Z2 z# K$ f9 s" z原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

! H, r  |' z8 Q- @
————————————————
9 n! l* [+ H' `8 m原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

, X" X" v( e7 m+ n