数学建模中的规划问题

杨利霞

数学建模中的规划问题
2 @" A7 W* g/ _- q7 {3 K9 I
& u+ W" ~8 c! \& p7 c
*规划算法综合概述*
3 [/ e) ]* f" ]9 a4 ]0 q规划的基本概念
; }" b* y2 S% d  Q. t3 x# ~规划的分类方法（了解）
求解规划的基本方法
*线性规划*
线性规划模型的建立
+ v. A, b" m8 H' o线性规划求解
*非线性规划*
' f! L; h/ A3 y  d- I*整数规划*
# o, ]1 E1 P6 W( g整数规划的分类
$ Z2 ^1 y/ n6 @8 I" s% y整数规划的求解方法
特殊整数规划0-1规划
: g. J, f: L. D3 ^3 h! x* I动态规划（了解即可）
7 u$ i, L9 M2 |! ^8 b) h6 V1 E3 f1 s% @动态规划模型的基本原理
3 q( A' p" O9 H( f) p) V% m动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
3 I# F# ~  ?* [( y9 P4 H- j9 ]# j引入偏差变量的概念
# V( Q* ~+ O9 m7 D$ X4 e& _* J引入优先因子
- ?5 D. Y& j: I# p1 n) Z目标规划的一般模型
, r- q5 c9 R" d4 ~0 W) Q" ~目标规划的求解方法
规划算法的应用
) n3 _) X" o7 d8 V: C: q2 ^+ n$ u0 b装了半天数学公式编辑器，没装好，见谅。

4 J3 D  h) M4 o3 N9 R5 ~. P/ y& K规划算法综合概述
8 c5 }( f$ M  U! c
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
; C/ d+ g* j$ k  ?7 \" m
规划的基本概念

4 W$ P  T6 ~' \4 q3 A- y6 j规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

  q' N9 L! p+ x  ]决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
8 [$ S) u* _* L2 c2 P$ y: L
, L5 k$ D( U# y$ @; S* n. h
& [8 Q: H* t) u5 N
: E# A6 R& Y0 q. g$ `

求解规划的基本方法
1 b0 R$ V8 C- c9 E! Z; G) D. O; P& z
  g( K" ?) V8 ]: X  p方法：在具体规划模型中会说明
软件：Lingo Matlab
+ d8 U0 ^1 U+ d: j) c
线性规划

. b/ f5 I2 K8 Y1 [  _: z+ H- \线性规划即目标函数以及约束条件都是线性的规划。
' r) N1 G- W, a6 r' k- T2 U
" o5 N% Z$ J# G! ]线性规划模型的建立

% g1 ?# a! _. L" q. X0 K线性规划的标准化
5 t0 N4 ?' q) j
- k( h. b. N/ X& o' q3 W目标函数标准化
7 g" y7 V: r  U, C, p. w; q约束条件标准化
决策变量的标准化
# @4 j+ w% f0 y# X. |. y# s' Z) D1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
/ r2 t0 b$ b6 J5 B2 T
+ N8 _  b5 I2 }' b2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
/ _6 r, _1 A2 v( i7 D
例如

引入松弛变量 Xn+1,Xn+2
8 e& P8 w* L' T/ t, m
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
Xn+1>=0
7 N! n9 i$ w" |7 [1 TXn+2>=0


7 H' g7 o, ]: c) y+ |5 j4 _2 H1 ]4.因此所有的线性规划都可以化成标准形式：
( @# ?5 N& J' F$ B1 M


7 }5 I2 _/ [" U+ u6 n) {* E* l" T  p线性规划求解

+ Y- U1 Y$ W' |7 i7 m" R6 i3 H理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解

/ T/ m3 H1 Z6 G: m代码简单
结果易分析
不容易报错

大概就是这个样子
Matlab求解

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

, ?2 c- V+ Q; ^+ Z0 _
所有量需要化成矩阵形式，负责代码的同学自己去了解。

2 ~" Q: D! ?) ~0 r: Q  P8 [
非线性规划
$ F6 O( O5 \: ^( `- P
简单说就是目标函数和约束条件至少有一个是非线性的规划。
- K7 {. p4 U5 o; b* U
Matlab形式
9 g3 T& G! T9 [0 D/ w
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
* n; |: C+ }9 t# }$ s% R9 ?总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

# j1 i9 n  Q% L" i整数规划

5 c4 H0 B0 U* K7 l8 _2 j/ @$ Q( a决策变量为整数类型的规划。

4 n) m. H0 z& |! W3 q4 x- N( d整数规划的分类
4 \. J6 x! n5 h3 X. b- N

) ]2 s7 C9 r8 I1 Q8 P$ ~5 {. u
整数规划的求解方法
- L) k, X5 h. K9 x, z, v
# L1 L- G9 {) D蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程
! P( {. V5 @& b2 r' |, ^' W. ~
! I" R" a. V' U1 ]2 j
6 t# [  [+ W* k5 q/ k$ h; l
特殊整数规划0-1规划
2 u- L3 ?! G. o5 Z: x0 b
即在整数规划的基础上增加一个限制条件 0<=x<=1



9 \+ q, k! m0 i7 R- @/ |
$ `2 Q  y* [4 p# R! _

+ I3 g  k6 S3 a: K
动态规划（了解即可）
' M5 D" j8 L9 ^+ S7 y6 F: ]  z% U
" ^4 J$ n9 W$ z' k6 t; I2 q4 S简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
) I# H0 ?" z, t9 z) y2 u# h
" W# A2 Z1 R# i5 W5 A& J- ~- N( u动态规划模型的基本原理
) ?" I0 o4 u1 c
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
6 e$ g% j+ b% B4 h
9 Z) ~# S5 l. J' _- y: c' \! p; i贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

% u1 _2 D  p: ?* P0 C4 n逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

7 e4 S2 @8 y) C. i( N动态规划的优缺点
8 z$ b; q# f, F- V: W: e( v# I
优点：
+ z: W; N& A2 }  [1.可得到全局最优解
2.可得到一族最优解
" @9 y, t0 C6 q/ Q2 _3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
7 d# W8 l$ _* p$ l2.用数值方法求解存在维数灾
! r1 m& ^9 C$ Z/ d
& u- D. G  U3 h5 Y' A0 y$ v" D- [& n目标规划（重点）
' G0 L/ G) P% p' m. I
# g: F4 r7 h9 S6 L目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
( e1 A, R; @; p* F6 W" q6 D5 [
目标规划模型的建立

! h& ^2 T2 N+ k3 J1 Z5 V( L/ E/ L
* s+ A" B# g3 X& M. x& M
) j2 |% M1 p1 Z% F8 l" E' k! Y* W* M
引入偏差变量的概念
  @& K/ d! D+ T' R/ k5 s" l5 v


) Z6 @0 f6 {. h$ j& |* V  L9 \' }
3 F5 B# T+ t/ b0 b: p) m9 c- n$ c
. K7 q+ o8 _# n" g8 E0 d: I2 X
引入优先因子

6 Q# Z: ?8 }# X7 j0 f* w1 _* Z: ~4 Z
, |, c; g: P9 M; N7 m7 o  t8 y
! K4 V1 ?" E$ ~  p# E  L目标规划的一般模型



目标规划的求解方法

6 K, V  I- ?% `9 G0 G理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
  \) R3 o1 |( s: {+ [& \7 f
; i4 L$ {1 ?. f1 Y" \( i, A7 y2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

$ S5 o$ Z0 s- N* K& D

德古拉

Nice shot, thx for sharing
4 U; b, Q$ ~1 ?