数学建模中的规划问题

杨利霞

数学建模中的规划问题


7 Z8 S0 L5 |  R( q. z& D# l*规划算法综合概述*
" V/ O5 N" I, c" F7 a, f  H  U  `规划的基本概念
规划的分类方法（了解）
3 }/ B+ J, j9 t# [$ F) c/ B6 ^求解规划的基本方法
*线性规划*
( }- t$ U6 u- o1 l( f; E% X线性规划模型的建立
线性规划求解
*非线性规划*
' s+ @0 `4 _) ~4 @4 Z*整数规划*
整数规划的分类
' N1 o2 E7 \! s4 D( L6 y整数规划的求解方法
特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
# N* s( |8 E2 H4 z! K# |动态规划的优缺点
$ ~- p% g4 W; M8 F! Y4 J) }- H$ K==目标规划（重点）==
目标规划模型的建立
引入偏差变量的概念
1 c. Q  w+ m  E) Y9 }9 X+ K引入优先因子
目标规划的一般模型
目标规划的求解方法
/ w9 X7 D. ^5 [7 Q9 r9 T& o规划算法的应用
装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述
7 N2 {) l4 I$ D% T5 b) o
% P0 ?- c& d1 A0 c对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

5 z! _" }6 _' k, T规划的基本概念
5 Z4 U# _; ~# w7 z, X( R2 @  u/ S
7 D; d- P4 x7 l! H4 {7 q规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。

0 d4 y3 ^9 m1 r! Z+ `决策变量x，目标函数z，约束条件g(x)
3 h3 w" F  D8 h% S4 f6 z5 N2 }
; B6 y/ N. H; B& a: r& q规划的分类方法（了解）
9 M& J" o9 W1 I( L
) ?: ^1 }1 V) ]


- c9 a) S$ [) j* S( l  N0 Z
求解规划的基本方法
( b" A4 K( @  E4 m
方法：在具体规划模型中会说明
软件：Lingo Matlab

线性规划
( Q8 `" R, N) ~# k5 E
线性规划即目标函数以及约束条件都是线性的规划。
* I8 |  _+ O2 w7 N. R. i
0 W7 @2 _6 P6 w- x9 J  B8 P线性规划模型的建立
* E" h4 T, R( V2 D- F) ]5 P% O' g+ L
* j! y+ L# N+ X# m- ]7 _# B) ~线性规划的标准化
' G- v3 \. \0 F! V& Q4 G
3 e3 I3 e; d( Z目标函数标准化
约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
) o% M4 f9 S$ H$ k9 {, ^
% i5 ?* k+ {/ u6 ?& Q2 t% j2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
! Y( d: N0 k* N: E* b2 c0 C8 z
) R$ @7 r/ t' W* ~( Y2 w$ X例如

6 c& o2 T9 P" h1 u- F% e) @引入松弛变量 Xn+1,Xn+2

2 n/ C8 w( H2 h3 Q% d2 D4 `1 s, Y! e. Za1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
! }* |  [; x: N- `' I
添加限制
Xn+1>=0
Xn+2>=0
, G; H% S" h6 q3 T0 F

4.因此所有的线性规划都可以化成标准形式：
+ a; l1 a0 ^( u! c8 F


3 k: J- D; E7 X3 ~; P线性规划求解
% }4 t6 j0 E8 Y* w+ g# X7 u
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
+ ~! q* r& O1 p) F  Y$ ]5 Q/ z# l
9 C+ R/ O, I# C9 p4 f& k. j% t  l代码简单
' x& J, O. S6 Q( \0 A结果易分析
不容易报错

大概就是这个样子
Matlab求解
/ ~0 B4 o7 U5 l( q6 {
% e% ]9 G- W- B3 Y其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。

: J) T0 _; r7 D) d: ~' z
  M8 M0 j# g% {0 d所有量需要化成矩阵形式，负责代码的同学自己去了解。

, X3 ~8 V7 Z9 k& h0 _( p# ^
7 [% u5 _- w/ W* Y非线性规划

& J# F' B- g7 N' j( @# H- S1 z9 B3 n& o简单说就是目标函数和约束条件至少有一个是非线性的规划。
9 X) M5 e, Y/ S$ q: A& a' O) g0 c
Matlab形式
$ F9 [' D( Z  Q6 G
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
/ B1 K) m5 b6 |6 ~6 g总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

- f! W. S7 Q! e3 n# F整数规划

+ Y* l* v$ M4 d+ o1 a- Z! v决策变量为整数类型的规划。

整数规划的分类

4 Z2 l1 q# Y: R4 [" T  |" ~
8 A  w, m- [4 X! p+ T/ l
整数规划的求解方法
3 z( P+ _, j2 o' g+ Z
蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
7 c1 |4 u; D! ]/ K' ~" b, p2 F1 S
某整数规划题目的求解过程



  Z; T* k$ a' E; z特殊整数规划0-1规划
2 K# k) A: [: R
即在整数规划的基础上增加一个限制条件 0<=x<=1
0 ?( ?( L3 u& J' b
. Z7 k& l) ~$ e4 x. `' R

# l3 L# ^% A- b; P' ?
# f, Y; C! a! Q
$ ]' h& O! S4 z. E) `

动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
% @) s4 A: \; P' @& B3 p) {1 g
动态规划模型的基本原理
3 L. [( e3 D. W( g
( W7 U$ O7 H4 T0 z9 _! T最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。

; s$ U# j: R, A; m贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
  P. h% u* ~4 A
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

2 G- }" f5 H! G! @动态规划的优缺点
( z. w1 f* j% [& r
优点：
+ w" |  o  z& ~/ {1.可得到全局最优解
+ q8 ~0 W; c( o" B+ H) i2.可得到一族最优解
3.可以利用经验提高解题效率
2 P; X- R7 J" ]缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

目标规划（重点）

目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。

目标规划模型的建立
4 H# [, V0 e+ Y  O" U
- e* m% N# @3 g, N! O

( }3 z" F7 V- c5 S, F
4 H$ ]. q0 S" ?; ]+ q引入偏差变量的概念

4 c* E' w/ b0 c8 e$ S! w. ?
) Y  b9 [# K! ?% U* t
% @+ |8 s6 X: H+ [

  g  Q) c7 n9 X; l* D6 P: Y. {
引入优先因子
+ L" `9 o9 m! d- f8 J

" Q3 P7 k- U. h
目标规划的一般模型


/ Z; H/ o) C4 O  W/ o& q% ^
$ \6 W+ I) D. j* f  o. q3 [目标规划的求解方法
$ I% g; {+ S! t5 ?6 `$ J" @; O
9 F* @( S0 F; y理论基础：序贯式算法
/ b) Q1 I5 W4 S, M6 `. o按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
, b% J) ]/ `" T
1 Q& r0 z2 K1 j  I* `7 }( T规划算法的应用
5 ?1 V8 D/ K6 o; p; O0 o6 K
2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
. s5 a, A' \0 X1 Q, Z2 _* t* L6 j' H
2 p: {$ L" f# c( X

德古拉

Nice shot, thx for sharing