数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题
( ^$ r8 E8 q. i' A! ^" @6 `# @* x* K8 `* |! ?, t. Z. U

. [0 F7 D: v$ t/ Z. b7 i*规划算法综合概述*8 L: x9 r, y/ o. ]: e* M7 d
规划的基本概念& D" M) f1 ^9 z7 m6 t/ _0 G
规划的分类方法（了解）3 I: D& @! v5 a& V, v+ I; n& j. p
求解规划的基本方法1 F# R% R+ X9 f+ X9 z
*线性规划*
" E3 O: e3 `! n, a% y线性规划模型的建立6 w, W( d. X" K+ p( x" I" e
线性规划求解2 V* M) p# d2 ]) W8 p
*非线性规划*5 m$ D' X  F$ L6 E
*整数规划*, x0 ?1 `$ V" ^1 h0 O
整数规划的分类- `$ |5 K! a& l, H; P
整数规划的求解方法
8 S( r7 K2 y; ?  K特殊整数规划0-1规划5 J5 w2 v- T% o* @, {# G! D
动态规划（了解即可）
4 P+ O$ J6 ~* M* P- I' ?$ w动态规划模型的基本原理
) C; @3 R3 i0 z动态规划的优缺点
; H) o+ g* Z1 [: |3 ~( L==目标规划（重点）==
7 `: V* }9 T( s' O/ J目标规划模型的建立: c- V% g& K. m  y: F5 K* q
引入偏差变量的概念  Y/ h8 t9 |7 S2 X  a/ n1 m
引入优先因子
' t: G# u' w7 a4 D目标规划的一般模型4 X' A8 C- U; @+ e9 O- ^- J
目标规划的求解方法$ u$ b  b; l( s) G- Y
规划算法的应用  f1 E( o; Z9 v/ X
装了半天数学公式编辑器，没装好，见谅。
; ]" y7 l, g1 p( @/ q) g! k1 r# [! Q0 y
规划算法综合概述
; {1 M( d6 J9 }; `# c
9 a4 }  |' B; K" X8 _' D! Q对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
+ J( ^( R+ A6 K% O1 `5 l' a& X- Z' x5 w8 r2 ?
规划的基本概念
$ r  a) N8 p3 `% y: s5 p+ k
9 w; o/ b+ N& t  n0 A2 A规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
8 w9 `2 l( n2 u7 a# `) u7 q& d& ]- w% W 55.png
3 s& f# f1 s& w, J决策变量x，目标函数z，约束条件g(x)3 {7 y% G7 Q& o, X3 O2 ~

! B% h! R# ^* O) Z7 h5 H规划的分类方法（了解）
0 Z8 j3 B; i3 Q7 ^% g. E1 ], U# u" o5 i+ D. S! z; @. w

8 k" K% V8 ?8 Y 77.png
1 P. o5 m9 k0 z3 Y. d; I8 f* `6 [" G! Y7 C1 l- T0 _
66.png
1 J' K- i/ z2 b6 k; p( O+ ~求解规划的基本方法
5 F" d+ a& A( |' X# W, |3 _; P* N& m4 |' ~9 s
方法：在具体规划模型中会说明6 y/ t, K  Q- X. H9 H; |
软件：Lingo Matlab
: r0 E" i( U! G% B# L* f# P1 \" z
& c4 D& E% r" I. i线性规划
' J3 _2 R4 g! F6 w; ~) P
! g! r, z/ l3 B6 a% Q) w线性规划即目标函数以及约束条件都是线性的规划。
3 Y2 X1 y2 L2 s) m5 y. C3 E
1 L6 [9 ]$ |2 Y5 x线性规划模型的建立: S/ ~2 [$ v0 E' {
2 r8 a3 {$ J# `3 y- p: a# e
线性规划的标准化
/ J/ {  N6 S1 ^1 t+ f, C! g) e# u. ?- v. l, Q( d
目标函数标准化- x7 \$ ?. Y3 R% Y
约束条件标准化) K. ]$ i3 ~$ X; j( Q* c9 R
决策变量的标准化( N. B0 C- @4 z1 R0 M
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
  w- ~8 A8 W! u9 F9 Z7 ]7 K8 A/ j1 ~# |/ z
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。( _7 j4 D# f+ d* }/ g
7 W) B8 J, D1 v. S2 o7 s  Z
例如/ o5 A' O+ s& r0 l6 }$ p. W8 Q( R$ X
3 O0 E4 J4 M9 C) S
引入松弛变量 Xn+1,Xn+2
" i9 W- Z( N3 D" @: L5 A8 Z2 S# |' Y* V. o5 j; N
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1# @; a  U% v$ {2 a# p
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
0 B5 `/ V; s' X- @3 _6 L2 Q
6 R8 v" H/ [2 F添加限制
  G5 h+ S9 V- N# V: xXn+1>=05 m& F  A) x8 p1 O2 R2 s  V
Xn+2>=0: l* _1 w% h0 o$ J: O5 x

& t4 ~9 ?! I2 z+ a 88.png $ ^9 M0 F% ?: f, P: J; u
4.因此所有的线性规划都可以化成标准形式：
. y: \1 S+ g; }+ M+ q
5 c7 p: U2 d( w# E4 ^ 99.png 6 B0 T/ n+ @& M) Q
" @5 ~* T0 `7 F7 O: z6 b
线性规划求解; |6 {9 w2 D0 R' @% {# m2 o

8 K* I# y* x, I7 a# P  c0 A6 Z理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
/ @1 i* V8 b' K, z% c$ ]/ M5 o) a0 q8 x8 h) r3 |
Lingo求解
+ v5 H" G5 F' S
! t6 q! Y+ v  s, ?代码简单* ?& U: n1 Y' Z- q, M# O( I8 X# S
结果易分析
! G# l- `! n5 o* a8 D) }不容易报错
: u. s* I1 y9 j9 x  N+ V 10.png
- g' H$ `( y. L8 F大概就是这个样子7 _9 J8 b$ P" S. w
Matlab求解" R6 n2 ]3 @. q0 M- ~
. F3 @( _0 E1 F7 l! F
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。0 k' j! N  I6 a

  c# {6 k  x6 t2 y! _9 Y  Q/ A& ~ 1111.png
- g2 U. `9 V( |* k0 ~% @所有量需要化成矩阵形式，负责代码的同学自己去了解。  G( k. L" ^2 t4 x8 ?

9 l; u# X' x1 t7 G0 ~1 L: m3 g2 ^% U. T/ i# k3 e7 d4 N" S& F
非线性规划- @2 O5 Z. t8 n$ x" |$ a7 y
) \6 w) j0 C1 h$ v
简单说就是目标函数和约束条件至少有一个是非线性的规划。0 T! i' s0 N  J
; M5 H" u% a. E# o/ E3 U4 ^
Matlab形式; b7 g# y0 m9 |# b
1212.png & H9 R& e, T# D. M1 i2 _2 R9 M: W
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。, r: `5 l+ Z8 T4 i. C
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
! e! R2 v$ i; Z/ c* I  G! c# [  f5 p8 w' B9 `% v
整数规划9 s0 A- p3 a2 v6 k6 w7 H9 h) B4 M

& X5 |5 V3 m3 n2 t决策变量为整数类型的规划。9 m5 ?! ?. T9 F! P
" ^7 ~% r! F2 @# t: W
整数规划的分类+ }* C7 b+ `( l6 k: ?
7 M+ k6 n" I# t- u" o
1313.png   c; s3 A9 Y. j
& w9 Z3 B3 d: ?) ~+ _- C* L
整数规划的求解方法6 [) C9 ^4 O2 W+ h; t& v
2 h2 n  A/ z4 d7 X9 |. f# p. M
蒙特卡洛算法: w& g/ ~5 d: r
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
+ t" Q6 P5 i$ a% o
0 r1 a* u+ p# H  Z8 f某整数规划题目的求解过程
* w  [  q/ F$ D$ ^) }4 s& e& U. F# W% Y1 e* j  f
1414.png
! \; O0 X- Q8 Z! C& A$ o2 E6 d/ T! w; R+ e
特殊整数规划0-1规划
( |: b: ~9 M4 d* T- v8 _' o8 z9 [6 ?4 B0 }! z; c
即在整数规划的基础上增加一个限制条件 0<=x<=1
0 R& ~* Z+ f3 T3 e4 s$ l
, D! C/ q' A, p8 L0 J/ G+ l: S) \* D: D( Q) {$ n) i# C
1919.png
5 }1 ^! B/ |% \& F; }% A0 G6 i* d. c
1 ]+ |# @, O) i# \. G 1818.png 2 O9 \& q% O# H0 X: w5 S
: G1 L% X7 A" C, \) J
2020.png 3 @: [0 c& \9 n" c5 K
动态规划（了解即可）
( S& w- F7 p" @* H' n+ `: H+ D
  z2 B: W2 c' L1 @8 V, a简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
