数学建模中的规划问题

杨利霞

数学建模中的规划问题


6 ]/ ^, K4 X( F/ g( J* p3 {5 M: v*规划算法综合概述*
! D7 X" I" x, Y  d" @( l" B% b9 T5 F规划的基本概念
规划的分类方法（了解）
7 a) s" ]: @' I$ x( U: l求解规划的基本方法
*线性规划*
, ?& ~+ {' g& x4 d4 N0 j1 g线性规划模型的建立
2 g$ g9 Z' i5 ]) e线性规划求解
*非线性规划*
  _" U) q/ y, E8 s*整数规划*
整数规划的分类
整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
9 z; U1 q/ X- c# x, r7 b动态规划的优缺点
! o0 A8 k3 n4 \! X4 K! T' G==目标规划（重点）==
目标规划模型的建立
, w5 @! f/ j/ O5 E引入偏差变量的概念
$ Y& A# L% c4 d/ a) E  i8 f引入优先因子
7 q( j/ H. [: t  k/ j1 Y目标规划的一般模型
目标规划的求解方法
1 [- ]  z+ n/ M规划算法的应用
4 Q! _; ~' v1 X: C5 n0 ?" ]装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
' V4 c. N2 M7 D$ u; e: ?
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

. i) c5 d% n& G3 t规划的基本概念

- i4 e+ F% e8 I( v规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
3 u, z1 `6 d+ P: Z6 \/ O2 q1 T, p
& c1 Y9 V. F* M  R# w  ~. I决策变量x，目标函数z，约束条件g(x)
: |  q$ a  {* F
规划的分类方法（了解）
- E5 k2 r  q+ D, N# O1 A% O
: S7 e9 R6 i1 S  |* e- p) o! N" [$ t
7 c' Q" }6 @- V0 k# ~0 t2 t& O
+ p9 e& o- P" v+ f0 ]% l

: v6 I8 e' `% w+ \* }. K求解规划的基本方法
9 h% r9 _% f: ~' W6 S
/ r5 D5 q" l( ^: M- I方法：在具体规划模型中会说明
软件：Lingo Matlab
  J1 S$ y+ P. x0 E+ X3 c& Y
线性规划

7 c3 e. ^. ]. F% V; g线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立
* d. b' ^- e" n" M
" S; x9 b5 [. m, I; o线性规划的标准化

目标函数标准化
+ C1 W! y" S8 w) f1 y$ S约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
: j8 ~- f! f' W' w. {
5 h. f- \/ c: }) {5 i  v) f1 Z2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
; o- W# Z; W3 }9 N+ b; ]
  t' Y/ v6 u$ B4 b0 O例如

, \/ ~4 b" n# m5 i+ U. J  Z引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
2 L" z$ z# Y- u+ o9 f7 oa1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
Xn+1>=0
- x- v1 e) ^! g, z9 H* W+ sXn+2>=0
8 C3 V4 l! H4 y5 }5 e/ q/ F2 d
% e* r- G! D$ h5 i( z- l
4.因此所有的线性规划都可以化成标准形式：

6 \; ~6 B+ K" t* `( s+ e

线性规划求解

# _/ D2 h7 P) {+ v( U) q+ p2 [理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解

代码简单
# g& A& }8 C& p; v; s结果易分析
不容易报错

大概就是这个样子
Matlab求解

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

! \1 _6 ^( a- H& s
所有量需要化成矩阵形式，负责代码的同学自己去了解。

$ R. h9 B: E* X7 O, p" _6 h
非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。

+ [3 ~$ j/ W, V: ~. z/ ^Matlab形式
# o( G3 Y( C% s& V0 a) x
2 ~3 z4 ?6 `$ v  R0 t' w从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
& }6 l# A5 L7 b4 a
3 F. b7 B% L" L整数规划
; q; p. Z6 E' H6 t0 I
- X/ l' q% N1 ~( n9 ?1 A! l决策变量为整数类型的规划。
2 E1 p  o  o7 s2 r% f+ t( e
6 S# \  r3 q# W9 Y7 L7 j! u整数规划的分类
4 A0 d, H1 k: B! ?9 }


整数规划的求解方法

蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
0 J. u; A# a& b) G$ L1 q) X, {- e
' u$ r/ s$ g$ l5 ^. T某整数规划题目的求解过程


) h6 V2 e' r; k0 p( E
特殊整数规划0-1规划
3 O1 S  s- A' `' h4 m+ d
# h: N, O7 `( y- }8 \4 C即在整数规划的基础上增加一个限制条件 0<=x<=1

  v9 Z4 B6 g. r* M4 v

9 l1 Z/ C. G6 d4 {9 W8 n8 s( b
( D* J8 N4 s0 E7 K8 W7 k


5 `! u7 U1 z) `, c' P. {7 K% M动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

# F8 {& j3 ^# z动态规划模型的基本原理
; b, K9 V4 Y, M! S! k0 p
. c2 i# B. K, A; C% l- P最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
1 L+ e1 m6 [4 j' O
- f- ~& o! h, F' Y贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
; D) E  A! \& R/ T% X& U
5 U* @* y3 Y, U+ R! E逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

% y& Y3 C  C( Y1 j5 Q6 M# M: |8 _动态规划的优缺点
5 R. C4 e* |3 H1 n
优点：
1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
, p+ u! o$ O# n+ Q, }1.没有统一的模型
. A2 T# u! A( ]- N3 X2 |" t2.用数值方法求解存在维数灾
& J" ?$ }4 d% @; V( F
目标规划（重点）

5 X! L" v( Z! j. ]9 r目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立

! j* W# x) R6 F% r3 b6 N7 }
* i3 H: x: C9 o) e
5 d4 f9 }3 D8 T  C
引入偏差变量的概念
" M8 x+ l, o7 E, k$ v

7 }- r4 g% J, f, W! y1 r* E
0 V  Y. H2 Y% ^% J/ G
& \  B7 l8 |! a) v
0 N* T! |# {% c+ @- i
) s; c6 m+ l0 u: _! o% M引入优先因子


# {0 n9 P6 D8 L* K( l
目标规划的一般模型



目标规划的求解方法

5 e4 A0 E4 s' k) t; Q; A4 b" i理论基础：序贯式算法
" o0 @. M' l# u6 w按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
+ S" f% ?+ w% u  o1 b; H
9 V% Y4 f# e. N  N' |& y2015国赛 太阳影长的问题
$ `! I6 t4 F3 I3 o4 y: W原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

2 I/ G% A/ K$ w% k% `

德古拉

Nice shot, thx for sharing
( A) Q0 ^- G3 X) ~; s1 P" M