教学设备更新问题动态规划算法的C语言实现.doc

教学设备更新问题动态规划算法的C语言实现摘 要：公司购买的教学设备每年都会创造一定的利润，但是随着教学设备使用年限的增加，教学设备的维修费用也会增加，同时教学设备创造的利润也会随教学设备的老化而逐年降低，因此我们要对已老化的教学设备进行更新。这就带来了一个问题，何时更新教学设备才能为公司带来最大的利润。本文将利用动态规划算法来解决这一问题，并通过C语言来实现它。关键词：教学设备更新；算法；程序；C语言11 教学设备更新的原因分析随着经济社会的高速发展，当代社会对各种资源的需求也日益增加，因此资源的利用率对经济的促进作用也日渐凸显。为了满足公司建筑物布局和规划的发展，对教学设备的需求量和功能要求也不断提高。然而，随着教学设备使用时间的增长，教学设备的技术状况会逐渐劣化，其价值和使用价值也会逐渐降低。我们把引起这些变化的原因统称为磨损，教学设备的磨损是导致教学设备更新的根本原因。教学设备的磨损又分为有形磨损和无形磨损，因此教学设备的磨损是有形磨损和无形磨损的共同结果。 (1)教学设备的有形磨损（物质磨损）。教学设备的有形磨损是指教学设备在使用或闲置过程中所发生的实体磨损，它又可以分为第I类有形磨损和第II类有形磨损。其中第一类有形磨损是指教学设备在运转的过程中由外力的作用所造成的磨损，它跟教学设备的使用频率和使用强度有关，例如教学设备各部件尺寸的改变甚至变形，实体损失等，这类磨损会导致教学设备的精度，效率有所下降。第二类有形磨损跟教学设备的运转过程无关，它是指教学设备在自然力的作用下所发生的磨损，例如教学设备会腐蚀，生锈，风化等。由此可以看出，教学设备的有形磨损会导致教学设备整体性能的下降和使用价值的降低，甚至发生故障，难以继续正常工作，这些都会降低企业和工厂的生产效率，使企业在市场竞争中处于劣势，进而使企业和工厂的利润减少甚至出现亏损。(2)教学设备的无形磨损。教学设备的无形磨损不是由自然力和外力所引起的磨损，在这种情况下，教学设备的实体没有产生损失，而是教学设备原始价值的降低，它也可以分为第一类无形磨损和第二类无形磨损。第一类无形磨损是指随着劳动生产率的不断提高，生产该教学设备的成本不断降低，而原来购买的教学设备价值出现了贬值。由此可以看出，第一类无形磨损只会导致教学设备原始的价值减少，但不会影响教学设备的正常使用，也不会降低企业的劳动生产率。第二类无形磨损是指随着生产该教学设备的技术升级或者工艺的不断完善，生产出了比原来的教学设备更加先进，生产效率更高，耗费原材料和能源更少的新型教学设备，使原有教学设备在技术上显得陈旧落后。第二类无形磨损会直接导致教学设备的使用价值降低甚至丧失使用价值，因为如果继续使用原来的教学设备，会严重影响企业的生产率，或者生产的产品无法满足社会的新需求，从而使企业丧失市场竞争力。通过上面对教学设备磨损的具体分析可以看出，为了维持企业生产的正常进行，必须对教学设备的磨损进行补偿。由于机器教学设备遭受磨损的原因不同，因此补偿磨损的方式也不一样，它可以分为局部补偿和完全补偿两种方式。局部补偿是对教学设备进行维修或现代化改造，完全补偿是指直接更换教学设备。12 教学设备更新问题的提出为了对教学设备的磨损进行补偿，我们可以采取维修和更换两种策略（对教学设备的现代化改造可视为维修）。毫无疑问，教学设备的维修和更换都会增加企业的利润。如果采用直接更换教学设备的方法，与维修教学设备相比，它会带来更多的利润，但是投入的成本也会增加。一般来讲，企业进行生产和服务是为了追求利润的最大化，采用何种更新策略才能得到最大的利润呢？我们一般用年值法进行比较，也就是每年年末企业能得到的总利润之和。如果采用维修教学设备的策略，则企业当年所得利润可以表示为：企业当年利润=企业当年生产所创造的利润-当年维修教学设备的费用。如果采用更新教学设备的策略，则企业当年所得利润=企业当年生产创造的利润-当年更新教学设备所花的费用。通过上面的分析可以看出，企业通常可以通过比较当年所得的利润来选择采用何种策略更新教学设备，但问题却没有这么简单，因为企业生产不仅仅是为了追求一年的利润，企业还要进行生产的扩大化和一段时间内的利润最大化（通常为几年或十几年）。因此，我们所讲的教学设备更新策略，并不是一年的更新策略，而是连续多年的更新策略，这里的连续多年也就是我们所称的决策年限，例如教学设备的决策年限为四年，教学设备的更新策略指的就是对教学设备在第二年，第三年，第四年的更换或者继续使用做出选择，以达到利润的最大化。通常情况下，新教学设备往往具有较高的购置费和较低的运营成本，而要维修的旧教学设备往往具有较高的运营费。也就是说，随着教学设备使用年限的增加，对教学设备维修所付的费用也会随之增加，但较之教学设备的更换，所付出的费用则要少得多，反之，如果选择更新教学设备，则需付出较多的购置费，而其运营成本要相对少一点，与此同时，与维修教学设备相比，更换教学设备的当年所创造的利润也比较多。如果选择持续维修，其维修费会逐年增加，教学设备创造的利润也会逐年降低，并且教学设备的效率也会逐年降低甚至无法运转；如果选择持续更换，虽然创造的利润会比较多，其维护成本也比较低，但需付出高昂的购置费用，这会导致企业成本激增甚至出现亏损。这才是真正的问题所在，教学设备更新策略，就是从宏观上决定在一段时间内，对于教学设备在每年的更新与否做出决策，从而达到利润的最大化。2 教学设备更新的实现21 动态规划简介讲解动态规划之前，有必要简单了解一下贪婪法。在一个问题的若干阶段中，贪婪法只追求的是每个阶段当前的最优解，该算法过分依赖过去所做的选择，而不考虑以后所做的选择，因此最终得到的全局最优解不一定是整个问题的最优解。与贪婪法不同，动态规划从全局考虑问题的最优解，它对问题进行全面的规划处理，从而弥补了贪婪法在这方面的不足。动态规划算法是将一个问题划分为若干个阶段，每一阶段的决策依赖于前一阶段的状态。例如一个问题的初始状态是S0,经过决策P1到达下一状态S1，而状态S1经过决策P2到达下一状态S2，以此类推，最终到达问题的最后一个状态Sn。由此可以得知，一个问题的各个决策是在不断地选择中得到的，每个状态都依赖于上一状态的选择（第一个状态除外）。根据上面这类问题的多段性决策原理，贝尔曼等人在20世纪50年代提出了解决这类问题的最优性原理，也就是动态规划的最优决策原理。这一原理指出，无论决策过程的初始状态和初始决策如何，其余的决策过程都必须相对于初始决策所产生的状态，构成一个最优决策序列。对于一个具有n个输入的最优解问题，它的初始状态是S0,结束状态是Sn。根据动态规划的算法，先将该问题划分为k个阶段，即S0S1,S1S2,Sk-1Sk。在问题的第一个阶段，它的初始状态是S0,而该问题最初具有n个输入，这里将这n个输入看做n个决策P11、P12、P13P1n-1、P1n，根据这n个决策，第一个阶段的结束状态S1也可以得到n个状态，即S11、S12、S13S1n-1、S1n。在问题的第二个阶段，它的初始状态是S11、S12、S13S1n-1、S1n,根据第二个阶段的n个决策P21、P22、P23P2n-1、P2n，可以得到第二个阶段的n个结束状态，即S21、S22、S23S2n-1、S2n。同理，第二个阶段的这n个结束状态将作为第三个阶段的初始状态。依此类推，第k个阶段的初始状态也就是第k-1个阶段的结束状态，它们分别为Sk-11、Sk-12、Sk-13Sk-1n，进过该阶段的n个决策Pk1、Pk2、Pk3Pkn-1、Pkn（注意，每个阶段的n个决策不一定相同），可以得到n个结束状态，它们分别为Sk1、Sk2、Sk3Skn，这n个结束状态也是整个问题的结束状态。 第一个阶段 第二个阶段 中间阶段 第k个阶段初始状态 决 策结束状态初始状态 决 策结束状态初始状态 决 策结束状态初始状态 决 策结束状态 S0P11P12P1n-1P1nS11S12S1n-1S1nS11S12S1n-1S1nP21P22P2n-1P2nS21S22S2n-1S2n Sk-11Sk-12Sk-1n-1Sk-1nPk1Pk2Pkn-1PknSk1Sk2Skn-1Skn 表2.1 动态规划的决策过程表1.1展示了一次动态规划的决策过程，从表中可以看出，在第一次决策完毕之后，会有n个不同的决策值集合，但是此时我们尚且无法确定哪一个决策值是最优的。同理，在第二个阶段，第三个阶段，我们都无法确定哪一个决策值是最优的。直到第k个阶段，也就是最后一个阶段，它的结束状态有Sk1、Sk2、Sk3Skn,此时可以很直观地确定第k个阶段的最优解，因为它是最后一个阶段，所以这个最优解也是整个问题的最优解。假设第k个阶段的最优决策值是状态Skr，它是由决策Pkr所产生的。再假设决策Pkr是由初始状态Sk-1r所做出的，由此回溯，可以确定第k-1个阶段的最优解就是状态Sk-1r。按照上面的方法继续回溯，可以依次确定第k-2个阶段的最优解,第k-3个阶段的最优解，第二个阶段的最优解，直到第一个阶段的最优解。在回溯的同时，我们会得到一个最优决策序列P1r、P2r、P3rPk-1r、Pkr,而这个决策序列导致了状态转移序列S1r、S2r、S3rSk-1r、Skr.根据最优性原理，上述决策序列，是根据初始状态S0和初始最优决策P1r所产生的状态而构成的一个最优决策序列。正是这个最优决策序列，使得问题从最初状态S0转移到最优状态Skr。在上面的决策过程中，有一个赖以决策的策略或目标，把这种策略或目标称为动态规划函数，该函数具体指的就是如何由初始状态经过决策到达结束状态，它由问题的性质和特点所确定，并应用于每一个阶段的决策。由于每个阶段都包含一个初始状态和一个结束状态，并且结束状态都是经过一个决策而得到的，因此可以采用递归或者循环迭代的方法进行。这样，动态规划函数可以递归地定义，也可以采用递推公式来定义。通过表1.1可以看到，最优决策是在最后一个阶段的结束状态得出的，然后向前递推，直到第一个阶段的初始状态。但是在定义动态规划函数时，并不是计算每个决策，直到最后一个结束状态，而是由初始状态开始计算的，然后向后递推或迭代，直到最终结果。下面将采用该策略来定义教学设备更新的动态规划算法，为了便于理解，该算法用形式化语言来表明。22 动态规划实例、教学设备更新问题根据第一部分关于教学设备更新问题的介绍，现假设如下一个教学设备更新问题。设某公司有一批同类型号的教学设备，为了保证该教学设备的使用率，降低资的源消耗和浪费，该教学设备在购置后必须最少使用两年，教学设备在不同购买时间，随着使用年限的递增，它的利润逐年降低，更新费用和维修费用逐年升高。教学设备的数据如下表所示。购买年限 i=0 i=1 i=2 i=3 i=4 i=5使用年限2 3 4 5 60 1 2 3 40 1 2 30 1 2 0 1 0 利 润13 12 11 10 916 15 14 13 1217 16 15 14 18 17 16 19 18 20维修费用2 3 4 4 51 1 2 2 31 1 2 2 1 1 2 1 1 1更新费用25 26 27 28 2920 22 24 25 2620 22 24 25 20 22 24 21 22 21 表2.2 教学设备更新的有关数据 上表中第i=0列表示公司当前教学设备的有关数据，第i=1列表示第一年购买的教学设备的有关数据；其余依次类推。为了便于求解，需对上表中的各个数据用函数和变量的方式进行定义，其定义如下：（1） Ri(j) 该函数表示第i年购买的教学设备，使用了j年之后，在第n=i+j年所创造的利润。例如（Pi=2(j=1)）=16。（2） Mi(j) 该函数表示第i年购买的教学设备，使用了j年之后，在第n=i+j年所需的维修费用。例如（Mi=0(j=5)）=4。（3） Ui(j) 该函数表示第i年购买的教学设备，使用了j年之后，在第n=i+j年所需的更新费用。例如（Ui=1(j=0)）=20。（4） BUYi(j) 该函数表示使用了j年的教学设备，第i年被更新，在第i年及其以后的年份里所创造的总利润，在今后的年份里被更新的该教学设备有可能被再次更新。（5） REMi(j) 该函数表示使用了j年的教学设备，第i年继续使用，在第i年及其以后的年份里所创造的总利润，在今后的年份里该教学设备有可能被再次更新。（6） Fi(j) 该函数表示使用了j年的教学设备，在第i年及其以后的年份里，所创造的总利润。（7） Xi(j) 该函数表示使用了j年的教学设备，在第i年所作出的更新教学设备或者保留继续使用的决策。（8） Pi 对于现有教学设备，在第i年所作出的更新教学设备或保留继续使用的最优决策。要得出教学设备更新之后的最大利润Fi(j)和最优决策序列Pi，需要比较每年的决策之后创造的利润，即BUYi(j)和REMi(j)，如果BUYi(j)REMi(j)，则当年的最优决策是更新教学设备，否则当年的最优决策是保留教学设备继续使用。如果使用了j年后的教学设备，第i年决定更新，则利润函数如下所示： BUYi(j)=Ri(0)-Mi(0)-Ui-j(j)+Fi+1(1) j=i如果使用了j年后的教学设备，第i年决定保留继续使用，则利润函数如下所示： REMi(j)=Ri-j(j)-Mi-j(j)+Fi+1(j+1) j=i规划函数如下所示: Fi(j)=MAX(BUYi(j),REMi(j) Xi(j)=TURE BUYi(j)=REMi(j) Xi(j)=FALSE BUYi(j)REMi(j) 3 教学设备更新算法的C程序实现及实例31 教学设备更新算法输入：决策年限n，教学设备已使用年限D，教学设备利润表r，维修费用表m，更新费用表u。输出：最优利润optg及最优更新方案p。1. Template 2. Type update_dev(int n, int D, Type r, Type m, Type u, BOOL p)3. 4. int i,j,k; /* 分配工作空间 */5. Type optg,rem;6. Type (*f)n+1 = new Typen+2n+1;7. BOOL (*x)n+1 = new BOOLn+1n+1;8. for(i=1;i0;i-) /* 第1n年各种教学设备使用年限的利润 */ 11. for(j=1;jj) /* 买，可得到的利润 */13. fij = ri0 - mi0 - ui-jj + fi+11;14. else15. fij = ri0 - mi0 - u0j-1+D + fi+11;16. xij = TRUE;17. if(ij) /* 留，可得到的利润 */18. rem = ri-jj - mi-jj + fi+1j+1;19. else20. rem = r0j-1+D - m0j-1+D + fi+1j+1;21. if(fijrem) /* 决策，取二者中的最大值 */22. fij=rem;23. 24. 25. 26. j=1; /* 全局的更新决策 */27. for(i=1;i=n;i+)28. pi = xij; /* 从第一年开始决策 */29. if(pi) /* 当年的决策：更新 */30. j=1; /* 下一年决策时，教学设备年限为1年 */31. else32. j=j+1; /* 否则，下一年决策是，教学设备年限增1 */33. 34. optg = f11;35. delete f; delete x; /* 释放工作空间 */36. return optg; /* 返回最优更新时可得到的利润 */37. 32 教学设备更新算法的C程序下面是一个教学设备更新的实例，按照上面所给的算法，首先采用数学运算的方式得到教学设备更新的最优决策及其利润，然后编出教学设备更新算法的C语言程序，对于同一实例，再采用计算机运行程序得到结果，最后对两个结果进行比较。例 教学设备已使用2年，按照表2.2所示数据，确定5年内的教学设备更新决策，及在此决策下的最大利润。假定，用数组fit和xit分别存放fi(t)和xi(t)的值，按照上面所述的步骤，计算fi(t)和xi(t)，得到表3.1。f1D=41 rf21=46 rf21+D=30 bf31=40 rf32=32 rf32+D=20 bf41=30 rf42=25 rf43=20 rf43+D=10 rf51=17 rf52=14 rf53=12 rf54=9 rf54+D=4 r 表3.1 例2.2中各年限可得到的利润及决策 由此得到，5年中的更新决策为留、买、留、留、留，5年内可得到的总利润为41。决策过程如图3.2所示，其中，粗线表示最优决策。x1,D=F x2,1=F x2,1+D=Tx3,1=F x3,2=F x3,2+D=T X4,1=F x4,2=F x4,3=F x4,3+D=Fx5,1=F x5,2=F x5,3=F x5,4=F x5,4+D=F 图3.2 教学设备更新决策过程 在上图中，图的左子树表示更新策略为买，图的右子树表示更新策略为留。 如果采用计算机程序运行的方法得到结果，则其具体的程序如下所示：1. #include 2. int main(void)3. 4. int year,D;5. int i,j;6. float r1010,m1010,u1010;7. printf(下面是一个教学设备更新程序，请输入教学设备相关的数据!n);8. printf(请输入决策年限year=);9. scanf(%d,&year);10. printf(n请输入教学设备已使用的年限Date=);11. scanf(%d,&D);12. /当前教学设备的相关数据，包括利润，维修费用和更新费用 13. printf(n请输入当前教学设备的数据n);14. for(j=0+2;jyear+2;j+)15. 16. printf( 请输入r0%d=,j); 17. scanf(%f,&r0j);18. printf( 请输入m0%d=,j); 19. scanf(%f,&m0j);20. printf( 请输入u0%d=,j); 21. scanf(%f,&u0j);22. printf(n);23. 24. /以后year年购买的教学设备的相关数据 25. printf(n请输入以后%d年购买的教学设备的数据n,year);26. for(i=1;iyear+1;i+)27. for(j=0;jyear-i+1;j+)28. 29. printf( 请输入r%d%d=,i,j); 30. scanf(%f,&rij);31. printf( 请输入m%d%d=,i,j); 32. scanf(%f,&mij);33. printf( 请输入u%d%d=,i,j); 34. scanf(%f,&uij);35. printf(n);36. 37. getchar();38. printf(nyear=%d,year);39. printf(nDate=%dn,D);40. printf(第一年的数据:n); 41. for(j=2;jyear+2;j+)42. 43. printf( r0%d=%f,j,r0j); 44. printf( m0%d=%f,j,m0j); 45. printf( u0%d=%f,j,u0j); 46. printf(n);47. 48. printf(以后%d年的数据:n,year-1); 49. for(i=1;iyear+1;i+)50. for(j=0;jyear-i+1;j+)51. 52. printf( r%d%d=%f,i,j,rij); 53. printf( m%d%d=%f,i,j,mij); 54. printf( u%d%d=%f,i,j,uij); 55. printf(n);56. 57. getchar();58. /计算利润 59. int k;60. float op,re;61. float fyear+2year+1;62. bool p10,xyear+1year+1;63. for(i=1;i0;i-)66. for(j=1;jj) 68. fij=ri0-mi0-ui-jj+fi+11;69. else70. fij=ri0-m