摘要
对两个约束条件下多产品报童问题的求解方法进行研究。首先分析了问题的结构特征,利用对偶问题解空间的四个不同区域对应的最优解具有的不同性质,给出了不同解空间区域的求解思路。然后基于两种资源的边际利益的性质,提出一种二分搜索算法对问题进行求解,并证明了该算法能够得到问题的最优解或者近似最优解,且具有多项式复杂度。最后应用算例说明算法计算效率高,可以在较少的迭代步骤内快速求解两个线性约束下产品数较大的多产品报童问题。
The multi-product newsvendor problem with two constraints is studied.Firstly,the characteristics of the problem are described,and the properties of the optimal solution to four distinct regions of the dual of the solution space are analyzed.Then the binary search algorithm with polynomial computation complexity is proposed to obtain the optimal or near optimal solution by the properties of marginal benefit of resources.Finally the numerical examples show the effectiveness of the algorithm,and it is proved that the common situation where a large number of products are involved can be efficiently handled.
出处
《运筹与管理》
CSCD
北大核心
2010年第6期27-32,72,共7页
Operations Research and Management Science
基金
国家自然科学基金资助项目(70563005)
福建省社科基金资助项目(2008B2033)
福建省教育厅资助项目项目(JA08040S)
福州大学社科研究资助项目项目(826535)
关键词
运筹学
算法
二分搜索算法
多产品报童问题
两个约束
operational research
algorithm
binary search algorithm
multi-product newsvendor problem
two constraints
