数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
) l8 V* w: w. [: e5 W规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
6 W7 k8 a$ b$ `: I  u  e) K4 o*线性规划*
! H- n+ g, I/ f7 }  n线性规划模型的建立
线性规划求解
& W& p7 }' p' q*非线性规划*
*整数规划*
- L& y8 B7 X" d% P3 [* t; S) n; i整数规划的分类
整数规划的求解方法
' b; G1 N) H: m特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
# [9 S  M" \" k- X/ U4 p动态规划的优缺点
% [) P3 d  e3 a" n+ z* {6 L+ l==目标规划（重点）==
% j* D9 ^" e2 |5 r2 h) t目标规划模型的建立
引入偏差变量的概念
7 {' [9 A! F. k; D. z: w  m) d/ ?引入优先因子
/ r; g: L( S: @# a* T$ `目标规划的一般模型
. a* f- E2 G4 l. O5 I目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
1 I& W; k. A. y$ r, D+ E- f
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

) s) ]# T' A/ W规划的基本概念

' K% _$ a2 s" Q规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
/ q+ J7 r) z5 e- B
决策变量x，目标函数z，约束条件g(x)

. q' J8 I6 f- f$ T规划的分类方法（了解）
: |$ ^# M- W7 _1 ~7 k- g) t6 J& j) W  t



3 H5 o8 W. `0 H# D
/ s% e( p& `, O$ t6 S* S: F; N求解规划的基本方法

方法：在具体规划模型中会说明
) _- G4 i8 c4 y4 W! X" R, M软件：Lingo Matlab

线性规划

线性规划即目标函数以及约束条件都是线性的规划。
" W, h) ]" ]; U: K* t) H
8 `* h, h4 @! g9 ?2 C' \线性规划模型的建立

线性规划的标准化

目标函数标准化
" e' c6 n1 D, E6 @5 V约束条件标准化
: H8 Q% \) q* P% Q$ O' j决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
8 o8 v. ^# Z0 T9 P, W* Q
例如
; `9 i4 M$ n$ J4 D. j
引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
" b- W0 Y- X% ?) U+ \8 V  S
添加限制
, Q! Q* J/ o) }: q. aXn+1>=0
6 m2 Q5 N, f. e$ pXn+2>=0
8 E9 p3 h0 a8 L( f1 W2 N. {

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



线性规划求解

理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
5 n% l4 Z3 A& t% S3 X
Lingo求解
0 C) J0 \' w' s) a6 K; l
代码简单
结果易分析
5 O7 ^2 g* }4 {5 e% f& M* Q$ s不容易报错

4 k& i& @! R; N/ Y/ {% b0 m大概就是这个样子
! |) r( m2 M2 \' F1 |1 `# E' ]6 ~Matlab求解

其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
, M# n% X0 T* `0 D& Z& L
) ?: m+ P5 A6 s) O
* J" n7 P# P3 i" K! L) }( ^0 [所有量需要化成矩阵形式，负责代码的同学自己去了解。
0 u; s$ U* D6 h% {* G. K& c5 R! }

非线性规划
  q) w( K: K+ X4 G
' D; ^6 z+ l) Q: K8 H+ P$ H简单说就是目标函数和约束条件至少有一个是非线性的规划。

3 A& X; f$ `. ?4 E( f- ~; FMatlab形式

1 O" ?3 K1 e; Y9 r从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划

! V/ S% u. h$ p  u3 ]+ e决策变量为整数类型的规划。
1 m" ^2 Z& D; P8 P& m/ D/ N
2 q- P8 m1 v' k整数规划的分类

1 B1 ?! k- p$ p

整数规划的求解方法

, z8 d) ~8 Z3 b蒙特卡洛算法
3 c# X) F1 `2 P# \3 }蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

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


3 I1 q! E8 N- }
特殊整数规划0-1规划
7 M9 k0 Z5 p* G" m9 t2 o+ V
即在整数规划的基础上增加一个限制条件 0<=x<=1


2 b4 U8 L% y9 T
9 Z/ E' t9 z. ?8 j7 B
  f- V) }1 c9 ]9 X/ [

2 G6 `  l# `2 T5 S" c. q
* N, @8 e0 D+ x$ d; s9 b2 b# a7 @动态规划（了解即可）

; j- t% U: L/ u9 c简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

/ }# \+ H( }$ M动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

/ H/ I0 @( k  t2 v, Y+ _动态规划的优缺点
' m/ E/ s- w) `8 n& `  A
4 j) T7 |6 l* V* Y2 `优点：
% d! B9 ^( i% q6 m5 g4 q1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

8 g3 B7 t) E. L: p2 V+ _目标规划（重点）

5 o  z) h3 `' k) N+ e7 v8 k目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
, N" e4 @7 K- I; S1 v; c
+ U( n8 k! _' Q$ \目标规划模型的建立

+ C2 J- V4 ~; x4 D$ H( L


; E& d* Q& L. c) ^引入偏差变量的概念



* K' e0 _+ j( _# h- |% W) U& E0 N


/ ?! X8 a" h" L  N引入优先因子

8 O( A. H( w" N2 ~" }1 g( |# B
7 r2 s; ~2 q" _! j
) J* N- y: E% h目标规划的一般模型



' v% ~+ f4 K+ q1 m4 F9 P0 J目标规划的求解方法

1 ~" K, O; t* F3 i  x5 T4 |, T理论基础：序贯式算法
  f" ^( |1 J0 E$ M5 p5 f! g" }按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
% f9 G& A4 ?& C/ N! d- w
  ]. ]+ j. z" X4 r. d4 d$ H, B规划算法的应用
; d# z, Y: _9 e7 e! a
$ J$ Y8 W* r) B- S/ J2 l6 x1 O( S# R2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
( \  @! n$ c. ~/ X) e2 ^; B

6 m$ T1 f. q- v0 t% k

德古拉

Nice shot, thx for sharing
0 J! j% i6 D5 N% p6 T, O