两端固定资源连续分配问题

《两端固定资源连续分配问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、两端固定资源连续分配问题的区间根式解算法证明摘要对两端固定资源连续分配问题，动态规划解法过程复杂，针对目标函数及约束条件均为线性函数的此类问题，给岀一个根式解的算法证明，将针对点的根式解的算法推广到区间的根式解。关键词运筹学，资源分配，动态规划，算法AbstractTheproblemofresourcescontinuousallocationwithfixedtwoendscanbesolvedbydynamicprogram.Buttheprocessiscomplicatetosolveitbydynamicprogram.Tosolvethisk

2、indofproblemwhichbothobjectiveandconstraintfunctionsarealllineal,aproofaboutaprogramforitsradicalexpressionofpointbutalsotheinterzoneradicalexpression.KeywordsOperationsresearch;resourcescontinuousallocation;dynamicprogram;algorithm引言资源分配问题是指将数量一定的一种或若干种资源恰当的分配给若干使用者，从而使目标函数为最优，在资

3、源分配问题中，有一种要考虑资源回收利用的问题,其决策变量为连续值，故称为资源连续分配问题。若这种问题的目标函数及约束条件均为线性函数称全线性问题，对资源分配问题，通常的解法为动态规划。由于动态规划的求解方法计算量比较大，所以，寻找根式解是这类问题的一个研究方向。对始端I古I定终端自由的全线性问题，文献1给岀了通用的根式解。所谓始端固定终端自由的全线性问题指给定始端的约束，但不给定终端的约束，目标函数与约束均为线性，文献2则以始端固定终端自由问题的解作为两端固定的问题解，这种做法在某些特殊情况下是可行的，但在一般情况下，终端自由问题的最优解不是两端固定问题的

4、可行解。文献3给出了计算两端固定问题的根式解的算法，但是，该算法针对了两端固定问题的点模型（即点解），而不是区间模型（区间解），因此，如何将文献3的算法推广到区间模型尚需研究。本文给了一个证明,将文献3的根式解算法推广到区间模型上。1.两端固定全线性连续资源分配问题的描述设有n阶段和两种模式，分别为高消耗模式和低消耗模式。在任一阶段均可在一种或者两种模式下使用全部或者部分资源，在高消耗模式下，资源回收率为a,且产出O0,在低消耗模式下，资源回收率为b,且产出d>0,其中，0d>0.给出的起点资源为①，终点资源为5/l+1o设/为总产出，且

5、在i阶段，叫•是高消耗模式下的资源权因子，1-嗎是低消耗模式下的资源权因子，其中l0,(0

6、如下：n（z-lmax/（W）=S]0[wjC+（l-wJd]]J[MV7+（l-wJb]>Z=1IBl,[叭(d-®+可二陥(1.3)k=0,(0

7、即，其最优解总在第一约束取等号时得到，则模型（1.3）与模型（1.1）具有完全等价性，在这种情况下，针对任意一个模型的算法均对另一个模型有效。所以，如果要将文献3中的算法推广到区间解，则必须证明模型（1.1）的最优解总是在第一约朿式的边界取得。用反证明法，假设模型（1.1）的最优解不在第一约束式的边界取得，则必存在一个臨>陥，使得模型（2.4）z-Imax/(w)=®立W+/=!(1-骂)〃］11［叱+(1-叫)可>Bl•［叭(。一方)+可=$:+］(2.4)k=O,(O

8、优解/,即，对于模型(1・3)而言，有单一>0就+】所以，如果有里