多维离散资源分配问题的模型转换及其Excel求解方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇多维离散资源分配问题的模型转换及其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规划问题，并利用大家熟悉的Excel软件进行求解，以利于分析利用。
对于多维离散资源分配问题，设第n个部门可能得到的第k种资源数量（即第n个部门关于第k种资源的可能分配方案）为{x■■，m=1，2，…M■}，该部门得到各种资源的数量分别是x■■，x其中Mn，1=4，Mn，2=5，Mn，3=4。
对上述模型建立如下Excel求解表2。
建立Excel表2时，在C15：G20中任意一个位置输入1，其余位置填0，在H15：M20中任意一个位置输入1，其余位置填0，在N15：R20中任意一个位置输入1，其余位置填0。在21行、22行、23行中分别填入按该方案分配各个工厂得到的设备数、资金数和公司得到的总收益的计算公式。在24行中填入计算公式SUM（C15：G20）、SUM（H15：M20）、SUM（N15：R20），这些公式表明公式，各工厂只能选择其中的一个方案。表明丙工厂只能0—5台设备中的一个。建立上表后，点击Excel中的工具，找到规划求解选项并点击，出现如下界面，并将模型数据填入，得到表3。
点击选项，将其中的采用线性模型、假定非负两项打√后，点击确定回到该界面，再点击求解，将得到如下求解信息表4。
再点击确定，可得如计算结果表5。
表5说明：最优分配方案：
设备：甲工厂3台、乙工厂2台、丙工厂1台；
资金：甲工厂300万元、乙工厂200万元、丙工厂300万元。
最大盈利为4700万元。
3 进一步讨论
从表1可看出取得相同数量的资源，三个工厂中乙工厂的效益最好。但在上最优分配方案中，乙工厂得到的资源数并非最多。
①如果分配给乙工厂的设备数不小于2台，资金数不小于300万元，这时的最优分配方案将使公司获利多少？此时，只要在规划求解模型中增加如下相应约束：
并求解即可。
经过求解可得：此时的最优分配方案：
设备：甲工厂3台、乙工厂2台、丙工厂1台；
资金：甲工厂300万元、乙工厂200万元、丙工厂300万元。
最大盈利为4700万元。
该求解表明，利用Excel求解工具，只能给出一个求解结果。是否有多个最优方案，可以随便改变初值，看计算结果是否一致。如果一致，最优解很可能唯一。当然也可象前面一样给解进一步的限制，看最优解的状况。
②如果分配给乙工厂的设备数不小于3台，资金数不小于300万元，这时的最优分配方案将使公司获利多少？这时，只要在规划求解模型中修改相应约束：
并求解即可。经过求解可得：此时的最优分配方案：
设备：甲工厂2台、乙工厂3台、丙工厂1台；
资金：甲工厂200万元、乙工厂300万元、丙工厂300万元。
最大盈利为4600万元。
该结果表明：从追求最大利润来看，乙工厂的资金数不小于300万元，设备数不小于3台的方案不能施行。
4 结论
本文中，将多维离散资源问题转化为0-1规划问题，并利用大家熟悉的Excel软件进行求解。当资源状况发生变化，或管理者有进一步的要求时，只需将相应数据加入Excel表格，并电击求解工具即可。利用Excel软件计算，简单、有效，而且实用，便于推广使用。
参考文献：
[1]邱启荣，吕蓬.运筹学及其应用[M].北京：中国电力出版社，2009.
[2]叶向.实用运筹学：运用Excel建模和求解[M].北京：中国人民大学出版社，2007.
[3]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社， 2005.
[4]黄政龙.资源分配问题的优化模型转换及其算法.中南林业科技大学学报[J]，2007，27（2）：122-125.
[5]郑怡，赵海良，徐永，基于Matlab的动态规划问题.重庆工学院学报（自然科学）[J]，2008，22（5），152-155.