数学建模中的规划问题

杨利霞

数学建模中的规划问题
0 f  X# q: L( z' l2 e1 p
+ {9 G3 R: X+ O
6 w# f4 F5 b2 a* a  l*规划算法综合概述*
* A* O% N$ e4 ^; }规划的基本概念
( W6 w0 Z* D& v6 {规划的分类方法（了解）
求解规划的基本方法
0 ?/ T+ P1 i- j" m5 E, w: V*线性规划*
. E# @4 l7 \. U( e6 u1 q线性规划模型的建立
线性规划求解
  A$ U! h# s5 k" ]' D3 C9 |4 u*非线性规划*
7 E/ {2 U- A. j) v# x. T*整数规划*
整数规划的分类
$ j' q% R9 z  `6 f2 l: ^6 H# I整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
0 Z/ B8 H5 c. g% f动态规划模型的基本原理
* `6 O2 w. t' m  V3 ~, i7 ~动态规划的优缺点
3 x" E$ z5 M) c==目标规划（重点）==
* ^0 h0 \: c" Y$ T- D9 x/ Q5 i- M目标规划模型的建立
3 w0 `7 t$ J2 T, k% [引入偏差变量的概念
引入优先因子
目标规划的一般模型
8 u: s5 l" n* o目标规划的求解方法
' B& ]  B' J0 G( @' S1 a: }规划算法的应用
- p8 D8 N# _6 L/ S9 \' c  @+ d装了半天数学公式编辑器，没装好，见谅。

$ A% i4 _6 z! l, u% I) B. B规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

- c8 {2 W+ D/ Y规划的基本概念
* T+ t/ X8 n& E5 X) d- ^
' L! B) B/ @4 U) F5 G3 ~规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）


; L: P( T: V" a! Y5 t


# f  J7 ]2 Z$ H求解规划的基本方法
0 `  T0 Y, ?. ~  |2 e5 L. M
方法：在具体规划模型中会说明
/ U0 w+ e! V( E* ?8 X# D% ]! \1 W软件：Lingo Matlab

线性规划
3 v6 }' F% y" I# F( M% v! i1 d+ w) S
线性规划即目标函数以及约束条件都是线性的规划。

# A# j3 R  f2 Y: V  M( ?4 Q: e线性规划模型的建立

0 y7 ?2 W; P  K2 I& s  R$ {, w线性规划的标准化
  x- B; ~) W, r1 I) m+ `
目标函数标准化
/ X7 F; X: H, p2 I6 O6 S# Z约束条件标准化
决策变量的标准化
+ D  i5 j1 }( t. A5 J! N1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如

引入松弛变量 Xn+1,Xn+2
2 Z+ p! X+ a' p5 F0 W1 s& f6 E
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
$ @# ]# H% E3 Q) t0 ^" |  q" ?a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

7 O1 m+ d1 h$ L# i% ~7 h/ i# q8 H添加限制
7 d) Y- Z0 `" q' J7 Y7 V' D1 sXn+1>=0
Xn+2>=0

, q& Y4 G0 N5 F7 V/ X& r
, w5 A, X3 e0 s( l2 V# X" g4 ^4.因此所有的线性规划都可以化成标准形式：

4 v1 l, ]. s! \7 ^; y4 a7 Z
( N* p9 Q# V$ u% ?( |% p4 X; N
$ P: s3 B! o8 B+ s7 T线性规划求解

# B, O( ?, L. K) n! h; u理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
: K* H: s: P6 d/ C( U0 f
2 W2 D4 P' L2 V3 d$ w5 Q2 |! X, tLingo求解

代码简单
结果易分析
不容易报错

8 t5 g! n) M1 q! @/ |& ]% {大概就是这个样子
! ^$ W$ y% J: f; w- i! e& x9 r+ aMatlab求解

其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。


5 Y& M: }' D1 N/ P' @& ]* o所有量需要化成矩阵形式，负责代码的同学自己去了解。

( _8 d1 w' r' Z# V5 T0 q
, H- }0 B( T/ D7 L非线性规划

. G, m8 O9 V+ Y( @3 H- M简单说就是目标函数和约束条件至少有一个是非线性的规划。
0 o1 A9 Z; J* r- [- l5 [$ Y
+ i& @2 Z3 }/ Q" ~( @/ d! NMatlab形式

  D$ V4 y" h2 p从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
. l; Q" V: z, T! a: R+ a总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
. }6 y; F( V, |- B& T2 |1 h6 r
- w3 j: B0 A4 y6 [8 G整数规划
- h" W- h3 v7 |% D- {. J3 E
决策变量为整数类型的规划。

整数规划的分类

" d) f& O+ L* r+ [4 a6 }5 U
$ _& K. H9 ]3 q; M
整数规划的求解方法

蒙特卡洛算法
9 B4 M: f: N* J7 ~. G蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
7 J& ^( j# D8 H
5 U9 x' V* @" P6 H' \某整数规划题目的求解过程



特殊整数规划0-1规划
1 w9 v: z9 D# L. f0 f; H
) \/ I6 s: x: T- ~, D+ y' b0 a, @即在整数规划的基础上增加一个限制条件 0<=x<=1

! \% v; k$ j' ]5 \
2 m- B4 Q1 {1 y4 _2 h4 u  X9 Q

$ m3 I  Z- O( I+ b8 a' S" q
- O0 |& k9 J/ [

动态规划（了解即可）
) H5 Q  R& ~6 Z/ Q9 w( @) _' u" M7 n
8 B% A2 E; l; S0 i; E" m. K! R$ D简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
# F# |- p" n$ _1 P" H
: ?5 a8 f; h4 [. G贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
2 j) O$ v6 Z) [+ Z  R5 i* ]
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
; l" O+ G3 r, |- @4 y8 B
6 P6 B; O* ~# J& D' ^: Q1 i动态规划的优缺点
: W! E, i0 b- B' ^0 Z
6 i2 t- P+ E* `# n" P( ^$ R优点：
+ q: g6 B% g3 n# }' U9 Z7 f1.可得到全局最优解
2.可得到一族最优解
: a/ h5 K, G( V* O/ |3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾
- G4 g% Q# J$ H: s- O3 f/ P
+ C: k2 {' u/ M; I目标规划（重点）
# p! k" F+ j! \$ q) M) S, z$ @) i
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立


: l/ R; m; v$ C7 G8 i! t5 ~2 {, @

: d& I: B: @7 R引入偏差变量的概念




) l% P. s, C& [2 d! y9 W
- h+ D3 m( |- s& b5 U4 U1 V& S4 M
引入优先因子
8 l* `$ k8 ?% p

! H/ Q# T/ ?  W4 D, c* }" i
; `9 H$ q: q+ J& j目标规划的一般模型



目标规划的求解方法
8 X/ k8 L4 w0 d# ~
理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
- n9 \& H# ~$ _( O2 E- r
规划算法的应用

4 _8 i$ k+ m( c" Z: t1 r2015国赛 太阳影长的问题
; u5 C6 y6 j9 X# e( F+ a' y原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

$ [, Z- {0 b) ]% v* u+ U
) m/ [! z  o( w3 T  y

德古拉

Nice shot, thx for sharing