1 图论应用

①最小生成树

• 连接所有顶点；
• 无环路；
• 权值之和最小。

②最短路径

• 起点；
• 终点；
• 只要有1条通路就可以了
• 权值之和最小。

③网路与最大流量

• 起点；
• 终点；
• 多条路径合并。

1.1 最小生成树

例题：
某小区有七栋楼房①~⑦(见下图),各楼房之间可修燃气管道路线的长度（单位:百米)已标记在连线旁。为修建连通各个楼房的燃气管道，该小区内部煤气管道的总长度至少为多少百米?

分析

• 克鲁斯卡尔算法：最短边
  

• 普利姆算法：最近顶点
  

• 故煤气管道的总长度至少为：2+3+3+4+5+6=23百米

注意：最小生成树可以有多种，但是最小权值只有一个。

1.2 最短路径

例题：
有一批货物要从城市s发送到城市t，线条上的数字代表通过这条路的费用(单位为万元)。那么，运送这批货物，至少需要花费多少万元?

分析

最短路径：S->2->3->5->6->t，需要花费21+20+20+8+12=81万元

1.3 网络与最大流量

例题
下图标出了某地区的运输网，各节点之间的运输能力如下表所示。那么，从节点①到节点⑥的最大运输能力(流量)可以达到多少万吨/小时?

分析

1. 多段流量分析时，流量由瓶颈决定；
2. 以抽取的方式分析剩余流量；

• 先根据表在图中标上数据：
  
• 步骤1：（1）最大流量路径：1->3->5->6，最大运输能力10
• 步骤2：抽取对应路径
• 重复步骤1、步骤2，直到没有路径为止。
• （2）1->2->5->6，最大运输能力6
• （3）1->4->6，最大运输能力5
• （4）1->4->2->5->6或1->4->3->5->6，最大运输能力1，1
• 故从节点①到节点⑥的最大运输能力(流量)可以达到10+6+5+1+1=23万吨/小时

例2
在军事演习中，张司令希望将部队尽快从A地通过公路网(见下图)运送到F地:

图中标出了各路段上的最大运量（单位:千人/小时)。根据该图可以算出，从A地到F地的最大运量是（）千人/小时。
A 20
B 21
C 22
D 23

分析
（1）A->B->F，最大运输能力8；
（2）A->B->E->F或A->D->E->F，最大运输能力4，4；
（3）A->D->C->E->F，最大运输能力3；
（4）A->C->E->F，最大运输能力2；
（5）A->B->C->E->F，最大运输能力1；
故最大运量是8+4+4+3+2+1=22千人/小时

2 运筹方法

2.1 线性规划

线性规划的一些特点:

• 线性规划的可行解域是由一组线性约束条件形成的，从几何意义来说，就是由一些线性解面围割形成的区域，不一定是封闭的多边形或多面体。
• 如果存在两个最优解，则连接这两点的线段内所有的点都是最优解，而线段两端延长线上可能会超出可行解区。
• 增加一个约束条件时，要么缩小可行解域(新的约束条件分割了原来的可行解域)，要么可行解域不变(新的约束条件与原来的可行解域不相交)
• 如果最优解在可行解域边界某个非顶点处达到，则随着等值域向某个方向移动，目标函数的值会增加或减少(与最优解矛盾)或没有变化(在此段边界上都达到最优解)，从而仍会在可行解域的某个顶点处达到最优解。若最优解存在且唯一，则可以从可行解区顶点处比较目标函数值来求解。

