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

杨利霞

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

2.1 基本概念
3 u; [1 F# b9 u) D, t& I5 \/ z* p* c
, \$ S4 A1 g6 i整数规划：数学规划中的变量（部分或全部）限制为整数
6 a4 E) ~! F4 |  h目前只能求解整数线性规划
整数规划的解有如下三种情况：
6 R! {0 N, q( b* v5 {0 K$ Q
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划
( K5 ~1 M3 z4 i) p9 g$ D! D: m
6 E5 h8 J% ]' J1 p' Y( ^. @; H定义：变量x仅取值0或1，即0-1变量
6 Z- f9 E+ w: l6 O
2.2.1 相互排斥的约束条件
% T  j. g% M1 R. [: ?
0 y8 \7 p- p- m引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
6 C8 r6 L3 D; z; n. K改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
+ c7 G5 [  m# w; b5 Q/ t

3 b! N, t2 C! ]$ E$ n1 N需保证只有一个起作用，则引进m个0-1变量：
: h3 }& H" n9 D2 f* J/ D

和一个充分大的常数M，则有：

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

定义：变量部分限制为整数
! s( f7 ^0 H1 u; P) V( c0 e可用约束条件：

y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
% S4 U0 f7 z% M# u上式即代替了该分段函数：

$ f2 [5 r) U$ h, T
" d: ?7 T7 M, A, x/ i2 s0 B4 y
2.2.3 指派问题

关键：给出系数矩阵C
! ]" f) o( [; l9 [# T; X% v规划模型为：（x为引入的0-1变量）

3 q: i3 b! O5 a) ?* g! X
$ x1 k/ _% J1 O+ y  D) ?2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
) x& e) G7 M5 c4 I, N$ umatlab程序如下：
0 O) \2 Q* b3 ~9 J4 G; g$ v7 S  定义目标函数 f 和约束向量函数 g

, a5 |) u% M( ?# Q
7 c2 _( A! A5 W7 l. \求解问题
; m9 b/ c! E+ D0 E8 _

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

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

( d6 F; t! t2 r
1 Y3 f; Z" F" X  Y
1 A, ~( z% [6 q8 U
————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
/ `" S6 ~; d. T" T  }' r原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

/ n, \9 g# H2 T
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
- K, w8 Q1 f  ]
5 W, W! U3 j- [( }6 {