多维离散资源分配问题模型转换及其Excel求解方法.docVIP

多维离散资源分配问题模型转换及其Excel求解方法 　　摘要： 离散资源分配问题是管理科学中的一个重要问题。对于一维资源问题，一般都采用动态规划方法求解，而对于多维离散资源问题，用逐次逼近法转化为一维资源问题求解，其计算量巨大，需要利用专门的优化软件计算。本文中，将多维离散资源问题转化为0-1规划问题，并利用大家熟悉的Excel软件进行求解，以利于分析利用。算例表明，该方法是简单、有效，而且实用。 　　Abstract： The resource allocation problems are key problems in a management science. To solve the one-dimensional resource allocation problems， the dynamic programming method is used generally.However， the multi-dimensional resource allocation problems are transformed as the one-dimensional resources problems with successive approximation method. But it is trivial and takes much time， so it needs to use the special optimization software to find its solutions. In this paper， we transform the multi-dimensional resource allocation problems to 0-1 programming problems， and solve them by using the Excel software which everybody is familiar with. The example indicated that this method is simple， effective， and practical. 　　关键词： 资源问题；0-1规划；多维；Excel 　　Key words： resource allocation；0-1 programming；multi-dimensional；Excel 　　中图分类号：TL372+.3 文献标识码：A 文章编号：1006-4311（2013）01-0096-03 　　1 问题的提出 　　在实际问题中，经常会遇到要将数量一定的一种或若干种资源（如原材料，资金，设备，专门人才，电力等）恰当地分配给N个部门或单位，而使效益达到最优的问题。由于各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异，即使给各部门提供同数量的资源，各部门所产生的效益也是不尽相同的，即各部门的效益函数有异。 　　对于K种资源的分配问题，假设资源总量分别为a1，a2，…，ak。如果分配给第n 部门的数量分别是非线性规划问题，可利用非线性规划问题的求解方法求解。利用Excel软件求解利用非线性规划问题的方法，有兴趣的读者可阅读[1]、[2]或其它有关文献资料，在此不做详细地讨论。由于效益函数受着资源类型、时间、市场、消费者心理等很多不确定因素的影响，其函数关系不一???是解析式， 可能是对特定资源某几种分配可能值及其效益由表格形式给出。效益函数的非解析性及离散性使得解析计算变得困难。当部门少，分配方案少时，可利用穷举法进行求解。当部门较多，分配方案也较多时，对于一维资源问题，一般运筹学教材上都采用动态规划方法列表求解[3]。该方法较一般的穷举法而言，计算过程能得到一些简化，但仍然存在着时间过程长，计算量大，特别是N，a至少有一个较大时更是如此。对于二维资源问题，用逐次逼近法转化为一维资源问题求解，其计算量很大[3]。如果维数大于2，用逐次逼近法转化为一维资源问题求解，计算量将变得巨大。此外，效益表格的数据一旦发生变化，（在市场经济诸多因素的影响下这种改变是很可能而且很快的）前后分配方案之间极少有借鉴之处，不利于及时予以调整.为了避免上述不足，充分利用现有应用软件的强大功效，应是一个探索的方向。文[4]、[5]中，对一维资源问题分别给出了利用Lingo软件和利用Matlab软件进行求解的方法。我们知道，Lingo是一个专业化的优化计算软件，Matlab软件是一个专业化的大型计算软件，利用它还需要熟悉该系统的命令系统和相应的建模语言的命令，不利于大家使用和推广，此外实际问题中，一维问题少。本文中，我们将多维离散资源分配问题的模型转换为0-1规划问题，并利用大家熟悉的Exce