最优指令控制的设计

最优化计算机指令控制设计摘要本文为了使计算机指令控制最优，建立了解决最优控制的整数规划模型。问题1，通过分析题意知，此问目标是求出使得所有部件得到控制的最少指令集合，约束为使各部件至少得到一次控制，建立了0-1整数规划模型，运用lingo软件求得最少的指令集合是2，4，7，11，12，17，18，19，20，28，29，30，31，共13条指令。问题2，此问目标变为求出使得所有部件得到控制的总长度最短的指令集合，约束条件与问题1相同，同样的建立0-1整数规划模型，运用lingo软件求得总长度最小的指令集合是1，3，4，5，6，7，10，14，17，19，21，22，23，24，总长度为360。问题3，首先介绍了单纯形法和穷举法，再根据这两种算法的原理运用Matlab软件来求解问题，得到的最优解同问题1和问题2。问题4，对所设计算法的时间复杂度和空间复杂度以及对计算所得结果进行了分析。关键词：计算机指令优化控制0-1整数规划单纯形算法穷举法一．问题的重述在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制。一个根本的问题是，在指令集合里寻找最少的指令，使得所有的部件得到控制；另一个问题是，当给定每条指令的长度时，在指令集合里，寻找总长度最小的假设干指令，使得他们可以控制全部部件。对于上面两个问题，建立如下两个数学模型：建立使得所有部件得到控制的最少指令集合；建立是所有部件得到控制的总长度最小的指令集合；再给出指令控制的部件和指令的长度后如表1所示，用所建立的数学模型对表1所列的数据求出结果。设计模型的求解算法，用表1中所示的数据给出求解结果；分析所设计算法的复杂性和计算所得到的结果。表1指令控制的部件和指令的长度指令指令所控制的部件指令的长度指令指令所控制的部件指令的长度14，8，20，31，44151913，23，26，392628，19，22，29，3780207，12，40，412232，16，34，33，320302112，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，4545272，3，5，882106，10，39，42，4336284，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，3991842，44，4，4532二．问题的分析2.1对问题1的分析问题1中，目标是求出使得所有部件得到控制的最少指令集合。为了实现这个目标，设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。此问属于典型的整数规划模型，故此可以设立0-1变量，建立0-1整数规划模型。2.2对问题2的分析问题2相对问题1而言，只是目标有所变化，其实质是一样的，同样可以设立0-1变量，建立0-1整数规划模型。2.3对问题3的分析问题3要求我们设计模型的求解算法，最后再求出结果。对于一般的0-1整数规划模型，有很多算法可以实现，常见的有：分支定界法，穷举法，贪婪算法，单纯形法和遗传算法。故此，本模型就可采用其中几种不同算法对模型进行分析求解。2.4对问题4的分析问题4要求我们分析所设计算法的复杂性和计算所得到的结果，复杂性分析是多方面的，要从时间和空间以及适应性等角度去分析。三．模型的假设和符号的说明3.1模型的假设1.假设每个部件都能被指令集合中一条或多条指令控制；2.假设每条指令在运行时都不发生逻辑错误,且每个部件均正常工作；3.假设控制同一部件的指令间无优先关系；4.假设一条指令控制多个部件时无优先关系；5.在指令控制部件的过程中我们只考虑指令和部件的对应性,而不考虑计算机指令控制过程中的延迟性等问题。3.2符号的说明符号表示意义第i条指令是否使用第i条指令是否控制第j个部件m表示指令总数n表示部件总数F表示使用指令的总数L表示使用指令的总长度四．模型的准备4.1线性规划线性规划问题：求多变量线性函数在线性约束条件下的最优值。线性规划的一般形式：线性规划问题的标准形式：任意线性规划问题可化为标准形式。具体如下：1.目标函数标准化2.约束条件标准化假设约束条件中有不等式约束或引入新变量〔称为松弛变量〕，那么以上两式等价于以下两式：3.自由变量标准化假设变量无约束，可引入两个新变量，，令=-，，故以下我们只考虑标准形式，也可以用矩阵形式表示为一般要求，4.2单纯形法定理一：1、线性规划问题的可行域是一个凸多边形；2、线性规划问题如果存在最优解，那么最优解必在可行域的顶点处到达。可行域的顶点称为根本可行解。根本思想：从可行域的一个顶点〔根本可行解〕出发，转换到另一个顶点，并且使函数值逐步减小，有限步后可得到最优解。五．模型的建立5.1问题1模型的建立第一问目标是求出使得所有部件得到控制的最少指令集合。为了实现这个目标，设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。设置变量，令其中，m,n分别表示指令总数和部件总数。目标函数：〔F表示使用指令的总数〕约束条件：用表示第条指令与第个部件的关系，如果第个部件能被第条指令控制，那么=1，否那么=0。易知表示第个部件是否得到指令集合中的一条或多条指令的控制，当1时，表示第个部件得到指令集合中至少一条指令的控制。所以，可得到该问题的于约束条件为：矩阵形式为：综上所述，对问题一建立数学模型=1\*ROMANI：5.2问题2模型的建立第二问模型建立和第一问类似，只是目标变为求出使得所有部件得到控制的总长度最短的指令集合。为了实现这个目标，也设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。设置变量，令其中，，分别表示指令总数和部件总数。使表示各个指令的长度，那么目标函数为：〔L表示使用指令的总长度〕约束条件：用表示第条指令与第个部件的关系，如果第个部件能被第条指令控制，那么=1，否那么=0。易知表示第个部件是否得到指令集合中的一条或多条指令的控制，当1时，表示第个部件得到指令集合中至少一条指令的控制。所以，可得到该问题的于约束条件为：矩阵形式为：综上所述，对问题二建立数学模型=2\*ROMANII：六．算法的设计和模型的求解根据题目表1-1中的数据，我们利用之前建立的问题1模型和问题2模型求解得使所有部件得到的控制的最小指令集合和总长度最少的指令集合。6.1算法的设计第一种算法：单纯形法单纯形法是线性规划问题的一般解法，其根本思想是寻找一个基的可行解(极点)，便可以通过有限步的迭代找到问题的最优解。求解问题1用单纯形的二阶段法：第一阶段：第一步将数学模型的线性规划转化为单纯形法的标准形式(由于原始问题全部由“”约束条件构成．因此还需添加人工变量和剩余变量)本问题约束矩阵M=〔A，l，K)，其中A是系数矩阵，l和K分别是m阶单位矩阵，Z表示人工变量的和。辅助目标函数：将其转化为求最大值问题：同样目标函数转化约束方程组为：第二步检验各非基变量的检验系数，此题如果都成立那么基可行解已是最优解解计算结束；否那么转为下一步。第三步以辅助目标函数为判断依据进行迭代．选取辅助目标函数中具有非负系选取辅助目标函数中具有非负系数的非基变量(假设是)，作为进人下一个根本可行解的进基变量，然后转入下面介绍的第四步．如果此时所有系数均为非负，就得到辅助目标函数的最优解．假设此时的辅助目标函数值为零，并且所有人工变量均不在基内，这就得到了原始问题的一个根本可行解，然后就转入第二阶段计算；如果此时辅助目标函数值不为零，那么人工变量至少还有一个仍留在基内取非零的正值，那么原始问题就没有可行解，那么停止运算，转至第六步．第四步由进基变量，满足为出基变量。第五步以为主元进行迭代，把基变量转化为非基变量，重复一到五直到得到结果。第六步如果没有可行解那么根据题意设x都为1。第二阶段：去掉辅助目标函数所在的行和列，然后以原目标函数代替第一阶段的辅助目标函数作为判断依据，进行单纯形法迭代．运算步骤同第一阶段中第一至五步相类似(注意将第二步中j的范围定为到)，直到得到原线性规划问题的最优解．2．求解问题2的算法根据模型的相似性只需将求解问题1中的目标函数改为：即可，算法与求解问题1的相同．第二种算法：穷举法穷举法可以解决这种线性规划问题。第一步建立循序的约束条件，根据模型=1\*ROMANI可知：第二步通过运行得到的满足条件的指令结果，即得到了所以的可以控制所有部件的指令集合。我们再根据目标函数所要要求的，在这些结果，我们分别定义不同的目标函数，找到最少的指令条数集合和总长度最短的指令集合。第三种算法：lingo求解我们已经建立了模型=1\*ROMANI和模型=2\*ROMANII，可以直接通过lingo软件来解决问题，只要输入目标函数和约束条件，就可以得到结果。6.2对问题1模型的求解数据的分析由于模型的要求，对表1进行重新排列，改变表1按照指令排布，转为用部件为变量排布，这就是下面的表2：表2每个部件指令相对应的控制指令说明部件控制部件的指令部件控制部件的指令16，11，32247，16，2623，12，15，27256，13，26，31，3537，24，27，35261941，12，18，282722，3155，7，27，322821，3167，10，13，22292，16，1774，6，8，20，28，28，3430481,2,27311，1796,9,16,28323，8，291010,15,31333，14，23，25，30114,11,33343，11，14，33，1220,21,28354，8，21135,19,263613，24，30，34147,34372，12，15，23159,17,33,353811，14163,21,25,293910，16，19，351713,24,294020，231813,24,294120，23195,12,24,264210，18201，8，9，15，294310，28，33215，8，11441，18，25，32222，12，14，34459,,，18，22，25，32236，19，22，31模型的求解1第一种算法可以用matlab编写单纯形法的程序〔见附录1〕，结果如下表3所示。表3matlab运行结果指令1234567891011Xi01010010001指令1213141516171819202122Xi10000111100指令2324252627282930313233Xi00000111100指令3435Xi00总结可得：最少的指令集合是｛2，4，7，11，12，17，18，19，20，28，29，30，31｝；2第二种算法可以用matlab程序实现穷举法〔附录2〕，可以得到和单纯形法相同的结果。结果如下表4所示。表4matlab运行结果指令1234567891011Xi01010010001指令1213141516171819202122Xi10000111100指令2324252627282930313233Xi00000111100指令3435Xi00总结可得：最少的指令集合是｛2，4，7，11，12，17，18，19，20，28，29，30，31｝;3第三种算法直接使用lingo软件解决问题〔附录3〕。同样得到了结果如下表5所示。表1-5lingo的运行结果表格指令1234567891011Xi01010010001指令1213141516171819202122Xi10000111100指令2324252627282930313233Xi00000111100指令3435Xi00总结可得：最少的指令集合是｛2，4，7，11，12，17，18，19，20，28，29，30，31｝;6.3对问题2模型的求解数据的分析我们同样用到表2的数据,只是改变了目标函数。模型的求解1第一种算法也可以用matlab编写单纯形法的程序，和模型=1\*ROMANI的程序相同，只是改编了目标函数，可以得到下表6所示结果。表6matlab运行结果指令1234567891011Xi10111110010指令1213141516171819202122Xi00100101011指令2324252627282930313233Xi11000000000指令3435Xi00总结可得：总长度最小的集合是｛1，3，4，5，6，7，10，14，17，19，21，22，23，24｝，总长度为360。2第二种算法是用matlab程序实现穷举法〔见附录2〕，可以得到和单纯形法相同的结果。结果如下表7所示。表7matlab运行结果指令1234567891011Xi10111110010指令1213141516171819202122Xi00100101011指令2324252627282930313233Xi11000000000指令3435Xi00总结可得：总长度最小的集合是｛1，3，4，5，6，7，10，14，17，19，21，22，23，24｝，总长度为360。3第三种算法直接使用lingo软件解决问题〔见附录5〕。同样我们得到了下表8所示结果。表8lingo运行结果指令1234567891011Xi10111110010指令1213141516171819202122Xi00100101011指令2324252627282930313233Xi11000000000指令3435Xi00总结可得：总长度最小的集合是｛1，3，4，5，6，7，10，14，17，19，21，22，23，24｝，总长度为360。6.4模型补充由前面已经得出最小的模型集合为13，但lingo软件只能给出一个的解，并不代表没有其他可能。所以，例如先前最优解中X12=0,假设还有一组解中X12=1，那么改变目标函数在原有根底上减去0.1*X12。那么可以求出时的解同时满足最优解是13.最优解四组Xj=1如下，1.j=4,10,11,16,17,18,19,21,23,27,29,31,342.j=2,4,7,11,12,17,18,19,23,28,29,30,313.j=1,2,4,7,9,10,11,12,19,20,29,30,314.j=2,4,7,11,15,17,18,19,20,28,29,30,31七．算法的复杂性和结果的分析7.1单纯形法求解此题的复杂性分析如下：第一、计算时间的复杂性．显然对于单纯形法，约束及变量的个数影响其计算速度，对于最坏情况下的单纯形法需要迭代〔为约束个数)次才能求出最优解，但对此题的计算时间不超过．这是因为数以千计的实际问题计算经验告诉我们，迭代次数一般在次至次之间．有时缺乏次。大规模的迭代情况是极少出现的，因此单纯形法为计算该题的一种有效算法。第二、计算空间的复杂性．针对计算机编程求解过程，单纯形法程序的的缺点主要表达在以下两点：首先，单纯形法求解程序在求解约束方程较多、数据量较大(上万)时，运行较为费时，且数据存储所占内存空间较多，运行迭代过程过于复杂。其次，由于运算过程中的屡次迭带而产生的屡次除法运算，从而使得运算精度下降。7.2穷举法求解此题的复杂性分析如下：第一．计算时间的复杂性。对于穷举法来讲，优点是程序简单，缺点是计算量很大，例如要处理表1的数据计算机将要花费大约2个小时才能出结果。7.3lingo求解此题的复杂性分析如下：Lingo的程序十分简单，而且计算机的运行时间短，所以效率最高。八．模型的分析和评价6.1模型的分析本文所用模型为典型整数规划模型，设置0-1变量将实际问题转化为数学模型，实用且易于操作，具有广泛的应用性，并且可以用多种算法进行实现。6.2模型的评价本模型对计算机指令优化控制问题作出了细致的分析，提出了模型的算法，并对本题所给数据进行了计算求解，最后用数学软件lingo检验了结果的正确性。九．模型的推广最优控制理论是现代控制理论的一个主要分支，着重于研究使控制系统的性能指标实现最优化的根本条件和综合方法。最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。它是现代控制理论的重要组成局部。采用控制优化的方法往往可以到达满意的效果，而且设计简单应用方便，易于掌握。随着科学技术的开展对自动控制系统的控制精度，响应速度，系统稳定性和适应能力的要求越来越高，对于大多复杂的对象。采用控制优化的方法往往可以到达满意的效果，而且设计简单应用方便，易于掌握。本模型也适用于其他类似问题,且规划明确简单,易于操作,而且算法实用性强,所得结果还是令人满意的。十．参考文献[1]姜启源，数学建模[M]，北京：高等教育出版社，2003。[2]何建坤，实用线性规划及计算机程序[M]，北京：清华大学出版社，1985。[3]胡运权，运筹学根底及应用[M]，哈尔滨：哈尔滨工业大学出版社，1998。[4]曹楠，师鹏，杨阳，计算机指令优化控制模型[J]，数学的实践与认识，34(4)：5-10,2004附录附录1用于求解问题1的lingo源程序：model:!程序用来求解控制全部部件的最少指令集合;!目标函数;min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35;!约束条件;x6+x11+x32>=1;x3+x12+x15+x27>=1;x7+x24+x27+x35>=1;x1+x12+x18+x28>=1;x5+x7+x27+x32>=1;x7+x10+x13+x22>=1;x4+x6+x8+x20+x28+x34>=1;x1+x2+x27>=1;x6+x9+x16+x28>=1;x10+x15+x31>=1;x4+x11+x33>=1;x20+x21+x28>=1;x5+x19+x26>=1;x7+x34>=1;x9+x17+x33+x35>=1;x3+x21+x25+x29>=1;x13+x24+x29>=1;x5+x12+x17+x33>=1;x2+x21+x24+x26>=1;x1+x8+x9+x15+x29>=1;x5+x8+x11>=1;x2+x12+x14+x34>=1;x6+x19+x22+x31>=1;x7+x16+x26>=1;x6+x13+x26+x31+x35>=1;x19>=1;x22+x31>=1;x21+x30>=1;x2+x16+x17>=1;x4>=1;x1+x17>=1;x3+x8+x29>=1;x3+x14+x23+x25+x30>=1;x3+x11+x14+x33>=1;x4+x8+x21>=1;x13+x24+x30+x34>=1;x2+x12+x15+x23>=1;x11+x14>=1;x10+x16+x19+x35>=1;x20+x23>=1;x20+x23>=1;x10+x18>=1;x10+x28+x33>=1;x1+x18+x25+x32>=1;x9+x18+x22+x25+x32>=1;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9);@bin(x10);@bin(x11);@bin(x12);@bin(x13);@bin(x14);@bin(x15);@bin(x16);@bin(x17);@bin(x18);@bin(x19);@bin(x20);@bin(x21);@bin(x22);@bin(x23);@bin(x24);@bin(x25);@bin(x26);@bin(x27);@bin(x28);@bin(x29);@bin(x30);@bin(x31);@bin(x32);@bin(x33);@bin(x34);@bin(x35);End附录2用于求解问题2的lingo程序：model:!程序用来求解控制全部部件的最短指令长度集合;!目标函数;min=15*x1+80*x2+30*x3+12*x4+7*x5+19*x6+32*x7+12*x8+45*x9+36*x10+57*x11+78*x12+65*x13+53*x14+34*x15+48*x16+46*x17+32*x18+26*x19+22*x20+26*x21+19*x22+17*x23+22*x24+10*x25+30*x26+82*x27+73*x28+66*x29+55*x30+24*x31+46*x32+37*x33+77*x34+9*x35;!约束条件;x6+x11+x32>=1;x3+x12+x15+x27>=1;x7+x24+x27+x35>=1;x1+x12+x18+x28>=1;x5+x7+x27+x32>=1;x7+x10+x13+x22>=1;x4+x6+x8+x20+x28+x34>=1;x1+x2+x27>=1;x6+x9+x16+x28>=1;x10+x15+x31>=1;x4+x11+x33>=1;x20+x21+x28>=1;x5+x19+x26>=1;x7+x34>=1;x9+x17+x33+x35>=1;x3+x21+x25+x29>=1;x13+x24+x29>=1;x5+x12+x17+x33>=1;x2+x21+x24+x26>=1;x1+x8+x9+x15+x29>=1;x5+x8+x11>=1;x2+x12+x14+x34>=1;x6+x19+x22+x31>=1;x7+x16+x26>=1;x6+x13+x26+x31+x35>=1;x19>=1;x22+x31>=1;x21+x30>=1;x2+x16+x17>=1;x4>=1;x1+x17>=1;x3+x8+x29>=1;x3+x14+x23+x25+x30>=1;x3+x11+x14+x33>=1;x4+x8+x21>=1;x13+x24+x30+x34>=1;x2+x12+x15+x23>=1;x11+x14>=1;x10+x16+x19+x35>=1;x20+x23>=1;x20+x23>=1;x10+x18>=1;x10+x28+x33>=1;x1+x18+x25+x32>=1;x9+x18+x22+x25+x32>=1;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9);@bin(x10);@bin(x11);@bin(x12);@bin(x13);@bin(x14);@bin(x15);@bin(x16);@bin(x17);@bin(x18);@bin(x19);@bin(x20);@bin(x21);@bin(x22);@bin(x23);@bin(x24);@bin(x25);@bin(x26);@bin(x27);@bin(x28);@bin(x29);@bin(x30);@bin(x31);@bin(x32);@bin(x33);@bin(x34);@bin(x35);End附录3用于求解问题1的Matlab程序：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,0,-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];f=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];b=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]';Aeq=[];Beq=[];[x,fval]=bintprog(f,A,b,Aeq,Beq)附录4用于求解问题2的Matlab程序：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,0,-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