数学建模中的规划问题

杨利霞

数学建模中的规划问题
! ?; L; @2 |9 s- Y5 \# Q
* p& I, w" G" T$ a1 v) d; m
*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
, W- O5 q1 z  r/ R) N8 B*线性规划*
线性规划模型的建立
线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
8 r* Q$ a# i: F; n7 D9 d  |整数规划的求解方法
0 U  c) l$ G3 t9 s" K7 u- x1 `特殊整数规划0-1规划
动态规划（了解即可）
) i3 W5 p7 N7 }, _8 D动态规划模型的基本原理
" b  Z$ c% V0 S& R3 a7 A动态规划的优缺点
==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
引入优先因子
目标规划的一般模型
; ?2 A) G* E$ E. X5 w+ w4 ?目标规划的求解方法
+ U$ F0 ^) d. L$ n6 a, I3 M( U! T: {, F规划算法的应用
; h6 W# J+ Z5 D, P3 P  c; S1 z装了半天数学公式编辑器，没装好，见谅。

! X' U8 J9 s: _4 N# r9 L规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

7 p, U. {9 T. U6 b1 `决策变量x，目标函数z，约束条件g(x)
9 ^" a! \8 M/ r: E9 ~
规划的分类方法（了解）





求解规划的基本方法

方法：在具体规划模型中会说明
/ e  {( H+ Z8 x( r7 i5 g( ~软件：Lingo Matlab

% A# C6 N+ ~& ?2 G( T9 B+ U! c线性规划

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

线性规划模型的建立

线性规划的标准化

% v5 Z% n( f! W# u9 ^8 Y目标函数标准化
约束条件标准化
. o1 A- ?( H- [9 i4 s$ S% k+ s$ _决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
3 p& t% i" Z- G1 O4 [
; U0 c0 N% c+ w# o4 N2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如
/ n4 a6 d3 ]: y2 p
8 s7 L* g4 q' E- Q1 q; f引入松弛变量 Xn+1,Xn+2

a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
) H) `& {! d% J" l8 Y  f6 l
' k2 @& C8 ]: p: N) i( l添加限制
Xn+1>=0
1 s2 c  }: p! Y% ~Xn+2>=0


: }3 K6 T" @: }& v1 g1 v# M' X4.因此所有的线性规划都可以化成标准形式：
+ ^1 f! K1 P3 q
5 O4 x. n- w) @. e1 T7 z4 y

线性规划求解
$ U* N! f* y7 T7 l( N/ l
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解

0 f2 {5 X# _) @$ \. S代码简单
& P% \/ n9 J0 b' p7 Q结果易分析
: [+ @# \/ S! |; v% j5 ~% K6 z不容易报错

9 L+ W% W% A# c" V- Q大概就是这个样子
Matlab求解

3 W! T1 D# l$ z1 z5 c! D$ I其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
+ t9 ]8 w; x0 I; J

; y! K( n! y- u3 `  F& _# h所有量需要化成矩阵形式，负责代码的同学自己去了解。

  u0 d' T9 V* ?6 e1 r3 Z8 U) u
非线性规划
& k$ T/ l( x+ K% N% v* K
简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式

! l% q& j- K! s6 w# B- y0 p* d( s从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
, ~4 |9 C- y: w总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

: m9 x7 |. v, x4 \5 K; `整数规划

- ]) Y; x1 y: q决策变量为整数类型的规划。
+ @4 v; }5 y" [* k; h
/ }+ [8 q4 h/ J+ a3 w6 a% y: o! d整数规划的分类


" P# K. \+ A, E  u/ f1 y6 l
) L9 _. {, z, V2 `8 R; r整数规划的求解方法
9 S5 I- s: U# u1 o  u; x9 G0 c
2 @8 g+ j1 t' Z7 |! q& C" i; e2 O蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
0 L( T- w% _9 Q! X8 K+ d; |; a
( f: h; D4 S3 c某整数规划题目的求解过程

. y% g: n0 t; p; H7 k
' G7 ]! F. _1 U% h
9 N% P6 L% u/ k# C特殊整数规划0-1规划

4 i; ^) J' S" g& ~即在整数规划的基础上增加一个限制条件 0<=x<=1
$ W' y2 f& P1 r% i/ O7 E" f8 j
) Y/ F; l# B( C/ \; e0 k
: I! _. g* a1 X
& A4 T' m+ d# Z; v( V

3 ?* w- H1 @! e% \: M7 h5 I

动态规划（了解即可）
# b0 I9 B+ V( {4 N
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
8 \" \4 E; L" A9 E  Z
动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
( ~1 O3 Y0 ?/ d* L* E- t  ^+ o2 G
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
, S$ j$ T8 k! I. a& a4 t# M' }
% @) p  O- Y( U逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

动态规划的优缺点

优点：
  }9 G. H3 G+ @& ~8 S( R# R1.可得到全局最优解
. ]1 G2 g( H8 E. ]2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2 C3 n( D. t# `5 W) M2.用数值方法求解存在维数灾
, e; q9 u2 ^2 t- }- c
7 T! y$ k& i  C0 I5 y3 {% D目标规划（重点）
' P) L$ {8 _* `- |
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
% d+ d3 l4 o1 i5 K/ z0 R
目标规划模型的建立




引入偏差变量的概念



* s3 H) a* Y' M


引入优先因子
; @/ E  c) K# M9 a8 h; d. y

. B: q. z0 T! _8 m
目标规划的一般模型



目标规划的求解方法
+ s& K" r' `: h6 e4 v6 |- o
理论基础：序贯式算法
1 V, ~2 V: I0 y0 f9 q0 q按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
0 [% X6 a; ~/ e0 W5 w& {: V7 E' N
- j7 w7 }; ^  E& L* _: o6 A2015国赛 太阳影长的问题
+ A+ Z1 n1 n& g" g原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
7 D* k! i' L& P# F  \
# K9 E: t& Z. {: |- R3 s) _
; [1 S! O4 z0 a( s; W" `

德古拉

Nice shot, thx for sharing
6 V, m* q) m( I+ q/ z: W