数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题
: H8 J6 N2 O& P- _3 _  ~7 c# D' X9 j' C" H$ ], [& _

& I4 D! _1 E/ u) M% a& _, d*规划算法综合概述*+ P, U1 B- y9 b' g' h1 d$ t
规划的基本概念! h8 m4 n. ]& J3 {: \/ v4 ?
规划的分类方法（了解）, I) T- X8 M/ j" V# k) _7 }% T, v
求解规划的基本方法
$ m& R4 o" k6 Z& I8 F& C7 H*线性规划*
  m2 s5 n- t0 B! P/ u1 y线性规划模型的建立
, ?0 I$ i2 s" o$ c线性规划求解
4 M7 X: Q' E# h7 E( Y) \2 V# d! r*非线性规划*
( p: _- I+ F1 Q, ]4 w/ L. R*整数规划** h1 k9 g* C2 g3 k. F
整数规划的分类
2 p+ D0 [+ K$ J) ]9 U4 x+ q整数规划的求解方法. i; `% P7 C: ^% r, y; V
特殊整数规划0-1规划
8 s1 c( t2 u7 H* F$ E2 Z! O动态规划（了解即可）
5 j  _7 N$ `& O动态规划模型的基本原理" {7 ?1 J+ j6 U
动态规划的优缺点
" b1 ]! x" P3 H==目标规划（重点）==
. d9 _1 F0 k+ ~6 o3 v目标规划模型的建立
6 i6 b: G8 Y* P1 \: I2 Y引入偏差变量的概念$ G8 R5 g( l" X  e
引入优先因子" ]4 y. s" T' L3 y& q
目标规划的一般模型. J6 d$ E/ G9 I; G; R
目标规划的求解方法
4 n5 Y! p" l8 d: _) \) s2 z: Q规划算法的应用
( v) E1 O; x+ g3 S* f. [: }% H" @7 f装了半天数学公式编辑器，没装好，见谅。: ^. _& ^& R" M7 |& `! }* t% ^; m

# N' m/ K8 M/ C' [规划算法综合概述9 _- m$ D$ c" ?! Z1 P

$ J( [- {) I, B) D3 \3 }$ R对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
" X7 N% `. r% O0 O2 o2 C2 f- N- i; U
) z; \$ o! z9 |$ [1 @规划的基本概念
7 u" d  T0 _; j% W/ w2 F1 w( X$ ]7 ]7 D
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
0 j) C- q- t- K: Q 55.png ; N2 M' o" v7 t/ N6 W2 g
决策变量x，目标函数z，约束条件g(x)
# f0 X) u4 }& ]) Y# |, O7 ?+ Z0 w6 k9 H) W
规划的分类方法（了解）. p4 p7 }% i5 O0 B
8 g2 _3 J3 \9 V/ T2 K4 Z
- ?' Z1 Q: k' O; `, G4 [/ \
77.png ! s9 `  O: F+ m% e; Y9 }5 O! A
; G* S" P5 I5 Q" Y8 c7 }
66.png $ w  ~9 g, ~6 c" r( h
求解规划的基本方法  Y7 N. A4 {* q" M
! `8 _8 H/ v7 j" p! j3 o5 x
方法：在具体规划模型中会说明% K+ I  ]8 ]9 J3 p& m- Q6 X
软件：Lingo Matlab
. \/ {! n8 i6 _( u5 n, `+ Y; `) y, n) H0 h  i/ k1 E
线性规划
* M' O9 k3 I3 y& @' _! s, @# K+ u3 I' r; U# [0 |* R
线性规划即目标函数以及约束条件都是线性的规划。% t/ O, _; i# w0 T$ M7 h, z

7 H& r1 @9 M7 R5 {" G! W线性规划模型的建立, q, `- J+ o8 I/ g* u

/ T9 A- K( K4 T& X3 ~. T线性规划的标准化
5 i4 ]) G. |( J, b3 `2 r- y3 l; @% F8 r8 p, m2 l4 U
目标函数标准化5 ]) b( L: b% Y) H3 s* z1 ?( T
约束条件标准化. R+ r% W6 ?3 Z. r( M( `
决策变量的标准化, R' O. ?9 C! Q8 q
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z). T  @1 f4 P/ f. q, f% \
3 _6 [6 \% l+ @
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。# l3 G$ e9 @$ A

, A, [9 v3 E$ T例如% S9 v2 v) f9 R5 m, i6 `5 c. P
/ }* Y+ e! X* w" t# }' z6 H6 y- m
引入松弛变量 Xn+1,Xn+2
0 i9 n! e' i% \' `2 P, {
+ [) o% {/ k+ D6 s  a7 Aa1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b11 Q8 H  `7 x* T. b1 P9 D
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b27 A" Z# Z/ x" x, i) M

! ^9 R' i: t: b9 G1 S添加限制& B! H  ^4 B8 e5 i/ n
Xn+1>=02 `) k$ r/ @7 }+ H2 a% Z
Xn+2>=0' J0 `1 w5 I  D* T/ E5 L
: c- p! I2 U$ L+ O! R1 }% e: L
88.png
1 b4 ?4 f; r6 y9 [: B) C4.因此所有的线性规划都可以化成标准形式：
( t, ?) K& Y, \/ J! X: N9 n; c7 l, _: D+ x
99.png
& M! w8 Z! Q$ U+ Q( z
4 ]7 [2 Y2 H8 {  Z/ B( p+ J! {" u线性规划求解
7 p2 \' w' r! x- ]/ L8 T! u- u# }/ M
9 c& @0 w' m+ `) W8 a理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
2 J5 `& @* q8 ^+ f- ]( {3 F
) o4 x. H: r- ]6 f. W+ h' mLingo求解
2 T, o  K% b2 ?  {
2 L; u0 M6 }3 \+ X. T8 D- F: A* F代码简单% D) p+ d+ m8 q' v, f# s2 N2 R1 U
结果易分析
5 ~; Y7 R* Q7 c% ]9 D% b7 m7 a& W不容易报错
1 m3 j% T/ K9 @: ^ 10.png
- V2 A; R0 G( Y% m( ~- t" c$ y大概就是这个样子- t* v9 C9 D  |8 i$ }; F, ~
Matlab求解
5 ~: H: W1 ?4 b2 {" A4 Q
$ N3 g, f: z+ ^* s% Y& |& C2 h- O其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。+ W, K) B" ~# L' h5 U& r( L

& I6 `0 n! v  w 1111.png + {7 p  b, O$ I( n( ?
所有量需要化成矩阵形式，负责代码的同学自己去了解。- S. }- B+ @+ |# N

, B# U! q) Y. P' e* G4 W, E# d8 e" b* ~: O$ Y4 E0 O
非线性规划
" M. \+ @1 o' g# ~3 f6 M
5 u* T! z, d2 U3 |1 N7 s1 }; {2 g5 x简单说就是目标函数和约束条件至少有一个是非线性的规划。
2 y5 g: @  p& F2 k3 ?5 L8 Y1 [$ |/ R& ~3 m
Matlab形式" t. x; [( ?$ |6 V
1212.png
1 d" U1 D/ y1 s: h" |% Z7 F从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
! G& ?, D' H& ~( d' N* M总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
' ?+ x3 O* z/ Y6 {. G/ _
1 x# m6 [3 P' F8 C& a3 r整数规划
: m, ]9 i1 x8 R2 r. l0 B( l: ], q: `$ j; t
决策变量为整数类型的规划。( S9 L1 t1 f# Z1 o
+ d# Y' V% ^- N5 f* u
整数规划的分类
# p2 c) K1 p8 X& X' S( H2 z; t* z6 _, q9 u7 o8 Z* C8 F! O
1313.png
: J) A/ H- x: G7 Z. x& t7 |" @6 G  e0 I# Y4 j9 }# U
整数规划的求解方法
" J: n  k  W8 @3 O/ H9 l' c$ q6 k7 O/ a1 d  e$ D& k
蒙特卡洛算法
3 H' z2 Y  Y/ Q8 |  }9 [* N; w蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
) E: K5 [6 y' ~8 h1 r" S9 z1 p* E3 q- c  m6 m6 r- c- a
某整数规划题目的求解过程% a( E9 v$ a. M

& a& e- c7 z# h  r$ n: w7 q 1414.png
* G9 @# V" |/ A% k, o$ }* @! D/ `
特殊整数规划0-1规划
4 C! H/ a2 i; g3 N; v1 U) B8 X8 X
" X8 W. e, }, B9 R即在整数规划的基础上增加一个限制条件 0<=x<=1
7 {" A) D8 c2 Y5 ^* p1 p# [/ c& [5 i6 R+ E/ Q! `% \1 w
7 q6 z; ^- e: w5 f1 k
1919.png , H/ i2 t8 O; J" ~& O
) B0 R6 M, P* y& s) d4 q  ~
1818.png # ~1 }/ R8 l8 S( S6 E5 y" l
" V4 W- O* F7 ?0 N2 \
2020.png ' F4 f1 S) u& [" }" y  T
动态规划（了解即可）+ P$ |  f9 x& c/ a6 ?, p* E
' q3 H5 u' A) ]) y
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
0 [9 o/ j; p, K( e/ w2 h  V
$ K% E3 E. K6 ]4 H动态规划模型的基本原理: }* g( A2 f. Q( u8 n
6 J. e, N) S0 A- ?
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。2 ^! ?. P- _9 J" z
: y8 r' G) m9 t0 q, g
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。. y3 E& {: K) g5 B9 s2 y
, _0 x# k. I8 G
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
3 U. Y& ?1 f6 Y! @; m  @7 ~/ U
. K, E, L5 Y. D; ?$ r' R9 u% l8 v动态规划的优缺点" {' z7 Z8 E0 k# z) W
0 ~0 ?4 I; M0 L6 V8 S! X
优点：& J! ~$ b5 y$ m9 `0 j" [3 J! `
1.可得到全局最优解7 A9 U! ]  r4 _( \' I! I6 d
2.可得到一族最优解1 {3 C! e, B; r3 z2 I
3.可以利用经验提高解题效率
  g* P* D/ Z" R# b, z缺点：
: @+ M& \8 F: n0 T" w1.没有统一的模型
2 D4 s, y+ H; y: L2.用数值方法求解存在维数灾
  }: H! z2 [& r- H) f9 R" p( D- F* a9 Z8 T( t: M" M
目标规划（重点）6 @  ]# |5 M; o
, q2 A8 m5 v" Z* e
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。. E  D" ^5 V' b  Q

