数学建模社区-数学中国
标题:
数学建模算法之优化模型【线性规划问题、整数规划问题、二次规划问题】
[打印本页]
作者:
1047521767
时间:
2021-10-28 15:36
标题:
数学建模算法之优化模型【线性规划问题、整数规划问题、二次规划问题】
0 m3 z. R5 L! o) s1 e) s
数学建模算法之优化模型【线性规划问题、非线性规划问题、整数规划问题、二次规划问题】
1. 线性规划问题(LP)
# o p2 I/ l* N" I! F+ W; W- k
线性规划问题是要最小化或最大化一个受限于一组有限的线性约束的线性函数。
5 ^/ k8 z8 a! k. X2 r+ M+ W m
! b, o) a+ U/ m y R- @/ k
3 ^! g% n2 e4 n7 ~
Matlab 中规定线性规划的标准形式为
3 @9 f% ^8 B8 D, h' G8 }
, h t& L8 M" H4 ~1 |. U: s. x6 L
- s2 R$ Y# \' G+ v* d& U2 J# j
第一个式子为目标函数，s.t. 式是约束条件。其中 c 和 x 为 n 维列向量，A、Aeq 为适当维数矩阵，b、beq 为适当维数列向量
" G a- y5 _) E% s: B- f
# ~" t; R/ {) e; W
5 G& S7 N( R1 y( E
在 matlab 中，线性规划的函数为 linprog() ，有两种常用形式：
7 t6 F, U |2 a/ }
X = linprog(f,A,b,Aeq,beq,LB,UB,X0)
: P/ W4 ?( \1 R& U
[X,FVAL]=linprog(f,A,b,Aeq,beq,LB,UB,X0)
8 X2 z# o' t8 x% A1 E' E# R
返回的值 X 是向量 x 的值，FVAL 是目标函数的值，LB 和 UB 分别是变量 x 的下界和上界， 是 x 的初始值。
2 Q- f; _8 L, ~
" u% V* z! R" y7 Q+ ]$ }1 N; v
4 e/ }% M1 f. s* ~7 M6 r
1.2 应用例子
" z# Q3 l W; r' ]; m
求下列线性规划问题：
3 G. _ F8 M$ a, V) z; T; r7 c
+ h) ^4 T9 {8 C3 p4 O/ z1 u
: P' l9 ^! D6 w" r
依据 Matlab 的标准，默认求解是求最小值，而本例是求的最大值，把 z 的系数变为相反数，即 -1 就好了，同理下面的大于等于号也做同样处理，然后没有上界 UB，下界 LB 为三个变量都为 0，也就是一个全零的矩阵 zeros(3, 1)
1 c3 x: y: G' y* L
3 F4 O4 n% c: V
b% \9 A9 ~1 ~- o4 T7 o' `
编写一个 .m 文件：
5 Q! {$ s% M# G# Z" X* L0 U
3 ^3 P4 H+ m( c/ r" a
7 t9 `& y- e9 R
1.3 相关问题
& A/ Q) L$ B+ b& \
运输问题(产销平衡)
: c: |4 ?) G, R& p0 a9 x
指派问题（匈牙利算法）
8 m2 A2 ?1 y9 l
对偶理论与灵敏度分析
7 {) O$ [/ q" [6 B) J7 [2 z3 w# F K
投资的收益和风险
4 z+ m( y W0 I( d" o( U6 c
2. 非线性规划问题(NLP)
: k: f$ s, x6 b) ]3 u+ e
如果目标函数或者约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。
, ?. _6 w3 I' P2 F5 z
& s2 l* p- ^, C
. Y" X1 O$ i+ t7 c" X$ Y
% F1 C6 T- z3 A2 @5 q1 P
2.2 非线性规划的基本解法
' f! R6 Y$ b" f B) g
罚函数法
/ [, B$ T% V% X' V8 N, Z
近似规划法
3 T6 t" c0 `& R' D0 n. h: |
近似规划法的基本思想;是将问题(3)中的目标函数f(x)和约束条件g(x);h(x)近似为线性函数，并对变量的取值范围加以限制。从而得到一个近似线性规划问题。再用单纯形法求解。把其符合原始条件的最优解作为(3)解的近似。
1 U1 Z% x% ]( f( u& s
每得到一个近似解后，都从
[color=rgba(0, 0, 0, 0.75)]
都从这点出发，重复以上操作。
+ X, s" x: C2 L8 v7 j4 w# O$ o
8 C& a: O2 ~# z1 `3 I: o
7 l; O1 k# X! e+ f# ~4 i; w
# F7 u9 Q {5 `+ L* i6 H6 C8 g
2 X( t7 u! F, O
2.3 相应问题
# m# X( R+ A( k) a+ a/ j& i
无约束问题（一维搜索方法、二次插值法、无约束极值问题的解法）
2 @, G: N1 P4 h3 I8 ]
约束极值问题（二次规划、罚函数法）
+ k5 t, B. d0 W0 Y+ s
飞行管理问题
( q3 {8 [% l) w) Z4 f
3. 整数规划问题(IP)
/ c0 s" y* B' G( P- \5 x
数学规划中的变量(全部或部分)限制为整数时，称为整数规划，例如，所求的解是机器的台数，人数，车辆船只数等等。
5 S/ [% t0 ?* w0 j; @6 f
! C& l( Z5 e5 T
! Y. ]3 V$ P/ j
整数规划的分类：
- X7 v% K% k+ P
纯整数规划：全部决策变量只能取整数的线性规划
2 Q! ^1 }* B& ?& S7 ?! c+ w v
混合整数规划：决策变量中有一部分必须取整数，另一部分可以不取整数的线性规划
4 b, S4 Q' a- ^0 \: k
0-1整数规划：决策变量只能取0,1的线性变化
, Y# r( J) [" A4 Q: t; F
3.1 混合整数规划问题(MIP)
. m2 o3 q, K7 k' e
混合整数线性规划是整数线性规划模型的一种。
3 e7 H% Y: W _; D0 V2 n: I
) i( ^6 R/ t# [6 V0 w; `: d! i
" a# D& s+ I0 e7 l& q$ q
整数线性规划模型分类:
$ _! p, `8 w4 T: P
, M+ R h/ L5 [# P
) M, l% R8 c7 o! w" @" D4 G1 F
若I={0,1},J={1,…,n},即全部的决策变量仅取0或1,称之为0-1规划;
2 a! Y2 l! i; J& Z6 z1 i) G1 f s _
若J是{1,2…n}的非空真子集,即仅有部分决策变量要求取整数,称为混合整数线性规划;
& y' C: `- E3 K
若J={1,2,…n},即全部的决策变量都取整数,称为纯整数线性规划;
I" d7 s( ]+ t( }: A, L. d( v
常用的整数规划问题解法有:
) U2 L- b$ T; d. a) y# Y0 f
, ^! \$ K0 {- N# F0 Y$ e" l
4 J% a% |2 l" H2 R! V3 o% x
分枝定界法：可求纯或混合整数线性规划
" s5 Y% @1 A2 ~# V) g" [
割平面法：可求纯或混合整数线性规划
. T9 r a0 w! n
隐枚举法：用于求解0-1整数规划，有过滤法和分枝法。
* u( z. N7 Z* P% k) ~4 v+ S
匈牙利法：解决指派问题（0-1规划特殊情形）
) q4 s. d0 d4 y
蒙特卡罗法：求解各种类型规划
# d: \# n% R3 t2 G
3.2 常用方法讲解
' |3 D8 R! R" k9 Y2 S
0 \$ I4 C# b% z7 q$ K$ c3 C8 k6 k
9 y2 S# r* e* w$ _. p
% M: d' j0 E3 u3 B
$ z I r, J c* B7 Z/ N
, p3 X& o# y/ _# R( l
4. 二次规划问题(Quadratic Programming)
1 _4 Y7 {7 |9 h" l( a1 l
+ p: |7 [9 s2 C
% D* r+ S9 h& C) Z/ S/ i- u
& M& `. e" P) {3 \8 U
5. 混合整数二次规划问题(MIQP)
$ Z- R+ \: z) c D" c5 G
通过上面的定义我们不难看出混合整数二次规划问题本质就是一种混合整数规划问题的一种特例，其中他的目标函数为二次型，其约束条件满足混合整数规划问题。
5 U6 M7 z) S; d" A7 t
6 A$ J" @& S- R5 I. S
1 `& f0 _* h, z R1 f
; r% Z, F4 G/ N9 D. I0 a, r+ O
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
3 G. _ F8 M$ a, V) z; T; r7 c
5 Q! {$ s% M# G# Z" X* L0 U
7 l; O1 k# X! e+ f# ~4 i; w
2 X( t7 u! F, O
