[BWL] QM (OR) - Simplexalgorithmus vs. geom. Ecken

Alle Anwendungsfächer des Bachelorstudiengangs (Abkürzungen)

QM (OR) - Simplexalgorithmus vs. geom. Ecken

Beitragvon Marco » 09.08.08 15:34

Hallo zusammen,

ich bin immer wieder auf ein Problem gestoßen, wo ich irgendwie auf dem Schlauch stehe: Wie ist das genaue "Zusammenspiel" zwischen dem Simplexalgorithmus und den geometrischen Ecken des zulässigen Polyeders?

Das tauchte z.Bsp. an den folgenden Stellen auf:
  • Kap. 3.1, Folie 22-24: Woher weiß ich, dass ich, wenn ich die abgebildeten Rechnungen durchführe, den entsprechenden Punkt betrachte?
  • Kap. 3.2, Folie 21-24: Woher weiß ich auch hier wieder vor dem Ausfüllen der Tabelle, welchen Punkt ich betrachte? Oder ist die Reihenfolge der Erkenntnisse auf der Folie einfach falsch dargestellt?
  • Übung 5, Aufg. 3b: Ähnlich wie gerade: Den betrachteten geometrischen Punkt kann ich doch erst nach dem Ausfüllen der Tabelle bestimmen, oder?


Und noch eine andere Frage: Wenn ich in meiner optimalen Lösung eine Schlupfvariable mit einem Wert ungleich Null belegt habe, was sagt mir das aus? Diese dürfte doch eigentlich keinen Einfluss auf meine Entscheidung in der Realität haben, da in der Zielfunktion doch nur die ursprünglichen Variablen berücksichtigt werden, oder?

Grüße
Marco
Marco
 
Beiträge: 256
Registriert: 02.08.06 23:05
Wohnort: Aachen
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon druid87 » 09.08.08 21:29

Also kurz erklärt:

Die Idee des Simplexalgorithmus ist es:

Wähle Punkt P = 0 (0 Vektor des R^n) und somit zulässige Lösung.

Gehe an den "Ecken" des Polyeders lang. Ecken sind hierbei Schnittpunkte von Hyperebenen.

Also zu Kap. 2.1: Folie 22:

Die sollte am klarsten sein:
Du wählst ja x = (x_1, x_2) = (0,0) also ist x nicht in der Basis (dafür der Rest, also die Schlupfvariablen)

Folie 23:
Du siehst wohl ein, dass hier x = (15, 0) ist.

also ist x_2 nicht in der Basis, x_1 aber. Also muss der Vektor von x_1 rein, dass ist der (4,2,5)^t.

Dann musst du halt noch schaun, dass du deine Basis voll kriegst. Setzen wir doch mal x = (15, 0) in das LGS ein:

Offensichtlich ist

4*15 + 2*0 + x_3 = 80 (erste Gleichung)

für x_3 = 0 NICHT erfüllt, also x_3 != 0
=> x_3 in die Basis packen => (1,0,0)^t vektor inne Basis rein

Schaun wir uns die 2te Gleichung an

2*15 + 3*0 + x_4 = 100

für x_4 = 0 NICHT erfüllt, also x_4 != 0
=> x_4 in die Basis packen => (0,1,0)^t vektor inne Basis rein

so nu sind wir eigentlich fertig, als Argument gilt auch gleichung 3:

5*15 + 1*0 + x_5 = 75
=> x_5 = 0 => x_5 NICHT in die Basis rein

Ich hoffe das ist erstma so klar, wenne noch Fragen hast, kannst die explizit nochma stellen.

Nun zu deinem 2ten Problem:

Wenn du eine Schlupfvariable mit einem Wert ungleich 0 belegt hast, dann bedeutet das, dass du eine Restriktion nicht völlig ausnutzt.

Das passiert immer dann wenn du primale Degeneration hast (das schaust du am besten bei "Dualität" nach, denn hier ist der Satz vom komplementären Schlupf dein Ansatzpunkt)
--

Nichts ist einfach und nichts ist trivial, insbesondere ist das Informatikstudium keins von beiden!
druid87
 
