数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
9 U' \& ]( @) a3 b/ \7 H; a规划的基本概念
7 g6 i0 ?3 j% D! r规划的分类方法（了解）
求解规划的基本方法
; W. t8 q: ]) Z- i5 R# ]*线性规划*
线性规划模型的建立
线性规划求解
2 M: |5 x5 w3 w0 e# _) r; X*非线性规划*
8 W* d5 W* j* U*整数规划*
整数规划的分类
整数规划的求解方法
1 t. d# X+ {* C特殊整数规划0-1规划
8 F  }0 p. G6 s动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
5 P9 L2 r, O+ u/ s==目标规划（重点）==
! \- _/ Q) i0 S" a  A' w5 {( U目标规划模型的建立
0 Q6 L0 L4 q/ b4 x, Y$ m引入偏差变量的概念
0 W/ x$ N+ _0 q0 K, D9 }引入优先因子
: y* P& R7 }2 t9 A6 R0 ~3 m( H目标规划的一般模型
: g3 U7 e: F8 r% H# S0 }目标规划的求解方法
5 H& \  o% A) n- |2 a! X( l9 t7 S规划算法的应用
  d6 v7 v! A3 b8 j- t装了半天数学公式编辑器，没装好，见谅。
8 O, t6 k/ i+ s, A0 i
* ~6 U0 i# Y: g0 V6 Y) O规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
0 g- O2 \9 l/ m; P  {
6 u1 X# k# b. h4 M( x% @0 R) r规划的基本概念

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

) e/ [; N$ h5 l" K/ k决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
, N. j; _& L  J# x7 k4 H9 ~

+ W$ `* V0 V& y' ~6 R
% ~5 A/ {) [4 c6 f
, p7 X) z; F) ^. K5 r
求解规划的基本方法
0 g; P: `9 _4 ~
. R, [1 z0 S3 j9 V方法：在具体规划模型中会说明
3 C9 X* t* H9 z# N# b软件：Lingo Matlab

2 R' B' H/ e7 ^2 p( I/ k3 |线性规划

- \* H4 K- w! n+ b' O- A线性规划即目标函数以及约束条件都是线性的规划。
: T+ M# n" o( z& b# V
线性规划模型的建立

+ T8 o/ q  p) P4 t线性规划的标准化
/ u, V5 j& l# Q$ M; K
目标函数标准化
约束条件标准化
5 a+ `9 R2 _( w0 L* U, \$ T+ @决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
) j6 B) {/ z5 r7 g
/ z; ?% |" O' ^. \2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如
0 P; B2 A; g$ r+ p: }/ m( [2 r' b
, w5 ~; M5 D( L: p2 Z引入松弛变量 Xn+1,Xn+2
, }) B, O2 c6 x& M7 `, v9 E
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

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

( y. ^! X6 k: o5 U% P
( {/ C8 T6 g% u2 r" }1 W/ q4.因此所有的线性规划都可以化成标准形式：
# q& m- U* B" Z' v  E& z( \

0 [7 J2 Z# `" V' H6 i
6 g9 d% a- m! X2 _4 p线性规划求解
) r( i* W9 U- Q) |* i
2 s" h8 G9 \% f# l理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

" }' v; ?6 c" J8 \; g1 }Lingo求解

. B8 E- ^1 O7 V3 v0 ]代码简单
结果易分析
5 f  v1 {  t, D: H( c9 e不容易报错
* |) f) p) h' A# x# u" m0 R8 I% m  C
( y3 n& c. ]( P. X5 W; q& X大概就是这个样子
  \  H- U- T9 U% P- u% V( K$ uMatlab求解

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

: W8 A# Q" D2 |; X- v2 G0 s% M! g
所有量需要化成矩阵形式，负责代码的同学自己去了解。
8 w* o$ ^- C8 V% K
; J. N# T! h% F3 t( k7 e- L
$ v- I& K2 @8 A# ?8 G非线性规划
0 E2 z! I1 ?' W+ o4 E' k
简单说就是目标函数和约束条件至少有一个是非线性的规划。
$ h" r5 h- a0 L- ^% u5 [1 d2 K* _
Matlab形式

* x, A$ w% v4 E& l5 z, Y从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
+ E) }* X+ {" d/ k5 q总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
5 o9 ]& h/ ]1 u$ M
9 G9 R* W8 R! S3 q" Z9 x整数规划
  l3 k5 K; ?0 ]9 Y6 E1 e2 q
7 Q( j/ R% G( F& c8 z决策变量为整数类型的规划。

整数规划的分类

, r2 f& q$ S- B

% ?1 k( L% L) x# Y- |! {+ I整数规划的求解方法

% p5 B6 r: {  O) s5 B' i- H蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
) V" T5 T! f7 i
某整数规划题目的求解过程
+ {4 M2 L( ]. z' H
8 [, [- T; k7 S6 O$ D2 e7 T

6 e1 J" p2 \. F+ _特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
5 c; H' J+ x3 M: ]1 u

( Q* u# ]; z7 o9 c  A

6 |* {: p0 }, a) {. b5 E9 Q7 o
5 V* M) S/ k! R* M+ M8 x3 C+ R0 j: F5 K

动态规划（了解即可）

2 B& l; e+ j. F- S4 O简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

7 |5 h8 G9 `, @% e2 S  T' ]& }动态规划模型的基本原理

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

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

$ d- m4 c  e3 s% X  c' ^4 N逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
7 y9 q# R- ]. G, {" ]% u) E0 Z
! g- c8 t, T* R- C动态规划的优缺点
9 a6 |" P) d. F7 `* F, v5 z
优点：
1.可得到全局最优解
; r% ~& d, Q6 L6 K% X- k& [6 S2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

目标规划（重点）
2 t6 N4 m! m7 C
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
" A3 D; h2 B! K4 w  o% @" R: y
目标规划模型的建立
* M) I. w  P) b; m



引入偏差变量的概念

* n/ b$ x+ }+ |" [; h* p4 }
2 ~5 H$ |' t. N- j


- l! I, Z& u6 X$ u" J& S3 `3 t
& T9 R5 u* h9 V" y% j引入优先因子
7 }* p" j# ?) _1 w
1 H; o1 n6 s0 R% U

目标规划的一般模型
  d& a; C3 ?( u# G2 k: W' p
) m, ~& C0 r  u2 v% p# _1 p3 V: z
1 i# T5 G" _5 }2 g; E1 s6 s
- Y# [) }1 |: ]/ @7 @目标规划的求解方法
. o5 `6 s* @$ p
, N7 I9 l& Z: O4 j理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

* o- |9 t6 e+ O; G, ?规划算法的应用

, S" X1 Z7 X" H1 q+ ?3 z2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

德古拉

Nice shot, thx for sharing
6 e6 c4 w1 a- c" o, U5 P