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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur julian19. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €2,99. Vous n'êtes lié à rien après votre achat.
