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

杨利霞

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

. o+ d+ T3 b* _3 j% k2.1 基本概念
/ w  p( D' B* E( P2 ?( P
: z$ u( h6 \( |- h: G7 r- a7 k整数规划：数学规划中的变量（部分或全部）限制为整数
' ]+ t9 X9 r$ w0 Y* B目前只能求解整数线性规划
整数规划的解有如下三种情况：
% m+ @& c' a4 e/ e$ W
; _" g$ r, P6 W* V& y# V没有可行解（最优解不是整数）
7 `5 A3 G/ p& @  _0 I' @) C& v. w' `存在最优解（最优解为整数）
' z  u! I0 l8 J( z# c$ V有可行解（最优解值变差）
' n& p4 T8 p% {7 m; k+ h4 K1 e2.2 0-1整数规划
: @) r( R8 Z- l" X
: V( z. O/ ~) r) H! ^0 _; G定义：变量x仅取值0或1，即0-1变量
" {. k% \, A: o* v  k5 \
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
( f7 @% S9 ]' X0 P改为普通的约束条件（不常用）
若有m个互相排斥的约束条件

( n$ l& U" a% D  y0 o4 j
需保证只有一个起作用，则引进m个0-1变量：

# e* n& Z0 D1 f
, d( N" `' w- V5 S! J和一个充分大的常数M，则有：

; T/ A. S+ w6 k# x" w8 C, f5 T1 B2.2.2 混合整数规划（固定费用）

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

% \# @- s8 b4 d0 U+ n2 S
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
# K, |3 Q& L0 }) h- ^0 ]上式即代替了该分段函数：
3 e/ j  s+ [. X2 E; q


1 N0 [. m/ A! \, H2 V& j( A) T2.2.3 指派问题

关键：给出系数矩阵C
( H. p8 O; m" s" F2 k规划模型为：（x为引入的0-1变量）

! n# a* p1 S+ q! c, _, y
& E4 x) l2 q. X3 O( Q) [5 U
" m2 I2 x' M. t2.3 蒙特卡洛法（随机取样法）

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

. ~+ x* J' h* g$ f' }' \求解问题


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

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
3 {5 R) L- g* [5 P  标准形式为：

' b* c$ Q: r# _
9 L: O& P7 o/ X4 M) @* D, K
  P& X8 f$ a! x0 |" O$ Y
————————————————
8 K* Z) q  O2 Q) Q
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
9 l# Y& l/ Z; |# n
9 N9 q& @6 b! W7 {! G1 R
9 Q! A8 H# r) l2 d————————————————
0 i( b. G. m1 ]3 O1 k* m2 m8 B原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
& o& z' Y3 u) P6 N3 B7 c7 ?: B. q* y
) l- S2 F4 {0 t3 x: W. J