图论与网络最优化算法答案.docx

图论与网络最优化算法答案.docx

《图论与网络最优化算法答案.docx》由会员分享，可在线阅读，更多相关《图论与网络最优化算法答案.docx（25页珍藏版）》请在冰点文库上搜索。

图论与网络最优化算法答案

图论与网络最优化算法答案

【篇一：

《运筹学》复习题】

一、名词解释

1松弛变量

为将线性规划问题的数学模型化为标准型而加入的变量。

2可行域

满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。

3人工变量

亦称人造变量.求解线性规划问题时人为加入的变量。

用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵a中所含的单位向量常常不足m个，此时可加入若干（至多m）个新变量，称这些新变量为人工变量。

4对偶理论

每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。

研究线性规划中原始问题与对偶问题之间关系的理论

5灵敏度分析

研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。

在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。

通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。

6影子价格

反映资源配置状况的价格。

影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。

即影子价格等于资源投入的边际收益。

只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加

7产销平衡运输

一种特殊的线性规划问题。

产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。

8西北角法

是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。

也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。

9最优性检验

检验当前调运方案是不是最优方案的过程。

10动态规划

解决多阶段决策过程优化问题的方法：

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

11状态转移方程

从阶段k到k+1的状态转移规律的表达式

12逆序求解法

在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。

13最短路问题

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

14最小费用最大流

在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：

流量从a到b，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。

15排队论

排队论（queueingtheory）,或称随机服务系统理论,是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。

二、选择题

1.用图解法求解一个关于最大利润的线性规划问题时，若其等利润线与可行解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题（b）。

a、有无穷多个最优解b、有可行解但无最优解

c、有可行解且有最优解d、无可行解

2.若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（b）

a、两个b、无穷多个

c、零个d、过这的点直线上的一切点

3.用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题（a）。

a．有无穷多个最优解

b、有有限个最优解

c．有唯一的最优解

d．无最优解

4.在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为（a）。

a、很大的正数b、较小的正数c、1d、0

5.对lp问题的标准型：

maxz?

cx,ax?

b,x?

0，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值z必为（b）

a增大

b不减少

c减少

d不增大

6.若lp最优解不唯一，则在最优单纯形表上（a）

a非基变量的检验数必有为零者

b非基变量的检验数不必有为零者

c非基变量的检验数必全部为零

d以上均不正确

7.求解线性规划模型时，引入人工变量是为了（b）

a使该模型存在可行解

b确定一个初始的基可行解

c使该模型标准化

d以上均不正确

11.用大m法求解lp模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（c）

a有可行解，但无最优解

b有最优解

c无可行解

d以上都不对

12.已知

ax?

（4,4）

bx?

（1,2）

cx?

（2,3）

d无法判断

13、线性规划问题的灵敏度分析研究（bc）

a、对偶单纯形法的计算结果；

b、目标函数中决策变量系数的变化与最优解的关系；

c、资源数量变化与最优解的关系；

d、最优单纯形表中的检验数与影子价格的联系。

14、对偶单纯形法迭代中的主元素一定是负元素（a）

a、正确

b、错误

c、不一定

d、无法判断

15、对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（b）

a、换出变量

b、换入变量

c、非基变量

d、基变量

16、影子价格是指（d）

a、检验数

b、对偶问题的基本解

c、解答列取值

d、对偶问题的最优解

17、影子价格的经济解释是（c）

a、判断目标函数是否取得最优解

b、价格确定的经济性

c、约束条件所付出的代价

d、产品的产量是否合理

18、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为iwb=50元，

iwc=-80元，iya=0元，ixc=20元，则最好挑选（a）为调整格。

a、wb格b、wc格c、ya格d、xc格

19、在一个运输方案中，从任一数字格开始，（b）一条闭合回路。

a．可以形成至少b．不能形成

c、可以形成d．有可能形成x?

（2,4），x12?

（4,8）是某lp的两个最优解，则（d）也是lp的最优解。

20、运输问题可以用（b）法求解。

a、定量预测b、单纯形c、求解线性规划的图解d、关键线路

21、在运输问题的表上作业法选择初始基本可行解时，必须注意（ad）。

