Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
LECTURE 5 – DP MODELS
EXAMPLE 10 – NETW ORK PROBLEM (P.964)
Determine the shortest path from NY(1)
to LA(10)
𝐶𝑜𝑠𝑡𝑠 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑐 𝑓𝑟𝑜𝑚 𝑐𝑖𝑡𝑦 𝑖
𝑡𝑜 𝑐𝑖𝑡𝑦 𝑗
Apply backward recursion
o 𝑓 (𝑖) = 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡
𝑝𝑎𝑡ℎ 𝑓𝑟𝑜𝑚 𝑖 𝑡𝑜 10 𝑤ℎ𝑒𝑛
𝑦𝑜𝑢 𝑎𝑟𝑒 𝑖𝑛 𝑖 𝑎𝑡 𝑡ℎ𝑒 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔
𝑜𝑓 𝑑𝑎𝑦 𝑡
𝑓 (8) = 1030
𝑓 (9) = 1390
𝑓 (5) = min{𝑐 + 𝑓 (8), 𝑐 + 𝑓 (9)} = min{610 + 1030∗ , 790 + 1390} = 1640
𝑓 (7) = min{𝑐 + 𝑓 (8), 𝑐 + 𝑓 (9)} = min{790 + 1030, 270 + 1390∗ } = 1660
Cost function
o 𝑓 (𝑖) = min{𝑟 (𝑖, 𝑑) + 𝑓 (𝑖, 𝑑)}
o 𝑛 = 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔 𝑑𝑎𝑦 𝑛
o 𝑖 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛
o 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑑 = 𝑛𝑒𝑥𝑡 𝑐𝑖𝑡𝑦
𝑓 (𝑖) = min{(𝑐𝑜𝑠𝑡 𝑑𝑢𝑟𝑖𝑛𝑔 𝑠𝑡𝑎𝑔𝑒 𝑡) + 𝑓 (𝑛𝑒𝑤 𝑠𝑡𝑎𝑡𝑒 𝑎𝑡 𝑠𝑡𝑎𝑔𝑒 𝑡 + 1)}
CHARACTERISTICS OF DP-APPLICATIONS
1. The problem can be divided into stages with a decision required at each stage t = 1, …, T
2. Each stage has a number of states associated with it
o State is the information needed to make the optimal decision
3. The decision chosen at any stage describes how the state at the current stage is transformed into
the state at the next stage
4. Given the current state, the optimal decision for each of the remaining stages must not depend on
the previously reached states or previously chosen decisions
o Principle of optimality
5. If the states for the problem have been classified into one of T stages, there must be a recursion
that relates the cost or reward earned during stages t, t+1, …, T to the cost or reward earned during
stages t+1, t+2, …, T.
18
, Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
EXAMPLE 11 – FISHE RY EXAMPLE (P.990)
The owner of a lake must decide how many bass to catch and sell each year
If he sells x bass during year t, then a revenue r(x) is earned
The cost of catching x bass during a year is a function of c(x, b) of the number of bass caught during
the year and of b, the number of bass in the lake at the beginning of the year.
o Number of bass in the lake at the beginning of the year is 20% more than the bass left at the
end of previous year
o 10000 bass are in the lake at beginning of first year
o Maximize owners profit over a T-year horizon
Stages (decision required at each stage)
o The beginning of year t
States (information needed to make decision)
o Number of fish at the beginning of each year: 𝑏
Decisions
o 𝑥 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑏𝑎𝑠𝑠 𝑡𝑜 𝑐𝑎𝑡𝑐ℎ 𝑑𝑢𝑟𝑖𝑛𝑔 𝑦𝑒𝑎𝑟 𝑡
Optimal value function
o 𝑓 (𝑏 )
o For all t, 0 ≤ 𝑥 ≤ 𝑏
o Net profit: 𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 )
o State in year t+1: 1.2(𝑏 − 𝑥 )
Recursion
o After year T:
𝑓 (𝑏 ) = max{𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 )}
With 0 ≤ 𝑥 ≤ 𝑏
o For other stages:
𝑓 (𝑏 ) = max{𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 ) + 𝑓 [1.2(𝑏 − 𝑥 )]}
With 0 ≤ 𝑥 ≤ 𝑏
19
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
LECTURE 5 – DP MODELS
EXAMPLE 10 – NETW ORK PROBLEM (P.964)
Determine the shortest path from NY(1)
to LA(10)
𝐶𝑜𝑠𝑡𝑠 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑐 𝑓𝑟𝑜𝑚 𝑐𝑖𝑡𝑦 𝑖
𝑡𝑜 𝑐𝑖𝑡𝑦 𝑗
Apply backward recursion
o 𝑓 (𝑖) = 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑠ℎ𝑜𝑟𝑡𝑒𝑠𝑡
𝑝𝑎𝑡ℎ 𝑓𝑟𝑜𝑚 𝑖 𝑡𝑜 10 𝑤ℎ𝑒𝑛
𝑦𝑜𝑢 𝑎𝑟𝑒 𝑖𝑛 𝑖 𝑎𝑡 𝑡ℎ𝑒 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔
𝑜𝑓 𝑑𝑎𝑦 𝑡
𝑓 (8) = 1030
𝑓 (9) = 1390
𝑓 (5) = min{𝑐 + 𝑓 (8), 𝑐 + 𝑓 (9)} = min{610 + 1030∗ , 790 + 1390} = 1640
𝑓 (7) = min{𝑐 + 𝑓 (8), 𝑐 + 𝑓 (9)} = min{790 + 1030, 270 + 1390∗ } = 1660
Cost function
o 𝑓 (𝑖) = min{𝑟 (𝑖, 𝑑) + 𝑓 (𝑖, 𝑑)}
o 𝑛 = 𝑏𝑒𝑔𝑖𝑛𝑛𝑖𝑛𝑔 𝑑𝑎𝑦 𝑛
o 𝑖 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛
o 𝑑𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑑 = 𝑛𝑒𝑥𝑡 𝑐𝑖𝑡𝑦
𝑓 (𝑖) = min{(𝑐𝑜𝑠𝑡 𝑑𝑢𝑟𝑖𝑛𝑔 𝑠𝑡𝑎𝑔𝑒 𝑡) + 𝑓 (𝑛𝑒𝑤 𝑠𝑡𝑎𝑡𝑒 𝑎𝑡 𝑠𝑡𝑎𝑔𝑒 𝑡 + 1)}
CHARACTERISTICS OF DP-APPLICATIONS
1. The problem can be divided into stages with a decision required at each stage t = 1, …, T
2. Each stage has a number of states associated with it
o State is the information needed to make the optimal decision
3. The decision chosen at any stage describes how the state at the current stage is transformed into
the state at the next stage
4. Given the current state, the optimal decision for each of the remaining stages must not depend on
the previously reached states or previously chosen decisions
o Principle of optimality
5. If the states for the problem have been classified into one of T stages, there must be a recursion
that relates the cost or reward earned during stages t, t+1, …, T to the cost or reward earned during
stages t+1, t+2, …, T.
18
, Julian Klep
OR Models for Pre-Master IEM
Winston Ch. 1, 3, 9, 15, 16, 18, 20
EXAMPLE 11 – FISHE RY EXAMPLE (P.990)
The owner of a lake must decide how many bass to catch and sell each year
If he sells x bass during year t, then a revenue r(x) is earned
The cost of catching x bass during a year is a function of c(x, b) of the number of bass caught during
the year and of b, the number of bass in the lake at the beginning of the year.
o Number of bass in the lake at the beginning of the year is 20% more than the bass left at the
end of previous year
o 10000 bass are in the lake at beginning of first year
o Maximize owners profit over a T-year horizon
Stages (decision required at each stage)
o The beginning of year t
States (information needed to make decision)
o Number of fish at the beginning of each year: 𝑏
Decisions
o 𝑥 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑏𝑎𝑠𝑠 𝑡𝑜 𝑐𝑎𝑡𝑐ℎ 𝑑𝑢𝑟𝑖𝑛𝑔 𝑦𝑒𝑎𝑟 𝑡
Optimal value function
o 𝑓 (𝑏 )
o For all t, 0 ≤ 𝑥 ≤ 𝑏
o Net profit: 𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 )
o State in year t+1: 1.2(𝑏 − 𝑥 )
Recursion
o After year T:
𝑓 (𝑏 ) = max{𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 )}
With 0 ≤ 𝑥 ≤ 𝑏
o For other stages:
𝑓 (𝑏 ) = max{𝑟(𝑥 ) − 𝑐(𝑥 , 𝑏 ) + 𝑓 [1.2(𝑏 − 𝑥 )]}
With 0 ≤ 𝑥 ≤ 𝑏
19
