数学建模中的规划问题

杨利霞

数学建模中的规划问题
9 P! D* [" O. W& V- a' l9 j4 a

*规划算法综合概述*
规划的基本概念
4 }# @4 W9 h+ n规划的分类方法（了解）
5 E, p+ P6 l6 F" L9 Q. y求解规划的基本方法
: g" s3 ^0 u# p& a9 ~*线性规划*
; z: e; e) x; g- y& D' [+ Y9 a线性规划模型的建立
* ~) Z! _6 b$ p; R' r& j% k4 ?( |线性规划求解
8 E2 d  \# {1 e( C3 q0 |*非线性规划*
*整数规划*
整数规划的分类
. Y. R0 z; K6 K# P, \0 l整数规划的求解方法
特殊整数规划0-1规划
6 a$ I9 e+ I% U9 p7 p' o动态规划（了解即可）
动态规划模型的基本原理
动态规划的优缺点
==目标规划（重点）==
) k( {3 n& ~3 Y& A目标规划模型的建立
9 v$ b, l; o$ d" R  F引入偏差变量的概念
引入优先因子
目标规划的一般模型
- a9 ~2 q' c1 R: j, M) q, O- n目标规划的求解方法
1 C7 u7 J( J1 g$ u6 p规划算法的应用
6 _& @2 H' u7 {) Q$ \! W装了半天数学公式编辑器，没装好，见谅。

规划算法综合概述

对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799

规划的基本概念

规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
7 I9 V2 N1 e" R% Y3 g' d- J
决策变量x，目标函数z，约束条件g(x)

+ v! w% @7 D$ `& a9 {7 d7 }  I) F' p( K规划的分类方法（了解）

3 ~8 G" I/ I# J$ x0 k9 g# @  T3 `# @


* ]; I( J/ b+ J0 D( k; Q! y
9 K4 b0 r, U6 J: K3 U/ j" {求解规划的基本方法

) N+ w" T; Q  @方法：在具体规划模型中会说明
软件：Lingo Matlab
! {6 d$ v2 X7 O! V2 ?* u  F$ [% o& B
/ e. X, o" P/ e+ Y& R% ?5 _- d7 \线性规划
& w* j: y) J- d
# Q% \. \; r1 A线性规划即目标函数以及约束条件都是线性的规划。

线性规划模型的建立
$ j8 Z2 z9 V5 d' A
  h$ c' m* B3 E, c& d. F线性规划的标准化
+ Z# T$ ~- l* {$ Q
* G: `' N+ @/ G1 E目标函数标准化
  G" e/ A0 ]) j$ [, U" {3 ]约束条件标准化
决策变量的标准化
8 Q- `( @" @6 ?$ M& b- o8 A7 u- [% R1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)
) J0 ~; A1 t7 ]  P
2.约束条件统一由不等式化为等式。简单说就是如果式子是大于等于号，则式子左端减去一个正数，反之则加上一个正数。
- {3 X- K4 `8 {$ t; @
& ~8 \& o# S4 k5 w% S7 \; b例如

0 K/ U; W3 R* ]! P6 ]1 \引入松弛变量 Xn+1,Xn+2
6 @' [! ?" @! }" g; P" p
+ p; f: C2 D/ ~& aa1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
- u0 f3 h# E4 ^8 ]; b" V7 Ta1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2
( s! j& h: F9 p1 x
添加限制
Xn+1>=0
Xn+2>=0

6 x( S% h; W$ z4 R
4.因此所有的线性规划都可以化成标准形式：

* `7 x7 |5 j  i7 d, l% {

线性规划求解
+ S# X$ m' H: q- A! I) S$ X0 h* q/ `8 L
理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

* U0 a7 K! Y5 t; R  p" jLingo求解
3 a( `5 i& J! D; R1 U& i
) s2 N/ W5 g0 W' d5 c! S; G代码简单
结果易分析
# P4 l5 R  l! ~+ x  H# |" E不容易报错

大概就是这个样子
Matlab求解

. w5 k, g) Z7 \. R其中A,b,Aeq,X,beq,C都是系数矩阵。 约束条件中第一个为不等式约束，第二个为等式约束，第三个为决策变量的范围，在下节非线性规划中会再次升级。
: Y2 x. \$ @* v& E3 i" R  u. v& t

所有量需要化成矩阵形式，负责代码的同学自己去了解。
4 ^% D* g$ ]  i2 G: k
- C3 s6 y/ e. u) X( ?0 v
5 N- A3 o9 @: z6 `3 [非线性规划

简单说就是目标函数和约束条件至少有一个是非线性的规划。

Matlab形式
; {  N, h9 m3 B4 k# q5 H5 |  y) f. e
从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。

整数规划
/ d8 ~: |& h* w$ j& E5 R6 c8 M
5 s+ S1 D. G  Y决策变量为整数类型的规划。
6 l- d6 [) j4 h4 m
整数规划的分类



整数规划的求解方法
" O) p$ }5 O- c/ A- P; Q
9 M1 I/ ?5 [5 S, t. p蒙特卡洛算法
* h' H4 g& B* j! |0 y) m3 c蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
& o& B* C7 B; _# s0 a  n, ]7 [
  W" _! M( b: z9 h% |某整数规划题目的求解过程


- T. m# K# m( ]4 R' b  b
特殊整数规划0-1规划
6 }# ?! F9 E6 @& r5 g" R
即在整数规划的基础上增加一个限制条件 0<=x<=1
$ t: v  [6 R0 j" ?- f
: y: x3 v6 P3 Y1 ]) v" K" [1 g
$ ~# R4 v; z# X( B% h4 I$ a

& T, Z+ N* T3 F1 y

, Y4 t# v7 o" B4 a+ B  I1 f
动态规划（了解即可）
6 S8 t2 N/ W. q( r* J  S
1 V( B4 g# O' s简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。
* x: a/ q" p/ v
动态规划模型的基本原理

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

8 m/ k1 [" ~  n* ?0 J) ^贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。

  F( Z4 A0 q* I# Y5 o6 Z逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

% A( f1 F( a) b动态规划的优缺点
- M8 V, N1 V. X0 a; |
. M+ {! {* F# l* V, j6 `# {& H优点：
1.可得到全局最优解
2.可得到一族最优解
) G: B& }' {8 B. r# Z3.可以利用经验提高解题效率
! a$ ?$ t6 W5 s* z缺点：
1.没有统一的模型
2.用数值方法求解存在维数灾

目标规划（重点）

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

目标规划模型的建立
( I1 z. J8 k6 {! b

: @+ I+ G, N* W3 l: {- W

/ y# D6 k# O" A) b% b$ X# p3 P- u引入偏差变量的概念
$ d3 z  Z! c3 ~

7 l* X& y, w# G7 z



引入优先因子



目标规划的一般模型
5 N; i# |. N1 B- F0 R


目标规划的求解方法

理论基础：序贯式算法
5 `! h$ q$ Z' e( q5 S% }6 m* p按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。
5 o" g) s1 ]! o  }
规划算法的应用
" E0 {# G' N0 u8 G  @, d( K
2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
% W+ M: {, P% l6 X* S' B2 ]+ p

# D' F! t: r  l+ d7 m6 O4 v! l- h

德古拉

Nice shot, thx for sharing