论文部分内容阅读
普通网络下的最大流问题,最短路问题,运输问题及分配问题作为最小费用流问题的特例在六七十年代就有了许多有效的算法,而最小费用流问题是各种网络规划问题的核心和基础,在金融,管理,经济等科学应用与研究中发挥着重要作用。很多工作者致力于建立新的数学模型并把它转化成最小费用流问题来解决。
研究网络图上的线性分式规划有着重要的理论背景与实际意义,本文首先考虑了普通网络模型中有限制的线性分式转运问题的数学模型,给出了基本可行解的概念并通过引进一个新的检验数论证了基本可行解是最优解的判别准则,总结了有限步终止的迭代步骤。其次把目标函数推广为分段线性分式函数给出了普通网络模型中的分段线性分式转运问题的数学模型,给出了该模型下的基本可行解的概念,论证了基可行解是最优解的充要条件,总结了有限步终止的迭代步骤。本文最后考虑了增益网络模型下的线性分式转运问题,通过分析增益网络中节点位势及流量增广迹上流量调整算法,提出了增益网络中线性分式转运问题基的迭代算法及有限终止。