数学建模中的规划问题

杨利霞

数学建模中的规划问题
: [; f/ i) z: k

*规划算法综合概述*
- I5 s: Z: ]  y1 D9 j& s+ u( [5 {规划的基本概念
; c( l, R$ q6 u6 H0 A- u% J, m规划的分类方法（了解）
5 O. [$ U7 ^" ^; K6 b求解规划的基本方法
2 s$ c9 n$ O, Y% A: [*线性规划*
& h5 w: R) W! I3 n1 k% O9 l0 e线性规划模型的建立
6 P/ `5 e8 ?! `4 _1 H) V线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
% y0 }; n7 l' b3 k& Q' c整数规划的求解方法
/ J( Z- ^, e- Q! O7 d3 o特殊整数规划0-1规划
动态规划（了解即可）
: p$ X: ~# l5 h2 E动态规划模型的基本原理
动态规划的优缺点
  C6 }  p& L3 k9 M! G+ _" Q==目标规划（重点）==
$ X( M- J5 s- t+ r目标规划模型的建立
引入偏差变量的概念
, ]$ R8 k. \1 z9 e引入优先因子
- q0 R5 {' \: C' p2 T& B6 Q目标规划的一般模型
目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

. R9 F2 U) S: f9 A对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
, q0 n7 d( W7 J$ V+ F
规划的基本概念

8 x2 w* T% z0 u, }: {8 J4 D" z- ~5 {/ w规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
7 o& _  q' G  n# l8 O

决策变量x，目标函数z，约束条件g(x)
9 P& v. j# L( @; C$ @$ C4 R! G
规划的分类方法（了解）

$ J0 m6 x1 O" [
+ I5 [$ I) L0 `

求解规划的基本方法
9 |+ l9 y: d; p" H3 a1 t* W, e
+ y; U9 \9 |6 I5 |$ S& s4 {方法：在具体规划模型中会说明
9 H- A" s, s' c软件：Lingo Matlab

线性规划

线性规划即目标函数以及约束条件都是线性的规划。
$ G8 W, L# l0 z& v" q
线性规划模型的建立

线性规划的标准化
; T, n# c! \+ k$ K  i/ p
目标函数标准化
约束条件标准化
+ H; a( t! }7 h% c$ J9 Y决策变量的标准化
! q. h/ s+ T5 ^4 a1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
8 y0 |1 Y) @: a
, w% S/ ]( J& \& ?2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
- S2 R: a: K$ D0 B/ J& s& }9 Y
例如
! u# S- y! {3 I* Q& c9 Z9 |
! X* W/ I  g8 K! K& J+ J& ^; H, `+ s1 T引入松弛变量 Xn+1,Xn+2
6 f" t3 d, {  l! I
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
+ r5 C) c+ K  l  [5 V; UXn+1>=0
8 t& o* O3 t1 Q6 J: QXn+2>=0

4.因此所有的线性规划都可以化成标准形式：
9 m3 n! h  K, I/ \5 R2 v: O- h% l  r
) ^3 k4 g* O, f: b" L! x

线性规划求解

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

Lingo求解
6 v1 x7 n* c1 P0 s
0 {3 R! h7 w& ~8 A1 T* R. k0 L& h代码简单
结果易分析
不容易报错
" F3 m4 ^% n% b) Z! B

& V; q% Z7 V7 a: P- D大概就是这个样子
Matlab求解

) Q. _! N% m* A5 g# P& v( O' o其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

所有量需要化成矩阵形式，负责代码的同学自己去了解。
. ]$ D; _. F0 h/ h
# A  n  F5 T, n* g6 O
非线性规划

3 h, X( z0 w8 k5 U+ o简单说就是目标函数和约束条件至少有一个是非线性的规划。

* L; U" o" [3 {Matlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
; P; ?5 M; Q, a* ]
; i  C* K7 ^3 n3 r0 x整数规划

决策变量为整数类型的规划。
, Y; K5 S: Y7 a8 Y# E
: v' W) D( h6 F: B* [整数规划的分类
9 v" H3 U3 G3 R8 |8 Q
- A, `- j# A6 x" Q

; q! C0 N: y+ U
整数规划的求解方法

+ Q* f2 j  C, r* A蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程

+ |$ h  s( ^" h$ T9 l. @' i5 D

9 o% b* r5 [( ~- e% m' A+ C特殊整数规划0-1规划

即在整数规划的基础上增加一个限制条件 0<=x<=1
+ J4 u/ Y9 C# k% y% w! J3 ^

! k- u6 e) G; i' m# ^" {9 r

* @+ g2 H- S7 r) z

8 ^- ~, ^$ v* F! G6 e$ D动态规划（了解即可）

$ D+ r  R5 [/ R# M1 ]$ V: v简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
) J- ^" g7 A2 w3 M: P3 U" ]
动态规划模型的基本原理

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

8 O3 H* ^' P% X贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
3 q8 V' ~, N* y, n
. Y! t( B9 @5 K( d, ]! P" U& A; a逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

9 {% J" j) g/ d) R动态规划的优缺点
% r  E; F* m6 |' D. k
优点：
( M+ ]7 u/ ]! j) L. ?* p! I: n1.可得到全局最优解
1 ^2 T; E0 ^3 L( I2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
. w1 d" i, a3 a3 I2.用数值方法求解存在维数灾
# j) A/ D  `) s  u
. X- y- S' m" p0 z( }5 [目标规划（重点）

/ H) c$ x# D" O+ S; L3 e1 M目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

. i9 w% B2 S- a) x1 W; N- C. E9 L# F目标规划模型的建立
1 q" m1 d: h% f8 u

$ }' u: A7 ~6 X" w* u
1 {, I9 K5 z$ E- ]/ t& O

6 {, I1 `# y: A1 w9 x引入偏差变量的概念

6 X$ M6 g1 `. w

, B8 K2 o; K) m9 h

( K- \4 h  Y! }* x

引入优先因子
4 o) s: d; [9 U* q9 t; N, t
; q2 `1 \" H! j! d( I3 `

目标规划的一般模型


* P" i$ w  Y, `4 P2 A! q2 Y! w1 C
; q& I! y4 Q- l: n! F0 t9 Y9 c目标规划的求解方法
# {8 X; c3 |+ Q& e1 p
' {. v# q% B$ s5 b% l理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
( s- Y6 S8 t* Q+ \- Z. G0 T+ X
# k" ~% N) i6 k$ b9 |, d规划算法的应用
& N) h+ ?$ S% z4 @. n! c
2015国赛 太阳影长的问题
- a9 O+ e( M) J原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
1 Q* O" {" K" Q2 M3 D- w

德古拉

Nice shot, thx for sharing
& s; u! u# a: W5 t* K# a# z