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

杨利霞

数学建模算法与应用第二章：整数规划
- s- Y6 X. k4 w" O
( W7 o! Y; }3 j2 f2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
, i' j) C3 }' q7 D. |' p整数规划的解有如下三种情况：

& ~0 S+ U3 D8 @没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
, ~& o9 `# _6 y7 V3 ]: i: ~2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量
0 a/ V% h  F. S9 q! G
2.2.1 相互排斥的约束条件
9 }  _  W: l4 Y  o( b) p) O5 P
引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
" m/ q# q( x# N! s" Y0 P" L) T若有m个互相排斥的约束条件
- v6 U' w: t( k/ U9 v

. @( q4 {$ R0 R2 V  M! f( l: G需保证只有一个起作用，则引进m个0-1变量：


和一个充分大的常数M，则有：
6 [5 z1 n- t: }: I. n
  o! a0 a* E8 s. \) b# b/ G2 h2.2.2 混合整数规划（固定费用）

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

" ^  F# [0 O/ g6 h3 G) g4 E
: p& J5 s. J5 V1 H# X0 S5 Iy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
9 j/ m4 s0 o: h0 ]1 J. ]5 a6 u2 n
' t% z- ^0 R( P. |) L7 ?4 a* R( |
1 \9 d& I  R+ S( r& M. w# ~
, Y' l9 I! d! p% L2 r. ]' Q2.2.3 指派问题

关键：给出系数矩阵C
  O6 a/ X3 H5 q0 v规划模型为：（x为引入的0-1变量）

& m/ _0 O; O% J1 n% o: |1 Q
4 g. P' Q5 S9 j6 ~1 T- @; @
2.3 蒙特卡洛法（随机取样法）

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

3 N2 _& Z& E2 ~1 ]' y/ o' p  J求解问题


5 P* _1 I$ u) ?8 x+ c8 v, b# e2 p2.4 整数线性规划的计算机求解

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

  A1 s' \, z5 }9 Y" I; w

! m; u4 @. r& m9 P+ }% D9 U  j2 L
————————————————
$ G9 A/ o- f9 j
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
/ k. H; @$ v$ I- L" w# ~6 [. Y原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
( S5 k9 C1 k& E6 \- }
% \% A, s" U7 Z: C
0 I4 V& n. A5 S8 V2 o  \————————————————
2 j( }4 _9 U) U6 c/ o% R原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231