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

杨利霞

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

2.1 基本概念

( Q+ {6 d" G) o* P; F整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
- W6 Q7 r' r3 @) n整数规划的解有如下三种情况：
8 h: a6 C2 J1 k4 d1 J
" q) x( e1 I1 W  N& T没有可行解（最优解不是整数）
* J: w  z6 ^  u) b' l存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划
( q( `& o+ L' j# i) M) N8 v
& b2 F) d7 {# u2 n定义：变量x仅取值0或1，即0-1变量

6 v! i# _  ?1 W. o. v/ U5 N8 ^2.2.1 相互排斥的约束条件
' ]& @# ^( V+ Z4 @/ c8 m( v5 j6 L
  w0 g- Q1 g5 f0 p& F* }引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
) t% s* D; e* z2 O4 m# Q改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
& G' v* v- L& A1 N

需保证只有一个起作用，则引进m个0-1变量：
' b6 x; K7 {% |
  }, d; `/ n9 p% T4 j0 K% B
和一个充分大的常数M，则有：

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

定义：变量部分限制为整数
6 F5 o3 Q3 L4 m, `( Q" H可用约束条件：

8 b5 B' L. v& g; A. ^& ^y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
: Z5 S/ o  T$ y上式即代替了该分段函数：

, N* G0 q3 }, p
+ Y) f3 B" ^- E2 J( t
& l3 y: F1 l9 d2.2.3 指派问题

关键：给出系数矩阵C
  ?& D' c: q, ?. \; n规划模型为：（x为引入的0-1变量）

  @' p1 l8 m1 D. a  j" F
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
5 q: Y9 g6 ~( Y" U; a+ cmatlab程序如下：
  定义目标函数 f 和约束向量函数 g

2 `9 Z$ p( k$ o4 F
求解问题
! w7 d. [2 B. a; I
* k( ^7 f7 A6 z" u3 k
2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
$ F' S1 p! ^2 z- U: H  标准形式为：

5 G3 d  K8 I# t5 R
1 j+ a5 g# G7 k$ J
  `" ^+ e% a6 r# Z! q$ l
* I" g: d$ u' P+ I$ n————————————————
' \' ^3 \* Y- t) |. |$ |
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

( T5 I& ]! R, [- f8 t2 C. G$ c
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

# j! ?, S- o" c% W8 E) o) b
% }4 Q* }& x9 p7 n