Dynamic Programming
Dynamic Programming
1 Sticks 2 Sticks
30 0 30
30 0 30
30 0 30
30 0 30
30 0 30
30 0 30
30 0 30
30 0 30
No Winner Yet No Winner Yet
Number of
Ounces in 9-
oz Cup
6 Remains at 6 oz (My Mother will be happy)
6 Transfer 3 oz to the 4oz cup
9 Order 9oz Milk (cup becomes completely filled)
0 Transfer 1 oz to the 4oz cup
1 Remains at 1 oz
1 Transfer 4 oz to the 4oz cup
5 Remains at 5 oz
5 Transfer 4 oz to the 4oz cup
9 Order 9oz Milk (cup becomes completely filled)
0 empty
Number of
Ounces in 4-
oz Cup
0 Empty the 4 oz cup
4 completely filled
1 Remains at 1 oz
1 filled with 1 oz
0 Empty the 4 oz cup
4 completely filled
0 Empty the 4 oz cup
4 completely filled
0 empty
0 empty
Days State f
0 New York 1
1 Columbus 2
1 Nashville 3
1 Louisville 4
2 Kansas City 5
2 Omaha 6
2 Dallas 7
3 Denver 8
3 San Antonio 9
4 Los Angeles 10
Quantity to be produced
Min Z
Variable
Demand Set Up Cost Cost/unit
Month
(in units) (Dollars) produced
(Dollars)
Month 1 1 3 1
Month 2 3 3 1
Month 3 2 3 1
Month 4 4 3 1
Beginning Inventory 0
Maximum Prod Capaci 5
Dynamic programming
Beginning Quantity
Demand
Inventory to Produce
Month
Month 4 4 4 0
Month 4 3 4 1
Month 4 2 4 2
Month 4 1 4 3
Month 4 0 4 4
Beginning Quantity
Demand
Inventory to Produce
Month
Month 3 0 2 2
Month 3 0 2 3
Month 3 0 2 4
Month 3 0 2 5
Month 3 1 2 1
Month 3 1 2 2
Month 3 1 2 3
Month 3 1 2 4
Month 3 1 2 5
Month 3 2 2 0
Month 3 2 2 1
Month 3 2 2 2
Month 3 2 2 3
Month 3 2 2 4
Month 3 3 2 0
Month 3 3 2 1
Month 3 3 2 2
Month 3 3 2 3
Month 3 4 2 1
Month 3 4 2 2
Beginning Quantity
Demand
Inventory to Produce
Month
Month 3 0 2 2
Month 3 1 2 5
Month 3 2 2 0
Month 3 3 2 0
Month 3 4 2 2
Beginning Quantity
Demand
Inventory to Produce
Month
Month 2 0 3 3
Month 2 0 3 4
Month 2 0 3 5
Month 2 1 3 2
Month 2 1 3 3
Month 2 1 3 4
Month 2 1 3 5
Month 2 2 3 1
Month 2 2 3 2
Month 2 2 3 3
Month 2 2 3 4
Month 2 2 3 5
Month 2 3 3 0
Month 2 3 3 1
Month 2 3 3 2
Month 2 3 3 3
Month 2 3 3 4
Month 2 4 3 0
Month 2 4 3 1
Month 2 4 3 2
Month 2 4 3 3
Beginning Quantity
Demand
Inventory to Produce
Month
Month 2 0 3 5
Month 2 1 3 4
Month 2 2 3 3
Month 2 3 3 0
Month 2 4 3 0
Beginning Quantity
Demand
Inventory to Produce
Month
Month 1 0 1 1
Month 1 0 1 2
Month 1 0 1 3
Month 1 0 1 4
Month 1 0 1 5
ment vs Warehouse Capacity
Holding
Capacity
Cost/ unit
Limitation
on hand
(units)
(Dollars)
0.5 5
0.5 5
0.5 5
0.5 5
y is nonnegative
d per month
he beginning of the current month
et up cost
Variable
Set Up
Cost/unit Production Ending
Cost
produced Cost Inventory
(Dollars)
(Dollars)
0 1 0 0
3 1 4 0
3 1 5 0
3 1 6 0
3 1 7 0
Variable
Set Up Holding Total Month 4
Cost/unit Production Ending
Cost Cost per Holding Month 3 Production
produced Cost Inventory
(Dollars) Unit Cost Cost
(Dollars)
3 1 5 0 0.5 0 5 7
3 1 6 1 0.5 0.5 6.5 6
3 1 7 2 0.5 1 8 5
3 1 8 3 0.5 1.5 9.5 4
3 1 4 0 0.5 0 4 7
3 1 5 1 0.5 0.5 5.5 6
3 1 6 2 0.5 1 7 5
3 1 7 3 0.5 1.5 8.5 4
3 1 8 4 0.5 2 10 0
0 1 0 0 0.5 0 0 7
3 1 4 1 0.5 0.5 4.5 6
3 1 5 2 0.5 1 6 5
3 1 6 3 0.5 1.5 7.5 4
3 1 7 4 0.5 2 9 0
0 1 0 1 0.5 0.5 0.5 6
3 1 4 2 0.5 1 5 5
3 1 5 3 0.5 1.5 6.5 4
3 1 6 4 0.5 2 8 0
3 1 4 3 0.5 1.5 5.5 4
3 1 5 4 0.5 2 7 0
on capacity
not exceed 4, since demand for month 4 is only 4
Variable
Set Up Holding Total Month 4
Cost/unit Production Ending
Cost Cost per Holding Month 3 Production
produced Cost Inventory
(Dollars) Unit Cost Cost
(Dollars)
3 1 5 0 0.5 0 5 7
3 1 8 4 0.5 2 10 0
0 1 0 0 0.5 0 0 7
0 1 0 1 0.5 0.5 0.5 6
3 1 5 4 0.5 2 7 0
Variable
Set Up Holding Total
Cost/unit Production Ending Month 3 and
Cost Cost per Holding Month 2
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
3 1 6 0 0.5 0 6 12
3 1 7 1 0.5 0.5 7.5 10
3 1 8 2 0.5 1 9 7
3 1 5 0 0.5 0 5 12
3 1 6 1 0.5 0.5 6.5 10
3 1 7 2 0.5 1 8 7
3 1 8 3 0.5 1.5 9.5 6.5
3 1 4 0 0.5 0 4 12
3 1 5 1 0.5 0.5 5.5 10
3 1 6 2 0.5 1 7 7
3 1 7 3 0.5 1.5 8.5 6.5
3 1 8 4 0.5 2 10 7
0 1 0 0 0.5 0 0 12
3 1 4 1 0.5 0.5 4.5 10
3 1 5 2 0.5 1 6 7
3 1 6 3 0.5 1.5 7.5 6.5
3 1 7 4 0.5 2 9 7
0 1 0 1 0.5 0.5 0.5 10
3 1 4 2 0.5 1 5 7
3 1 5 3 0.5 1.5 6.5 6.5
3 1 6 4 0.5 2 8 7
Variable
Set Up Holding Total
Cost/unit Production Ending Month 3 and
Cost Cost per Holding Month 2
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
3 1 8 2 0.5 1 9 7
3 1 7 2 0.5 1 8 7
3 1 6 2 0.5 1 7 7
0 1 0 0 0.5 0 0 12
0 1 0 1 0.5 0.5 0.5 10
Variable
Set Up Holding Total
Cost/unit Production Ending Month 2 and
Cost Cost per Holding Month 1
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
3 1 4 0 0.5 0 4 16
3 1 5 1 0.5 0.5 5.5 15
3 1 6 2 0.5 1 7 14
3 1 7 3 0.5 1.5 8.5 12
3 1 8 4 0.5 2 10 10.5
Month 3
and 4
Cost
12
12.5
13
13.5
11
11.5
12
12.5
10
7
10.5
11
11.5
9
6.5
10
10.5
8
9.5
7
Month 3
and 4
Cost
12
10
7
6.5
7
Month 2
to 4
Cost
18
17.5
16
17
16.5
15
16
16
15.5
14
15
17
12
14.5
13
14
16
10.5
12
13
15
Month 2
to 4
Cost
16
15
14
12
10.5
Month 1
to 4
Cost
Dynamic Programming
Investment
(thousand NPV (r)
dollars) (x3)
0 0
1 9
2 13
3 17
4 21
5 25
6 29
Stage 2 (investment 2)
d2 (amount
x2( amount invested in r2 (NPV of
available for
investment 2) Investment 2
investment)
0 0 0
1 0 0
1 1 10
2 0 0
2 1 10
2 2 13
3 0 0
3 1 10
3 2 13
3 3 16
4 0 0
4 1 10
4 2 13
4 3 16
4 4 19
5 0 0
5 1 10
5 2 13
5 3 16
5 4 19
5 5 22
6 0 0
6 1 10
6 2 13
6 3 16
6 4 19
6 5 22
6 6 25
d2 (amount
x2( amount invested in r2 (NPV of
available for
investment 2) Investment 2
investment)
0 0 0
1 1 10
2 1 10
3 1 10
4 1 10
5 1 10
6 1 10
d1 (amount r1 (NPV of
x1( amount invested in
available for Investment
investment 1)
investment) 1)
6 0 0
6 1 9
6 2 16
6 3 23
6 4 30
6 5 37
6 6 44
Investment 1 4
Investment 2 1
Investment 3 1
ed to investment j
for investment
vestment?
r3 (NPV of
d3 (d2- Total
Investment
x2) NPV
3)
0 0 0
1 9 9
0 0 10
2 13 13
1 9 19
0 0 13
3 17 17
2 13 23
1 9 22
0 0 16
4 21 21
3 17 27
2 13 26
1 9 25
0 0 19
5 25 25
4 21 31
3 17 30
2 13 29
1 9 28
0 0 22
6 29 29
5 25 35
4 21 34
3 17 33
2 13 32
1 9 31
0 0 25
r3 (NPV of
d3 (d2- Total
Investment
x2) NPV
3)
0 0 0
0 0 10
1 9 19
2 13 23
3 17 27
4 21 31
5 25 35
r2+r3 (NPV
d2 (d1- of Total
x1) investment NPV
2 and 3
6 35 35
5 31 40
4 27 43
3 23 46
2 19 49
1 10 47
0 0 44
Option 1 option 3
2 item 3 2 item 1
Option 2 optiom 4
3 item 2 1 item 1, 1 item 3
Stage Item
State Remaining pound to be caried
Decision Maximum benefit
Stage 3 (Item 3)
d3 (pound
x3 weight
available to total pound filled in remaining
(quantity of item benefit
be filled in knapsack capacity
of item 3) 3
knapsack)
10 0 5 0 0 10
10 1 5 5 12 5
10 2 5 10 24 0
Stage 2 (Item 2)
d2 (pound
x2 weight
available to total pound filled in remaining
(quantity of item benefit (x2)
be filled in knapsack capacity
of item 2) 2
knapsack)
10 0 3 0 0 10
10 1 3 3 7 7
10 2 3 6 14 4
10 3 3 9 21 1
9 0 3 0 0 9
9 1 3 3 7 6
9 2 3 6 14 3
9 3 3 9 21 0
8 0 3 0 0 8
8 1 3 3 7 5
8 2 3 6 14 2
7 0 3 0 0 7
7 1 3 3 7 4
7 2 3 6 14 1
6 0 3 0 0 6
6 1 3 3 7 3
6 2 3 6 14 0
5 0 3 0 0 5
5 1 3 3 7 2
4 0 3 0 0 4
4 1 3 3 7 1
3 0 3 0 0 3
3 1 3 3 7 0
2 0 3 0 0 2
1 0 3 0 0 1
d2 (pound
x2 weight
available to total pound filled in remaining
(quantity of item benefit (x2)
be filled in knapsack capacity
of item 2) 2
knapsack)
10 0 3 0 0 10
9 3 3 9 21 0
8 1 3 3 7 5
7 2 3 6 14 1
6 2 3 6 14 0
5 0 3 0 0 5
4 1 3 3 7 1
3 1 3 3 7 0
2 0 3 0 0 2
1 0 3 0 0 1
Stage 1 (Item 1)
d1 (pound
x1 weight
available to total pound filled in remaining
(quantity of item benefit (x1)
be filled in knapsack capacity
of item 1) 1
knapsack)
10 0 4 0 0 10
10 1 4 4 11 6
10 2 4 8 22 2
quantity of
x3 that can total
be filled into benefit benefit
the (x3) (item 2
remaining and 3)
capacity
2 24 24
0 0 21
1 12 19
0 0 14
0 0 14
1 12 12
0 0 7
0 0 7
0 0 0
0 0 0
benefit total
(x2+X3) benefit
24 24
14 25
0 22
mi cost of maintaining an engine analyzer
i year
Date Purchased 1 2 3 4
0 260 540 760
1 260 540 760
2 260 540
3 260
4
5
760
540
260
0
Quantity to be produced
Min Z
Variable
Demand Set Up Cost Cost/unit
Month
(in units) (Dollars) produced
(Dollars)
Month 1 1 3 1
Month 2 3 3 1
Month 3 2 3 1
Month 4 4 3 1
Beginning Inventory 0
Maximum Prod Capaci 5
Dynamic programming
Beginning Quantity
Demand
Inventory to Produce
Month
Month 4 4 4 0
Month 4 3 4 1
Month 4 2 4 2
Month 4 1 4 3
Month 4 0 4 4
Beginning Quantity
Demand
Inventory to Produce
Month
Month 3 0 2 0
Month 3 0 2 1
Month 3 0 2 2
Month 3 0 2 3
Month 3 0 2 4
Month 3 0 2 5
Month 3 1 2 0
Month 3 1 2 1
Month 3 1 2 2
Month 3 1 2 3
Month 3 1 2 4
Month 3 1 2 5
Month 3 2 2 0
Month 3 2 2 1
Month 3 2 2 2
Month 3 2 2 3
Month 3 2 2 4
Month 3 2 2 5
Month 3 3 2 0
Month 3 3 2 1
Month 3 3 2 2
Month 3 3 2 3
Month 3 3 2 4
Month 3 3 2 5
Month 3 4 2 1
Month 3 4 2 2
Month 3 4 2 3
Month 3 4 2 4
Month 3 4 2 5
Beginning Quantity
Demand
Inventory to Produce
Month
Month 3 0 2 2
Month 3 1 2 5
Month 3 2 2 0
Month 3 3 2 0
Month 3 4 2 2
Beginning Quantity
Demand
Inventory to Produce
Month
Month 2 0 3 0
Month 2 0 3 1
Month 2 0 3 2
Month 2 0 3 3
Month 2 0 3 4
Month 2 0 3 5
Month 2 1 3 0
Month 2 1 3 1
Month 2 1 3 2
Month 2 1 3 3
Month 2 1 3 4
Month 2 1 3 5
Month 2 2 3 0
Month 2 2 3 1
Month 2 2 3 2
Month 2 2 3 3
Month 2 2 3 4
Month 2 2 3 5
Month 2 3 3 0
Month 2 3 3 1
Month 2 3 3 2
Month 2 3 3 3
Month 2 3 3 4
Month 2 3 3 5
Month 2 4 3 0
Month 2 4 3 1
Month 2 4 3 2
Month 2 4 3 3
Month 2 4 3 4
Month 2 4 3 5
Beginning Quantity
Demand
Inventory to Produce
Month
Month 2 0 3 5
Month 2 1 3 4
Month 2 2 3 3
Month 2 3 3 0
Month 2 4 3 0
Beginning Quantity
Demand
Inventory to Produce
Month
Month 1 0 1 0
Month 1 0 1 1
Month 1 0 1 2
Month 1 0 1 3
Month 1 0 1 4
Month 1 0 1 5
Month 1 1 1 0
Month 1 1 1 1
Month 1 1 1 2
Month 1 1 1 3
Month 1 1 1 4
Month 1 1 1 5
Month 1 2 1 0
Month 1 2 1 1
Month 1 2 1 2
Month 1 2 1 3
Month 1 2 1 4
Month 1 2 1 5
Month 1 3 1 0
Month 1 3 1 1
Month 1 3 1 2
Month 1 3 1 3
Month 1 3 1 4
Month 1 3 1 5
Month 1 4 1 0
Month 1 4 1 1
Month 1 4 1 2
Month 1 4 1 3
Month 1 4 1 4
Month 1 4 1 5
ment vs Warehouse Capacity
Holding
Capacity
Cost/ unit
Limitation
on hand
(units)
(Dollars)
0.5 5
0.5 5
0.5 5
0.5 5
y is nonnegative
d per month
he beginning of the current month
et up cost
Variable
Set Up
Cost/unit Production Ending
Cost
produced Cost Inventory
(Dollars)
(Dollars)
0 2 0 0
3 2 5 0
3 2 7 0
3 2 9 0
3 2 11 0
Variable
Set Up Holding Total Month 4
Cost/unit Production Ending
Cost Cost per Holding Month 3 Production
produced Cost Inventory
(Dollars) Unit Cost Cost
(Dollars)
0 2 0 -2 0.5 -1 -1 #N/A
3 2 5 -1 0.5 -0.5 4.5 #N/A
3 2 7 0 0.5 0 7 11
3 2 9 1 0.5 0.5 9.5 9
3 2 11 2 0.5 1 12 7
3 2 13 3 0.5 1.5 14.5 5
0 2 0 -1 0.5 -0.5 -0.5 #N/A
3 2 5 0 0.5 0 5 11
3 2 7 1 0.5 0.5 7.5 9
3 2 9 2 0.5 1 10 7
3 2 11 3 0.5 1.5 12.5 5
3 2 13 4 0.5 2 15 0
0 2 0 0 0.5 0 0 11
3 2 5 1 0.5 0.5 5.5 9
3 2 7 2 0.5 1 8 7
3 2 9 3 0.5 1.5 10.5 5
3 2 11 4 0.5 2 13 0
3 2 13 5 0.5 2.5 15.5 #N/A
0 2 0 1 0.5 0.5 0.5 9
3 2 5 2 0.5 1 6 7
3 2 7 3 0.5 1.5 8.5 5
3 2 9 4 0.5 2 11 0
3 2 11 5 0.5 2.5 13.5 #N/A
3 2 13 6 0.5 3 16 #N/A
3 2 5 3 0.5 1.5 6.5 5
3 2 7 4 0.5 2 9 0
3 2 9 5 0.5 2.5 11.5 #N/A
3 2 11 6 0.5 3 14 #N/A
3 2 13 7 0.5 3.5 16.5 #N/A
on capacity
not exceed 4, since demand for month 4 is only 4
Variable
Set Up Holding Total Month 4
Cost/unit Production Ending
Cost Cost per Holding Month 3 Production
produced Cost Inventory
(Dollars) Unit Cost Cost
(Dollars)
3 2 7 0 0.5 0 7 11
3 2 13 4 0.5 2 15 0
0 2 0 0 0.5 0 0 11
0 2 0 1 0.5 0.5 0.5 9
3 2 7 4 0.5 2 9 0
Variable
Set Up Holding Total
Cost/unit Production Ending Month 3 and
Cost Cost per Holding Month 2
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
0 2 0 -3 0.5 -1.5 -1.5 #N/A
3 2 5 -2 0.5 -1 4 #N/A
3 2 7 -1 0.5 -0.5 6.5 #N/A
3 2 9 0 0.5 0 9 18
3 2 11 1 0.5 0.5 11.5 15
3 2 13 2 0.5 1 14 11
0 2 0 -2 0.5 -1 -1 #N/A
3 2 5 -1 0.5 -0.5 4.5 #N/A
3 2 7 0 0.5 0 7 18
3 2 9 1 0.5 0.5 9.5 15
3 2 11 2 0.5 1 12 11
3 2 13 3 0.5 1.5 14.5 9.5
0 2 0 -1 0.5 -0.5 -0.5 #N/A
3 2 5 0 0.5 0 5 18
3 2 7 1 0.5 0.5 7.5 15
3 2 9 2 0.5 1 10 11
3 2 11 3 0.5 1.5 12.5 9.5
3 2 13 4 0.5 2 15 9
0 2 0 0 0.5 0 0 18
3 2 5 1 0.5 0.5 5.5 15
3 2 7 2 0.5 1 8 11
3 2 9 3 0.5 1.5 10.5 9.5
3 2 11 4 0.5 2 13 9
3 2 13 5 0.5 2.5 15.5 #N/A
0 2 0 1 0.5 0.5 0.5 15
3 2 5 2 0.5 1 6 11
3 2 7 3 0.5 1.5 8.5 9.5
3 2 9 4 0.5 2 11 9
3 2 11 5 0.5 2.5 13.5 #N/A
3 2 13 6 0.5 3 16 #N/A
Variable
Set Up Holding Total
Cost/unit Production Ending Month 3 and
Cost Cost per Holding Month 2
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
3 2 13 2 0.5 1 14 11
3 2 11 2 0.5 1 12 11
3 2 9 2 0.5 1 10 11
0 2 0 0 0.5 0 0 18
0 2 0 1 0.5 0.5 0.5 15
Variable
Set Up Holding Total
Cost/unit Production Ending Month 2 and
Cost Cost per Holding Month 1
produced Cost Inventory 4 Cost
(Dollars) Unit Cost
(Dollars)
0 2 0 -1 0.5 -0.5 -0.5 #N/A
3 2 5 0 0.5 0 5 25
3 2 7 1 0.5 0.5 7.5 23
3 2 9 2 0.5 1 10 21
3 2 11 3 0.5 1.5 12.5 18
3 2 13 4 0.5 2 15 15.5
0 2 0 0 0.5 0 0 25
3 2 5 1 0.5 0.5 5.5 23
3 2 7 2 0.5 1 8 21
3 2 9 3 0.5 1.5 10.5 18
3 2 11 4 0.5 2 13 15.5
3 2 13 5 0.5 2.5 15.5 #N/A
0 2 0 1 0.5 0.5 0.5 23
3 2 5 2 0.5 1 6 21
3 2 7 3 0.5 1.5 8.5 18
3 2 9 4 0.5 2 11 15.5
3 2 11 5 0.5 2.5 13.5 #N/A
3 2 13 6 0.5 3 16 #N/A
0 2 0 2 0.5 1 1 21
3 2 5 3 0.5 1.5 6.5 18
3 2 7 4 0.5 2 9 15.5
3 2 9 5 0.5 2.5 11.5 #N/A
3 2 11 6 0.5 3 14 #N/A
3 2 13 7 0.5 3.5 16.5 #N/A
0 2 0 3 0.5 1.5 1.5 18
3 2 5 4 0.5 2 7 15.5
3 2 7 5 0.5 2.5 9.5 #N/A
3 2 9 6 0.5 3 12 #N/A
3 2 11 7 0.5 3.5 14.5 #N/A
3 2 13 8 0.5 4 17 #N/A
Month 3
and 4
Cost
#N/A
#N/A
18
18.5
19
19.5
#N/A
16
16.5
17
17.5
15
11
14.5
15
15.5
13
#N/A
9.5
13
13.5
11
#N/A
#N/A
11.5
9
#N/A
#N/A
#N/A
Month 3
and 4
Cost
18
15
11
9.5
9
Month 2
to 4
Cost
#N/A
#N/A
#N/A
27
26.5
25
#N/A
#N/A
25
24.5
23
24
#N/A
23
22.5
21
22
24
18
20.5
19
20
22
#N/A
15.5
17
18
20
#N/A
#N/A
Month 2
to 4
Cost
25
23
21
18
15.5
Month 1
to 4
Cost
#N/A
30 This is the most optimal since given
30.5 in the problem, that there is no
31 beginning inventory.
30.5
30.5
25
28.5
29
28.5
28.5
#N/A
23.5
27
26.5
26.5
#N/A
#N/A
22
24.5
24.5
#N/A
#N/A
#N/A
19.5
22.5
#N/A
#N/A
#N/A
#N/A