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

杨利霞

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

0 Q, |( N% V6 C3 x" ~2.1 基本概念
0 N; a0 L4 e, {! j) {
整数规划：数学规划中的变量（部分或全部）限制为整数
: D9 i- m( N5 K; h( V# a目前只能求解整数线性规划
+ h0 u: Z% Y* k' Q/ @. z整数规划的解有如下三种情况：
# w' |. ~& q5 X* v2 w" c3 w- k' T
没有可行解（最优解不是整数）
3 A- O: m1 o+ k9 Q" O存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划
# ?2 P* D; m3 i: g) C
定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件

5 [( ]* t8 |9 U* R; V引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
% L2 Y  d$ w6 u; I. y改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
0 j( E% X3 B& s" b$ r/ T& B

6 k6 d; a! K0 g- Q- R  f( K6 n( H需保证只有一个起作用，则引进m个0-1变量：
+ w7 y$ s0 F* o' B& x

7 o& l6 R; r, @, Z0 V7 l' q) w( {和一个充分大的常数M，则有：

- O0 r; Y8 H' j+ I1 I: ?2.2.2 混合整数规划（固定费用）

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

1 a6 o. e* P: E& t2 W
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
! N6 r( m+ v' u/ ~+ s' l, [& \- L上式即代替了该分段函数：

; x, f! E8 C- R" u/ n3 y

7 `  f3 p  {6 m3 l  U  C6 e2.2.3 指派问题

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

7 }/ m0 N! l$ y2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
+ D4 S1 y; i" [8 G% Amatlab程序如下：
6 d- l" z6 Z1 Y  定义目标函数 f 和约束向量函数 g

: x% y$ [. l( ?  p2 [
# _* ]) P" V& Z% }+ a' y求解问题
" [( q) z3 a* }1 h- H) T
- ^& s$ h) x! }) U- D
2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
. v, W+ m$ N/ P) Y  标准形式为：

) u; k# n+ k- W( c- M% \


————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
: p5 [6 a; [$ P. L原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
8 ]' ^2 Y/ k2 F) n4 ?& m

————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
/ _$ t2 k8 B4 x9 q; x* Y' @