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

杨利霞

数学建模算法与应用第二章：整数规划
% z, t1 }+ x! P
/ B9 z2 r5 V! s7 F) E6 u3 L2.1 基本概念

4 a: M( X: D" f; E整数规划：数学规划中的变量（部分或全部）限制为整数
' ?# t4 K  }3 J' \5 [6 e" V; I目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
/ s7 {$ h! H4 l. w" P有可行解（最优解值变差）
2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量
% L4 C3 L8 i% v9 {7 i9 f- X
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
7 x3 p! e  Y  m6 W7 h- V) b

' u5 U  y2 c  p6 ~7 g9 D需保证只有一个起作用，则引进m个0-1变量：

! Z7 s! m8 Z4 T* t0 E/ H0 c
和一个充分大的常数M，则有：
: s! j7 T& Z) G( {6 R# p( S
4 @1 n2 h* E0 q6 @4 Z2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
8 P$ R. Y, |& i7 O可用约束条件：

0 C5 {' I3 w7 c3 b" n
1 X5 D* z; O+ ly为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
' K# L# x* ?. A6 a- i上式即代替了该分段函数：



2.2.3 指派问题

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

* n8 b1 k( E! \# w- m7 c

3 S' L$ N5 d3 \, |4 |2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
" \& |. c8 i' ~+ l" {  定义目标函数 f 和约束向量函数 g

' \! {/ O5 I4 |; o
求解问题

/ s7 y& M& q  n/ I
3 h! T9 X. u1 k5 t; j, {2.4 整数线性规划的计算机求解

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

, _# N5 [2 _, p" w+ p+ g

$ q: Q9 o& }! y& G) q; g

7 E6 ]( ]% p* \" j0 A4 W————————————————
  o) d9 F" q/ G/ s5 Q1 [/ F; k. X
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
% a/ L, H, }' S& f, b! C) @
" X0 h) \. N# {& b4 Z, M/ f
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
0 g, Y8 u0 B! g2 E" A% V