{ "cells": [ { "cell_type": "markdown", "id": "51370de1-2d7e-458a-a634-4229d48a6184", "metadata": {}, "source": [ "# Ganzzahlige Lineare Optimierung\n", "\n" ] }, { "cell_type": "markdown", "id": "ca08475c-b693-4d3c-a411-7691b4c3d043", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "2b82c8ef-11c0-4bc9-b622-51b0488abe79", "metadata": {}, "source": [ "
\n", "Ziel des Notebooks:\n", "\n", "- Grundlegende Konzepte der kombinatorischen Optimierung und Graphentheorie verstehen\n", " - (Ganzzahlige) lineare Programme\n", " - Relaxierung von linearen Programmen\n", " - Simplex-Algorithmus (nur Idee)\n", " - Branch-and-Bound\n", " - Knapsack-Problem\n", " - Matching-Problem\n", "\n", "
\n", " \n", "Mathematische Tools:\n", "- Lineare Programmierung\n", " - Simplex-Algorithmus\n", " - Branch-and-Bound\n", " \n", " \n", " \n", "
" ] }, { "cell_type": "markdown", "id": "0e2b0a7a-baa6-4f36-a070-5da612864691", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "824667f2-4b93-415e-bfaf-286dbd5f71e9", "metadata": {}, "source": [ "## Lineare Programme mit ganzzahliger Lösung" ] }, { "cell_type": "markdown", "id": "ba0a998a-bad8-4705-b8c5-ab480e45da4b", "metadata": {}, "source": [ "Sie haben im Buch bereits ein Beispiel kennengelernt, in dem die Firma Kakaofriends verschiedene Produkte zu einem möglichst günstigen Preis herstellen lassen lassen möchte. \n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "d0d471a9-167c-40fc-ac6e-acbc1897bfb1", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Lesen Sie aufmerksam den Abschnitt im Proseminar-Buch. Verstehen Sie insbesondere, wie der Simplex-Algorithmus für lineare Programme funktioniert und fassen Sie stichpunktartig zusammen, wie dieser ein lineares Programm löst.\n", "
" ] }, { "cell_type": "markdown", "id": "bf5fbf7b-738c-47a8-8d8b-c2c5cdf0b373", "metadata": {}, "source": [ "Aus den gegebenen Informationen wurde im Buch bereits das folgende Optimierungsproblem aufgestellt:\n", "\n", "$$\\begin{align}\n", "\\text{minimiere} \\ \\quad & 3 x_1 + 5 x_2 \\\\\n", "\\text{u.d.N.} \\ \\quad & 2x_1+x_2 & \\geq 3 \\\\\n", " & 2 x_1 + 2 x_2 & \\geq 5 \\\\\n", " & x_1 + 4 x_2 & \\geq 4 \\\\\n", " & x_1, x_2 \\geq 0 \\\\\n", "\\end{align}$$\n" ] }, { "cell_type": "markdown", "id": "52ccb43e-0a0b-477e-9869-516bea25c5d2", "metadata": {}, "source": [ "Diese besondere Art von Optimierungsproblemen nennt man auch lineare Programme." ] }, { "cell_type": "markdown", "id": "e6052ee9-fbff-442e-b895-3a7d4c8ca99a", "metadata": {}, "source": [ "
\n", "Ein lineares Programm ist ein Optimierungsproblem, welches sich in folgender Form schreiben lässt:\n", " \n", "$$\\begin{align}\n", "\\text{maximiere/minimiere} \\ \\quad & c^\\top x \\\\\n", "\\text{u.d.N.} \\ \\quad & a_{1,1} x_1 + \\dots + a_{1,n} x_n & \\sim_1 b_1 \\\\\n", " & \\vdots & \\vdots \\\\\n", " & a_{m,1} x_1 + \\dots + a_{m,n} x_n & \\sim_m b_1 \\\\\n", "\\end{align}$$\n", " \n", "wobei $A\\in\\mathbb{R}^{m\\times n}$, $c\\in\\mathbb{R}^n$, $b\\in\\mathbb{R}^m$ für $m,n\\in\\mathbb{N}$ beliebige Matrizen bzw. Vektoren sind. \\\n", "Die Zeichen $\\sim_1, \\dots, \\sim_m$ stehen hier für die verschieden Relationen der $m$ Nebenbedingungen. Dabei muss gelten $\\sim_i \\, \\in \\{ \\leq , = , \\geq \\}$ für alle $i\\in\\{1,\\dots,m\\}$.\n", " \n", "Die Einträge des Vektors $x=\\begin{pmatrix} x_1 & x_2 & \\dots & x_n\\end{pmatrix}^\\top$ nennen wir Entscheidungsvariablen. \\\n", "Die Abbildung $\\mathbb{R}^n \\to \\mathbb{R}, \\; x \\mapsto c^\\top x$ heißt Zielfunktion. \\\n", "Die (Un-)Gleichungen unter der Zielfunktion nennen wir Nebenbedingungen.\n", "\n", "Wir nennen die Lösung $x^* \\in\\mathbb{R}^n$ eine optimale Lösung des linearen Programms genau dann, wenn $x^*$ die Nebenbedingungen erfüllt und die Zielfunktion maximiert bzw. minimiert. \\\n", "Alle Vektoren $x\\in P := \\{\\mathbb{R}^n \\mid Ax\\leq b, x\\geq 0 \\}$, die die Nebenbedingungen erfüllen, heißen zulässige Lösung. \\\n", "Dementsprechend nennen wir Vektoren $x\\in\\{\\mathbb{R}^n \\mid Ax\\leq b, x\\geq 0 \\}^{C}$ unzulässige Lösung.\n", "
" ] }, { "cell_type": "markdown", "id": "88be2e49-1ceb-455a-8719-dbab8045a71c", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Nennen Sie eine zulässige und eine unzulässige Lösung des obigen linearen Programms.\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "26cd2fdf-2f29-4559-8085-3fe3911d0663", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "32d639d5-0335-429a-bc5a-f4de14c7ffe2", "metadata": {}, "source": [ "Im obigen Beispiel waren fraktionale Lösungen erlaubt, d.h. $(x_1,x_2)=\\left( 2,\\frac{1}{2} \\right) $ ist eine zulässige und optimale Lösung. Es handelt sich um ein stetiges Optimierungsproblem
\n", "Das ist aber nicht immer der Fall. In vielen Praxisproblemen wird eine ganzzahlige Lösung gefordert. Dann spricht man von diskreten Optimierungsproblemen.\n", "Dazu betrachten wir ein weiteres Produktionsproblem von Kakaofriends.\n" ] }, { "cell_type": "markdown", "id": "c404b5d9-e614-45e9-ba22-030feddbd091", "metadata": {}, "source": [ "Schokolade und Pralinen kamen bei den Kunden leider nicht so gut an, deswegen entscheidet sich die Firma jetzt dazu, Schokocreme und Schokodrops herzustellen.\n", "- Für eine Pallette Schokocreme werden 7 Einheiten Kakaobutter und 3 Einheiten Kakaopulver benötigt. \n", "- Für die Herstellung von einer Pallette Schokodrops werden 3 Einheiten Kakaobutter und 5 Einheiten Kakaopulver benötigt.\n", "- An den Verbraucher wird ein Glas Schokocreme für den Preis von 3€ verkauft, eine Packung Schokodrops kostet 2€.\n", "\n", "Angenommen, Kakaofriends hat noch einen Restbestand von 21 Einheiten Kakaobutter und 15 Einheiten Kakaopulver zur Verfügung. Es können nur vollständige Palletten Schokocremes und Schokodrops an den Händler verkauft werden. Welche Produkte sollen aus den vorhandenen Zutaten produziert werden, damit der Gewinn maximal ist? Wieviel Kakaobutter und Kakaopulver bleiben ggf. übrig?" ] }, { "cell_type": "markdown", "id": "c9f376d9-46ce-48ec-9687-66b524bc715a", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "1. Formulieren Sie das obige Beispiel mathematisch als lineares Optimierungsproblem. Orientieren Sie sich dabei an das Kapitel im Buch. Wie lautet die Zielfunktion? Welche sind die Nebenbedingungen? \n", "2. Zeichnen Sie wie im Kapitel im Buch ein kartesisches Koordinatensystem mit dem Polyeder der zulässigen Lösungen. Plotten Sie diesen auch mit Julia.\n", "3. Wieviele zulässige ganzzahlige Lösungen gibt es? \n", "
" ] }, { "cell_type": "markdown", "id": "87c59447-27c8-4fb6-9279-cf08fa0a93f4", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "da1eb94d-5697-4830-874b-f7ae4b49f5fb", "metadata": {}, "source": [ "Löst man das Optimierunsproblem mit dem Simplex-Algorithmus, so erhält man die fraktionale Lösung $(x^*,y^*)= \\left( \\frac{21}{13}, \\frac{30}{13} \\right)$, wobei $x^*$ und $y^*$ der Anzahl der Palletten Schokodrops bzw. Schokocreme entsprechen. Da wir aber eine ganzzahlige Lösung brauchen, können wir dieses Ergebnis leider nicht verwenden.\n", "\n", "Auch Kakaofriends hat den Simplex-Algorithmus verwendet und ist auf dieses Problem gestoßen. Ein Mitarbeiter schlägt vor, einfach den nächstgelegenen ganzzahligen Wert zu nehmen, also $(x^*,y^*)$ zu einer ganzzahligen Lösung abzurunden.\n", "\n" ] }, { "cell_type": "markdown", "id": "b9ed7488-c9d3-4b20-b36b-3cc669d772a9", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Was würden Sie dem Mitarbeiter antworten? Warum ist das keine gute Idee? \n", "
" ] }, { "cell_type": "markdown", "id": "8c3d5ff1-21a2-4bf7-ab8b-e0f59c0d1506", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "b4c12a78-8b49-428c-9a27-d15ad03ab7d5", "metadata": {}, "source": [ "Wir können also festhalten, dass der Simplex-Algorithmus für dieses Beispiel kein guter Lösungsansatz ist. Das liegt daran, dass der Simplex-Algorithmus optimale Lösungen im Wertebereich $\\mathbb{R}^n$, $n\\in\\mathbb{N}$, sucht, also für stetige Optimierungsprobleme. Führen wir den Simplex-Algorithmus mit den gegebenen Zahlenwerten durch, dann berechnen wir anstatt einer Lösung des diskreten Optimierungsproblems\n", "\n", "$$\\begin{align}\n", "\\text{minimiere} \\ \\quad & c^T x \\\\\n", "\\text{u.d.N.} \\ \\quad & Ax \\leq 0 \\\\\n", " & x \\in \\mathbb{Z}^n \\\\\n", "\\end{align}$$\n", "\n", "eine exakte Lösung des stetigen Optimierungsproblems\n", "\n", "$$\\begin{align}\n", "\\text{minimiere} \\ \\quad & c^T x \\\\\n", "\\text{u.d.N.} \\ \\quad & Ax \\leq 0 \\\\\n", " & x \\geq 0 \\\\\n", "\\end{align}$$\n", "\n", "Dieses lineare Programm nennt man auch Relaxierung." ] }, { "cell_type": "markdown", "id": "6f76df62-a113-40b9-b74b-a2566aacde52", "metadata": {}, "source": [ "
\n", "Sei $\\max\\{c^T x \\mid Ax\\leq b, x\\in \\mathbb{Z}_+^n \\}$ ein lineares Programm $\\mathcal{P}$. Dann nennen wir $\\max\\{c^T x \\mid Ax\\leq b, x \\geq 0 \\}$ die Relaxierung von $\\mathcal{P}$.\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "966b3fca-83d7-4f7c-be4a-abcd899a3594", "metadata": {}, "source": [ "Für diskrete lineare Programme gibt es zum Glück auch eigene Lösungsmethoden. Eine davon ist Branch-and-Bound." ] }, { "cell_type": "markdown", "id": "7185c07a-f4f3-4873-96f0-04b2be114f5c", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "3a28d9e7-e3fd-4c7f-9ec0-3c8b51defd05", "metadata": {}, "source": [ "## Branch-and-Bound" ] }, { "cell_type": "markdown", "id": "02532fe3-f92b-463d-a4c6-69a6160a9327", "metadata": {}, "source": [ "Einen zuverlässigeren Ansatz als das Runden von fraktionalen Ergebnissen liefert der Branch-and-Bound Algorithmus.\n", "\n", "Die Idee des Algorithmus ist es, das Minimierungs- bzw. Maximierungsproblem auf Teilmengen $X_1,\\dots, X_k$ zu lösen, sodass $X = X_1 \\cup \\dots \\cup X_k$ eine Partition des Raums der zulässigen Lösungen ist." ] }, { "cell_type": "markdown", "id": "c11568ad-cc6e-4ac3-973e-b19fce6706c2", "metadata": {}, "source": [ "Weiter werden wir das folgende Prinzip benutzen:" ] }, { "cell_type": "markdown", "id": "30215f34-d310-4b47-b2db-d041df02c22f", "metadata": {}, "source": [ "
\n", "Satz 1
\n", "Sei $X = X_1 \\cup \\dots \\cup X_k$ eine Partition. Definiere $z := \\max\\{ c^T x\\mid x\\in X\\}$, $z_i := \\{ c^T x \\mid x\\in X_i \\}$ für alle $i \\in \\{1,\\dots,k\\}$. Sei $a_i$ eine untere Schranke und $b_i$ eine obere Schranke für $z_i$ für alle $i \\in \\{1,\\dots,k\\}$. Dann gilt\n", " \n", "- $\\max_{i=1,\\dots,k} a_i$ ist eine untere Schranke für $z$\n", "- $\\max_{i=1,\\dots,k} b_i$ ist eine obere Schranke für $z$\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "350fa164-689a-4706-aa68-9f4e5602bb6e", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Beweisen Sie Satz 1. \n", "
" ] }, { "cell_type": "markdown", "id": "f50097ba-3204-4897-915e-8657a480aa70", "metadata": {}, "source": [ "Wir betrachten den Algorithmus direkt an einem Beispiel, dem Knapsack-Problem.\n", "\n", "Ein Rucksack der Kapazität $15 L$ soll mit Elementen befüllt werden. Eingepackt werden können vier Elemente verschiedener Größe, die gleichzeitig auch einen Profit mit sich bringen.\n", "- Element $1$ hat eine Größe von $5 L$ und bringt einen Profit von $10$\n", "- Element $2$ hat eine Größe von $7 L$ und bringt einen Profit von $13$\n", "- Element $3$ hat eine Größe von $4 L$ und bringt einen Profit von $8$\n", "- Element $4$ hat eine Größe von $3 L$ und bringt einen Profit von $6$\n", "Welche Elemente sollte man wählen, um den Profit zu maximieren?\n", "\n", "Um die Frage zu beantworten, müssen wir das folgende ganzzahlige lineare Programm lösen:\n", "\n", "$$\\begin{align}\n", "\\text{minimiere} \\ \\quad & 10 x_1 + 13 x_2 + 8 x_3 + 6 x_4 \\\\\n", "\\text{u.d.N.} \\ \\quad & 5 x_1 + 7 x_2 + 4 x_3 + 3 x_4 & \\leq 14 \\\\\n", " & x_1, x_2, x_3, x_4 & \\in \\{0,1\\} \\\\\n", "\\end{align}$$\n" ] }, { "cell_type": "markdown", "id": "d534ea89-784f-4b22-87c6-9437cbade9b2", "metadata": {}, "source": [ "Die Relaxierung dieses Programms besitzt eine optimale Lösung $x^*=(0,\\frac{1}{4},1,1)$ mit Zielfunktionswert $c^T x^* = 49$. Dieser Wert ist eine obere Schranke für $z = \\max\\{ c^T x \\mid Ax \\leq b , \\ x_1, x_2, x_3, x_4 \\in \\{0,1\\} \\}$, wobei $c,A,b$ entsprechend der obigen Werte passend gewählt sind. \n", "\n", "
\n", "Denkanstoß: Warum gilt das?\n", "
\n", "\n", "Wir benötigen allerdings eine ganzzahlige optimale Lösung." ] }, { "cell_type": "markdown", "id": "96698fd8-737c-4e97-bbf0-19f3abe57bd9", "metadata": {}, "source": [ "
\n", " \n", "### Recherche-Aufgabe\n", "***\n", "Recherchieren Sie nach dem Branch-and-Bound-Verfahren zum Lösen von ganzzahligen linearen Programmen. Wie funktioniert der Algorithmus? An welcher Stelle fließt die Aussage von Satz 1 ein?
\n", "Lösen Sie mit dem Algorithmus die oben definierte Instanz des Knapsack-Problems. \n", " \n", "Hinweis: Für die Lösung von relaxierten linearen Programmen müssen Sie keinen Rechenweg angeben. \n", "
" ] }, { "cell_type": "markdown", "id": "2207924b-d326-45bb-9e85-6f581d171f87", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "eb327f9e-ca40-4427-bfc0-eddb87c5584e", "metadata": {}, "source": [ "## Total unimodulare Matrizen" ] }, { "cell_type": "markdown", "id": "33ba9d5a-075c-473f-a03c-f29c6f8c5066", "metadata": {}, "source": [ "
\n", "Ein Polyeder $P\\in\\mathbb{R}^n$ heißt ganzzahlig, falls für alle $c\\in \\mathbb{R}^n$ das lineare Programm $\\max\\{ c^T x \\mid x\\in P \\}$ eine ganzzahlige Lösung besitzt. \n", "
" ] }, { "cell_type": "markdown", "id": "b668c212-3b3a-4b20-9ca5-8dc031392129", "metadata": {}, "source": [ "Das bedeutet, dass wir automatisch eine ganzzahlige Lösung bekommen, wenn wir ein lineares Programm über ein Polyeder dieser Art lösen." ] }, { "cell_type": "markdown", "id": "09546c5c-11d3-4699-9dfe-13d8dcd4e4b1", "metadata": {}, "source": [ "
\n", "Eine Matrix $A\\in\\mathbb{R}^{n\\times n}$ heißt unimodular, falls $\\text{det}(A) \\in\\{\\pm 1\\}$.\n", "\n", "Eine Matrix $A\\in\\mathbb{R}^{m\\times n}$ heißt total unimodular, falls für jede quadratische Untermatrix $U$ von $A$ gilt: $\\text{det}(U) \\in\\{\\pm 1, 0\\}$.\n", "
" ] }, { "cell_type": "markdown", "id": "cca08661-e6c9-4f56-ba18-3c25075bdfc0", "metadata": {}, "source": [ "Wenn sich ein ganzzahlige lineares Optimierungsproblem durch eine total unimodulare Matrix beschreiben lässt, haben wir Glück. Denn es gilt der folgende Zusammenhang:\n", "\n", "
\n", "Theorem 1 (Hofmann, Kruskal)\n", " \n", "Sei $A\\in \\mathbb{Z}^{m\\times n}$. Dann sind die folgenden beiden Aussagen äquivalent:\n", "1. $A$ ist total unimodular.\n", "2. Für alle $b\\in\\mathbb{Z}^{m\\times n}$ ist das Polyeder $P = \\{x \\in\\mathbb{R}^n \\mid Ax\\leq b\\}$ ganzzahlig.\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "d450f75e-8e3d-4e99-8e60-1d7870526d7e", "metadata": {}, "source": [ "Wenn wir also wissen, dass unser ganzzahliges Optimierungsproblem durch eine total unimodulare Matrix $A$ gegeben ist, brauchen wir gar nicht zwangsläufig einen Lösungsalgorithmus wie den Branch-and-Bound-Algorithmus, der die Bedingung der Ganzzahligkeit der Lösung $x^*$ beachtet. Wir können diese Bedingung einfach fallen lassen und das relaxierte lineare Programm z.B. mit dem Simplex-Alorithmus lösen. Denn wir wissen dank des Theorems nun: Die Lösung wird ohnehin ganzzahlig sein." ] }, { "cell_type": "markdown", "id": "4d0be5cb-88d0-4a2a-ac1b-17554ada2b76", "metadata": {}, "source": [ "Zu bestimmen, ob eine Matrix $A\\in \\mathbb{Z}^{m\\times n}$ total unimodular ist, scheint für kleine $m,n\\in \\mathbb{N}$ noch leicht zu sein. Aber für große $m,n$ alle Unterdeterminanten zu berechnen, ist sehr ineffizient. Glücklicherweise gibt es einige Kriterien, anhand denen man schneller auf totale Unimodularität testen kann." ] }, { "cell_type": "markdown", "id": "b6ab72f0-290e-4ca8-a4a5-088c6406cc1a", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Sei $A \\in \\mathbb{Z}^{m\\times n}$ total unimodular. Beweisen Sie, dass die folgenden Matrizen dann auch total unimodular sind:\n", "1. $(A^T \\mid I_n)$, wobei $I_n$ die $n\\times n$- Einheitsmatrix ist\n", "2. $(A \\mid -A)$\n", "3. $A \\cdot (I_n-2e_i ^T e_i)$ für alle $i\\in \\{1,\\dots, n\\}$\n", "
" ] }, { "cell_type": "markdown", "id": "14ad2489-ae60-43b0-b589-8414fd420267", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "b9eff2c8-b667-4c05-aa03-97f20d605d02", "metadata": {}, "source": [ "
\n", "Theorem 2\n", " \n", "Sei $A\\in\\{\\pm 1 , 0\\} ^{m\\times n}$. Die folgenden Aussagen sind äquivalent:\n", "\n", "1. $A$ ist total unimodular.\n", "2. $A$ enthält keine quadratische Matrix $U$ mit $\\text{det}(U) \\in\\{\\pm 2\\}$.\n", "3. Für alle $I \\subseteq \\{1,\\dots,m\\}$ existiert eine Partition $I = I_1 \\uplus I_2$, sodass $$\\forall j \\in \\{1,\\dots, n\\} : \\ \\sum_{i\\in I_1} a_{ij}- \\sum_{i\\in I_2} a_{ij} \\in \\{\\pm 1, 0\\}$$ \n", "
" ] }, { "cell_type": "markdown", "id": "31522e94-c3ca-4858-a872-ce69f97e65ab", "metadata": {}, "source": [ "
\n", "Theorem 3\n", " \n", "Sei $A\\in\\{\\pm 1 , 0\\} ^{m\\times n}$, sodass jede Spalte genau zwei Einträge verschieden von $0$ enthält. Dann sind die folgenden Aussagen äquivalent:\n", "\n", "1. $A$ ist total unimodular.\n", "2. Für alle $I \\subseteq \\{1,\\dots,m\\}$ existiert eine Partition $I = I_1 \\uplus I_2$, sodass $$\\forall j \\in \\{1,\\dots, n\\} : \\ \\sum_{i\\in I_1} a_{ij}- \\sum_{i\\in I_2} a_{ij} = 0$$ \n", "
" ] }, { "cell_type": "markdown", "id": "0d7449d5-4085-4bcf-a7bd-9eaf6464b4be", "metadata": {}, "source": [ "
\n", " \n", "### Freiwillige Aufgabe\n", "***\n", "Beweisen Sie Theorem 3. \n", "
" ] }, { "cell_type": "markdown", "id": "d3860b4c-a4ab-4186-b146-1e9830b03152", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "6d7520e1-332d-4039-8068-7b802259c954", "metadata": {}, "source": [ "Außerdem wurde im Proseminar-Buch bereits das Matching-Problem eingeführt. " ] }, { "cell_type": "markdown", "id": "3c95f078-af96-4b3e-9d0d-ecc1bc988123", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Lesen Sie den Abschnitt zu Matchings erneut und arbeiten Sie die folgenden Definitionen heraus:\n", "- Matching\n", "- bipartiter Graph\n", "
" ] }, { "cell_type": "markdown", "id": "58c97fcd-bc7d-4518-8312-4a74e568a617", "metadata": {}, "source": [ "Auch das Problem, in einem gegebenen Graphen ein Matching zu finden, zählt offenbar zu den ganzzahligen Optimierungsproblemen.\n", "\n", "Um das Matching-Problem als lineares Programm auszudrücken, müssen wir eine Matrix $A \\in \\mathbb{R}^{m \\times n}$ und Vektoren $b \\in \\mathbb{m} , \\ c \\in \\mathbb{n}$ aufstellen, die das Problem beschreiben." ] }, { "cell_type": "markdown", "id": "e2004a12-c8b5-48a5-816f-6f4992c57e6f", "metadata": {}, "source": [ "
\n", "Sei $G = (V,E)$ ein Graph mit $V=\\{v_1, \\dots, v_n\\}$, $E=\\{e_1, \\dots, e_m\\}$. Seine Inzidenzmatrix ist gegeben durch $A= (a_{ij})_{1\\leq i\\leq n, \\ 1\\leq j\\leq m}$, wobei \n", " \n", "$$a_{ij}:= \\begin{cases} 1 && \\text{falls } v_i \\in e_j \\\\ 0 && \\text{sonst} \\end{cases}$$\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "9a0c6dea-9661-4b03-8f0a-ab2182253e25", "metadata": {}, "source": [ "Anhand der Inzidenzmatrix lässt sich das Maching-Problem leicht als lineares Programm darstellen." ] }, { "cell_type": "markdown", "id": "0e80b71d-065f-4130-9e6c-37f0df78a3af", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Sei $G$ ein Graph mit Inzidenzmatrix $A$. Zeigen Sie, dass $G$ bipartit ist, wenn $A$ total unimodular ist.\n", "\n", "Gilt auch die Rückrichtung? \n", "
" ] }, { "cell_type": "markdown", "id": "41e07f39-1f76-47ce-9905-4312778c6182", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "8197e71f-50af-4dbd-a423-6eafa1ba3243", "metadata": {}, "source": [ "
\n", " \n", "### Rückblick-Aufgabe\n", "***\n", "Ausgehend von einem bereits bekannten Beispiel eines stetigen Optimierunsproblems in der Produktionstechnik wurde in diesem Notebook gezeigt, dass es in vielen Fällen auch sinnvoll ist, zusätzlich die Ganzzahligkeit der optimalen Lösung zu fordern. Wir haben gesehen, dass man in diesem Fall typische Löser für kontinuierliche lineare Programme, wie z.B. den Simplex-Algorithmus, nicht mehr anwenden bzw. die fraktionale Lösung nicht immer sinvoll interpretieren kann. Als Alternative für ganzzahlige lineare Programme eignet sich der Branch-and-Bound-Algorithmus. Ist die Matrix $A$ des ganzzahligen linearen Programms $\\max\\{c^T x \\mid Ax\\leq b, x\\in \\mathbb{Z}_+^n \\}$ bzw. $\\min\\{c^T x \\mid Ax\\leq b, x\\in \\mathbb{Z}_+^n \\}$ total unimodular, so lässt sich auch anhand des Simplex-Algorithmus eine ganzzahlige Lösung finden.\n", " \n", " \n", "Welche weiteren Lösungsansätze gibt es für ganzzahlige lineare Programme? Wie praxistauglich sind die Algorithmen? \n", " Finden Sie eine weitere übliche Lösungsmethode für ganzzahlige lineare Programme und somit eine Alternative zum Branch-and-Bound-Algorithmus. Erklären Sie deren Funktionsweise und rechnen Sie einige Beispiele mit der Methode durch.
\n", "Welche Vor- und Nachteile hat diese Methode gegenüber dem Branch-and-Bound-Algorithmus?\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "1132106e-18ee-41d1-ac64-7d92c2dae72a", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "171f80f8-69d9-4ecb-a269-2386a9283be5", "metadata": {}, "source": [ "### Literaturhinweise\n", "- Branch-and-Bound. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org/w/index.php?title=Branch-and-Bound&oldid=240092065\n", "- Ganzzahlige lineare Optimierung. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org/w/index.php?title=Ganzzahlige_lineare_Optimierung&oldid=241259762\n", "- Total unimodulare Matrix. (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org/w/index.php?title=Total_unimodulare_Matrix&oldid=210510914" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }