数学建模中的规划问题

杨利霞

数学建模中的规划问题

: _5 O: P) M: z& z8 U* Y
3 [1 B+ p& L' l1 V+ O/ p/ R  T*规划算法综合概述*
规划的基本概念
# P8 a; V& K- v* o. }% K规划的分类方法（了解）
5 o/ n, T7 n! H9 t8 \$ G* ?求解规划的基本方法
: ~, Y- b2 V' H5 s' I5 r*线性规划*
+ ~4 {. h- B7 M2 O1 ?- W线性规划模型的建立
线性规划求解
*非线性规划*
*整数规划*
  W( i1 r& i9 \1 Y整数规划的分类
整数规划的求解方法
  n7 |2 D# y( l8 O1 V特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
' A( k/ |8 x2 D+ c' W' m$ t  T! ?==目标规划（重点）==
  D) x6 c0 c% ~. q' u8 E( F+ V目标规划模型的建立
引入偏差变量的概念
引入优先因子
; T  j& I( h5 ]: n/ ^$ d" O目标规划的一般模型
目标规划的求解方法
7 d& `; b8 K; a! A  X8 P规划算法的应用
8 N6 p, m, U& i. B装了半天数学公式编辑器，没装好，见谅。

% i& P1 I9 l/ z. w3 O+ r规划算法综合概述
9 W( \8 Z1 c8 x8 B/ Y3 D' n  w
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
/ r# `& G+ N) F7 ?" j
5 k- D7 t$ x" R2 F+ F规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
9 S5 m7 B$ ~/ z2 ^( a  S+ O
决策变量x，目标函数z，约束条件g(x)
, J0 }% _! r1 p  ]
规划的分类方法（了解）





' k# o  U1 e# I( A5 Q7 A求解规划的基本方法

8 u6 P! {/ ^0 b* l' G9 d方法：在具体规划模型中会说明
软件：Lingo Matlab

线性规划

& u6 ]  U6 T/ A9 Y0 S5 P- Y线性规划即目标函数以及约束条件都是线性的规划。
* B" i. d, ?( m# x- o3 \/ Y
+ e* s' l4 Q* q& N3 a5 M* i线性规划模型的建立

* Z8 B- D# K( R- w& U, h% Y线性规划的标准化
  g4 Q2 q' y0 G6 ^2 d
; A" i, u4 H! p目标函数标准化
约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
' A% z5 o& D8 ^) U; @9 X' _  }
/ y, s$ I/ y; L2 o( c1 @( s1 D2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
+ t1 S+ U8 V2 m6 ~+ C' |
例如

5 M' g9 P, P  s引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
" p. [9 Z( g" b5 X' i& ^a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
3 V# U1 W0 _& Q; i0 T5 `/ l
添加限制
Xn+1>=0
Xn+2>=0
, Q  [% e/ ?1 k& N, Z' s

' W2 s( O* P/ T  G9 a: `4.因此所有的线性规划都可以化成标准形式：
/ x2 d9 m* \5 m$ O

  O" B. m1 G/ j5 T' h
线性规划求解

+ j2 U: x/ X- B, _0 I& L) m理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
: @: d4 z' f9 l/ b9 A  h* S6 T
; ^* e% D8 |5 t. V% }Lingo求解
+ h& ^7 A/ `! N) D
$ o. j/ ?- g# O; \3 c8 G9 {- n代码简单
结果易分析
不容易报错
( U7 M% v8 `/ f. z8 n2 ], K
大概就是这个样子
Matlab求解
0 Q1 H+ Z& J$ ]+ n( _6 J% l( Z2 ~
  L" a. J6 _/ u其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
& ~+ g9 h8 e; ?7 |) f3 H& ~+ Y
* D7 `; \4 x# j
所有量需要化成矩阵形式，负责代码的同学自己去了解。
1 N4 D8 F' F2 j( J1 b/ X% ~! C' A

非线性规划
* T* c9 ?2 |3 ?8 A' t
简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

; f. ?- ^& e+ w0 n, n( M+ J从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

: i* ^5 U# X) ~- }/ R+ D整数规划
3 n$ l* G8 X2 F; N- {
决策变量为整数类型的规划。

; t& x+ g# ?; D* e! W0 A+ K整数规划的分类


6 Z  w1 \& o% h; k9 @2 ?
! q" t4 U8 G& A4 L# u! j整数规划的求解方法
) e7 N, K0 z+ I+ w5 l  x
蒙特卡洛算法
( e5 r! V8 v5 U; P. {$ ]+ Q$ \蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程
! _0 Q9 i7 u& m- {
) Z9 v+ K' T6 y) M

特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
: q4 V5 G) T+ m5 g- q" ?






动态规划（了解即可）

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

) h4 r- O" ?/ O" B动态规划模型的基本原理

7 f7 I) x6 T! B5 O, U: k5 o最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
+ D& E7 {  j' f* R7 P+ |  J
7 D& ]* S9 i6 E贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

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

0 f7 Z, d6 @, a# ]动态规划的优缺点
3 j7 ?$ {( {' x6 A1 S# T
优点：
) s) A- R9 j1 h2 Y" g: ]1.可得到全局最优解
7 H4 F/ V9 t( _; n( j! Z2.可得到一族最优解
3.可以利用经验提高解题效率
4 f. {- U: p! I: a缺点：
1.没有统一的模型
, _2 h9 b  Y, n+ u7 t- [2.用数值方法求解存在维数灾

6 b  k7 n' k5 r, D, p目标规划（重点）
4 k& P; ]" I& h0 A2 v. t& ?: `
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

$ X' i$ [( q5 w+ y  u目标规划模型的建立


: p6 E- I* D5 {0 z

5 v/ i+ A' C$ ~# _) u" L引入偏差变量的概念
# D: g: R/ h+ O6 D6 d) x





5 q' r8 I5 U* D0 _引入优先因子
) {$ |) u  M! B# n$ [


4 E) A5 h1 V* g% {& W# I; z目标规划的一般模型
8 \, x+ H- K6 h1 k5 x  ]
! r$ l; h* o' k$ ~  h% g6 i! G

目标规划的求解方法

理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
: \/ j3 ^# w- y4 v6 ~
2 O" M- O9 e7 t. T4 R* U2015国赛 太阳影长的问题
% x0 W& N/ E! _5 f原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
$ b' G& _% N, J) R

德古拉

Nice shot, thx for sharing
; V% O( Y9 d' |3 D