{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Kapitel 1: Einführung in Operations Research — Vom Ursprung zur mathematischen Entscheidungsfindung\n", "\n", "Begleitnotebook zu *Optimierte Entscheidungsfindung mit Python*. Die Codezellen sind identisch mit den im Buch abgedruckten Programmen.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Einmalig ausfuehren: installiert alle im Buch verwendeten Pakete.\n", "# Lokal in einer virtuellen Umgebung genauso gueltig wie in Google Colab.\n", "%pip install --quiet ortools highspy cvxpy scipy numpy pandas polars \\\n", " scikit-learn matplotlib plotly pyomo linopy pymoo pydantic openpyxl" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Warum Ausprobieren scheitert — mit eigener Rechnung\n", "\n", "`Brute_Force_Vergleich.py`\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "# Brute_Force_Vergleich.py\n", "\"\"\"\n", "Kapitel Einfuehrung: Warum Ausprobieren scheitert.\n", "Vergleicht vollständige Enumeration mit einem Constraint-Solver an einem\n", "Zuordnungsproblem wachsender Größe (n Mitarbeiter auf n Aufgaben).\n", "\"\"\"\n", "\n", "import itertools\n", "import math\n", "import time\n", "\n", "import numpy as np\n", "from ortools.sat.python import cp_model\n", "\n", "\n", "def erzeuge_kostenmatrix(n: int, seed: int = 7) -> np.ndarray:\n", " \"\"\"Zufällige, aber reproduzierbare Kosten: Wer bearbeitet welche Aufgabe wie teuer?\"\"\"\n", " rng = np.random.default_rng(seed)\n", " return rng.integers(low=10, high=100, size=(n, n))\n", "\n", "\n", "def loese_brute_force(kosten: np.ndarray) -> tuple[float, tuple, int]:\n", " \"\"\"\n", " Probiert ALLE n! Zuordnungen durch und behält die beste.\n", " Rückgabe: (bester Kostenwert, beste Permutation, Anzahl geprüfter Kombinationen)\n", " \"\"\"\n", " n = len(kosten)\n", " bester_wert = math.inf\n", " beste_zuordnung = None\n", " geprueft = 0\n", "\n", " # itertools.permutations(range(n)) liefert nacheinander jede Reihenfolge\n", " for zuordnung in itertools.permutations(range(n)):\n", " # zuordnung[i] = Aufgabe, die Mitarbeiter i übernimmt\n", " wert = sum(kosten[i][zuordnung[i]] for i in range(n))\n", " geprueft += 1\n", " if wert < bester_wert:\n", " bester_wert = wert\n", " beste_zuordnung = zuordnung\n", "\n", " return bester_wert, beste_zuordnung, geprueft\n", "\n", "\n", "def loese_mit_solver(kosten: np.ndarray) -> tuple[float, tuple]:\n", " \"\"\"Dasselbe Problem als Constraint-Programm — der Solver probiert NICHT alles durch.\"\"\"\n", " n = len(kosten)\n", " modell = cp_model.CpModel()\n", "\n", " # x[i][j] = 1 <=> Mitarbeiter i übernimmt Aufgabe j\n", " x = [[modell.NewBoolVar(f\"x_{i}_{j}\") for j in range(n)] for i in range(n)]\n", "\n", " for i in range(n):\n", " modell.AddExactlyOne(x[i][j] for j in range(n)) # jeder genau eine Aufgabe\n", " for j in range(n):\n", " modell.AddExactlyOne(x[i][j] for i in range(n)) # jede Aufgabe genau einmal\n", "\n", " modell.Minimize(sum(int(kosten[i][j]) * x[i][j] for i in range(n) for j in range(n)))\n", "\n", " loeser = cp_model.CpSolver()\n", " loeser.parameters.max_time_in_seconds = 30.0\n", " status = loeser.Solve(modell)\n", " if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n", " raise RuntimeError(\"Solver fand keine Lösung.\")\n", "\n", " zuordnung = tuple(\n", " next(j for j in range(n) if loeser.Value(x[i][j]) == 1) for i in range(n)\n", " )\n", " return loeser.ObjectiveValue(), zuordnung\n", "\n", "\n", "if __name__ == \"__main__\":\n", " print(\"=\" * 72)\n", " print(\" VOLLSTÄNDIGES DURCHPROBIEREN vs. OPERATIONS RESEARCH\")\n", " print(\"=\" * 72)\n", " print(f\"{'n':>3} | {'Kombinationen':>18} | {'Brute Force':>14} | {'Solver':>10} | gleich?\")\n", " print(\"-\" * 72)\n", "\n", " for n in [4, 6, 8, 9, 10]: # n = 11 dauert bereits ~2 Minuten\n", " kosten = erzeuge_kostenmatrix(n)\n", "\n", " t0 = time.perf_counter()\n", " wert_bf, zuord_bf, geprueft = loese_brute_force(kosten)\n", " zeit_bf = time.perf_counter() - t0\n", "\n", " t0 = time.perf_counter()\n", " wert_or, zuord_or = loese_mit_solver(kosten)\n", " zeit_or = time.perf_counter() - t0\n", "\n", " gleich = \"ja\" if abs(wert_bf - wert_or) < 1e-9 else \"NEIN!\"\n", " print(f\"{n:>3} | {geprueft:>18,} | {zeit_bf:>11.4f} s | {zeit_or:>7.4f} s | {gleich}\")\n", "\n", " print(\"-\" * 72)\n", " # Hochrechnung: Wie lange bräuchte Brute Force bei n = 20?\n", " kombis_20 = math.factorial(20)\n", " # Messbasis: Prüfungen pro Sekunde aus dem letzten Lauf schätzen\n", " pro_sekunde = geprueft / max(zeit_bf, 1e-9)\n", " jahre = kombis_20 / pro_sekunde / (60 * 60 * 24 * 365.25)\n", " print(f\"Hochrechnung für n = 20: {kombis_20:,} Kombinationen\")\n", " print(f\"Bei gemessenen {pro_sekunde:,.0f} Prüfungen/s wären das {jahre:,.0f} Jahre.\")\n", " print(\"Der Solver löst dieselbe Instanz in Sekundenbruchteilen.\")\n", " print(\"=\" * 72)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Die Bausteine in der Praxis: eine Vorlage\n", "\n", "`Bausteine_Vorlage.py`\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "# Bausteine_Vorlage.py\n", "\"\"\"\n", "Kapitel Einfuehrung: Die Bausteine-Vorlage als ausfuellbares Python-Geruest.\n", "\n", "Uebersetzt die Vier-Bausteine-Vorlage aus dem Abschnitt 'Die vier\n", "universellen Bausteine jedes OR-Problems' direkt in Code: Wer sie\n", "auf Papier ausgefuellt hat, kann sie fast unveraendert in ein loesbares\n", "Modell umsetzen. Angewendet auf das Baeckerei-Beispiel der Handrechnung.\n", "\"\"\"\n", "\n", "from dataclasses import dataclass\n", "from ortools.sat.python import cp_model\n", "\n", "\n", "@dataclass\n", "class Bausteine:\n", " \"\"\"Die vier Bausteine jedes OR-Problems - wortwoertlich aus der Vorlage\n", " im Abschnitt 'Die vier universellen Bausteine' uebernommen.\"\"\"\n", " variablen: str\n", " parameter: str\n", " zielfunktion: str\n", " harte_bedingungen: str\n", " weiche_bedingungen: str\n", "\n", " def zeige(self) -> None:\n", " print(\"=\" * 78)\n", " print(\" AUSGEFUELLTE BAUSTEINE-VORLAGE\")\n", " print(\"=\" * 78)\n", " for feld, wert in [\n", " (\"Entscheidungsvariablen\", self.variablen),\n", " (\"Parameter\", self.parameter),\n", " (\"Zielfunktion\", self.zielfunktion),\n", " (\"Harte Bedingungen\", self.harte_bedingungen),\n", " (\"Weiche Bedingungen\", self.weiche_bedingungen),\n", " ]:\n", " print(f\"{feld:<24}: {wert}\")\n", " print(\"=\" * 78)\n", "\n", "\n", "# --- Baeckerei-Beispiel aus der Handrechnung ---------------------------------\n", "VORLAGE = Bausteine(\n", " variablen=\"x1 = Anzahl Brote, x2 = Anzahl Broetchen-Zehnerpackungen \"\n", " \"(beide ganzzahlig >= 0)\",\n", " parameter=\"Deckungsbeitraege (2,50; 3,00) EUR; Mehlbedarf (0,5; 0,6) kg; \"\n", " \"Ofenzeit (4; 3) min; Kapazitaeten (90 kg, 600 min); Mindestmenge 40 Brote\",\n", " zielfunktion=\"max 2,5*x1 + 3,0*x2 (Einheit: Euro Deckungsbeitrag)\",\n", " harte_bedingungen=\"0,5*x1 + 0,6*x2 <= 90 (Mehl); 4*x1 + 3*x2 <= 600 (Ofen); \"\n", " \"x1 >= 40 (Vertrag)\",\n", " weiche_bedingungen=\"keine\",\n", ")\n", "\n", "\n", "def loese_baeckerei():\n", " \"\"\"Baut aus der ausgefuellten Vorlage mechanisch ein CP-SAT-Modell.\"\"\"\n", " modell = cp_model.CpModel()\n", " x1 = modell.NewIntVar(40, 1000, \"Brote\") # Vertrag: mindestens 40\n", " x2 = modell.NewIntVar(0, 1000, \"Broetchen_Zehner\")\n", "\n", " modell.Add(5 * x1 + 6 * x2 <= 900) # Mehl, x10 fuer Ganzzahligkeit\n", " modell.Add(4 * x1 + 3 * x2 <= 600) # Ofenzeit\n", "\n", " modell.Maximize(25 * x1 + 30 * x2) # Deckungsbeitrag x10\n", "\n", " loeser = cp_model.CpSolver()\n", " status = loeser.Solve(modell)\n", " if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n", " raise SystemExit(f\"Keine Loesung: {loeser.StatusName(status)}\")\n", " return loeser.Value(x1), loeser.Value(x2), loeser.ObjectiveValue() / 10\n", "\n", "\n", "if __name__ == \"__main__\":\n", " VORLAGE.zeige()\n", "\n", " print(\"\\n--- Aus der Vorlage mechanisch abgeleitetes Modell ---\")\n", " brote, broetchen, gewinn = loese_baeckerei()\n", " print(f\"Optimale Brote: {brote}\")\n", " print(f\"Optimale Broetchen-Zehner: {broetchen}\")\n", " print(f\"Maximaler Deckungsbeitrag: {gewinn:.2f} EUR\")\n", " print()\n", " print(\"Genau diese drei Codezeilen (Variablen, Add, Maximize) entstehen\")\n", " print(\"direkt aus den fuenf Zeilen der Vorlage - das ist der ganze Trick.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Umsetzung mit Google OR-Tools\n", "\n", "`Bot_Allokation.py`\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "# Bot_Allokation.py\n", "\"\"\"\n", "Kapitel Einfuehrung: Erstes Optimierungsmodell mit Google OR-Tools (CP-SAT).\n", "Problem: Server-Allokation für Trading-Bots.\n", "\n", "Modell mit expliziter Nebenbedingung statt versteckter Variablengrenze,\n", "vollständiger Statusauswertung und Ergebnisprüfung.\n", "\"\"\"\n", "\n", "from ortools.sat.python import cp_model\n", "\n", "# --- Parameter (die \"Fakten\" des Problems) ---------------------------------\n", "GEWINN_A, GEWINN_B = 150, 250 # Euro pro Bot und Tag\n", "CPU_A, CPU_B = 2, 5 # vCPU-Bedarf je Bot\n", "RAM_A, RAM_B = 4, 6 # GB Arbeitsspeicher je Bot\n", "CPU_GESAMT, RAM_GESAMT = 40, 60 # verfügbare Kapazitäten\n", "MAX_ARBITRAGE = 8 # Marktliquiditätsgrenze\n", "\n", "\n", "def loese_bot_allokation(zeitlimit_s: float = 10.0):\n", " \"\"\"Baut das Modell, löst es und gibt eine Auswertung aus.\"\"\"\n", "\n", " # 1. Modell instanziieren\n", " modell = cp_model.CpModel()\n", "\n", " # 2. Entscheidungsvariablen anlegen\n", " # NewIntVar(untere_grenze, obere_grenze, name)\n", " # Die obere Grenze ist bewusst großzügig; die echte Beschränkung\n", " # formulieren wir unten als Nebenbedingung, damit das Modell die\n", " # mathematische Formulierung 1:1 abbildet.\n", " x_a = modell.NewIntVar(0, 100, \"Arbitrage_Bots\")\n", " x_b = modell.NewIntVar(0, 100, \"Trend_Bots\")\n", "\n", " # 3. Nebenbedingungen definieren\n", " c_cpu = modell.Add(CPU_A * x_a + CPU_B * x_b <= CPU_GESAMT) # vCPU-Limit\n", " c_ram = modell.Add(RAM_A * x_a + RAM_B * x_b <= RAM_GESAMT) # RAM-Limit\n", " c_liq = modell.Add(x_a <= MAX_ARBITRAGE) # Marktliquidität\n", "\n", " # 4. Zielfunktion: Maximiere den Tagesgewinn\n", " modell.Maximize(GEWINN_A * x_a + GEWINN_B * x_b)\n", "\n", " # 5. Solver konfigurieren und ausführen\n", " loeser = cp_model.CpSolver()\n", " loeser.parameters.max_time_in_seconds = zeitlimit_s\n", " status = loeser.Solve(modell)\n", "\n", " # 6. Status auswerten -- IMMER alle Fälle behandeln\n", " status_text = loeser.StatusName(status)\n", " if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n", " print(f\"Keine verwertbare Lösung. Solver-Status: {status_text}\")\n", " if status == cp_model.INFEASIBLE:\n", " print(\"Das Modell ist unlösbar - die Bedingungen widersprechen sich.\")\n", " return None\n", "\n", " a, b = loeser.Value(x_a), loeser.Value(x_b)\n", " gewinn = loeser.ObjectiveValue()\n", "\n", " # 7. Ergebnis ausgeben\n", " print(\"=\" * 58)\n", " print(\" OPTIMALE BOT-ALLOKATION\")\n", " print(\"=\" * 58)\n", " print(f\"Solver-Status: {status_text}\"\n", " f\"{' (beweisbar optimal)' if status == cp_model.OPTIMAL else ' (zulässig, nicht bewiesen)'}\")\n", " print(f\"Arbitrage-Bots (x_A): {a} Instanzen\")\n", " print(f\"Trendfolge-Bots (x_B): {b} Instanzen\")\n", " print(f\"Täglicher Max-Gewinn: {gewinn:,.2f} EUR\")\n", "\n", " genutzt_cpu = CPU_A * a + CPU_B * b\n", " genutzt_ram = RAM_A * a + RAM_B * b\n", " print(\"-\" * 58)\n", " print(f\"CPU-Auslastung: {genutzt_cpu} / {CPU_GESAMT} vCPUs \"\n", " f\"({genutzt_cpu / CPU_GESAMT * 100:.1f} %)\")\n", " print(f\"RAM-Auslastung: {genutzt_ram} / {RAM_GESAMT} GB \"\n", " f\"({genutzt_ram / RAM_GESAMT * 100:.1f} %)\")\n", " print(f\"Arbitrage-Limit: {a} / {MAX_ARBITRAGE}\")\n", "\n", " # 8. Selbstkontrolle: Sind wirklich alle Bedingungen eingehalten?\n", " assert genutzt_cpu <= CPU_GESAMT, \"vCPU-Limit verletzt!\"\n", " assert genutzt_ram <= RAM_GESAMT, \"RAM-Limit verletzt!\"\n", " assert a <= MAX_ARBITRAGE, \"Arbitrage-Limit verletzt!\"\n", "\n", " # 9. Zum Vergleich: die naive Strategie \"nur der lukrativere Bot\"\n", " naiv_b = min(CPU_GESAMT // CPU_B, RAM_GESAMT // RAM_B)\n", " naiv_gewinn = GEWINN_B * naiv_b\n", " print(\"-\" * 58)\n", " print(f\"Naive Strategie (nur Trendfolge): {naiv_b} Bots -> {naiv_gewinn:,.2f} EUR\")\n", " print(f\"Vorteil der Optimierung: {gewinn - naiv_gewinn:,.2f} EUR pro Tag \"\n", " f\"({(gewinn / naiv_gewinn - 1) * 100:.1f} %)\")\n", " print(\"=\" * 58)\n", " return a, b, gewinn\n", "\n", "\n", "if __name__ == \"__main__\":\n", " loese_bot_allokation()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Von Excel zu Python: Ihre Daten liegen schon da\n", "\n", "`Excel_Bruecke.py`\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "# Excel_Bruecke.py\n", "\"\"\"\n", "Kapitel Einfuehrung: Vom Excel-Solver zu Python - dieselbe Rechnung, dieselbe Datei.\n", "\n", "Das Programm bildet den vollstaendigen Arbeitsweg ab, den ein Excel-Modell im\n", "Betrieb sonst von Hand geht:\n", "\n", " Tabellenblatt lesen -> Modell bauen -> loesen -> Ergebnis zurueckschreiben\n", "\n", "Damit es ohne Vorbereitung laeuft, legt es die Eingabedatei beim ersten Start\n", "selbst an. Ersetzen Sie sie durch Ihre eigene Datei - solange die Spalten\n", "gleich heissen, aendert sich am Code nichts.\n", "\n", "Die vier Arbeitsschritte kommen aus or_kern.py (Kapitel Praxisfallen). Was\n", "hier steht, ist nur noch das, was diesen Fall ausmacht - der Rest ist\n", "gemeinsamer Unterbau. Wer das Modul nicht kennt: Es ist im Buch vollstaendig\n", "abgedruckt und liegt im selben Verzeichnis.\n", "\n", "Erzeugte Dateien (im Arbeitsverzeichnis):\n", " produktionsmix.xlsx Eingabe: Blaetter 'Produkte' und 'Kapazitaeten'\n", " produktionsmix_ergebnis.xlsx Ausgabe: Blaetter 'Plan' und 'Kennzahlen'\n", "\n", "Benoetigt: pandas, openpyxl, ortools, pydantic (ueber or_kern)\n", "\"\"\"\n", "\n", "from __future__ import annotations\n", "\n", "import os\n", "\n", "import pandas as pd\n", "\n", "from or_kern import (lade_produktionsproblem, loese_mit_glop, pruefe_loesung,\n", " schreibe_ergebnis)\n", "\n", "# Die Mappen liegen NEBEN diesem Programm, nicht im aktuellen\n", "# Arbeitsverzeichnis. Sonst haengt es davon ab, aus welchem Ordner man das\n", "# Skript startet, wo die Dateien landen - und wer es aus der\n", "# Repository-Wurzel aufruft, verstreut sie dort.\n", "HIER = os.path.dirname(os.path.abspath(__file__))\n", "EINGABE = os.path.join(HIER, \"produktionsmix.xlsx\")\n", "AUSGABE = os.path.join(HIER, \"produktionsmix_ergebnis.xlsx\")\n", "\n", "\n", "def lege_beispieldatei_an(pfad: str) -> None:\n", " \"\"\"Schreibt die Eingabemappe, wie sie auch aus dem Controlling kaeme.\"\"\"\n", " produkte = pd.DataFrame({\n", " \"Produkt\": [\"Tisch\", \"Stuhl\", \"Regal\"],\n", " \"Deckungsbeitrag\": [240.0, 60.0, 130.0],\n", " \"Montagestunden\": [3.0, 1.0, 2.0],\n", " \"Plattenmaterial\": [6.0, 1.0, 4.0],\n", " })\n", " kapazitaeten = pd.DataFrame({\n", " \"Ressource\": [\"Montagestunden\", \"Plattenmaterial\"],\n", " \"Verfuegbar\": [150.0, 240.0],\n", " })\n", " with pd.ExcelWriter(pfad, engine=\"openpyxl\") as mappe:\n", " produkte.to_excel(mappe, sheet_name=\"Produkte\", index=False)\n", " kapazitaeten.to_excel(mappe, sheet_name=\"Kapazitaeten\", index=False)\n", "\n", "\n", "if __name__ == \"__main__\":\n", " if not os.path.exists(EINGABE):\n", " lege_beispieldatei_an(EINGABE)\n", " print(f\"Beispiel-Eingabedatei angelegt: {EINGABE}\")\n", "\n", " # 1. Lesen und pruefen. Faellt hier etwas auf, ist der Fehler noch\n", " # zuzuordnen - spaeter waere er nur noch eine merkwuerdige Zahl.\n", " problem = lade_produktionsproblem(EINGABE)\n", "\n", " # 2. Loesen. Einzige solverabhaengige Zeile des ganzen Programms -\n", " # 'loese_mit_scipy' waere ein Einzeiler-Wechsel.\n", " loesung = loese_mit_glop(problem)\n", "\n", " # 3. Abnahmepruefung gegen die Anforderungen, ohne den Solver zu fragen.\n", " beanstandungen = pruefe_loesung(problem, loesung)\n", " if beanstandungen:\n", " raise SystemExit(\"Abnahmepruefung fehlgeschlagen:\\n - \"\n", " + \"\\n - \".join(beanstandungen))\n", "\n", " # 4. Zurueckschreiben - im Format, das die Fachabteilung ohnehin benutzt.\n", " schreibe_ergebnis(AUSGABE, problem, loesung)\n", "\n", " print(\"=\" * 66)\n", " print(\" PRODUKTIONSPLAN AUS DER EXCEL-MAPPE\")\n", " print(\"=\" * 66)\n", " for produkt in problem.produkte:\n", " menge = loesung.werte[produkt.name]\n", " print(f\"{produkt.name:<18} {menge:8.1f} Stueck \"\n", " f\"{menge * produkt.deckungsbeitrag:12,.2f} EUR\")\n", " print(\"-\" * 66)\n", " print(loesung.als_bericht())\n", " print(\"Abnahmepruefung: bestanden\\n\")\n", "\n", " # Die Schattenpreise beantworten die Frage, die der Plan nicht stellt:\n", " # Was waere eine zusaetzliche Einheit dieser Ressource wert?\n", " for ressource, preis in loesung.schattenpreise.items():\n", " print(f\" eine Einheit {ressource:<18} mehr waere wert: {preis:7.2f} EUR\")\n", " print(\"=\" * 66)\n", " print(f\"Ergebnis geschrieben nach: {AUSGABE}\")" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.11" } }, "nbformat": 4, "nbformat_minor": 5 }