数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题7 f% I  H; B+ {7 z: \+ w7 H

( P( _2 E5 r# _+ H# T
# \, U  ]& l! G! D*规划算法综合概述*
6 G5 P) w" B# J0 L; i/ g规划的基本概念; d4 Y) ^" ?" W# O
规划的分类方法（了解）6 e0 J9 p: ?) m/ v
求解规划的基本方法
# r4 F4 n4 p- O*线性规划*
, V. {# @* a. N! Z7 ~线性规划模型的建立
% D. r6 f) p( G  h. r3 u( `线性规划求解& W$ _/ d; y' a* U
*非线性规划** k' e' C7 B- n3 {3 a% D. U$ }
*整数规划*# y$ R' x9 y7 z3 u8 f3 g; f4 E
整数规划的分类
, c1 U. }, W. n( A, ]( b3 x; y5 f2 S* ]整数规划的求解方法8 F7 h& g5 w( V4 p% u5 p4 b5 ~
特殊整数规划0-1规划: G/ j$ |& D% i
动态规划（了解即可）
8 B' x# ^3 d/ F  Q( D( t2 P动态规划模型的基本原理8 R% Q  J; m' X7 }+ H1 g8 Y- R/ F+ n
动态规划的优缺点% j/ D) x3 Q$ u" \3 k" E# v
==目标规划（重点）==
4 h* p( V( r9 w- b5 n, w7 ^目标规划模型的建立; P" y- p8 p% D& c6 C
引入偏差变量的概念! _3 c; X0 o' C$ I: a1 Q6 K% r4 z
引入优先因子/ O: n& b) W/ F3 X( ]+ h
目标规划的一般模型
) K2 S- O% g- n目标规划的求解方法7 t1 j1 _4 n& g
规划算法的应用6 l) M% j9 Y" Z9 C- [9 c
装了半天数学公式编辑器，没装好，见谅。+ e( B2 @7 }8 g
* i# A7 \% `6 {! G( z
规划算法综合概述5 i9 T  p6 q7 `) g0 t

% P1 }/ M) Y* Q2 h" q对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799% N2 v5 s1 n% i6 R% F, T
9 L4 K6 Y& r9 [' }
规划的基本概念7 F- i6 F' y9 N, U+ ~! d
3 T& {% m/ D( {' L/ e0 f- e
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。7 w! _0 ?5 T* \" C
55.png 4 u1 |3 N  D" Z" ^0 T" Y
决策变量x，目标函数z，约束条件g(x)6 D$ F0 _8 r! V7 S; n0 i

) o  _1 N$ [" H+ g( _: [- L规划的分类方法（了解）
6 B( m/ X2 O1 S7 Z- v) S1 E5 O% ~3 ?" b5 u2 E
# U: [/ D1 [% _) I; N+ E1 K4 N
77.png ; e6 b5 ^4 ~0 M, _

/ x  L3 H! c3 C) S# f2 l 66.png
# [' }, z' Q3 Y1 Y, F求解规划的基本方法
1 n/ b, \' C. T7 }1 W- ]( _  y- ^& R# Z& o
方法：在具体规划模型中会说明2 [( H$ E- l" f. ]4 i9 {
软件：Lingo Matlab
: H% v0 o/ ?* X8 i$ H- ^7 N
. j: E4 M4 d/ a+ J8 a  w( j, ]线性规划
" Z' D  o  I% B7 u. z, S) o+ o! J" E2 E, D) u& @# d
线性规划即目标函数以及约束条件都是线性的规划。2 S. H; V* ~1 t; ~" A' [

  D* I8 E$ o4 n  `0 |线性规划模型的建立
+ n4 v, n' k' }% S# i( G7 Z% @" J; j! Z0 E
线性规划的标准化+ q5 y6 \, E0 r' r3 t; U" V1 c

1 v6 R4 G) I3 o& C* T" F; ^7 G. k. S7 }目标函数标准化
8 t& q& g# k3 x$ C* {+ T: o: n约束条件标准化
6 B# \+ u5 P4 ~1 I/ z0 f决策变量的标准化- O2 h' Z$ O& L1 [3 \" }* J0 `; v2 o
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
9 m( {/ m9 g$ W+ G% o8 P: D) j# y$ \) h1 I1 L
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
4 j3 ]& \+ L# a* @
6 o# A7 ^7 d' ~  z" U例如9 u4 P6 a7 j! G1 w. K
# o! B& y# s- Z
引入松弛变量 Xn+1,Xn+27 x! X: }- }' L4 k/ B& D7 [( \" J
, V6 c; v% x5 [6 F! h4 J0 x
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1! A5 t' J" ^, \2 a+ Z
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b28 Y1 r7 Z! J1 l# h/ f! X

3 y1 d& l3 }% M; l8 y* D" s' y添加限制0 g4 A7 D- g: O" n+ {1 [" _. T; f
Xn+1>=08 j! V) m2 E! @5 @* @3 `
Xn+2>=0
) j9 y# v$ _3 m2 v) j* G  }) ]+ Z7 |
88.png - {# v" z& \( n' Q) s& R
4.因此所有的线性规划都可以化成标准形式：5 j4 W$ @$ I; h) f

# D! Z  g% q. `+ }& h 99.png   ]) w& v; p$ d( K- f- Q

: R$ O: i/ T, b4 N) n* K8 C' E线性规划求解- w* @5 A& N, E; r* U" Z
& n+ `/ f. }- U* J
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
8 q, s5 Z1 U6 o& W: ?. w* c0 r4 q
3 ?: d" Y2 p6 o8 ]% ^( XLingo求解3 a+ F$ j' {2 B. Z5 m/ y
0 o: p7 I1 Y9 b: M
代码简单& B5 R& n. U" ?+ u
结果易分析
0 K3 F5 H2 ~) ?. e) T9 l/ s不容易报错
9 a$ W) g: s! }( U 10.png 7 ~. }7 ~4 {0 @. ?; N+ }; b* d  f
大概就是这个样子2 g% h6 E. z6 n9 o% R
Matlab求解; w' ]: p$ L$ N% ~8 \
8 B- P1 a3 Q% {1 k
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
$ |0 h, B6 N: n; m
3 a  ]4 Y8 n. G* _: D 1111.png / V, I4 E! b/ l9 f
所有量需要化成矩阵形式，负责代码的同学自己去了解。- E- r- Q% Q2 u# x$ J
) T+ j. `8 x5 P

