数学建模中的规划问题

杨利霞

数学建模中的规划问题
$ n. I: F3 B' K! a, b) R2 e+ ?4 w

*规划算法综合概述*
规划的基本概念
! K% k" S7 G0 N/ [4 j' l4 D- @- B规划的分类方法（了解）
" P& Y4 S$ ^) L求解规划的基本方法
*线性规划*
线性规划模型的建立
线性规划求解
* ]0 j* a8 R2 x- u3 {*非线性规划*
. U# a! v" ?! T- }' T  g4 {# w3 I*整数规划*
$ Z% P2 G# X+ l9 q整数规划的分类
整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
$ D4 D8 A6 X2 J4 ?  M6 C2 E动态规划模型的基本原理
: O; h8 P! H) n/ E: T动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
1 f' J1 e1 _, Q0 r# b; l9 l引入偏差变量的概念
. _* A# n6 r3 r' s2 f& H( C引入优先因子
目标规划的一般模型
目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
$ _' Z1 T( |. R- [# J
/ k0 f6 ]! t4 y. L! D# |/ G对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
" W" y2 C, }/ b8 ~: h3 ~3 k+ `
+ h4 e/ r5 ~% q. w规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
) b0 x' u0 |. p2 J: m. K# y8 U" y
! Q4 V7 C/ }* u% G- _0 Y, I决策变量x，目标函数z，约束条件g(x)

7 t7 c# O# `5 B" ~+ Z规划的分类方法（了解）
$ _4 V0 `6 P3 s+ i& E
, _( q0 \7 n7 o
5 ~/ f; u# F: w! r6 l  l1 V, p5 C

! G: K2 E# y% Y( t1 J
' k. E; Y$ X% F6 K' ~, I0 i- ?1 v求解规划的基本方法
" ]% G7 k' e5 s
- S# i0 z! o+ ^方法：在具体规划模型中会说明
软件：Lingo Matlab

线性规划
# t* ^5 Z, P# \$ \. Q7 }
线性规划即目标函数以及约束条件都是线性的规划。
2 G1 ?2 K" s# Y
- k0 n1 x: x% v& B线性规划模型的建立
4 f2 E8 r9 J) o+ u4 J" W
线性规划的标准化
$ K' `+ j9 G' Y7 L
& |9 f7 d, B3 `+ Y) }: \目标函数标准化
- G1 e; }" l& L" d  D; e, T( m约束条件标准化
; T0 Y6 r$ U& F, h# ?7 c$ z. w) M+ p/ u决策变量的标准化
& }9 s- b3 A! L1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
: G- M, x4 n% l6 B  Z
( g5 e2 R" ?1 g2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
$ @# i6 O$ w$ t% s6 T) s
例如
8 x- c( F$ y0 c* y4 {% V0 T2 r
3 ?, J" _+ y$ o* \引入松弛变量 Xn+1,Xn+2
  V. C9 o+ W& V+ Q7 J: l6 M
9 E% r  R! E# _- t% c' g. n9 Sa1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
$ \1 P( m1 @+ h4 b1 i+ fa1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
7 |! H' W& @; P* u
添加限制
( R2 ?0 U; p: A! H6 ]Xn+1>=0
Xn+2>=0
4 E" p+ h: @: I

4.因此所有的线性规划都可以化成标准形式：



线性规划求解

5 V; X5 E: {2 X/ w. f" w% w理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

. H2 f7 m- R& ~7 c: X( i. A1 GLingo求解
  I# A/ I3 G+ _# E+ B- R0 M
代码简单
结果易分析
4 Z6 i6 Q9 F1 b9 C不容易报错
$ u' K# l; }" x
/ j: I! Z. p2 b$ E大概就是这个样子
# \5 c- b. [) X- ZMatlab求解
9 b: P8 k2 s" V6 }3 D* ]
4 k' t0 L" L, ^* F: m% ?其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。


9 P, x8 Y) ~! W所有量需要化成矩阵形式，负责代码的同学自己去了解。
0 e+ D, Y- l- ^& u/ a* z* P

非线性规划
, G1 _: m' K0 I" g. T( I! b; A+ S3 i( ]6 N
0 H/ q# H- B) Y) j0 N简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式
& d$ l9 p% D, P' K: b' @
( c% A  U' ]* {9 E# d2 a从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划

4 a; s- n! I4 ~4 e0 T决策变量为整数类型的规划。

' z% x: u6 Z1 v整数规划的分类



( P) b; Q* w+ s8 ?4 U- }整数规划的求解方法
& S* J; T4 f, m! Q, D7 C
  t- S8 o6 X5 ?; l! H蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
7 g% X% x( S: ^/ p* W: R' v  v0 U
某整数规划题目的求解过程
' D! ~1 _% q9 X: a6 N- p
; r$ V6 o. ?/ _7 q7 Q4 d  V& N3 P' W

3 E4 u% j' H: r, H' ?' ~- I特殊整数规划0-1规划
. [* c9 A) D0 p3 a% l
3 P/ [9 H2 _9 B. [: X即在整数规划的基础上增加一个限制条件 0<=x<=1



: \2 w& |& g. W: G) h& z( k
" ?, ^! y; j2 t( [7 T9 ~+ q8 Q; V
( d0 ^- s1 W, e

* W+ ~/ T  U/ O动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

动态规划模型的基本原理
+ F+ A/ Q& C5 y0 b+ R3 N
最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

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

逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
' L2 w/ l! l: A
动态规划的优缺点
3 l2 G6 C7 d4 j2 T$ t4 k
优点：
* C* i7 [! h! k! u1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
  [/ l: n  v, I" i3 o1.没有统一的模型
2.用数值方法求解存在维数灾
" `( W) b- l& f& K8 [/ h& H' v
; x) _: \: k6 G2 I( P9 D& t目标规划（重点）
5 \/ H& Z% {' B8 L& k+ {- L
6 I4 b" }4 n8 ~1 q0 l4 s9 v( h8 S目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

& F( i5 y0 \$ ^& c* e目标规划模型的建立

. M8 Q# m/ \) T$ _
, L1 k" ?7 j8 l) ?3 L4 b

) I; I/ \( B2 k  M# k* Z" J! T引入偏差变量的概念
( h9 U% R. K0 i$ I  M



& O0 g, ^) B' p' e' G( g& I. T
. _1 z6 |2 Z/ @- f. P% I4 m
2 ^# |( i! H; I3 m& ]5 B0 ^7 @/ b引入优先因子
% |5 u$ o5 P( T9 Z# u, u
% e* _' Z2 ]4 E! I, l& \

" T+ e# f6 u$ z$ G# V" ~1 f目标规划的一般模型

  G5 s' X& r6 e9 N. h
' P9 b' t2 l! u8 W! B1 K  J
$ h! O7 I2 g, n目标规划的求解方法
9 l& a8 J6 O7 d, J$ e0 u& |
理论基础：序贯式算法
% _5 w1 ]9 w6 y/ V$ X3 _( S' e按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

) ~8 R7 p" ?& r. n( k规划算法的应用
, s7 Z! `$ g; f; ]6 \
# V6 B% b- W* U8 g/ b2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

德古拉

Nice shot, thx for sharing
* u) s( @  }9 U  V* u7 X- i