a、针对产销平衡的表；

b、位势的个数与基变量个数相同；

c、填写的运输量要等于行、列限制中较大的数值；

d、填写的运输量要等于行、列限制中较小的数值。

22、用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输

问题（a）

a、正确

b、错误

c、不一定

d、无法判断

23、通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题（c）

a、非线性问题的线性化技巧

b、静态问题的动态处理

c、引入虚拟产地或者销地

d、引入人工变量

24、动态规划方法不同于线性规划的主要特点是（ad）。

a、动态规划可以解决多阶段决策过程的问题；

b、动态规划问题要考虑决策变量；

c、它的目标函数与约束不容易表示；

d、它可以通过时间或空间划分一些问题为多阶段决策过程问题。

25、用dp方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（b）

a、正确

b、错误

c、不一定

d、无法判断

26、用dp方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（b）

a、正确

b、错误

c、不一定

d、无法判断

27、．动态规划最优化原理的含义是：

最优策略中的任意一个k-子策略也是最优的（a）

a、正确

b、错误

c、不一定

d、无法判断

28．动态规划的核心是什么原理的应用（a）

a、最优化原理

b、逆向求解原理

c、最大流最小割原理

d、网络分析原理

29．动态规划求解的一般方法是什么？

（c）

a、图解法

b、单纯形法

c、逆序求解

d、标号法

30．用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（b）

a、任意网络

b、无回路有向网络

c、混合网络

d、容量网络

31．动态规划的求解的要求是什么（acd）

a、给出最优状态序列

b、给出动态过程

c、给出目标函数值

d、给出最优策略

32．用动态规划解决生产库存的时候，应该特别注意哪些问题？

（bc）

a、生产能力

b、状态变量的允许取值范围

c、决策变量的允许取值范围

d、库存容量

33.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是（c）。

a、降低的b、不增不减的c、增加的d、难以估计的

34.最小枝权树算法是从已接接点出发，把（c）的接点连接上

a、最远b、较远c、最近d、较近

35.在箭线式网络固中，（d）的说法是错误的。

a、结点不占用时间也不消耗资源

b、结点表示前接活动的完成和后续活动的开始

c、箭线代表活动

d、结点的最早出现时间和最迟出现时间是同一个时间

36.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是（c）。

a、1200b、1400

c、1300d、1700

37.

15km，20km

25km，则（d）。

a、最短路线—定通过a点

b、最短路线一定通过b点

c、最短路线一定通过c点

d、不能判断最短路线通过哪一点

38.在一棵树中，如果在某两点间加上条边，则图一定（a）

a、存在一个圈

b、存在两个圈

c、存在三个圈

d、不含圈

39网络图关键线路的长度（c）工程完工期。

a．大于b．小于

c．等于d．不一定等于

40.在计算最大流量时，我们选中的每一条路线（c）。

a、一定是一条最短的路线b、一定不是一条最短的路线

【篇二：

奥鹏南开16春学期《数学大观》在线作业】

s=txt>一、单选题（共20道试题，共40分。

）

1.欧拉是世界上最高产的数学家之一，他出生于那个国家？

.法国

.德国

.瑞士

.俄罗斯

正确答案：

2.运筹学中经常需要在很多条件的约束下，寻找某一个问题的最优解。

在运筹学中，这种方法被称为：

.数理统计

.数学规划

.决策树

.启发性算法

正确答案：

3.在植物中会发现很多与黄金比例有关的现象，比如植物的叶序，这些现象存在的原因是.植物中的黄金比例只是偶然，没有什么特殊原因

.黄金比例令植物更加美观

.植物成长时，按照黄金比例生长的枝叶，可以更好地利用空间和阳光

.按黄金比例生长的植物，更符合人们的需要

正确答案：

4.迈一步通常是在半米左右，那么估计一亿步是多远的距离？

.相当于中国从东到西的距离

.相当于从中国上海到美国洛杉矶的距离

.相当于绕地球赤道一周多

.相当于从地球到月亮的距离

正确答案：

