Towards sensitivity analysis in dynamic programming
S.S. Irvine · Bulletin of the Australian Mathematical Society · 1997
This thesis presents a comprehensive and unified framework for sensitivity analysis in dynamic programming.The approach developed is novel in that it is based on an adaptive data base containing the k best forward and backward returns to each (stage, state) pair.Under investigation is the sensitivity of the optimal return and set of optimal policies of a multistage decision process to changes in the elements of the model such as stage, transition law, decision space and stage return function.We also address the question of what information should be stored in the data base so as to facilitate the quick determination via on-line calculation, of the effect of these changes on the optimal return and set of optimal policies.The theory developed is applied to two classes of problems, namely the knapsack and shortest path problems, the later being treated as a sequential rather than a multistage problem.Methods are developed for updating the data base efficiently, so as to be able to deal with the next change to the system.This is done through key modules which show how to update the data base by exploiting the stagewise structure of the dynamic programming algorithms.Also, a parametric analysis scheme exploiting the stagewise structure of dynamic programming algorithms is developed for functional equations containing Lagrange multipliers.Of particular interest is the application of these developed schemes to Lagrangian problems resulting from the incorporation of a constraint as a penalty term into the objective function.This is examined in the context of reliability constrained reservoir control problems.The relationship between reservoir control and inventory control is investigated and it is shown how to invert an inventory problem into a reservoir control problem, in particular, problems subjected to reliability constraints.The parametric analysis of the resulting Lagrangian problem then provides a framework for controlling shortages which does not require an explicit value to be assigned to the stockout cost.This method is also used to study the sensitivity of the optimal return to various reliability levels.