数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
; g$ z% e% e& S! Y5 L* _! U求解规划的基本方法
*线性规划*
2 K/ P7 J7 O8 [8 N, F6 D7 b9 j! ?6 [线性规划模型的建立
2 h1 x6 w4 N2 v* c; f9 @* m线性规划求解
5 F+ `; I3 Q# s  O5 r8 n*非线性规划*
( \% ]7 F- z6 a) d1 q4 U*整数规划*
! Y6 h1 U# X! Z; R$ F整数规划的分类
整数规划的求解方法
9 R9 L4 r6 Z. w& f$ w9 x3 D0 i. M特殊整数规划0-1规划
动态规划（了解即可）
' g$ s$ E" N) e5 J; }0 y) v! G动态规划模型的基本原理
' J; M* |" j. o( \9 S& |动态规划的优缺点
7 ?5 J2 r2 m) F==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
引入优先因子
( E9 s& C6 r" O5 J6 b目标规划的一般模型
% d: z+ k" T! S8 u# F4 ^' c目标规划的求解方法
规划算法的应用
3 p4 \) ~0 S' m' n8 ^装了半天数学公式编辑器，没装好，见谅。
) G7 d  c$ `' n" e
规划算法综合概述
% U* ^3 D& W0 t: A4 D6 W
" u0 c' U+ H# h7 F- s对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
* ], x( q. `4 d5 W5 `
5 T, N: R9 f# W: N( L规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
. c+ ?. D9 f3 r7 M
: g4 p8 Z- H, {. f决策变量x，目标函数z，约束条件g(x)
5 E/ }4 I" g5 z
5 L6 K4 m! }8 N" a1 [3 U% r规划的分类方法（了解）


0 G& I5 Y% ]; k; [4 b

4 E! ~1 M# h! U) S  D, L
2 w8 F3 l" W9 x2 r+ N7 h% V0 z求解规划的基本方法

1 b; m! z) C" f/ _3 S1 E4 Q方法：在具体规划模型中会说明
( i( U* b9 Q' v+ g4 \+ A' L, f软件：Lingo Matlab

, t9 f) r( h* X! O线性规划
6 t+ V. m+ v. L! f, N1 X5 y5 i+ C+ J* E
* m7 d3 B$ g4 X8 v1 f& p线性规划即目标函数以及约束条件都是线性的规划。
: s5 W' A- A. [& D5 Y4 V! Y
线性规划模型的建立
: T' I$ I" L- [
% H3 p' A9 R1 M. r! ?  f1 E线性规划的标准化
' V$ _7 [  P+ A! @8 F5 J
# l; R0 X) I' H5 C+ a+ `目标函数标准化
9 _# X' X5 B" o, ^- t; [, d5 q. Y9 g约束条件标准化
决策变量的标准化
# Q" A; J7 N6 Z8 ?1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
  \+ p9 t5 l" ~! v# L
例如

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

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
Xn+1>=0
Xn+2>=0
' ~' b2 h) t' i) w* v1 A: R
( M# Q1 a' ~4 b* O
4.因此所有的线性规划都可以化成标准形式：
7 j- k' Y! W7 m! ]9 W
! S$ i6 {" E+ \- {. O% G
" |7 o  W" ^  p+ p( k1 ^$ h0 H
线性规划求解
# l( L1 z: {7 ]4 [
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

8 o& F% e/ y' [9 Q' y& z' ULingo求解

$ p) F) t4 V! P& U+ C. h  U4 K代码简单
# X) M/ O# l2 ]$ h$ [: e7 t: \结果易分析
不容易报错
! \/ G1 L8 [: f, @' ]
大概就是这个样子
Matlab求解

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


所有量需要化成矩阵形式，负责代码的同学自己去了解。
  n0 F8 h! W: G5 Y; `" D/ t
9 m0 l( R- R7 p+ G- X' b
非线性规划

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

Matlab形式

' P' A) v: w# {( [- w从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
$ {4 H8 s) g( s+ }总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

; ]0 ~0 ?! L* O6 r整数规划

决策变量为整数类型的规划。
6 W( J! e- e3 a; F1 _9 |9 ^2 M3 s$ [+ }+ Q
整数规划的分类

9 j3 F3 A  }. b. ^7 o& o

' M/ [; F, R, P) o! O整数规划的求解方法

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

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

  Y; ~' v$ N% b$ @+ E# V
  s  s! ?0 \2 {4 m
特殊整数规划0-1规划
8 G; M+ }- ^) J$ i9 V+ d
) H3 U- a9 A; N% L8 ^$ E7 z即在整数规划的基础上增加一个限制条件 0<=x<=1





" }9 V- h! Z9 D+ ~; M- [

1 o  t! ?5 T- {" K1 {7 X4 M2 v动态规划（了解即可）
1 t9 r0 \9 @+ m4 E7 f; x2 K, W
  u7 p/ W1 m3 R8 D6 J# z% c简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
: f7 y- T: e1 p* k- p$ R
动态规划模型的基本原理
3 c; k/ v: J3 l5 ]7 X: ?, j
# `3 j4 S# i' d8 q9 t! a+ t最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

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

逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
8 Q3 w4 j& g9 ~# p7 H
( A# O3 r" L7 t. P5 z动态规划的优缺点

% n' p( H. O. s0 v优点：
3 @9 d5 C! G' m8 g0 R8 [" i1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
5 M3 q3 K' z% A$ E, _9 S1.没有统一的模型
2.用数值方法求解存在维数灾

目标规划（重点）
( `1 ?  f% f1 S$ `% }7 v
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
: V" z; {, Z/ r' o! V0 N# v
目标规划模型的建立
9 A, O" r9 d1 {. a6 m* W
, q3 |' y3 Z; S  T8 f
7 o# V3 P8 V. E9 W

引入偏差变量的概念

" x6 p5 }, R7 ?- B. c3 @



" c  R  D9 W& A& G9 X) A6 `
8 [8 t8 ^. Q9 ^3 ]引入优先因子
1 u: L- Z4 D, x

9 t- e$ v- ?. N( Y8 f$ ^
目标规划的一般模型
( s9 I; U5 W5 {" P9 s- O) w( Y
% O$ B4 A: c  W; u" U
# e! \( x" e2 k4 v
目标规划的求解方法
7 m) K4 S. x$ l" y5 n: L* k0 L
理论基础：序贯式算法
- A2 J* F2 T* M  I7 f# T/ z2 a按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用

- U; b( U, W# V3 [& @2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
: m9 y3 g/ R+ d' [% t- s7 {; n/ O
0 U* e( y( P9 _

德古拉

Nice shot, thx for sharing
9 ]) p- }2 t# N4 V0 w