线性规划的标准型(standard form of linear programrmng)是线性规划模型的标准形式。其主要特征为:
(1）目标函数为极大化类型;
(2）所有的约束条件都是等式;
(3）所有约束方程右端的常数都是非负的;
(4）所有决策变量都是非负的。

例题
线性规划问题由线性的目标函数和线性的约束条件（包括变量非负条件)组成。满足约束条件的所有解的集合称为可行解区。既满足约束条件，又使目标函数达到极值的解称为最优解。以下关于可行解区和最优解的叙述中，正确的是（ )。
A 可行解区一定是封闭的多边形或多面体
B 若增加一个线性约束条件，则可行解区可能会扩大
C 若存在两个最优解，则它们的所有线性组合都是最优解
D 若最优解存在且唯一，则可以从可行解区顶点处比较目标函数值来求解

分析

• 由一些线性解面围割形成的区域，不一定是封闭的多边形或多面体
• 增加一个约束条件时，要么缩小可行解域，要么可行解域不变
• 如果存在两个最优解，则连接这两点的线段内所有的点都是最优解，而线段两端延长线上可能会超出可行解区
• 若最优解存在且唯一，则可以从可行解区顶点处比较目标函数值来求解
• 故答案D

例2
某企业需要采用甲、乙、丙三种原材料生产l、I两种产品。生产两种产品所需原材料数量、单位产品可获得利润以及企业现有原材料数如下表所示，则公司可以获得的最大利润是(1）万元。取得最大利润时，原材料（2）尚有剩余。

(1)
A.21
B.34
C.39
D.48

(2)
A.甲
B.乙
C.丙
D.乙和丙

分析
设生产Ⅰ与Ⅱ产品的数量分别为︰X和Y。
则有:
(1)X+Y<= 4
(2)4X+3Y<=12
(3) X+3Y<=6
(4)X>= 0，Y>=0
目标函数：
9X+12Y

图解法：
找顶点，代入
联立方程求解：

例2
某公司现有400万元用于投资甲、乙、丙三个项目，投资额以百万元为单位，已知甲、乙、丙三项投资的可能方案及相应获得的收益如下表所示，则该公司能够获得的最大收益值是（)百万元。
A 17
B 18
C 20
D 21

分析
穷举法：

• 甲：1，乙：2，丙：1，收益值18
• 故答案：B。

2.2 动态规划

2.2.1 供需平衡问题

例题
设三个煤场A、B、C分别能供应煤12、14、10万吨，三个工厂x、Y、Z分别需要煤11、12、13万吨，从各煤场到各工厂运煤的单价（百元/吨)见下表方框内的数字。只要选择最优的运输方案，总的运输成本就能降到（）百万元。

A 83
B 91
C113
D 153

贪心策略分析

1. 找单价最低的：
   煤场A到工厂Y的单价最低；
   煤场B到工厂X的单价最多；
   煤场C到工厂X的单价最低。
   由于工厂Z没有单价最低的，就需要考虑分配一些产量给工厂C；
   

2. 分配一些产量给工厂C：
   对于煤场A：工厂Y分配产量给工厂X，单价成本增加4，分配产量给工厂Z，单价成本增加5；
   对于煤场B：工厂X分配产量给工厂Y，单价成本增加2，分配产量给工厂Z，单价成本增加1；
   对于煤场C：工厂X分配产量给工厂Y，单价成本增加3，分配产量给工厂Z，单价成本增加4；
   

现在想要成本越少越好，所以成本增长越少越好，所以把煤场B的产量分配给工厂Z，又工厂Z的需求量为13，煤场B最大供煤量14，所以工厂X分配产量为1，工厂Z分配产量为13。煤场C的最大供煤量10全部都分配给工厂X。煤场A的最大供煤量12全部都分配给工厂Y。最终得到最优方案。

3. 运输成本最低为：21+310+112+313=83百万元
4. 答案：A

伏格尔法求解供需平衡问题
伏格尔法的步骤是:
1、算出各行各列中最小元素和次小元素的差额,并标出差额最大的(若几个差额同为最大，则可任取其一)。
2、在差额最大的行或列中的最小元素处填上尽可能大的数。
3、对未划去的行列重复以上步骤,直到得到一个初始解。

2.2.2 任务指派问题

例题
某企业准备将四个工人甲、乙、丙、丁分配在A、B、C、D四个岗位。每个工人由于技术水平不同，在不同岗位上每天完成任务所需的工时见下表。适当安排岗位，可使四个工人以最短的总工时( ）全部完成每天的任务。

A 13
B 14
C 15
D 16

贪心策略分析

匈牙利算法分析

例2
某工厂分配四个工人甲、乙、丙、丁同时去操作四台机床A、B、C、D,每人分配其中的一台。已知每个工人操作每台机床每小时的效益值如下表所示，则总效益最高的最优分配方案共有（）个。
A 1
B 2
C 3
D 4

匈牙利算法分析
按行减：
按列减：

故正确答案C

3 预测与决策

3.1 不确定型决策分析

例题

分析
乐观主义者：（500，300，300）=>积极型
悲观主义者：（50，100，200）=>保守型
平均值决策法：（700/3，600/3，750/3）=>保守型
后悔值：（250，200，300）=>稳健型

例2
某公司为经营业务的需要，决定要在现有生产条件歹变的情况下，生产一种新产品，现可供生产的产品有甲、乙、丙、丁四种类型。由于缺少相关资料背景，对新产品的市场需求只能估计为大、中、小三种状态，在不同的市场需求条件下，新产品的收益值如表所示。如果决策者采用后悔值方法进行决策，该公司应生产（ ) 。

A 甲
B 乙
C 丙
D 丁

分析

答案：B

3.2 风险型决策

3.2.1 决策树

例1
某电子商务公司要从A地向B地的用户发送一批价值为90000元的货物。从A地到B地有水、陆两条路线。走陆路时比较安全，其运输成本为10000元;走水路时一般情况下的运输成本只要7000元，不过一旦遇到暴风雨天气，则会造成相当于这批货物总价值的10%的损失。根据历年情况，这期间出现暴风雨天气的概率为1/4，那么该电子商务公司该如何选择呢?

分析
水路：
好天气：70000.75=5250
坏天气：（7000+9000010%）0.25=4000
总计：70000.75+（7000+90000*10%）*0.25=9250

陆路：10000

水路的成本低些，故选择水路

例2
某企业拟进行电子商务系统的建设，有四种方式可以选择:①企业自行从头开发;②复用已有的构件来构造;③购买现成的软件产品;④承包给专业公司开发。针对这几种方式，项目经理提供了如图所示的决策树，根据此图，管理者选择建设方式的最佳决策是（ ） 。
A．企业自行从头开发
B．复用已有的构件来构造
C．购买现成的软件产品
D．承包给专业公司开发

分析
自行从头开发：0.338+0.745=42.9
复用：0.427.5+0.60.231+0.60.849=38.24
购买：0.721+0.330=23.7
承包：0.635+0.4*50=41
故最佳决策为购买现成的软件产品
答案C。

例3
生产某种产品有两个建厂方案:(1)建大厂，需要初期投资500万元。如果产品销路好，每年可以获利200万元;如果销路不好，每年会亏损20万元。(2)建小厂，需要初期投资200万元。如果产品销路好，每年可以获利100万元;如果销路不好，每年只能获利20万元。
市场调研表明，未来2年这种产品销路好的概率为70%。如果这2年销路好，则后续5年销路好的概率上升为80%;如果这2年销路不好，则后续5年销路好的概率仅为10%.为取得7年最大总收益，决策者应（) 。