5.自然界中存在丰富的斐波那契数列，斐波那契数列来源于一个古老的数学问题，是由12世纪意大利数学家斐波那契在其书中所产生的。

斐波那契数列和黄金分割的关系是？

.黄金比例是斐波那契数列中的一项

.斐波那契数列相邻两项的比例逐渐逼近黄金比例

.黄金分割是指用斐波那契数列对一个量进行分割

.黄金比例是斐波那契数列的别名

正确答案：

6.运筹学是最为重要的应用数学分支之一，运筹学始于那个年代？

.20世纪20年代

.运筹学出现于二战时期

.公元前500年的春秋战国时期

.出现在17世纪的欧洲

正确答案：

7.欧几里得几何原本是综合了整个地中海地区的数学成就而得到的。

文献和资料的搜集对于学术的发展和知识的保存起着至关重要的作用。

对欧几里得的几何原本起到重要作用的古代图书馆是：

.亚历山大图书馆

.阿拉伯智慧宫

.罗马梵蒂冈教廷藏书

.大不列颠图书馆

正确答案：

8.我见到的所有天鹅都是白的我的同学所见到的所有天鹅都是白的所以天鹅是白的这个推理过程所使用的推理方法是：

.归纳方法

.演绎方法

.化归方法

.模型方法

正确答案：

9.人类的审美行为中，很多都与比例有关。

下面哪一种现象与比例无关？

.跳芭蕾舞时演员会踮起脚尖

.女士普遍喜欢高跟鞋

.对称的面部通常更为美观

.九头身的身材比例更为美观

正确答案：

10.拉玛努金是一位著名的数学天才，他来自于那个国家？

.英国

.巴基斯坦

.俄罗斯

.印度

正确答案：

11.一个具体的工程或者项目的完成通常需要团队成员之间的分工合作，如何安排时间能在最短时间内完成工作是一个重要问题。

运筹学中处理这种问题的分支是：

.数理统计

.排队论

.存储论

.网络规划技术

正确答案：

12.著名的哲学家尼采把人类精神分类两个方面，这两个方面分别由希腊的日神阿波罗和酒神狄俄尼索斯来代表，它们分别是

.邪恶和正义

.高贵和低贱

.理性和感性

.动物性和神性

正确答案：

13.中国在明代时第一次有了几何原本的译本，它的译者是一位中国数学家和西方传教士利玛窦。

这位中国数学家是：

.李善兰

.朱世杰

.徐光启

.杨辉

正确答案：

14.人平均每天要喝水1.5升到2升，如果按2升计算，那一生会喝掉多少的水？

.6,000升

.60,000升

.600,000升

.6,000,000升

正确答案：

15.下面哪一种的变化更接近于指数增长？

.小麦种植面积和总产量之间的关系

.正方形的面积与其边长之间的关系

.声音的大小和声源距离之间的关系

.历史上全球人口随时间的增长

正确答案：

16.博弈论使用数学方法研究竞争现象，现代博弈论起源的时间是？

.公元前500年的希腊

.17世纪

.20世纪20年代

.第二次世界大战时期

正确答案：

17.分形几何被称为是“大自然的几何学“，它的创始人是

.纳什

.曼德布罗特

.黎曼

正确答案：

18.“四假象说”说明列举了人类获得确切知识所面临的一些困境，这种学说的创造者是：

.笛卡尔

.斯宾诺莎

.培根

.亚里士多德

正确答案：

19.统计显示一个男的每天说话2000—4000字左右，按3000字计算。

那他一生说话将会有多少字？

寿命按照80岁来估计

.900000

.9000000

.90000000

.900000000

正确答案：

20.博弈论的另一种困境是公地悲剧，它是指当少数人获利，成本由多数人承担时会出现的困局，有很多的适用范围。

下面哪一种困境不能用公地悲剧来解释？

.对工厂的监管不力，工厂排放污水导致河流污染

.各个国家为各自发展的需要，不加限制的排放温室气体，导致全球变暖

.在一块公共牧地上，所有人都尽可能的增加放牧数量，引起土地沙化

.产品质量监管不严，导致大量假冒伪劣产品出现

正确答案：

《数学大观》在线作业