7 m- g; e) d& u$ q, [2 y
& N: d) h' P( c% _* Q- O动态规划模型的基本原理4 S( N- q! t* G
, z  m, r+ a# d2 e/ E3 K
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。- G* s1 q7 `6 c9 \6 {- N- P
  O3 x. W$ W! e( I
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。& D2 [% s+ ]* v9 v8 {; R
: `5 \( a% F$ u3 j, ^2 J0 @
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
6 _5 \/ z4 X% Q: e- G$ r. e
, x8 k) _7 c/ }3 ?动态规划的优缺点# o6 k. `8 n0 ^

" k6 g! {5 i! T$ g5 M优点：
% j/ \; j! v. G! ]6 r! R5 _1.可得到全局最优解+ J& _5 h! [" P8 b/ O, @
2.可得到一族最优解
# o; @5 z9 ]7 d# Q9 `, `3.可以利用经验提高解题效率  t6 E- S7 {( T' v  m& a  _: Y
缺点：
; b% ]3 S1 L' r: ^3 c3 R# C1.没有统一的模型& I2 Q( m/ u- F
2.用数值方法求解存在维数灾+ Q- S3 k1 Q4 p' j& T& R
/ W. v: V. h& A. }/ b
目标规划（重点）- x* S( O! P- L

/ X5 e- q( A& C6 h7 D目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
; G* a: F5 K1 e, g* d. X& L
$ x9 [3 ?8 W( f/ a5 {: X目标规划模型的建立. j3 G2 |; m  R5 V- Z7 \+ Y
) M: Q& |" U2 o9 U5 H4 @, p
2121.png
% w3 U( t! a2 @2 L0 y( x9 o: `2 h+ F7 p$ c2 W
2222.png , a6 V  q/ w  z0 ^( [7 m5 `) X; z
引入偏差变量的概念
! v( p$ R+ Q, q5 Q. k7 |. H" D! L) Q  r1 b& N4 R
2626.png 2525.png & y9 C% X& P3 Q, z5 i- y
$ l( z& K6 x+ x
2323.png
* ?. j: a; N8 {. H9 }+ v% m7 ~- |& J5 b# K; l7 e
2424.png
5 |6 Y9 Z8 C* O% _9 z: g, U2 x6 ^引入优先因子
' Q3 h4 p7 D% d* v5 Y$ b, Z% B" T7 c9 q. V* I. }! a1 r

# z& C7 Y- _1 \$ _! Y$ X6 ~
1 @3 J2 P& A) S# g9 C- j目标规划的一般模型7 ]) e% B7 J, a9 H
0 c/ Z: ~: R, K3 T7 x
6 |) B1 v2 w7 b$ ?
3 t5 `1 A: N9 g
目标规划的求解方法# E- r0 ^6 R, K8 f3 d* F6 U
) Q$ l0 G9 ]+ s, G
理论基础：序贯式算法
: Z  j- }+ F$ b按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。$ k5 I$ g8 ~3 J6 o: B7 Q

0 s7 e9 W" _: U7 J2 j, |6 G4 e规划算法的应用
6 j/ B6 N6 u& E! ]+ }3 C! O* w. s6 q
2015国赛 太阳影长的问题/ v0 V& Q' p3 A
原文链接：https://blog.csdn.net/hyqhhxx/article/details/1000719568 v0 ?+ F# `5 ]8 G9 y* d

3 `. H1 x+ Y( y/ U+ v: A* u2 R; o/ b. d

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

1313.png

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

1414.png

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

1515.png

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

1616.png

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

1717.png

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

1717.png

作者: 德古拉    时间: 2020-3-18 17:56
Nice shot, thx for sharing/ c7 b2 C. c9 A( P! Z2 G3 W1 Y




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