两端固定资源连续分配问题的区间根式解算法证明摘要对两端固定资源连续分配问题，动态规划解法过程复杂，针对目标函数及约束条件均为线性函数的此类问题，给出一个根式解的算法证明，将针对点的根式解的算法推广到区间的根式解。关键词运筹学，资源分配，动态规划，算法AbstractTheproblemofresourcescontinuousallocationwithfixedtwoendscanbesolvedbydynamicprogram.Buttheprocessiscomplicatetosolveitbydynamicprogram.Tosolvethiskindofproblemwhichbothobjectiveandconstraintfunctionsarealllineal,aproofaboutaprogramforitsradicalexpressionofpointbutalsotheinterzoneradicalexpression.KeywordsOperationsresearch;resourcescontinuousallocation;dynamicprogram;algorithm引言资源分配问题是指将数量一定的一种或若干种资源恰当的分配给若干使用者，从而使目标函数为最优，在资源分配问题中，有一种要考虑资源回收利用的问题，其决策变量为连续值，故称为资源连续分配问题。若这种问题的目标函数及约束条件均为线性函数称全线性问题，对资源分配问题，通常的解法为动态规划。由于动态规划的求解方法计算量比较大，所以，寻找根式解是这类问题的一个研究方向。对始端固定终端自由的全线性问题，文献1给出了通用的根式解。所谓始端固定终端自由的全线性问题指给定始端的约束，但不给定终端的约束，目标函数与约束均为线性，文献2则以始端固定终端自由问题的解作为两端固定的问题解，这种做法在某些特殊情况下是可行的，但在一般情况下，终端自由问题的最优解不是两端固定问题的可行解。文献3给出了计算两端固定问题的根式解的算法，但是，该算法针对了两端固定问题的点模型（即点解），而不是区间模型（区间解），因此，如何将文献3的算法推广到区间模型尚需研究。本文给了一个证明，将文献3的根式解算法推广到区间模型上。1．两端固定全线性连续资源分配问题的描述设有n阶段和两种模式，分别为高消耗模式和低消耗模式。在任一阶段均可在一种或者两种模式下使用全部或者部分资源，在高消耗模式下，资源回收率为a，且产出c>0,在低消耗模式下，资源回收率为b,且产出d>0,其中，给出的起点资源为，终点资源为。设为总产出，且在阶段，是高消耗模式下的资源权因子，是低消耗模式下的资源权因子，其中，问题就成为，如何定义所有，使得最大。其数学模型如下（1.1）：（1.1）其中，目标函数为式（1.2）：（1.2）式中，为便于描述，本文将全线性连续资源分配问题简称为资源分配问题。注意这里的模型与文献3不同，文献3的模型如下：（1.3）模型（1.1）的第一约束式为，而模型（1.3）的第一约束式为，故。模型（1.1）称区间模型，其解称区间解，模型（1.3）称点模型，其解称点解。2．区间解的算法基础定理证明分析上面的模型（1.1）与模型（1.3），可知两式相差一个约束符号，如果模型（1.1）的第一约束式总是在其边界上取得最优解，即，其最优解总在第一约束取等号时得到，则模型（1.3）与模型（1.1）具有完全等价性，在这种情况下，针对任意一个模型的算法均对另一个模型有效。所以，如果要将文献3中的算法推广到区间解，则必须证明模型（1.1）的最优解总是在第一约束式的边界取得。用反证明法，假设模型（1.1）的最优解不在第一约束式的边界取得，则必存在一个，使得模型（2.4）（2.4）的最优解大于模型（1.3）的最优解，即，对于模型（1.3）而言，有所以，如果有，则上述假设不成立，模型（1.1）的最优解必然在边界取得，从而，模型（1.1）与模型（1.3）等价，文献3的算法可以推广到模型（1.1）求得区间解。由此，问题转化为求证模型（1.3）中，有证明由文献3算法知，存在两种情况：当时，对于有，对于有且至多存在一个使，当时有，当时有，当时，对于有，对于有且至多存在一个使，当时有，当时有。所以，对于问题的证明分两步证明，首先证明情况（1）时有，然后证明情况（2）时也有。令，因为当时有，当时有，故：（2.5）所以，是的函数，求导数得：。因为，所以从而有因为题设，，所以有因为且是常数，所以有（2.6）对模型（1.3）的第一约束，代入条件：当时有，当时有，有所以有（2.7）由式（2.6）和式（2.7）知令，因