数学建模中的规划问题

杨利霞

数学建模中的规划问题
8 }* V9 C  Z$ z% \3 @7 P
/ I. t! p0 j( w+ a
*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
*线性规划*
线性规划模型的建立
& k5 s  y) m8 }线性规划求解
*非线性规划*
5 Z0 ]- C4 Z1 z( h/ D- D. T. k*整数规划*
整数规划的分类
整数规划的求解方法
6 b( Q6 @( U) G7 V8 h4 E特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
$ h: M$ e* A3 h$ p+ t动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
, l5 \- ?! l+ W* N3 y8 C* W3 `引入偏差变量的概念
引入优先因子
目标规划的一般模型
" e* k. n8 i/ t目标规划的求解方法
规划算法的应用
1 w# I$ x3 |5 c3 z& j装了半天数学公式编辑器，没装好，见谅。
: x0 w, n, v7 d/ i3 K
, u# y1 {) ~1 L) w1 a$ G; {* o3 A" j规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
4 j  A% k/ q% w
规划的基本概念

, V% p" P+ l& o- w5 L规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

决策变量x，目标函数z，约束条件g(x)
0 U# u2 ?6 D4 V  L0 x2 S8 @
3 a2 T; J' v8 M; W$ O规划的分类方法（了解）
5 X# z' ~  Q0 J% A+ Y% r  c

# S  k% x; ?$ f
3 d/ D% D$ K/ N2 R9 T; {

求解规划的基本方法
* v' S* H( k& Q+ @
方法：在具体规划模型中会说明
. X/ o, J$ j6 X* L7 n软件：Lingo Matlab
) W6 @( `- u8 _/ N! @9 w5 g
/ v. o7 I. P$ j线性规划
# S& E% X6 h( _6 [) O: z0 o7 M
线性规划即目标函数以及约束条件都是线性的规划。
" k6 D) S# Y# }% ~5 K- q
线性规划模型的建立

线性规划的标准化
! D& R) k) a2 X% C  a6 j1 b% o3 k
# N& I! A$ f1 t& y目标函数标准化
约束条件标准化
决策变量的标准化
1 O$ I# ^9 E! @1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
2 T) I& i+ c& c" C9 Y
+ Q* W3 g3 Z# q& ]1 a5 Q. `2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

8 K) ^( {9 H0 G, Q# G2 s例如

引入松弛变量 Xn+1,Xn+2
: {- c& M0 P) X* n
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
: H8 M; @# Q5 ^5 {& Ga1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
+ V) T9 W1 E3 f+ f1 G6 s/ \2 \Xn+1>=0
; O( X( M& s# n2 pXn+2>=0
: ]9 a+ X: \6 Q5 X! A5 |

- q* Q  i4 f9 o$ I7 X" @7 W& D( l4.因此所有的线性规划都可以化成标准形式：
5 Q0 K, V: \6 ~, t% P
+ s. Y' D) Y! a2 ^

线性规划求解

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

( z7 J6 c* L3 X: B: bLingo求解
- E  D9 P% p: K6 A4 L2 [( W
代码简单
: f: I/ e1 k* d( d$ k6 W2 L结果易分析
) U7 L% o$ {( h% [6 [% z2 m不容易报错
2 Y% t" H! \# _$ W  V
大概就是这个样子
Matlab求解

+ a# \. ^2 U/ @- s; u) |0 R其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
% Y) m: S' d: D# z/ s# V! s7 n

$ Y! I/ C0 ]+ \8 g6 z1 b% e* P! b所有量需要化成矩阵形式，负责代码的同学自己去了解。


% F8 L% ~8 k3 \& b非线性规划
& O" M2 b6 ^8 |0 d5 F" e
" y# i( p3 M$ e简单说就是目标函数和约束条件至少有一个是非线性的规划。

! S+ y/ K5 z4 C1 b: sMatlab形式
% F6 u9 F7 {6 r% W' w! n, N  o
; W, d( d7 z. i# ]/ X* t从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

) w# }$ g8 T% x3 v/ U; F整数规划
4 K  b1 X: \# y  r6 ]: i; u. y
6 b5 A8 C% L. B6 z$ m决策变量为整数类型的规划。

整数规划的分类
; K( O! I# J5 a& A/ p" f- W8 g
! [  [& L' o% [; c: B8 h5 a( g

. R. j# Y7 d% j5 t4 @整数规划的求解方法

蒙特卡洛算法
- P1 q5 i  p7 P# c" i蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
( J8 x& J5 f/ H
7 |5 l9 l, v( S/ ]5 z0 l! W某整数规划题目的求解过程
" |' R. n6 z$ W2 ^' m+ I" \
, U# X, [" d1 U8 }% T  A
3 N) A4 ]: v3 X- W1 m, O+ I0 X* j
特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
* a+ ]$ ^5 J5 T% i# s  g






" S4 |: i4 n: N' z动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
% }0 H% d; V$ \
9 j9 z! J) Q7 w5 j动态规划模型的基本原理
; V( h! C# Q8 X$ H
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
; L* y  ^; C: Z9 @+ ?( X6 R3 N
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
% W3 U' s+ z3 `& @2 m
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

动态规划的优缺点
5 Q* k  E) V, B8 [6 B$ \# U/ F
" c" h. F9 y2 ]) v优点：
  S9 M8 O4 C0 \1.可得到全局最优解
. r+ {( W: ~+ v+ a: p! L2.可得到一族最优解
5 J2 O" [" X; {$ t3.可以利用经验提高解题效率
- Z( o# L$ H1 B* u, M& Z缺点：
7 c. a& f. a* D* o2 c6 [, U! p1.没有统一的模型
# X; {8 J% [! Y( j2.用数值方法求解存在维数灾
0 R, T/ q+ ?8 D6 o& P8 D9 N
; \2 K! i" p! k9 v- I2 Y目标规划（重点）

' Q6 o7 N5 I3 C目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
8 _  b! @$ j3 ?' ~
4 }2 [$ D$ p7 g2 P4 W- Q目标规划模型的建立
7 g) m. t0 |# \% A



引入偏差变量的概念
* x/ u: J  p4 ]# X6 ^" R6 o5 j, X9 h
0 k, S$ Y: f1 o0 W( N



6 {- d% b5 U# h' T! I$ c+ H: k
引入优先因子



目标规划的一般模型
: H- W2 ?8 {( f


5 b5 L* _( N: r& X! q目标规划的求解方法

8 Q2 ~1 p6 J1 D% X. q理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
) a0 `9 x4 w7 h/ S. U
规划算法的应用

5 p4 G! a& o5 c, L5 m2015国赛 太阳影长的问题
. j* p' M% X3 O6 W0 F: q- p原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
+ j; ?& T6 f  J) q! K* z

+ s& k$ s( P* D

德古拉

Nice shot, thx for sharing
9 e' `; E* s+ G' d