数学建模中的规划问题

杨利霞

数学建模中的规划问题


, A% o! u2 ~* J, G4 N*规划算法综合概述*
, H/ J! O9 y# O9 }+ D. T7 D规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
*线性规划*
( V) z4 |* n% Z  q' P线性规划模型的建立
线性规划求解
/ |( O# B4 e- t' H' a4 G2 Q7 H*非线性规划*
" X, v% u: U7 ?) Z6 M- h*整数规划*
整数规划的分类
整数规划的求解方法
2 Q8 M$ C& D7 j1 C: t4 z特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
8 n7 O+ n- B. o% d3 `==目标规划（重点）==
3 w+ b6 t4 c$ Y. t% ~目标规划模型的建立
  ~) D1 T; |, m2 i# u. G0 @2 r7 ~引入偏差变量的概念
# V2 i* c4 b* P2 P; J' r5 e引入优先因子
0 L( e4 v( O# w' j# L5 a8 P目标规划的一般模型
目标规划的求解方法
. D; k8 G" v1 k1 }, O1 ?规划算法的应用
装了半天数学公式编辑器，没装好，见谅。
- F% S& N5 C& u0 f# D4 D
规划算法综合概述
+ ?/ K, O' `* @( }( ~
) P" [$ r4 P7 O, x9 x" X对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
1 w8 `' r7 X, `% U+ v, ^6 D# H* [" j1 W
规划的基本概念

0 v' m1 `# D# F, n规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
! S% G* ?8 R4 ?4 F6 Q$ u# C
- h! i9 @, N" @$ p$ [( L决策变量x，目标函数z，约束条件g(x)
. ?* }" u4 T' L3 h
规划的分类方法（了解）





: F6 c5 @7 ]0 M4 K- J8 p求解规划的基本方法

0 E* {1 h3 |: u9 a9 l! V) ]方法：在具体规划模型中会说明
! y, G- b/ C* E  g* c' w" L/ P软件：Lingo Matlab

线性规划
% N# ?* N% H5 m, n& l
9 q8 h* B- t: D7 U0 Z5 v线性规划即目标函数以及约束条件都是线性的规划。

+ i- A1 R3 ?/ S& Q1 [线性规划模型的建立
* {$ r9 b: O1 M# b+ N
, G4 \. `7 F% G$ k) P) `线性规划的标准化

目标函数标准化
约束条件标准化
决策变量的标准化
) s' _" ^; v1 z" b4 y5 u1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

" X! R% |% r) {/ I" t$ L9 k2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
1 j8 q1 i: d, i5 _
例如

  C- {0 L0 b& \引入松弛变量 Xn+1,Xn+2

; ~3 P$ K# H& Q. r/ k4 z7 t* W- [a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
5 e6 s* d* K+ C% E, n
添加限制
- B, c6 R# k2 FXn+1>=0
1 ^/ I3 t: M) u1 ?1 Z% mXn+2>=0
* w# ~2 i4 |! N# N) y2 k

3 \0 M! U- r) f4.因此所有的线性规划都可以化成标准形式：
! p) A: a" Z5 j( c& ~* U0 d

6 ^: x4 e# e( X# Y/ a9 B
9 Z! k1 l- `9 Q3 Z$ I* R# ~! K线性规划求解

; Y0 \" R2 S' T+ n4 S理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
+ y0 Z- }1 x5 {* t
; H1 g9 j1 P+ t% D9 _. `+ t  RLingo求解
' N; C! d6 r" S. A. ]! M: ~1 ?  y
代码简单
结果易分析
不容易报错
- ^- [- g9 d- C3 u" G! o1 d7 e
大概就是这个样子
Matlab求解

* L% ]4 g  {( K; P! u其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
1 e' ]; ]3 U6 J6 s9 `
2 [' B5 ^5 Z. n& _
所有量需要化成矩阵形式，负责代码的同学自己去了解。

, _4 ]! n$ a% ^9 N. A8 f
- Z$ x; y) f- p1 o+ h: T非线性规划
' O2 N: e7 i, `" j' p/ n
+ N$ n9 {% D$ M. D% Y9 M简单说就是目标函数和约束条件至少有一个是非线性的规划。
3 n; m8 ~" m( }7 b- i) v
+ |9 `5 Y. x' n( o2 t; rMatlab形式

) `: n8 o# E0 G7 h5 S) O从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
: D/ Y5 K" k! C, x8 _3 e. X; |$ Q9 c总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

1 `. s; i4 s9 B# ~9 |2 e) K整数规划
$ Q! q7 t3 q; i3 c
决策变量为整数类型的规划。

$ u  C& ~9 ?2 l" l+ p整数规划的分类
8 r& H* C2 ?9 q9 u
( m* ~; V6 E& e* W, z9 g

整数规划的求解方法

蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程
$ J. x. y# V1 Z+ T6 O! r$ x! b" o& C


特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1


* x. f( ~" j, [1 E1 l' K5 `7 H9 K




动态规划（了解即可）
/ O2 p9 S5 \9 y# T* J
6 v6 |3 I/ v" u$ L( p1 r简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
7 @5 z4 J. G6 D2 ]& i( Q
# U$ g+ Q" g0 }, ]6 t( \" v动态规划模型的基本原理

7 Y% y, I, ^1 B- d+ r最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

: v# K  ^" C7 q' F. `贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
0 k: N5 h. x1 Q  A
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

5 i* A* b6 `  z- y7 r动态规划的优缺点

! o" a5 O3 ~; j& Y* [2 n/ ]优点：
% o2 i) J9 S" ]* K1.可得到全局最优解
2.可得到一族最优解
9 U5 L1 b: }0 J  N- L9 F3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

目标规划（重点）
& }' r4 A1 D  G% Z9 d) w( `
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立
  ~- T: O# v8 m* t& F
7 q3 I( |" t8 M8 ]
$ U$ C/ @! h  Z* \/ s8 ?
6 U8 J1 Z  }' o3 ?
3 d" Y0 E/ e% Q" a引入偏差变量的概念
* {7 Q( }( p' Y. W/ P% d

2 X8 k* T4 q/ s# k7 N


5 F0 V+ T0 n6 q: ^) R+ |
引入优先因子
8 J2 d. L6 v' r% J7 p
4 X! I& d0 U  V, Y9 P9 g- ?# g

目标规划的一般模型
" A. T7 ^8 @+ t3 K( ]4 O) z


目标规划的求解方法
: v" |& ]; G" Y7 V- X, _
4 m$ o# u+ E5 X' I1 _5 U: }理论基础：序贯式算法
8 h) ]6 ^: i8 v$ }7 F1 t按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

" \' @0 q1 I9 N4 k( W* Z规划算法的应用

4 Z& ^, e4 [) T8 [( U2015国赛 太阳影长的问题
" H7 l2 L7 O6 f. D% Y2 |: M0 C原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956


( J" @) A( B5 k8 d& [: `! v2 i- e  a" h8 W

德古拉

Nice shot, thx for sharing
( A' F; M" t* d) g7 m