A Preference Order Dynamic Program for a Knapsack Problem with Stochastic Rewards
作者:
SteinbergE.,
ParksM. S.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1979)
卷期:
Volume 30,
issue 2
页码: 141-147
ISSN:0160-5682
年代: 1979
DOI:10.1057/jors.1979.27
出版商: Taylor&Francis
数据来源: Taylor
摘要:
AbstractIn this paper, we extend the knapsack problem to include more realistic situations by treating the rewards (or values) associated with each item included in the solution as random variables with distributions that are known (or may be estimated) rather than known integers, as in the usual formulation. We propose a dynamic programming solution methodology where the usual real-valued return function is replaced by a preference ordering on the distributions of returns from the items selected. In addition to extending previous solutions to the knapsack problem, we demonstrate the selection of a preference ordering criterion and illustrate the conditions required of the ordering to guarantee optimality of the procedure. A sample problem is shown to demonstrate the algorithm, and results of computational experience with 459 problems of varying sizes and parameters are presented.
点击下载:
PDF (2512KB)
返 回