我们的最优设计论文改过

2011高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）： 西 安 理 工 大 学

参赛队员 (打印并签名) ：1. 张 晓 艳

2. 冉 康

3. 王 玉

指导教师或指导教师组负责人 (打印并签名)： 胡 钢

日期： 2011年 7 月 26日

赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评

阅

人

评

分

备

注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

1 最优控制设计

摘要

本文主要关于在计算机控制，对计算机指令控制计算机部件的问题作了具体的分析，对于使得所有部件得到控制的最少指令集合和所有部件得到控制的总长度最小的指令集合，我们建立了如下的模型。

模型一主要利用整数线性规划模型，列出所求优化问题式子，并列出约束条件，确保一个部件至少有1条指令控制，同时利用Lingo算出所有部件得到控制的最少指令的集合为13和所有部件得到控制的总长度最小长度为360。

模型二主要利用图论的思想，采用二分覆盖，指令为一个顶点集(n),部件为一个顶点集(m),如某个指令可以控制某个部件就用边连接起来.所以第一问转化为：在n选取最少的顶点使m通过边的关系全部被选中,第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集,使m全部被选中。利用这种思想,采用c编程可以很容易的求出结果，所求结果与模型一相同。

关键词：计算机控制；整数线性规划；二分图；最小覆盖

2 一、问题重述

在计算机控制的过称中，一条计算机指令往往可以控制几个计算机部件，反过来，一个计算机部件一般由几条计算机指令控制。指令有一定的长度，即在计算机的存储器中占用一定的空间。

因此，在对计算机部件的控制中需要考虑两个问题：一是在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制；二是在指令集合中寻求总长度最小的若干指令，且能使所有的计算机部件得到控制。

1、建立解决上述两个问题的数学模型；

2、设计模型的求解算法，用表1.1所列数据给出求解结果；

3、分析设计算法的复杂性和计算所得到的结果。

表1.1 指令控制的部件和指令的长度

指令 指令所控制的部件 指令长度 指令 指令所控制的部件 指令长度

1 4，8，20，31，26 15 19 13，23，26，39 26

2 8，19，22，29，37 80 20 7，12，40，41 22

3 2，16，34，33，32 30 21 12，16，19，28，35 26

4 7，11，35，30 12 22 6，23，27，45 19

5 5，13，18，21 7 23 33，37，40，41 17

6 1，7，9，23，25 19 24 3，17，19，36 22

7 3，5，6，14，24 32 25 16，33，44，45 10

8 7，20，21，32，35 12 26 13，19，24，25 30

9 9，15，20，12 45 27 2，3，5，8 82

10 6，10，39，28，27 36 28 4，7，9，12，43 73

11 1，11，21，34，38 57 29 16，17，20，32 66

12 2，4，18，22，37 78 30 28，33，34，36 55

13 6，17，25，36 65 31 10，23，25，27 24

14 22，33，34，38 53 32 1，5，44，45 46

15 2，10，20，37 34 33 11，15，18，43 37

16 9，24，29，39 48 34 7，14，22，36 77

17 15，18，29，31 46 35 3，15，25，39 9

18 4，28，26，12 32 3 二、问题分析

计算机已经成为现代社会发展的不可取代的有利助手，而计算机控制更是遍及各个领域。因而对计算机指令控制部件并达到最优的研究具有深远的意义。

由于一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，这两都是线性规划问题且约束条件相同，只是两个题的目标函数不同。

针对问题一：模型一建立使得所有的部件得到控制的指令集合里的最少的指令模型。我们利用整数线性规划模型，列出所求优化问题目标函数和约束条件，并确保一个部件至少有1条指令控制，同时利用Lingo软件算出所有部件得到控制的最少指令的集合。

模型二将第一问转化为：在n指令集合选取最少的顶点使m通过边的关系全部被选中。

针对问题二：仍然建立整数规划模型，依然要保证一个部件至少有1条指令控制，再用Lingo算出所有部件得到控制的总长度的最小长度。

模型二将第二问则转化为：当将n的点全部赋权后,在n中找出权数总和最小的顶点集，使m全部被选中。

针对复杂度，我们分为时间复杂度和空间复杂度。然后通过各自的影响因素进行分析，由此确定此模型是否正确，并且是否最合适。

三、模型假设

根据题目要求，并为了达到简化的目的，我们首先做如下假设：

1. 假设每个部件都能被指令集合中一条或多条指令控制；

2. 假设每条指令在运行过程中不发生逻辑错误，且每个部件均工作正常；

3. 在指令控制部件的过程中我们只考虑指令和部件的对应性，而不考虑计算机指令控制过程中的延迟性等问题；

4. 不考虑计算机发送指令所用的时间。

四、符号说明

符号 表示含义

ija 第i个部件是否被第j条指令控制（0或1）

jx 是否使用第j条指令（0或1）

jl 第j条指令的长度

m 部件的总个数

n 部件的总条数 4 1f 所用指令的总条数

2f 所用指令的总长度

d 最小指令覆盖集合的元素个数

cov[m] 部件是否覆盖的标记数组

New[n] 各个指令控制的部件数

五、模型的建立与求解

模型一

5.1 问题一的模型建立及求解

5.1.1 问题一的模型建立

1）目标函数

问题一的目的是为了在指令集合中寻找条数最少的指令，使所有的计算机部件得到控制，变量xi为0-1变量，xj表示是否使用第j条指令，如果使用则xj=1，如果不使用则xj=0，所使用指令的总条数可以表示为j，则目标函数为：

11minnjjfx (5-1)

2）约束条件

在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，则可以设aij表示第i个部件接受第j条指令，若第i个部件受第j条指令控制，则aij =1，若第i个部件不受第j条指令控制，aij=0。aijxj表示第i个部件总共接收到的指令条数，一个部件至少有1条指令控制。

所以约束条件为：

11,1,2,3,...0,10,1nijjjijjaximax (5-2)

5.1.2 问题一的模型求解

在考虑了目标函数及约束条件了以后，我们先做出各个部件所需要的控制表（表5.1），然后通过Lingo编程（附录1）可以得出结果(表5.2).

表5.1各部件的控制指令表

部件 控制指令 部件 控制指令

1 6,11,32 2 3,12,15,27 5 3 7,24,27,35 4 1,12,18,28

5 5,7,27,32 6 7,10,13,22

7 4,6,8,20,28,34 8 1,2,27

9 6,9,16,28 10 10,15,31

11 4,11,33 12 20,21,28

13 5,19,26 14 7,34

15 9,17,33,35 16 3,21,25,29,

17 13,24,29 18 5,12,17,33

19 2,21,24,26 20 1,8,9,15,29

21 5,8,11 22

2,12,14,34

23 6,19,22,31 24 7,16,26

25 6,13,26,31,35 26 19

27 22,31 28 21,30

29 2,16,17 30 4

31 1,17 32 3,8,29

33 3,14,23,25,30 34 3,11,14,30

35 4,8,21 36 13,24,30,34

37 2,12,15,23 38 11,14

39 10,16,19,35 40 20,23

41 20,23 42 10,18

43 10,28,33 44 1,18,25,32

45 9,18,22,25,32

表5.2 所有部件得到控制的小指令集合

指令Xj X2 X4 X7 X11 X12 X17 X18

所控部件 3,12,15,27 1,12,18,28 4,6,8,20,28,34 4,11,33 20,21,

28 13,24,

29 5,12,

17,33

指令Xj X19 X20 X28 X29 X30 X31