lineare Optimierung: künstliche Variablen?
Guten Tag,
aktuell befasse ich mich mit linearen Optimierungsproblemen in allgemeiner Form.
Nun wurden die künstlichen Variablen eingeführt. Ich verstehe nicht so ganz, was sie für einen Nutzen haben und wann man eine Ecke des Zulassungsbereiches des ursprünglichen Problems mit den Variablen und Schlupfvariablen erreicht.
Genauer geht es um die erste Phase der Zweiphasenmethode. Kann mir diese jemand (allgemein) erklären?
Es ist wahrscheinlich viel Arbeit, weswegen ich auch für hilfreiche Links dankbar bin.
Warum der Begriff Sphäre statt Polyeder bei A23.3?
1 Antwort
Bei einer zulässigen Ecke dürfen die Variablen nicht negativ sein. Wenn dies der Fall ist, verwendet man zunächst den dualen Simplex, um in den nichtnegativen Bereich zu kommen. Alternativ verwendet man die M-Methode mit den künstlichen Variablen. Diese stellen dar, um wie viel eine ursprüngliche Ungleichung verletzt wird. Je Einheit, um die ein Mindest-/Höchstwert unter-/überschritten wird, hat man M Strafkosten.
In der Praxis macht es auch Sinn, dass eine Ungleichung nicht ganz strikt einzuhalten ist, aber man bei Verletzung hohe Kosten hat. Wenn die Ungleichung strikt eingehalten werden soll, setzt man die Kosten hoch genug, sodass es sich diese nicht lohnen.
Beispiel: Man braucht Mindestens eine Einheit von x. Die Produktion von einer Einheit x kostet eine Geldeinheit. Wenn man mit x = 0 startet, verletzt man die Restriktion. Darum führt man eine Variable y ein, die bedeuten könnte, dass man sich das y von woanders kauft, sodass nun nicht x ≥ 1, sondern x + y ≥ 1 gelten muss. Wenn man will, dass trotzdem x ≥ 1 gilt, setzt man für y Strafkosten. Hier muss y mehr als eine Einheit kosten, damit es sich nicht lohnt.
In dem Beispiel ist die Zielfunktionsterm -x - 4y. Wenn man vom Punkt (0, 1) ausgeht, verbessert man sich also, wenn man nach (1, 0) geht und somit in den ursprünglichen zulässigen Bereich mit x ≥ 1 kommt.
Die Zweiphasenmethode ist die Anwendung der M-Methode zusammen mit dem primalen Simplex. Unter dem Suchbegriff (Big/Groß-)M-Methode findet sich mehr.
Eine künstliche Variable ist eine, die am Ende 0 werden soll, weshalb man ihr in der Zielfunktion einen sehr negativen Koeffizienten -M verpasst.
Also ich habe mir jetzt mal den Artikel auf Wikipedia angeschaut, bin aber immernoch nicht wirklich schlauer.
Wieso muss man jetzt nun die künstlichen Variablen einführen. Man hat ja die bei nicht-kleinergleich-Relationen die negativen Schlupfvariablen (bzw. eigentlich positiv, nur mit negativem Rechenzeichen)
Die Schlupfvariablen geben an, wie viel man bei einer Restriktion noch übrig hat. In einer zulässigen Lösung darf man auch positiven Schlupf haben.
Die künstlichen Variablen sind so ähnlich, aber sie geben an, wie sehr man eine Restriktion verletzt. Für die Restritktion x ≥ b hätte man die Gleichung x - y + z = b. Hier bei ist y der Schlupf, um wie viel man mit x die Mindestmenge b überschreitet. Wenn x am Anfang 0 ist, hätte man negativen Schlupf, was unzulässig ist, deshalb führt man die künstliche Variable z ein, welche zu Beginn als Basisvariable den Wert b hat. In der Lösung soll z = 0 sein, sodass man z in der Zielfunktion mit -M gewichtet. Der Schlupf wird dagegen in der Zielfunktion nicht bestraft.
Okay, ich glaube, ich verstehe es langsam. Ich schaue mir das morgen nochmal an.
Vielen Dank auf jeden Fall!
Wenn man eine Ecke des Systems mit den künstlichen Variablen gefunden hat, diese künstlichen Variablen aber alle null sind, dann darf man doch beim Eckpunkt die Komponenten der künstlichen Variablen weglassen, da dann das System äquivalent zu jedem ohne künstliche Variablen ist, oder?
Weil ich habe in meinem Buch gelesen, dass das für die künstlichen Variablen, die aus Gleichungen entstanden sind, der Fall ist, aber für jene, die aus Größergleich-Relationen enstanden sind, nicht, da dann wohl eine aktive Nebenbedingung fehle.
Ich habe noch ne andere Frage zum Thema.
Der Zulässigkeitsbereich der Zielfunktion wird in meinem Buch Polyeder oder Spähre genannt. Und ein Polytop ist ein beschränktes Polyeder.
Geometrisch ist ein Polyeder ja ein dreidimensionaler Körper (genaue Definition kenne ich gerade nicht) und die Sphäre eine (n‐dimensionale) Kugeloberfläche.
Im Bezug zum Thema kommen aber keine Kugeln oder nur dreidimensionale Körper vor (in den Beispielen meistens zweidimenionale Zulässigkeitsbereiche, also geometisch Polygone).
Wieso nennt man die Zulässigkeitsbreiche so und wann sagt man Polyeder und wann Sphäre?
Das sehe ich jetzt nicht, wieso man die Spalten der künstlichen Variablen noch beachten müsste.
Was ist das für ein Buch und wo steht das?
Der Begriff Polyeder wird auch verallgemeinernd bei höheren Dimensionen verwendet.
Bei der linearen Optimierung sind die Zulässigkeitsbereiche konvexe Polyeder. Bei einer Sphäre gibt es keine Ecke. Das wäre dann ein anderes Thema.
Hier der Link zum Buch:
https://link.springer.com/book/10.1007/978-3-662-56741-8
Aber das was ich meine steht im Bonusmaterial zum Buch (im Buch selbst werden nur Standardformen betrachtet), siehe hier - das erste bei "1 Electronic Supplementary Material" unten.
Das müsste dann auf Seite 68 (Beschriftung der Seiten) bzw. Seite 4 von der Dokumentenanzahl sein - linke Spalte relativ mittig.
Der Begriff Polyeder wird auch verallgemeinernd bei höheren Dimensionen verwendet.
Oh, ich dachte das sei Polytop (bzw. n-Polytop).
Bei einer Sphäre gibt es keine Ecke.
Ja, so verstehe ich das eigentlich auch. Aber in dem Bonusmaterial zum diesem Kapitel (selbe Link wie beim anderen Kommentar, Link), steht bei einem Polyeder der Begriff Sphäre.
Ich ergänze meine Frage mal mit diesem Ausschnitt.
Die haben anscheinend ihre eigene Definition, nämlich "die Sphäre eines Polyeders ist die konvexe Hülle seiner Ecken". Und Polytop und Polyeder eben auch wie es dort definiert ist. So wie du gesagt hast, ist die Definition von Polytop und Polyeder anscheinend tatsächlich üblich in der Linearen Optimierung. Das mit der Sphäre finde ich nirgendwo sonst.
Ok, danke. Das merke ich mir das mit der Sphäre, wie es dort steht, mal nicht für Allgemein.
Ist dir denn der Unterschied zwischen Polytop und Polyeder (unbeschränktes Polytop), wie es beschrieben wird, bekannt in diesem Bereich der Mathematik, oder zählte das auch zu deiner letzten Aussage dazu?
Ich habe den Begriff Polyeder für den zulässigen Bereich schon gesehen, aber die genaue Definition von Polytop und Polyeder wusste ich jetzt nicht.
Oh, vielen Dank.
Das wird noch eingeführt. Das mit den künstlichen Variablen und der Zweiphasenmethode (ist das die M-Methode?) verstehe ich nicht.