数学建模算法总结（一）

杨利霞

数学建模算法总结（一）
§1 线性规划
2 e3 K/ l! P; Y3 }3 I0 ~1 p$ I2 ?
* M3 j# B8 o2 Q+ b/ b在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear
Programming 简记 LP)则是数学规划的一个重要分支。
. ^5 L9 @1 l$ U, T
1 m! L0 l1 E5 w* L2 z1.1 线性规划的 Matlab 标准形式
线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性
# k$ f+ h. K1 {* x规划的标准形式为
% L) o; a, B) W
, x' G' F- l6 Q- w: N

) J5 z& z: p4 _+ J
& }0 A8 E: R# j9 @" U8 Q其中 c 和 x 为 n 维列向量， A 、 Aeq 为适当维数的矩阵， b 、 beq 为适当维数的列向量。
! o* h' [0 [: k# u
1.2相关问题
; N$ P# a/ k  d' a% I4 Z% H( F
运输问题(产销平衡)、指派问题（匈牙利算法）、对偶理论与灵敏度分析、投资的收益和风险

. X) Q7 [2 A4 T% S; U% m3 Z2 `7 l! [& V
: C: L, G+ H8 W
) e8 X! P8 z9 l8 e- p, `3 u) m§2 整数规划

, R7 x+ U; N6 t4 G& M) x% Y# O2.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
$ |# l5 S: d) V. F2.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1 M1 W: @" {! S" h" K; m1   变量全限制为整数时，称纯（完全）整数规划。
, H' ^6 u; d0 h2   变量部分限制为整数的，称混合整数规划。
" @4 |8 k9 C# O2.3 整数规划特点
（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
+ n+ v1 [: A) E0 A) e' Q8 x& r①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
3 _$ F; A  i1 |1 `
③有可行解（当然就存在最优解），但最优解值变差。
- U, k9 b7 B& E, T9 T5 O6 _+ p
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
2.4 求解方法分类：
# X" N* U8 k, O- @, p（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
9 }  x$ H* Z$ {①过滤隐枚举法；
②分枝隐枚举法。
' J/ h* [, J+ l  v! w* j6 i（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。

, h! L* E' `: P5 i4 h( m
6 X, u& p* ^3 _
§3  非线性规划
2 r+ a9 ^* }' X/ {/ X* W1 x
4 R& ?0 r' h: e8 K" [. X- n/ I如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有
单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。

