Dynamic Programming

Self Test Questions

Theory

1. What is Dynamic Programming ? In what areas of management can it be applied successfully?

2. Discus briefly:

• The general similarities between dynamic and linear programming
• How dynamic programming differs from linear programming?

3. Define the following terms

• Stage
• State
• Principle of optimality

Practical

1. Maximize z = x₁ + 9x₂

subject to
2x₁ + x₂ £ 25
x_{2 £} 11

x₁, x₂ ³ 0

2. Maximize z = 3x₁ + x₂

subject to
x₁£ 2
x_{2 £} 4
2x₁ + x₂ £ 6

x₁, x₂ ³ 0

3. The XYZ Trucking company has to deliver a shipment of goods from city A to city D as shown below. The numbers on the arcs represent the estimated driving times in hours between adjacent cities. The company wants to determine the route requiring the shortest travel time.

Solve the problem and find the minimum time and its associated optimal route.