% M* N  k2 w# _  l, P6 b( L& z" J" s非线性规划
( y# W' z& y: p+ f; N& N$ c9 ?- m7 ~
简单说就是目标函数和约束条件至少有一个是非线性的规划。
: E6 m0 T6 F/ e
- e1 D2 w. L3 yMatlab形式
+ H1 d' T# E6 y5 I; a$ x2 C( s 1212.png
/ G1 |' ~+ z- Z  b) Z从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。7 P9 g, o  d- D2 W  a$ [: W
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。: h1 e- |  k  B+ T* f' T

& H% E3 x  f# }; S$ g" C6 S" s整数规划2 v1 U# F* m+ w9 r* u) r4 d

, p: Y5 y" Y( P9 F( y决策变量为整数类型的规划。3 _- k+ m8 m' R& v" R! ]
- k8 [7 j  ~" G' E' {
整数规划的分类* _! g7 n# _8 d! b

3 S- o+ `7 W  K' b 1313.png 6 M5 `! P0 y/ C2 o; z) A

7 j1 a. k! r! Y; j整数规划的求解方法4 ^( {6 x! f; A2 j

' Y' e  |6 o% h  X; w0 L4 r# G* C( v蒙特卡洛算法
  s' Y3 Z9 X9 g4 {蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。! D. F7 u. S6 Q/ B, A
9 E5 N5 g0 {9 B7 ^" q% E: H( Y
某整数规划题目的求解过程
) I3 h9 A; O0 v4 T9 T, P
) p; _; r0 e" M" M3 E& N" O, t" E; Q 1414.png # `, t3 M0 [: C- C. o' Z

+ x( W3 M+ L2 C7 j6 G6 c$ i) a& n$ b# P特殊整数规划0-1规划; k, X7 @6 E% T' Z

8 Z+ \8 [# ?# K即在整数规划的基础上增加一个限制条件 0<=x<=1
: ?' p9 ?+ h4 X% `/ n, E5 E/ Y' |% I1 {( M1 D
' u* r: W! n$ A! p
1919.png $ ?/ o' z- @; H6 ^  C

: |1 h0 ?# g# t# d7 I/ H2 Y 1818.png
4 E! {2 [6 {- F+ ?! e/ {' [* R% Z3 G4 P3 t  L( ?* ?* b
2020.png
+ @8 i  o8 h" Z, Z: D9 @; O动态规划（了解即可）
7 G% S% w5 ?1 Q$ z& v" N  U, U  \* u# H
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
- D$ r( N% O: K) h& D: p! j7 z
9 o" `5 _* a( d) p& z- a4 R* y动态规划模型的基本原理
7 e* ~) ~6 b( `7 J" F; T! i# G- K9 @6 c" B# K+ t4 I& [
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
& m: h2 |2 n9 A2 E: @) G$ z; F2 A5 M8 j  Q
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。4 e* _0 c& \; j5 V+ H
+ Q, x6 Y. N, q$ l4 s5 y0 I
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。3 Z/ ?6 T' k% U7 H3 L
) D* c6 k3 p: o/ h1 S
动态规划的优缺点
" f( r; V6 m0 n' Y" ^; D
/ r( x9 o0 _, W: W0 E优点：! y5 I2 B5 o3 J' w& j# O
1.可得到全局最优解' S2 T$ q* O+ d" u
2.可得到一族最优解
% M. e0 G9 ~0 {9 p8 V3.可以利用经验提高解题效率  i* H" {; B4 D! ~4 Y( h4 \$ c6 }4 e7 a
缺点：6 Y2 z6 B8 d( j( |) x& o4 X( n8 p: `
1.没有统一的模型# |( m7 i, w6 o: w
2.用数值方法求解存在维数灾0 ?% j3 l9 A9 v/ r) o; c

2 {( U* o" }6 O  f& w目标规划（重点）
& F$ t+ S. C. S& z- ?+ ^  q0 M; \
; d$ G6 g$ k. c+ h/ E目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
7 z. E: ^" p! z3 g; a$ T# C7 Q3 X5 x# D' [' c) T
目标规划模型的建立
- y( u* |( _& L9 m7 \3 P) F# ?' J# T- W4 V) M3 Q: \3 e, ]/ }/ C2 F5 W
2121.png , B) e7 u* T9 [- u9 e. h
! E, N" c1 V* _* h1 D* F5 ^$ \
2222.png 3 \: N9 J& p" ^9 F$ j3 f  u9 `8 x6 L
引入偏差变量的概念
; E/ j4 A1 I: t4 ?4 h
# T- s; m, F. T8 A 2626.png 2525.png
  R# u! M) ?1 s0 U
. \* ^% S5 }. k2 Q& w/ d1 F, D 2323.png 6 R3 D; Q$ @, a, N) k9 r5 u7 ^3 e
4 q, S/ @) b4 B, E8 V+ G
2424.png 2 R0 v3 C( D: Q- y( s7 {
引入优先因子: L- q$ D  N2 V. h4 I. f

4 I# y1 O1 q; u! T. H) v
1 T: Y* L& `! r& }0 \" B* ]( A  V) c( Y- |3 K5 M" S" J' O. V3 p
目标规划的一般模型* ?' N. `* {, G0 D+ ?! h3 z

; y/ @" A! W, E5 v) Y
, M: |: _+ `4 ]6 V& V  Z' Z1 j
  @  Y* O6 l2 S' q目标规划的求解方法! z1 C% s6 ^  H) }! |; j& L% w

) A6 M: Y$ e  J9 G9 v" N% R$ f2 {理论基础：序贯式算法
$ S; i: E0 E7 f' I- i- u: ^按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
( c; S+ @* f0 l7 Y6 d
/ h4 Z% [5 q: s规划算法的应用
7 x" S, {. h0 @8 x8 x# r3 r" M( w% E' Y  \( o/ p- N+ d9 V
2015国赛 太阳影长的问题6 l3 ~( M3 t4 l' e8 h4 U6 x
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956! I2 x; m# c7 z

+ p: T1 g: ?! {4 R4 |. L% F0 l
. I$ V: A5 [  L. f

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

1313.png

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

1414.png

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

1515.png

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

1616.png

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

1717.png

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

1717.png

作者: 德古拉    时间: 2020-3-18 17:56
Nice shot, thx for sharing" y6 y  z, T& d+ g& y% t




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