数学建模算法与应用第二章:整数规划: c" D* n! T1 `4 Z( Y3 a4 a5 n
' \" O, ?% _! C1 s9 o# _
2.1 基本概念% G# ]& R! c9 H4 x; v4 I& X
( Q+ {6 d" G) o* P; F整数规划:数学规划中的变量(部分或全部)限制为整数1 t; v. V$ c' X! V
目前只能求解整数线性规划
- 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存在最优解(最优解为整数)6 {) x0 V9 F; \
有可行解(最优解值变差)0 B9 ~, o. E, s. D9 ?, \
2.2 0-1整数规划
( q( `& o+ L' j# i) M) N8 v
& b2 F) d7 {# u2 n定义:变量x仅取值0或1,即0-1变量" m( z' {; b% j9 S' [. r, w
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改为普通的约束条件(不常用)( V2 ~9 A: |6 y4 c
若有m个互相排斥的约束条件
& G' v* v- L& A1 N
0 w% ^4 y3 X( G
( X- C* g, |: f2 X, d3 a& E2 z5 g" D
需保证只有一个起作用,则引进m个0-1变量:
' b6 x; K7 {% |
}, d; `/ n9 p% T4 j0 K% B: p) s0 V' ?& G- f' l- M) k
和一个充分大的常数M,则有:% v- x! k1 {$ J/ m$ `) O
% Z b9 N6 k9 c% F# T/ k
2.2.2 混合整数规划(固定费用)定义:变量部分限制为整数
6 F5 o3 Q3 L4 m, `( Q" H可用约束条件: 2 U+ P7 M+ }: R" ^& g
8 b5 B' L. v& g; A. ^& ^y为引入的0-1变量,ε \varepsilonε为充分小的正常数,M为充分大的正常数
: Z5 S/ o T$ y上式即代替了该分段函数:; X! T$ K- G: \' U
, 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变量) 7 K6 a6 S/ Q/ g9 E7 X
@' p1 l8 m1 D. a j" F. g2 j; D# k! c3 {
2.3 蒙特卡洛法(随机取样法)目的:求解非线性整数规划
5 q: Y9 g6 ~( Y" U; a+ cmatlab程序如下:, I- P7 R0 d* M1 B" Z% o
定义目标函数 f 和约束向量函数 g
2 `9 Z$ p( k$ o4 F5 p' [2 u- y6 u$ j r6 m
求解问题
! w7 d. [2 B. a; I
* k( ^7 f7 A6 z" u3 k" S- ?! k: v& ?0 J8 t. ~# @+ {
2.4 整数线性规划的计算机求解matlab求解混合整数线性规划,用intlinprog函数,但必须把所有的决策变量化成一维决策变量,即需要做变量替换。
$ F' S1 p! ^2 z- U: H 标准形式为: 3 c1 h* G$ M2 T; V. }
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) |. |$ |. H( x' u. t, q. d6 U$ E0 f
版权声明:本文为CSDN博主「victor_cs_bit」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。' b- n0 }/ U) }, d
原文链接:https://blog.csdn.net/qq_41000485/article/details/96478231; o% s- Y; o6 ]
( T5 I& ]! R, [- f8 t2 C. G$ c ?3 G& W2 Z3 d& L% w- S4 q4 S
————————————————1 M+ g" \; y' T4 s$ [2 Y) t' K3 Z. u/ r
原文链接:https://blog.csdn.net/qq_41000485/article/details/96478231: t) s: K7 P0 s9 U
# j! ?, S- o" c% W8 E) o) b
% }4 Q* }& x9 p7 n |