设备最有维修次序.docx

兰州交通大学2010年大学生数学建摸竞赛论文题目：多台设备同时故障的最优维修次序参赛人1： 姓名 郭军军 学院 自动化学院 班级 电气073 参赛人2： 姓名 陈利锋 学院 自动化学院 班级 自动化071 参赛人3： 姓名 赵建祥 学院 数理学院 班级 软件071 学校统一编号，个人不得填写论文编号： 多台设备同时故障的最优维修次序摘要要让n台设备停工造成的总经济损失最小，至关重要的一步就是，将这个很难求解最小值的总经济损失问题，转化为易于求解的数学模型。本文在合理假设的基础上，把多个因子对总经济损失的影响综合起来考虑，建立一个总经济损失和已知因子的关系。进而抽象出数学模型。通过分析知，为使经济损失尽可能小，要将维修时间相对最短的和每小时损失相对最大的设备先维修。这儿要求先维修机器的维修时间短，是因为不让这台机器的维修耽搁了后面机器的维修；要求每小时损失大，是因为要让每小时损失大的尽可能早的维修。这样，就可以是二者的影响得到合理的折中，使得使总的经济损失最低。接下来，分析了每台机器的维修时间和每小时的损失这两个变量对总经济损失的影响情况，就可以把它们对总经济损失的影响，用一个参考因子f(t)/g(l)表示。同时本文也给各模型给出了严密的证明，从而保证了整个建模过程的严密性。 通过上面的分析，知f(t)/g(l)越小，总损失就越小。这样便可以将求最低损失的问题，转化为求这个影响因素非递减排序的问题。继而可以根据这一衡量标准来寻求我们希望得到的设备维修最优次序。使得整个问题能以最优排序的方式解决。在模型确立之后，本文通过以选择排序为核心的C语言程序给模型做了求解，该算法的时间复杂度是O(n2)。同时为了保证结果的正确，我们用了以Johnson-trotter为核心的算法做了验证。问题一的最优维修次序是：2-5-6-3-1-4-7，问题二的最小损失是117.3，第三问是问题一的简单推广。本文采用了先确定影响变量，再确定影响变量和总损失之间的关系的思路。这也让问题的模型具有创新性和简洁性。同时又通过推理论证和结果验证使得问题的准确性提高。关键词：最优排序 Johnson-trotter算法 枚举法 变治思想1、问题提出最近几年，对最优排序问题的研究越来越接近实际生活。当今社会的各个领域，都存在着不同类型的最优排序问题。在企业生产中，生产设备都会在一定的寿命期内出现各种原因的故障，需要对故障设备进行维修后才能继续用于正常的生产。对设备的维修需要企业负担一定的维修成本和因设备故障耽误生产而造成的经济损失。因此为了使企业的经济损失降到最低，就要对故障设备及时进行维修，使维修好的设备马上投入生产，维修工人继续维修其他受损设备。但是不同的故障设备所造成的经济损失和需要的维修时间是不同的，如果在多台设备出现故障而维修工人数量少于故障设备数量时，不同的维修次序会造成不同的经济损失。因此，在企业生产管理中需要寻求一种最优的维修次序，使得故障设备对企业所造成的经济损失达到最小。 本论文的研究需要解决以下几个问题： 1） 同时考虑各故障设备在特定的维修次序下维修所需时间和单位时间内停工所造成的损失对总经济损失大小的影响，寻求一种解决方案，使二者对总经济损失的约束达到某种程度上的平衡。2） 在只有一名维修工人的情况下，同时有7台设备需要维修，而每台设备的维修时间和其在单位时间内停工造成的损失都是已知的，通过分析给定的各个设备的具体参数，根据各设备在特定维修次序下对总经济损失大小的影响程度，建立使总损失达到最小的最优排序模型。3） 在上述问题2）中，如果维修工人有两名，每台设备的维修只能由其中一人单独完成，求出在这种情况下使总经济损失最小的最优维修次序。4） 对问题2）进行简单的推广，如果同时有n台设备需要维修，而每台设备的维修时间和其在单位时间内停工造成的损失都是已知的，并且只有一名维修工人的情形下，建立使总损失达到最小的数学模型，并给出求解算法。5） 对建模过程中所涉及的模型，设计一种简单快速的计算方法，并用计算机实现。6） 对模型结果做出细致精确的分析，讨论误差存在的原因并指出能减小或消除误差的改进措施。2、问题分析问题(1)使损失最低的维修次序，就是所求的最优维修次序。现在我们考虑的问题转化为保证损失最低的情况下，哪台机器应先维修的问题。通过分析知，为使经济损失尽可能小，要将维修时间最短的、每小时损失最大的先进行维修。这儿要求先维修机器的维修时间短，是因为不让这台机器的维修耽搁了后面机器的维修；要求每小时损失最大，是因为要让每小时损失大的尽可能早的维修。这样，就能够使总的经济损失最低。接下来，我们分析了每台机器的维修时间和每小时的损失,这两个变量对经济损失的影响情况，就可以把它们对总经济损失的影响，用两个函数f(t)、g(l)表示。通过上一段的分析，知f(t)/g(l)越大，总损失就越大。这样，我们只要确定f(t),g(l)，就能够通过f(t)/g(l)的次序，就能够确定使损失最小的维修次序。为最严密期间，我们又对我们的结论进行了证明。问题(2) 由问题(1)可知，影响设备维修次序的因素只与单台设备的维修时间和每小时的损失有关，所以很庆幸，在有m(1=mn时，前n名维修工同时修这n台设备就可以了。)名维修人员的情况下和只有一名维修人员的时候的维修次序基本一样，刚开始让m名维修工任意先维修前m台设备，m名当中谁先完成了任务就紧接做m+1台设备，依次类推只剩最后两台设备的时候，m名当中的前两名就开始选择剩下的两台设备维修，由于这两名维修工可能不是同时完成维修工作，如果是同时完成，两名维修工任意各修一台，如果不是同时完成，两台设备要么同一人完成，要么两人完成，这由t决定，设先维修完的一名员与另一位员工完成维修设备之间的时间差记为t，ttn-1则同一人完成，此时只按问题（1）的维修次序做就可以了，如果ttn-1则由同一人或者两人完成，为了归类简单，在此规定由两人完成。正因为有t，所以维修员工此时选择后面的两台设备之一时会让另一台设备的损失增加，为使损失最小，必须选择一个最优的次序。怎样才能做到损失最小就是关键问题，我们初步猜想如果选择第n-1台设备使第n台设备增加的损失为ln，选择第n台设备使第n-1台设备增加的损失为ln-1，如果lnt 先维修第n台设备给第n-1台造成的损失为：Ln-1=ln-1tLnLn-1 先维修第n-1台,否则修第n台 1Lnt 先维修第n-1台设备给第n台造成的损失为：Ln=lnttnt 先维修第n台设备给第n-1台造成的损失为：Ln-1=ln-1tntnt 先维修第n台设备给第n-1台造成的损失为：Ln-1=ln-1tLnLn-1 先维修第n-1台,否则修第n台 3LnLn-1 先维修第n-1台，否则修第n台 (4)化简：由1式得：lntn-1ln-1tn tn-1ln-1tnln (5)由2式得: lntn-1ln-1t tn-1ln-1t ln (6)由于是在tn-1t 的情况下推出的，易知(5),(6)是必然成立的，所以在这种条件下两名维修工是按问题（1）的次序完全进行的。由3式得：lntln-1tn tln-1tnln (7)由4式得: lntln-1t lnt 的情况下推出的, 易知(7)是必然成立的.所以在此种条件两名维修工修完前n-2台设备后，先修完的一名就选择li较大者先维修。设 c1,c2,c7为问题1的最优次序，为了方便起见，p1先修次序号为c1的设备，p2在修次序号为c2的设备。开始时 T1c1=txc1，T2c2=txc2; m1=1, m2=1.如果， T1c1T2c2 p1先维修次序为c3的设备，此时 m1=m1+1。否则， p2先维修次序为c3的设备，此时 m2=m2+1。依次判断到剩下最后两台设备，有上面的证明易知最后两台设备在两名维修工的情况下的次序，能最终得出：p1的次序为 c11，c12，c1mp2的次序为 c21，c22，c2m所以， p1 ：L总1=i=1 m1lxc1iTc1iTc1i=j=1 itxc1jp2 ：L总2=i=1 m2lxc2iTc2iTc2i=j=1 itxc2j求解在后面的附录全部用程序以实现，结果为：5.4问题（3）模型的建立与求解问题只是在问题（1）的前提下进行了推广。类似地，对于一名维修工时的最优次序为：c1,c2,cn模型：L总=Mini=1nlxiTcxiTi=j=1iTxci模型的求解同问题（1）相同，在此不再累赘。6、结果分析与检验6.1、问题1的求解过程对于这个模型，考虑到同时故障的设备不会太多，所以我们只需简单的选择排序就可以解决。这个算法的时间复杂度是O(n2),在n不是很大时，这个算法也并不亚于快速排序，要知道快速排序也会退化到O(n2)的。这个算法实在太简单，所以在此只给出计算结果，详细代码见附录，计算结果如图2所示。为保险起见，我们又再次用枚举法进行了验证。在此，我们选用最优的排序算法，Johnson-trotter算法生成n台设备的维修次序。下面简单对鼎鼎大名的Johnson-trotter算法做一简单介绍：我们给一个排列中的每个元素k赋予一个方向，如果元素k的箭头指向一个相邻的较小元素，我们说它在这个以箭头标记的排列中是移动的。例如，对于排列3 2 4 1来说，3和4是可移动的，而1,2不是。下面给出这个算法的流程图，详细代码见附录，计算结果如图3。开始输入一个正整数n存在一个可移动元素 N求最大的可移动元素 Y交换k和k箭头所指的元素调转所有大于k的元素的方向降薪排列加入到列表结束图1 Johnson-trotter算法下面分别是用我们严格证明过的模型和枚举法做出的结果。然而，由于内存都写错误，所以会和真实值之间有一个很小的误差。毫无疑问，二者相同。图2 问题1模型求解结果图3问题1Johnson-trotter求解结果6.2问题2的求解过程开始输入问题1的最优次序已维修次序in N YWorker1TimeWorker2Time Y N YWorker1 修第i个设备Worker2 修第i个设备终止下面分别是用我们严格证明过的模型和枚举法做出的结果。然而，由于内存都写错误，所以会和真实值之间有一个很小的误差。毫无疑问，二者相同。图5 问题2模型求解结果图6问题2Johnson-trotter求解结果6、模型的分析与评价在此模型中，我们采用了现实生活中遇到此问题很普遍的做法，就是选维修时间最小且停工造成的损失最大的那台故障设备先维修的思想进行的。这两者的折中方法就是 t1/l1 最小者先维修，且在模型中已充分证明按 t1/l1 非递减进行故障设备的维修次序进行维修造成的经济损失是最小的，即 L总i=L总(1=i=n)。在维修人员（m）少于故障设备（n）的数量时，由于维修次序是一定的，而只是让m名维修员工依次对故障设备进行维修即可。模型的建立简单易懂，计算过程用程序实现，结果精确。当然，模型也有很多不足之处，模型只是在考虑了维修时间不变及单位时间内造成的经济损失一定的两个因素下所建立的，还有诸多影响模型的因素并没有考虑，例如：维修各台设备的成本，先维修好的设备投入生产带给企业的收益，不同的维修人员维修各台设备的用时一般不同，及设备是否在规定的时间里能完全修好等等。要建立一个较好的能适用于社会生产的模型，应将考虑到上面所提到诸多因素，以及一些其它的细节，能做到这些所建立的模型将更适用现实社会。参考文献1 姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2003。2 Anany Levitin 算法设计与分析基础 北京：清华大学出版社 2007附录/*model.h*Define struct machineRepair*/#ifndef _MODEL_H#define _MODEL_H#define DEBUG0#include #include using namespace std;#define MACHINE_AMOUNT7struct MachineRepairintrepairTime;floatloss;#endif/*_MODEL_H*/* Arrangement.h* Define struct Arrangement * That defines elements of permutation* Use Johnson-trotter algorithm*/#ifndef _ARRANGEMENT_H#define _ARRANGEMENT_H#define DEBUG0#include #include using namespace std;#define NUM7#define PRINT_AVAILABLE0#define MINLOSS1typedef int elemType;struct Arrangementbool direction;elemType value;#endif /*_GETARRANGE_H*/* Arrangement.cpp* use Johnson-Trotter algorithm*/#include Arrangement.h#include model.h#include debug.hvoid initialize(Arrangement arr);void initMach(MachineRepair machRep);void initDestArr(int destArr);bool existMoveElem(Arrangement arr , int *maxElemAddr);void swap(Arrangement *arr1 , Arrangement *arr2);void arrayCopy(int destArr, Arrangement srcArr);void switchLarger(Arrangement arr ,int maxElem);void print(Arrangement arr, int count);float getLoss(MachineRepair machRep, Arrangement arr);void printArrange(Arrangement arr);void printSequence(int destArr);/ Two workers repair the machines.float getLossWhenTwo(MachineRepair machRep, Arrangement arr);int main(void)Arrangement arrNUM;printArrange(arr);return 0;void printArrange(Arrangement arr)bool moveFlag = false;int maxElem = 0;int