100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Eerder door jou gezocht
Eerder door jou gezocht
logo
Samenvatting Dynamic Programming Models €2,99
In winkelwagen
Snel navigeren naar
Voorbeeld
  2.  
  3. Universiteit Twente (UT)
  4.  
  5. (202000450)

Samenvatting

Samenvatting Dynamic Programming Models

 13 keer bekeken  0 keer verkocht

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

Voorbeeld 2 van de 10  pagina's

Document informatie

  • Onbekend
  • 2 november 2023
  • 10
  • 2023/2024
  • Samenvatting

Onderwerpen

Gekoppeld boek

book image

Titel boek:

Auteur(s):

  • Uitgave:
  • ISBN:
  • Druk:

Meer samenvattingen voor studieboek

Alles voor dit studieboek (12)

Geschreven voor

Verkoper

avatar-seller
julian19

Voorbeeld van de inhoud

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

Voordelen van het kopen van samenvattingen bij Stuvia op een rij:

Verzekerd van kwaliteit door reviews

Verzekerd van kwaliteit door reviews

Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!

Snel en makkelijk kopen

Snel en makkelijk kopen

Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.

Focus op de essentie

Focus op de essentie

Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper julian19. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 52355 samenvattingen verkocht

Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen

Start met verkopen
€2,99
  • (0)
In winkelwagen
Toegevoegd