برنامه نویسی پویا تصادفی برای حل مشکلات برنامه ریزی در مقیاس بزرگ تحت عدم قطعیت ☆

For quite some time, we have known that traditional methods of deterministic optimization are not suitable to capture the truly dynamic nature of most real-life problems, in view of the fact that the parameters which represent information concerning the future are uncertain. Many of the problems in planning under uncertainty, have logical constraints that require 0–1 variables in their formulation and can be solved via stochastic integer programming using scenario tree analysis. Given the dimensions of the deterministic equivalent model (DEM) of the stochastic problem, certain decomposition approaches can be considered by exploiting the structure of the models. Traditional decomposition schemes, such as the Benders and Lagrangean approaches, do not appear to provide the solution for large-scale problems (mainly in the cardinality of the scenario tree) in affordable computing effort. In this work, a stochastic dynamic programming approach is suggested, which we feel is particularly suited to exploit the scenario tree structure and, therefore, very amenable to finding solutions to very large-scale DEMs. The pilot case used involves a classical tactical production planning problem, where the structure is not exploited by the proposed approach so that it is generally applicable.