数学建模中的规划问题

杨利霞

数学建模中的规划问题

: P7 ^/ l* D4 k- S/ _( @7 t: h- o: }
  L3 j' G6 H, N: l*规划算法综合概述*
3 p8 j; x$ g, [% e8 s" n7 e! J规划的基本概念
" p+ s4 W/ _! P规划的分类方法（了解）
5 V  n: }- O* m6 y求解规划的基本方法
*线性规划*
; p5 Z& n& V4 C% q" J* f( C线性规划模型的建立
线性规划求解
: a; h8 x' p5 S7 E  h" w4 M*非线性规划*
*整数规划*
. y+ s; t: Y. u% f5 W$ m整数规划的分类
' m* w( w& R5 k. x整数规划的求解方法
# @. g6 v8 B5 N9 P8 G3 Y' ]9 M* x特殊整数规划0-1规划
动态规划（了解即可）
- p' c' g1 h+ q8 @6 D0 u; S- F# [动态规划模型的基本原理
. h. A) q; a4 n0 [  b/ C9 _; ~. @- {动态规划的优缺点
1 b/ A; B8 R7 x==目标规划（重点）==
目标规划模型的建立
& B  S5 z; j) W! U7 k( X引入偏差变量的概念
引入优先因子
$ O5 s- W. d8 J0 f9 M目标规划的一般模型
目标规划的求解方法
规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

1 ]" k6 s- ^3 B- W  |. m6 q- {: }对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念
1 i2 T2 [: {# J$ v
; o. m2 C" x. `& |规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
% U! P) d/ d; U; z3 `5 _4 L4 A; Q8 m
" s9 R* Z5 |3 B) r7 w决策变量x，目标函数z，约束条件g(x)

, R# O0 W0 L/ }3 _规划的分类方法（了解）

6 {+ v8 N, M/ q! a7 N



6 c9 ?8 P$ J; R! I' \. B求解规划的基本方法
) F5 g( A  E$ R3 Q
# F. r5 s: h4 Q. _  K- y' Z( U2 X$ q方法：在具体规划模型中会说明
2 P+ Z" B, }# B' G+ y9 Q  Y软件：Lingo Matlab

线性规划

+ E0 d* l' A# x; o4 l# `  P线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立

- c7 Z. d) Q' k, O. U线性规划的标准化

目标函数标准化
约束条件标准化
: O2 S& G6 f8 ~" i5 m1 X决策变量的标准化
0 s5 Z4 q( Z: V$ b' y! Z1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

, U4 T( c4 @6 s1 T8 l! v2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

例如

引入松弛变量 Xn+1,Xn+2
. ~4 ^/ w) w% o  ^- H
a1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
& W5 C6 v- }* S1 B+ ^3 I1 ^) Ba1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
- D+ J$ x+ s' P8 Y# G3 S' c/ L* Z
+ r# z1 z) x0 j" }- j$ W添加限制
3 v  c" {2 J6 p# wXn+1>=0
Xn+2>=0


  |4 x5 n( W4 m- [+ N% B3 b. E5 y4.因此所有的线性规划都可以化成标准形式：
8 U) Y" p1 {* x) g3 z4 [& K* H

7 |# x6 r  t) C; f: _
线性规划求解
, x2 i- X9 g6 y
- |4 r$ Z7 Y/ \- P7 v理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
  Q6 e) h: F' M
& p: e/ N8 U( ^5 e; z0 wLingo求解
6 ~) F& r8 W6 f( [5 R
9 [/ `& K3 s" Y8 B+ S, k7 ~$ ~# e代码简单
结果易分析
- R7 H% g; F6 }' A& X  F不容易报错

大概就是这个样子
5 A) Y# y) Q. ~' `$ vMatlab求解
& ], Q/ Q- Z' `0 A2 K
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

! T9 y5 W9 p* o& x' M! P2 w5 G
所有量需要化成矩阵形式，负责代码的同学自己去了解。
6 C( p1 h8 y" k  U/ z( Q: }
0 A" ?- v" e' V3 _% v/ H
非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。
- V  P) N0 d$ w; j& ^" c$ k/ z% W
Matlab形式

: P  G# D6 B% {. s: t, f从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

) z& I- P, B6 |7 c' A, T整数规划
+ N% I& j+ J7 q3 M
决策变量为整数类型的规划。
  X0 T( k& U7 H9 |0 t! ~
! v3 b( w, A9 a# p, s$ y5 ?整数规划的分类
1 O+ k* X; y. p& t* j* q; W; l


整数规划的求解方法
1 q4 _7 P) \! @  p' c7 E* t
蒙特卡洛算法
) j. a$ N- v' N8 ?蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
% m/ ~  R9 S% C5 |( T$ u. W
  H% {6 ]# k7 S某整数规划题目的求解过程


/ K1 s( D+ D: i& L
6 }+ d9 A' L, e# h8 {/ F8 Q" M特殊整数规划0-1规划

" W! p) i: d1 g即在整数规划的基础上增加一个限制条件 0<=x<=1

1 f# \* T" K8 i1 p) K
( s8 R! K4 W: f' F$ b- P

" G3 [  }7 d. d1 R1 B
1 Q6 V6 J: ]- i

: }' z+ h7 Z7 i5 B动态规划（了解即可）
/ V% I8 {' ^5 J9 Q/ h  ]
! b: l1 x  o# q9 n. o9 H" U3 o简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
: O, s4 U( q- Q! U1 h  W2 t0 w
" N  R' p2 H3 x. A7 \  e; @( ^动态规划模型的基本原理
, V) K' H' O1 S7 s3 G2 F0 K
5 Z+ m# [6 i% Z6 P, E* B( z" R6 P最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
' E4 j2 s8 E9 f4 D5 j
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
# R4 m; {- j2 E' H! X- s
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

( M4 v& z3 l9 y5 C动态规划的优缺点
( `) b+ O% [' p
优点：
1.可得到全局最优解
2.可得到一族最优解
- K! j8 }( [/ |" r3.可以利用经验提高解题效率
缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾
8 c* ?' }2 Z  E& j5 G, c
目标规划（重点）

/ g; j  l+ f4 O1 M- I, X& `! l目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

, [& k* I. [4 I5 x. Y目标规划模型的建立
9 G/ u0 C. Q' m! b% e$ }' |

  M8 E0 h: v' z$ E& t

$ @, [$ v8 s1 g, o引入偏差变量的概念




4 I9 ?" [. ^- g0 C3 p% h

  |1 u; R2 B3 N% `5 K% F% S引入优先因子
2 I3 X" O6 q* x

0 Z% D. a8 o1 D
目标规划的一般模型
' B' w/ e, ~2 }; M0 o  j; A9 g
+ k  G+ b. |3 d5 u6 J. O: L

目标规划的求解方法
; }7 k5 g7 d- F. O& w
理论基础：序贯式算法
按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

  z, \& v( m1 Z$ i) C* ^规划算法的应用

2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
# g* C. O2 s+ ^5 G, c3 G

德古拉

Nice shot, thx for sharing