转动可分解设计的构造及其应用毕业论文.doc

本 科 毕 业 论 文 题 目 转动可分解设计的构造及其应用 毕业设计 论文 原创性声明和使用授权说明 原创性声明 本人郑重承诺 所呈交的毕业设计 论文 是我个人在指导教师的指导下进行的研究工作及取得的成果 尽我所知 除文中特别加以标注和致谢的地方外 不包含其他人或组织已经发表或公布过的研究成果 也不包含我为获得 及其它教育机构的学位或学历而使用过的材料 对本研究提供过帮助和做出过贡献的个人或集体 均已在文中作了明确的说明并表示了谢意 矚慫润厲钐瘗睞枥庑赖 作 者 签 名 日 期 指导教师签名 日 期 使用授权说明 本人完全了解 大学关于收集 保存 使用毕业设计 论文 的规定 即 按照学校要求提交毕业设计 论文 的印刷本和电子版本 学校有权保存毕业设计 论文 的印刷本和电子版 并提供目录检索与阅览服务 学校可以采用影印 缩印 数字化或其它复制手段保存论文 在不以赢利为目的前提下 学校可以公布论文的部分或全部内容 聞創沟燴鐺險爱氇谴净 作者签名 日 期 原 创 性 声 明 本人声明 所呈交的论文是本人在导师指导下进行的研究成果 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已发表或撰写过的研究成果 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 残骛楼諍锩瀨濟溆塹籟 签 名 日 期 本论文使用授权说明 本人完全了解南通大学有关保留 使用学位论文的规定 即 学校有权保留论文及送交论文复印件 允许论文被查阅和借阅 学校可以公布论文的全部或部分内容 酽锕极額閉镇桧猪訣锥 保密的论文在解密后应遵守此规定 学生签名 指导教师签名 日期 南通大学毕业设计 论文 立题卡 课题名称 转动可分解设计的构造及其应用 出题人 课题表述 简述课题的背景 目的 意义 主要内容 完成课题的条件 成果形式等 可分解设计是组合数学中研究的经典问题 具有特殊结构的可分解设计在密码理论 统计设计中有广泛的应用 如不同构的转动可分解设计能在统计试验的超饱和设计中设计最优k 循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程试验领域 成果形式论文 课题来源 科研 课题类别 毕业论文 该课题对学生的要求 要求学生有较好的数学和计算机基础 教研室意见 教研室主任签名 年 月 日 学院意见 同意立题 不同意立题 教学院长签名 年 月 日 注 1 此表一式三份 学院 教研室 学生档案各一份 2 课题来源是指 1 科研 2 社会生产实际 3 其他 3 课题类别是指 1 毕业论文 2 毕业设计 4 教研室意见 在组织专业指导委员会审核后 就该课题的工作量大小 难易程度及是否符合专业培养目标和要求等内容提出具体的意见和建议 彈贸摄尔霁毙攬砖卤庑 5 学院可根据专业特点 可对该表格进行适当的修改 南 通 大 学 毕业设计 论文 任务书 题目 转动可分解设计的构造及其应用 学生姓名 陈媛 学 院 理学院 专 业 信息与计算科学 班 级 信计091 学 号 0902072006 起讫日期 2013年1月8日至6月5日 指导教师 王金华 职称 教授 发任务书日期 2013 年 1 月 8 日 课题的内容和要求 研究内容 研究目标和解决的关键问题 研究内容 可分解设计是组合数学中研究的经典问题 具有特殊结构的可分解设计在密码理论 统计设计中有广泛的应用 如不同构的转动可分解设计能在统计试验的超饱和设计中设计最优k 循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程试验领域 目标和要求 1 查阅资料 阅读文献 理解课题的含义 2 研究转动可分解设计的构造方法 了解现有的结论 3 转动可分解设计在最优循环的超饱和设计构造中的应用 课题的研究方法和技术路线 1 阅读与平衡不完全区组设计 BIBD 可分解平衡不完全区组设计 RBIBD 有关的文献 2 正确理解转动可分解设计的构造含义 了解它和组合设计的关系 3 构造不同构的转动可分解设计 并且探究其在超饱和设计中的应用 4 通过使用计算机编程 求出的转动可分解设计的结果 基 础 条 件 本课题的指导者近年来主要从事组合数学及其应用的研究 主持一项有关组合理论及其应用的国家自然科学基金项目的研究 一项南通市科技创新项目的研究 对组合设计理论的前沿状况比较了解 有多年指导本科生毕业论文的经验 已在国内外核心期刊上发表相关论文30多篇 同时该课题也是国家自然科学基金项目所要研究的部分内容 该生有较好的组合数学基础知识和刻苦钻研精神 学校图书馆和校园网有比较丰富的图书资料 同时指导老师能为学生提供相关的外文资料 综上所述 已基本具备完成本课题研究的基础条件 参考文献 1 Liu M and Zhang et al Construction of E s2 optimal supersaturated designs using cyclic BIBDs J J Statist Plann Inference 2000 91 139 150 2 Lu X and Hu et al A systematic procedure in the construction of multi level supersaturated design J J Statist Plann Inference 2003 115 287 310 3 Ngyuen N K An algorithmic approach to constructing supersaturated designs J Technometrics 1996 38 69 73 4 Hanani H On resolvable balanced incomplete block designs J J Combin Theory Ser A 1974 17 275 289 5 Plackett R L and Burman et al The design of optimum multifactorial experiments J Biometrika 1946 33 305 325 6 Hanani H Balanced incomplete block designs and related designs D Discrete Math 1975 11 255 369 7 Wu X H A Construction of optimal multi level supersaturated designs J Ann Statist 2005 33 2811 2836 8 Wilson R M An existence theory for pairwise balanced design J J Combin Theory Ser A 1972 13 220 273 9 Wilson D A R Solution of Kirkman s schoolgirl problem J Proc Sympos Pure Math 1971 19 187 203 10 Lu J An existence theory for resolvable balanced incomplete block designs J Acta Math Sinica 1984 27 458 468 11 Chen J and Liu et al Optimalmixed level k circulant supersaturated designs J J Statist Plann Inference 2008 138 4151 4157 12 Baker R D Resolvable BIBD and SOLS J Discrete Math 1983 44 13 29 13 Hanani H Ray Chaudhuri D K and Wilson R On resolvable designs J Discrete Math 1972 3 343 357 14 Ray Chaudhuri D K and Wilson R The existence of resolvable block designs J A Survey of Combinatorial Theory 1973 11 361 375 15 Fang K T and Lin et al Optimal mixed level supersaturated design J Metrika 2003 58 279 291 本课题必须完成的任务 1 介绍BIBD RBIBD的构造方法以及例子 2 介绍转动可分解的构造方法以及不同构的转动可分解设计的构造 并且其在超饱和设计 中的应用 3 给出时部分或完全的转动可分解设计的结果 成果形式 论文 进度计划 起讫日期 工作内容 备 注 1月10日 2月28日 选题 查阅文献资料 3月1日 3月5日 开题报告 3月6日 3月19日 根据开题报告情况继续查阅文献资料 3月20日 4月20日 写出论文第一稿 并完成外文翻译 4月21日 5月5日 指导老师批阅论文第一稿 5月6日 5月19日 修改论文 并定稿 5月20日 5月31日 指导教师评定成绩 评阅老师评阅论文 写出评阅意见 6月1日 6月15日 答辩 教研室审核意见 该任务书的内容符合南通大学本科生毕业设计 论文 要求和本专业的培养目标 同意下发 教研室主任签名 年 月 日 学院意见 教学院长签名 年 月 日 注 此表为参考表格 学院可根据专业特点 对该表格进行适当的修改 南通大学本科生毕业设计 论文 开题报告 学生姓名 陈媛 学 号 0902072006 专业 信息与计算科学 课题名称 转动可分解设计的构造及其应用 阅读文献 情 况 国内文献 0 篇 开题日期 2013 03 07 国外文献 15 篇 开题地点 理学院信息与计算科学教研室 1 文献综述与调研报告 阐述课题研究的现状及发展趋势 本课题研究的意义和价值 参考文献 可分解设计是组合数学中研究的经典问题 具有特殊结构的可分解设计在密码理论 统计设计中有广泛的应用 如不同构的转动可分解设计能在统计试验的超饱和设计中设计最优循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程试验领域 构建二水平因子的超饱和设计的方法已经在许多著作中被涉及 多水平超饱和设计也已经被一些研究人员研究 Lin和Dean 2004 提出了循环设计 并且给出了他们对于二水平因子的解释 本文主要介绍转动可分解设计的定义以及构造方法 并通过计算机编程计算的Rotational RBIBD 介绍利用Rotational RBIBD构造最优循环设计 以及其在实际中的应用 定义1 1 设为一个有限集 为的一个子集族 则称此序对是集上的一个区组设计 的元素称为区组 进一步 设与为给定的正整数 是给定的正整数 若区组设计满足 i ii 对任意 都有 iii 中任意一对不同的点都恰好同时包含在个区组中 当时 则称为平衡不完全区组设计 记为 易知 的必要条件是 1 当时 平衡不完全区组设计的存在性由Hanani 14 在1975年证明 定理1 2 设都是正整数 如果 并且 则除去不存在外 存在的必要条件 1 也是充分的 平衡不完全区组设计的存在性问题是转动可分解设计理论中的一个基本问题 条件 1 是存在的基本必要条件 不过这些条件并不是充分的 M Hall Jr 1967 提出了下面这个著名的存在性猜想 猜想1 存在性猜想 给定正整数 对满足条件 1 的正整数 除去有限个例外 都存在 Wilson 3 对上诉存在性猜想给出了证明 有下述 渐进存在性定理 定理2 3 给定正整数和 存在常数 使得当时 存在的必 要条件 1 也是充分的 定义2 4 设是一区组设计 若构成的一个划分 则称为此设计的一个平行类 如果区组能被划分成平行类 则称此设计为可分解的 如果一个是可分解 的 则称为可分解平衡不完全区组设计 记为 易知 存在的必要条件为 2 时 的存在性主要依赖于的情形 的存在性问题 也是历史上著名的Kirkman女生问题 经过一百多年的研究 于1971年由Ray Chaudhuri和Wilson 5 解决 而的情形由Hanani 6 于1974年解决 定理3 7 当且仅当下列条件之一成立时 存在 1 且 2 且 3 且 时 的存在性主要依赖于的情形 1972年 Hanani等解决了时的情形 即的存在性 Baker解决了 k 4 3 的情形 即的存在性 定理4 8 当且仅当下列条件之一成立时 存在 1 且 2 且 而的存在性问题在国内外多位学者的共同努力下 已接近完整解决 定理5 9 当且v 45 345 465 645 时 存在 对一般的 Ray Chaudhuri和Wilson 10 和Lu证明了的 渐近存在性 定理6 10 对给定的正整数和 除了有限多个正整数v外 存在的必 要条件 2 也是充分的 定义3 若D X B 为 其中 令 为的映射 B 令BB 若BB 则称为的一个自同构 此时称为Rotational BIBD 进一步 B在的作用下 产生轨道 轨道长度为 每个轨道中取一个代表 构成的一个基区组 如果这个基区组构成了的一个划分 即基区组是的一个平行类 称此平行类为的基平行类 此时 Rotational BIBD是可分解的 称其为 Rotational RBIBD 本文提供了一个系统的构造转动可分解设计的方法 二级水平设计同样包含于这个系统方法 这个系统的方法是基于利用满足某些特性的一系列初始区组的循环生成法的可分解的平衡不完全区组设计 RBIBDs 有些循环设计的其他可供选择的方法同样也包含于Lu et al 2003 11 中 然而 本文呈现最优K 循环超饱和设计的一个广泛比较方法 其包含在有关计算机的基础方法著作中或者在Lu et al 2003 中 在实际中 超饱和设计对于因子筛选试验很有帮助 现有的超饱和设计的构造方法主要是针对二级水平和多级水平情形的 但是实际中 混和水平超饱和设计有着更广泛的用途 此不部分可做一项独立研究 在此不做论述 参考文献 1 Liu M and Zhang et al Construction of E s2 optimal supersaturated designs using cyclic BIBDs J J Statist Plann Inference 2000 91 139 150 2 Lu X and Hu et al A systematic procedure in the construction of multi level supersaturated design J J Statist Plann Inference 2003 115 287 310 3 Ngyuen N K An algorithmic approach to constructing supersaturated designs J Technometrics 1996 38 69 73 4 Hanani H On resolvable balanced incomplete block designs J J Combin Theory Ser A 1974 17 275 289 5 Plackett R L and Burman et al The design of optimum multifactorial experiments J Biometrika 1946 33 305 325 6 Hanani H Balanced incomplete block designs and related designs D Discrete Math 1975 11 255 369 7 Wu X H A Construction of optimal multi level supersaturated designs J Ann Statist 2005 33 2811 2836 8 Wilson R M An existence theory for pairwise balanced design J J Combin Theory Ser A 1972 13 220 273 9 Wilson D A R Solution of Kirkman s schoolgirl problem J Proc Sympos Pure Math 1971 19 187 203 10 Lu J An existence theory for resolvable balanced incomplete block designs J Acta Math Sinica 1984 27 458 468 11 Chen J and Liu et al Optimal mixed level k circulant supersaturated designs J J Statist Plann Inference 2008 138 4151 4157 12 Baker R D Resolvable BIBD and SOLS J Discrete Math 1983 44 13 29 13 Hanani H Ray Chaudhuri D K and Wilson R On resolvable designs J Discrete Math 1972 3 343 357 14 Ray Chaudhuri D K and Wilson R The existence of resolvable block designs J A Survey of Combinatorial Theory 1973 11 361 375 15 Fang K T and Lin et al Optimal mixed level supersaturated design J Metrika 2003 58 279 291 二 本课题的基本内容 预计解决的难题 基本内容 本课题将研究不同构转动可分解设计的构造及其应用 首先 理解设计 BIBD RBIBD以及转动可分解设计 Rotational RBIBD 的定义 以及不同构的转动可分解设计的构造方法 可分解设计是组合数学中研究的经典问题 具有特殊结构的可分解设计密码理论 统计设计中有广泛应用 如了解不同构的转动可分解设计能在统计试验的超饱和设计中设计最优的K 循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程试验领域 其次了解转动可分解的定义 本课题主要研究转动可分解设计 Rotational RBIBD 的构造 并讨论它在超饱和设计的应用 同时利用计算机编程计算的转动可分解设计 预计解决的难题 对于此类最优超饱和设计未知结论的构造 可能需要较长时间的寻找 对于计算机运算 需要时间的调整 三 课题的研究方法 技术路线 研究方法 1 查阅文献 2 向学长及老师请教 3 网上搜集资料 4 自我归纳总结 技术路线 1 阅读与转动可分解设计的构造问题有关的文献 2 正确理解转动可分解设计的构造含义 了解它和组合设计的关系 3 研究转动可分解设计的构造方法 以及理解通过不同构的转动可分解设计构造最优循环设计 并且论述其在实际中的具体应用 4 通过使用计算机程序 求出一类Rotational RBIBD的最优解 四 研究工作条件和基础 本课题的指导者近年来主要从事组合数学及其应用的研究 主持一项有关组合理论及其应用的国家自然科学基金项目的研究 一项南通市科技创新项目的研究 对组合设计理论的前沿状况比较了解 有多年指导本科生毕业论文的经验 已在国内外核心期刊上发表相关论文30多篇 同时该课题也是国家自然科学基金项目所要研究的部分内容 该生有较好的组合数学基础知识和刻苦钻研精神 学校图书馆和校园网有比较丰富的图书资料 同时指导老师能为学生提供相关的外文资料 综上所述 已基本具备完成本课题研究的基础条件 五 进度计划 起讫日期 工作内容 1月10日 2月28日 选题 查阅文献资料 3月1日 3月5日 开题报告 3月6日 3月19日 根据开题报告情况继续查阅文献资料 搜集数据 3月20日 4月20日 写出论文第一稿 并完成外文翻译 4月21日 5月5日 指导老师批阅论文第一稿 5月6日 5月19日 修改论文 并定稿 5月20日 5月31日 指导教师评定成绩 评阅老师评阅论文 写出评阅意见 6月1日 6月15日 学生进行答辩 论文阶段完成日期 文献调研完成日期 3月10日 论文实验完成日期 撰写论文完成日期 5月18日 评议答辩完成日期 6月05日 指 导 教 师 评 语 该生能按任务书计划完成课题研究 研究进展顺利 已经取得了部分研究成果 论文翻译已经完成 下一步的研究计划可行 有望准时完成课题研究 同意开题 导师签名 年 月 日 教 研 室 意 见 教研室主任签名 年 月 日 学院 意见 通过开题 开题不通过 教学院长签名 年 月 日 注 1 学院可根据专业特点 可对该表格进行适当的修改 南 通 大 学 毕 业 论 文 题目 转动可分解设计的构造及其应用 姓 名 陈媛 指导教师 王金华 专 业 信息与计算科学 謀荞抟箧飆鐸怼类蒋薔 南通大学理学院 2013年5月 XV 南通大学毕业论文 摘 要 超饱和设计在许多领域有广泛的应用 如计算机实验 软件测试 医药 工业和工程试验 以及生物识别应用领域 构建二水平因子的超饱和设计的方法已经受到广泛关注 多水平超饱和设计也已经被一些研究人员研究 Lin和Dean 2004 提出了循环设计 并且给出了二水平因子超饱和设计的构造 厦礴恳蹒骈時盡继價骚 本文给出了由差方法得到的RBIBD构建最优循环设计的生成列的方法 这样的RBIBDs被称为可分解的转动平衡不完全区组设计 如果在两个可分解转动BIBD之间存在一个同构映射保持初始区组集不变 则称之为同构的 当个不同构的可分解的转动BIBDs存在 则可以构造个最优循环设计其列是非完全别名的 如果一列通过水平置换可以得到另一列 那么这两列完全的别名 此时 可以通过把这个循环设计列并列得到最优循环设计 茕桢广鳓鯡选块网羈泪 本文描述了可分解1 转动平衡不完全区组设计的概念 利用差的方法给出了不同构的可分解1 转动平衡不完全区组设计的构造方法 在计算计的辅助下 得到了区组大小为4指数为3的不同构的可分解1 转动平衡不完全区组设计对 直接应用获得了一些新的最优2 循环设计其中 鹅娅尽損鹌惨歷茏鴛賴 关键词 平衡不完全区组设计 转动可分解平衡不完全区组设计 最优k 循环设计 ABSTRACT Supersaturated designs are important in various fields including computer experiments software testing medical industrial and engineering experiments and biometric applications Methods for constructing supersaturated designs for two level factors have received considerable attention Multi level supersaturated designs have also been studied by several authors Liu and Dean 2004 introduced k circulant designs and gave their constructions for two level factors 籟丛妈羥为贍偾蛏练淨 This paper presents a method for constructing the generating column of an optimal 1 circulant design using a RBIBD obtained through the method of differences Such RBIBDs are called resolvable 1 rotational balanced incomplete block designs Two resolvable 1 rotational BIBDs are called isomorphic if there is an isomorphism between them that preserves the set of initial blocks When nonisomorphic resolvable 1 rotational BIBDs exist then k such optimal 1 circulant designs with no fully aliased columns can be constructed Two columns are fully aliased if one column can be obtained by permuting levels in another column An optimal k circulant design is then obtained by column juxtaposition of these k 1 circulant designs 預頌圣鉉儐歲龈讶骅籴 This paper describes the definitions of resolvable 1 rotational balanced incomplete block designs and gives constructions of 1 rotational RBIBDs by the method of differences With help of computer we obtain some pairs of nonisomorphic resolvable 1 rotational BIBDs with bock size 4 and index 3 for As its application we obtain some new optimal 2 circulant designs for 渗釤呛俨匀谔鱉调硯錦 keyword BIBD Rotational RBIBD Optimal k circulant design铙誅卧泻噦圣骋贶頂廡 目 录 摘 要 XVI擁締凤袜备訊顎轮烂蔷 ABSTRACT XVII贓熱俣阃歲匱阊邺镓騷 第一节 引言 1坛摶乡囂忏蒌鍥铃氈淚 第二节 转动可分解设计的构造 3蜡變黲癟報伥铉锚鈰赘 第三节 转动可分解设计的应用 10買鲷鴯譖昙膚遙闫撷凄 第四节 结束语 16綾镝鯛駕櫬鹕踪韦辚糴 参考文献 17驅踬髏彦浃绥譎饴憂锦 致 谢 18猫虿驢绘燈鮒诛髅貺庑 XIX 第一节 引言 一个区组设计是一个二序组 其中为一个有限集 为的一个子集族 的元素称为区组 进一步 设与为给定的正整数 是给定的正整数 若区组设计满足 i ii 对任意 都有 iii 中任意一对不同的点都恰好同时包含在个区组中 当时 则称为平衡不完全区组设计 记为 锹籁饗迳琐筆襖鸥娅薔 易知 的必要条件是 1 当时 平衡不完全区组设计的存在性由Hanani 6 在1975年证明 若是一区组设计 若构成X的一个划分 则称为此设计的一个平行类 如果区组能被划分成平行类 则称此设计为可分解的 如果一个是可分解的 则称为可分解平衡不完全区组设计 记为 12 構氽頑黉碩饨荠龈话骛 易知 存在的必要条件为 2 时 的存在性主要依赖于的情形 的存在性问题 也是历史上著名的Kirkman女生问题 经过一百多年的研究 于1971年由Ray Chaudhuri和Wilson 9 解决 而的情形由Hanani 4 于1974年解决 輒峄陽檉簖疖網儂號泶 时 的存在性主要依赖于的情形 1972年 Hanani 13 等解决了时的情形 即的存在性 Baker解决了的情形 即的存在性 而的存在性问题在国内外多位学者的共同努力下 已接近完整解决 尧侧閆繭絳闕绚勵蜆贅 对一般的 Ray Chaudhuri和Wilson 14 和Lu 10 证明了的 渐近存在性 若为 其中 令 为的映射 令 若 则称为的一个自同构 此时称为Rotational BIBD 进一步 在的作用下 产生轨道 轨道长度为 每个轨道中取一个代表 构成的一个基区组 如果这个基区组构成了的一个划分 即基区组是的一个平行类 称此平行类为的基平行类 此时 Rotational BIBD是可分解的 称其为 Rotational RBIBD 识饒鎂錕缢灩筧嚌俨淒 例1 1 设 取基区组为 利用上面给出的定义 我们可以得到 此时 称 BIBD为 Rotational RBIBD 本文主要介绍不同构的转动可分解的构造及其应用 不同构的转动可分解设计能在统计试验的超饱和设计中设计最优的k 循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程试验领域 凍鈹鋨劳臘锴痫婦胫籴 在实际中 超饱和设计对于因子筛选试验很有帮助 现有的超饱和设计的构造方法主要是针对两水平和高水平情形的 但是实际中 混水平超饱和设计有着更广泛的用途 本文对此部分不做研究 恥諤銪灭萦欢煬鞏鹜錦 第二节 转动可分解设计的构造 这一节主要介绍不同构的转动可分解设计的定义及其构造方法 同时利用计算机编程计算出了一些不同构的转动可分解设计的例子 鯊腎鑰诎褳鉀沩懼統庫 定义2 1设为的子集族 若 其中称为的差 则称为差族 记为 特别地 当时 称其为差集 记为 例2 1在中 称为 有了差族的定义 下面我们利用差族的定义来给出Rotational RBIBD的构造方法 构造方法 设为上的个元子集族 其中 令 若 则为一个 RBIBD 其中为其平行类 证明 令 由 有为Rotational BIBD 又构成的一个平行类 可以划分为个平行类 所以为Rotational RBIBD 硕癘鄴颃诌攆檸攜驤蔹 因为本节研究的是不同构的转动可分解设计 所以下面我们给出不同构的概念 定义2 2设 是两个Rotational RBIBD 其中分别是的平行类 若存在的一个双射 并且满足和 则与是同构的 若不存在这样的 则与是不同构的 阌擻輳嬪諫迁择楨秘騖 以下是通过上面的构造方法 同时利用计算机编程计算出了一些不同构的转动可分解设计的例子 引理2 1 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 0 1 2 5 0 2 3 7 3 8 11 12 1 4 8 13 4 6 10 13 5 9 10 11 7 9 14 6 12 14 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 2 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 3 4 5 18 6 10 12 16 1 2 8 12 5 9 14 17 0 7 10 14 0 2 11 18 6 9 15 17 1 3 4 15 11 13 16 7 8 13 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 3 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 4 7 11 15 4 10 15 19 0 3 5 17 2 9 12 21 2 10 12 19 0 3 11 16 1 6 13 16 1 5 14 22 8 9 14 18 6 7 8 13 20 21 22 17 18 20 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 4 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 1 4 9 21 13 17 22 25 8 10 23 26 1 2 4 14 3 7 11 16 10 12 16 23 2 5 18 22 0 7 21 26 0 6 15 17 3 11 18 20 12 13 14 20 5 6 9 15 19 2 25 8 19 24 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 5 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 8 13 17 23 2 3 4 12 7 11 18 30 0 1 6 20 5 10 14 26 7 13 22 26 0 1 3 21 11 21 24 27 2 9 15 16 5 9 16 23 4 19 22 24 8 10 15 18 6 12 20 29 14 19 28 30 25 27 28 17 25 29 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 6 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 9 18 31 33 15 19 26 34 3 7 10 34 11 20 27 33 0 19 20 25 8 17 22 32 5 13 17 30 0 1 2 3 4 14 16 23 4 7 12 18 1 6 24 27 5 23 25 28 2 8 29 32 6 10 16 29 11 12 26 28 9 13 21 30 15 21 22 14 24 31 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 7 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 11 16 24 30 3 20 22 28 5 22 23 34 2 17 24 26 1 7 10 27 1 4 19 29 8 9 12 18 13 15 18 36 6 17 20 21 5 12 16 32 0 14 19 32 0 9 10 23 2 4 25 33 6 11 33 37 3 15 26 38 7 8 14 34 13 28 35 37 21 25 30 31 29 31 36 27 35 38 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 8 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 6 30 33 41 7 8 9 21 3 9 13 24 3 32 36 39 1 19 34 40 1 18 23 41 15 18 20 38 4 12 14 33 5 14 35 37 2 13 24 29 2 31 32 37 0 10 26 35 10 17 26 29 5 11 17 37 0 16 28 42 6 15 30 34 4 11 21 23 16 19 20 28 7 8 12 25 22 27 40 42 22 27 36 25 31 38 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 9 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 4 5 23 26 5 33 39 42 3 33 43 44 3 10 38 41 1 25 27 37 2 20 44 45 16 19 24 28 9 17 22 46 8 21 36 41 1 16 18 37 7 12 39 45 0 14 15 25 10 18 20 35 7 8 28 43 0 2 9 31 4 21 29 35 6 22 29 42 6 19 23 26 11 32 40 46 11 13 27 34 13 14 17 30 12 24 30 32 15 34 38 31 36 40 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 10 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 9 25 40 48 4 7 13 26 3 6 17 34 20 35 14 28 0 21 24 43 49 22 19 38 18 22 31 36 9 16 27 40 4 11 45 49 45 29 33 47 2 15 27 35 21 43 12 31 19 20 26 30 3 5 11 39 10 16 37 39 0 1 17 18 1 8 23 50 2 41 44 48 5 41 44 46 6 8 30 34 7 28 42 47 10 24 25 50 12 13 29 38 15 23 36 46 14 32 33 32 37 42 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 11 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 11 14 32 44 13 16 20 31 7 29 46 51 12 44 45 51 5 22 28 52 0 29 50 52 21 30 31 48 5 7 28 41 16 17 36 40 4 35 49 54 15 26 27 41 1 2 26 48 4 9 13 20 18 27 46 53 0 18 47 49 8 10 21 25 1 6 8 42 3 6 15 43 2 12 25 54 9 22 34 42 3 10 37 45 11 23 39 40 19 33 35 39 14 24 32 38 23 38 50 53 17 33 37 47 24 34 43 19 30 36 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 引理2 12 存在一对不同构的Rotational RBIBD 证明 根据上面的构造方法 在上构造基平行类 其基区组见下表 序号 基区组1 基区组2 初始区组 18 22 24 34 17 18 27 49 11 16 27 45 7 25 39 51 4 30 39 56 4 10 14 38 13 28 32 55 11 26 28 33 8 10 38 41 21 24 30 44 5 42 51 52 13 23 35 42 15 29 47 50 12 15 19 53 14 23 37 44 6 36 48 52 6 7 43 49 8 16 34 54 0 3 48 54 0 9 32 43 1 2 21 36 1 3 20 31 9 17 19 57 2 41 46 47 12 20 25 40 5 40 45 56 26 33 46 58 22 55 57 58 31 35 53 29 37 50 通过验证 满足不同构 所以存在一对不同构的Rotational RBIBD 第三节 转动可分解设计的应用 本节介绍利用转动可分解设计来构造超饱和设计 基于上节介绍 转动可分解设计可用于统计试验中设计最优k 循环的超饱和设计 它广泛应用于计算机试验 软件测试 医药 工业和生物工程式验领域 多年来 大量的科研工作者致力于超饱和设计的研究 下面介绍一些前人有关最优k 循环设计以及超饱和设计的研究成果 氬嚕躑竄贸恳彈瀘颔澩 利用Fang et al 2003 15 中E 符号表示最优设计 符号E 1 表示二水平因子 在著作中提及的其他一些用来表示的多级水平因子试验最优化标准符号与E 最优标准符号是一样的 为了本文的完整性 我们给出最优性判别 方法解释以及相关的定理证明 釷鹆資贏車贖孙滅獅赘 1 最优性判别 给定一个矩阵的处理组合 其中表示有限集中元素的个数 运行超饱和设计的初始区组的个数是 这样的最优超饱和设计用表示 这个初始区组用标号 在级处理组合中 假设所有初始区组是用同样的方法构造 则可划分为组 假设表示D的第列 一般的二水平因子的表示符号为E Fang et al 2003 15 引用E 符号 定义如下 怂阐譜鯪迳導嘯畫長凉 此时 并且在D的子矩阵组成的和列中 是对 p q 的频数 在Fang et al 2003 15 中证明了下面的结论 谚辞調担鈧谄动禪泻類 1 其中是D中行和行之间的任意数 如果满足下界 1 那么这个设计是最优化 下界被满足当且仅当对于D中所有的行对是一个实数 此时等价于 对于多水平超饱和设计的其他一些最优化符号参见文献中的 如在Xu和Wu 2005 7 然而 对于多水平实验关于具有相同数量水平的因子 它们中的大多数与符号是等价 在下文中 通过优化设计 即是指通过最优化k 循环超饱和设计D 11 嘰觐詿缧铴嗫偽純铪锩 2 构造方法的解释 循环设计的构造是基于循环法 循环法是由Plackett和Burman 1946 5 提出的 这个方法中的设计利用了生成列的循环 可以是一个大小为的行向量或者一个大小为的列向量 此的设计是首次基于循环法构造的 后来 对应于第行处理组合的最后一行是被添加到里面的 在第行处理组合中 所有的因素产生于同一水平 对于k 循环设计 生成列可以是一个大小为的行向量或者每个大小的k列向量 Liu和Dean 2004 7 通过一个单个生成列构造了k 循环设计 根据这些列 使用循环方法 每个k个生成列产生一个有个因子的1 循环设计 具有因子的k 循环设计是通过列并置这k个1 循环设计得到的 显然 k 循环设计的性质是由这k个1 循环设计的性质决定的 因此 为了从这些k 循环设计中得到最优设计 我们是通过列并置个生成列计而不是并置单个生成列 如前所诉 如果对于它的所有生成列是常数 那么此1 循环设计是最佳的 令表示从第个生成列得到的循环设计 同时表示第列 并且表示的第个元素 当大小为的k 循环设计由k个1 循环设计按列并置得到 可以看出 如果常数对其每个k个1 循环组设计是稳定的 那么是最优的 熒绐譏钲鏌觶鷹緇機库 我们现在考虑下面的结果 这将有助于证明我们的主要结果定理3 2 定理3 1 对于l 循环设计 其中 是中s行和t行之间的任意数 表示只对那些和的值求和 其中或者且是克罗内克符号 如果 否则为0 鶼渍螻偉阅劍鲰腎邏蘞 证明 对于环状的施工方法 它可以验证 2 此时 如果 那么它将被替换为 现在考虑