2022年2022年机器任务分配问题 .pdf
西安交通大学数学与应用数学专业课程设计（本科）机器任务分配问题班级： 应数 61姓名： 李宗欣学号： 060910022009年 6 月第 1 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）摘要机器任务分配问题属于资源连续分配问题，它是生产活动中的一个很重要的问题。生产者为了获得最大的收益，总是希望能够找到最优策略。因此，能够迅速而准确地求出问题的解非常重要。 本文首先对一般问题建立了模型，然后对几种常见的特殊情形的求解进行了详细而深入的讨论，并进行了可视化的软件开发。最后，将资金的时间价值考虑进去从而使得模型更加接近实际。此外， 将模型由一维情形推广到高维的情形并给出了求解的大致思路和方法。关键词：机器任务分配资源连续分配动态规划方法资金的时间价值第 2 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）Abstract The problem of the machines, tasks distributing belongs to the questions of continuous distribution. It is a very important part in production. In order to obtain the largest proceeds, producers always want to find the optimal strategy. Therefore, it is rather important to solve the problem quickly and accurately. In this passage, I establish the model of the general firstly, and then discuss several special circumstances in details and in depth. Meanwhile, I develop the visualization of software. Finally, I take the time value of money into account so that the models are more realistic. In addition, I extend the one-dimensional case to high- dimensional and give the general ideas and methods of the solution. Key words machines, tasks distributingcontinuous distribution methods of dynamic programming time value of money 第 3 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）目录引言 .51、一般问题及相应的模型.61.1 一般问题重述 .61.2 模型的建立 .61.2.1静态规划模型 .61.2.2动态规划模型 .62、特殊情形及相应模型的求解.92.1 效益函数为线性函数时.92.2.1末端自由情形 .92.2.3末端固定情形 .122.2 效益函数为非线性函数时.133、进一步讨论效益函数为线性，末端自由情形.153.1 最优策略的一般关系式.153.1.1问题简述与模型建立 .153.1.2模型的求解及结论 .153.2 基于一般式的计算机求解.173.2.1基于C+ 的求解 .183.2.2基于VC的可视化软件开发 .194、模型的改进与进一步推广.214.1 考虑资金时间价值的模型.214.1.1基本假设和相关的符号说明.224.1.2模型的建立与求解 .224.2 多元分配问题的推广.225、动态规划方法的评价.23附录一： C+程序 .26附录二：复利终值系数表.27参考文献 .31第 4 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）引言机器任务分配问题是生产活动中的一个很重要的方面，在问题中考虑机器损耗。因为决策变量是连续值，故属于资源连续分配问题。这类问题的一般叙述如下：设有某种机器，初始的拥有量为，计划在A和 B 两种零件的生产上连续使用n 个阶段，已知投给 A的机器数为时相应的阶段效益为，投给 B的机器数为时相应的阶段效益为。在实际生产过程中，机器都会有损失。根据以往的经验可知，生产A零件，一个阶段后的完好率为a，生产 B零件，一个阶段后的完好率为b（） ，求 n 阶段总收益最大的资源分配计划。 1sAU)g(UABU)(BUh1ba0 ，显然，问题属于动态规划的范畴（事实上也可以得到静态的数学模型）。经过简单分析我们可以很容易得到问题的模型。由于效益函数的具体形式未知，故求解起来非常复杂。因此可以从简单的情形做起。目前，人们对于该问题的求解仅仅局限在末端自由、效益函数为线性且给定的情形，并没有给出一般情形的求解方法。本文不仅考虑了末端受约束的情形，还对效益函数为线性函数的一般情形给出了相应的结论，并开发了相应的可视化软件便于客户使用。最后，结合财务管理中的相关知识知，当生产时间较长或阶段收益较大时，资金的时间价值不能忽略。因此将其考虑进去重新建模求解，从而得到更加接近实际的模型。另外，为了得到更一般的情形，将一维资源分配问题推广到高维，并给出相应的模型和求解的大概思路和方法。针对具体问题，可以从中选择合适的方法进行求解。上面的过程是对问题的逐步细化、逐步拓展，最终使得模型更加接近实际，更加具有双重价值（理论价值和实际价值）。第 5 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）1、一般问题及相应的模型1.1 一般问题重述设有某种机器，初始的拥有量为，计划在A 和 B 两种零件的生产上连续使用n 个阶段，已知投给 A的机器数为时相应的阶段效益为，投给 B的机器数为时相应的阶段效益为。在实际生产过程中，机器都会有损失。根据以往的经验可知，生产A零件，一个阶段后的完好率为a，生产 B零件，一个阶段后的完好率为b（） ，求 n 阶段总收益最大的资源分配计划。 1sAU)g(UABU)(BUh1ba0 ，1.2 模型的建立1.2.1静态规划模型记：n 各阶段的总收益；Zku第 k 个阶段开始时分配给A 的机器数；Ks第 k 个阶段开始时完好的机器数则得该问题的静态规划模型为)()()()()()(gZmax222111nnnushugushugushu-+-+-+=?=-+=-+=-+=+nisuusbaususbaususbaustsiinnnn,2 , 10)()()(. .1222311121.2.2动态规划模型动态规划模型就是多阶段决策过程的数学模型。包括“一个大前提、四个条件、一个方程 DT 基本方程”：第 6 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）一个大前提： 把所研究的决策问题，按先后顺序划分为n 个相互联系的决策阶段，以便按一定的次序进行求解。四个条件： 状态与状态变量、决策与决策变量、状态转移方程和阶段效益与目标函数。状态与状态变量：状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况。描述状态的变量称为状态变量，第k 阶段的状态变量用表示。ks决策与决策变量：决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。 描述决策的变量称决策变量，第 k 阶段的决策变量用表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。ku状态转移方程：若第k 阶段的状态变量值为，当决策变量的取值决定后，下一阶段状态变量的值也就完全确定。这种对应关系=称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。ksku1+ks1+ks),(TkKkus阶段效益与目标函数：阶段效益是对某一阶段的状态和决策产生的效益值的度量，用表示。目标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为R。),(kkkusr一个方程： 即动态规划的基本方程。包括递推方程和边界条件两个部分。其中递推方程的合第 7 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）理性是由贝尔曼最优性原理给出的。其内容如下：（贝尔曼最优性原理）多步决策过程中的最优决策具有这样的性质：若将过程任意分成两段，则不论前半段的初始状态和决策如何，余下的后半段决策对于新的初始状态（即前半段的末值状态）仍构成一个最优决策。基于以上描述，结合问题，可以得到与问题相应的动态规划模型，为更加简洁明了，用表格表述该模型，详情如下：从第 k 个阶段至最后一个阶段的总收益函数)(kksf动态规划模型大前提n 阶段决策，每个阶段要决定A、 B 两种零件的机器投放量状态与状态变量k 阶段初拥有的完好机器数ks0nkssk,21=决策与决策变量k 阶段对零件A 的机器投放量kuAU=则有1 , 1,0UB-=-=nnksuuskkkk状态转移方程1 ,2, 1,BA)(1-=-+=+nnkusbauskkkk的机器阶段末完好数生产的机器阶段末完好数生产四个条件阶段效益& 目标函数 )()(1 ,2,1,)()(),(11=-+=-=-+=nknkkkkkkkkkkkushugrRnnkushugusr动态规划基本方程?-=+-+=+1 , 2, 1,0)()()()(max)(1111nnksfsfushugsfnnkkkkkkk第 8 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）2、特殊情形及相应模型的求解2.1 效益函数为线性函数时一般问题中的效益函数并没有具体给出，这给求解带来了诸多不便。为了求解所建立的模型， 将效益函数具体化。一般情况下， 产量越高， 效益越大。 这要求效益函数为增函数。现从最简单的情形开始考虑，即假设效益函数与产量成正比。多阶段决策问题本质上是一个最优控制问题，在控制论中我们知道，末端是否受限制对最优控制的结果有直接的影响。基于这种思想， 我们分末端自由和末端固定两种情形进行讨论。2.2.1末端自由情形在该种情形下，末端不受任何限制，是比较理想的状态。求解起来相对较为简便，为详细说明求解步骤，举例如下：【例题】某工厂用 125 台机器来加工两种零件，需要 5 年完成任务。 根据以往经验知道：机器加工第一种零件，一年后的损坏率为0.5；加工第二种零件，一年后的损坏概率是0.2。如果机器加工第一种零件一年的收益为10 万元，加工第二种零件一年的收益为6 万元。问如何安排这些机器，才能使5 年内获得的收益达到最大？解：第一步：划分阶段每一年为一个阶段，5 年分为 5 个阶段，5 ,4,3 ,2 ,1=k第二步：确定状态变量状态变量为第 k 年年初拥有的完好机器数，且ks1251=s5, 4, 3, 21250=ksk第三步：确定决策变量 决策变量为第 k 阶段安排加工第一种零件的机器数，且kxkksx 0，则在第k个阶段安排加工第二种零件的机器数为kkxs -第 9 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）第四步：状态转移方程 由于机器在两种工作任务下的损坏率分别是0.5 ，0.2 ，故相应的完好率分别是0.5和 0.8 。从而第k+1 年初拥有的完好设备数为： kkkkkkxsxsxs3 .08.0)(8. 05 .01-=-+=+ 状态转移方程 第五步：阶段效益与目标函数 阶段效益函数1 , 2, 3 ,4, 546)(610),(=+=-+=kxsxsxxsrkkkkkkkkmax 目标函数=+=5151)46(kkkkkxsrR第六步：基本方程?=-+=+=+边界条件递推方程0)()5, 4, 3, 2, 1()3.08 .0(64max)(),(max)(66111sfkxsfsxsfxsrsfkkkkkkkkkkkk下面开始求解，从最后一个阶段开始向前做逆推运算。k=5 时)64max()(5555sxsf+=550. .sxts因为是关于的线性单调增函数，故得最优解，此时有5f5x5*5sx=55510)(ssf=k=4 时)14max()3.08.0(*1064max)1064max()(64max)(444444544554444xsxssxssxsfsxsf+=-+=+=+=440. .sxts同理可得最优解为，此时有4*4sx=44415)(ssf=k=3 时)*5 .018max()3.08.0(*1564max)1564max()(64max)(333333433443333xsxssxssxsfsxsf-=-+=+=+=330s.t.sx 因为是关于的线性单调减函数，故得最优解，此时有3f3x0*3=x33318)(ssf=第 10 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）k=2 时)*4 .1*4 .20max()3 .08 .0(*1864max)1864max()(64max)(222222322332222xsxssxssxsfsxsf-=-+=+=+=220. .sxts同理可得最优解，此时有0*2=x222*4 .20)(ssf=k=1 时)*12. 2*32.22max()3.08.0(*4 .2064max)*4.2064max()(64max)(111111211221111xsxssxssxsfsxsf-=-+=+=+=110. .sxts仍然同理可得最优解为，此时有0*1=x111*32.22)(ssf=将反向代入得到1251=s163 .08 .032323 .08.064643 .08.00803.08.001003.08 .0055*6*544*5*433*4*322*3*211*2*1=-=-=-=-=-=xssxxssxxssxxssxxssx故决策过程如下：0*1=x0*2=x0*3=x64*4=x32*5=x万750*1=r万600*2=r万480*3=r万640*4=r万320*5=r即最优分配方案是第一年把全部机器都用来生产B，阶段收益为750 万，年末完好机器为 100 台；第二年把全部机器都用来生产B，阶段收益为600 万，年末完好机器为80 台；第三年把全部机器都用来生产B，阶段收益为480 万，年末完好机器为64 台；第四年把全部机器都用来生产A，阶段收益为640 万，年末完好机器为32 台；第五年把全部机器都用来生产 A，阶段收益为320 万，年末完好机器为16 台。五年总收益为2790 万元。第 11 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）2.2.3末端固定情形在实际生产过程中，往往会对末端加上一定的约束条件。比如，由于资金不足或其它某种原因， 在第五年结束时， 现在设备不能全部更新，要求完好的设备台数为台 （上例中为 16 台） ，则应如何安排生产，才能满足这一终端要求的情况使利润最高？30*6=s解：kkkkkkxsxsxs3 .08 .0)(8.05.01-=-+=+303. 08. 0556=-=xss（台）即1003855-=sx（1）显而易见， 由于固定了终端的状态，第五年的决策变量的允许决策集合也有了约束，（1）式说明已经退化为一个节点，也就是说，第五年投入A 的机器数只能由（ 1）做出一种决策。6s5x)(55sD)(55sD故40067.16)6400332max()64max()(5555555-=+-=+=ssssxsf利用递推公式不难解得k=4 时)40034.19max()(64max()(44554444-=+=xssfsxsf440. .sxts故得，相应的有0*4=x40034.19)(444-=ssf同理可得0*3=x，相应的有40047.21)(333-=ssf0*2=x，相应的有40018.23)(222-=ssf0*1=x，相应的有40054.24)(111-=ssf将代入得到1251=s)(5.266740054.24)(111万=-=ssf由此可见，为了使第五年年末的完好机器数为30 台，其最优策略发生了改变，详情如下表：第 12 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）年度年初完好设备数生产 A 机器数生产 B 机器数阶段收益（万元）1 125 0 125 750 2 100 0 100 600 3 80 0 80 480 4 64 0 64 384 5 51 36 15 453.5 由上面表格可知，由于末端受到约束，不仅使最优策略改变，而且使总收益也降低了一些。2.2 效益函数为非线性函数时2.1 给出了效益函数为线性函数时的问题的解，本节讨论更为复杂的情形效益函数为非线性函数。下面以二次函数为例进行详细说明。 【例题】 现有 1000 台机器，用于生产A、B 两种零件，计划连续使用三年。已知投入台机器生产 A时的年收益为（元） ，机器的完好率为a=0.5。投入台机器生产B时的年收益为（元），机器的完好率为b=0.9。试求使三年间总收益最大的年度机器分配方案。 AU24)(AAUUg=BU22)(BBUUh=解： 这是一个 3 阶段资源分配问题，每一个年度是一个阶段。可以看出， 年收益是年投入量的连续函数，并且机器数量相当大。若用离散化的方法来求解，工作量将非常的大，因此用解析的方法进行求解。为此设状态变量和决策变量都是连续取值的。 记 kx第 k 个阶段初完好的机器数； ku第 k 个阶段投入A的生产的机器数。 则 kkkxux010000第 13 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）状态转移方程： )(9.05 .01kkkkuxux-+=+动态规划基本方程：?=+-+=+0)()()(24max)(441122xfxfuxuxfkkkkkkk逆序求解，过程如下： k=3 时 )(24max)()(24max)(23323442332333uxuxfuxuxf-+=+-+=由于阶段效应是以为自变量的下凸抛物线（如下图），故23323333)(24),(uxuuxr-+=3u2333334)(xxfxu=k=2 时 )(9 .05 .04)(24max)()(24max)(222222222332222222uxuuxuxfuxuxf-+-+=+-+=上式右边 内作为的函数仍然是下凸的抛物线，因此最大值发生在的端点。比较函数在这两点的取值可以得到2u20 x2222224.5)(0 xxfu=同理可以得到k=1 时211112444.6)(0 xxfu=将反向代入，得到10001=x6244400)(11=xfR（元）从而40581081009000433221=xuxuxu第 14 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）即得最优分配方案。【#】由这个例子可以看到：当效益函数为定点在原点的二次函数时，问题是易于求解的，当它们为更复杂的函数时，求解就困难多了。但是，当为凸函数且时，可以证明在每个阶段上的最优决策总是取其上限或者下限。因此，对于解的结构来说，它与为线性的情况是类似的。)()(xhxg和)()(xhxg和0)0()0(= hg)()(xhxg和3、进一步讨论效益函数为线性，末端自由情形3.1 最优策略的一般关系式3.1.1问题简述与模型建立设有台某种机器，连续生产A、B 两种零件n 个阶段，一个阶段内，生产A、B 的效益函数分别为，其中1s21duhcug=cd 0。一个阶段后相应的机器的完好率为a 和b（） 。试求出最优策略的一般关系式。（符号说明同上）10d，所以1=n时才能使最大，此时)(nnsfnnncssf=)(1-= nk时)()()max()()()max()()(max)()(max)(111111111111111-+-=+-=-+-+=+-+=nnnnnnnnnnnnnnnnnsbcdabcdcsbcduabcdcusbaucusdcusfusdcusf?-=-elseabcdcn0)(11由前面例子我们知道，只要在第 k 阶段投入 B 的生产， 那么递推计算结果必然是从第1阶段到第k 阶段均生产B，即有021=k。由此可见，算出0=k后，前几年就没有必要再计算了。故只需研究那一年由生产B 转向生产A 即可。当11=-n时，)(1() 1()(22111-+-+=+=nnnnnbsubaacsacsf2-= nk时2222222221122211)1()(1()max()1()(1()max()(1()(max)()(max)(-+-+-=+-+-=+-+-+=+-+=nnnnnnnnnnnnnnnnsacbdabacdcsbacduabacdcbsubaacusdcusfusdcusf?-+-=-elseabacdcn0)(1 (12第 16 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）依此进行下去，得到(*)(1()(1 (t12)1(2?-+-=-+-abaaacdcabaaacdctntnt满足当故得问题相应的最优策略为011211=-ttnn由上述过程，可以得到一个很重要的结论：最优生产策略与初始状态无关。即不论机器的台数是否已知，不论机器的台数的多少，最优生产策略都是不变的。3.2 基于一般式的计算机求解由上节内容可知，只要求出满足（*）式的 t，即可确定机器任务分配问题的最优策略。因此，准确求出t 值是程序的关键之处。为使程序简单明了，引入相应的记号如下：记)()(1(1abcdcaR-=tna-=E（注意 E 是以 t 为自变量的增函数）注意到0001-abdca于是（ * ）式变为?RaERE从而可以得到基于一般式的计算框图如下：第 17 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）3.2.1基于 C+的求解用 Microsoft Visual C+ 6.0编写程序并进行调试，得到最终程序（见附录1） 。为检验其正确性，下面用2.2.1 中例子进行测试。在 2.2.1 中的例子中，6108.05.05=dcban。运行程序进行求解，将整个求解过程简述如下：（1）运行程序得到：第 18 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）（2）输入 n 的值，继而依此输入其它参数，得到：（3）回车即得机器任务分配问题的最优策略：与手动求解结果完全一致。因此可以认为运用该程序可以很准确地对收益函数为线性函数且末端自由的机器任务分配问题进行求解。3.2.2基于 VC 的可视化软件开发为了方便客户使用，基于 VC 进行可视化软件的开发，主要实现下面功能：提示客户进行相关参数的输入，然后以对话框的形式显示结果，单击确定显示进一步详细的结果。为了第 19 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）说明功能得以实现并且检验其正确性，仍应2.2.1 中的例子进行测试。详细过程如下：（1）双击 jqrwfp.exe ，进入界面（2）单击机器任务分配，得到（3）输入相应参数值，单击“确定”，得到第 20 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）（4）单击确定，得到详细的生产策略如下：由此可以看到，软件实现了所预想的功能，且测试成功！4、模型的改进与进一步推广4.1 考虑资金时间价值的模型众所周知， 即使是在没有通货膨胀和没有风险的理想状态下，今年获利1 万元与前年获利 1 万的价值是显然不同的。因为前年获得的1 万元如果存入银行，今年的现值（本金+利息）要超过1 万元。这是由资金的时间价值引起的。时间价值是客观存在的经济范围，任何企业的财务活动，都是在特定的时空中进行的。离开了时间价值因素，就无法正确计算出不同时期的财务收支，也无法正确评价企业的盈亏。时间价值原理，正确揭示了不同时间点上资金之间的换算关系，是财务决策的基本依据。当生产周期较短，或者阶段收益较小时，资金的时间价值可以忽略不计。但是，对于生产周期较长且阶段收益较大的机器任务分配问题就不得不将资金的时间价值考虑进去。下面给出考虑资金时间价值的机器任务分配问题模型（以收益函数为线性函数，末端自由的一般情形为例）。第 21 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）4.1.1基本假设和相关的符号说明（1）假设市场条件是理想的（即无通货膨胀且没有市场风险）；（2）假设资金的时间价值是按复利方式进行计算的；（3）假设在生产过程当中年利息率保持不变，均为)10( ii；（4）不妨假设一个阶段为一年（主要是和利息率的计量保持一致）；（5）记，则称为复利终值系数；ni)1 (FVIFni,+=ni,FVIF（6）假设各个阶段的收益在阶段末就可以全部获得（即从下一阶段开始生息）；（7），n 代表的含义同上。)(,kkkkksfrus4.1.2模型的建立与求解当将资金的时间价值考虑进去的时候，状态转移方程不变，但是阶段效益函数和基本方程均需做略微修改。在原来模型的基础上，很容易得到考虑资金时间价值的模型如下：状态转移方程：nkusbauskkkk,2,1),(1=-+=+阶段效益函数：nkusdcuFVIFrkkkknik,2 , 1),()( ,=-+=-基本方程为：?=-+-+=+-0)()()(max)(111)( ,nnkkkkkkkknikksfusbaufusdcuFVIFsf对于某一个特定的时期，i是一个已知的不变的数。因为动态规划是逐步求解的，故对于给定的k，n-k 已知，从而可以直接查表或者利用插值的方法得到的值（见附录 2） 。于是，问题又转化为效益函数为线性，末端自由的情形，可以参考前面求解的方法进行求解。)( ,kniFVIF-4.2 多元分配问题的推广前面所研究的机器任务分配问题仅仅涉及一种资源，因此也可称为一维机器任务分配问题。如果涉及两种机器任务的分配，则可称为二维资源分配问题。这类问题的一般提法是：第 22 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）现有总量为的两种资源，准备分配给n 项生产活动。如果分配给第i 种生产活动两种资源的数量分别是21MM 和), 2, 1(,niyxii=，由此产生的效益为，问应如何分配资源可使总收益达到最大？)(iiiyxg根据已知的信息，该问题的静态模型为?=njjniiniiiiMyMxtsyxg12111.)(max该模型可能是线性规划，也可能是非线性规划。当试图用动态规划处理该问题时，其阶段的划分与一维分配问题相同，但是状态变量和决策变量都是二维的。若设状态变量分别表示第k 阶段初所拥有的两种机器的完好数，即可用于分配给第 k 种至第 n 种生产活动的两种资源的总量；决策变量为分配给第k 种生产活动两种资源的数量，则状态转移方程是kkts ,kkyx ,?=-=?-=-=+221111) 1, 1,(MsMsnnkyttxsskkkkkk动态规划基本方程为?=+=+0),(),(),(max),(111111nnnkkkkkkkkktsftsfyxgtsf在实际问题中，由于状态变量、决策维数的增加和的复杂性，大大增加了计算的难度。 当状态变量为离散时适用于动态规划方法求解，对于连续情况， 一般先进行离散化处理，然后求其数值解。在求解过程中，常用疏密格子法、逐次逼近法和Lagrange 乘子法进行简化和降维。这些方法不再一一赘述，详见数学规划方面的相关书籍。),(yxg5、动态规划方法的评价机器任务分配问题运用了动态规划的方法进行求解。纵观整个过程， 对这种应用广泛的方法从优缺点两个方面作如下评价：第 23 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）优点：（1）它不需要对系统的状态转移方程、阶段指标函数等的解析性质作任何假定，因此，对于一些经典方法（如微分法、变分法）所不能解决的最优化问题，它常常能够提供一种可行的解法。（2）在动态规划中，它的约束条件的存在，不仅不会造成求解的困难，反而会因它们的存在减少了可选择状态和决策的数目，而对问题的求解更有利。（3）动态规划的方法不仅可以求出整个问题的最优策略和最优目标函数值，而且还求出了决策过程中各个中间状态的最优策略和最优目标函数值。也就是说， 动态规划方法求出的不是一个最优策略，而是一族最优策略，这对许多实际问题是很有用的，有利于分析所得到的结果。缺点：（1）动态规划虽然有一定的建模要求和解题步骤，但在一个具体问题中，如何划分阶段、识别状态、确定决策等，以及如何得到具体的状态转移方程，在很大程度上依赖于分析者的经验、洞察力和判断能力。（2）在利用“最优性原理”得到基本方程后，没有统一的处理方法，必须根据问题的各种性质，并结合一定的技巧来处理。（3）当问题中的自变量个数太大时，由于计算机存储器容量和计算速度的限制，而无法解决。即“维数障碍”。以上内容可以总结如下：第 24 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）总之，由于动态规划方法跨越了数学规划的各个领域，一些线性规划、非线性规划、整数规划的问题都可以用其求解，因此，它的应用广泛性是毋庸质疑的。另一方面，由于动态规划仅仅是人们提供了一种解决问题的手段，因此，如何更为有效地利用这种方法，还需经过不断的实践，并在应用中作进一步的探讨和研究。第 25 页 共 31 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 31 页 - - - - - - - - - 西安交通大学数学与应用数学专业课程设计（本科）附录一： C+程序#include #include int main() int n; double a,b,c,d; coutn; coutbd; coutac; double R=1-(c-d)*(1-a)/(c*(b-a); for(int t=n;t
