Lineare Programme abstrakt formulieren

Neue Frage »

Jaqomo Auf diesen Beitrag antworten »
Lineare Programme abstrakt formulieren
Meine Frage:
Hallo zusammen,

zur Zeit belege ich an der Uni das Fach Quantitative Methoden. Hierbei ist ein Teilgebiet die Lineare Programmierung. Solange es darum geht Sachverhalte in ein LP mit Zahlen und Variablen zu verwandeln fällt mir das ganze relativ (intuitiv) leicht. Geht es dann jedoch an die abstrakte Formulierung bspw. (gemischt) ganzzahliger LPs versage ich vollkommen.

Kann man evtl. eine Art Grundvorgehensweise verfolgen, wie man vorgeht? Ich habe bereits Probleme damit alleine den richtigen Index zu wählen, über welchen summiert werden soll.

Würde mich über Anregungen/Tipps sehr freuen.

LG

Meine Ideen:
Der Aufbau an sich , also Zielfunktion (min/max), Nebenbedingungen und evtl. Nichtnegativitätsbdg. oder bspw. xi{0,1} ist mir klar. Jedoch absolut ratlos bin ich, wenn es um die Auswahl z.b. Summe oder Doppelsumme etc. geht.
Elvis Auf diesen Beitrag antworten »

Das ist kein leichtes Thema, aber nach ca. 10-30 Jahren kann man auf diesem Gebiet einige Erfahrung gewinnen. Wenn du nicht weißt, worum es geht, musst du anfangen zu lesen, z.B. bei Wikipedia: https://de.wikipedia.org/wiki/Lineare_Optimierung

Da George B.Dantzig die lineare Programmierung erfunden hat, lohnt sich die Lektüre seines Werkes immer noch (zumindest aus historischer Sicht). Nach 65 Jahren weltweiter Forschung und Entwicklung gibt es auch viele sehr gute neue Lehrbücher.

Wenn du spezielle Fragen hast, musst du sie formulieren, dann wird dir nach Möglichkeit geholfen.
Jaqomo Auf diesen Beitrag antworten »

Schonmal vielen Dank für die rasche Antwort. Ein Grundgerüst an Wissen habe ich diesbezüglich. Themen wie kanonische oder Standardform, Ecken, Basen, sowie komplementärer Schlupf oder auch dualisieren bzw. Dualität habe ich größtenteils verinnerlicht.
Wo es jedoch mangelt ist die abstrakte Formulierung von LPs. Ist bspw. ein Sachverhalt in Kombination mit einer Tabelle gegeben, so fällt es mir sehr leicht dies als LP zu formulieren. Beschränkt sich das ganze jedoch lediglich auf einen Text, welcher nun abstrakt formuliert werden soll, versage ich auf ganzer Linie.
Jaqomo Auf diesen Beitrag antworten »

Hier vllt mal ein Beispiel.
Elvis Auf diesen Beitrag antworten »

Das sieht aus wie eines der hundert Millionen Standardbeispiele in Lehrbüchern für Anfänger. Ich begreife nicht, wie du die komplizierten Theorien verstanden hast ohne einfachste Beispiele zu modellieren. Hier sollst du nur Variablen festlegen und Nebenbedingungen formulieren. Tipp zu den (nichtnegativen, ganzzahligen) Variablen: "Grundstück i versorgt Stadtteil j" (was denn sonst ?). Nebenbedingungen sind dann Beschreibung der Kosten, die Zielfunktion minimiert die Summe der Kosten.
Jaqomo Auf diesen Beitrag antworten »

Das wird wahrscheinlich auch der Grund sein, wieso ich dazu einfach nirgends Erklärungen finde, da es scheinbar absolute Basics sind an denen es mir da mangelt smile
 
 
Elvis Auf diesen Beitrag antworten »

So scheint es zu sein. George Dantzig hat reichlich Standardbeispiele entwickelt und ausführlich beschrieben (und natürlich gelöst). Der wesentliche Trick besteht darin, Entscheidungsvariablen so festzulegen, dass die Nebenbedingungen des Problems ohne grossen Aufwand als Ungleichungen und Gleichungen geschrieben werden können. Anders gesagt: immer mit Variablen starten, der Rest ergibt sich dann fast von selbst.

Im Beispiel sind die übrigens binär, und für jedes i ist ihre Summe kleiner gleich q.
Jaqomo Auf diesen Beitrag antworten »

Mit zahlen oder Tabellen sowas zu formulieren ist wirklich einfach. Ohne weiß ich einfach nicht in welchem Moment über welchen Index summiert werden soll, oder ob ich verschachtelte Summen nutze oder einzelne.
Elvis Auf diesen Beitrag antworten »

Das Leben und die große weite Welt besteht aus (manchmal lösbaren) Problemen, nicht aus Tabellen. Augenzwinkern
Jaqomo Auf diesen Beitrag antworten »

Freude
Jaqomo Auf diesen Beitrag antworten »

Trotzdem witzig warum du überhaupt antwortest. Das Wissensstände ganz unterschiedlich sind dürfte doch klar sein und für den Austausch über diese ist dieses Forum doch denke ich da. Deine Antworten sind jedoch im Endeffekt überflüsig. Erst verweist du darauf, dass 10-30 Jahre an Erfahrung hilfreich sind und verlinkst einen allg. Wikipedia Eintrag mit dem Verweis auf genauere Eingrenzung der Wissenslücke. Nachdem dies erfolgt erläuterst du das das doch absolut simpel sei und rundest das in der nächsten Antwort mit das Leben besteht aus Problemen ab.
Viel gesagt und nichts gesagt.
Elvis Auf diesen Beitrag antworten »

Was willst du mir damit sagen ? Hast du bemerkt, dass ich nebenbei dein Problem gelöst habe ?
Jaqomo Auf diesen Beitrag antworten »

Hast du nicht. Zuindest sehe ich kein LP in Summenschreibweise
Elvis Auf diesen Beitrag antworten »

Ich habe dir den allgemeinen Weg aufgezeigt: Definiere die Entscheidungsvariablen, formuliere danach Nebenbedingungen und Zielfunktion.

Ich habe die (binären) Variablen des speziellen Problems definiert und erklärt. Ich habe für jedes i eine Nebenbedingung mit rechter Seite q formuliert.

Wenn du nicht weiterkommst, liegt es nicht an mir, dann musst du Dantzig lesen.
Elvis Auf diesen Beitrag antworten »

Weil du so freundlich gefragt und verständig mitgearbeitet hast, kommt hier das LP in Summenschreibweise inklusive Erläuterung.

=" versorgt " (binär)
"eine Station kann höchstens für Bezirke zuständig sein"
="Station wird gebaut (1), oder nicht gebaut (0)" (binär)
"wie man leicht sieht, nehmen die linken Seiten genau dann den Wert 1 an, wenn die -te Station gebaut wird"
(man könnte ebensogut durch jede Zahl größer gleich dividieren, ist in diesem Sinne für die Modellierung zufällig gewählt)
"minimiere die Gesamtkosten"
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »