数学建模中的规划问题

杨利霞

数学建模中的规划问题


*规划算法综合概述*
规划的基本概念
规划的分类方法（了解）
0 E5 K  V4 l$ x- [求解规划的基本方法
*线性规划*
线性规划模型的建立
8 k8 Z+ M% Q3 _4 ?; U4 c线性规划求解
% x5 T8 S( v' M) l8 B*非线性规划*
*整数规划*
* P9 L, w& P4 e+ Y整数规划的分类
整数规划的求解方法
9 n+ ]0 ?6 M2 e2 o6 T特殊整数规划0-1规划
动态规划（了解即可）
9 J% D6 ~: [* |( n8 \" ]动态规划模型的基本原理
7 r* J, r5 u) B' L动态规划的优缺点
9 d: E: V- o. C( B8 l! V  c==目标规划（重点）==
目标规划模型的建立
% C% L0 X( G: q9 e引入偏差变量的概念
引入优先因子
目标规划的一般模型
: z- M: C  S  B1 {; T$ R- c# v" U0 h目标规划的求解方法
规划算法的应用
# R* y: p' f; y装了半天数学公式编辑器，没装好，见谅。
- j- k$ i. e. n$ w3 |! m
2 x5 [# P; b3 ^. j规划算法综合概述
3 U) {; c' u- }- v
对规划问题学习的心得 https://blog.csdn.net/hyqhhxx/article/details/100075799
  H6 k" U5 a+ D( g5 _
- B/ r, w2 W: ]% B0 M1 s' u规划的基本概念
. d% }5 q! w4 ]0 G4 }& Q
+ f6 e1 f9 s2 l% i规划是运筹学的一个重要分支，主要研究数值最优化问题。三个主要构成要素为决策变量、目标函数以及约束条件。
" ~% z5 I( C) ^1 K: Z+ X" r
决策变量x，目标函数z，约束条件g(x)

0 C* {% D- z0 D& `规划的分类方法（了解）

2 r1 F; \: L. ^% W! J" B. j0 F


2 e# ]9 r6 U7 j
求解规划的基本方法

方法：在具体规划模型中会说明
0 v. B" g" P0 G3 T* ^9 T1 b软件：Lingo Matlab

/ b0 g3 w/ Q6 V线性规划
' T5 H+ U+ y! V6 w( P7 m. l& X
' G, K- p( p) f% d5 {% s6 S7 X$ k线性规划即目标函数以及约束条件都是线性的规划。
* `' ~* ?5 s+ m+ ]/ \0 s* h
线性规划模型的建立
8 A* c5 u* C; ]+ r) H1 p" z- Q
$ F$ g6 l: {% v线性规划的标准化
7 ]" F' u8 A. p# k
# F: _/ w# s8 v目标函数标准化
* s, C5 ]! y  [约束条件标准化
决策变量的标准化
1.目标函数统一为求最大，如果原式为求最小，转化公式为 min(z)=max(-z)

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

: d4 f) K& o/ o" V4 L2 N% X0 k例如

引入松弛变量 Xn+1,Xn+2
5 E4 A9 D4 t4 _2 r; J
0 k. M5 w- y, |0 ta1x1+…+anxn<=b1 化为 a1x1+…+anxn+Xn+1=b1
# H; U/ c. y+ `( L  Oa1x1+…+anxn>=b2 化为 a1x1+…+anxn-Xn+2=b2

添加限制
5 f' n) o/ Z0 @- X: [, y, sXn+1>=0
Xn+2>=0
8 h: F* \. G3 S6 e

4.因此所有的线性规划都可以化成标准形式：
# z* Z  |7 _1 b- _
# q" E- s# ?5 f# }/ A7 [

线性规划求解
  ~# X" B5 b, R% e$ A
