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

杨利霞

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

2.1 基本概念
/ m+ y- ^/ q. d6 B/ o4 w5 o
整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
- b: {0 ?9 D- ]. R1 e) y整数规划的解有如下三种情况：

7 ^& @6 G7 a/ B. q% T) g, I; Z没有可行解（最优解不是整数）
存在最优解（最优解为整数）
) @2 \- h. C3 H! C4 a' I6 y有可行解（最优解值变差）
2.2 0-1整数规划
6 N% e2 E0 b) j1 `
定义：变量x仅取值0或1，即0-1变量
8 G& O1 I1 V  O! U& B3 Y
2.2.1 相互排斥的约束条件
/ ^! ~  M; K. ?8 @4 o" ?4 r2 S' R
/ L6 x/ t1 S9 p+ h, M2 D引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
# P, g6 I0 }- f$ ^! n* u$ j" U4 \7 k改为普通的约束条件（不常用）
4 L- A% {5 M  G9 R# [3 O若有m个互相排斥的约束条件


; T5 a( Q; @" l1 M1 y2 }  g' }需保证只有一个起作用，则引进m个0-1变量：
# ^, u# r6 ?3 o( ~

和一个充分大的常数M，则有：
" y0 h4 v) e7 s' r, V
! }4 a! P  i4 E2 V/ u2.2.2 混合整数规划（固定费用）

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

4 E9 h; P2 G+ W& V" I* C5 A7 z/ a- fy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
1 N% l: A' x2 |5 T1 c; X


$ F. }6 l  Z/ q1 H2.2.3 指派问题

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

1 {' q; p4 L) K4 t1 f  K5 E
2.3 蒙特卡洛法（随机取样法）

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

& w: K' M' V( D' X2 \9 l# |1 ]; r
9 E; C  H% a+ Z求解问题


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

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
1 D- K" U) p$ l9 s  标准形式为：

( M7 |' I( T/ N' ]1 ~2 `! C
6 n% b# o. {- y
/ s( Q3 h6 g5 ~+ f0 u
- ^8 ~/ V' w. t( r
" r$ l  X- f# r2 w; H; r————————————————
, f  N8 ?' I* a7 r3 y
5 Y3 [/ H8 i  x) {$ F' f版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
, j% n+ E- F' W原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

; P& b. b7 O2 P, e( T, h) v) u& x/ j
) K" m6 H5 f; m. Y8 d7 M# h4 V————————————————
% b, c( G" ^5 l  `. J原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
: U- s. C% V6 d) O$ @$ H

/ x7 C% w7 q. D( |