数学建模中的规划问题

杨利霞

数学建模中的规划问题

  _* X3 C: |' ^0 R% M* ^1 E
*规划算法综合概述*
# C7 L$ o! ]; }0 t+ J规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
2 f8 `" e/ H' Z' Y# S' n*线性规划*
* u  N7 O7 Y4 z, E2 b4 c) O线性规划模型的建立
线性规划求解
- r" o6 z/ m7 |4 z*非线性规划*
! h. ^3 @. b: H5 t6 O6 o$ l% U/ M*整数规划*
0 t7 e7 x2 a! ~5 _5 ~整数规划的分类
( z8 B; ~( U4 B+ T/ u; \整数规划的求解方法
特殊整数规划0-1规划
  \% p* F* v' ]* ^, p动态规划（了解即可）
动态规划模型的基本原理
: E$ ?$ B+ G1 N动态规划的优缺点
! Z( K. {& N* D2 J; N" t==目标规划（重点）==
3 B4 I7 y4 @; c3 c/ Y3 q* o# e目标规划模型的建立
引入偏差变量的概念
) {9 p4 b! O! f: `引入优先因子
$ o/ o( V% V3 _/ Q目标规划的一般模型
' J! N7 J% y9 I5 [5 _8 a8 X目标规划的求解方法
规划算法的应用
8 u/ H- @0 v( U  |" z5 Q装了半天数学公式编辑器，没装好，见谅。
) j: T5 d, I) k, @
规划算法综合概述
6 C2 [+ Z" X3 F& i
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

% I+ L0 I  Z) M' o7 P' t规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
$ |9 e& e+ L9 e! Z4 v
% E9 S7 s* I: e7 w4 A+ @决策变量x，目标函数z，约束条件g(x)
' a+ V; h$ v, `/ h, n
' i% @; O7 x. U: u- \( A( k规划的分类方法（了解）
" M( L2 b% V+ B- h' |; D. d9 Y



$ ?& I3 f% Q( F" ?! @
求解规划的基本方法
$ e+ _  G' Y$ _+ f, M' K; q
, ]7 ]' [* A5 p$ s方法：在具体规划模型中会说明
+ }/ ?% T% z3 w9 [5 R$ A1 s( H软件：Lingo Matlab
# `2 z2 W) C8 U* t! ^" f, \
% t) s; G+ a& P3 a7 C& R+ |) o线性规划
9 w: Y5 V) C( f1 j
线性规划即目标函数以及约束条件都是线性的规划。
! G, Z3 P6 A- n6 }
线性规划模型的建立
7 C$ c# k& g9 c( p, e$ @' l; Y9 x
线性规划的标准化
* n! d; {6 W; w4 F; e! s0 F. h
! B6 S) r0 |3 B& D目标函数标准化
% f8 Q- C1 @) o% L  l. r) d# W约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
2 b( N4 F( p; z* Q3 _
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
* I6 F! r, _6 A' B. E' f
例如
7 R- F! d6 D9 |2 q. R
引入松弛变量 Xn+1,Xn+2

- _8 ^8 f5 z6 ]6 F9 J' m, qa1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
# H8 T8 x& q1 A% P4 ]a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
1 L. F7 h- L1 i. M  U4 v2 w
. ~, o, Y' k) X. x  I0 V添加限制
: c# {' Z( t6 T. d/ g0 R# S+ xXn+1>=0
7 D1 \6 n' W# w, i9 I  cXn+2>=0


: ~$ G+ G7 c/ Q4.因此所有的线性规划都可以化成标准形式：

, ^* t# ?9 t; _& }. f, i' [- X
9 i, S7 Q- X9 k- S4 x: T
3 o' a' u- O) @& z0 ?# f) V线性规划求解
- k6 ^5 j3 Z0 Q
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
; ~  Z! {. m7 U; @/ _& T3 c
7 c% \- L6 T) ?) V$ P3 t6 ULingo求解

# \) D# K  A! e" G- u9 T! I代码简单
结果易分析
不容易报错
( M( d# z- p# A  F1 |
2 w. D; L- Z; d# N! a$ j, I: h1 e  X& C7 H大概就是这个样子
. g2 ~7 q" L& K4 n0 F6 j6 z- \Matlab求解

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


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

  }$ p! \2 f/ r2 b- U
) L- j5 p* R  G非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。
2 m, ?. f1 [+ H
& v; w/ ?1 }; ]: QMatlab形式

) N& ^4 g8 _# o: M: r  @0 K& f从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
+ }! Y- q( g0 j5 r- D总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
2 o! T* t! Z. f8 P" J$ e3 F
整数规划

, ]0 o/ L# F! b% c3 W1 n/ `决策变量为整数类型的规划。

整数规划的分类


1 A3 h9 h. ^+ e& Y; }0 S% c  u  N: a7 y
整数规划的求解方法
+ G; q) V4 R0 A1 a, Z: L
; m( x4 j$ ?# C8 I$ k0 `5 a9 l蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

; `& X7 o3 \$ A* U* Q某整数规划题目的求解过程
: e$ k" d; n3 [# F+ ?
3 [4 T# v* V% L1 \9 d
4 Z/ M  z- U/ B2 y$ M0 f" a/ A1 d
2 O, B4 h6 e# ?: X特殊整数规划0-1规划

1 l3 a5 A/ p, w# J即在整数规划的基础上增加一个限制条件 0<=x<=1

7 O$ W/ a. l3 G6 o) w- x


, L* k: g9 l- @$ W; q* ]& E


动态规划（了解即可）
) S( G0 \+ R- H4 q5 y* [# E
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
. S+ O5 O/ f+ F
动态规划模型的基本原理
1 q! G- |$ b, ]
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
  q& v/ A& G8 q$ O3 X
动态规划的优缺点
( @8 y$ E' r3 R5 m. h
优点：
1.可得到全局最优解
; n2 ~' D/ b# p1 k3 Q2.可得到一族最优解
: Q0 R, g" h! X+ R, I( L$ ^+ X- T3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾
2 ^, _* b1 J  k4 s- p# J% X9 r8 N
目标规划（重点）
. c; |+ O2 R+ M' j
8 U& a% ]8 J4 F6 ^5 G8 R$ w目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
  \( x: K4 d5 L# C# I
目标规划模型的建立
) p) |* m' M2 X# X6 f. k5 Y$ I! h
0 c; {' Y' h7 }& v  r( u/ r2 [


引入偏差变量的概念





3 k. m$ m9 `8 k- n3 Q9 u  G- I
1 z# p" V' U5 M5 |1 S引入优先因子

- O+ }% k9 e1 f- d/ W$ |

目标规划的一般模型


, Q' v; a& C2 v) ~
目标规划的求解方法

: n" [9 _' ^1 ]: M+ F4 ]) T& A6 n理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
/ z. k: v7 _  B
规划算法的应用
1 m9 H# g. z) m. L: |3 K
) B9 e$ _9 Q7 ^& q$ p6 a5 j2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
9 E; Z- f2 M7 W' J
- ?  d& V7 E4 X2 u) X

德古拉

Nice shot, thx for sharing