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

杨利霞

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

2.1 基本概念
- q2 H0 \: i2 F1 y
整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：
7 t+ S; G8 X  U3 |
0 ?2 ~& i8 {5 @: J- l" |没有可行解（最优解不是整数）
$ r" X: V0 j8 C% R$ X存在最优解（最优解为整数）
! B9 v5 y. s; I% t" I有可行解（最优解值变差）
2.2 0-1整数规划

5 H1 S+ I& n( u; s6 m* l1 E定义：变量x仅取值0或1，即0-1变量

. q4 V# l. ?2 I5 O; J" W/ X2 e$ a2.2.1 相互排斥的约束条件

$ Z0 e( O0 g' w引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
8 E) f1 X0 J% |3 g6 @# |9 V# {改为普通的约束条件（不常用）
! z5 C0 Z+ j7 ^1 w  c若有m个互相排斥的约束条件


6 ^( R) _9 [: ?" T  g需保证只有一个起作用，则引进m个0-1变量：

9 y( K$ y/ p  s) `3 g
( h) l6 B  Z6 k1 o2 E; }3 l( q6 f& N8 q和一个充分大的常数M，则有：

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

定义：变量部分限制为整数
# l9 [4 e/ K8 ?) g/ [; h可用约束条件：

4 b7 n2 t% W5 N" X
* Z; m+ i9 ^5 |' i1 y+ W4 w2 Vy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
: j0 j, B7 q: {" V

1 C' A/ e* E3 K7 L
  b5 A9 I, I' F: z- C9 y2.2.3 指派问题

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

# R& N: O, N4 D. C" q% |

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

目的：求解非线性整数规划
: U2 j- m9 B* x9 I+ O( {+ bmatlab程序如下：
8 F0 c4 g+ ~4 Q  定义目标函数 f 和约束向量函数 g

8 z4 C0 f: _% M/ W% Z求解问题
( I4 q. k3 ~& [8 {+ i& W7 ~) A! U

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

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
  g4 g9 R) p+ o0 R2 D& g) i  标准形式为：

7 C8 ^: L* g& z% s" {3 F, @/ m


% {( W/ s. @5 c4 g# R3 h6 b/ |- k
————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
& S$ w, G: R  p3 l8 W  g原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
5 ^6 |) b( ]1 K+ x
& y' B- G( k9 h; T+ O: e; b: Z0 k
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
* t1 q( t( |( E! s+ g& g

! k0 o! t/ Q5 f) l3 o0 K' |0 ?+ P. Z