数学建模中的规划问题

杨利霞

数学建模中的规划问题
" f3 x' R: k) i" l
- E5 H5 N% q4 J" `& k
*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
/ H, r8 R! C5 ?8 R7 z- Z! a! c5 c求解规划的基本方法
2 {3 |# M4 V. h% L& X3 j*线性规划*
线性规划模型的建立
线性规划求解
3 v+ l8 t; p5 r*非线性规划*
) J, @# R4 t, ^& Y0 `8 O. _*整数规划*
+ W0 w% I$ }. A整数规划的分类
整数规划的求解方法
$ c5 F9 f! p7 F6 v1 _  y- X7 i特殊整数规划0-1规划
4 M; r$ X3 H: X0 u+ i: Q# G动态规划（了解即可）
- r/ j# h3 z1 ]% J# v" v) |动态规划模型的基本原理
动态规划的优缺点
" E- \; U/ s, l; |% T0 p==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
/ Y; A2 f5 C- n9 U$ X引入优先因子
  h. h1 P2 P; i" c" _目标规划的一般模型
$ q& r8 g! _  ~" n; u# W9 D- Y) H目标规划的求解方法
规划算法的应用
4 w, {4 F2 d0 C装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
6 K+ ?" p; `  s# \) K
7 e8 y) k5 y7 \8 [8 D& v2 i( |对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

0 g* _$ i7 [/ B  W# ^规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
* G9 a- q4 K$ B! R% y5 ^
$ U6 X! A4 W# B3 |1 C决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
7 J" I( I+ h3 N% x5 G5 g  a

3 ?$ h: w, w$ N9 t$ {

* t9 k( Y. M, q7 f  Q
+ p; y9 {3 K% R1 E求解规划的基本方法
6 Z. U; i1 f3 ?" S3 a0 e
" ^2 N+ T, t  b3 U* Z方法：在具体规划模型中会说明
( y; i# u7 A5 D3 ?6 O软件：Lingo Matlab
7 b# c' b! @; C, a$ T
' ~* z% g9 u% z8 A线性规划
# t! ~' f; _' g
线性规划即目标函数以及约束条件都是线性的规划。

. t  F5 a) Q6 M, q6 s0 t线性规划模型的建立

线性规划的标准化

目标函数标准化
约束条件标准化
' e2 \- N! [7 V$ Q% L( S决策变量的标准化
3 S- ?7 S2 f0 k# w9 B; A1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
& J- |& E2 e8 `: q
5 V8 G2 ]" s4 C2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如

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

4 s0 W1 ?; N3 T& H5 {+ ~a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
+ J, l6 F4 c) C' `; L& ]a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
: e" z: G+ I3 |/ c: T
* E4 q4 `: z2 {' B- o( T! v% n/ v" j添加限制
% H0 t4 ^# w5 f3 I& p& RXn+1>=0
& `: w% B% X1 S" N2 k' m4 WXn+2>=0
$ S, ~+ Y4 U1 a; |' u8 {

/ J, t; X* e) O; @+ m  m. R4.因此所有的线性规划都可以化成标准形式：
8 @/ c/ `) d% i0 u3 O

5 l  g. ^2 d% |! Y0 V
线性规划求解

, o) K3 R) W/ f8 Z9 }( E- l) R理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

+ S8 Q/ f: g1 f* U4 ~( O5 [5 xLingo求解

代码简单
9 B( H0 @% a; _( I# W结果易分析
- D* Z5 }, b9 ~( H) |不容易报错
' Y. D  {6 S; F
大概就是这个样子
' S2 r4 o- V1 `Matlab求解
( ^2 m" l) Y+ Q
8 M; \' @1 A2 A1 ?# g1 O( W6 s( ]' F其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

- q' j$ R2 |! s. y( i3 v' i, M+ O
/ f7 n* X3 v2 ]8 a5 z所有量需要化成矩阵形式，负责代码的同学自己去了解。
) v% Y2 ~  G* _4 q$ j
% C  \# n9 S+ V  B' A; x
非线性规划

0 K! }0 d$ i; Q简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

6 B& |% n7 a0 }2 u0 }8 I! X从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
2 D/ g  _0 F% G) `0 B
整数规划

# y6 u8 m% @* h. _决策变量为整数类型的规划。
) B" F2 q+ n' U8 N" r
  r' R0 j/ g8 S% x, |整数规划的分类



整数规划的求解方法

蒙特卡洛算法
- R1 [0 P4 [% |) {8 p蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

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



特殊整数规划0-1规划
8 \! F% {8 c" `$ a0 j  K
$ |8 N3 |# W& i$ h, i* i8 ^! G即在整数规划的基础上增加一个限制条件 0<=x<=1

; H/ m5 z+ e& b
2 b0 K1 K- N5 H
% K  z$ B& g7 v8 X

! Y7 d; _' a0 u" z

: G8 F: Y" C; ?4 ^4 z动态规划（了解即可）
. T: B& W7 T/ [
* ~9 ]  X  D% {0 q& A. m/ s; v4 `) r* q简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
5 [6 N0 e- @" k" l
动态规划模型的基本原理

5 f6 n/ F! e* [! x' Z. j6 F: O最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
% {4 e, E! ~6 ~. N4 _
! ~" l% _+ X4 g6 _# }9 k1 s( h贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

+ v, }2 e& t3 |% m9 ^; J! q逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

0 p# M* X4 c$ [( A$ U" u动态规划的优缺点

. U! B. C, ^+ |: i+ N: I优点：
/ ^$ ]9 I0 D* v9 _! N/ b1.可得到全局最优解
2.可得到一族最优解
4 ]# H8 C; W! t2 K1 m0 D* d' U3.可以利用经验提高解题效率
缺点：
) [. Y/ K1 k4 n$ [1.没有统一的模型
- y# i3 _+ L8 ]% ]) S* }, b3 L2.用数值方法求解存在维数灾
& q4 u2 R1 Y  _6 r: ?/ q4 X& O
目标规划（重点）

目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
2 h8 r0 e* \7 s$ ~
/ w5 w( F6 o$ p* M+ V6 ~目标规划模型的建立
# d, ]1 d$ c( C7 A# {
1 Q; i! ?$ q2 D) Y
; w4 ^2 o! ?9 b
9 Z0 \4 ~/ _! a8 O6 G
引入偏差变量的概念

3 i& ]  n& a  Q" P& D5 H- b
; o  y- Y: r! A: ~1 ~5 j% y

. Y; T5 B  {1 ~2 e6 S

引入优先因子



& N% C) R6 q3 U4 F1 R  i目标规划的一般模型

  ]3 \9 ^! U4 Q; q" e( T$ C2 s

! i* O8 q' Z3 K; ~' A/ w9 ?! u5 u目标规划的求解方法
" ^/ u7 a4 U. r
理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

# ~+ C1 t6 j- S' E- Q规划算法的应用
& P: S& o- L! B; c! j
1 z( b) C+ R+ Q5 L2015国赛 太阳影长的问题
4 P: }0 U" F0 E! R& @, `原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956


  q3 q" N  F* P7 ~

德古拉

Nice shot, thx for sharing
: Y4 _; e, \8 k. r! D