数学建模中的规划问题

杨利霞

数学建模中的规划问题

9 `) ^6 a* e  h  E$ T" ~) ~
6 p! _0 `* h# F6 j5 l( B  d*规划算法综合概述*
6 b  t: |2 Z2 T规划的基本概念
2 X3 b: g7 U  q0 W规划的分类方法（了解）
求解规划的基本方法
*线性规划*
' S) S1 J& q7 B& i5 T线性规划模型的建立
! g' b& T; p: F) ]线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
; J7 I3 F' j/ E3 _6 A' y8 W==目标规划（重点）==
目标规划模型的建立
% T! q6 H! ?) M& ~1 v# Q引入偏差变量的概念
6 k* I7 a4 z! N$ W  ?引入优先因子
6 I" }& F+ {8 w" G目标规划的一般模型
# I* M( z2 \0 o7 ~9 `4 p目标规划的求解方法
规划算法的应用
) W* Q" |% H4 X. S# O0 e装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
, k" Y% z- E1 c% S
规划的基本概念

0 J( s. s: R) W  `6 B$ h- D规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

% o; }- H% R+ M. U! e" ]决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）


5 e$ }% j$ Z$ x+ \- ~8 ]9 e

, S7 y6 K: g. U, U- _$ l% ^5 t
求解规划的基本方法

5 _8 G0 z# I6 r6 Q% i$ N方法：在具体规划模型中会说明
软件：Lingo Matlab

线性规划
; x# m# V: H9 g2 {$ B, F: E. M2 x
线性规划即目标函数以及约束条件都是线性的规划。
6 g1 U& s; C9 a$ p% n
线性规划模型的建立
: s" _1 t. K" E+ E) V+ z( W
$ H3 ?1 t3 N8 I& X. [% `, I" j线性规划的标准化
1 U! [$ y, T+ G* y* Q
8 Z2 H2 |" q" w: r3 a  @目标函数标准化
* R# M( E/ A% G* f$ z# M' j3 ~% @% ?5 u2 V约束条件标准化
  b7 C. n4 c, d4 G: F决策变量的标准化
, O" E- x: D9 o3 b# L2 G- }$ ]1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

7 @9 i7 i! c8 K2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如
5 S( _% h. @0 U; e$ ~
引入松弛变量 Xn+1,Xn+2
2 V6 p) w1 ^1 W# X) U
/ a& H# \2 Q  A9 H5 `1 s3 La1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
Xn+1>=0
Xn+2>=0

" O6 ]8 J. X, \! L7 @: R
# c9 s# y+ ]& t8 A4 P  o# x4.因此所有的线性规划都可以化成标准形式：


  D3 U2 Z. z4 x/ s6 I# l3 W4 b4 k
线性规划求解

' \: s, N8 C  s. Q! J理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
/ s9 H% j3 q8 `: Z! ^3 j6 B  m
* c! E" p  M% i8 n8 }( F代码简单
结果易分析
$ O' }! h, c4 u0 r( a! d不容易报错

大概就是这个样子
/ ]& T' }1 T, h. `% ?. g% aMatlab求解
9 M( K, a! j" [3 j+ H8 w! l
& {# z; y) d& e: n1 Y+ d3 R- W5 @其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
- A2 @3 s( H  v2 K. W& G

4 P) g0 M8 \8 V, u0 |, d6 n6 H- T所有量需要化成矩阵形式，负责代码的同学自己去了解。

+ t' p/ p1 t: d$ G8 k: q& D3 g
非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式
* m! H; Z! a; o5 ?
2 }% l0 g% G6 G5 F& b* K从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
) Y2 b+ T7 j5 _7 [- ^总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
, v+ q7 z# N4 G
4 z# [% i1 {7 s2 W整数规划

决策变量为整数类型的规划。

" \$ q$ j% r: k整数规划的分类

2 ^5 x- x: p9 [* a$ s

整数规划的求解方法

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

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

/ `; H1 ^' N( ^' |3 q  J, S" J  `1 a

% O% d) N( e1 f1 h% A特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
$ z, P: T- u0 P0 t: ?


$ u$ ^& G& }) S# }; M% E* d

8 L9 Y- T1 j; o; _7 Z

- @9 h2 C5 E: H+ X动态规划（了解即可）

7 c" ?5 s% `7 G简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
$ O7 T9 J# K, P, D( g1 R4 Q
6 s  U) X9 p; P. n7 }& F5 f/ H2 [动态规划模型的基本原理

7 u6 z9 F! r: K) Z最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
0 \# w" `4 p8 p' F8 T* j0 r
8 Q5 b* w2 Q8 J贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

$ I' X; x' U1 w0 z6 L逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
% }" R2 |+ f- u0 V0 O# _
动态规划的优缺点
3 t! A9 Z0 V  ~3 t
优点：
1.可得到全局最优解
5 H8 q3 ]9 I. z5 A2.可得到一族最优解
9 i5 [1 Z. p- A+ f. e& p2 U3.可以利用经验提高解题效率
7 F- ~/ t+ @4 u: A缺点：
1.没有统一的模型
  m. X. F+ j* x4 Q- O5 H2.用数值方法求解存在维数灾
, y/ m6 \! Z5 y
目标规划（重点）

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

目标规划模型的建立
0 z( J) H- B) Z! p8 r

4 I6 q) `3 K; q) ?: M
+ H' s" T/ L: [7 R2 b5 U
引入偏差变量的概念
1 D. ]' N. ^: l+ }0 T* N* u


" ?! n( R2 W, @& D/ l3 Z. S2 L) E
; r$ @+ b) h; s8 w

引入优先因子
0 K: Q  u6 |) n% }, J5 y' t0 S


目标规划的一般模型

" [5 ], n" c& p+ M5 H
6 z/ d3 J+ V6 D9 I
% _& J4 E1 w7 c  Q' _4 k3 }  }5 R目标规划的求解方法
* `- }0 @( C+ o( R* m
理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
  y( ]" T8 q8 K3 x+ G5 t
规划算法的应用

) h9 P& w  o' B" Q2015国赛 太阳影长的问题
8 v! V; s( P$ m+ d8 n9 |+ S原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
: I' C" q% l* y. H
- I' X0 i) D" P% g9 [  N) Z
7 @* z( O- E) p8 u" q/ q/ o

德古拉

Nice shot, thx for sharing