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

杨利霞

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

2.1 基本概念
3 y! L) s4 s7 @& n& d; u$ R
4 O. F9 f6 c6 Z( u& d整数规划：数学规划中的变量（部分或全部）限制为整数
$ k: x8 p# N/ B7 {目前只能求解整数线性规划
$ s1 c, m* i' Y* e% l$ K整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
) g0 A0 q$ |6 ^5 x有可行解（最优解值变差）
7 C( E% c0 h  F) R7 @2.2 0-1整数规划
) r  j- l; C+ S% H8 b4 i' N" S
( ^* Q" u; J% P3 c' E/ w定义：变量x仅取值0或1，即0-1变量
2 I% q' K/ x5 z  m* E& Q/ ~
2.2.1 相互排斥的约束条件
& D) ~; \  v5 u+ J" O; ~& c/ P
+ z6 w: w& R  y0 k9 y  K) g$ C引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
' Z$ d1 F3 X/ b+ _改为普通的约束条件（不常用）
, _+ c9 \" t- `; B: j若有m个互相排斥的约束条件

' {+ N" f; C9 l9 i: X* k
需保证只有一个起作用，则引进m个0-1变量：


7 p1 E( f. ~4 V; _, u- T# j, U和一个充分大的常数M，则有：

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

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

. q- s2 t# u$ U8 E0 Oy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

) |8 L& n2 J  ~0 A

. s, y( Y9 q  X5 I6 ]7 K2.2.3 指派问题

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

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

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

3 j8 Z( c6 p( K1 _5 u2 L4 _求解问题
) u) M$ r* e/ x: Z# W8 f6 e
9 ~& l& O) h. w9 O
$ A( c( ?* y1 J6 L2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
6 s7 r& j0 j/ o; E- C4 H  j  标准形式为：

8 z3 \" s3 ^+ R; g( s
- x- o$ @  m0 p, N
) z4 F2 d  R- g* N1 K6 a————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
" V7 G# J& [3 y0 S4 W  V$ }原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

0 Y; P( `8 Z' N  Q
# e" K- [4 W: W# {8 {& i  K————————————————
8 s8 @( x, j  J6 K2 d7 r6 C9 l原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
+ Z+ Z4 O% u$ n# K  ~) ^

- y* f$ ~; h- n8 }1 B  w