数学建模中的规划问题

杨利霞

数学建模中的规划问题
1 a1 v# a% N, l8 q8 B

" Z( h/ q& K/ w0 t*规划算法综合概述*
& h+ d4 v8 s3 E, D7 ?规划的基本概念
规划的分类方法（了解）
! }0 n/ _9 \+ m( a5 o' Z求解规划的基本方法
*线性规划*
线性规划模型的建立
5 S3 `+ F+ N4 m) S. F* Q线性规划求解
  C( v0 Y' d9 `- ~' z/ R3 H5 S# X, O, V*非线性规划*
, S8 C8 i( W  C# @# j4 F*整数规划*
- j5 t) R" Q" ^+ H6 h* a9 {整数规划的分类
" t/ w+ \/ C. d' n' _: K整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
3 _( e+ w8 [$ p9 k* V: `( i, G动态规划模型的基本原理
动态规划的优缺点
==目标规划（重点）==
: S7 t0 l8 u+ m$ o* g目标规划模型的建立
! ^/ X, S  e+ W6 z6 Q8 ^; L( t3 M) S引入偏差变量的概念
引入优先因子
3 ^; b( a$ F$ y6 Y; V2 K目标规划的一般模型
目标规划的求解方法
规划算法的应用
3 _) ?/ ?# f* x4 X& Y$ k装了半天数学公式编辑器，没装好，见谅。
# x2 m1 O4 @# T) u
规划算法综合概述

& M& a& e( b" h6 W5 v, F; s对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

/ {' E) {, h; e8 h. Q规划的基本概念
- x# k" ^) [$ l! }1 \/ v
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

, s5 Y+ V1 `( ^决策变量x，目标函数z，约束条件g(x)
: O7 w& c! Q+ V/ _+ r# A7 p
; H& ~3 k0 i5 a% M" F规划的分类方法（了解）
% _: m) c  Z5 R0 \2 U7 a


  r- w* ?' }5 E2 f+ S' R) H

5 `) V; R5 d# C* y6 ]9 y* _求解规划的基本方法

7 G$ k# I. V# \" N方法：在具体规划模型中会说明
软件：Lingo Matlab
8 N/ Z4 N+ A+ _3 P, e+ k0 H8 X
线性规划

线性规划即目标函数以及约束条件都是线性的规划。
! N: w6 B* n9 K/ [& \2 a4 C# }
; O# `% h( S* ^9 D线性规划模型的建立

, p7 ?5 [% V. e/ }$ _5 Z' _5 X线性规划的标准化

0 |. G4 z+ d* L: _0 W目标函数标准化
约束条件标准化
4 Y6 h7 u8 g; i0 O6 t/ `! M决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
* \) p: c( O, v0 A
例如

( I$ Q0 F0 ?8 p; P引入松弛变量 Xn+1,Xn+2

& H+ u+ ^; C4 ?" O  S3 g) ~) Va1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
. X1 u  ?$ `) P! P/ f$ X3 }; h9 x
添加限制
Xn+1>=0
* Z; J4 D1 R* ?3 TXn+2>=0

8 x2 C' E- t9 {! y
4.因此所有的线性规划都可以化成标准形式：

, _2 a8 D2 F' b7 I/ ^! W0 D( l

线性规划求解
# Y- f7 G# O; u5 a* g& i1 W  u
0 @4 h; c2 A6 Z: V理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
/ V& f' L9 }" B+ Z, o! Z
代码简单
8 }  ]& k, y' Z3 h6 G7 N结果易分析
8 E9 t9 _! Z2 b9 e: k, M* Q5 k不容易报错
0 |; s3 p; E- O+ b; Y! H& Y# \
8 X2 |0 h! x. h0 ^* a大概就是这个样子
3 K* P$ L; P# _& E$ E6 Z( o* _Matlab求解

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


所有量需要化成矩阵形式，负责代码的同学自己去了解。

; ?# E8 w5 i7 _* Y/ F5 L1 k
非线性规划
  Q8 V& n2 v* d3 D  f" Z2 L! ?  e
简单说就是目标函数和约束条件至少有一个是非线性的规划。
3 P0 k( E0 E) F9 Y9 Z
" D8 K7 g# O# x( y0 u- t+ n" u5 mMatlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
" l; i2 Q) y% Q4 |5 e4 W9 v总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划
8 U% H. X$ C! r0 P  @
决策变量为整数类型的规划。
. p5 `( p+ @& [" x9 A8 y" g- v: e, X0 ?
整数规划的分类
8 k& M$ A! m" T" X1 ]

4 a3 C) _4 z1 B; K3 S' a
整数规划的求解方法

蒙特卡洛算法
: X) o1 O+ N5 ?2 J, F蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
- F% j: ]# H* v  ~8 B! R
$ w( x& f. \) {4 E% Z4 Z8 p某整数规划题目的求解过程


( S) q/ ?. q% D& j$ o& E
特殊整数规划0-1规划
+ U/ r, n' J* I, D# |0 S$ @; T
- |3 \0 B+ U1 w+ N% c8 r即在整数规划的基础上增加一个限制条件 0<=x<=1

! `& M+ |) ]* c9 m+ i
' G. a; N" y2 t1 ^" W
9 R1 B: u1 B$ `% ?' _$ d5 l

& [% r5 Y: D" b1 t0 d& q$ }

4 X, c5 ~( H' b$ r3 Y0 `! q$ N6 [" ]动态规划（了解即可）

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

动态规划模型的基本原理

3 d8 R* S: |7 U. q最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

* u7 U+ @, \1 b. K* }, s, H# O贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

6 C7 l/ M1 ^8 `1 d逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

! u4 S& N" P5 M" s; ?动态规划的优缺点
7 \7 j9 d- H& O
  j- b' W& A, i2 c9 K7 l优点：
1.可得到全局最优解
7 ^9 K# A8 }+ h/ a9 c" j) T" }5 B4 ~2.可得到一族最优解
9 d/ x7 v% e0 m1 \3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

. ?2 j, b& U6 O) e. R目标规划（重点）
& }/ Q% X! k0 f! U
; [( F' ?: c1 q; z' P: F+ d目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

2 K' E/ Y4 w( i* L: W目标规划模型的建立
/ y5 |: }! P5 D* P
  J; U) p7 [6 O' Z' F- o. |5 H
9 z: E* W' S! O6 j2 g+ O

引入偏差变量的概念

4 ]5 A4 k, _5 z

: e! m7 ?% ~! x
) U  B2 J* f0 a! v
6 O, p9 x& b+ r' g+ k! `
4 _5 v* w' w9 w' ~3 [引入优先因子
- U: k( m3 G: _3 J. V# k
' q, |3 D5 H/ j7 S9 o- A# B! ~

" q, {# J7 x4 W, I& K目标规划的一般模型
7 ], F8 b. q, u: v
- \8 a! \0 S! E

4 l3 G2 C* A8 @目标规划的求解方法
* `' I% }  H' H+ V  M8 v
- N: j  l6 M: t; u" V6 l  d, ~理论基础：序贯式算法
' j% Y5 u$ O+ G7 v按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
# K/ N/ @" `0 Y" z
2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

德古拉

Nice shot, thx for sharing
( \. M- q8 F7 s