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

杨利霞

数学建模算法与应用第二章：整数规划
9 `) E$ V7 q5 I" r+ [
2.1 基本概念
9 l8 q* R+ Q9 Z" ~
6 \8 P5 X: k$ e8 {6 i整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：
) B! C* i0 b9 e; M, m* j, ^
( B2 h: B; A8 q+ ]8 B) h没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划
! e. v  Q. F$ V# X$ b& D
" l: B; j8 Y' b* v3 D5 Q定义：变量x仅取值0或1，即0-1变量
/ ?" l9 O- q3 M" z8 H' r, g2 K9 Q% {9 k
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
4 Z, ]) Q- ^+ z- m7 ], u1 P9 s改为普通的约束条件（不常用）
若有m个互相排斥的约束条件


% f$ P3 o6 N# N4 R1 B( z3 \5 F4 V2 v需保证只有一个起作用，则引进m个0-1变量：
% `4 i* n& {9 f: u, R; d. c

和一个充分大的常数M，则有：

/ a" _8 l6 C2 Q5 x9 O2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
% C6 i" B. X' g' m可用约束条件：

y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：


( n1 D5 l* |8 S. G- ^' U
2.2.3 指派问题

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

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

目的：求解非线性整数规划
matlab程序如下：
. Q3 J; d8 ^# L. J  定义目标函数 f 和约束向量函数 g

" T9 Y' e4 }( |8 t. r: q" D
1 K; _" b- ~6 }- w求解问题

' c3 [: q9 `, C" X8 q  R
3 ?6 b; u) D- g* x2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
) ]2 J) M/ N$ ]. m; J5 m3 e  标准形式为：

) X* A/ a3 J+ \. w- n

+ U& i2 X$ Z3 ^  d0 _% ?

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

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
' B5 X# d6 n" n! S% N8 A. c0 W
; P7 _2 x- ^2 U' r: W1 q0 z3 C; u
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

- ?0 e/ r+ q/ W