{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Anhang C: Fehlerdiagnose-Handbuch\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": [ "## Wenn die fünf Schritte nicht reichen: den Konflikt einkreisen\n", "\n", "`Konfliktsuche.py`\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#!/usr/bin/env python3\n", "\n", "# Konfliktsuche.py\n", "\"\"\"\n", "Anhang Fehlerdiagnose: Den Konflikt finden, der INFEASIBLE verursacht.\n", "\n", "Ein Deletion Filter (auch: IIS, Irreducible Infeasible Subset) isoliert aus\n", "einem unloesbaren Modell eine kleinste widerspruechliche Teilmenge von\n", "Bedingungen: Nimmt man aus ihr auch nur eine einzige Bedingung heraus, ist\n", "der Rest wieder loesbar.\n", "\n", "Das Programm zeigt sechs Dinge:\n", " 1. Der Solver meldet INFEASIBLE - und sonst nichts.\n", " 2. Die naive Suche (\"jede Bedingung einmal weglassen\") findet hier gar nichts.\n", " 3. Der Deletion Filter findet einen Konflikt in n Solveraufrufen.\n", " 4. Ein Konflikt ist selten einer: nach der Reparatur folgt der naechste.\n", " 5. \"Den\" kleinsten Konflikt gibt es nicht - dieses Modell enthaelt neun.\n", " 6. Welchen davon man zu sehen bekommt, steuert die Pruefreihenfolge.\n", "\n", "Abgrenzung zu Infeasibility_Diagnose.py (Kapitel Praxisfallen): Dort geht es\n", "um die Relaxation - das Modell soll trotz Widerspruch eine brauchbare Antwort\n", "liefern. Hier geht es um die Diagnose - welche Bedingungen widersprechen sich\n", "ueberhaupt. Beides zusammen ergibt den Umgang mit INFEASIBLE in Produktion.\n", "\n", "Benoetigt: numpy, scipy\n", "\"\"\"\n", "\n", "from __future__ import annotations\n", "\n", "import numpy as np\n", "from scipy.optimize import linprog\n", "\n", "PRODUKTE = [\"Rahmen\", \"Gehaeuse\", \"Deckel\", \"Traeger\", \"Halter\"]\n", "\n", "# Jede Bedingung traegt einen sprechenden Namen - das ist keine Kosmetik,\n", "# sondern die Voraussetzung dafuer, dass der Befund lesbar wird.\n", "# (Name, Koeffizienten je Produkt, Richtung, rechte Seite)\n", "BEDINGUNGEN: list[tuple[str, list[float], str, float]] = [\n", " (\"Kapazitaet Montage\", [3, 2, 1, 4, 2], \"<=\", 400),\n", " (\"Kapazitaet Lackieren\", [2, 3, 0, 1, 0], \"<=\", 150),\n", " (\"Kapazitaet Pruefung\", [1, 1, 1, 1, 1], \"<=\", 300),\n", " (\"Liefervertrag Rahmen\", [1, 0, 0, 0, 0], \">=\", 40),\n", " (\"Liefervertrag Gehaeuse\", [0, 1, 0, 0, 0], \">=\", 30),\n", " (\"Liefervertrag Deckel\", [0, 0, 1, 0, 0], \">=\", 20),\n", " (\"Liefervertrag Traeger\", [0, 0, 0, 1, 0], \">=\", 25),\n", " (\"Marktgrenze Rahmen\", [1, 0, 0, 0, 0], \"<=\", 120),\n", " (\"Marktgrenze Gehaeuse\", [0, 1, 0, 0, 0], \"<=\", 90),\n", " (\"Marktgrenze Deckel\", [0, 0, 1, 0, 0], \"<=\", 150),\n", " (\"Marktgrenze Halter\", [0, 0, 0, 0, 1], \"<=\", 200),\n", " (\"Mindestumsatz\", [90, 70, 30, 60, 20], \">=\", 12000),\n", " (\"Sortimentsbreite\", [0, 0, 1, 1, 1], \">=\", 100),\n", " (\"Lackierbudget Schicht 2\", [0, 1, 0, 1, 0], \"<=\", 55),\n", "]\n", "\n", "# Welche Bedingungen koennte ein Planer im Ernstfall wirklich veraendern?\n", "# Kapazitaeten lassen sich durch Sonderschichten dehnen, Liefervertraege und\n", "# Marktgrenzen nicht.\n", "VERHANDELBAR = {\"Kapazitaet Montage\", \"Kapazitaet Lackieren\",\n", " \"Kapazitaet Pruefung\", \"Lackierbudget Schicht 2\"}\n", "\n", "aufrufe = 0 # zaehlt jeden Solveraufruf mit - der Preis des Verfahrens\n", "\n", "\n", "def ist_loesbar(auswahl: list[int]) -> bool:\n", " \"\"\"Gibt es einen Punkt, der ALLE Bedingungen aus 'auswahl' erfuellt?\n", "\n", " Es wird nur Zulaessigkeit geprueft, keine Zielfunktion optimiert: die\n", " Zielfunktion ist konstant null. INFEASIBLE haengt nie an der Zielfunktion.\n", " \"\"\"\n", " global aufrufe\n", " aufrufe += 1\n", " matrix, rechte_seite = [], []\n", " for i in auswahl:\n", " _, koeffizienten, richtung, grenze = BEDINGUNGEN[i]\n", " zeile = np.array(koeffizienten, dtype=float)\n", " # linprog kennt nur \"<=\", also \">=\" durch Negation umdrehen\n", " matrix.append(zeile if richtung == \"<=\" else -zeile)\n", " rechte_seite.append(grenze if richtung == \"<=\" else -grenze)\n", " ergebnis = linprog(np.zeros(len(PRODUKTE)),\n", " A_ub=np.array(matrix), b_ub=np.array(rechte_seite),\n", " bounds=(0, None), method=\"highs\")\n", " return ergebnis.status == 0\n", "\n", "\n", "def deletion_filter(auswahl: list[int]) -> list[int]:\n", " \"\"\"Verkleinert eine unloesbare Menge zu einer kleinsten unloesbaren Menge.\n", "\n", " Der Kern des Verfahrens ist eine einzige Regel: Nimm eine Bedingung\n", " versuchsweise heraus. Bleibt der Rest unloesbar, wurde sie fuer den\n", " Widerspruch nicht gebraucht - sie darf endgueltig weg. Wird der Rest\n", " loesbar, war sie beteiligt und muss bleiben.\n", "\n", " Nach genau einem Durchlauf ueber alle Bedingungen ist das Ergebnis\n", " unreduzierbar: n Solveraufrufe statt 2^n Teilmengen.\n", " \"\"\"\n", " rest = list(auswahl)\n", " for i in list(auswahl):\n", " probe = [j for j in rest if j != i]\n", " if not ist_loesbar(probe):\n", " rest = probe\n", " return rest\n", "\n", "\n", "def namen(auswahl: list[int]) -> list[str]:\n", " return [BEDINGUNGEN[i][0] for i in auswahl]\n", "\n", "\n", "def teil_1_der_befund(alle: list[int]) -> None:\n", " print(\"=\" * 68)\n", " print(\"1. Was der Solver sagt\")\n", " print(\"=\" * 68)\n", " print(f\"Modell: {len(PRODUKTE)} Variablen, {len(BEDINGUNGEN)} Bedingungen\")\n", " status = \"OPTIMAL\" if ist_loesbar(alle) else \"INFEASIBLE\"\n", " print(f\"Status: {status}\")\n", " print(\"\\nMehr ist es nicht. Der Solver nennt keine Ursache, weil es die eine\")\n", " print(\"Ursache nicht gibt: Unloesbarkeit ist eine Eigenschaft von Mengen von\")\n", " print(\"Bedingungen, nicht von einzelnen Bedingungen.\")\n", "\n", "\n", "def teil_2_die_naive_suche(alle: list[int]) -> None:\n", " print(\"\\n\" + \"=\" * 68)\n", " print(\"2. Die naheliegende Idee - und warum sie hier scheitert\")\n", " print(\"=\" * 68)\n", " print(\"Jede Bedingung einmal weglassen und schauen, ob es dann geht:\\n\")\n", " treffer = [i for i in alle if ist_loesbar([j for j in alle if j != i])]\n", " for i in alle:\n", " print(f\" ohne {BEDINGUNGEN[i][0]:<26} {'loesbar' if i in treffer else 'weiter unloesbar'}\")\n", " print(f\"\\nGefundene Schuldige: {len(treffer)}\")\n", " print(\"Keine einzelne Bedingung ist schuld. Genau das ist der Normalfall -\")\n", " print(\"und der Grund, warum diese Suche in der Praxis so oft im Nichts endet.\")\n", "\n", "\n", "def teil_3_der_filter(alle: list[int]) -> list[int]:\n", " global aufrufe\n", " print(\"\\n\" + \"=\" * 68)\n", " print(\"3. Der Deletion Filter\")\n", " print(\"=\" * 68)\n", " vorher = aufrufe\n", " konflikt = deletion_filter(alle)\n", " kosten = aufrufe - vorher\n", " print(f\"{kosten} Solveraufrufe -> Konflikt aus {len(konflikt)} von \"\n", " f\"{len(BEDINGUNGEN)} Bedingungen:\\n\")\n", " for name in namen(konflikt):\n", " print(f\" * {name}\")\n", " print(\"\\nProbe auf Unreduzierbarkeit - jede einzelne davon weglassen:\")\n", " for i in konflikt:\n", " rest_loesbar = ist_loesbar([j for j in konflikt if j != i])\n", " print(f\" ohne {BEDINGUNGEN[i][0]:<26} {'loesbar' if rest_loesbar else 'UNLOESBAR - nicht minimal!'}\")\n", " print(f\"\\nAufwand: {kosten} Aufrufe. Alle Teilmengen durchzuprobieren waeren \"\n", " f\"2^{len(BEDINGUNGEN)} = {2 ** len(BEDINGUNGEN):,} gewesen.\".replace(\",\", \".\"))\n", " return konflikt\n", "\n", "\n", "def teil_4_der_naechste_konflikt(alle: list[int], konflikt: list[int]) -> None:\n", " print(\"\\n\" + \"=\" * 68)\n", " print(\"4. Ein Konflikt ist selten einer\")\n", " print(\"=\" * 68)\n", " entfernt = konflikt[0]\n", " rest = [i for i in alle if i != entfernt]\n", " print(f\"Angenommen, '{BEDINGUNGEN[entfernt][0]}' laesst sich verhandeln\")\n", " print(\"und wird aus dem Modell genommen. Dann ist das Modell ...\")\n", " if ist_loesbar(rest):\n", " print(\"... loesbar. Fertig.\")\n", " return\n", " print(\"... immer noch unloesbar. Der Filter erneut:\\n\")\n", " zweiter = deletion_filter(rest)\n", " for name in namen(zweiter):\n", " print(f\" * {name}\")\n", " gemeinsam = set(zweiter) & set(konflikt)\n", " print(f\"\\nUeberschneidung mit dem ersten Konflikt: {len(gemeinsam)} Bedingungen\")\n", " print(\"Ein zweiter, unabhaengiger Widerspruch, den der erste verdeckt hat.\")\n", " print(\"Deshalb ist die Konfliktsuche eine Schleife, kein einzelner Aufruf:\")\n", " print(\"reparieren, neu suchen, bis das Modell loesbar ist.\")\n", "\n", "\n", "def teil_5_die_reihenfolge(alle: list[int]) -> None:\n", " print(\"\\n\" + \"=\" * 68)\n", " print(\"5. Es gibt nicht DEN Konflikt\")\n", " print(\"=\" * 68)\n", " print(\"Derselbe Filter, nur eine andere Pruefreihenfolge - 200-mal gewuerfelt:\\n\")\n", " zufall = np.random.default_rng(0)\n", " haeufigkeit: dict[tuple[int, ...], int] = {}\n", " for _ in range(200):\n", " ordnung = [int(i) for i in zufall.permutation(alle)]\n", " schluessel = tuple(sorted(deletion_filter(ordnung)))\n", " haeufigkeit[schluessel] = haeufigkeit.get(schluessel, 0) + 1\n", " for schluessel, anzahl in sorted(haeufigkeit.items(), key=lambda p: -p[1]):\n", " print(f\" {anzahl:3d}x {len(schluessel)} Bedingungen: \"\n", " f\"{', '.join(namen(list(schluessel)))}\")\n", " print(f\"\\n{len(haeufigkeit)} verschiedene minimale Konflikte in EINEM Modell.\")\n", " print(\"Der Filter liefert *einen* kleinsten Konflikt, nicht *den* kleinsten -\")\n", " print(\"den gibt es nicht. Alle oben sind gleichermassen korrekt.\")\n", "\n", "\n", "def teil_6_den_befund_steuern(alle: list[int]) -> None:\n", " print(\"\\n\" + \"=\" * 68)\n", " print(\"6. Den Befund brauchbar machen\")\n", " print(\"=\" * 68)\n", " print(\"Der Filter wirft heraus, was er zuerst in die Hand bekommt. Wer die\")\n", " print(\"unveraenderlichen Bedingungen zuerst pruefen laesst, bekommt sie eher\")\n", " print(\"aus dem Befund heraus - und sieht dafuer mehr Stellschrauben.\\n\")\n", " fest = [i for i in alle if BEDINGUNGEN[i][0] not in VERHANDELBAR]\n", " frei = [i for i in alle if BEDINGUNGEN[i][0] in VERHANDELBAR]\n", " for titel, ordnung in ((\"unveraenderliche zuerst\", fest + frei),\n", " (\"veraenderliche zuerst \", frei + fest)):\n", " konflikt = sorted(deletion_filter(ordnung))\n", " stellschrauben = [i for i in konflikt if BEDINGUNGEN[i][0] in VERHANDELBAR]\n", " print(f\" {titel} -> {len(konflikt)} Bedingungen, davon \"\n", " f\"{len(stellschrauben)} veraenderlich\")\n", " print(f\" {', '.join(namen(konflikt))}\")\n", " print(\"\\nBeide Befunde sind wahr. Nur einer davon nennt dem Planer etwas,\")\n", " print(\"das er tatsaechlich tun kann.\")\n", "\n", "\n", "if __name__ == \"__main__\":\n", " alle = list(range(len(BEDINGUNGEN)))\n", " teil_1_der_befund(alle)\n", " teil_2_die_naive_suche(alle)\n", " konflikt = teil_3_der_filter(alle)\n", " teil_4_der_naechste_konflikt(alle, konflikt)\n", " teil_5_die_reihenfolge(alle)\n", " teil_6_den_befund_steuern(alle)\n", " print(\"\\n\" + \"=\" * 68)\n", " print(f\"Insgesamt {aufrufe} Solveraufrufe fuer die gesamte Diagnose.\")\n", " print(\"=\" * 68)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.11" } }, "nbformat": 4, "nbformat_minor": 5 }