刘昊翔-10828089-关于设备更新问题的建模与算法实现.doc

关于设备更新问题的建模与算法实现 刘昊翔  The modeling and algorithm implementation of equipment renewal Haoxiang Liu 摘要：应用优化理论，建立设备更新问题的数学模型，是解决设备更新问题的行之有效的方法。传统的做法是运用动态规划的方法建模。但是传统的做法对于规模较大的问题，解决的效率较低。本文尝试运用非线性规划的思想来构建一个较复杂的设备更新问题，并将其与传统的动态规划建模做法进行对比，希望从对比中得出对于设备更新问题解决方法的新启示。 关键词：动态规划、非线性规划、设备更新问题 Abstract: Applying the optimization theory and establishing the equipment replacement model is an effective way to solve the equipment replacement problem. The traditional method is modeling with the dynamic programming. However, the traditional way proves to be ineffective when dealing with large-scale problems. In this article the non-linear programming theory is introduced to solve a complicated equipment replacement problem. And the two ways will be compared to seek some guidance to the solution of the equipment renewal problem. Keywords: Dynamic programming, non-linear programming, equipment replacement 在企业的生产运作过程中，设备更新应该是经常要面临的问题，其决策将直接影响产品的生产成本和企业的收益，因此根据设备运行状况及市场行情，确定合适的设备更新时机尤其重要。应用优化理论，建立设备更新问题的数学模型，是解决该问题行之有效的方法。传统的做法是运用动态规划的方法建模。但是传统的做法有其局限性，对于规模较大的问题，解决的效率较低。本文尝试运用非线性规划的思想来构建一个较复杂的设备更新问题，并将其与传统的动态规划建模做法进行对比，希望从对比中得出对于设备更新问题解决方法的新启示。同时，在算法实现方面，非线性规划问题采用了Dijkstra算法，相比之下动态规划问题采用的是常规的逆序算法。本文的最后附上Dijkstra算法以供参考。 一、非线性规划建模方法 1．问题的一般提法 某企业使用一台设备，每年年初企业领导总要考虑是购买新设备，还是继续使用旧设备．若购置新设备，就需要支付购买费，且购买费与购买的时间有关；购买新设备的同时卖掉旧设备，可得到一笔设备折旧费．设备运行就要支付运行维护费，折旧费和运行维护费均与设备的使用年限和出厂时间有关．设备每年给企业创造的收益也决定于设备的使用年限和出厂时间．问题是要制定一个几年之内的设备更新计划，使企业在计划内的收益达到最大． 2．问题的非线性规划模型 2．1 简化的设备更新问题的模型 2．1．1 建立模型 先建立简化后的问题的规划模型，然后在此基础上再建立上述问题的模型．这里通过假设来对上述问题进行简化． 假设(1)：一年最多只能购买一台新设备． 假设(2)：计划内第一年初必须购置新设备． 假设(3)：不考虑旧设备的折旧费． 假设(4)：运行维护费仅与设备的使用年限有关． 假设(5)：不考虑企业的收益，即问题的目标是使企业支付的设备购置费和运行维护费最小． 建立静态规划模型的关键在于决策变量的选取，它直接决定模型的类型和质量，切人点可以从问题方案的数学描述人手．问题是要制定一个几年之内的设备更新计划，结合上述假设(1)可知计划的内容是对于每一年而言，是继续使用旧设备还是购置新设备，这可以用一组0-1变量来描述，记为，其中i 表示年份．作为决策变量，它的一组取值就表示了一个设备更新计划．记第i年设备的购置单价为，则计划内设备的购置总费用是，费用的另外一部分是设备的维护费用，其数学描述是本问题的一个难点．下面通过