Dynamic Programming and Decision Analysis Principles

Second Partial: Operations Research II

Dynamic Programming Fundamentals

Dynamic programming is a mathematical optimization method used for situations requiring a sequence of decisions.

The deterministic dynamic programming model is one where the state of the next stage is completely determined by the policy decision of the current stage.

Problems in deterministic dynamic programming are classified by their objective function, which can be maximized, minimized, or optimized based on contributions at each stage.

Troubleshooting Dynamic Programming

• The problem is divided into stages, each requiring a decision.
• Solving each individual stage contributes to solving the overall problem.

An optimal policy for the remaining stages is independent of the policy adopted in previous stages: this is the Principle of Optimality.

Bellman's Principle: An optimal set of decisions has the property that if a particular decision is optimal, then all subsequent decisions following this specific decision must also be optimal.

Probabilistic Dynamic Programming

Dynamic programming differs from deterministic models when the state of the next stage is not completely determined by the current state and the policy decision.

Decision-Making Tools

Key tools include consensus, probability theory, decision models, game theory, and Markov chains.

Data Mining Applications

Data mining enables the discovery of hidden patterns, the creation of predictive models, and the identification of relationships within databases to extract valuable information for decision-making.

It is employed to improve the performance of business or industrial processes that handle large volumes of structured data.

Modeling Concepts

A model is an abstraction of reality designed to simulate an event, fact, or phenomenon as closely as possible. Models can be mental, mathematical, or computational.

Game Theory

Game theory is a decision model applied to relationships between two independent entities, such as individuals or organizations, often seeking an agreement.

Zero-Sum Games: A scenario where the gain of one player is the loss of the other. Rational opponents seek strategies to maximize their gain while identifying and eliminating non-optimal strategies.

• Maximin: Player A chooses the strategy where the minimum payoff is the greatest.
• Minimax: Player B chooses the strategy where the maximum payoff to A is as small as possible.

Empirical Decision Trees

This graphical method expresses viable alternatives and chance-based outcomes in chronological order.

Conditional Profit = (Demand * Price) - (Units Bought * Purchase Price)

Imperfect Information

When additional information regarding an event can be obtained, it is considered imperfect information. This implies that current data is insufficient to determine which specific outcome will occur.