求解预支约束下商品批发零售问题的近似算法  

A New Approximation Algorithm for Wholesale-retail Problem

作　　者：罗亮[1] 魏万喜 贾欣鑫[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070 [2]皋兰县教育局,甘肃兰州730200

出　　处：《兰州交通大学学报》2009年第6期138-140,共3页Journal of Lanzhou Jiaotong University

摘　　要：研究了求解预支约束下批发零售问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法相结合并从理论上分析了该算法的可靠性和有效性,最后得出了该算法的性能保证为1-e-1.A new approximation algorithm is presented for wholesale-retail problem.The algorithm is an improved greedy algorithm which combines the part of enumeration method with the greedy algorithm.At the same time,the reliability and effect of this algorithm are theoretically proved.Finially,it is presented that the algorithm has 1-e-1 performance guarantee for this problem.

关 键 词：预支约束 下模函数 近似算法 性能保证 

分 类 号：O224[理学—运筹学与控制论]