Applications of Dynamic Programming

Dynamic programming

Dynamic programming is a special kind of optimization technique which subdivides an original problem into as many number of subproblems as the variables, solves each subproblem individually and then obtains the solution of the original problem by integrating the solutions of the subproblems.

The dynamic programming can be applied to many real-life situations. A sample list of applications of the dynamic programming is given below.

  1. Capital budgeting problem
  2. Reliability improvement problem
  3. Stage-coach problem (shortest-path problem)
  4. Cargo loading problem
  5. Minimizing total tardiness in single machine scheduling problem
  6. Optimal subdividing problem

They are discussed in the following sections:

Capital budgeting problem (Plant Expansion)

Waste-Water Treatment Plant Expansion (McKim & Creed)

A capital budgeting problem is a problem in which a given amount of capital is allocated to a set of plants by selecting the most promising alternative for each selected plant such that the total revenue of the organization is maximized.

Reliability improvement problem (Standby Unit)

Generally, electronic equipments are made up of several components in series or parallel. Assuming that the components are connected in series, if there is a failure of a component in the series, it will make the equipment inoperative. The reliability of the equipment can be increased by providing optimal number of standby units to each of the components in the series such that the total reliability of the equipment is maximized subject to a cost constraint.

Stage-coach problem (shortest-path problem)

Stage-coach problem is a shortest-path problem in which the objective is to find the shortest distance and the corresponding path from a given source node to a given destination node in a given distance network.

Cargo loading problem

Cargo loading problem is an optimization problem in which a logistic company is left with the option of loading a desirable combination of items in a cargo subject to its weight or volume or both constraints. In this process, the return to the company is to be maximized. The application of dynamic programming to the cargo loading problem which has only the weight constraint is illustrated.

Minimizing total tardiness in single machine scheduling problem

Single machine scheduling problem consists of n independent jobs which require processing in the same single machine. This n jobs will have subsequent !n sequences. The application of Dynamic Programming is to determine the sequence(s) which will minimize the total tardiness in the single machine scheduling.

Optimal subdividing problem

The objective of optimal subdiving problem is to for example, consider a cable of length k units. The objective is to subdivide the cable into n parts each having a length pi, where i varies from 1 to n such that the product of the lengths of the parts is maximized.

References:

Book: Operation Research by Paneerselvam

Images: https://images.google.com/

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store