数学建模中的规划问题

杨利霞

数学建模中的规划问题
1 b; [; h) Y3 m

6 ^2 [2 |% z* V*规划算法综合概述*
规划的基本概念
8 i3 q- o2 d) ?- B& d! k  X, h规划的分类方法（了解）
求解规划的基本方法
*线性规划*
2 s$ M6 N9 U  P( ]$ q" m8 |7 P* r线性规划模型的建立
线性规划求解
) L9 {0 v9 y/ C$ g*非线性规划*
*整数规划*
整数规划的分类
4 z9 L5 S' y/ e6 _0 B整数规划的求解方法
特殊整数规划0-1规划
6 P) v0 A2 x3 }/ o/ Q  b2 ~动态规划（了解即可）
动态规划模型的基本原理
. t* y8 G& G7 w; I1 m动态规划的优缺点
" w) a( _0 P# _# @# M  @) _" c==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
引入优先因子
目标规划的一般模型
( }2 O0 \# V9 o8 ~目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
! Q, a/ b  I" U5 K% r1 {' ]" U
- c2 [( O& @. J3 I8 o对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
5 D  x4 w2 S  R' S
6 s4 k4 l) @: Z5 I5 L* h规划的基本概念
0 ]4 H$ v- z* [/ I& i9 d1 [( i
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
3 k. |6 I* j8 P
决策变量x，目标函数z，约束条件g(x)

1 I+ X* u, B) u9 x( r4 g规划的分类方法（了解）

+ C/ v! d' Y$ [6 k, _; P
% ^8 e6 @' m' L* g! h5 W: \# Q! S4 x


2 n8 p: w& U) U; {8 e) _求解规划的基本方法
# b' ^/ I6 j( l4 N; O2 E% ?
方法：在具体规划模型中会说明
软件：Lingo Matlab
) E9 z1 p/ B  g, k+ L1 U/ U
线性规划
  K* |: j$ ~! s
9 F8 u* p9 j' s6 l  D1 g  K线性规划即目标函数以及约束条件都是线性的规划。
7 J5 h5 j% b0 w- \% [0 T
* @* d; [& l8 J, ]! U. F9 @( D+ b线性规划模型的建立
5 [  J) a6 |  A* Z
! q/ F7 g4 [7 }8 U% J  o线性规划的标准化
; q# F2 w7 {+ k! s3 Z$ V
) J; G! y* ~, ~1 e* \6 d; Z4 y目标函数标准化
约束条件标准化
& f& [4 w$ {; ~- J' T决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

/ }7 S& [1 S0 z5 Q8 }1 W2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
5 u8 l# S8 f$ Q: W
9 \$ P; O2 o" C$ b9 B( ~例如

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

6 i7 a. Y2 ^$ _' O! D4 s+ X3 Ma1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

) w, L% g. C( J0 U- I$ o  N添加限制
Xn+1>=0
Xn+2>=0


; Z' V( B" T/ _5 Q% X2 |4.因此所有的线性规划都可以化成标准形式：
7 b* m* N5 K% ?

: e( _1 ], l* [: D
+ y0 N; \5 r* c线性规划求解

# U3 {3 L# F' _( D" u理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
' `# Z! O7 ?. T5 @2 R
! Z3 w/ m% P9 l2 f& ^6 I* }Lingo求解
# s! p( P  f/ l$ B& z7 N9 `  T
8 ^! O+ U2 F6 J: Z代码简单
结果易分析
2 G% L( ?9 y- q- \不容易报错

) U& H: L5 ~& b# N大概就是这个样子
+ V1 k. ?6 m5 C8 A) H/ _+ ~Matlab求解
9 M0 d2 X1 [) Q- o
' |. v5 j5 E8 A其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。


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

( i; U( d2 v. w3 C, t
$ Q8 Y5 T6 G) c! V& s* V# Y  b9 m非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。
& o/ T4 c/ {5 r
! }1 r4 _' Z/ J! ]- g- xMatlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
. t2 a5 f, x4 k/ h1 q% `7 p
整数规划

* _% ?' E/ S8 q决策变量为整数类型的规划。

+ o8 |- q  j7 F6 \7 ]! i整数规划的分类
/ z5 x$ {% l9 q( ~
7 R4 e1 i+ Q/ L: K* m9 m& X

整数规划的求解方法
: x) |# b/ ^( ?6 D8 e7 W) T1 I
  m  y; v( j: Y8 i) |蒙特卡洛算法
+ g- ~( e  \$ X; z* K" T* l蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程

8 |$ P# G1 k( O$ h3 ^- ?' q
. G& m! o4 `3 N0 I
特殊整数规划0-1规划

; J9 m" N5 S0 B1 D7 n即在整数规划的基础上增加一个限制条件 0<=x<=1

- U, ]! L# D: R0 Q( B' B
7 M& i& T: y" I* N4 W
! q( {! x" b5 X

! A; ~0 W! R, g( ^5 r3 |0 a! _

动态规划（了解即可）
: ^% D5 k7 b5 K
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
" }" p! S( T) J4 S) y# N* A' s
* g4 A& P. g$ K: B6 @9 _9 a$ p/ d动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
. l; Z% G, x# L9 g! X0 g
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
( h5 @" g) U4 Q  \0 Z, w' t' w
8 s/ E+ w& U, M! k$ w3 E+ r3 T动态规划的优缺点
2 a' M( a6 ]0 b+ |  F
优点：
! M# X. _: v. f1 Z0 q/ Q1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
5 ^  D5 O* P4 e; U$ K% \缺点：
% a- L/ Y7 o& |  f1.没有统一的模型
' w2 G& T3 {# S8 B! O; j2.用数值方法求解存在维数灾

目标规划（重点）

) a0 q" j8 N6 R! f: k! W4 P目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立
  J4 f3 K2 Z) F9 g
* N( f& W" b9 j


引入偏差变量的概念



" R( F5 [7 J1 o! U. X

: V$ S" B/ R) y5 {  t4 b
引入优先因子
' n6 ?5 g3 _, L# k

& H. g, P+ A0 }1 J4 w8 v9 U& ~
+ K8 V0 P3 R# C) ]  [8 H5 N0 Y目标规划的一般模型

6 y2 C# t" V0 X5 N/ N

目标规划的求解方法
( a  Y, U$ a2 P/ e
理论基础：序贯式算法
1 o5 l9 L4 b: Q2 H3 M& j& r按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
7 v. @* a6 q4 S3 Z
) o2 y7 R/ }# h4 a" H- e2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
1 O2 \. V0 L. U
/ o% g9 h6 }3 E8 v$ ~8 U; B8 j& G3 p1 z( @' k

德古拉

Nice shot, thx for sharing
$ H8 k9 Y4 U) _3 I$ o: K