数学建模习题

数学建模（i）习题。习题6

1．求解指派问题，其系数矩阵为：

2．求图6-1的一颗最小生成树。

3．假如你开了一家婚姻介绍所，你会遇到以下两类为题之一：

1）如果你并非以盈利为目的（只是为了做好事），在你了解了前来登记的男女青年。

的个人情况以及他（她）们对对方的基本要求以后，你希望知道第一批至多可以介绍多少对男女青年见面。请分析这一问题，建立模型并设计一个求解方法。

2）如果你开办婚介所是为了盈利，每一前来登记的男女青年还写下了假如你介绍。

成功愿意支付多少钱的介绍费，情况又会有什么不同？请写出这一问题的数学模型，你有什么办法可以求解它？试举一实例并用算法求解之。

4．作出图6.4对应的增广网络，从增广网络中你能发现什么现象吗？（提示：请想一下，如果你想进一步增加由1到6的流量，应当如何改造网络）

5．酋长嫁女儿也可化为最小费用最大流问题的一个实例，请利用最小费用最大流问题的算。

法来求解酋长嫁女儿问题。

6．求解右图给出的中国邮路问题，其中a为邮局，邮递员必a443

须从邮局出发最后返回邮局47．（1）试构造一个可用来求图g(v, e)的最小生成树的标号算642

法8（2）任意作一个有7个顶点的图g，设计一个可让计算机41

记录这个图的方法1

7（3）对你所作的图g的每边赋以一个权使之成为网络，应5

用你设计的算法求其最小生成树33

38．假如你能设计出求解tsp问题的多项式时间算法a，我就可44

以利用你的算法来求解哈密顿圈问题。利用方法如下：如。

果图g是完全图，g中当然含有哈密顿圈，例如1-2-……n-1就是一个。如果图g不是完全图，加入虚边使其成为完全图。在原先就有的边上赋权1，在虚边上赋权2，于是原图是否有哈密顿圈等价于新网络对应的tsp问题的最优旅行圈长度是否为n，我可以利用算法a来判断图g是不是哈密顿图。

（1）请想一下为什么我能这样作出判断（2）为什么这样就能知道tsp问题一定是np难的？

9．给定平面上的九个点：a、b、c、d、e、f、g、h、i，两两间的距离如下图所示，试用。

近似算法1和近似算法2求解此九点决定的旅行商问题的近似最优解。10．证明：一维bin-packing问题时np难的。

11．利用上题结果证明两维、三维bin-packing问题是np难的。12．证明：对一维bin-packing问题的nf算法，有：

nf(i)2opt(i)

13．证明0-1线性规划是np难的，（提示：划分为题和背包问题均可写成0-1线性规划，如0-1线性规划问题可在多项式时间内求解，则划分问题和背包问题均可在多项式时间内求解，然而，我们已经知道，划分问题和背包问题是np难的）

14．设有7台机器已损坏需检修，各机器检修所需时间分别为
小时，各机器停工1小时给工厂造成的损失分别为
（百元），修理工只有一名。

1）试求一个使工厂总损失最少的检修顺序。

2）将此实例推广到一般情况（即有n台机器要检修，各机器检修所需时间及停工1

小时所造成的损失均已知），用三参数法来表示，此问题为1//σwjcj，试给。

出能求出此问题的一个最优加工顺序的算法。

3）证明你的算法必能求得最优顺序。

数学建模习题

数学建模 i 习题。习题 21 兔子出生后两个月就能生小兔，如果最初你养了刚出生的一雌一雄两只小兔，长成后兔子每月生一次且恰好生一雌一雄的一对，出生的小兔年内均不死，问一年后你家里共有多少对兔子？注 本问题关系到一个十分重要的数列 菲波那奇数列 2 有甲乙二人，乙对甲进行盯梢，甲开始时沿甲乙二人连线...

数学建模习题

数学建模 i 习题。习题 21 兔子出生后两个月就能生小兔，如果最初你养了刚出生的一雌一雄两只小兔，长成后兔子每月生一次且恰好生一雌一雄的一对，出生的小兔年内均不死，问一年后你家里共有多少对兔子？注 本问题关系到一个十分重要的数列 菲波那奇数列 2 有甲乙二人，乙对甲进行盯梢，甲开始时沿甲乙二人连线...

数学建模习题

数学建模 i 习题。习题 11 试用右图1 12证明余弦定理。2 取一根很长的绳子，它的长度恰好能紧贴地球表面绕赤道一周。如果把绳子再接长15米，将其悬在空中绕赤道一周 如果可以做到的话 问 你是否可以从绳子的下方自由地穿行？3 在一个等边三角形的内部寻找一点，使得该点到三边的距离之和最小。如果是普...