数学建模中的规划问题

杨利霞

数学建模中的规划问题

8 U" p3 |2 z/ R* D: {6 z
*规划算法综合概述*
# l1 X, H9 ^2 G& {6 s6 y, M规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
*线性规划*
线性规划模型的建立
, W5 V1 m6 J8 B2 P2 {8 W: y+ q5 Z线性规划求解
3 p! K6 w- ~! S' ~3 U  |& r*非线性规划*
*整数规划*
整数规划的分类
整数规划的求解方法
特殊整数规划0-1规划
. b  c( H6 x* D8 i( X; X/ r动态规划（了解即可）
! Y9 g& }7 s3 A% N0 T6 N! ^$ `动态规划模型的基本原理
动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
" c; r$ Q. r/ S引入偏差变量的概念
引入优先因子
目标规划的一般模型
: F  n$ z/ P- h1 h6 \目标规划的求解方法
规划算法的应用
- T' L1 v' p2 L" E# A装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
- M7 ?$ a/ d1 x( i' n4 f& w
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
# d6 t" I+ w4 ^( |
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
% ?5 C5 e1 V" n# M; Z: ]
决策变量x，目标函数z，约束条件g(x)
+ p: s& k3 J( o% ^8 ]! `
* L! c9 b2 n5 Q1 Y, G规划的分类方法（了解）
- t: n# B! x! W& D

6 j$ p" o, A  a9 r4 A8 k


$ v+ F. `6 C$ X0 ?* e8 g6 N/ R9 X求解规划的基本方法
% {. q3 y. S7 d  T# q
方法：在具体规划模型中会说明
: ?1 Q) Q" n6 {, K4 Z软件：Lingo Matlab

线性规划

8 v6 P7 f1 O# l* [' n' A* k线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立
# k, O/ R: z3 R" z
0 O% J+ t) h2 j, S: z7 O0 P! T线性规划的标准化

目标函数标准化
; w  L) a% p5 @, c8 N约束条件标准化
0 T# p+ {, [; N+ l决策变量的标准化
4 b* \9 y5 r  o( S  M1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
3 q5 a. o5 K6 g6 H; m* p
* L! W, l4 d' r5 E6 }% l) F$ P例如

引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
0 x; h2 G' c. v
添加限制
, ^& B0 Y1 p! f8 J( {Xn+1>=0
Xn+2>=0
5 O( k" M) Y) m- k# h
+ ]& X( C- k$ L3 y$ z
9 r9 o' m& G) G$ }2 w% }3 ~! g4.因此所有的线性规划都可以化成标准形式：

/ L& e& {$ @* G6 u
  W9 e9 `8 M3 k/ U4 I7 Z! }
, Q/ s) }* h( g, F5 c4 g' M5 W# S线性规划求解
7 {$ `4 M. C. r$ w# M7 Y; @
) M7 z5 Z3 g; H9 f1 i3 L& n理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

) ^) l, }* O  v) s; ]Lingo求解

代码简单
7 d: ?: c) v) T8 K结果易分析
& L, v( _+ c9 n- M" y/ K& x) a不容易报错

大概就是这个样子
Matlab求解
  F& f6 o% K& y0 ?' R8 X
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
; z: b7 c+ {, R" L

4 ~; _9 }" l6 {6 A5 m; ]所有量需要化成矩阵形式，负责代码的同学自己去了解。

0 k, }6 D) |6 V) A) I
非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。
5 F8 Q" Q3 ^+ T  j
Matlab形式
0 a. X, d. P# ?% o1 D+ c
) V, c  \: T$ Z1 T: V从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
5 s- N8 R5 m1 s5 r0 v总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划
# g' F% |, A7 s6 E0 t. Y1 W
决策变量为整数类型的规划。

整数规划的分类

" R. ]: F; W. M/ f: Z

' U) J6 b" A+ _1 B( ~整数规划的求解方法

2 t/ {! P! t* t8 Y9 \5 C# k蒙特卡洛算法
  A. D& r" t  F2 ]# {$ F蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

' i5 G2 ]  V! j6 g某整数规划题目的求解过程



特殊整数规划0-1规划
3 \. L/ e) K2 L3 z5 U
. i* T1 f  n/ E即在整数规划的基础上增加一个限制条件 0<=x<=1


! m1 O  L) o" _


0 N! x. A  A' G6 g( }3 Z+ O- J
* I) g7 q- Q: C) x2 D
+ m+ R" n3 O0 T$ n动态规划（了解即可）

$ i. V: j" T+ f* Z$ h: }- ~. p简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

6 H6 p+ }- Q9 b& m1 V/ q动态规划模型的基本原理
$ c- i) B" v; B  u2 k& g8 B
) G7 P% M0 t& l最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
4 E6 z! w8 Q" ]- y1 ^( e" Q7 V
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
* ^6 F( ?7 M) J1 H( M2 }8 L4 l
动态规划的优缺点
# W7 n3 {5 V1 q- b
- }: l! x2 v, e, c& h优点：
1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
2 k) {; F+ b! J/ T, h; B/ U; ~1.没有统一的模型
* K% w! i" M1 i! P9 Z$ ?0 l2.用数值方法求解存在维数灾
$ _' |3 m3 v; V/ p3 I2 }: l
目标规划（重点）
4 v! O9 F& J9 v
0 [! D, E: G+ K+ Y目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立

" ^; D6 B6 j9 X: ^


8 f- E: ]0 \7 g% k* G引入偏差变量的概念




. }' o9 L7 M. r  u$ D5 ^
6 o2 M, d. y- I. b% s
; |9 L; f% K4 s* w( D2 q# w) }引入优先因子
$ Q/ H4 x% ~1 t) M# P6 d1 r& ~
* q8 I" B# @) P, A

0 q& P/ ]" S& b) ^目标规划的一般模型
* |  O1 @% @+ {9 M4 F


- v1 f' W  _- }" S目标规划的求解方法
% Q( M9 `3 ?( d8 j6 G( d
7 w; L9 a4 @( R, O" f/ t: W$ V9 c理论基础：序贯式算法
7 Q3 D7 R! T4 g6 Q* a( ^按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
& N  t5 ]0 F) ~- k0 W; u# p2 [& Y
3 l, Z5 T' f. O% c9 m2 g规划算法的应用

& f7 f2 L2 U: p+ `) u/ r! B9 C" O2015国赛 太阳影长的问题
& h7 f# W- s( m/ C. S. X原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956


7 z" b4 b. L; r0 }3 G

德古拉

Nice shot, thx for sharing