数学建模中的规划问题

杨利霞

数学建模中的规划问题

2 ^) p. t! T+ _# m5 @
, l/ R/ _: T; ]. C; {9 M5 @5 E1 J*规划算法综合概述*
规划的基本概念
) p: e, w) o( q4 O规划的分类方法（了解）
求解规划的基本方法
, _, p. |7 Y, O! I( {*线性规划*
& N& a( B7 u# `线性规划模型的建立
线性规划求解
*非线性规划*
*整数规划*
整数规划的分类
, b. x9 S5 x3 j% ?, F整数规划的求解方法
% `$ P- w2 ]+ x0 i( s/ W. {! m特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
0 ~. T" |% j3 L8 x- {0 P* h; g* i- M动态规划的优缺点
==目标规划（重点）==
; ~- V# {2 o, ?1 V- G. e" U目标规划模型的建立
引入偏差变量的概念
6 b3 j- ]3 g) s+ ]( ]9 l& q5 m引入优先因子
目标规划的一般模型
7 y) }% q5 G" |4 r. r  S9 c目标规划的求解方法
规划算法的应用
2 r) v1 @9 O" W/ B  Q. F装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

: m5 r0 m1 V* x" t  l5 J对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
% t5 \1 T0 a  _- s. x: A5 u  u
规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

+ f: L& ]/ M- `, w( |, r决策变量x，目标函数z，约束条件g(x)
" y; b$ D4 v6 B& X* y8 v
规划的分类方法（了解）





0 n$ [+ ~& V$ ^$ F/ O- Q- R4 ?* W求解规划的基本方法
  l) P  K8 [+ H$ M/ y
方法：在具体规划模型中会说明
软件：Lingo Matlab

. R. t; R3 f8 n% t8 U8 C线性规划
5 W5 p9 E+ n* s1 ?' Q, ?( t
线性规划即目标函数以及约束条件都是线性的规划。
. G: x7 h. a7 F" l% U
线性规划模型的建立

; |- V& `% m! N0 c, A5 x  Q" \线性规划的标准化

- R( U# a, Y0 `9 I' P目标函数标准化
0 t1 @/ ]% t! z1 @" u1 A约束条件标准化
决策变量的标准化
2 C+ l# ?* z8 j6 _& c1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
2 @# Y% X2 ]* j
4 t7 A* l3 [8 Z  z2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
. \; a& V% J( t3 S# W  ^7 h3 d' }
+ g( Y1 I" o2 ^# C$ c# O/ u2 ]5 Y例如

' Q4 j& E  l) U! ~2 s$ }+ w. t: q引入松弛变量 Xn+1,Xn+2

7 R1 N" y- Z% `+ x8 b5 R  Aa1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
& f3 n6 ^8 D7 [8 ]( Ya1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

, D! [; {, O3 o# f9 p. [: ^( C添加限制
Xn+1>=0
Xn+2>=0
* V) U! T& _; i# A4 i2 Z) w& {
3 \' z) K# L8 K2 {; C2 s5 a' S, \& N
; J' t' h% Y5 ^  U" L4 Z  [8 f4.因此所有的线性规划都可以化成标准形式：
! j/ p; {" P, s+ q9 Q, c6 R


  l/ z) @) J  |7 Z% S/ G3 p- Q线性规划求解

; M- A# S+ Q: I/ S2 m; `% G5 I理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
  p# t+ k- N% t% H
代码简单
1 Y9 I. l3 ^" z结果易分析
不容易报错

# L. O1 g, P( P7 l# I! C0 F1 @  @大概就是这个样子
1 \: a' `3 }5 S; a; ZMatlab求解

其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

' q* t4 \4 u" M  X5 s# V6 E$ i" N
所有量需要化成矩阵形式，负责代码的同学自己去了解。


' H  [: ~4 z5 Q3 d: Z# A非线性规划

8 V. p( O' X  T5 t6 n简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式
$ k5 R: ]/ {" ~' k4 s3 s
- q' T* H6 h* l* r5 h8 L& o* m从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
: `: }( a2 \4 G5 X; _- k1 L' e9 m4 `总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
+ r8 w2 A  Q- x, a5 `' P
- h6 y* m7 k0 w4 F( \& X整数规划
( ~& X: J9 D& G& E( x$ j  I: e
  M, s4 y" l7 n# H% w- A决策变量为整数类型的规划。
8 Y8 |1 Q9 _9 t9 l: U  G+ Z
) d, L- K. x" Y( ^6 R4 f8 z整数规划的分类
( p* I: D, R" d
0 {( a) `+ k9 ^
4 U8 U( q) O4 y, H6 x2 @3 f' l
/ P9 V5 K+ V( o* l% j3 f整数规划的求解方法

蒙特卡洛算法
: x# l+ I+ h6 Z% V: @1 s/ p5 a& T蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
0 f5 x; U" q4 z8 I
某整数规划题目的求解过程

+ Y* ^2 \) T; u7 G

特殊整数规划0-1规划
6 e: G( [3 v# _% B3 e6 e
即在整数规划的基础上增加一个限制条件 0<=x<=1
* Z( c7 A- ~) h/ ?) \1 [

) j5 ~8 F6 K- [



2 c. x% |, Y/ T
- E) z' L" d1 v1 o2 H动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
* B/ Y8 _6 a+ M  u" H
+ O" s' E) p/ s: O* i+ j% Q" J9 o动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
2 |/ b% Z4 g) [3 @4 R) W
- J3 ~. w7 A  k5 F: ]' f. k) {$ ]贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
: f- U0 [1 s! s3 z2 h& w# a
* S- a! S( _' Q7 I4 Z3 H逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
! @" Q: K9 M" q) n
动态规划的优缺点

优点：
" ^9 L" b# c8 c# t- f# H( C1.可得到全局最优解
. u8 z& G6 R0 f: w2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
" F/ n( @- {) g+ }; N1.没有统一的模型
- J( D2 u* o/ I- ~+ z$ i2.用数值方法求解存在维数灾
5 z0 F4 M- ~$ m+ \4 y) H$ ?
目标规划（重点）
3 d* L! w3 {) F$ \+ O5 G/ I) ?
目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

5 i+ _3 }% V2 g  l目标规划模型的建立
' s( j: A3 X2 L
! h$ p# @- L- o% m$ ]) b

+ o7 w% c7 V( ^& M) V. S* }1 ]
% Z5 G* l- T* {1 S3 w0 @引入偏差变量的概念

* f0 q! d8 ~) Z; J$ s% v
1 e2 [# U/ R1 W  q! J  o" H

. `7 |( E! O0 ?7 ^
2 X. o. G3 S3 z0 v! w/ t# e' r
引入优先因子
- |2 q  q' V, s" a$ b4 b
) D7 q+ n5 |& a( D
* s2 V, H- j  I
目标规划的一般模型
1 B3 Q; z1 [; t( N
1 o3 z8 S" o$ x* D4 L
( N: ^8 m0 o# G9 J$ M: z
目标规划的求解方法

理论基础：序贯式算法
1 Y& Z: c$ {. P0 q" D按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用
( r* L; f0 `  o+ S
' ~, ?9 o3 o' S. V) `* l# [2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

6 q) ]' Y/ y4 E1 l5 \6 R
" W% b% m/ e9 \4 k, e: Y' n$ s; ]/ N

德古拉

Nice shot, thx for sharing