数学建模中的规划问题

杨利霞

数学建模中的规划问题
( @! u, ~) J& c, I+ `) i
/ e' d/ T0 c' E
) K9 _8 S" e- }7 a3 W*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
+ R9 T* Z. i! d0 o7 y6 a! y求解规划的基本方法
. x  u. ^' s; F# m  @9 i+ l* ?9 m*线性规划*
5 t  g& u+ P& T线性规划模型的建立
% N, x' Y! T: N3 d线性规划求解
. C% ~6 A, x% y# o- G*非线性规划*
*整数规划*
& V( Z, Q( H$ r' t' m整数规划的分类
整数规划的求解方法
+ b, D6 }1 ~6 U. c( x4 S( D特殊整数规划0-1规划
* g9 M( e/ i0 b- L动态规划（了解即可）
动态规划模型的基本原理
3 @8 l+ @4 S; X+ N3 N6 u% M动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
5 O% R; _% e/ p( W引入偏差变量的概念
引入优先因子
目标规划的一般模型
9 s( p* n) `8 ?$ w目标规划的求解方法
规划算法的应用
6 @, K# f' w. x+ }& [装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
( ]6 ]0 g. U4 Y4 F! z
规划的基本概念
. U. W8 M& {, @! }. F6 M( Q" A
, a1 h. x$ R; u规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
1 j+ l9 I2 O- k4 e' j. Y9 G0 ]
决策变量x，目标函数z，约束条件g(x)
0 \7 r; P( v. o" y2 H  C
" Q6 |3 ]# q: ~2 S$ q规划的分类方法（了解）

! o0 s! j: s# w4 u0 u! j3 u" B; D

! p! T, y9 D3 Y2 D, \- C8 P. @

3 f0 U5 H" K  v+ {  I, H1 O求解规划的基本方法

3 u1 N) l+ E/ j" h方法：在具体规划模型中会说明
3 t3 q! E1 E; B6 ]软件：Lingo Matlab
6 g5 `5 a  s" |8 f+ G9 z# H
线性规划
1 c# L5 U* I% l  P
线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立

0 v: e: b3 h( h* d4 o. e  r线性规划的标准化

! O, ]0 t7 \  E2 a目标函数标准化
; V3 K6 v6 q  o7 I2 f6 u约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
2 O5 H7 L: c" m8 f+ h
例如

0 h5 @0 C  X5 I4 H# d" P引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
( i  p$ |: n- N, s+ K8 V' ba1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

: t6 g# x5 r, |$ I添加限制
Xn+1>=0
Xn+2>=0
0 l, y! @6 Q, g+ h# ]; C

4.因此所有的线性规划都可以化成标准形式：
* m# g+ X0 I, o) v
' g& _! R$ r1 e
# n; A- Y' R' X4 \% G7 J/ A
线性规划求解

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

Lingo求解
( d, U% S  Q$ m
代码简单
& W8 ~3 Q4 b5 L. C" E结果易分析
不容易报错

大概就是这个样子
" d- m. Z* _2 O# X4 F5 PMatlab求解
) \$ x0 {" w) ]
4 M# T3 K4 b3 T, ]/ A; h/ l1 x; g其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
4 L5 |; O6 s/ d6 V, I
# y2 C" `9 A2 z, f4 Q: L
所有量需要化成矩阵形式，负责代码的同学自己去了解。

! b  U. `- K9 j7 x9 a+ F$ U7 R
非线性规划
, Z0 K# q. Q( F2 c% G0 C$ S' g
简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

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

整数规划

# S  Q0 i' T3 L* M决策变量为整数类型的规划。

整数规划的分类
6 L! y9 e/ F. W7 d8 O
9 I; Q. g: z3 v. o( I( M5 }
9 M0 u, G# r6 Q- |1 }- y
* H3 \& e# D7 o% W整数规划的求解方法

蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
. L5 |: t7 L" X! o# h) g- B
某整数规划题目的求解过程
. v0 J4 H2 f; }( x

2 o% q- J) d7 I: A: a4 p
特殊整数规划0-1规划

* M7 ^* |  k6 w4 b0 K即在整数规划的基础上增加一个限制条件 0<=x<=1
' O( x0 F! h: P; ~# K' `9 S
! f9 a/ A) b9 R3 {! Y
1 C: m' Q! f  d- y! }




  F9 k7 O8 w7 C8 a$ V( B动态规划（了解即可）
& a3 L1 Y* L- G4 D+ R
' v, r7 S* A5 y1 L简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

动态规划模型的基本原理

/ M: T( L: P/ `- p. Z( I) X( s最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

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

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

8 b' G  F3 u6 {2 C% a, x$ o动态规划的优缺点

优点：
4 A9 }) C7 K' g  |- p1.可得到全局最优解
2.可得到一族最优解
1 E$ \& r( F9 E3.可以利用经验提高解题效率
5 P. ?8 s& z1 N" }( G缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

8 A) W. V# o! O# x  c目标规划（重点）

目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
7 e5 ~: E. J( _9 j: Z5 D
目标规划模型的建立

' D, |& C- V6 G1 m

7 n( x9 z2 @( |: i6 A( v
$ p: \& A7 ~0 O% ~8 H9 }引入偏差变量的概念
. Y& _7 R- A* Z  G



0 m/ Z; k/ t/ {7 n) f+ y" b

引入优先因子


& u4 Y: U& F3 ~3 _& f) m
目标规划的一般模型

% L- r5 _/ b2 y3 `" u$ t
* f4 O6 k& w( [. n: ^& R' A' H! u
目标规划的求解方法

- W& ~) F* e" }) n理论基础：序贯式算法
" m0 f1 R( ~$ {7 G" u按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
- W- x& t3 h! [
规划算法的应用
0 J6 {3 |& a: E
" q. g/ j/ i0 B: v3 D( m8 Q2015国赛 太阳影长的问题
0 I7 Q" z6 E( ?9 J% v原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
* i! _% R& m0 [5 L( r

/ ?  J$ l- u; W0 \/ E  y# Z3 x

德古拉

Nice shot, thx for sharing