' `- ?( ~: V( P# C( |/ u目标规划模型的建立
! D: u2 G: A: n9 X1 |. n
) _# Y6 j0 C8 U& N 2121.png 0 u: O/ ?+ f9 B5 M

  ~' h3 F4 `7 t1 t, ]) V. _4 { 2222.png
& @$ {9 I, M/ j- k4 Z/ z% _* g7 d引入偏差变量的概念) p2 i, k8 G9 D0 r# a' p! S

: `" }% d: G. i" Z0 k# @ 2626.png 2525.png ) s5 V4 `6 v& M
6 x. u) }/ a! D! d. g
2323.png
- O5 C# m" t3 L: n2 d3 e( `
& ^, h0 i8 p, Z+ t% W 2424.png / D6 i, x  D& k# v( y
引入优先因子3 E% j8 W, c" c- w: B3 a- M
& ]8 ?1 ]4 F- G9 p+ ]: S
0 w& z7 Y6 E. X- W. ?

0 K. a7 ^4 g% J目标规划的一般模型; f. `. T) H+ ?: a

' W+ ^! E5 _# n+ S7 X0 c
) B# y; B. H4 c, M
; {8 t7 K5 Q) m9 [目标规划的求解方法+ _# T% }, A8 p7 }
* f) ]3 R4 z; ~. P" J" d
理论基础：序贯式算法
3 N( P/ {- Q3 T按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。& f# o1 i2 }8 O  Q0 Q( ?# Z" T+ r& {1 ]; A

8 z/ J# q( {, U% M规划算法的应用
8 t2 `" H% j) N; k: ^. d1 J; k, j
8 E& Z: E9 f9 J) `2015国赛 太阳影长的问题& p+ w0 [$ u" i/ Y/ f, |
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956; S& d; G3 d& k2 {  V3 L
7 w, J" \* }' `  W1 F; a

( O, I# d( H( p" d

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

1313.png

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

1414.png

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

1515.png

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

1616.png

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

1717.png

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

1717.png

作者: 德古拉    时间: 2020-3-18 17:56
Nice shot, thx for sharing$ \1 ?5 n8 Z! H% K- @  D  T) k. l




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