chapter3

Report
第三章应用实例
§1、确定比赛的胜负
一、问题
设有5个球队进行单循环赛,已知它们
的比赛结果为:
1对胜2,3队;2队胜3,4,5对;
4队胜1,3,5队;5队胜1,3队,
设按胜的次数多少排名次.
若两队胜的次数相同,则按
直接胜与间接胜的次数之
和的多少排名次.
所谓间接胜,即若1队胜2队,2队
胜3队,则称1队间接胜3队.
试为这5个队排出比赛名次.
二、分析
用平面上的 5个点表示五个队,若一
个队直接 胜另一个队则用有向线
段连接.
可以看出2,4队直接胜的次数相同,
但2队间接胜5场,而4对间接胜4
场,所以不难排出2对为冠军,4队
为亚军,1队为第三名,五队第四
名,3对第五名.
2,4,1,5,3
如果参赛队很多,我们应该
怎样解决呢
?
关于上面那个图,我们给出一些
术语.
顶点集: V  v1 , v 2 , v 3 , v 4 , v 5 
边集:若i队直接胜j队,则从i到j的
有向线段称为有向弧,或边。记
为有序队 ( v , v )
i
j
A  ( v i , v j )
若i,j间存在k个顶点使得有向弧
连接到j,则称i,j间存在长为k+1的路。
因此若i队间接胜j队,则它们之
间必存在长为k(k大于等于2)的路.
如何用矩阵来体现这些结果呢
?

1 ( v i , v j )  A
设 a ij  
0
(
v
,
v
)

A

i
j

定义矩阵 M  ( a ij ) n  n n为顶点的个数
则每个图可用一个矩阵表示,
称之为图的邻接矩阵。
定理 : 设 M  ( a ij ) n  n 为图 G  (V , A )的
邻接矩阵,则
k
M 的 i 行 j 列的元素等于
v i 与 v j 之间长为 k 的路的数目。
注 : 由此可知 , M 中每行和表示了
每个队直接胜的场数
就表示直接胜的次数相
, 若行和相等,
同。
2
由此继续算 M  M 的行和,若
还有两行和相等,继续
往下算,
直至行和各不相同。
下面我们利用图的邻接矩阵来求
解这个问题.
三、解:

1 ( v i , v j )  A
设 a ij  
0
(
v
,
v
)

A

i
j

M  ( a ij )5  5
它的邻接矩阵M如下:
注:每一行的和代表相应的
队直接胜的次数
即算 M  M
2
 M
3
的行和,直至各行和都
   M
