数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
; K% ]9 N1 a& ^2 `, i% v规划的基本概念
5 U% E4 o- ^: N# ?# y规划的分类方法（了解）
+ ~) B2 c8 X3 a3 }' c. J求解规划的基本方法
*线性规划*
. g5 O3 ]2 U1 {+ Z, ^, o* m- R# l线性规划模型的建立
, G" Y5 Q) [: }7 N% d$ y# h线性规划求解
*非线性规划*
*整数规划*
3 h" G' D! P7 N整数规划的分类
整数规划的求解方法
/ |  J4 I. i1 t% J特殊整数规划0-1规划
  C2 X) v) b: \! l. D. L5 _/ `动态规划（了解即可）
2 K) s2 H+ W' ]动态规划模型的基本原理
6 \; {7 R7 M  ^# X; g6 m& H动态规划的优缺点
( L! a2 g' u8 @! V8 _8 L$ i) N, Z5 h==目标规划（重点）==
" M" y% _& M! U' W- L目标规划模型的建立
引入偏差变量的概念
& A: [8 x* Q; ^' Z引入优先因子
7 e- G" W% [. y+ K目标规划的一般模型
目标规划的求解方法
规划算法的应用
* r- Y" I" Y0 T1 y装了半天数学公式编辑器，没装好，见谅。

& `% w8 x- k; X: \: Q" Y规划算法综合概述
) g- U- N  Q& W) C( r! S! Q$ T5 `
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
" W( Y  i8 Z; d" }; M
1 ~3 D8 a# Q8 G1 g+ Q! T" @! s规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

6 z/ ^* h, r; U7 L- F" \! {5 l决策变量x，目标函数z，约束条件g(x)
. y* ?; H0 Y  [- h( ^2 f; U
规划的分类方法（了解）
% f4 c4 ^; o% p( R% O8 n

; N) k8 x  S2 s: T7 m( S0 k% Y
/ {! d4 p3 ~$ K# V5 ?& @/ s
) _! N/ Z  R# p5 g* G+ a3 [
, Z4 p1 n( E( Y求解规划的基本方法

方法：在具体规划模型中会说明
软件：Lingo Matlab
* P: C6 u8 \4 q1 ^5 ?. f( [7 U: \) t8 n: r
线性规划

线性规划即目标函数以及约束条件都是线性的规划。

" m" X' x) e- M- w! b线性规划模型的建立
3 A7 ^; ]& m& x& R  K$ |
' z  Y2 j  V5 A2 K& |0 Q- [线性规划的标准化

目标函数标准化
约束条件标准化
" B- `/ T9 J+ F" C6 {' _决策变量的标准化
) q9 d( T, Z7 f1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
* j9 Z$ Z  F6 Q# }; z& v
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如

引入松弛变量 Xn+1,Xn+2
7 B, c3 h' a3 H2 n- g4 N; ]/ @1 X
* {' g8 a/ o1 P+ Ha1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
" P% c9 k, p& `9 G9 ^a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
0 }$ I3 O$ t6 ^/ X
) g1 c2 W( {7 |% j0 m) ~& x添加限制
Xn+1>=0
Xn+2>=0
) \7 ?- u1 a0 d( d  I/ o5 B) T, Y

4.因此所有的线性规划都可以化成标准形式：
) t+ r- P! @7 i. }; A& X+ i3 J


  b+ w# J& G* O线性规划求解

理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
* B  M4 U" y+ f# J2 G0 c, }; L) z8 M
代码简单
; R/ A7 M1 y' A% [3 p结果易分析
不容易报错
1 }( z* B* L" F6 H  o6 P9 ~* u
' R* ~' m5 s0 E8 M大概就是这个样子
Matlab求解
: n5 _9 A( z( L! R
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

( F0 F6 a; Y! b7 d0 E
所有量需要化成矩阵形式，负责代码的同学自己去了解。

2 T8 m" ^: I2 |( A0 u/ `
" v) W+ j! ~( T5 Z  C非线性规划

. l; S& f1 x2 x5 ~9 L( N; o简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

! N$ v4 n) @0 x& X从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
6 e0 n% C+ m) S6 p: G8 e5 n
整数规划
/ {- j6 y% R$ y8 @
8 u, s  U0 B1 e决策变量为整数类型的规划。

6 n# G1 o$ }! S5 ], @/ r2 r整数规划的分类
2 N% T. r: T" Y, G2 F1 ^3 z% Z4 E# N

3 w8 B7 W$ P( W( r
) z2 n! P) i2 U. V整数规划的求解方法

: x6 ~7 D6 C: E5 c5 h3 }) H! r6 X) U蒙特卡洛算法
7 V+ z* k1 m; x' j蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

8 z; \5 p$ A' T6 B$ Y  X某整数规划题目的求解过程
& Z. i7 u3 f' {& z) e  F9 D, f6 Q) r

" ~+ h7 [5 k0 d: ^" ?  t& M
3 H& K/ j/ P( A- r* }9 m特殊整数规划0-1规划

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



/ @) G$ E# I' _7 V) D# e
( z  E( ]6 i+ a4 n7 P

/ t2 f: l! [% _
动态规划（了解即可）
) @2 ?& V' y* A/ h/ m5 i
  f/ K$ p: a3 @3 S1 R简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

3 M" @* i% o9 p动态规划模型的基本原理

6 R1 ]1 j5 o' T- ^最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
, f3 C, L  c4 L
0 q! l% e% F. \2 a9 n/ N- c- f8 ]1 t贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

0 _8 c# S. z7 O4 W: r+ ?8 l逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
8 \" K# f% \0 s2 U" Y! h
动态规划的优缺点
* f1 N$ O3 R! d# s0 R/ r% M( ~
) d' ]3 h; k4 y优点：
1.可得到全局最优解
: V3 B8 A; y; @+ x$ h! r4 U/ ~( _2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
6 B+ H& w5 q% ~9 v  r$ k9 S2.用数值方法求解存在维数灾
; A6 I* w+ ~  `% _% z5 _8 P; `
目标规划（重点）
  l0 E# y2 s2 T2 x2 I2 I+ H/ F
# ?+ h0 u$ i) N: `+ e目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

+ C4 v$ w4 \& b, o$ \目标规划模型的建立
8 o' C: ?# ^; r( D% y& A' X1 _
. z% F$ v4 \3 N
6 E0 e* |  E8 w/ j: C- R8 V7 J

引入偏差变量的概念


1 ^: K9 O" u8 \



  s0 X& y$ K0 J  A3 p, O引入优先因子

2 l! E2 e( L" ]3 q: z- A  x6 b% B3 E

目标规划的一般模型
  H! w/ e( Y! |* {% r* r

% m2 L. u9 O: B
/ |) Q& [: ^# Z7 m  ^5 |目标规划的求解方法

理论基础：序贯式算法
2 f) I  {3 K! t按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
* h, A  g5 l* [3 T7 s$ m2 P1 s; _
规划算法的应用
. ]) R9 Q4 b) u7 U- t
2 `0 q0 O3 h9 Z; W: r+ V2015国赛 太阳影长的问题
& y- `/ k/ I$ @' X原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
9 K/ d3 v1 u# [% v
# J1 a, \" ~. C. m
6 Y+ R! M" ~8 g, z5 d( A7 a

德古拉

Nice shot, thx for sharing
, j" Y+ k* U; P4 R; w" ?