数学建模社区-数学中国

标题: 数学建模中的规划问题 [打印本页]
作者: 杨利霞    时间: 2020-3-18 15:42
标题: 数学建模中的规划问题
数学建模中的规划问题) t/ A# t6 [  @* s* K, s
* ^9 }2 p& Q5 |0 S  b- ^
+ ~4 u+ }$ I0 B0 Y6 D3 a
*规划算法综合概述*6 s3 R$ K7 Z7 R' @: Q7 e
规划的基本概念5 Q4 {9 L8 J7 M7 ]
规划的分类方法（了解）" ~0 h% V8 T2 _9 P* C0 ^
求解规划的基本方法3 t+ C) j6 y' n( e/ m8 U% f) D
*线性规划*4 ]4 j  a1 ~# k4 M
线性规划模型的建立
0 K8 O" k" S8 L+ A线性规划求解
( d: m. h' S* @8 _% d*非线性规划*! e" q% W' K- ]$ F/ P1 I
*整数规划*
" m) a7 ]5 K+ ^. l+ S  a整数规划的分类
- j6 {* l9 F+ Y+ j! ~9 n整数规划的求解方法/ f% l) j7 o2 |9 S4 v7 y
特殊整数规划0-1规划
% K. ?/ H/ w5 F: R动态规划（了解即可）
+ U2 o& j% P' @) v0 d6 T动态规划模型的基本原理8 h3 Q+ m6 Q* q) ~
动态规划的优缺点) Z  T: Z) Z6 Q. c% @3 l0 ?
==目标规划（重点）==
, N' x  n9 U1 E6 @& j6 ~% V目标规划模型的建立
' B( f/ |1 e8 N: L+ i引入偏差变量的概念9 a0 Z# g/ P/ d- h' b, N0 R
引入优先因子
& ]% T& j* w9 J目标规划的一般模型% [% t6 K4 n, Z5 p5 E
目标规划的求解方法, z% y) D, m2 w8 ^+ z
规划算法的应用  L% D9 I/ F9 ]8 q1 z/ _
装了半天数学公式编辑器，没装好，见谅。
) Q4 ^6 \: ]& i
1 B) L+ |# k; t8 s& K  ^, m规划算法综合概述8 P7 C/ T' E* K; n% s
/ `7 l5 _0 i  U
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
+ F( P! L; P* R; h# R! a' k  |+ x. t3 t/ C+ P
规划的基本概念
2 u6 d) o0 ]# A
8 a* E- U0 ~. i6 E规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。+ S, q+ v8 \4 z& i" I
55.png
% V" L* o, e& g2 V2 f决策变量x，目标函数z，约束条件g(x)( M) L+ F# z9 q* O: T; w. g, ~

5 R6 r2 M1 X7 W0 M' }$ Z规划的分类方法（了解）
$ l( l, ^+ S) E) |2 J; o% v+ k9 N4 i, w; {, y. Z. b

" X- h* W' z2 I 77.png
, u( _; m! [0 f& k( `2 G, O
& Z" c  y# F& a* f 66.png 2 R/ q) Q' ~& u+ E6 D, Z
求解规划的基本方法
0 Y) f& v5 g$ F* A9 Y0 f: |# h# F1 L- K
方法：在具体规划模型中会说明
2 g8 d8 @: O, l, x3 E软件：Lingo Matlab/ f9 o: l  G$ [9 h, w
# B" T& [2 W$ ]$ s* g9 j
线性规划6 i4 Q9 ?6 f" v: g+ b( D
6 B) L8 e3 w7 N# T' a
线性规划即目标函数以及约束条件都是线性的规划。; u! M- u$ X4 e+ O. T/ {: g/ B# Z7 O

3 F/ l' @$ W' Q  K2 \' I) r线性规划模型的建立
- l) Z. w6 `% C+ c8 |1 Y9 W- J5 P2 {; n2 e0 y/ e
线性规划的标准化
' m/ Z! B) {6 {" G9 S4 o. R5 j3 i: V) `2 ~" ]* Q. l4 q( [- u# }. z
目标函数标准化) Y6 w& e6 Y5 Q' @) O9 B4 q
约束条件标准化
$ z6 z/ y% Q5 z  w/ i决策变量的标准化  T( j, e; J2 T& o2 `9 x
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
/ e* x2 d# o4 i) z
8 |  ^" ?& D" ^% ?7 x- x2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
- C9 y. H" X8 x; I4 j% a) q
" N9 d0 A$ g: G9 W例如- |6 v0 }' _! R- e0 y4 W

1 `1 s; |7 j# \! h# e* L; _引入松弛变量 Xn+1,Xn+2$ W1 U, l" [5 A

6 P# r7 j: e8 I- V0 I: ta1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1: ^0 Q+ T5 i) S5 V
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2- [( t8 N3 ]1 ^
$ b7 r2 _8 R% p  R' j
添加限制
/ |( W6 ~0 p+ t+ Y7 h% B0 KXn+1>=0
' S! o+ U9 ~! B) Q, U/ q; b$ C; xXn+2>=09 l/ [+ B# l% M3 c3 b( Q
0 `( B5 D5 R2 A; D& }0 q
88.png
8 J& |1 |/ N$ N0 C4.因此所有的线性规划都可以化成标准形式：
/ k  b8 p( s& U" A
$ t. x& i4 W! c! L3 |1 ~2 t2 W 99.png ( @0 r5 \- N. d4 r
/ ^0 [0 ^: N. Q9 S
线性规划求解
9 A2 d, C) c- p; F8 x
: j# K+ m/ L& }- a+ Q理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)- o8 @# \" p& v' {
0 n- U1 F# I* `7 A8 A
Lingo求解
4 C  J  W! v$ U7 u( J) V/ L) y1 D* v' M8 A$ l1 V
代码简单+ `0 @( y) B  A8 ~/ t$ u3 H
结果易分析  U( F' D3 n. l" R: r
不容易报错
# `" J* ?8 z( I% m( V# Y3 O 10.png 0 v, m" w$ a* k( f
大概就是这个样子
6 y( ~4 G8 B  k4 SMatlab求解7 s1 y9 b% k  S2 {

$ r. |) J1 x+ M: |5 C# f& S. Y其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
$ S8 e9 f4 x) d5 v3 Y0 R8 x
# O& `$ u, V* C* j- e% g( A& h 1111.png
) q+ f/ k' H+ J! m+ O6 e所有量需要化成矩阵形式，负责代码的同学自己去了解。3 {# v3 {9 U5 U- V6 K2 r
1 R) p1 V3 ?6 W) u6 y3 k
6 i" e7 f& e% m
非线性规划
1 u" a$ c. @0 e( i, W: q. e( U' t5 ]
简单说就是目标函数和约束条件至少有一个是非线性的规划。( {; d- W. e- k5 N# @2 R, b

1 }9 h  W6 v  IMatlab形式' e5 B5 ]9 t- ~
1212.png
4 o1 v- C$ @: z2 t: T从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
8 A! v, p  [, x) x- ^7 Q" o总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
6 ?8 F) H1 D% M: y" r3 U- P0 z/ Z1 C8 }6 O
整数规划
2 }# y4 V1 k2 n. L1 `
4 R; ^6 l  [& [$ _决策变量为整数类型的规划。: P/ j( g5 U2 T. A- B* b
- m2 \" ^- C- W; @2 |
整数规划的分类
" J! }; j, r6 z- l
6 H8 G2 b. ~2 j. o' k 1313.png : O' h3 Q  D' q/ ~9 F
' E( z* v1 z# y! Q
整数规划的求解方法
, `' l: c. |5 e2 L% C- I1 @/ \/ z9 T  u" k% _
蒙特卡洛算法
! j% @; z* [2 V蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
0 U* Q" |$ f" I3 _, p. ?2 X  L9 X7 o! @0 b
某整数规划题目的求解过程% f' n0 @4 K! d6 r4 c
+ t; k* M4 ]) w, g4 C( h! _$ w
1414.png 6 I+ b" q4 O4 \0 u

4 H. i. j/ t" V6 Q特殊整数规划0-1规划0 C% |7 D* k- R9 ^5 C+ K
9 s: y  h# k8 s; g5 K8 e* v
即在整数规划的基础上增加一个限制条件 0<=x<=1
: f+ I, B) `: |  f/ W1 z: N
  L8 H# u' a, \' N! }6 i% ?! o  o
/ k% a0 E, z* Z- z7 B. d* z; h 1919.png
2 a4 q; C+ n* O' w0 ?9 O$ |% p8 q- Y" S( E8 L6 c
1818.png ; w$ y0 c- w2 ?7 f) v2 _
/ B3 @/ Z  v1 \) M0 j( g$ _
2020.png 0 X/ o% L6 v" V2 c: `5 f
动态规划（了解即可）
- A4 @6 h5 m) g( X9 P. W2 M) [. }+ S/ P- L$ A# @) P/ g
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
- \  W* q% W; O" \# ?, c: `
+ `5 O' U+ u: g/ N7 T1 A动态规划模型的基本原理/ n9 j1 x' c& a- l, M; y
. S" u( z  ~8 V4 n- ?
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
6 Z) T. V0 `* `" H, X& B
, R$ b% g5 l7 `9 L+ \& E1 `贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
) G) h4 d) }; y7 y9 g# t) q5 E1 ]
1 J1 K# ^$ y# }* `/ D* R逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。. a4 g4 G& ^1 B

& X1 Y% T' `: U! W) E动态规划的优缺点; o1 J% r* i6 |7 n
7 Z4 L# M/ C! }8 L3 A' ?
优点：* a( y! i2 n! M) n: \/ S
1.可得到全局最优解
1 q& T5 k0 [& D; I) A4 M2.可得到一族最优解
) l' o+ c  H- a7 d) @0 w; W, X2 V3.可以利用经验提高解题效率' A$ \& `5 z+ y. _4 b
缺点：
5 D* W2 M! \& L1.没有统一的模型5 ]# a3 B' R1 I# m0 q6 L
2.用数值方法求解存在维数灾
- W1 k% |2 J. f; d) ]9 Y
+ h- h1 l. S* [1 r目标规划（重点）
, H% A9 k' I3 B4 i$ l3 S5 X7 `- M
) c( y7 U1 @3 k/ F目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。9 G- B, h7 M/ T% `% q

( P# H9 F+ _9 e  i& Z% x目标规划模型的建立/ ~) @% e! B5 |5 P

2 K5 S; Z7 M, o& w1 c% y 2121.png
  M% G* f! o% H$ R" S
; t4 U- ^+ r2 h. H 2222.png
; x; M$ _5 k0 b8 M) j! W5 s引入偏差变量的概念
8 T# _$ _1 v% y( z: A3 U
2 D/ v# N% d" A) D4 ] 2626.png 2525.png $ S+ S( o. l9 k. J% q% Q! _+ J

, _3 M* n5 o+ j! S# M& r3 q 2323.png . p1 l6 h7 W& T3 V5 a

/ ]. ^( j1 Q7 Y+ u: S. y 2424.png : W- r$ Y$ |/ k4 o
引入优先因子" v& d1 t: P  D

! C" J( p. Y- ?# o# a8 S/ u* D" i

2 {2 O' e+ @7 Y" \+ e+ j# f6 D  y目标规划的一般模型
8 P) v' }. j1 k8 y0 h' N9 R* V- _' m4 J" I# l- C  m1 q

/ J4 z+ q7 a  T* p5 v$ |: W6 B  s0 C6 x
目标规划的求解方法
7 Q# I! D$ p7 \* c2 y
6 A# o: d2 e7 R. L& X理论基础：序贯式算法
' A2 b4 y9 n$ Q5 {( p* i+ c0 ?9 b按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。7 o3 J  e8 C- W+ b
( o8 X5 y- O3 \5 @/ J
规划算法的应用; C8 ]6 O+ W! v0 f

+ G3 F( y: Z. w2015国赛 太阳影长的问题( ~7 g- N, {7 p/ t
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
  @4 |4 F7 ^, T* Q
8 O* ]. x4 t% r: X, ^7 R6 t4 t% T' e/ u/ }# i

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

1313.png

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

1414.png

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

1515.png

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

1616.png

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

1717.png

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

1717.png

作者: 德古拉    时间: 2020-3-18 17:56
Nice shot, thx for sharing. ?" [! `: W% ]6 l




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