Uitleg aan de hand van veel voorbeelden!
Onderwerpen die behandeld zijn:
- Network Problem
- Characteristics of DP Applications
- Production Inventory Problems
- Resource Allocation Problems
- Wagner-Whitin Method
- Silver-Meal Heuristic
- Equipment Replacement Problem
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller julian19. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.25. You're not tied to anything after your purchase.