- B4 o, o$ S9 ^/ s3 N& p3.1 线性规划与非线性规划的区别
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任
意一点达到。
* P; A7 r/ u9 {* ~* a4 Q2 v/ H+ i3.2 非线性规划的 Matlab 解法
6 O, q, D9 H$ w0 AMatlab 中非线性规划的数学模型写成以下形式

* b6 R9 P3 |' i  R, `其中f(x)是标量函数， Beq,Aeq,B,A 是相应维数的矩阵和向量， Ceq(x),C(x) 是非线性向量函数。
# w% l; {2 ~) B! ?Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
  J8 U3 W  Z# I: E. z* C它的返回值是向量 x ，其中 FUN 是用 M 文件定义的函数f(x)；X0 是 x 的初始值；A,B,Aeq,Beq 定义了线性约束 Beq= X *Aeq , A*x≤ B,如果没有线性约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和 UB 是变量 x 的下界和上界，如果上界和下界没有约束，则 LB=[]，UB=[]，如果 x 无下界，则 LB 的各分量都为-inf，如果 x 无上界，则 UB的各分量都为 inf；NONLCON 是用 M 文件定义的非线性向量函数Ceq(x),C(x)  ；OPTIONS定义了优化参数，可以使用 Matlab 缺省的参数设置。

  H; [- ]! E. ~! y8 e1 l3.3 相应问题

无约束问题（一维搜索方法、二次插值法、无约束极值问题的解法）、约束极值问题（二次规划、罚函数法）、飞行管理问题
! K- [3 J! s7 ?! g# B) H


§4 动态规划（搞ACM的较熟）

动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decisionprocess）最优化的数学方法。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。



3 F! L( v1 R5 B" ^& y- c§5 与网络模型及方法（搞ACM的较熟）

0 C3 r! V  I8 I" s0 N4 e图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
2 ^: T3 O( W: ^) u. q
图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。主要包括最短路问题、最大流问题、最小费用流问题和匹配问题等。



§6 排队论模型（2017年美赛B题，2005年美赛B题主要涉及排队论）
8 X( ]2 a: t' T6 |$ [
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。
排队论（Queuing Theory）也称 随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分：
（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
. _2 s. t% T7 r% @0 X3 r$ E- A（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。
! B# w$ H- @3 t# s# J9 \（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。
" j5 `3 Y; n8 x$ S! ]
6.1 排队系统的组成和特征
+ C/ `; I6 h; }一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下：
6.1.1 输入过程
输入过程是指顾客到来时间的规律性，可能有下列不同情况：
0 [7 q; X+ Y3 Q9 K% Q& k, ?" q（i）顾客的组成可能是有限的，也可能是无限的。
9 m% g4 s6 i0 F1 C5 V& V0 r8 O（ii）顾客到达的方式可能是一个—个的，也可能是成批的。
（iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。
（iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。
6.1.2 排队规则
排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制三种。
（i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。
（ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。例如出故障的机器排队等待维修就是这种情况。
（iii）混合制。介于损失制和等待制之间的是混合制，即既有等待又有损失。有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。
3 \% J0 A* J1 A/ d+ {+ ~排队方式还分为单列、多列和循环队列。
6.1.3 服务过程
$ K9 u; x4 o* {  q, d! b" Z（i）服务机构。主要有以下几种类型：单服务台；多服务台并联（每个服务台同时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。
! A% S* O4 k( ^（ii）服务规则。按为顾客服务的次序采用以下几种规则：
& o3 T+ c- v8 t9 `①先到先服务，这是通常的情形。
7 p+ q1 `! l* k. O! h9 D% q6 g②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理。
③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。
④优先服务，如医疗系统对病情严重的病人给予优先治疗。
9 y! T6 x9 N4 V
- L5 r* K. x( ]) m9 A
2 ^( R7 z- [* X4 R/ q) [5 T0 ^
§7 对策论（搞ACM的较熟）
/ _! l7 v* l. |' Y- X
3 h: B  H" {( f1 S6 T3 }/ u对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。
+ Z' @# I$ y/ z* v1 I& u在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为 对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。
# A! S- F2 b" w5 F+ U6 S6 ]9 R3 S
/ s1 B+ H7 P9 q3 i4 r% P* G

) A3 Y/ T" R8 S6 p9 f§8 层次分析法

/ Y7 w% U$ X$ [) H4 @1 U9 _层次分析法（Analytic Hierarchy Process，简称 AHP）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。

层次分析法的基本原理与步骤
" Y+ X- H" u  E, g6 V人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。运用层次分析法建模，大体上可按下面四个步骤进行：
（i）建立递阶层次结构模型；
（ii）构造出各层次中的所有判断矩阵；
（iii）层次单排序及一致性检验；
9 }+ M0 p8 D1 h& }（iv）层次总排序及一致性检验。
下面分别说明这四个步骤的实现过程。
$ |0 [5 r! H3 M9 f7 G8.1 递阶层次结构的建立与特点
$ a% n& H, c% o) }+ x" [) H7 h% X应用 AHP 分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。
" I6 ~9 t' B( q7 {4 l这些层次可以分为三类：
（i）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。
（ii）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。
7 W' b: V7 Z2 H: M8 F（iii）最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。
递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地层次数不受限制。每一层次中各元素所支配的元素一般不要超过 9 个。这是因为支配的元素过多会给两两比较判断带来困难。
8 Q7 q* ~: w) |' O0 X" L- Q
层次分析法的应用
* T# `7 F, `+ J& B6 H+ e4 O) Q! i在应用层次分析法研究问题时，遇到的主要困难有两个：（i）如何根据实际情况抽象出较为贴切的层次结构；（ii）如何将某些定性的量作比较接近实际定量化处理。
) }' r" e8 Z$ _! O. U: o层次分析法对人们的思维过程进行了加工整理，提出了一套系统分析问题的方法，为科学管理和决策提供了较有说服力的依据。但层次分析法也有其局限性，主要表现在：
（i）它在很大程度上依赖于人们的经验，主观因素的影响很大，它至多只能排除思维过程中的严重非一致性，却无法排除决策者个人可能存在的严重片面性。（ii）比较、判断过程较为粗糙，不能用于精度要求较高的决策问题。AHP 至多只能算是一种半定量（或定性与定量结合）的方法。
. }! Y' E7 s- F9 n+ w$ ]在应用层次分析法时，建立层次结构模型是十分关键的一步。



§9 插值与拟合
# S2 Q6 v6 U1 Y# c# U; O
% U9 J+ p- D3 Z3 Q插值：求过已知有限个数据点的近似函数。
, o  ?' b+ B" O  b$ ]拟合：已知有限个数据点，求近似函数，不要求过已知数据点，只要求在某种意义下它在这些点上的总偏差最小。
" W0 o+ B( o9 g5 O" n插值和拟合都是要根据一组数据构造一个函数作为近似，由于近似的要求不同，二者的数学方法上是完全不同的。而面对一个实际问题，究竟应该用插值还是拟合，有时容易确定，有时则并不明显。
* }0 W( N5 y2 v$ U
! l) [  D; Q7 Q插值方法
几种基本的、常用的插值：拉格朗日多项式插值、牛顿插值、分段线性插值、Hermite 插值和三次样条插值。

8 O* Y# _4 U  r! Y! y0 C4 o曲线拟合的线性最小二乘法（线性最小二乘法）
$ x# O5 _- p+ x, Z+ }' x
8 r# q4 U$ p3 p& h- G9 j最小二乘优化（lsqlin 函数、lsqcurvefit 函数、lsqnonlin 函数、lsqnonneg 函数）
" M* ^" R+ p% X# e7 j
- @2 a. w( |- F1 l: v7 t
( d" z- d( \& q% [8 G
* z. P1 F7 u7 K# r§10 数据的统计描述和分析

数理统计研究的对象是受随机因素影响的数据，以下数理统计就简称统计，统计是以概率论为基础的一门应用学科。数据样本少则几个，多则成千上万，人们希望能用少数几个包含其最多相关信息的数值来体现数据样本总体的规律。描述性统计就是搜集、整理、加工和分析统计数据，使之系统化、条理化，以显示出数据资料的趋势、特征和数量关。它是统计推断的基础，实用性较强，在统计工作中经常使用。面对一批数据如何进行描述与分析，需要掌握参数估计和假设检验这两个数理统计的最基本方法。我们将用Matlab 的统计工具箱(Statistics Toolbox)来实现数据的统计描述和分析。
) E3 j, }: k+ s  P7 Y& B/ N4 K
6 R& z& C+ F* }+ Z3 Y' X7 Y+ F
) H, @1 h0 w$ ^9 E4 e