资源分配问题的求解

. . . 信息与计算科学专业学年论文评阅意见表标 题资源分配问题的求解 作 者玉娟学号3070942232指导教师林亮关键词资源分配；线性规划；单纯形法；0-1规划；动态规划；逆序递推中 文摘 要资源分配问题将一种或几种资源（原材料、机器设备等）分配给若干产品或用户，以获得最大的效益。它可以是静态规划问题，也可以是多阶段决策过程，构造动态规划模型求解。本文用线性规划单纯形法、整数0-1规划、动态规划逆序递推算法求资源分配问题最优值。 指 导教 师评 语签字： 年 月 日 答 辩小 组评 阅意 见签字： 年 月 日 评 定等 级备 注. . 资源分配问题的求解学生：玉娟 学号：3070942232 指导老师：林亮摘 要：资源分配问题将一种或几种资源（原材料、机器设备等）分配给若干产品或用户，以获得最大的效益。它可以是静态规划问题，也可以是多阶段决策过程，构造动态规划模型求解。本文用线性规划单纯形法、整数0-1规划、动态规划逆序递推算法求资源分配问题最优值。关键词：资源分配；线性规划；单纯形法；0-1规划；动态规划；逆序递推1 引言近年来，随着社会经济的发展，资源分配问题广泛存在于社会各个领域。所谓资源分配问题，就是将数量一定的的资源（例如原材料、资金、机器设备、劳动力、食品等）分配给若干个使用者，而使总的目标函数值为最优。如何在满足各使用方的基础上，高效分配有限的资源，是资源分配问题中亟待解决的难题。资源分配问题，属于线性规划、非线性规划这样一类静态规划问题，通常是与时间无关的。线性规划问题的求解方法有统一而简单的方法即单纯形法，但在决策变量个数较多，求解过程都比较复杂时，用手动来算繁琐，所以用MATLAB软件编程求解线性规划问题则比较简单。但实际上由于各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异,即使给各部门提供同数量的资源,各部门所产生的效益也是不尽相同的,即各部门的效益函数有异.另一方面,上面所说的效益函数还受着资源类型、时间、市场、消费者心理等很多不确定因素的影响,其函数关系不一定是解析式.很可能是对特定资源某几种分配可能值关于当前时段的统计数据而常常以表格形式给出,正是这种效益函数的非解析性及离散性使得解析计算变得困难。存在着时间过程长,计算量大,特别是N、M至少有一个较大时更是如此.另一方面,效益表格的数据一旦改变,(在市场经济诸多因素的影响下这种改变是很可能而且很快的)前后分配方案之间极少有借鉴之处,不利于及时予以调整。所以引用整数0-1规划，运用Lingo软件编程求解。这类静态问题也可以人为地引入时间因素，把它看作是按阶段进行的一个多阶段决策问题，也可以用动态规划方法方便地求解。在资源分配问题上使用动态规划是将分配过程划分为多个阶段，在每个阶段中选取最优决策，最后达到整个过程的总体最优目标。可以用逆序递推列表求解，但是当数据比较大，列表求解就非常繁琐，利用MATLAB编程求解就非常容易了。2 问题和求解2.1 问题的提出对于这类要需要种不同的原材料生产种不同的产品的资源分配问题，一般是已知每样原材料的库存量，每个产品所需各种材料的分量，以及生产每个产品能获得多少利益。这类资源分配问题只要运用线性规划就可以解决。表1产品库存量原材料利润2.1.1 线性规划求解一般线性规划问题的数学模型为：这里f为由目标函数的系数组成的向量，A和b分别为约束条件的系数矩阵和右端向量，Aeq和Beq分别为等式约束条件的系数矩阵和右端向量，当约束条件没有等式时，Aeq和Beq就用空矩阵表示，lb和ub分别是变量的下界和上界约束。满足全部约束条件的一组决策变量，称为此线性问题的可行解，而使目标函数达到问题要求的最优值(max或min)的可行解称为线性规划问题的最优解。MATLAB程序代码见附录程序代码1。2.1.2 单纯形法单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：Step1.把线性规划问题的约束方程组表达成典型方程组，找出基本可行解作为初始基本可行解。Step2.若基本可行解不存在，即约束条件有矛盾，则问题无解。Step3.若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。Step4.按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。Step5.若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解。2.1.2 实例1某工厂生产、五种产品，这五种产品需要1、2、3、4、5、6六种不同原材料。如下表1所示。问如何安排这五种产品的生产量可以获得最大的利润？表2产品库存量原料114012182204052632113122442213205034322562204028利润23345解：方法一：目标函数：，因为标准型是求目标函数的最小值，将maxf通常转换为minf来编程求解。原问题转化为：运用附录程序1，工厂应选择生产、产品的分别为0、0、0、5、5，工厂最多可获利45。方法二：利用单纯形法，引入附加变量，将原问题转化为：如若用单纯形法表格法求解，则非常繁琐，计算量很大。所以运用附录程序2，单纯形法的初始表A=1 4 0 1 2 1 0 0 0 0 0 18;2 0 4 0 5 0 1 0 0 0 0 26;2 1 1 3 1 0 0 1 0 0 0 22;4 2 2 1 3 0 0 0 1 0 0 20;0 3 4 3 2 0 0 0 0 1 0 25;2 2 0 4 0 0 0 0 0 0 1 28;2 3 3 4 5 0 0 0 0 0 0 0，初始的基变量的下标N=6 7 8 9 10 11。求得，则最优值为z=45。2.2 问题的提出对于此类设资源总量为，分配给个部门，第部门的分配量记为,相应的效益函数为, ,模型可以表示为：表3资源单位数各部门产生的效益值1201由于实际上各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异，即使给各部门提供同数量的资源，各部门所产生的效益也是不尽相同的,即各部门的效益函数有异.另一方面,上面所说的效益函数还受着资源类型、时间、市场、消费者心理等很多不确定因素的影响,其函数关系不一定是解析式。很可能是对特定资源某几种分配可能值关于当前时段的统计数据而常常以表格形式给出,正是这种效益函数的非解析性及离散性使得解析计算变得困难。对于这类实际问题，一般的做法是先预想出几种可能的分配方案，根据有关调查，统计，给出表3（表中为第种资源分配量在第部门产生的效益值）。此时问题就变成了如何在每列取一个效益值（因每个部门最后只能得到一种分配结果，只能产生一种效益）使这个效益值之和为最大，而所取得效益值又必须满足资源总数为的约束。2.2.1 整数0-1规划求解引进0-1变量：及资源单位数向量：则可建立与实际相应数学模型：这是常见的0-1规划模型，应用Lingo软件，可以方便、快捷的求解。2.2.2 实例2 现有某种设备共有八台，拟分给用户1、2、3、4、5等五个工厂，各工厂利用这些设备提供的盈利各不相同（如表4）问如何分配这四台设备，使总盈利为最大？表4资源单位数各部门产生的效益值123450000001423432645543767654788675798676710867781097889101088解：已知设备,用户。运用附录程序3，可求得结果为，即分配1台给用户1，获得盈利，分配2台给用户2，获得盈利，分配3台给用户3，获得盈利，分配1台给用户4，获得盈利，分配1台给用户5，获得盈利。总盈利为。2.3 动态规划求解2.3.1 算法步骤(1)阶段的划分和阶段变量的确定。根据多阶段决策问题的特点，将其划分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就是需要作出一个决策的子问题。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。(2)确定状态、状态变量。在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，过程的状态用一个或一组变量来描述，状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息，用 表示第个阶段的状态变量。(3)定义决策变量和允许的决策集合。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用表示，允许决策集合是决策变量的取值围，用表示。(4)正确写出状态转移方程。状态转移方程,如果给定第个阶段的状态变量,则该阶段的决策变量一经确定,第阶段的状态变量的值也就可以确定。(5)正确写出阶段效益函数。(6)写出动态规划函数基本方程：(边界条件)动态规划求解算法的逆序算法步骤：Step1. 设定初值，取Step2. 逆向递推，依次取，计算Step3. 逐阶段求出最优决策和过程的最优值，直至求得。2.3.2 实例3引用上面的实例2解：已知设备，用户，即分五个阶段。如果用动态规划逆序递推法列表求解非常繁琐，要花费很多时间。所以运用附录程4，键入命令：；;。输出结果为 1 2 3 1 1.它与上面的计算结果是相同的。当或很大时，用程序代码求解非常方便，只要输入，和的值就可以求出最优解。3 方法总结和推广线性规划是目前应用领域最广泛的一种系统优化方法，可以应用于生产计划、物资调运、资源优化配置、地区经济规划等许多实际问题。线性规划问题的求解有统一且简单的方法即单纯形法，但在决策变量个数较