数学建模中的规划问题

杨利霞

数学建模中的规划问题
3 U3 p* c+ e8 b/ y/ n. v& v" w3 X" s

*规划算法综合概述*
) i, R7 K, e1 N6 R; ]8 \. P规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
  Q% L$ H5 q. |! H% a) L*线性规划*
' B2 d9 @9 v1 E7 V. r) S线性规划模型的建立
线性规划求解
*非线性规划*
" Z- t/ Z7 V) E# v% d  E' C2 v1 P  U*整数规划*
整数规划的分类
整数规划的求解方法
特殊整数规划0-1规划
3 f2 H1 b! t0 R) R$ B# T; L# r; C5 M3 l动态规划（了解即可）
动态规划模型的基本原理
/ I6 }6 Y9 S5 }; m% A3 ^动态规划的优缺点
==目标规划（重点）==
+ ?  T# |5 ~2 T3 n4 H3 V4 ?1 v" O目标规划模型的建立
引入偏差变量的概念
引入优先因子
6 W/ H" ~6 U+ K4 R+ }目标规划的一般模型
5 {# r$ e& J3 E7 Q0 O/ R5 {目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。
* M3 J8 ]1 F/ Q7 y
' |+ g' j9 Y/ X7 p& b  N规划算法综合概述

) Z( G- A# N4 d. C# Z0 Z对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

+ I6 B9 T8 F8 ^  |. O/ E( b. W4 S规划的基本概念
* K1 \" l: r$ L- N/ n1 ^
& Z9 s7 H% _! L1 v% n, E规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
  R% _! e9 {, b( l
* ?# G8 L) k2 H! d, z  m7 o决策变量x，目标函数z，约束条件g(x)
. T7 M1 x! m, q% `9 r* i8 G, s
' U# I7 Q( M# L4 }, _3 \规划的分类方法（了解）

6 n4 V  q, Z# b# l2 v- R9 b' B
* l. a+ L& {: [# @5 T. R

0 o' w% x2 K) Q. b7 k+ a- a* i
* N, A4 J6 ?2 b  W! C; j2 L求解规划的基本方法
8 D+ ]. N8 m& H5 ?% \
& O+ |& [4 g  j4 C0 W' E方法：在具体规划模型中会说明
2 u# e, g" F4 q' {0 o软件：Lingo Matlab

2 W( I! D/ U+ J, G2 ^5 e线性规划

4 D7 b0 D% M% ^/ g# |( D) G线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立
5 ^- h. V% I3 j
线性规划的标准化

目标函数标准化
5 Z0 Y" L- w" g3 E: P. x约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

$ |# u- @" E' U- x8 j. h% g, N2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
" J4 _; U. ~& C  O' L& H
例如
* c6 N8 u$ w) f
引入松弛变量 Xn+1,Xn+2
9 Y6 m# {  _, r* _8 B* n
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
7 j$ I& ^$ Q3 y* ga1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
+ E# N% F; c- u* v4 C/ a# j' z8 D+ N
添加限制
3 M* ^$ c* z; Q3 G# p) C5 FXn+1>=0
Xn+2>=0

, I3 F. p0 m( N/ w5 q1 H; l# A
3 L( v7 u% _6 l' ^7 y7 `, V" A* {4.因此所有的线性规划都可以化成标准形式：



线性规划求解

% X4 C- D6 c/ ~" w4 d理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

; ]; Z1 Y# _6 y  q$ _. X1 q4 a& F# QLingo求解
! b7 \. ?# V% W/ @
! `' ]$ a; X4 W- g代码简单
" S5 e& z( E6 f0 l- y0 K结果易分析
不容易报错

: C, a! ^' L- {5 c5 ~大概就是这个样子
3 f% m# p( P1 {5 T; t( {' M, JMatlab求解

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


7 X/ z7 `/ D* R" Y8 o/ {* b9 V所有量需要化成矩阵形式，负责代码的同学自己去了解。


7 Y2 R+ x; i/ r7 [: v% a* t. @非线性规划
1 F8 o8 ]1 M4 R- x
* K% ]* g+ }! s5 D+ s8 w# {简单说就是目标函数和约束条件至少有一个是非线性的规划。
- B# D4 d" f& x7 b
Matlab形式
9 K) D; L5 U: w& ^; }4 ~4 w
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
7 t8 R  m% k" N  h! b! k总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
3 V1 h8 U# R4 [+ u' K
/ Y$ o& M5 p6 |  Y/ Z4 Y' v# ?/ e整数规划
% M7 Q) U3 T% |5 ^
决策变量为整数类型的规划。

" ]2 a; ^9 C* Q) N- ~整数规划的分类

) n1 D* b1 T/ f- v

0 r6 T, Q; z# U& N( r: t整数规划的求解方法

  {$ w1 a; B: _% F: o蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

8 ^3 a) @. F' o- S+ U( j# [某整数规划题目的求解过程
. E3 i7 @/ s2 o* t! T
7 j9 d' a4 K* ]7 M8 T
9 B5 J. F+ `) Y1 S# Z4 R
特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
8 M, m# m5 W' k. o, ]$ A" r( ~
; N0 ?" h: e1 O2 Q- t9 m1 \


; b! p! U" Y0 _  G6 q


5 q% x7 @" ?/ N% \7 {8 s( ]动态规划（了解即可）

, I* b, ~2 j7 |- l- D# N简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
, a+ I; s  ]! U$ l
动态规划模型的基本原理
1 U0 R1 [$ T' e# v4 ?3 ^* u
% H* S9 I* _! z2 o( z( g7 h! |7 M) r最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

( Y& @$ C) t" s5 K& A  L贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
' r) S8 V# V# Z; @  l1 r
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

动态规划的优缺点
3 R) x! q: Y: ~$ H  r. u
优点：
* X5 b! b( l6 _) G# N/ I1.可得到全局最优解
8 B& z3 A% X2 u; M2.可得到一族最优解
3.可以利用经验提高解题效率
; w; }; I7 y% z6 x- e* p6 s缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

7 `- r" J6 J6 B' ?7 }; V" y目标规划（重点）
- g3 s3 R( m; V6 B% Y. n
+ J' Q! B1 h3 X6 c9 V  b6 d: j目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
. y8 ?+ Q; A3 P& e( Z
目标规划模型的建立



, u- s. }4 E7 q$ f" ^1 |( N
% {- |. ^; U) ^% h2 D$ ~引入偏差变量的概念

4 y& O6 K* X% z8 x0 `, R. X* o

! E6 J+ O/ z! \
! s2 ~: l' V/ F* k3 Z) R% S5 m$ Y+ \( B

( G/ S  B- e0 ?' ]$ G引入优先因子
3 t8 z3 b; M% J! C
. m) W. F6 \  h, e0 b

目标规划的一般模型

+ @( @& D1 O3 z- H3 A# R
# t* q' Q; [3 ?, E9 W$ x( x, k- C! M
: a( q: x( D4 Q9 q, N+ U0 ]% F目标规划的求解方法

% y5 D: D& c- e# E8 f理论基础：序贯式算法
6 K* S& j0 X, n4 v4 X按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用

1 e# y4 t  O$ q2 X$ t8 A8 \4 h& Z2015国赛 太阳影长的问题
' E" F9 u5 h, M9 H$ @& I4 j原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
( A( A- j% ^8 J( c8 C
. O4 o7 O+ T, }3 }+ U* }- M
" [0 }/ ^1 v1 A4 a1 r

德古拉

Nice shot, thx for sharing
) ~+ R+ e; `) n  b% s0 H9 s) O5 _