数学建模论文-最优控制设计.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 西 安 理 工 大 学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011年 7 月 26日赛区评阅编号（由赛区组委会评阅前进行编号）：142011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最优控制设计摘要本文主要关于在计算机控制，对计算机指令控制计算机部件的问题作了具体的分析，对于使得所有部件得到控制的最少指令集合和所有部件得到控制的总长度最小的指令集合，我们建立了如下的模型。模型一主要利用整数线性规划模型，列出所求优化问题式子，并列出约束条件，确保一个部件至少有1条指令控制，同时利用lingo算出所有部件得到控制的最少指令的集合为13和所有部件得到控制的总长度最小长度为360。模型二主要利用图论的思想，采用二分覆盖，指令为一个顶点集(n),部件为一个顶点集(m),如某个指令可以控制某个部件就用边连接起来.所以第一问转化为：在n选取最少的顶点使m通过边的关系全部被选中,第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集,使m全部被选中。利用这种思想,采用c编程可以很容易的求出结果，所求结果与模型一相同。关键词：计算机控制；整数线性规划；二分图；最小覆盖 一、问题重述在计算机控制的过称中，一条计算机指令往往可以控制几个计算机部件，反过来，一个计算机部件一般由几条计算机指令控制。指令有一定的长度，即在计算机的存储器中占用一定的空间。因此，在对计算机部件的控制中需要考虑两个问题：一是在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制；二是在指令集合中寻求总长度最小的若干指令，且能使所有的计算机部件得到控制。1、建立解决上述两个问题的数学模型；2、设计模型的求解算法，用表1.1所列数据给出求解结果；3、分析设计算法的复杂性和计算所得到的结果。表1.1 指令控制的部件和指令的长度指令指令所控制的部件指令长度指令指令所控制的部件指令长度14，8，20，31，26151913，23，26，392628，19，22，29，3780207，12，40，412232，16，34，33，32302112，16，19，28，352647，11，35，3012226，23，27，451955，13，18，2172333，37，40，411761，7，9，23，2519243，17，19，362273，5，6，14，24322516，33，44，451087，20，21，32，35122613，19，24，253099，15，20，1245272，3，5，882106，10，39，28，2736284，7，9，12，4373111，11，21，34，38572916，17，20，3266122，4，18，22，37783028，33，34，3655136，17，25，36653110，23，25，27241422，33，34，3853321，5，44，4546152，10，20，37343311，15，18，4337169，24，29，3948347，14，22，36771715，18，29，3146353，15，25，399184，28，26，12322、 问题分析计算机已经成为现代社会发展的不可取代的有利助手，而计算机控制更是遍及各个领域。因而对计算机指令控制部件并达到最优的研究具有深远的意义。由于一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，这两都是线性规划问题且约束条件相同，只是两个题的目标函数不同。针对问题一：模型一建立使得所有的部件得到控制的指令集合里的最少的指令模型。我们利用整数线性规划模型，列出所求优化问题目标函数和约束条件，并确保一个部件至少有1条指令控制，同时利用lingo软件算出所有部件得到控制的最少指令的集合。模型二将第一问转化为：在n指令集合选取最少的顶点使m通过边的关系全部被选中。针对问题二：仍然建立整数规划模型，依然要保证一个部件至少有1条指令控制，再用lingo算出所有部件得到控制的总长度的最小长度。模型二将第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集，使m全部被选中。针对复杂度，我们分为时间复杂度和空间复杂度。然后通过各自的影响因素进行分析，由此确定此模型是否正确，并且是否最合适。三、模型假设根据题目要求，并为了达到简化的目的，我们首先做如下假设：1. 假设每个部件都能被指令集合中一条或多条指令控制；2. 假设每条指令在运行过程中不发生逻辑错误，且每个部件均工作正常；3. 在指令控制部件的过程中我们只考虑指令和部件的对应性，而不考虑计算机指令控制过程中的延迟性等问题；4. 不考虑计算机发送指令所用的时间。四、符号说明符号表示含义第i个部件是否被第j条指令控制（0或1）是否使用第j条指令（0或1）第j条指令的长度m部件的总个数n部件的总条数所用指令的总条数所用指令的总长度d最小指令覆盖集合的元素个数covm部件是否覆盖的标记数组newn各个指令控制的部件数五、模型的建立与求解模型一5.1 问题一的模型建立及求解5.1.1 问题一的模型建立1）目标函数问题一的目的是为了在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制，变量xi为0-1变量，xj表示是否使用第j条指令，如果使用则xj=1，如果不使用则xj=0，所使用指令的总条数可以表示为j，则目标函数为： (5-1)2）约束条件在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，则可以设ij表示第i个部件接受第j条指令，若第i个部件受第j条指令控制，则ij =1，若第i个部件不受第j条指令控制，ij=0。ijxj表示第i个部件总共接收到的指令条数，一个部件至少有1条指令控制。所以约束条件为： (5-2)5.1.2 问题一的模型求解在考虑了目标函数及约束条件了以后，我们先做出各个部件所需要的控制表（表5.1），然后通过lingo编程（附录1）可以得出结果(表5.2).表5.1各部件的控制指令表部件控制指令部件控制指令16,11,3223,12,15,2737,24,27,3541,12,18,2855,7,27,3267,10,13,2274,6,8,20,28,3481,2,2796,9,16,281010,15,31114,11,331220,21,28135,19,26147,34159,17,33,35163,21,25,29,1713,24,29185,12,17,33192,21,24,26201,8,9,15,29215,8,11222,12,14,34236,19,22,31247,16,26256,13,26,31,3526192722,312821,30292,16,17304311,17323,8,29333,14,23,25,30343,11,14,30354,8,213613,24,30,34372,12,15,233811,143910,16,19,354020,234120,234210,184310,28,33441,18,25,32459,18,22,25,32表5.2 所有部件得到控制的小指令集合指令xjx2x4x7x11x12x17x18所控部件3,12,15,271,12,18,284,6,8,20,28,344,11,3320,21, 2813,24, 295,12, 17,33指令xjx19x20x28x29x30x31所控部件2,21, 24,261,8,9, 15,2921,302,16,1741,17最小指令集合为：x2 x4 x7 x11 x12 x17 x18 x19 x20 x28 x29 x30 x31，总共为13条指令。5.2 问题二的模型建立及求解5.2.1 问题二的模型建立首先我们引入一组变量l1,l2,l3, lm , 其中lj表示第j条指令的长度问题二的目的是为了在指令集合中寻求总长度最小的若干指令,使所有的计算机部件得到控制.根据对问题一的分析可知,问题二同属整数线性规划问题,并得出相似模型为: (5-3)相应的相应的约束条件为： (5-4)5.2.2 问题二的模型求解同问题一，该模型属于整数规划问题，利用lingo编程（附录2）可以得出结果：表5.3 所有部件得到控制的总长度最小的指令集合指令xjx1x3x4x5x6x7x10长度1530127193236所控部件6,11,327,24,27,351,12,18,285,7,27,327,10,13,224,6,8,20,28,3410,15,31指令xjx14x17x19x21x22x23x24长度53462626191722所控部件7,3413,24,292,21,24,265,8,112,12,14,346,19,22,317,16,26所以最小长度为：l=15+30+12+7+19+32+36+53+46+26+26+19+17+22=360模型二模型二采用集合的思想，建立两个集合，然后运用最小集合的知识，c编程计算所求结果。5.3问题一的模型建立与求解我们采用二分图的理论，指令为一个顶点集(n),部件为一个顶点集(m),如某个指令可以控制某个部件就用边连接起来。所以第一问转化为：在n选取最少的顶点使m通过边的关系全部被选中,第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集,使m全部被选中。 六、算法的复杂性与结果分析1对于时间复杂度，题目要求是使每个部件都受一条或多条指令的控制，所以对于每一个部件都要从135遍历每一个的指令，若结果遍历过程中发现某一条指令控制此部件，则对其加一，表示第i个部件总共接收到的指令条数。则时间复杂度为45*35=1575，而第二问同第一问时间复杂度为45*35=1575。2对于空间复杂度，求解约束方程较少、数据量较小时，运行较为容易，且数据存储所占内存空间较多，运行循环过程过于复杂。总体来说，空间复杂度所占较大。7、 模型的评价优点：模型采用整数线性规划模型，本身较为严密，思路清晰，分步骤逐个击破，对题目一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制考虑周全，并且可以运用于实践问题，达到数学建模的根本目的，采用先进的lingo软件解决复杂程序，将问题简单化。缺点：当然我们对缺点也不避讳，因为知识面的局限及时间有限我们没有采用大量的文献资料来证明，且模型还有一些漏洞，以后我们会改进。8、参考文献1 沈继红，施久玉，张晓威. 数学建模m. 哈尔滨：哈尔滨工程大学出社,2000.2 何建坤. 实用线性规划及计算机程序m. 北京：清华大学出版社,1985(2)3 胡运权. 运筹学基础及应用m. 哈尔滨：哈尔滨工业大学出版社,1998(5).4 西北工业大学应用数学系. 线性代数m. 西安：西北工业大学出社,1998(3).1、将参考文献用12上标在文档中标出（在比赛评卷时非常重要）2、公式用5-1，5-2标出，表格和图也是3、参考文献另起一页4、标题用黑体，不是宋体加黑5、文章中涉及的字母和数字用新罗马字体（times new roman）6、图表很重要，就是曲线图之类的，尽量加一些有用的上去，但也不能过多7、摘要太少了，500字左右，到关键词结束差不多占了一页的3/4附录附录1：model:sets:zhiling/1.35/:x;bujian/1.45/:b;shuju(bujian,zhiling):a;endsetsdata:a= 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 ; enddatamin=sum(zhiling:x);for(bujian(j):sum(zhiling(i):x(i)*a(j,i)=1);for(zhiling:bin(x);end附录2:sets:zhiling/1.35/:x,l;bujian/1.45/:b;shuju(bujian,zhiling):a;endsetsdata:a=0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0