数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题
1 S* ~; |+ V+ z( h$ j& F% s$ U9 ^/ W5 q; T( W& i- z

; [/ {2 S' @) e/ k*规划算法综合概述*
6 j) w: K( r- u) _  {( H/ P6 l规划的基本概念/ R( ]4 H4 q; k2 o1 b/ l4 S* O  ?
规划的分类方法（了解）
; ~: f  @+ T5 d: d( X9 \求解规划的基本方法
' B' _0 v7 `0 T% {! z+ E*线性规划*3 W& S* E  X, M# n" Q$ P4 ?/ p
线性规划模型的建立, I1 n1 o2 h+ `) t9 Z" Y) r
线性规划求解
* A" v  U& L7 t+ H*非线性规划*& Y9 M2 o3 K8 g7 |- W! n- I
*整数规划*% C/ \1 S' W* R% w/ Q; Q
整数规划的分类
8 |4 m4 k8 W; C6 b. H1 `整数规划的求解方法; r# S  Y* E$ f4 _5 g1 X7 T/ t
特殊整数规划0-1规划: @% ^1 a, Q1 z1 k
动态规划（了解即可）* Z$ V; O+ q  E
动态规划模型的基本原理
0 Y$ P% f7 r* B$ ]4 i' I3 E动态规划的优缺点
6 x# `4 l2 |* r==目标规划（重点）==/ [+ ~. U* c4 t) O$ T- h; j
目标规划模型的建立- h& M3 {; v9 w- Z& M
引入偏差变量的概念8 a! \, k# j6 L# Y1 h
引入优先因子
1 M, n+ g1 Z5 ]  P( y0 V, b目标规划的一般模型
' q! h# i; g; D  V" B: d目标规划的求解方法# f2 k& [& d* `% x. \
规划算法的应用
, U- E& O# u6 ]; @' Y4 v% k装了半天数学公式编辑器，没装好，见谅。
9 E5 @! l4 R& K3 M( Q4 F: S& i( b8 j2 `" s% u$ q, X9 v
规划算法综合概述
8 E' b0 @) Q6 }; A8 o
; Q5 l+ z8 m1 C) c0 ~0 ?4 X对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
" r8 r& o6 A9 G) t
* s! m: N# V$ j  E9 k规划的基本概念  v/ c3 ?" @1 I* J7 `

; v  [& O- [  a4 Z6 V/ M, D规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
. x5 S; {! E, B% b: s 55.png
4 A) G* P7 a4 V. ~9 d决策变量x，目标函数z，约束条件g(x)
6 Y; M2 |4 Q3 J- w8 [. _# X9 r1 P& g* w1 @3 r
规划的分类方法（了解）5 D0 Z" @- [7 M4 q3 U

6 w* S; T: C. s  G; e+ l
; i# _- U* G' F* H- z 77.png . _1 }) C7 p  O0 t8 v( U  d) q: Z+ d, c6 h
. H; f9 I( K' d8 R9 r
66.png
5 }/ D% u( D" P; @2 @- Q求解规划的基本方法
8 v+ [7 a" o; T4 U# Q* z; l4 z( _* i/ O/ P! M
方法：在具体规划模型中会说明- P. N! g: u5 D9 m
软件：Lingo Matlab
. u6 \, y" _) G, K! ~: t$ ~  L/ a" G( O! h, m
线性规划
* e; q3 i+ d" n2 ^3 K# [+ Y
$ ^6 n; I  [" H# Y9 [- g1 I线性规划即目标函数以及约束条件都是线性的规划。
1 N$ W4 t' Y3 V+ Y( }4 h+ J, e7 Z
线性规划模型的建立4 p, S$ L/ t: Q& y' m: @. D* |

8 ^. {2 X) r- U( T1 x: r$ V7 X7 g线性规划的标准化. W; ~& D0 e- J3 a
# M. G9 g. \# _% z* w
目标函数标准化6 x4 W$ |0 y7 J
约束条件标准化
, [8 ^8 g, R8 k8 P, E1 e决策变量的标准化
4 P& x3 O! ?) ^3 C1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)0 X0 M2 Z7 X  ]7 b; r

! D& T! K/ B, @8 Y. T; z) }2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
9 D: u$ ^# A. u) g( p- x' G& w$ U2 |, A6 u6 x4 n, Z. v
例如
% Y1 r  s' T7 l5 O7 \" F
- H* X0 k# ^: `* f4 S+ O! I引入松弛变量 Xn+1,Xn+2( i# ~) T- B; K1 k$ x! w2 D1 I% b. p9 _

, f0 s3 @, x' w' R( Ga1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
( W: W6 A% g$ K9 B- N* ba1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
9 I& Q" o; r4 P& G1 @' d$ V/ m9 b  G# K. y' k- @
添加限制
' X+ f7 N6 Q  w  U- U) x0 _2 BXn+1>=0
  L- k1 K0 S0 U8 u4 ]3 o& K% eXn+2>=0
3 r4 l+ l2 Z0 _% Q" D- l* u$ D% i# i. ~  ]. D1 U8 q( l! g
88.png 0 F* ?: X3 n5 `! w
4.因此所有的线性规划都可以化成标准形式：
) @' T( ^! |: T, o% y$ i% o. Q
" {6 t5 {3 A) l% S# o8 z. V8 B 99.png + Q9 b/ Z2 \. K# U7 e

9 j- a/ O! ^5 w  n' A线性规划求解) O8 G- Y* a3 z) K3 i7 ?8 Y
) K: J7 l3 C1 L; z+ K% L
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
/ A% H  Z: V. s. g1 U' M: F! m  G/ h- A2 X
Lingo求解, a  y2 i7 U$ s9 d; C% R
! U, Y( C9 a$ Y+ g; D0 ^- I3 l
代码简单
7 R. ~8 E/ q* ]7 }" s/ R结果易分析. E. |7 y" h9 M6 X/ ]3 M
不容易报错7 x0 Q5 ^4 c" @# ~5 K; E
10.png
& }  h: x; B+ L1 \) ^大概就是这个样子- v: N* E$ A/ E0 b1 N% ]& |
Matlab求解
1 s- n' d6 X* q6 Z% _7 d9 A8 J  p* ?9 X' ~+ F
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。+ y% S/ ~. ]9 S8 C4 R( m

5 F8 E) `1 F/ p$ _4 l% P3 {9 \, j 1111.png
0 u6 \+ y- @  Q2 l所有量需要化成矩阵形式，负责代码的同学自己去了解。
4 a  Q1 ^3 e0 m3 m  Q  ^1 c9 y1 n1 y0 V6 Q5 h5 Q: J* p
: I$ U* _( R4 u# y+ D' ?$ z
非线性规划
9 a3 X2 N% |4 I' p
2 y3 E3 y9 g$ ^& U5 K- v简单说就是目标函数和约束条件至少有一个是非线性的规划。
/ o% Q0 q- B3 p$ o4 q2 u& N  E% M5 E8 P3 f; T
Matlab形式
. S- m: P3 E1 W  m  M 1212.png
2 a3 p, j  k2 S, D( A/ A从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。  c9 g/ b8 ?* c4 q( L; b
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
0 n( |+ H$ G+ x/ d
$ S  Y% B1 F0 H4 a# N整数规划/ f2 a9 V/ @" g; t7 V+ {5 o% L

! B! A8 _' ]: \6 R) l2 H决策变量为整数类型的规划。& R5 S( ?1 |- T% L% I6 u
& a; ?. x( H/ Y- `, T
整数规划的分类/ i1 B& U8 _, v0 p; g

1 t! `  t; F  l/ G  T% R 1313.png
4 N8 n5 Y2 y& k! |: \/ ^5 `9 E6 Z! o0 r& j+ z
整数规划的求解方法
) Q& y( ?; |# S. I+ v; e8 a* d
: s' o8 R$ L8 Z蒙特卡洛算法; P: b( e  N) S2 M! h0 B( r
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。5 i( C' o* H; }! C9 {  D% a
/ }! o" j" m( I$ m
某整数规划题目的求解过程
8 a4 A# N  Y1 r( a: q# Q5 t& j' X) G: B" G( ^* @& H) P. ]; X
1414.png . |$ s6 S3 X- {$ C2 ~( u

/ _. n  d+ Z: z* e6 n1 Y特殊整数规划0-1规划2 o4 q2 i3 k& B# @$ [; [
7 ^4 j% [/ m: Z# i1 I1 ^  N, ?! j
即在整数规划的基础上增加一个限制条件 0<=x<=1  P' X+ T4 t' u' `! e* r4 Q, L3 b! c3 i

7 B2 U# T1 \( w- \  I2 S+ a
) s9 Z5 t0 K, j: G$ z1 ?4 B 1919.png
; N5 r1 Y% a" F& ?+ M2 w3 L( t$ A& L! L0 @) }* `5 m: x+ f, y
1818.png 4 ~% s3 E* W8 m! J

8 E  y& e# a! Q/ ~( u) G4 L1 o. [ 2020.png 1 k" e* U5 U0 Y8 R9 _
动态规划（了解即可）
5 j. h4 f1 ~* z1 C
% @* S  x/ X2 h; N. n1 N# M  v简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
& k  N' N- ~9 ?' c3 Z# `/ I% \, A$ O  M$ `3 W4 i- ?
动态规划模型的基本原理" x2 d7 s  A# r- k% w1 r) n  J
2 l/ Y/ Q( h" ^  s
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
8 b4 C1 D. I" ~, p! V/ l4 ~4 ~) W  F! ?- `0 @# J2 K
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
2 t" ^) r  B! q. ~
5 @$ I8 Z# b" t+ s8 b* D. n: j+ o逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。1 b' M+ ~8 I' O
; @, b+ E' g7 l/ B
动态规划的优缺点. n% h  s& O0 `6 E2 _
! i) h1 O) r7 h7 K$ s3 m4 i
优点：
$ _. a/ W4 ~# ?$ R* B# K1.可得到全局最优解
. N/ L& _, N5 j: m6 ]7 i4 p2.可得到一族最优解
! C- l0 N9 q% v) \3.可以利用经验提高解题效率
- b" ^, U" c% B% J! U缺点：" O7 D% Z) R" b  o$ A% d) W
1.没有统一的模型
' S/ a$ c: K/ c# K; }( a( z# Z' [2.用数值方法求解存在维数灾1 _% Q; `. K* a& S
7 H4 q( W' |; Z3 `4 p6 b! E8 @
目标规划（重点）
2 p6 E$ t. G* {& c* h- f: Y/ u
5 S6 F/ c* i% M# L" H# _0 D3 {/ E目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
, c) Q0 a5 g5 o( I& M- K3 d
7 G: t' I0 x( Z目标规划模型的建立1 v7 p9 a' d& J. J6 A8 W6 t+ G5 F& ?

% ?; X* v- M& `" ], l; O% z9 L 2121.png 5 z# U' p$ M2 S* m% {$ U! m* A; ^

$ N1 `) v& y( ?3 i  s6 a 2222.png 4 ^7 J) F' n8 K
引入偏差变量的概念2 o1 B+ k" e9 H# M
- ^$ g) W0 T8 S  Q% x6 v
2626.png 2525.png ; ]7 o( j/ C4 t9 H. j; P
. i& E# V9 ^9 N+ M6 D- b% B9 H
2323.png
' I- l9 R8 ]) T( _1 F6 U
3 k. T1 m# I) B" S  D' h6 h 2424.png
* J! N% N" R/ _7 h引入优先因子' R2 ]2 J* ]0 ?- L- c& v
* h& C7 a; M# _3 q

7 l2 G) c9 K! K, l9 z
: L% k8 }' `- h目标规划的一般模型
) T$ R& E9 b0 @) c
) Y$ u  k& Z/ x4 a) {* l7 J2 ^
) G1 K1 x5 l# n+ {" S' ^' v' ?; u# H  h1 v2 z, j
目标规划的求解方法
, e( ?+ L, `( U9 y
4 W- R) q. g& E7 U5 u4 |$ V理论基础：序贯式算法7 M" Q1 X* D6 ^
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
1 @; `$ N2 E) ?5 |2 b2 q+ x
+ q% F1 Y  [& I1 O" F规划算法的应用
6 o+ P3 e3 p3 O1 c# l* r+ y. N" H" T$ \; ~5 x7 ?! n7 ^
2015国赛 太阳影长的问题* W5 \8 n& i, A) P
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
& \# }1 K" w1 L1 o2 Q% C8 o0 `' ^$ x8 l- n: k
. d9 I. S* q* h) S

1313.png (30.98 KB, 下载次数: 426)

1313.png

1414.png (34.26 KB, 下载次数: 405)

1414.png

1515.png (79.16 KB, 下载次数: 419)

1515.png

1616.png (79.16 KB, 下载次数: 384)

1616.png

1717.png (27.95 KB, 下载次数: 416)

1717.png

1717.png (27.95 KB, 下载次数: 401)

1717.png

作者: 德古拉    时间: 2020-3-18 17:56
Nice shot, thx for sharing) v7 v' V; I7 E& t% m. K




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5