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

杨利霞

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

/ g$ s1 m  T, i2.1 基本概念
' z/ F+ F5 S3 m
! a+ q4 Z0 D5 @, [) R整数规划：数学规划中的变量（部分或全部）限制为整数
- j4 |3 O9 c5 G* x+ s, o1 Y% I# A目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
* u$ ^5 ?, ]; K存在最优解（最优解为整数）
4 G' s" N. o- w有可行解（最优解值变差）
2.2 0-1整数规划
9 j1 A2 H$ w' L/ z3 Q1 Y4 d6 T
定义：变量x仅取值0或1，即0-1变量
+ j6 ?# U2 |6 o; e# n
2.2.1 相互排斥的约束条件

" R5 n( _! ~7 b引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件

/ L% {- W+ W% R# Y/ E7 ~% K
2 y& I" A' G3 F* x+ g9 V# I$ z+ v( g需保证只有一个起作用，则引进m个0-1变量：
5 M! c8 X6 b" P$ S

) t3 j$ s6 `1 I和一个充分大的常数M，则有：

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

定义：变量部分限制为整数
) Y" w4 E6 b( \# `3 L! N" t可用约束条件：

. \6 K+ d5 b/ h( P
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
# M2 g" D6 w" _; ]( v
) d4 J/ Y! z$ y4 c) Q) B0 M( A

2.2.3 指派问题

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

' C8 {+ j  l. Y. N- W9 V

  v* P3 b- k" H' j2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
  定义目标函数 f 和约束向量函数 g

' r3 e- K' X* ~5 ?
求解问题
* n& k6 n6 `+ \
4 H3 `) U8 Z4 l! p+ f
2.4 整数线性规划的计算机求解

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

) g; S' x6 V! k! a) c0 g* a% I
+ N# r" @5 `3 b% e
" V! C1 t/ N" c2 M4 M6 D3 O6 ~
  O* Z  L, i, m# X' T
/ P1 k9 {6 S( U: P* L% @$ M+ W————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
) H$ o- _2 N2 t/ V( g/ i; I原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
9 z( _/ Y( j$ Q
/ A, F% j" Y5 X0 t6 E8 B
$ Y: d- E, z+ V% p7 A————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
/ H( O- [: V1 T$ Z$ U% Z1 ?4 [