《《数学建模论文最优控制设计》》由会员分享，可在线阅读，更多相关《《数学建模论文最优控制设计》（16页珍藏版）》请在金锄头文库上搜索。
1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括 、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号
2、的话）： 所属学校（请填写完整的全名）： 西 安 理 工 大 学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011年 7 月 26日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最优控制设计摘要本文主要关于在计算机控制，对计算机指令控制计算机部件的问题作了具体的分析，对于使得所有部件得到控制的最少指令集
3、合和所有部件得到控制的总长度最小的指令集合，我们建立了如下的模型。模型一主要利用整数线性规划模型，列出所求优化问题式子，并列出约束条件，确保一个部件至少有1条指令控制，同时利用Lingo算出所有部件得到控制的最少指令的集合为13和所有部件得到控制的总长度最小长度为360。模型二主要利用图论的思想，采用二分覆盖，指令为一个顶点集(n),部件为一个顶点集(m：在n选取最少的顶点使m通过边的关系全部被选中,第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集,使m全部被选中。利用这种思想,采用c编程可以很容易的求出结果，所求结果与模型一相同。关键词：计算机控制；整数线性规划；二分图；
4、最小覆盖 一、问题重述在计算机控制的过称中，一条计算机指令往往可以控制几个计算机部件，反过来，一个计算机部件一般由几条计算机指令控制。指令有一定的长度，即在计算机的存储器中占用一定的空间。因此，在对计算机部件的控制中需要考虑两个问题：一是在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制；二是在指令集合中寻求总长度最小的若干指令，且能使所有的计算机部件得到控制。1、建立解决上述两个问题的数学模型；2、设计模型的求解算法，用表1.1所列数据给出求解结果；3、分析设计算法的复杂性和计算所得到的结果。表1.1 指令控制的部件和指令的长度指令指令所控制的部件指令长度指令指令所控制的部件指令长度
5、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，2
6、1，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，1232二、 问题分析计算机已经成为现代社会发展的不可取代的有利助手，而计算机控制更是遍及各个领域。因而对计算机指令控制部件并达到最优的研究具有深远的意义。由于一条计算机指令往往可以控制
7、几个计算机部件，反过来，一个部件一般有几条指令控制，这两都是线性规划问题且约束条件相同，只是两个题的目标函数不同。针对问题一：模型一建立使得所有的部件得到控制的指令集合里的最少的指令模型。我们利用整数线性规划模型，列出所求优化问题目标函数和约束条件，并确保一个部件至少有1条指令控制，同时利用Lingo软件算出所有部件得到控制的最少指令的集合。模型二将第一问转化为：在n指令集合选取最少的顶点使m通过边的关系全部被选中。针对问题二：仍然建立整数规划模型，依然要保证一个部件至少有1条指令控制，再用Lingo算出所有部件得到控制的总长度的最小长度。模型二将第二问则转化为：当将n的点全部赋权后,在n中找
8、出权数总和最小的顶点集，使m全部被选中。针对复杂度，我们分为时间复杂度和空间复杂度。然后通过各自的影响因素进行分析，由此确定此模型是否正确，并且是否最合适。三、模型假设根据题目要求，并为了达到简化的目的，我们首先做如下假设：1. 假设每个部件都能被指令集合中一条或多条指令控制；2. 假设每条指令在运行过程中不发生逻辑错误，且每个部件均工作正常；3. 在指令控制部件的过程中我们只考虑指令和部件的对应性，而不考虑计算机指令控制过程中的延迟性等问题；4. 不考虑计算机发送指令所用的时间。四、符号说明符号表示含义第i个部件是否被第j条指令控制（0或1）是否使用第j条指令（0或1）第j条指令的长度m部件
9、的总个数n部件的总条数所用指令的总条数所用指令的总长度d最小指令覆盖集合的元素个数covm部件是否覆盖的标记数组Newn各个指令控制的部件数五、模型的建立与求解模型一 问题一的模型建立及求解 问题一的模型建立1）目标函数问题一的目的是为了在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制，变量xi为0-1变量，xj表示是否使用第j条指令，如果使用则xj=1，如果不使用则xj=0，所使用指令的总条数可以表示为j，则目标函数为： (5-1)2）约束条件在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，则可以设ij表示第i个部件接受第j条指令，
10、若第i个部件受第j条指令控制，则ij =1，若第i个部件不受第j条指令控制，ij=0。ijxj表示第i个部件总共接收到的指令条数，一个部件至少有1条指令控制。所以约束条件为： (5-2) 问题一的模型求解在考虑了目标函数及约束条件了以后，我们先做出各个部件所需要的控制表（表），然后通过Lingo编程（附录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,33
11、1220,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,1843
12、10,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条指令。 问题二的模型建立及求解 问题二的模型建立首先我们引入一组变量l1,l2,l3, lm , 其中lj表示第j条指令的长度问题二的目的是为了在指令集合中寻求总长度最小的若干指令,使所有的计算机部件得到控制.根据对问题一的分析可知,问题二同属整数线性规划问题,并得出相似模型为: (5-3)相应的相应的约束条件为： (5-4) 问题二的模型求解
