85 lines
3.1 KiB
Python
85 lines
3.1 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
# Bellman_Minimalbeispiel.py
|
||
|
|
"""
|
||
|
|
Kapitel Dynamische Programmierung: Die Handrechnung zur Rueckwaertsinduktion als Code.
|
||
|
|
Zeigt die Wertfunktionstabelle und die optimale Politik Schritt fuer Schritt.
|
||
|
|
"""
|
||
|
|
|
||
|
|
import numpy as np
|
||
|
|
|
||
|
|
GESAMT = 3 # zu verkaufende Einheiten
|
||
|
|
PERIODEN = 2 # Anzahl Verkaufsperioden
|
||
|
|
|
||
|
|
|
||
|
|
def kosten(menge: int) -> float:
|
||
|
|
"""Ueberproportionale Marktauswirkung: doppelte Menge kostet vierfach."""
|
||
|
|
return float(menge ** 2)
|
||
|
|
|
||
|
|
|
||
|
|
def loese_rueckwaerts():
|
||
|
|
# V[t, x] = minimale Restkosten, wenn zu Beginn von Periode t noch x Stueck offen sind
|
||
|
|
V = np.full((PERIODEN + 1, GESAMT + 1), np.inf)
|
||
|
|
politik = np.zeros((PERIODEN, GESAMT + 1), dtype=int)
|
||
|
|
|
||
|
|
# Endbedingung: nach der letzten Periode darf nichts mehr offen sein
|
||
|
|
V[PERIODEN, 0] = 0.0
|
||
|
|
|
||
|
|
print("=" * 70)
|
||
|
|
print(" RUECKWAERTSINDUKTION SCHRITT FUER SCHRITT")
|
||
|
|
print("=" * 70)
|
||
|
|
|
||
|
|
for t in range(PERIODEN - 1, -1, -1):
|
||
|
|
letzte_periode = (t == PERIODEN - 1)
|
||
|
|
print(f"\nStufe t = {t}" + (" (letzte Periode: alles muss weg)" if letzte_periode
|
||
|
|
else " (freie Wahl der Menge)"))
|
||
|
|
print(f" {'Zustand x':>10} | {'beste Aktion':>12} | {'Sofortkosten':>13} | "
|
||
|
|
f"{'V[t+1]':>9} | {'V[t]':>8}")
|
||
|
|
print(" " + "-" * 62)
|
||
|
|
|
||
|
|
for x in range(GESAMT + 1):
|
||
|
|
aktionen = [x] if letzte_periode else range(x + 1)
|
||
|
|
bester_wert, beste_aktion, beste_teile = np.inf, 0, (0.0, 0.0)
|
||
|
|
|
||
|
|
for n in aktionen:
|
||
|
|
rest = x - n
|
||
|
|
sofort = kosten(n)
|
||
|
|
zukunft = V[t + 1, rest]
|
||
|
|
gesamt = sofort + zukunft
|
||
|
|
if gesamt < bester_wert:
|
||
|
|
bester_wert, beste_aktion = gesamt, n
|
||
|
|
beste_teile = (sofort, zukunft)
|
||
|
|
|
||
|
|
V[t, x] = bester_wert
|
||
|
|
politik[t, x] = beste_aktion
|
||
|
|
print(f" {x:>10} | {beste_aktion:>12} | {beste_teile[0]:>13.1f} | "
|
||
|
|
f"{beste_teile[1]:>9.1f} | {bester_wert:>8.1f}")
|
||
|
|
|
||
|
|
return V, politik
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
V, politik = loese_rueckwaerts()
|
||
|
|
|
||
|
|
# --- Vorwaertspfad: der optimalen Politik folgen ---------------------
|
||
|
|
print("\n" + "=" * 70)
|
||
|
|
print(" OPTIMALER PFAD (Vorwaertssimulation)")
|
||
|
|
print("=" * 70)
|
||
|
|
bestand = GESAMT
|
||
|
|
gesamtkosten = 0.0
|
||
|
|
for t in range(PERIODEN):
|
||
|
|
aktion = politik[t, bestand]
|
||
|
|
gesamtkosten += kosten(aktion)
|
||
|
|
print(f" Periode {t}: Bestand {bestand} -> verkaufe {aktion} "
|
||
|
|
f"(Kosten {kosten(aktion):.1f}) -> Rest {bestand - aktion}")
|
||
|
|
bestand -= aktion
|
||
|
|
|
||
|
|
print(f"\n Gesamtkosten: {gesamtkosten:.1f} (V[0, {GESAMT}] = {V[0, GESAMT]:.1f})")
|
||
|
|
assert abs(gesamtkosten - V[0, GESAMT]) < 1e-9, "Pfadkosten != Wertfunktion!"
|
||
|
|
|
||
|
|
# --- Vergleich mit naiven Strategien ---------------------------------
|
||
|
|
alles_sofort = kosten(GESAMT)
|
||
|
|
print(f"\n Zum Vergleich - alles in Periode 0 verkaufen: {alles_sofort:.1f}")
|
||
|
|
print(f" Ersparnis durch Stueckelung: {alles_sofort - gesamtkosten:.1f} "
|
||
|
|
f"({(1 - gesamtkosten/alles_sofort)*100:.0f} %)")
|
||
|
|
print("=" * 70)
|