(组合数学)第5章区间设计.ppt

《(组合数学)第5章区间设计.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学第二部分讲课老师：张承钿2011.11.091第5章区组设计2011.11.092内容问题的提出拉丁方与正交的拉丁方域的概念Galois域GF(p)正交拉丁方的构造正交拉丁方的应用举例均衡不完全的区组设计区组设计的构成方法Steiner三元素Kirkman女生问题2011.11.093问题的提出◆有一块梯田种植3种不同的农产品A、B、C。由于高度、方位不同，所有其自然条件有差异。按图5-1的(a)种植，每种产品只在同层出现；而按图5-1的(b)种植，则每种产品只在同一方位出现；按图5-2种植，

2、则每种产品即在同层出现，又同一方位出现。显然，按图5-2种植，实验结果较准确。◆测试4种轮胎，同一牌子在汽车不同位置磨损程度不同，所以每种不能只测试一个轮胎，用4辆小汽车A、B、C、D参加测试，如右图所示。这个测试的特点是，每一种品牌的轮胎都在不同的汽车和不同的位置作了安排。每种轮胎都用了4次。测试的次数也均衡，其中A、B、C、D是汽车的代号，矩阵的元素是轮胎的品牌代号。2011.11.094问题的提出◆再论梯田种植问题农作物类：Ａ、Ｂ、Ｃ梯田高度：高、中、低日照方向：东、南、西进一步的问题：▲种子是

3、买来的，三家种子公司都提供这些种子，价钱差不多▲三种农作物的出售价格也差不多，只是播种方式不一样▲实验的目的是比较出哪家公司的种子质量好，哪种作物产量高。？怎样安排实验分析一：下面方法是否可行如果把上面每块地（共九块）再分成三小块，每小块种上一家公司的作物问题：每个小块的面积太小的话，无法判别产量分成三次播种季节，每个季节种一家作物问题：分三个季节的话，时间太长分析二：下面结论是否成立种子公司生产水平高，它的种子质量好，即公司X比公司Y好，则X的种子A、B、C应该比Y的种子A、B、C都相应的质量好。农作物

4、的产量不依赖于公司，即作物A比B产量高，则每家公司的作物A比B产量都高。2011.11.095问题的提出◆重新描述梯田种植问题农作物类：Ａ、Ｂ、Ｃ梯田高度：高、中、低日照方向：东、南、西种子公司：Ｘ、Ｙ、Ｚ假如各个公司的实际产量如下：即：公司X的A作物产量最高？：有没有办法，只在一个季节内种植后，就能判别出结果？2011.11.096问题的提出◆重新描述梯田种植问题农作物类：Ａ、Ｂ、Ｃ梯田高度：高、中、低日照方向：东、南、西种子公司：Ｘ、Ｙ、Ｚ在九块田分别种植三家公司的三种农作物，寻找如下方案的解：▲每行

5、（梯田高度）包含三个公司，及三种作物▲每列（日照方向）包含三个公司，及三种作物例如下图方案：　　　　　　　具体产量：　　　　　　　　正交拉丁方：各个作物的产量：　　　　　　各个公司的产量：2011.11.097拉丁方与正交拉丁方◆拉丁方的定义：由数1,2,...,n构成的n×n矩阵：如果数1,2,...,n中的每个都在每行和每列各出现一次，则称其为n阶拉丁方。前面的4阶矩阵是拉丁方。如果把图5-2中的A、B、C用1、2、3代替，则我们得到一个3阶的拉丁方。◆36军官问题有6个不同地区的6种不同军衔的军官

6、各一名，共36名。现要将他们排成6×6的一个方阵，要求做到：(a)每行、每列都有军官来自6个地区；(b)每行、每列都有6种军衔的军官每个军官都有二个标志，即军衔和地区。我们把军衔按1至6编号，把地区也按1至6编号，用(i,j)表示某军官的来自i号地区，其军衔是j号。如果我们不考虑军衔，只寻找满足条件(a)的矩阵，则问题是求6×6的拉丁方。同样，不考虑地区，只寻找满足条件(b)的矩阵，则也是求6阶拉丁方。当我们把6×6方阵中的军官用其军衔号i和地区号j组成的数偶(i,j)替代后，组成的方阵就满足：数偶(i,

7、j)的第一个数组成一个6阶拉丁方，第二个数也组成一个6阶拉丁方，且数偶(i,j)是唯一的。2011.11.098拉丁方与正交拉丁方◆正交拉丁方的定义：中的n×n个数偶　　　　互不相同，则称A和B是互相正交的拉丁方。◆例子5-1矩阵都是3阶拉丁方，而方阵中的9对数偶不同，故A和B是正交的。36名军官问题实际上就是求一对6阶的正交拉丁方。并不是任意的n阶都有正交拉丁方。36名军官问题就是没有解的。2011.11.099拉丁方与正交拉丁方◆正交拉丁方的应用正交拉丁方问题有实际的应用，例如测试药物：有三种治发烧的

8、药和三种治感冒的药配合起来给三位病人进行医疗实验，要求在三天内每人都服过这几种药，要试验出哪种退烧药和感冒药配合起来的疗效最佳。用上述的二个3阶正交拉丁方，就可解决这个问题。假设第h行、第k列的元素是(i,j)，我们就在第h天让第k号病人服用第i种的治发烧的药和第ｊ种的治感冒的药。具体例子就是，在第二行、第三列是数偶(1,3)，则在第二天三号病人服用第一种治发烧的药和第三种的治感冒的药。◆引理5-1设A是拉丁方，则A的转置A’