数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
& y3 U4 i4 }5 e9 G) f! w$ W求解规划的基本方法
& M3 `5 _! A! U' W0 e0 t0 y' q*线性规划*
线性规划模型的建立
) U% Z. L8 o$ Z线性规划求解
9 l/ T: W6 n9 o2 }" H  _! o*非线性规划*
*整数规划*
整数规划的分类
+ c0 p4 d2 J5 s$ n( X$ i整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
5 d8 V) |6 H' |% G& ?/ I/ ^8 o动态规划模型的基本原理
动态规划的优缺点
7 a9 R  a$ E& ]8 Y- r  {" K==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
引入优先因子
目标规划的一般模型
* `5 t$ d1 o. F目标规划的求解方法
规划算法的应用
" z. I; [7 x; ]# r$ [0 @2 b+ f0 S装了半天数学公式编辑器，没装好，见谅。
7 s5 u3 J5 d, r6 E# i0 P+ I: n
规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
) M! A/ z% v5 ^' J. k3 F
规划的基本概念

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

决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
4 D( c% f% @/ [+ U! H$ H8 `

1 M. b: D% T' p. c3 M& N* L: R
2 R7 ?- C& s) p' T6 a- K5 i

! i- m  V* l9 M6 P. ]9 |0 m& x2 p求解规划的基本方法
% J9 K2 ]$ q* _) v+ V2 x
方法：在具体规划模型中会说明
+ e. y( v; Y% J9 F2 L5 {  h软件：Lingo Matlab
- u! f) s* m5 r( i' k
! f: {, ?( B9 _* j" c1 _$ n: i6 r4 w# I线性规划

( X% A: F" B& Q1 t线性规划即目标函数以及约束条件都是线性的规划。
- X# d8 n- K# T" D  n& U
线性规划模型的建立

线性规划的标准化
# J2 Q) p% N* M) r+ N4 S0 \( n+ F! Y, [: w
目标函数标准化
约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
# g( g: J2 w! O5 i
! l, Z6 x7 Y2 e例如
, H  f' H7 A3 K! ?
8 x% i: y) [1 ~, P1 X引入松弛变量 Xn+1,Xn+2
& J! s3 o) A5 m! ~" }! H- a
: j* {. I; t* e" z, ja1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
! z9 m4 J- |0 l; h  Ra1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
  d: L$ d- J: ^: p# t
6 d1 I: p0 J5 m" R$ n9 q# o5 g添加限制
Xn+1>=0
Xn+2>=0

. p9 y; L( z+ j" V: H- W
7 E! o5 y, W& \& v; f3 b4.因此所有的线性规划都可以化成标准形式：



2 K6 C+ I# T: p, z( |# p! F1 [线性规划求解

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

* Y/ L2 i' q3 P2 k3 iLingo求解
5 O4 u% i5 o5 p8 M4 L
* T$ r+ Y) j* O2 L代码简单
结果易分析
不容易报错

大概就是这个样子
0 i! e: ~$ c6 R1 x1 iMatlab求解

其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。


! c( g/ i3 t+ s2 Z. ^6 a( P! b所有量需要化成矩阵形式，负责代码的同学自己去了解。

" w# u# Y8 d* X, ?0 o
非线性规划

$ i2 R9 @" G: s& k9 m1 N简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

$ {) ~- ^& z: R: \7 s从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
; \1 u" `! M4 t3 A总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
9 ^/ R) T9 n, ~# v4 a( S) P
整数规划
8 J, A' p. n5 j
6 ^$ l' n" \( \/ s& `$ ^决策变量为整数类型的规划。

整数规划的分类

% M) M1 S4 p* M5 U  H8 J7 A

5 }& o6 ^! P7 W) N整数规划的求解方法

5 s+ u" ]' Y) z9 j2 j蒙特卡洛算法
8 O! n+ N4 `' W# U, I3 Q蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
* T9 z- F( ^6 c6 l. h
某整数规划题目的求解过程

5 J2 z3 l% `4 p

( _; j( l" I1 V! b; H7 D特殊整数规划0-1规划

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

7 F) ~, V% a1 V3 E+ P7 T


% A# x# H* y, I3 l0 T3 H
. M' t- ]9 T% R

8 a( M/ D; U6 q- ]2 b4 _0 G* z' J6 `' z: J动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
; ?+ p. t" e2 T) _& P/ ~+ _
7 \+ i, b  c. z# e1 B; D贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

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

动态规划的优缺点

' R/ d9 B, }6 x4 D优点：
. x" }* A4 g$ ]" ]7 c( _1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
" D- O2 W) g6 Y6 G! d2.用数值方法求解存在维数灾
7 J# A0 K8 q7 S6 J
2 d# w9 x  O! A. X% Z5 J目标规划（重点）
4 h. @/ A* J- M1 ^; H* |- ~. n
" z3 d6 V+ }8 B4 h! l  u目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立
1 t. ?& j! O  V$ x# J8 T

- B1 [8 s# x2 G" H$ I: M
  ^4 b% ?1 n3 [/ @: q
引入偏差变量的概念



' F) r2 v4 O8 c: l
& s' G" q  m) {  w

引入优先因子

' E; S: F3 c9 X6 G- L# l

. \1 S! p0 k: O  N/ w  m目标规划的一般模型
8 B5 D0 W6 M6 y


* f% J/ F$ m- v- t目标规划的求解方法
% y; t" ]% f5 U, i6 L4 H
% m! L# b4 U( A9 O) @! H" p( s理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
3 g6 T  Q* l7 A4 p! v# D9 R
6 o" C- H1 C' ~+ S, d4 M规划算法的应用
$ h) c7 S6 T' U
2015国赛 太阳影长的问题
# C* b) J# d/ y3 R9 a) C原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
9 P0 o) s: u& s0 ~; I) {" I, T% A  u

, i3 H% r; Y( Z( [2 C1 t9 P% [  E/ D$ S

德古拉

Nice shot, thx for sharing