A 建大厂，总收益超500万元
B 建大厂，总收益略多于300万元
C 建小厂，总收益超500万元
D 建小厂，总收益略多于300万元

分析
首先画决策树：
求平均收益值：
建大厂的平均收益高，总收益略高于300万。
故答案选A。

3.2.2 决策表

案例
评估和选择最佳系统设计方案时，甲认为可以采用点值评估方法，即根据每一个价值因素的重要性，综合打分来选择最佳的方案。乙根据甲的提议，对如表所示的系统A和B进行评估，那么乙认为( ) 。

A．最佳方案是A
B．最佳方案是B
c．条件不足，不能得出结论
D．只能用成本/效益分析方法做出判断

分析
系统A：9535%+7040%+8525%=82.5
系统B：7535%+9540%+9025%=86.75
故最佳方案是B
答案：B

4 随机函数

例1
根据历史数据和理论推导可知，某应用中，随机变量s的分布密度函数为f (x)=2x，(0<x<1)。这意味着，当Δx充分小时，随机变量s落在区间（x，x+Δx）内的概率约等于f (x) Δx。为此，开发该应用的仿真系统时，可用（）来模拟该随机变量，其中，r1和r2为计算机逐个产生的、均匀分布在(0，1)区间内的互相独立的伪随机数。