9 H( W% D/ U' W0 j理论基础：单纯形法(简单说就是在基本可行解中循环迭代求得最优解的过程)

Lingo求解
- r3 p& [$ H+ s; M
$ u) `+ J9 }+ [& {. [- \; n9 E& _代码简单
) h9 L4 k, `+ {  d结果易分析
/ K: L1 l5 ~' Y不容易报错

大概就是这个样子
Matlab求解

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

; N: j+ {0 E8 ?( |3 H& p5 i& A2 j
所有量需要化成矩阵形式，负责代码的同学自己去了解。
. k. {0 e+ x. N  y/ B# L7 y" c+ g
6 c: U: Z- N7 Q
非线性规划
0 u3 J' F$ G7 m2 F' s# T
  y" Z: k  w: z8 p- z简单说就是目标函数和约束条件至少有一个是非线性的规划。
  Y* b3 b. T9 B3 m3 p- l; C/ I. U
) ~* h: D$ |5 F& G% U6 ZMatlab形式

从公式来看，目标函数不能简单的表示为C^Tx的形式，多出了两条非线性约束条件。
' [9 R$ `# n! \9 S' z总的来说非线性规划比线性规划仅仅增添了解方程时的麻烦。
8 l7 W" ~( s7 q% r* C
整数规划

决策变量为整数类型的规划。
! B# w! A. j$ |# S% T) G
整数规划的分类

; [$ H# J6 k, g- d
4 \( w5 x9 s' a2 p" \+ S2 U! R
整数规划的求解方法
8 f7 }+ R' }+ z. ]4 ^4 ]4 p% f
蒙特卡洛算法
蒙特卡洛算法，本质就是随机取样法，是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。

某整数规划题目的求解过程

, |9 {: }+ ?, \- p
8 N8 t& ^; s  ^+ f2 n) O1 h
特殊整数规划0-1规划
0 `* U$ T/ H) k. |
即在整数规划的基础上增加一个限制条件 0<=x<=1


+ S* ?  t& b9 b/ r5 _5 U' g2 S
! M$ G( }% `5 ^8 |+ K9 {# c


3 N4 p8 n7 b7 Z* p. H) ?
6 J) c* x. g3 n( i+ B2 K1 I动态规划（了解即可）

简单来书每一阶段的决策，常常会影响下一阶段的决策，通过动态规划求取全局最优解。

  F6 c) K/ W) ^动态规划模型的基本原理

8 \- l; i" J1 P  L最优化原理：如果一条最短路经过Xk，那么这条路线上从Xk到终点的一段，是从Xk出发到终点的所有路线中最短的。
3 h% r2 U7 V" D2 n5 n
贝尔曼—福特算法：在整个过程的最优化策略中，无论过去的状态和决策如何，对当前而言，余下的策略必须构成最优策略。
! v6 @5 }0 a3 s, Q
逆序法由1和2衍生出来：从后往前逐步求出各点到终点的最佳路线，最后求出全局最优路线。

动态规划的优缺点
3 l0 g) D$ z* c" V+ b5 o% ?
0 u9 S9 |$ B$ V9 a4 k4 X3 v5 V3 B优点：
1.可得到全局最优解
2.可得到一族最优解
3.可以利用经验提高解题效率
缺点：
/ Z( [: \. s& D1.没有统一的模型
+ j# c; F% H+ }7 y6 ~5 g3 {  p: Q( K6 k9 }2.用数值方法求解存在维数灾

目标规划（重点）
9 G! {9 p) C/ K4 `, q' f& \
- k8 p- d, |+ k9 W/ F: e目标规划中的目标不是单一目标而是多目标，既有主要目标又有次要目标。根据主要目标建立部门分目标，构成目标网，形成整个目标体系。制定目标时应注意衡量各个次要目标的权重，各次要目标必须在主要目标完成之后才能给予考虑。
. K, d9 ]; Z2 ~% q
目标规划模型的建立
( Z0 x2 D0 ?4 j. p

# ?) |. \1 p* Y! b/ h$ x. C
# ^9 e; ?; U* B6 z. M
引入偏差变量的概念


5 ?5 x0 c- S# L4 O( g



  s+ G6 o# L' m* E$ d2 R引入优先因子

9 x. W- V" T1 `/ w- l2 R2 a

目标规划的一般模型



目标规划的求解方法
* W) T6 f9 y4 k' N$ c. d/ X
3 C7 L0 I4 _# W9 e9 N. F; p: N" `理论基础：序贯式算法
' k5 r/ g& b5 M按各个目标的优先次序，由高到低按单目标的规划问题求解，最高级的优先解解出后，添加到目标偏差的上界添加到约束条件中。

规划算法的应用

4 B& W6 T- E( [5 H: W2015国赛 太阳影长的问题
原文链接：https://blog.csdn.net/hyqhhxx/article/details/100071956
$ T) U$ b: k5 G2 i5 V/ u
1 \0 S: A: R! F! J9 y; n
# X* h1 v7 o6 l3 {, @8 V  g# `" }

德古拉

Nice shot, thx for sharing