二、多选题（共10道试题，共20分。

）

1.下列关于数学和艺术的关系的说法中，错误的是：

.数学和艺术是完全不相关的两个领域

.数学就是艺术，艺术就是数学

.艺术中的形式美法则和数学有着深入联系

.数学是理性的代表，数学家必须尽可能的去除感性

正确答案：

2.沃尔夫奖是数学家的终身成就奖，以表彰获奖数学家对数学所作出的重要的贡献。

在获得沃尔夫奖的数学家中，有两位华人数学家，他们是师生，成为华人的骄傲。

他们是：

.陈省身

.丘成桐

.华罗庚

.陈景润

正确答案：

3.“四假象说”说明列举了人类获得确切知识所面临的一些困境，包括

.种族假象

.洞穴假象

.市场假象

.剧场假象

正确答案：

4.下列关于运筹学的描述中，那种描述是正确的

.运筹学使用数学方法研究如何做事更好

.运筹学能够为决策提供良好依据

.运筹学始于公元前500年的春秋战国时期

.运筹学广泛的使用计算机

正确答案：

5.人类的审美行为中，很多都与比例有关。

下面哪一种现象与比例有关？

.跳芭蕾舞时演员会踮起脚尖

.女士普遍喜欢高跟鞋

.对称的面部通常更为美观

.九头身的身材比例更为美观

正确答案：

6.柯尼斯堡问题的解决，引发了对数学分支的研究不包括

.微积分

.图论

.非欧几何学

.射影几何学

正确答案：

7.运筹学是一个重要的应用数学分支，它的精髓在于数学方法的运用。

下面的那些问题是运筹学所要解决的问题？

.运输问题

.排队问题

.国家发展数据的统计

.项目工作最优化

正确答案：

8.博弈论有很多应用领域，下列哪些领域是博弈论的应用领域?

.使用博弈论进行工业设计

.使用博弈论研究市场竞争

.使用博弈论研究战争

.使用博弈论研究生物竞争和进化

正确答案：

9.分形几何所处理的形状最为根本的特征不包括

.属于自然的而不是人造的

.形状的不规则

.连续和平滑

.自相似性和尺度不相关性

正确答案：

10.著名的哲学家尼采把人类精神分类两个方面，这两个方面分别由希腊的日神阿波罗和酒神狄俄尼索斯来代表，它们分别是

.邪恶

.正义

.理性

.感性

正确答案：

16春学期《数学大观》在线作业

【篇三：

算法合集之《由图论问题浅析算法优化》】

>武钢三中贾由

【摘要】

论文以图论问题为对象、以算法优化为主题、以分类和举例为基本模式进行了一系列探讨。

第一部分引言简单地介绍了图论与信息学竞赛的关系；第二部分分析了算法优化的根本途径：

寻找特别之处；第三部分从算法的纠错入手，详细讨论其中的方法，进一步展示了发现问题的特殊点对算法优化的推动作用。

【关键字】

图论算法优化错误分析

【正文】

一、引言

图论是一个十分有趣而且与信息学竞赛联系紧密的数学分支。

随着图论问题的日渐增多，一些经典图论模型与它们的相关算法已成为竞赛中不可或缺的知识。

与此同时，题目也越来越注重模型的转换与算法的优化。

这意味着在将知识转变为分数的过程中，我们需要做出更多的努力。

本文以其中的算法优化为主题，尝试了一些相关的归纳与讨论。

另外，由于黑箱测试的缘故，我们所体验到的信息学可以说是一个以结果论成败的学科。

这是很好的，因为结果是对历史的总结。

但无论如何，对于一次以优化为主题的讨论来说，得到的最优算法仅仅是用来证明我们的优化过程是切实而有效的。

二、寻找特别之处——优化的根本途径

2.1介绍

每一个让算法更加漂亮的改进都可以称为优化。

不过在整体考虑一个问题时，优化的过程应该包括从原始算法到一个优秀算法当中的所有改进。

这通常是一个逐步发现并利用问题的特殊之处、使算法更有针对性的过程。

做好优化的根本在于找出题目的特别之处。

