What is dynamic programming? Discuss the applications of dynamic programming in decision-making. How is this different from linear programming? Explain

Dynamic Programming:
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler overlapping subproblems and solving each subproblem only once, storing the solutions to avoid redundant computations.

Get the full solved assignment PDF of MMPO-001 of 2023-24 session now.

The approach is particularly useful for problems exhibiting the optimal substructure and overlapping subproblems properties.

Applications of Dynamic Programming in Decision-Making:

1. Optimal Resource Allocation: DP is used to find the optimal allocation of resources over time, considering changing conditions and constraints.
2. Project Scheduling: DP helps in scheduling tasks over time to minimize completion time or costs, considering dependencies and resource constraints.
3. Inventory Management: DP is applied to determine the optimal inventory levels over time, considering demand fluctuations and costs associated with holding and ordering.
4. Finance: In finance, DP is used for portfolio optimization, asset allocation, and investment decisions by considering changing market conditions and risk factors.
5. Robotics and Control Systems: DP is employed in designing optimal control policies for systems that evolve over time, such as robotics or manufacturing processes.

Difference from Linear Programming:

1. Nature of Problems:

• Dynamic Programming: DP is used for problems where decisions are made sequentially over time, and the optimal solution depends on previous decisions.
• Linear Programming: LP deals with problems where a linear objective function is to be optimized, subject to linear equality and inequality constraints.

1. Time Dependency:

• Dynamic Programming: Considers the time dimension, making decisions at different time points, with solutions dependent on the state at each time.
• Linear Programming: Typically does not involve time; decisions are made at a single point in time.

1. Optimal Substructure:

• Dynamic Programming: Utilizes optimal substructure, where the optimal solution to the overall problem can be constructed from optimal solutions to its subproblems.
• Linear Programming: Involves solving a single, comprehensive problem without breaking it down into smaller subproblems.

1. Memory Usage:

• Dynamic Programming: Involves storing solutions to subproblems to avoid redundant computations, often requiring memory for memoization.
• Linear Programming: Solves the entire problem in one go, without the need for storing intermediate solutions.

In summary, dynamic programming is a method for solving optimization problems with a temporal dimension, breaking them into overlapping subproblems. In contrast, linear programming focuses on optimizing a linear objective function subject to linear constraints without the time-dependent aspect seen in dynamic programming.