数学建模中的规划问题

杨利霞

数学建模中的规划问题

- k, S# R& C. `& Q2 f5 n
" [2 ~; R( D6 ^: Q  j* ~0 [*规划算法综合概述*
6 `  O* Z, X( F, ~规划的基本概念
规划的分类方法（了解）
求解规划的基本方法
# l7 v9 ]  |/ T7 g*线性规划*
! c3 e( \; Y+ [线性规划模型的建立
$ s. P1 E) [7 y; S  @+ v线性规划求解
. N* ?) N0 K- R*非线性规划*
. z. X. i# o8 A0 N' j*整数规划*
整数规划的分类
* a: Y$ L. H& q0 Z" m1 m2 y4 M整数规划的求解方法
4 t4 e' `6 P9 m1 }特殊整数规划0-1规划
动态规划（了解即可）
动态规划模型的基本原理
+ [+ N* i. c# v& b1 n动态规划的优缺点
==目标规划（重点）==
( `2 @6 Q- O1 ^# ]+ A目标规划模型的建立
  k5 Y4 ~) p/ [# ]' J8 ?$ B+ \引入偏差变量的概念
2 m) O. a& }( z引入优先因子
目标规划的一般模型
" y7 _* J/ O9 h+ U1 f3 r目标规划的求解方法
0 v5 }2 _2 C, n规划算法的应用
  G, t6 x' |" c% ~0 `& `装了半天数学公式编辑器，没装好，见谅。
- N  L  H5 @3 c/ D! X
规划算法综合概述
1 i* [$ |# ?" {/ F
3 ]7 V9 U/ I  Q& U# m5 _$ ]! n对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
3 b' A" W# i% M, m* {
决策变量x，目标函数z，约束条件g(x)

规划的分类方法（了解）
) L2 |, N4 T0 z; S6 e: q

# e: X  H) Y9 d: J
" W% L% ]+ {: O2 f9 i
: ]0 p* L1 }& l7 J4 Q
求解规划的基本方法
' {  P7 h% ]% r4 d
* f; ^2 K3 U8 h, i1 v) g方法：在具体规划模型中会说明
软件：Lingo Matlab
& ~! O* U3 W" i6 W
线性规划

线性规划即目标函数以及约束条件都是线性的规划。
9 N3 q, S: m. O+ n% x
线性规划模型的建立
% M) r' w* j, w. Q8 h+ ^8 C& D
线性规划的标准化

目标函数标准化
* o$ m- j2 T! Z3 f4 j  n约束条件标准化
决策变量的标准化
, z' t3 \! p3 {1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

! n0 _2 }& F. w8 i2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。

+ i, v; J( d, w例如

引入松弛变量 Xn+1,Xn+2

$ Z/ E- q) b; J, ra1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
a1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
2 z4 }$ J( j& r" a' W. t4 P5 ^6 h
1 o8 j* v4 J/ W! j添加限制
: ?$ c) E. {. i8 d% KXn+1>=0
  Q0 y- R0 o( a6 Z, d0 V0 Y4 @Xn+2>=0

8 F: e- `( @/ P6 t1 y2 m
4.因此所有的线性规划都可以化成标准形式：


& [6 V- U8 w* Z8 R+ ?- l4 K
线性规划求解

' D) E1 n- _/ E: [3 i$ F理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)
0 G) k$ ?/ P" ^; W: J! P
Lingo求解

代码简单
结果易分析
# X/ i3 C7 o+ ^- m8 J6 W不容易报错

大概就是这个样子
, F$ x; C# ~/ S5 c* sMatlab求解
3 p5 |, h/ A+ V6 Y# T( E
其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
% ~# p1 \# T, @( @( Z0 m% ?9 a  `2 `

( X- `  E# g: b/ `所有量需要化成矩阵形式，负责代码的同学自己去了解。

! h8 \: f0 \3 k' ~) d
' u1 T! `$ f9 }6 P6 i非线性规划

7 `. F- ~& W6 i简单说就是目标函数和约束条件至少有一个是非线性的规划。
: i' M% A/ v" o+ ^6 _- ?
Matlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
& K& M% K6 W1 D3 b) K; R总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划
7 T/ t6 A4 I5 D5 \. a+ q$ s; \7 Y* ~
决策变量为整数类型的规划。
* T, ?$ d1 j: V/ w6 c5 }
整数规划的分类
5 Z4 [9 {0 G) N/ ?
9 ^, a- J" L( @' y
1 z+ y# R' @0 ~
- C! _1 L" ~. W( V7 k整数规划的求解方法

4 `! |6 Q( }: {7 Z4 O, N蒙特卡洛算法
9 l8 R" K# I2 E" |5 E0 \" s# y蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
% U& I; J  S" t6 }1 C
某整数规划题目的求解过程

9 _4 c- R! r& A4 D9 P0 M

特殊整数规划0-1规划
" v0 j% I- }, S' e$ |, r
( N6 s# `( Y, g; ?, G9 X即在整数规划的基础上增加一个限制条件 0<=x<=1
- \, N8 j4 i$ r/ M6 @
. E( b( ]( t; e  ^9 q. Z" T

. p9 Z% @: {/ m; o. `- w
; L8 v. u/ E6 K" d" n
8 n3 z! x1 S. e4 L/ V+ y$ U+ P
( U. ]& W; R" V" O# J: z
动态规划（了解即可）
  H5 ?: ?" w8 K- W5 P
简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
' k1 g' k$ F+ V% I
动态规划模型的基本原理

最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
9 w+ B% G7 L+ s& d
+ Z- g2 A  Z; d  u5 K6 [贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
  e% I( a5 ]7 X
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。
* Z# q, |& e# e1 ~+ b% f
动态规划的优缺点
; t# b- k: `% {; J* U
) O$ H0 N5 j; y$ I0 |优点：
1.可得到全局最优解
2.可得到一族最优解
6 q, a: v, p3 |3.可以利用经验提高解题效率
4 O) R% ]; y! ]" y. v; `缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

8 ]# h- [; |$ y1 [1 g目标规划（重点）

目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
7 y* N$ ~5 m# C
目标规划模型的建立
+ `9 \) T! Y. v: n' A
7 G8 O- b7 S  q. H1 e) U; ?
" b+ ^& L/ k" i  ]% v) Y

5 \5 u& u7 k+ a7 f+ P2 n/ U引入偏差变量的概念
* H7 m) w, o8 d. R: O9 r




. ^2 s; t, v/ s% I
引入优先因子
" P/ {  J; @# @: q( a
4 g2 h& a' F( E& M6 H, C% z
' p% V/ H2 `8 u7 d) H
目标规划的一般模型


1 [: z$ j4 t+ F% R0 y
目标规划的求解方法

理论基础：序贯式算法
5 M7 T. V" |: z- h" w按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用

$ B9 R6 A; S; d. u; n2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956

- p7 Y2 G, V* b5 l) j" j

德古拉

Nice shot, thx for sharing
; h2 u* |# Q- C' ~1 ]