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

杨利霞

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

2.1 基本概念
4 @0 [3 V. n! Q4 P4 X
2 Y' j) D9 |2 l) [) [整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
) h- \; j+ x  F6 e/ s整数规划的解有如下三种情况：
( O/ ^2 ?  U1 g  K  E: x  }& t4 i
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划

" \5 L1 O  w2 C  M定义：变量x仅取值0或1，即0-1变量
; x" L+ `7 _6 k$ X
- \1 q5 Q8 H$ C' d2 m2.2.1 相互排斥的约束条件
, _/ k" K9 d6 O6 E/ T5 ?$ }: s
& Q- S+ E$ z+ _$ Q4 {( c( r引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
3 [0 }; ]+ s* p# F- I改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
1 R* X8 W! R! Y# G

6 t/ v8 t% O+ R; C- n  _+ ?/ I: t
' d1 e1 i4 N( d6 l需保证只有一个起作用，则引进m个0-1变量：

$ }- y9 w* O5 x  \' ~8 X
和一个充分大的常数M，则有：

2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
; l5 T/ e! b- [: \. ~& D  s可用约束条件：

; |5 V1 w( Z$ t) w- [7 @y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

9 t$ H2 v) M  f& N' y6 \
. v  X4 S& |1 w% Q2.2.3 指派问题

关键：给出系数矩阵C
规划模型为：（x为引入的0-1变量）

. Y5 V% x5 j" _, [; k2 W

2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
  定义目标函数 f 和约束向量函数 g

7 F- q' D7 Q. p4 B1 O
, d- J& u  b5 C$ @( ^4 j求解问题

' D2 `* j# Q0 T) \4 p# q2 x: {
6 N9 q9 @4 A. j2.4 整数线性规划的计算机求解

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

- E, ~9 V$ J& F( ^, L5 K  o( D! H5 d. E

9 C; ~4 s, H& [4 F————————————————
1 c$ D- j; m) m$ a
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
1 _7 A* H/ T9 \/ B+ ^原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
2 A6 U, c/ [1 F7 o; L" f+ ?, M
8 o6 ^6 g8 L& A  O
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231