Beiträge: 5
Registriert: 09.08.08 21:09
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 07/08
Anwendungsfach: BWL

Beitragvon Marco » 10.08.08 20:00

Danke für die ausführliche Beschreibung! Damit ist die Vorgehensweise in dem ersten Fall schon einmal geklärt.

Noch einmal zu Kap. 3.2, Folien 21-24: Wie ist hier die "richtige Lesereihenfolge"? Ich kann ja aus dem Tableau relativ einfach den geometrischen Punkt ablesen, da ja x = (x_1,x_2) ist und x_i = <br />\begin{cases}<br />b_i^*  & \text{falls } x_i \text{ in der Basis} \\<br />0 & \text{sonst}<br />\end{cases} \quad , \quad i=1,2
Man könnte aber doch auch nach obigen Rechnungen anhand eines gegebenen Punktes nach und nach das Tableau füllen, oder?
Also kurz gesagt: Was war hier zuerst da, der Punkt oder das Tableau? ;-)


druid87 hat geschrieben:Wenn du eine Schlupfvariable mit einem Wert ungleich 0 belegt hast, dann bedeutet das, dass du eine Restriktion nicht völlig ausnutzt.
Das passiert immer dann wenn du primale Degeneration hast (das schaust du am besten bei "Dualität" nach, denn hier ist der Satz vom komplementären Schlupf dein Ansatzpunkt)

Bist du dir sicher, dass das nur bei primaler Degeneration passiert? In Ü5 Aufg. 1 zum Beispiel erhält man als optimale Lösung
x_B = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 8 \\ 8 \\ 2 \end{pmatrix}
und die Lösung ist ja nicht primal degeneriert, da keine der Komponenten von x_B null ist.

Grüße
Marco
Marco
 
Beiträge: 256
Registriert: 02.08.06 23:05
Wohnort: Aachen
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon druid87 » 10.08.08 20:16

Marco hat geschrieben:
druid87 hat geschrieben:Wenn du eine Schlupfvariable mit einem Wert ungleich 0 belegt hast, dann bedeutet das, dass du eine Restriktion nicht völlig ausnutzt.
Das passiert immer dann wenn du primale Degeneration hast (das schaust du am besten bei "Dualität" nach, denn hier ist der Satz vom komplementären Schlupf dein Ansatzpunkt)

Bist du dir sicher, dass das nur bei primaler Degeneration passiert? In Ü5 Aufg. 1 zum Beispiel erhält man als optimale Lösung
x_B = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 8 \\ 8 \\ 2 \end{pmatrix}
und die Lösung ist ja nicht primal degeneriert, da keine der Komponenten von x_B null ist.


Hm also hierzu: Ja du hast hier völlig recht es muss nicht primale Degeneration vorliegen. Seh ich auch absolut ein:

Primale Degeneration tritt dann auf, lapidar gesagt, wenn sich ja die Dinger schneiden, also im 2D also 3 Geraden sich in einem Punkt schneiden, im n-Dimensionalen sich n+1 Hyperebenen in einem Punkt schneiden.

Da muss ich leider nochmal selbst nachschaun, wie man primale Degeneration aus dem Simplextableau erkennen kann.

Das alte Argument bleibt jedoch: Wenn eine Variable nicht Null ist, ist Sie in der Basis.

Marco hat geschrieben:Also kurz gesagt: Was war hier zuerst da, der Punkt oder das Tableau?


Hm, zuerst war das Problem da? Zu einem Problem ist das Anfangstableau eindeutig sowie die graphische Darstellung. Du kannst aus dem Tableau auf die Punkte schließen, andersherum gehts wahrscheinlich auch, das ist aber dann nicht mehr schön (insbesondere bei größeren Problemen, da bei höherdimensionalen Problemen die graphische Darstellung nunja etwas schwerer zu bewerkstelligen ist.)
--

Nichts ist einfach und nichts ist trivial, insbesondere ist das Informatikstudium keins von beiden!
druid87
 
Beiträge: 5
Registriert: 09.08.08 21:09
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 07/08
Anwendungsfach: BWL


Zurück zu Anwendungsfächer