这是一个宽泛的想法，没什么步骤和诀窍可言。

解决具体问题时，我们只能靠广泛的优化经验、充足的耐心以及一部分的灵感因素。

关于经验，之前的几篇论文已经分别就一些有共同特征的题目介绍了深入挖掘信息的具体过程。

这一章不再深入探讨某类问题，而是通过一个经典算法对“寻找特别之处”作出解释。

2.2例题

[例]二分图的最大匹配1

图的匹配指图中任何两条边都没有共同顶点的子图，二分图最大匹配问题旨在求出二分图中边数最多的一个匹配。

求解这个问题最基本的方法是将它转换成一个网络流模型：

为了方便叙述，我们将二分图的两个顶点集合成为a和b。

在图中加入源点和汇点，从源点向a中的每个点引一条边，容量为1；从b中的每个点向汇点引一条容量同样为1的边。

然后将原图中的边作为有向边添加进来，由a指向b，容量为1。

新图中用容量限制了每个点最多只能被一条边覆盖、每条边只能被记一次。

容易看出，这个图的最大流与最大匹配中的边数相等。

通过最大流算法，我们同样可以得到选边的具体方案。

最显然的一个优化是不记录容量，所有边的容量都是一。

其次，这个网络中的可增广链很特别，它一定由源点开始，在点集a和点集b之间做若干次往返，再由b到达汇点的。

搜索时可以不考虑第一条与源点连接的边和最后一条与汇点连接的边，直接从点集a中的一个未匹配点开始到点集b中的一个未匹配点结束。

可以想象，在广搜的目标路径中减少两条边对于需要扩展的结点数的影响是巨大的。

这就是匈牙利算法的基本思想。

基本的网络流算法与匈牙利算法的时间复杂度其实没有区别2，但是后者在所需空间、编写难度以及实际的运行时间上都拥有绝对的优势。

几乎可以肯定匈牙利算法最初不是由上面这样的优化得到的，但这两种优化手段在网络流算法的设计中是很实用的：

根据图的特殊性简化存储方式、量身定制搜索可增广链的方法。

[例]牧场规划3

小可可的好朋友sealock最喜欢吃花生了，于是借用了小可可的牧场从事花生选种试验。

他以网格的方式，非常规整地把牧场分割成m*n个矩形区域（m*n≤5000），由于各个区域中地水面、沼泽面积各不相同，因此各区域地实际可种植面积也各不相同，已知区域（i,j）地可种面积使a（i,j）。

每个区域种最多只能种植一个品种地花生。

可种植面积为零地区域不能被选择用来从事选种试验，同时为了防止花粉传播到相邻区域造成试验结果不正确，任何两个相邻的区域都不可以同时种植花生。

这里说的相邻指的是两个区域有公共边，仅仅有公共点的两个区域不算做相邻。

小可可准备帮助sealock规划一下如何选择种植区域，才能使得实际可种植面积总和最大。

对应选择方案与网络的割

建立方案与网络的割之间一一对应关系的方法在[4]中曾有所描述，我们根据这道题再回顾一遍。

1

图1建立网络

将试验田转化为点、并连接相邻的试验田后可以发现，我们得到的是一个二分图。

通过对原图的黑白染色，可以把其中的一部分称为白点、另一部分称为黑点。

由二分图建立网络：

加入源点和汇点，从源点向每个白点引一条边，容量为白点对应试验田的面积；从每个黑点向汇点引边，容量为该黑点的对应面积。

最后将相邻点之间的边改为网络中的边，由白点指向黑点，容量为正无穷。

方案对应的割：

将方案中所选的白点和未选的黑点再加上源点划为一个集合，其它点划到另一个几何，就得到了一个割。

直接把这个过程反过来，我们很容易由割得到一个方案。

在这个对应中：

一、不合法方案对应的割均为正无穷；二、在合法方案对应的割中，割上的点代表了方案没有取到的边。

所以当割的容量最小时、方案选取的面积最大，而根据最大流最小割定理，我们可以通过求网络最大流得到它的最小割。

广搜可增广链

这同样是由二分图转换来的网络，但是边的容量一般化了。

我