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

杨利霞

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

: m9 z5 a# f- c) d( a: k" L, I/ f1 z2.1 基本概念
! _1 _# m7 Q% K
, S, \4 `$ e! ^1 J1 ]# U整数规划：数学规划中的变量（部分或全部）限制为整数
2 b' H; b4 {  ?) q1 @. }0 ~# p0 C4 E目前只能求解整数线性规划
整数规划的解有如下三种情况：

# ^5 w- s, h* L9 ^1 C0 P6 C没有可行解（最优解不是整数）
存在最优解（最优解为整数）
' _2 e0 Z1 L) F9 ]. R0 o# q有可行解（最优解值变差）
, S+ ^5 p% e3 n2 X+ ^1 k8 j2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件

) k; u& S8 s& x! O1 }/ L9 c引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
! K! x; v* q2 U2 O若有m个互相排斥的约束条件


/ L; T4 r5 i" z+ l6 x需保证只有一个起作用，则引进m个0-1变量：
5 j& R8 k9 L% y! e

- L- |6 G' @8 `- I和一个充分大的常数M，则有：
6 M: r' |" c8 V8 v1 U! `6 H
) X% k' C, P1 o1 |2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
, L* Y$ B( P) d2 w% w' D$ K: G可用约束条件：

" T$ @9 c; }4 H5 h4 M% ?
5 ^8 h8 G% Y; b2 x$ v" y1 xy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
: ?! H) V$ e5 [; U) C5 A- W
$ Z% s0 t1 x+ N; R7 h0 k
' Q4 X  o# ^/ o# j% i3 P, U- q
2.2.3 指派问题

关键：给出系数矩阵C
3 u  H) v% ^/ ]$ w  W规划模型为：（x为引入的0-1变量）

0 @! g  r% Y/ F7 w

' ^  x/ G/ y9 z5 J( Y2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
" g7 H1 N& a9 o5 i, [& F& O8 W( Omatlab程序如下：
  定义目标函数 f 和约束向量函数 g

求解问题


2.4 整数线性规划的计算机求解

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

* m+ C5 w3 W. |- I: s- Z1 z% Z
: T0 W* O0 d+ k
: I$ y4 v( k: s/ R
————————————————

4 s2 ]: w. a+ C; b' t3 a版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231