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

杨利霞

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

: ?% ?1 u0 o3 H. S( I' h4 h2.1 基本概念

. p4 _% N. b; c$ S整数规划：数学规划中的变量（部分或全部）限制为整数
; o- x% O6 u: o/ p' Y% Y! V" F目前只能求解整数线性规划
+ g& ?; Q, H0 s$ u3 N整数规划的解有如下三种情况：
5 X& k! Q0 x7 k+ {7 t( R/ {
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
% r) j2 m: U  P$ H2.2 0-1整数规划
( R2 E5 J* v0 p% H
定义：变量x仅取值0或1，即0-1变量
9 M  ]3 T6 {5 O
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
2 b% G3 b" m. w1 n* u6 I0 O若有m个互相排斥的约束条件
, h# |& H1 f, e! T

需保证只有一个起作用，则引进m个0-1变量：


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

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

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

9 h! _. q9 F' P. k' Q  U. Q; }
2 z5 J( z# s- J) w9 i) ]y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
+ ?- t! P. O' v/ N9 _: T+ }上式即代替了该分段函数：

1 s6 t- r1 G% l& K
3 T! ^8 r( E6 W' B
2.2.3 指派问题

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

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

目的：求解非线性整数规划
matlab程序如下：
6 O% S) _9 U9 I* }7 k: ]  定义目标函数 f 和约束向量函数 g

3 w" i4 z6 B7 e4 G2 N! M求解问题
  k0 |/ Q5 _+ v/ }+ B) w/ a) e% y+ W
. N9 L% W" A% L) @1 X( B
/ _/ p- A4 W! T2.4 整数线性规划的计算机求解

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

8 f$ i3 ], ?/ H- Q" m
( E* u4 v( e6 x( n

3 f* v. E7 A  O* D
————————————————
7 d+ r4 b, A6 t' Q5 e1 B
) D3 ~+ h: s# Y/ Y版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
! j3 [) b3 B$ J7 h; `原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

8 r+ A( O, e0 v# S2 m; Q, f
————————————————
5 }) N% R- V3 I  ]0 l$ c1 a原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

' w" A/ a6 [* V( f& T
/ ~1 k; D; \1 a4 h1 H. C