数学建模中的规划问题

杨利霞

数学建模中的规划问题
) |4 F- i# n  `
# A5 _7 ^/ @$ @5 p( l$ N2 F
0 r* k3 J2 p$ V' V! Y*规划算法综合概述*
5 c3 f5 X5 z( ?7 u9 c5 O9 j6 E- ]规划的基本概念
8 }: R3 I2 ~% R% ^规划的分类方法（了解）
求解规划的基本方法
*线性规划*
/ m, @3 M, x: F2 H& R线性规划模型的建立
线性规划求解
*非线性规划*
*整数规划*
& F! |; c0 P% Q+ \  X" o整数规划的分类
整数规划的求解方法
" ^* F* `+ k* b特殊整数规划0-1规划
动态规划（了解即可）
5 `% I! J1 j1 x9 q# L  u动态规划模型的基本原理
动态规划的优缺点
==目标规划（重点）==
, H) U1 V7 f& p6 T/ C* y  O- }目标规划模型的建立
引入偏差变量的概念
引入优先因子
1 H" I3 Q7 Q% |; P$ m目标规划的一般模型
目标规划的求解方法
规划算法的应用
' F7 j5 Y1 m$ }" w+ S! f0 W9 O0 e装了半天数学公式编辑器，没装好，见谅。
/ c  E+ s' u) x: @, A+ |
. m+ q" b5 T2 n& z6 Y! v5 k规划算法综合概述
+ D9 {) m( N! {, q# V
! c' U3 C" C/ B1 f% s0 I对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
# W4 q" b  {+ x* A% x
- C) d: F$ Q* o. I# V/ z规划的基本概念

. T7 o! `5 f+ t! W" _1 x) P  |规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
9 Q" _6 `! K* C! N
3 f5 g. w1 q+ p2 o/ A' k) @" r决策变量x，目标函数z，约束条件g(x)

7 a% Z& w0 C, H; {规划的分类方法（了解）



% N; c- A- M: L8 r- E! N" Q, o0 }

( U# ^( ^  S/ q" a$ \% z求解规划的基本方法

方法：在具体规划模型中会说明
5 t6 C# D: ^$ J$ H5 w" E软件：Lingo Matlab

线性规划

线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立

& H- L$ h; m5 ^+ l7 ^2 c线性规划的标准化

. P, {: i8 L5 k8 [目标函数标准化
约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
' J6 i- F6 c$ W3 b" i# @2 I  Y
$ v5 ]3 Q. d, u* C0 L' B例如

& L- h" |+ }2 u4 D2 Y( G3 m引入松弛变量 Xn+1,Xn+2
" M) ~2 @; [5 j* i0 L/ a+ R
- s7 p0 p1 j! B# y' Ra1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
$ e  X4 Q8 \0 F9 h- e) {) k) ]% ~a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
Xn+1>=0
Xn+2>=0
4 N/ O" S8 G( Z. R6 g9 ^* d

9 M. y) E" N) a- C3 C4.因此所有的线性规划都可以化成标准形式：
# }& s# P2 m9 m8 t, ?% O
$ s& t+ Q8 |5 F& N

- }, f1 @' v& S1 D% ?9 ?线性规划求解
. A+ t* f/ T3 M1 E
6 L& N  |+ d2 `; ~理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

# a% D- D4 U6 a4 Z/ c4 p, NLingo求解

6 ]. e2 R3 N% R# X$ _代码简单
结果易分析
不容易报错

大概就是这个样子
Matlab求解

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

% V1 L. _: G9 h& ~& K" S! F
所有量需要化成矩阵形式，负责代码的同学自己去了解。


非线性规划

: }4 c( R+ T# k- r: k- Y简单说就是目标函数和约束条件至少有一个是非线性的规划。
. _- h7 l  Y$ L2 e
7 k$ W6 L7 ^+ j( M+ \& D/ qMatlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划

4 j" c; n/ D( W决策变量为整数类型的规划。
' R* }, O# I  M0 V2 H3 ]
& K* |! ^9 ]  @* h5 x0 |" ^整数规划的分类


1 E1 h/ D! V( t5 l/ j" c6 T, Z
整数规划的求解方法
: O$ j3 ^) N" o+ z0 |5 f/ U
蒙特卡洛算法
% V8 L7 o7 m6 ]5 i, \蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

, U( G3 ?5 U( ~  p7 H某整数规划题目的求解过程
/ {; t. B* d$ }: N

+ s. N2 Z( P% I% a
特殊整数规划0-1规划
0 a; f; k, X* Y/ s  J- g  P! G7 x
! X' }6 `. a. s1 S* K* |/ x即在整数规划的基础上增加一个限制条件 0<=x<=1
$ i+ z" p; }: ]- Y$ J

+ @( g" o/ _- M! \: U) m




动态规划（了解即可）
% ~8 P. m1 y( W
. j5 [& D4 R0 T: I简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
5 Q; H  w8 y. z: o2 @' e
9 R1 P" L7 U/ M动态规划模型的基本原理

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

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

- g7 D9 u; o9 H2 _% H; ^逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

$ K3 s$ R) _) L5 y& `: K动态规划的优缺点
' _% ]3 c5 O2 C
7 u. N: X8 |8 y) Y, O# M优点：
2 d' F/ ~  p& S1.可得到全局最优解
9 N9 w$ x, c: F% {* y2.可得到一族最优解
8 b* h% Q! G3 V  o7 X. B: Q, X3 Y3.可以利用经验提高解题效率
缺点：
" w" z5 x- W3 T- G1.没有统一的模型
% L6 ~( Y6 ]2 q2.用数值方法求解存在维数灾

0 Z& e% m0 j7 H3 Q' v( U, F, B目标规划（重点）
, S' J. G' Y4 O6 N9 D( j# b2 m
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
( q( O6 s: d  d7 H6 R+ W% `6 O4 V  |
+ z9 R# X0 d' e% m目标规划模型的建立

4 z  P& ^8 ~, u* H" D: l& F
; I# t# c, U& K  \4 J2 r6 r: g
% o  _9 O( Q6 D" n
引入偏差变量的概念
0 z7 O, V- P9 i! \
# M+ n4 U7 T$ z0 _


. [5 {. X- W6 _/ L8 l
  X9 s' t( K: L
7 d) g$ p: H# w# Q引入优先因子
6 E3 v' Y; {3 M9 a/ Y


目标规划的一般模型


/ h* k$ g9 i# c; j" h4 |+ j: g; J
# l' O0 g3 L8 z目标规划的求解方法

5 l) x% m5 U4 ^理论基础：序贯式算法
' F$ ^# H- C: e按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
' q. W) [) c% \. ?$ d/ S1 m
2 v2 j' R% `) v# d* J2 E! W. Q$ z0 Y规划算法的应用

- B% L- _6 |/ k8 K7 J* J* x2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

德古拉

Nice shot, thx for sharing