最优控制设计.doc

最优控制设计摘 要计算机已经成为现代社会发展不可取代的有利助手，而计算机控制更是遍及各领域。因而对计算机指令控制部件并达到最优的研究具有深远的意义。本文主要关于在计算机控制方面，对计算机指令控制计算机部件的问题作了具体的分析，对于使得所有部件得到控制的最少指令集合和所有部件得到控制的总长度最小的指令集合，分别建立了相应的整数线性规划模型。对于模型的求解,我们用lingo软件同时计算出结果。对所设计算法的复杂性，主要是从算法的时间复杂性和空间复杂性两方面进行分析。关键字：计算机指令 最优控制 线性规划 时间复杂性 lingo 一、 问题重述在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般由几条指令控制。一个基本问题是，在指令集合里寻找最少的指令，使得所有的部件得到控制；另一个问题是，当给定每条指令的长度时,在指令集合里，寻找最长度最少的若干指令，使得他们可以控制全部部件。对于上面的两个问题，建立如下两个数学模型：1. 建立使得所有部件得到控制的最少指令集合；2. 建立使得所有部件得到控制的总长度最小的指令集合。再给出指令控制的部件和指令的长度后如表11所示，用所建立的数学模型对表11所列的数据求出结果。3设计模型的求解算法，用表11中所列的数据给出求解结果；4. 分析所设计的算法的复杂性和计算得到的结果。二、 问题分析由于一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，这两个都是线性规划问题且约束条件相同，只是目标函数不同。对于问题一：建立使得所有的部件得到控制的指令集合里的最少的指令模型。我们利用整数线性规划模型，找出所求优化问题的目标函数和约束条件，并确保一个部件至少有1条指令控制，同时利用软件计算得出所有部件得到控制的最少指令的集合。对于问题二：仍然建立整数线性规划模型，依然要保证一个部件至少有1条指令控制，再用软件计算得出所有部件得到控制的指令的总长度的最小长度。对于问题三：对于模型1和模型2求解，我们用的是Lingo软件同时进行求解。对于问题四：主要是从时间复杂度和空间复杂度两方面对算法的复杂度进行分析。三、 模型假设1) 假设每个指令都正常控制相应的部件。2) 假设每个部件都能被指令集合中一条或多条指令控制。3) 假设每条指令在运行过程中不发生逻辑错误, 且每个部件均工作正常。4)在指令控制部件的过程中只考虑指令和部件的对应性, 而不考虑计算机指令控制过程中其他的关系和问题。四、符号的定义及说明符号定义及说明第条指令是否被使用第个部件是否被第条指令控制第条指令的长度部件的总个数指令的总条数所用指令的总条数 所用部件的总个数这里只给出主要符号的意义，其他符号将在文中给出，在此不再一一赘述。五、 模型的建立及求解5.1 建立使得所有的部件得到控制的最少指令集合此问的目的是为了在指令集合中寻找条数最少的指令, 使所有的计算机部件得到控制。变量为0- 1 变量, 表示是否使用第条指令, 如果使用第条指令, 则其对应的= 1, 否则= 0 。 所使用指令的总条数可表示为, 因此目标函数为:Min: （1）约束条件：1）表示第个部件和第条指令的关系, 如果第个部件能被第条指令控制= 1, 否则= 0 .2）用表示第个部件是否得到指令集合中一条或多条指令控制，则表示第个部件得到指令集合中至少一条指令的控制.即：，=1，2，3. （2）由此，建立了如下的数学模型：Min: （3）5.2 建立使得所有部件得到控制的总长度最小的指令集合首先我们引入一组变量其中表示第条指令的长度. 问题二的目的是为了在指令集合中寻求总长度最小的若干指令, 使所有的计算机部件得到控制. 根据对问题一的分析可知, 问题二同属整数线性规划问题, 并得相似模型为:Min: （4）5.3 建立求解算法的模型用lingo软件实现：根据附表一所列数据利用lingo软件求得一组最优解为:=1, =1, =1, =1，=1 , =1, =1, =1,=1, =1, =1, =1, =1, 目标函数min:=13。即能控制所有部件, 且所用指令条数最少的一组指令为: 2, 4, 7, 11, 12, 17, 18, 19, 20,28, 29, 30, 31, 共13 条指令。根据附表一所列数据利用lingo软件求得一组最优解为:=1, =1, =1, =1，=1 , =1, =1, =1,=1, =1, =1, =1, =1, =1,目标函数min: =360。即能控制所有部件, 且所用指令长度总和最小的一组指令为 1，3 ，4, 5 ，6, 7，10 ，14, 17, 19, 21, 22, 23, 24, 共14 条指令, 总长度360 。5.4 算法的复杂度分析Lingo求解本题的复杂性分析如下： 虽然模型的约束及变量个数影响其计算速度，但此模型用Lingo编程，在优化编程方面，Lingo的计算机的运行时间短，所以效率最高。 六、 结果分析七、模型的评价和与推广我们建立的模型对计算机指令优化控制问题作了细致的分析，并且提出了模型的几种算法，而且还进行实例的计算求解，最后还用了lingo数学软件检验了结果的正确性总的来讲本模型可以适用于其他的相似问题，而且单纯形法的算法快捷，整数规划明确简单。但是由于我们采用的算法有局限性，所以在问题有多组最优解的时候，我们只能求到一组，不过经过检验，所得的结果还是令人满意的。八、参考文献1钱颂迪，运筹学M，北京: 清