Operations Research, 2nd Edition

6

Dynamic Programming

6.1 INTRODUCTION

The mathematical technique of optimising a sequence of interrelated decisions over a period of time is called dynamic programming (DP). It uses the idea of recursion to solve a complex problem, broken into a series of sub-problems. The word dynamic has been used because time is explicitly taken into consideration. The objective in dynamic programming is to select a decision policy so to optimise the returns that are in the form of costs or benefits.

Mathematically a dynamic programming problem DPP is a decision–making problem in n variables, the problem being sub-divided in to n sub-problems and each such problem being a decision-making problem in one variable only. The solution to a DPP is achieved sequentially ...