数学建模中的规划问题

杨利霞

数学建模中的规划问题
5 m$ g' q6 h& {1 ~" Z! E/ }: V% E
4 J! b" z, ]2 F: E8 D7 r8 _
*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
*线性规划*
线性规划模型的建立
, u7 I$ ^/ f4 x$ e; n* Z" M8 C线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
整数规划的求解方法
: u4 v, k( {$ B( B' R( F特殊整数规划0-1规划
& D' |+ r8 a( i1 M0 ?8 |; Q7 l% i动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
7 W; }$ `& u' b==目标规划（重点）==
3 B" y; D+ q2 ~6 g5 X目标规划模型的建立
引入偏差变量的概念
引入优先因子
目标规划的一般模型
目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

! t) `  G1 I. k; v- k/ V规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
+ ~% L  A9 ]4 H3 F3 _
: u- f1 s; v/ `1 F/ C规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
* B  ~' E7 |4 ~0 E- m( Y
决策变量x，目标函数z，约束条件g(x)

* K* {+ Q" C4 |规划的分类方法（了解）

( G# F/ P, k2 d( E3 j* k3 t7 G" I



. G& G2 {1 T! p1 p8 F+ j/ O1 K求解规划的基本方法
4 g7 p5 _/ ]4 E2 E% }' b1 q
方法：在具体规划模型中会说明
! A) A" _+ ]6 ~2 Y5 s软件：Lingo Matlab
! s. L/ v: K! ^$ ~3 A
% G* ~* ^& S2 ~( W. P3 `线性规划
6 S* y1 h5 D: B+ v* `$ s( H
线性规划即目标函数以及约束条件都是线性的规划。
1 S8 ~1 Z4 l5 V2 i
% F+ \4 g  W9 Y线性规划模型的建立
# G, X" ^' y1 k
线性规划的标准化
: j+ r) j, p, v. C
目标函数标准化
- A: ^0 N& K7 p+ |约束条件标准化
/ s: F- h7 F* `8 B4 `5 e7 g9 L5 s/ k决策变量的标准化
& C' m: J( C8 f0 }. R1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
9 m& S1 _$ E- ?) i8 b
例如

引入松弛变量 Xn+1,Xn+2
, U1 g* f  b: _) L- s! T( u+ V7 C8 e: G
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
2 c, B* w% ~. ~; X) ~  ^' c5 O7 W
添加限制
Xn+1>=0
Xn+2>=0


4.因此所有的线性规划都可以化成标准形式：

0 ]# H( F- X3 M
7 i# \) u. y5 R) _9 H1 A; m
+ o% u' u8 d4 R7 D6 X# }6 j; N( |: o线性规划求解
# n7 q  D4 ]9 i: F" ^
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
( V8 \1 j7 R! F6 v" j
Lingo求解

代码简单
' ?3 A! W& g9 e- ~0 u7 D. r结果易分析
不容易报错

大概就是这个样子
1 D3 z% ]5 q: j: xMatlab求解
- t+ y" c8 C  ^" a7 i4 O
( i  B9 I! J) H, m" r6 d其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。


4 O" ?/ v5 V5 u5 s4 j4 g所有量需要化成矩阵形式，负责代码的同学自己去了解。


! c9 `& _1 |) M& w# f非线性规划

+ [7 m2 f" \  c简单说就是目标函数和约束条件至少有一个是非线性的规划。
% Z7 R) F' e$ C! ~( k3 `, p: I
Matlab形式
, v9 B/ D# u0 F" ~/ A
* @$ @3 Q: m! P8 }5 ]从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划
1 }+ S0 c! @4 ?* e# m3 Z" [
决策变量为整数类型的规划。

整数规划的分类



整数规划的求解方法
" M; ]: o# R2 B9 i* k
蒙特卡洛算法
' Y* ~% ]: u8 m2 f4 ?- W8 p; F蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
; \0 Y& T  _2 l& T: I9 P
, ]0 s) y* [3 m某整数规划题目的求解过程

9 f' M4 M. d" S7 P& E
: J3 Y' _6 k& P1 k, }
& E- M9 ?1 Q& P特殊整数规划0-1规划
3 H+ b$ R7 b, V% R
. c, w7 @* H/ ], n9 e# w即在整数规划的基础上增加一个限制条件 0<=x<=1

, W5 l. K+ V$ q
! d- i2 }0 B' |" H, K" X! |7 y

: w+ A$ R% |. M* Y1 @
$ x! E! B9 [3 l4 l# \3 p! f0 z( i
: x# i! N5 p% O, A- ^9 w5 @
" l+ S' ~. C( e3 R4 ^动态规划（了解即可）
* N# ?% K  H+ {, V$ |: R7 Q
9 b2 @2 m4 e  i( s简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

' s4 E. r+ Z! C3 w: `动态规划模型的基本原理
, z9 n3 V2 S) n% q. n
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

. A; E. u( H& y9 o& p) ~. @( `7 {8 `8 X3 J7 s贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

7 ]: `- T2 v, J3 A4 a/ ?7 [逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

动态规划的优缺点
  P. p: b6 p( }* o4 B9 L% U
优点：
2 J0 R6 F- `/ r. Y1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
3 d% F" m# O6 K' q3 V- y! d缺点：
1.没有统一的模型
8 D- {2 F" I" Z5 g/ d5 |9 G; B  K2.用数值方法求解存在维数灾
, y  J# R0 P  I! A$ O/ O; I
目标规划（重点）
9 ]5 c, t4 A3 }4 e$ t
/ i' Z2 r# ^3 u; r8 C/ ?目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
/ i: x, V; t$ x, c# y
: \# L. O$ B4 z: r( u目标规划模型的建立


( K4 l" w* }% Z  ?

引入偏差变量的概念


/ [' J1 I' e: N8 ~
# M* s4 i( M5 \$ A2 j8 n

7 v+ j. D! ]- c2 ~  O$ P
引入优先因子
( g9 O! D+ \5 j6 T1 ~8 G9 L5 F
* q8 g; G% J, ^, z$ l7 h2 e

目标规划的一般模型
1 p8 W" O" Z( T7 [


目标规划的求解方法

, K( n) I, e' S! j! V3 W理论基础：序贯式算法
/ ^3 N+ Q& U% ~2 \按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

4 u; h; _& O' H$ G2 A规划算法的应用

2015国赛 太阳影长的问题
7 e9 F# Q- n' m9 D1 N1 k4 l原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
3 S7 E1 Z" d4 E( @
6 P8 X" Q8 t; j2 J

德古拉

Nice shot, thx for sharing