资源分配问题的求解

./信息与计算科学专业学年论文评阅意见表标题资源分配问题的求解作者玉娟学号3070942232指导教师林亮关键词资源分配；线性规划；单纯形法；0-1规划；动态规划；逆序递推中文摘要资源分配问题将一种或几种资源〔原材料、机器设备等分配给若干产品或用户,以获得最大的效益。它可以是静态规划问题,也可以是多阶段决策过程,构造动态规划模型求解。本文用线性规划单纯形法、整数0-1规划、动态规划逆序递推算法求资源分配问题最优值。指导教师评语签字：年月日答辩小组评阅意见签字：年月日评定等级备注..资源分配问题的求解学生：玉娟学号：3070942232指导老师：林亮摘要：资源分配问题将一种或几种资源〔原材料、机器设备等分配给若干产品或用户,以获得最大的效益。它可以是静态规划问题,也可以是多阶段决策过程,构造动态规划模型求解。本文用线性规划单纯形法、整数0-1规划、动态规划逆序递推算法求资源分配问题最优值。关键词：资源分配；线性规划；单纯形法；0-1规划；动态规划；逆序递推1引言近年来,随着社会经济的发展,资源分配问题广泛存在于社会各个领域。所谓资源分配问题,就是将数量一定的的资源〔例如原材料、资金、机器设备、劳动力、食品等分配给若干个使用者,而使总的目标函数值为最优。如何在满足各使用方的基础上,高效分配有限的资源,是资源分配问题中亟待解决的难题。资源分配问题,属于线性规划、非线性规划这样一类静态规划问题,通常是与时间无关的。线性规划问题的求解方法有统一而简单的方法即单纯形法,但在决策变量个数较多,求解过程都比较复杂时,用手动来算繁琐,所以用MATLAB软件编程求解线性规划问题则比较简单。但实际上由于各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异,即使给各部门提供同数量的资源,各部门所产生的效益也是不尽相同的,即各部门的效益函数有异.另一方面,上面所说的效益函数还受着资源类型、时间、市场、消费者心理等很多不确定因素的影响,其函数关系不一定是解析式.很可能是对特定资源某几种分配可能值关于当前时段的统计数据而常常以表格形式给出,正是这种效益函数的非解析性及离散性使得解析计算变得困难。存在着时间过程长,计算量大,特别是N、M至少有一个较大时更是如此.另一方面,效益表格的数据一旦改变,<在市场经济诸多因素的影响下这种改变是很可能而且很快的>前后分配方案之间极少有借鉴之处,不利于及时予以调整。所以引用整数0-1规划,运用Lingo软件编程求解。这类静态问题也可以人为地引入时间因素,把它看作是按阶段进行的一个多阶段决策问题,也可以用动态规划方法方便地求解。在资源分配问题上使用动态规划是将分配过程划分为多个阶段,在每个阶段中选取最优决策,最后达到整个过程的总体最优目标。可以用逆序递推列表求解,但是当数据比较大,列表求解就非常繁琐,利用MATLAB编程求解就非常容易了。2问题和求解2.1问题的提出对于这类要需要种不同的原材料生产种不同的产品的资源分配问题,一般是已知每样原材料的库存量,每个产品所需各种材料的分量,以及生产每个产品能获得多少利益。这类资源分配问题只要运用线性规划就可以解决。表1产品库存量原材料利润线性规划求解一般线性规划问题的数学模型为：这里f为由目标函数的系数组成的向量,A和b分别为约束条件的系数矩阵和右端向量,Aeq和Beq分别为等式约束条件的系数矩阵和右端向量,当约束条件没有等式时,Aeq和Beq就用空矩阵[]表示,lb和ub分别是变量的下界和上界约束。满足全部约束条件的一组决策变量,称为此线性问题的可行解,而使目标函数达到问题要求的最优值<max或min>的可行解称为线性规划问题的最优解。MATLAB程序代码见附录程序代码1。单纯形法单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是：先找出一个基本可行解,对它进行鉴别,看是否是最优解；若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：Step1.把线性规划问题的约束方程组表达成典型方程组,找出基本可行解作为初始基本可行解。Step2.若基本可行解不存在,即约束条件有矛盾,则问题无解。Step3.若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。Step4.按步骤3进行迭代,直到对应检验数满足最优性条件〔这时目标函数值不能再改善,即得到问题的最优解。Step5.若迭代过程中发现问题的目标函数值无界,则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解。实例1某工厂生产、、、、五种产品,这五种产品需要1、2、3、4、5、6六种不同原材料。如下表1所示。问如何安排这五种产品的生产量可以获得最大的利润？表2产品库存量原料114012182204052632113122442213205034322562204028利润23345解：方法一：目标函数：,因为标准型是求目标函数的最小值,将maxf通常转换为minf来编程求解。原问题转化为：运用附录程序1,工厂应选择生产、、、、产品的分别为0、0、0、5、5,工厂最多可获利45。方法二：利用单纯形法,引入附加变量,将原问题转化为：如若用单纯形法表格法求解,则非常繁琐,计算量很大。所以运用附录程序2,单纯形法的初始表A=[1401210000018;2040501000026;2113100100022;4221300010020;0343200001025;2204000000128;233450000000],初始的基变量的下标N=[67891011]。求得,则最优值为z=45。2.2问题的提出对于此类设资源总量为,分配给个部门,第部门的分配量记为,相应的效益函数为,,模型可以表示为：表3资源单位数各部门产生的效益值1201由于实际上各部门的原有基础、地理位置、市场定位、使用目的等各方面的差异,即使给各部门提供同数量的资源,各部门所产生的效益也是不尽相同的,即各部门的效益函数有异.另一方面,上面所说的效益函数还受着资源类型、时间、市场、消费者心理等很多不确定因素的影响,其函数关系不一定是解析式。很可能是对特定资源某几种分配可能值关于当前时段的统计数据而常常以表格形式给出,正是这种效益函数的非解析性及离散性使得解析计算变得困难。对于这类实际问题,一般的做法是先预想出几种可能的分配方案,根据有关调查,统计,给出表3〔表中为第种资源分配量在第部门产生的效益值。此时问题就变成了如何在每列取一个效益值〔因每个部门最后只能得到一种分配结果,只能产生一种效益使这个效益值之和为最大,而所取得效益值又必须满足资源总数为的约束。整数0-1规划求解引进0-1变量：及资源单位数向量：则可建立与实际相应数学模型：这是常见的0-1规划模型,应用Lingo软件,可以方便、快捷的求解。实例2现有某种设备共有八台,拟分给用户1、2、3、4、5等五个工厂,各工厂利用这些设备提供的盈利各不相同〔如表4问如何分配这四台设备,使总盈利为最大？表4资源单位数各部门产生的效益值123450000001423432645543767654788675798676710867781097889101088解：已知设备,用户。运用附录程序3,可求得结果为,即分配1台给用户1,获得盈利,分配2台给用户2,获得盈利,分配3台给用户3,获得盈利,分配1台给用户4,获得盈利,分配1台给用户5,获得盈利。总盈利为。2.3动态规划求解算法步骤<1>阶段的划分和阶段变量的确定。根据多阶段决策问题的特点,将其划分为若干个相互独立又相互联系的部分,每一个部分为一个阶段,划分出的每一个阶段通常就是需要作出一个决策的子问题。阶段通常是按决策进行的时间或空间上的先后顺序划分的,阶段变量用表示。<2>确定状态、状态变量。在多阶段决策过程中,状态是描述每个阶段所必须的信息,表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态,过程的状态用一个或一组变量来描述,状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息,用表示第个阶段的状态变量。<3>定义决策变量和允许的决策集合。决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用表示,允许决策集合是决策变量的取值围,用表示。<4>正确写出状态转移方程。状态转移方程,如果给定第个阶段的状态变量,则该阶段的决策变量一经确定,第阶段的状态变量的值也就可以确定。<5>正确写出阶段效益函数。<6>写出动态规划函数基本方程：<边界条件>动态规划求解算法的逆序算法步骤：Step1.设定初值,取Step2.逆向递推,依次取,计算Step3.逐阶段求出最优决策和过程的最优值,直至求得。实例3引用上面的实例2解：已知设备,用户,即分五个阶段。如果用动态规划逆序递推法列表求解非常繁琐,要花费很多时间。所以运用附录程4,键入命令：；；;。输出结果为12311.它与上面的计算结果是相同的。当或很大时,用程序代码求解非常方便,只要输入,和的值就可以求出最优解。3方法总结和推广线性规划是目前应用领域最广泛的一种系统优化方法,可以应用于生产计划、物资调运、资源优化配置、地区经济规划等许多实际问题。线性规划问题的求解有统一且简单的方法即单纯形法,但在决策变量个数较多,求解过程都比较复杂时,用MATLAB软件求解线性规划问题则比较简单。但是在实际中也有部分分配问题要求解答必须是整数的,但是线性规划求解时,其最优解可能是整数,也可能不是整数。所以用线性规划求解资源分配问题有一定的局限性,可以用整数规划求解。从LINGO编写的程序3可以看出,转化后的模型对于a,n都大的情形也是适用的,只要改些相应的数据就可以了。该模型具有向大型问题扩展的功能,它仍然具有方便、快捷、准确的特点。动态规划与静态规划<线性和非线性规划等>研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。许多问题用动态规划求解比用线性规划或非线性规划更加有效,特别是对离散性问题,运用解析数学无法解决。用动态规划解决多阶段决策问题效率很高,而且思路清晰简便,同时易于实现,本文中运用MATLAB语言实现了动态规划的逆序算法。动态规划可以广泛地用于解决最短路径问题、资源分配问题、生产计划与库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。但是使用动态规划方法也有一定的限制,如没有统一的标准模型,状态变量必须满足无后效性,并且只适用一些维数相当低的问题等。在当今企业的生产经营活动中,最高层管理者主要关心的是企业的目标、方针和基本战略等全面性决策问题,这些问题的解决为在变化环境中指导企业提供一个骨架,中下层管理的很多决策活动是处于操作层次的,可以编写程序,让计算机来为管理阶层提供最优解答。一旦问题被编成程序,则可以把它们移交给一个管理信息系统。这种运筹模型的程序化可以避免日常繁琐的计算分析工作,以便他们能集中精力解决更为困难的战略性问题。本文中的数学规划模型程序化做法是非常必要的,值得应用和推广。致：在写作过程中遇到了一些问题,多亏指导老师的帮助完成,在这里向指导老师林亮表示诚挚的意。参考文献[1]熊义杰.运筹学教程〔第2版[M].:国防工业,2007.9.[2]莹.运筹学基础[M].：清华大学,1995.4.[3]瑞丰,等.精通MATLAB6.5[M].：中国水利水电,2004.[4]吴庆丰.资源分配问题的动态规划求解方法[J].煤炭师学院学报,2008,第29卷第2期.[5]黄政龙.资源分配问题的优化模型转换及其算法[J].中南林业科技大学学报,2007.4,第27卷第2期.SolvingtheproblemofresourceallocationStudent:zhangyujuanID:3070942232Teacher:linliangAbstract:Resourceallocationproblemwillbeoneorseveralresources<rawmaterials,machineryandequipment,etc.>assignedtoanumberofproductsoruserstogetmaximum.Itcanbeastaticplanningproblemcanbeamulti-stagedecision-makingprocess,structuraldynamicprogrammingmodel.Inthispaper,thesimplexmethodoflinearprogramming,integer0-1programming,dynamicprogrammingrecursivealgorithmreverseordertotheoptimalvalueoftheallocationofresources.Keyword:Resourceallocation;LP;Simplex;0-1programming;Dynamicprogramming;Reverserecursive附录：用线性规划、单纯形法、整数0-1规划、逆序递推求解程序1代码如下：clearf=-[2,3,3,4,5];%目标函数的系数组成的向量A=[1,4,0,1,2;2,0,4,0,5;2,1,1,3,1;4,2,2,1,3;0,3,4,3,2;2,2,0,4,0];%约束条件的系数矩阵b=[18,26,22,20,25,28];%右端向量lb=[0,0,0,0,0];%变量的下界[X,fval]=linprog<f,A,b,[],[],lb>%当没有等式约束条件时,Aeq和Beq都用空矩阵[]表示运行结果如下：>>Optimizationterminatedsuccessfully.X=0.00000.00000.00005.00005.0000fval=-45.0000程序2代码如下：function[sol,val,kk]=ssimplex<A,N>A=input<'请输入矩阵A=：'>;%单纯初始表,最后一行是目标函数系数,最后一列是资源向量N=input<'请输入一组向量N=：'>;%初始的基变量的下标[mA,nA]=size<A>;kk=0;%迭代次数flag=1;whileflagkk=kk+1;ifA<mA,:><=0%已找到最优解flag=0;sol=zeros<1,nA-1>;%给每个变量赋初值0fori=1:mA-1sol<N<i>>=A<i,nA>;%给基变量赋新值〔替换0endval=-A<mA,nA>;elsefori=1:nA-1ifA<mA,i>>0&A<1:mA-1,i><=0%问题有无界解disp<'haveinfinitesolution!'>;flag=0;break;endendifflag%还不是最优表,进行转轴运算temp=0;fori=1:nA-1ifA<mA,i>>temptemp=A<mA,i>;inb=i;%进基变量的下标endendsita=zeros<i,mA-1>;fori=1:mA-1ifA<i,inb>>0sita<i>=A<i,nA>/A<i,inb>;endendtemp=inf;fori=1:mA-1ifsita<i>>0&sita<i><temptemp=sita<i>;outb=i;%出基变量下标endend%选择最小的sita横向对应的变量为出基变量%以下更新Nfori=1:mA-1ifi==outbN<i>=inb;%以进基变量的下标替代出基变量的下标endend%以下进行转轴运算A<outb,:>=A<outb,:>/A<outb,inb>;%将主元化为1fori=1:mAifi~=outbA<i,:>=A<i,:>-A<outb,:>*A<i,inb>;%将进基变量所在列除主元外的其余元素化为0endendendendend运行结果如下：请输入矩阵A=：[1401210000018;2040501000026;2113100100022;4221300010020;0343200001025;2204000000128;233450000000]请输入一组向量N=：[67891011]ans=Columns1through100005.00005.00003.00001.00002.000000Column118.0000程序3代码如下：sets:R/1..9/:z;!建立行号集合,派生出设备台数集合;L/1..5/;!建立列号集合;C<R,L>:x,y;!建立双下标集合<i,j>,派生出效益集合X以及0-1变量集合Y;endsetsdata:X=00000,42343,64554,76765,78867,79867,710867,810978,9101088;z=012345678;enddatamax=sum<c<i,j>:X<i,j>*y<i,j>>;!目标函数;for<l<i>:sum<c<j,k>|k#eq#i:y<j,k>>=1>;!每个工厂只取一个效益值;sum<c<i,j>:y<i,j>*z<i>>=8;!设备总台数为9;for<c<i,j>:Bin<y<i,j>>>;!为0-1变量;end运行结果如下：Globaloptimalsolutionfound.Objectivevalue:22.00000Objectivebound:22.00000VariableValueReducedCostX<2,4>4.0000000.000000X<2,5>3.0000000.000000X<2,1>4.0000000.000000X<3,2>4.0000000.000000X<4,3>7.0000000.000000Y