数学建模中的规划问题

杨利霞

数学建模中的规划问题

) q4 o# w+ S/ F& o3 r4 J6 X
*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
8 K* n, p- r- Q3 P* l. V求解规划的基本方法
*线性规划*
3 n2 |9 |5 k: d) ^$ I线性规划模型的建立
2 T/ V4 d* o; B( q6 c" N线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
) }: J# u. j9 m整数规划的求解方法
特殊整数规划0-1规划
' c3 {( _9 F3 ~, q( T4 R动态规划（了解即可）
8 C4 k( V4 v1 s动态规划模型的基本原理
" Q5 r) W0 M8 ^7 a* n* v6 U动态规划的优缺点
==目标规划（重点）==
4 n$ V) _2 O3 u  t目标规划模型的建立
1 u6 t, b* U/ B1 i9 `% i( M引入偏差变量的概念
引入优先因子
目标规划的一般模型
) \: O" w/ m+ K; X9 G7 E目标规划的求解方法
规划算法的应用
: z4 `7 i; j3 N8 m' X装了半天数学公式编辑器，没装好，见谅。
% T' K5 l8 l  j' x- @- A
规划算法综合概述

9 p% u1 W0 q% E: p# o对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
& W' j5 ^7 b- N* Q
规划的基本概念

6 K/ a5 k9 R, k! b- v& B+ r" v规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

. V6 d* C  Y7 [决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
& H; Y& h( V! `9 y" X: |



7 R. B3 j9 K* K' a, W
. ~: u0 U: e& F' M, K求解规划的基本方法

方法：在具体规划模型中会说明
! h9 Q. y* W# l  j7 k! t1 g0 I软件：Lingo Matlab
* W* W7 q# A9 {+ C9 {3 [; h
3 X# Q- y1 r3 h; H- c线性规划

线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立

线性规划的标准化

目标函数标准化
约束条件标准化
% V0 x# |( m2 c9 Z( f决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
! P; Z$ u# ~7 x( U
例如

, C/ j4 @9 M. D$ {引入松弛变量 Xn+1,Xn+2
) {, e; I: p  E  D; V2 P& A! F
5 _, w3 H  R& \' l2 ~! Na1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
6 ~; H: y. D& }! ~, a# z  p3 J
添加限制
Xn+1>=0
Xn+2>=0
- l- C" A- C2 h- D

4.因此所有的线性规划都可以化成标准形式：

+ }/ x& f3 D6 x0 y/ X
5 v9 v7 k1 n: U+ ]: F* b
线性规划求解

理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
9 l! r$ y8 T+ R. J( d9 k/ A
, R# H1 ^' D+ y9 s1 O0 i2 H# {  P代码简单
结果易分析
不容易报错
) y* m. [( V& h  b# ^. O
大概就是这个样子
' O3 O. K" R4 [5 k$ y% AMatlab求解
9 O: a, L1 J8 s8 Q& _- M
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

/ a. _" v) W3 ?% ]3 E8 ~9 A1 s
( E$ r, z8 w5 D- w! Z所有量需要化成矩阵形式，负责代码的同学自己去了解。
# n; n0 f2 E, t% H0 Y# P  g9 f+ }
5 K% Y/ t% ]8 {
: @/ @: u# Q% T$ a% O非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。
! g% y- Z8 T+ n. a; H/ G
Matlab形式

3 ^6 `9 r. K, F" {* V% Y3 Y从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
3 V( g0 S3 [; ?" K3 i  c, R
整数规划

决策变量为整数类型的规划。

整数规划的分类

  x  W7 e0 M$ A& _& u
( h8 S0 Q3 w, H0 l
' n6 v3 n; V7 D整数规划的求解方法
8 `: O0 |; D1 ]" a+ ~7 `/ s
1 S) S/ z; E7 j( i9 j5 A6 }* t- ^蒙特卡洛算法
+ j/ |/ ]2 u5 ^4 ]4 E1 I蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
; X4 A" {, w; E& F  g! @
某整数规划题目的求解过程
& H  w7 o6 C/ f) j- m

/ w8 d: C0 Q: U3 g
5 D" Y1 u; }( C" x特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
+ x  R" @1 B" \' ~. A- T4 N- c) J
; w6 d/ j5 k+ Q

/ _% e2 ?. t6 {, O8 D9 f

1 Q1 k! G. c* S$ I/ t3 P
! ?# _4 S& q  c2 W4 A, k) w
动态规划（了解即可）
7 T9 ~" |  R, `, i% n
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

动态规划模型的基本原理
5 L. v+ y! H; w% b8 y
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
* t/ o. `9 p% N& ^% M) U
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

! W6 @' P5 Y" f逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

  k: ]" A  p6 S动态规划的优缺点

6 Q; Z! S' g# F, e优点：
1.可得到全局最优解
2.可得到一族最优解
6 `- Y) \8 E# f- o- D( S" p3.可以利用经验提高解题效率
$ F. Z- L& t1 D+ I& o缺点：
1.没有统一的模型
. R( B  T& Y1 |' ^- I2.用数值方法求解存在维数灾
5 q3 j" y; p+ X) _0 Z
目标规划（重点）

$ R3 x& P8 N) g% E目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
7 _# |2 K5 J' \
目标规划模型的建立
- o4 X; R9 ~% T; O& I0 L; ~
! R/ r) n$ @1 r7 A
6 ~4 _* P/ i0 N$ I7 l2 \
3 z5 b6 S( C+ p2 Z
引入偏差变量的概念
7 t6 j: B) b" {( z, n% B- l

+ x# L* q& X/ u
: B# `1 R& C" o1 W/ B

: ^% w* F) ~7 B
引入优先因子


' Q; a$ c: v0 e: z
+ {% P$ ]6 S8 q8 d) Z1 a' r目标规划的一般模型
: t+ L, t' i( D+ b7 M: E! g

* B" J) e3 k( X! \  T* F8 P
* t, `( h/ O1 `* m# w6 o( I2 ~目标规划的求解方法
- m$ I6 L7 |* ]/ p
. h! X+ `) H9 _9 V' e" ~理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

5 l* R5 C0 `7 K1 ^, G9 Y. o3 u规划算法的应用
3 r: b5 M* x0 y: C" I1 [. @' q4 i: E
2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
9 h' e3 P3 I8 k

, C. K4 y, g- H3 M8 u5 b1 g

德古拉

Nice shot, thx for sharing