A max (r1，r2)
B min (r1，r2)
C r1*r2
D (r1+r2)/2

分析
假设随机变量s的分布密度函数为f (x)=2x
这意味着，当△x充分小时，随机变量s落在区间(x，x+Ax)内的概率约等于f (x)Ax。r1和r2为计算机逐个产生的、均匀分布在(0，1）区间内的互相独立的伪随机数。

–随机数即约等于密度函数的结果
密度函数为上升趋势，则随机数应该满足上升趋势。此处采用模拟函数max (r1, r2)随机产生随机数r1和r2。

法二：
f(x)近似等于命中率，则：
假设r1 = 0.1，r2= 0.2，
A：max(r1，r2）=0.2，f(x)=0.4；
B：min(r1，r2）=0.1，f(x)=0.2；
C：r1*r2=0.02，f(x)=0.04；
D：(r1+r2)/2=0.15，f(x)=0.3
f(x)越大，命中率越高，故max(r1,r2)命中率最高

答案：A

例2
根据历史数据和理论推导可知，某应用中，随机变量s的分布密度函数为f (x)=3x^2，(0<x<1)。这意味着，当Ax充分小时，随机变量s落在区间(x，x+△x)内的概率约等于f (x)Ax。为此，开发该应用的仿真系统时，可用（）来模拟该随机变量，其中，r1、r2、r3…为计算机逐个产生的、均匀分布在(0，1）区间内的互相独立的伪随机数。

A max (r1，r2，r3)
B min (r1，r2，r3)
C r1r2r3
D (r1+r2+r3)/3

分析
假设r1=0.1，r2=0.2，r3=0.3
A：max(r1，r2，r3）=0.3，f(x)=0.18；
B：min(r1，r2，r3）=0.1，f(x)=0.02；
C：r1r2r3=0.006，f(x)=0.000072；
D：(r1+r2+r3)/3=0.2，f(x)=0.08
f(x)越大，命中率越高，故max(r1,r2,r3)命中率最高
答案：A。

5 数学建模

数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象和简化，建立能近似刻画并解决实际问题的模型的一种强有力的数学手段。

数学建模过程

• 模型准备：了解问题的实际背景,用数学语言来描述问题。
• 模型假设：根据实际对象的特征和建模的目的，对问题进行必要的简化，并用精确的语言提出一些恰当的假设。
• 模型建立：在假设的基础上，建立相应的数学结构。
• 模型求解：利用获取的数据资料，对模型的所有参数做出计算(估计)。模型分析:对所得的结果进行数学上的分析。
• 模型检验：将模型分析结果与实际情形进行比较，以此来验证模型的准
  确性、合理性和适用性。
• 模型应用：应用方式因问题的性质和建模的目的而异。

模型分析

• 模型的合理性分析:最佳、适中、满意等。
  • 利用实际案例数据对模型进行检验
  • 可以请专家来分析模型是否合理
  • 利用计算机来模拟实际问题，再在计算机上检验该数学模型。
• 模型的误差分析:模型误差、观测误差、截断误差、舍入误差、过失误差、绝对误差、相对误差等。
• 参数的灵敏性分析∶变量数据是否敏感，在最优方案不变的条件下这些变量允许变化的范围。

例1
面对复杂的实际问题，常需要建立数学模型来求解，但根据数学模型求出的解答可能不符合实际情况，故还需分析模型参数和输入数据的微小变化是否会引起输出结果的很大变化。这种分析常称为（ ) 。

A 准确度分析
B 敏感度分析
C 可靠性分析
D 风险分析

分析
答案：敏感度分析