数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题
: E; Z+ ]- u  D; B! Q) F1 _/ v0 x5 q& r; P4 s4 r

4 E6 q4 O! R! q- z5 M- N" }*规划算法综合概述*
5 S) f# Z, J3 f7 Z5 i/ B规划的基本概念$ S) e1 Y: U+ z4 E" p! @; c& J. ]
规划的分类方法（了解）
0 O3 |3 ~; ]- e" J) Z! i求解规划的基本方法1 {7 w0 o3 B2 Y$ K# t
*线性规划*
8 H# |6 e6 T8 R: `* G+ h3 X9 s4 ?/ \/ _) J线性规划模型的建立
! x8 ?2 O0 p9 M0 A3 _线性规划求解
2 S! L& v) _7 j8 M  _*非线性规划*5 _" E2 m# ~8 [9 U$ `: @
*整数规划*6 R! Y5 _9 E( s" r( Z
整数规划的分类
+ @4 g$ g0 ~/ K整数规划的求解方法/ }  B+ p) p9 d* ~% ?$ ^  o
特殊整数规划0-1规划
5 O/ }. L( C3 G1 O0 f. T动态规划（了解即可）
/ ^) [$ R. Y+ w2 r& N9 t7 O6 e动态规划模型的基本原理3 c) c6 g$ \# v5 b0 t, d
动态规划的优缺点
* C; Y% z7 k3 d, X3 x0 |==目标规划（重点）==
( B0 @9 z# M% y( s0 e: R! z5 s" N目标规划模型的建立. y9 [/ }! G* g6 ]% `
引入偏差变量的概念7 c  m7 y! ~. [' o
引入优先因子" z& a! F9 F: p6 R
目标规划的一般模型
' x  P# P. R8 z6 B目标规划的求解方法/ k0 B/ K( M. o5 e2 |: C; g* a. Z
规划算法的应用
8 k( [6 K$ Y7 T* a装了半天数学公式编辑器，没装好，见谅。7 k0 x4 {8 S6 C1 {

" I/ K% A& ]! a规划算法综合概述
! Q& o/ W5 D' W( i! I
7 `- g. H( q) R4 S对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799* E5 S$ j) w% P3 p6 W) p  F0 D
' A; @. g( }  x/ l- P- \
规划的基本概念- {! N/ ?( k( J* t/ u) e
) l2 [5 f# A4 V. j! |; X5 |
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
! y" y. ]' F3 i6 ?  B 55.png
: N' m0 b6 ~# n8 e决策变量x，目标函数z，约束条件g(x)0 d8 r  j. d/ H0 M5 q0 ]; P
  @" H* m% v( p# A7 f7 t/ e7 x- |
规划的分类方法（了解）  p  F4 C$ n  l- t

2 P3 b$ ~4 }; o! v" Q! Q1 }$ K3 e1 b6 F( c8 }
77.png 6 m! K# A) ^) o6 H* U

9 H! q4 [! \: Q! _8 E" X6 j 66.png 3 V) a/ ~8 A2 M; ?$ c7 k6 a
求解规划的基本方法2 a: K$ y% `2 b2 R

5 J3 F! b7 @+ H* l$ [! `方法：在具体规划模型中会说明1 a$ V+ a( ]1 Z) X7 q: Z7 K
软件：Lingo Matlab
8 ]: V! R. _! O$ ~0 z) B  Z, A# p5 c9 @9 W1 L0 [
线性规划+ Q/ J4 A$ n- R! ^( U# r+ d
# F5 J4 i# W  A& l' d: b
线性规划即目标函数以及约束条件都是线性的规划。
  I+ A$ @. v( Z. C: d) }* M% k" b% ?7 b; e5 ?: R, {
线性规划模型的建立4 V, Q, f- y0 l& o; G  d
! q7 G5 V. J/ [% r; D* F/ _" J0 c
线性规划的标准化
8 x0 E) O$ t8 @8 h. T3 X( n& e
! ^. t7 y7 t; ~7 {! u3 @. ]目标函数标准化% `+ A4 P) {- e; Z
约束条件标准化2 Q" ~5 O) v8 F+ T4 ]& R
决策变量的标准化
8 L' U( V5 d6 s  I6 A' V! ^1 a1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)* c" [: G) x8 S( r" g7 G) y0 e
8 h" x0 K, |2 c2 ~  P* [7 z
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。! z  z( o5 G1 R9 @
7 L& n, J; \* h6 m9 Z& }. T
例如
) h$ {. u# T9 l/ |# s, B1 H+ X& A" v  c* Y
引入松弛变量 Xn+1,Xn+2
+ W1 ]7 i' I4 a0 W+ p: K( ^" c* I
+ x% q  n/ G6 d, Ca1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
6 u9 A" E/ O4 `9 j8 V& W2 E! Aa1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
" R9 l! @- ]1 }; x  }  N; [
& @  c; \! o& |3 ^2 p添加限制
5 g7 N4 b: c3 x1 J4 ]* dXn+1>=0
! V' P% ]" ?- O( ]& ^+ L% f7 v: TXn+2>=0
( e0 z3 t% ]6 [# k7 M& m8 Z& f, v  c# d. Z
88.png 8 @' R! ~' `9 d$ |" ?5 Y# j
4.因此所有的线性规划都可以化成标准形式：+ E& x2 ~" i6 x! G

& t: n8 Y& M; I& c2 l2 r. b' L- @# X 99.png
! e! \% V/ x( a7 f( T/ W$ P( e9 `2 Y
线性规划求解* @6 P) S. y* w; Q) F7 t5 f+ p

$ Z0 S! f. K4 I% @理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
" A1 w, S* p& ]. \% S, s
( s" s. J0 q" w- g+ }4 ZLingo求解1 i4 H1 Y# |6 y

  H1 t+ Y2 u. G- c代码简单# e1 ~! J6 {) S
结果易分析
; C' d; m+ X  {/ c2 _2 l  g0 K& N不容易报错
7 S& y8 O4 t0 h2 R2 n0 M 10.png ( k/ [  B1 ]. }' x; f
大概就是这个样子
& J8 D3 c' B8 `Matlab求解
9 R1 |; p' A. a$ L( _$ h, {! `2 K# p! c. n7 _
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。$ W# y+ V* p2 I, h3 W2 A) t: A
' ]3 q+ G$ \  J* z0 R: C' |
1111.png
' k' G  i0 G/ B: B; _& q所有量需要化成矩阵形式，负责代码的同学自己去了解。" d% u$ b: A) P9 O. a

. D; `4 @& E# f0 _, }  D6 @* V& s1 F/ [/ n: d
非线性规划
7 X( W% A7 ]; O; Y
* {" W. _& B% P: _1 d简单说就是目标函数和约束条件至少有一个是非线性的规划。
" Q4 m: S' I8 N3 r# V9 @) ~: c( O) M; A9 h) }/ E5 E' @
Matlab形式0 h9 ^9 D7 c+ a6 [8 `
1212.png & W; E9 a$ n( z) X  J. V
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。; C9 o- n+ `4 p. O7 E' m! @3 y% {- G
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
: t( d( G1 H% p) r! u! o) R" R& W# s6 I5 |
整数规划) Z6 G8 b8 U5 J' \6 n

) w3 H& i4 g7 y6 t7 o决策变量为整数类型的规划。( n5 r/ V0 C; U% l" ]
8 d9 r* g& z! y- D% T
整数规划的分类
3 k" Q3 `- }0 ]7 D, _% E
; J' i6 S9 n1 O+ n 1313.png 4 X3 l- T% l& Y7 N) ?
7 i7 r1 M, G& z) ]
整数规划的求解方法' e2 K$ a7 j/ I( K5 o  b
% i8 o0 k) I) I) {
蒙特卡洛算法
) R+ H9 V" ?; h) U1 S6 d/ [+ n蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。* M3 B1 ?1 [/ G) v9 P  k
  G( J  K6 p& x, I: j' @! F& I9 F) M
某整数规划题目的求解过程
- W0 R- F0 |( x* c5 P2 n# I" A  z& L* M; z1 l, I* o) {
1414.png 9 |( n7 ^$ f; m! Z* s8 G7 m. ^& g  q
5 Q; W. `* `0 G% |5 N
特殊整数规划0-1规划4 V. e2 y" T( y3 f% P9 V

0 _+ W8 N. S% l9 [即在整数规划的基础上增加一个限制条件 0<=x<=1
8 X* E% g5 X% g6 V. U' a( s0 u1 F
2 T' x7 w# B$ a. |& m0 D4 r8 ^4 Z# q2 e2 c
1919.png
4 B  f. {! A) ]
) o! `  k4 v3 ` 1818.png ; a& G. d$ H. c

) H( q8 M0 B  n' ~: [ 2020.png % E- N- [" z4 ?2 P0 |* h/ l! `) g( i
动态规划（了解即可）
# d) p) I: f' ~0 A6 Z- D5 |. s- Y0 X9 o1 G3 c6 i" D0 H
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
- X& W3 W: F& x' H7 _) n
' f3 n4 h, S' j! ~  Y! Y9 [动态规划模型的基本原理, g9 ^! W' G! [6 u8 r7 F+ z
! H) \% w. U6 c' C
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
3 h4 W$ |. A9 B1 e# F& v  f+ b# ~  k1 z7 L0 f- R
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。( H  i5 Q/ d' x$ m0 H, G  ]1 H
; {" {4 o1 s. ^' b
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。# U0 {# {) v7 B# R' V1 b1 Z( R
$ D/ n9 X1 e6 {+ O8 ?9 K' h: v
动态规划的优缺点
  x7 Y; C. ?1 `2 F4 V; r" K5 u6 F% E/ ?$ c) D% y" X
优点：
0 m/ T) c7 n2 [! F1.可得到全局最优解
7 R( B3 t) _' U# }! j. T/ R/ m. q4 P2.可得到一族最优解
: ?5 P6 T# s9 B3 S) ?, ^3.可以利用经验提高解题效率
4 b: k  z; ^: T/ P; t缺点：
5 l+ Q1 l7 ^: W- k' |1.没有统一的模型" N0 {  i. @* E) u! [. A2 x
2.用数值方法求解存在维数灾* k% O: J' @/ m4 D! B
! L2 ^$ U8 N0 _' H+ ]$ ^( [/ S
目标规划（重点）' m) b8 I5 ^6 S
  e' E. L2 ?" X* P" U( D) K$ m
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
, L. Z( p8 W1 R8 |
  [0 \0 Z, X) U. r3 r% m, \) i目标规划模型的建立( S, c+ L* F8 F) ]2 ^4 Y
5 O/ M2 M  [5 h4 _4 S( H4 b9 T
2121.png   t  h& i" {$ E! i8 i; e. d
; [4 s3 q/ w: q! g7 i0 y
2222.png
; t7 s) h! O0 l: O/ \& W引入偏差变量的概念
! C$ w! }2 [7 Z1 \
% J7 Y' s) i5 V& p 2626.png 2525.png
) e' e6 d+ h$ ^  S" \5 Z7 f1 j' j  L) ~& V
2323.png
; h* n0 o# Z$ j& A0 b) N
% }1 p  m, U( ?# ?9 s8 D: a4 r 2424.png 8 G( D2 ^$ a" e+ P* G, T7 g
引入优先因子. a6 I  D5 l: |  n) M1 m* W

8 h7 n* v; G, }( z5 J' |3 I) r7 b

% s8 w% X) Y; j* k. V4 `目标规划的一般模型
! m8 P, c/ X: V& f! }6 b- D4 [
$ r/ g$ F/ U- @8 h8 `6 u
$ j# j/ A# E& {' q
% V; k  G* U  T2 V# p目标规划的求解方法
9 X- ]" E) G! e  o
; \) z5 i, [  W; p# g; }  l: b理论基础：序贯式算法0 ^# B- u' X2 i; q8 e. C3 \! h
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
6 O) n: ^0 Y! O0 y5 g+ s- i
: ^, C& [- J. `3 b' {! O0 w规划算法的应用, r( h) w( a1 y8 p+ p

  Z8 T4 X, U5 N3 U7 }$ S& U2015国赛 太阳影长的问题' u3 V- q" }; V: ]0 J6 p
原文链接：https://blog.csdn.net/hyqhhxx/article/details/1000719563 X& N3 p9 p% g0 i

6 V. O. M# ?4 ]2 |7 M+ q! E( v  ^) q% f: r* u' G

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
/ R2 @) Q; l) {; T$ Q8 B



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