k
不相等,
然后比较大小。
四、Matlab实现
>> M=[0 1 1 0 0;0 0 1 1 1;0 0 0 0 0;
1 0 1 0 1;1 0 1 0 0];
>> s1=sum(M')
s1 =
2 3 0 3 2
>> s2=sum(M'+(M^2)')
s2 =
5
8
0
7
4
所以2队为冠军,4队为亚军,1队为
第三名,五队第四名,3队第五名.
当然,若有计算机程序基础,
对队数比较多的情况,你可直接写程
序来实现整个计算过程。
下面的脚本程序供大家参考。
利用图的“邻接矩阵”的思想,我
们来看下面的例子.
例、简单匹配搜索引擎的原理。
假设数据库有下列书,题目分别是:
B1.运用线性代数
B2.初等线性代数
B3. 初等线性代数及应用
B4. 线性代数和它的应用
B5. 线性代数及应用
B6.矩阵代数及应用
B7. 矩阵理论.
它们的关键词按顺序排列如下:
代数,应用,初等,线性,
矩阵,理论.
如果搜索“线性代数应用”,请给出
相匹配的搜索结果。
解:
设 a ij
1

 
0

第 i 个关键词出现在
第 j 本书的题目中
不出现
书
关键
词
B1
B2
B3
B4
B5
B6
B7
代数 1
1
1
1
1
1
0
应用 1
0
1
1
1
1
0
初等 0
1
1
0
0
0
0
线性 1
1
1
1
1
0
0
矩阵 0
0
0
0
0
1
1
理论 0
0
0
0
0
0
1
于是我们可得数据库的“邻
接矩阵”
1 1 1 1 1 1

1 0 1 1 1 1

0 1 1 0 0 0
A  
1 1 1 1 1 0

0
0
0
0
0
1


0 0 0 0 0 0
0

0

0

0

1

1
注:此“邻接矩阵”每一列代表
了该本书的信息,第j列的列和
表示第j本书包含的关键词的个
数
把数据库里的关键词排成列看
作一个向量,于是任意一个
搜索也可用向量表示,若包
含第i个关键词,第i个分量取
值为1,否则取值为零。
搜索“线性代数应用”,即
搜索向量为
1
 
1
 
0
x   
1
 
0
 
 
0
3
 
2
 
3
 
T
A x  3
 
3
 
2
 
0
计算
注:结果中的
每个分量就
表达了每一
本书与你搜
索的东西相
匹配的词条
数
故搜索结果为第一、三、四、五
本书的题目。
§2、平板的稳态温度分布
一、问题
在热传导的研究中,需要确定某一快平板
的稳态温度分布,设下图中的平板代表一
条金属梁的截面,忽略垂直方向的热传导.
内部节点的温度近似等于与它最接近的
上下左右节点温度的平均值.
(1)写出内部节点a,b,c,d所满足的方程组;
(2)求解此方程组。
解: 根据已知条件,
可列出如下方程:

x a


x
 b

x
 c

x
 d




10  20  x b  x c
4
40  20  x a  x d
4
10  30  x a  x d
4
30  40  x b  x c
4
,
,
,
.
整理得:
4x a  x b  x c 

 x a  4x b  x d

 x a  4x c  x d
 x  x  4x
b
c
d

30 ,
 60 ,
 40 ,
 70 .
用Matlab求解:
>> A=[4 -1 -1 0;-1 4 0 -1;-1 0 4 -1;
0 -1 -1 4];
>> b=[30;60;40;70];
>> rref([A,b])
ans =
1.0000
0
0
0
0 1.0000
0
0
0
0 1.0000
0
0
0
0 1.0000
20.0000
27.5000
22.5000
30.0000
故a,b,c,d四点的温度
分别为:
20,27.5,22.5,30
摄氏度。
§3、投入产出分析
一、问题
一个城镇有三个主要生产企业:
煤矿,电厂和地方铁路
作为它的经济系统.
已知生产价值一元的煤,需消耗
0.25元的电费和0.35元的运输费;
生产价值一元的电,需消耗
0.40元的煤费、0.05元的电
费和0.10元的运输费;
而提供价值一元的铁路运输费,
需消耗0.45元的煤、0.10元的电费
和0.10元的运输费.
假设在某个星期内,除了这三个企
业间彼此需求,
煤矿得到50000元的订单,
电厂得到25000元的电量供应要求,
地方铁路得到价值30000元的运输要求。
试问:
(1)这星期这三个企业各应生产多少产值
才能满足内外需求?
(2)
除了外部需求,试求这星期各
企 业之间的消耗需求,同时求
出各企业新创造的价值;
(3) 如果煤矿需要增加总产值
10000元,它对各个企业的产
品或服务的完全需求是多少?
二、分析
这是一个小型的经济投入产出模型,
在经济系统中,有下列经济规律:
1. 对每一部门,物资消耗和新创造
的价值等于它生产的总值.即投入
和产出之间的平衡关系:
中间产品(作为系统内各企业的消
耗)+最终产品(外部需求)=总产品,
称之为分配平衡方程组
2. 对每一产品,支付系统内各产品
的消耗加上新创造的价值等于它
的总产值.即
系统内各企业产品的消耗+新创造
的价值=总产值,
称之为消耗平衡方程组
3. 企业在进行生产或提供服务时,
对任何一个产品的直接消耗(直
接消耗系数)也蕴含着对其它产
品的间接消耗.
完全消耗系数:是指企业生产单
位产值的产品而对其它企业产品
的总消耗值.即
设煤矿、电厂和地方铁路生产单
位产值对煤、电和铁路运输的直
接消耗系数和完全消耗系数分别
为
a ij 和 bij , i , j  1, 2 ,3
则
3
a ij 
b
k 1
ik
a kj  b ij ,
 b11

B   b 21
b
 31
b12
b 22
b 32
b13 

b 23  ,

b 33 
称之为完全消耗矩阵.
三、求解
(1)设煤矿、电厂和地方铁路在这
星期生产的总产值分别为
x1 ,
x2 ,
 0 


 1   0 . 25  ,
 0 . 35 


x3
( 元 ),
 0 . 40 


 2   0 . 05  ,
 0 . 10 


 0 . 45 


 3   0 . 10 
 0 . 10 


A  ( 1 ,  2 ,  3 ) 
 0

 0 . 25
 0 . 35

0 .4
0 . 05
0 . 10
称之为直接消耗矩阵。
0 . 45 

0 . 10 

0 . 10 
由分配平衡方程组关系,有向量方程
 0 
 0 . 40 




x1  0 . 25   x 2  0 . 05  
 0 . 35 
 0 . 10 




 0 . 45   50000

 
x 3  0 . 10    25000
 0 . 10   30000

 
  x1 
  
   x2 
 x 
  3
令
 x1 
 
X   x 2 ,
x 
 3
 50000

Y   25000
 30000



,


X称为产出向量,Y称为最后需求向量
或最终产品向量,则前向量方程可
写成矩阵形式为
AX  Y  X .
有
( E  A) X  Y 
1
X  ( E  A) Y .
现用Matlab来求解此方程组
>> A=[0 0.4 0.45;0.25 0.05 0.1;0.35
0.1 0.1];
>> Y=[50000;25000;30000];
>> X=(eye(3)-A)\Y
X=
1.1446e+05
65395
85111
故 煤矿、电厂和铁路运输各应生产
114460元、65395元和85111元的
产值才能满足内外需求。
注:求出 X 后,
 0 


x1 1  x1  0 . 25  表示三个企业为煤矿
 0 . 35 


总产值 x1所做的产品消耗(投入
);
 0 . 40 


x 2 2  x 2  0 . 05  表示三个企业为电厂
 0 . 10 


总产值 x 2 所做的产品消耗(投入
);
 0 . 45 


x 3 3  x 3  0 . 10  表示三个企业为铁路
 0 . 10 


总产值 x 3 所做的产品消耗(投入
);
(2)令 T  ( x  x  x  ) 
1 1
2
2
3 3
 x1

( 1  2  3 ) 


 x1

 A


x2




x3 
x2




x3 
矩阵T里的每一行即为每一个企
业分别用于企业内部和其它
企业的消耗。
由消耗平衡方程组,新创造的价值应
等于总产值减去系统内各企业对该产
品的消耗需求。
现用Matlab来求解
>> T=A*diag(X)
T=
0
28615
40060
>> X-sum(T)'
26158
3269.8
6539.5
38300
8511.1
8511.1
ans =
45783
29428
29789
故 各企业新创造的价值为
z1  45783 ( 元 ),
z 3  29789 ( 元 )
z 2  29428 ( 元 )
(3)由直接消耗系数和完全消耗系数
之间的关系有
A  BA  B  B  A ( E  A )
 ( E  A)
1
E
>> B=inv(eye(3)-A)-eye(3)
1
B=
0.45658
0.44818
0.61625
0.69813
0.2799
0.4137
0.80586
0.3663
0.4652
故 若煤矿需增加总产值10000元,对煤
的完全需求为0.45658万元,对电的
完全需求为0.44818万元,对铁路的
完全需求为0.61625万元。
注:可把上述问题的结果列表如下,
(投入产出表)
§4、艺术建筑模型
一、问题
假定一艺术建筑的局部为一二次曲面,
其在某空间直角坐标系下的方程为
3 x  4 y  5 z  4 xy  4 yz  1  0
2
2
2
试判断这个二次曲面的类型,并写出所
用的变换。
二、分析
判断二次曲面的形状,先用正交变
换化为标准型,由标准方程确定形状。
这些计算问题都可用Matlab来实现。
三、求解
解:由
3 x  4 y  5 z  4 xy  4 yz  1  0
2
有
2
X
T
3
其中

A  2
0

2
AX  1
2
4
2
0

2
5 
x

X  y

z






>> A=sym([3 2 0;2 4 2;0 2 5]);
>> [V,D]=eig(A)
V=
[ 2, 1/2, -1]
[ -2, 1, -1/2]
[ 1, 1, 1]
D=
[ 1, 0, 0]
[ 0, 7, 0]
[ 0, 0, 4]
>> s=sqrt(sum(V.*V));
>> V./[s;s;s]
ans =
[ 2/3, 1/3, -2/3]
[ -2/3, 2/3, -1/3]
[ 1/3, 2/3, 2/3]
正交矩阵
 2
 3

2

Q  
 3

 1

 3

2
3

1
3
2
3
1

3

2
3

2

3
令 X=QY,即
 2

 x1 
 3
 
 2
x2   
3
 

x
1
 3


 3
2

3
1

3
2
3
为所用的正交变换。
1

3  y 1 
2  
y


2

3  

2 y3 


3
此时二次曲面方程化为
2
2
y 1  4 y 2  7y 3
2
 1
故原二次曲面为椭球面,
三个长轴长分别为
1
1、0.5和
7
§5、杂交育种的稳定性
一、问题
假设某农场的试验场中某种植物的
基因型为 AA ,
A
和  ,
三种基因型各占1/3. 已知
AA
型基因属于优良品种,试分析
下列三种方案中的哪一种方案
有利于培养出优良品种?
,
方案(Ⅰ):采用
AA
型的植物与每种
基因型植物相结合的方法
培育植物后代;
方案(Ⅱ):采用
A
型的植物与每种
基因型植物相结合的方法
培育植物后代;
方案(Ⅲ):将具有相同基因型植物
相结合。
后代可能的基因型概率如下表
亲本的基因
AA - AA
后
代
的
基
因
型
AA
1
A
0

0
AA - A 
1
2
1
2
0
AA - 
0
1
0
A - A
1
4
A  - 
 - 
0
0
1
1
2
2
1
1
4
2
0
1
二、分析
考虑第n代作物中各种基因型所
占的比例,从而确定出哪一种
方案优。
由所给出的可能的基因型组合
表,可建立递推关系式,再求
解。
三、求 解
设 a n ,b
c
,
n
n
分别代表在第n代作物中
AA 型, A  型及

型所占的比例,
n  1, 2 , 
则由题意有
且
a 0  b0  c 0 
a 0  b0  c 0  1
1
3
方案(Ⅰ):由表知,第n代的基因
由第n-1代的基因决定,有
1

a

a

b
n
n

1
n 1

2

1
 b n  c n 1  b n 1
2

c

0
n


n  1, 2 , 
 an

  bn
c
 n
设
X
(n)
M1
则有
X
1

 0
0

(n)


,


n  0 ,1, 2 , 
0

1

0
1/ 2
1/ 2
 M1X
0
( n 1 )
,
n  1, 2 , 
从而有
X
(n)
 M 1X
( n  1)
M X
2
1
(n2)

 M X
n
1
(0)
下用Matlab进行计算,利用矩阵对角化
计算方阵的幂。
>> M1=sym([1 1/2 0;0 1/2 1;0 0 0]);
>> x0=sym([1/3,1/3,1/3]');
>> [V,D]=eig(M1)
V=
D=
[ 1, -1, 1]
[ -2, 1, 0]
[ 1, 0, 0]
[ 0, 0, 0]
[ 0, 1/2, 0]
[ 0, 0, 1]
有三个不同特征值,故可对角化,即
V
1
M 1V
0

 0

0

0
1/2
0
0

0  D

1
n
n
1
M 1  VD V
有
>> syms n;
>> xn=V*D^n*V^(-1)*x0
xn =
1 - (1/2)^n
(1/2)^n
>> limit(xn,n,inf)
0
ans =
1
0
0
即若一直使用方案(Ⅰ),将得到纯种
AA
对方案(Ⅱ),
M
2
1 / 2

 1 / 2

0

1/ 4
1/2
1/ 4


1 / 2

1 / 2
0
>> M2=sym([1/2 1/4 0;1/2 1/2 1/2;
0 1/4 1/2]);
>> x0=sym([1/3,1/3,1/3]');
>> [V,D]=eig(M2)
V = [ 1, -1, 1]
>> xn2=V*D^n*inv(V)*x0
[ -2, 0, 2]
[ 1, 1, 1]
xn2 = 1/4
D = [ 0, 0, 0]
1/2
[ 0, 1/2, 0]
1/4
[ 0, 0, 1]
对方案(Ⅲ),
M
3
1

 0

0

1/ 4
1/2
1/ 4
0

0

1
>> M3=sym([1 1/4 0;0 1/2 0;0 1/4 1]);
>> x0=sym([1/3,1/3,1/3]');
>> [V,D]=eig(M3)
V = [ 1, 1, 0]
[ -2, 0, 0]
[ 1, 0, 1]
D = [ 1/2, 0, 0]
[ 0, 1, 0]
[ 0, 0, 1]
>> xn3=V*D^n*inv(V)*x0
xn3 = 1/2 - (1/2)^n/6
(1/2)^n/3
1/2 - (1/2)^n/6
>> limit(xn3,n,inf)
ans =
1/2
0
1/2
三种方案比较,方案(Ⅰ),将得到纯种
AA,有利于培养出优良品种。

similar documents