Einschätzen von Ecken bei einem LOP |
| 10.01.2020, 18:48 | Matrickser | Auf diesen Beitrag antworten » |
| Einschätzen von Ecken bei einem LOP Gegeben seien folgende Nebenbedingungen eines LOPs. ?2x1 + 3x2 ? 12 8x1 ? x2 ? 40 x1 + x2 ? 9 ?2x1 + x2 ? 4 3x1 + 3x2 ? 27 x1, x2 ? 0 . Beantworten Sie rechnerisch: Welcher der Punkt A = (0, 4), B = (3, 6), C = (4, 5), D = (0, 0), E = (6, 8), F = (9, 0) ist (i) eine Ecke (ii) eine ausgeartete Ecke (iii) zulässig? Meine Ideen: Zeichnerisch würde ich einfach die Funktionen einzeichnen und schauen, ob die jeweiligen Punkte eine Ecke des zulässigen Bereichs sind und wenn ja, ob sich da 2 oder mehr Bedingungen schneiden (ausgeartete vs. normale Ecke)bzw. ob der Punkt innerhalb des zulässigen Bereichs liegt (iii). Als rechnerische Lösungsmöglichkeit fiele mir jetzt nur ein, einfach die Punkte einzusetzen und zu schauen, was für Ergebnisse herauskommen. Sind alle 6 Nebenbedingungen erfüllt, dann ist der Punkt auf jeden Fall schon mal zulässig. Aber wie unterscheide ich, ob es sich zusätzlich um eine Ecke bzw. ausgeartete Ecke handelt. 
Hierfür müssten dann für einen Punkt 2 oder mehr Ungleichungen mit Gleichheit erfüllt sein, damit sich die "Begrenzungsgeraden" der Ungeraden in diesem Punkt schneiden, oder?
|
||
| 10.01.2020, 19:11 | hawe | Auf diesen Beitrag antworten » |
A weng viele Fragezeichen in Deinem Text ;_)... Grundsätzlich findest Du die Ecken dort, wo mind. 2 Schlupfvariablen = 0 sind. Das könnte man durchtesten... Zur zeichnerischen Umsetzung siehe https://www.geogebra.org/m/rf3ftcaq Ein Beispiel z.B. https://www.geogebra.org/m/BpqJ28eP#material/k3ngusuy |
||
| 10.01.2020, 19:47 | Matrickser | Auf diesen Beitrag antworten » |
Dann stimmt ja mein Ansatz eigentlich. 
wenn die Schlupfvariablen 0 sind, dann sind ja die Ungleichungen Gleichungen. |
||
| 10.01.2020, 20:52 | hawe | Auf diesen Beitrag antworten » |
Kannst Du die Angaben richtig stellen? - nur so fürs Protokoll Nun es genügt im allgemenien nicht nur den Schnittpunkt zu bestimmen, es könnten neg. Werte entstehen ( nicht Neg.-Bedingung) - bei 2 Basisvariablen "siehst" Du das vielleicht. Bei mehr als 2 Basisvariablen musst Du das gesamte Tableau berechnen um zu sehen was los ist. Vielleicht meinst das mit "(ausgeartete vs. normale Ecke"? Angenommen LP Max und alle NB<=0 die 2 ersten NB Schlupfvariablen = 0 ==> X=(6,8) Grafisch "sieht man" Schnittpunkt weit außerhalb des Lösungsgebietes... Rechnerisch 2 andere Schlupfvariablen sind neg.,d,h die betreffenen Ressourcen werden überschritten... |
||
| 11.01.2020, 01:02 | Matrickser | Auf diesen Beitrag antworten » |
Habe das ganze Problem jetzt erstmal mittels Geogebra dargestellt. Daran erkennt man erstmal, dass E und F nicht zulässig sind, weil die Schnittpunkte außerhalb des zulässigen Bereichs liegen (dem dunkelblausten Pentagon mit einer Ecke am KUS). Des Weiteren dass C zulässig ist. weil alle Bedingungen erfüllt sind, aber C auf keiner Ecke liegt. B und D sind jeweils Ecken, hier sind 2 Ungleichungen mit Gleichheit erfüllt. A ist eine ausgeartete Ecke, weil hier 3 Ungleichungsnebenbedingungen mit Gleichheit erfüllt sind. |
||
| 11.01.2020, 10:55 | hawe | Auf diesen Beitrag antworten » |
Tja, was ist so schwer daran die Aufgabe in lesbarer Form darzustellen? Du brauchst ja eine rechnerische Lösung und die hab ich im letzten Post skizziert.... ist auch in dem Beispiel-Link enthalten |
||
| Anzeige | ||
|
|
||
| 13.01.2020, 15:58 | Matrickser | Auf diesen Beitrag antworten » |
Oh sorry, ich hab jetzt erstmal verstanden, was du mit den Fragezeichen gemeint hast? 
Also, die Nebenbedingungen sehen wie folgt aus: -2x1 + 3x2 <= 12 8x1 - x2 <= 40 x1 + x2 <= 9 -2x1 + x2 <= 4 3x1 + 3x2 <= 27 x1 >= 0 x2 >= 0 Es handelt sich also abgesehen von der fehlenden Zielfunktion also um ein klassisches LOP mit kleiner-gleich-Bedingungen, positiven Koeffizienten auf der rechten Seite und einer positiven Schranke für die x. Eine ausgeartete Ecke ist bei uns definiert als eine Ecke, bei der das Simplexverfahren trotz eines Austauschschritts zu keiner Verbesserung des Zielfunktionswerts führt, da sich dort mehr als 2 Bedingungen schneiden. Um nun wieder auf die Lösung zurückzukommen: Ich habe nun jeweils erstmals eine positive Schlupfvariable für die ersten 5 Nebenbedingungen eingeführt (die Nichtnegativitätsbedingung für x muss man aber natürlich auch noch betrachten
- da aber für y ebenfalls eine Nichtnegativitätsbedingung gilt, sollte hier dann aber Schlupfvariablen subtrahiert werden, oder? (wobei das im Endeffekt eh keinen Unterschied macht, weil 0+0=0-0=0))Habe das ganze jetzt mal für A(0|4) durchgespielt: Für A ergibt sich beispielsweise: für die 7 Gleichungen ergibt sich dann: y2=44; y3=5;y5=15;y7=4 (nach obiger Reihenfolge) y1=y4=y6=0 Weil hier also 3 Nebenbedingungen mit Gleichheit erfüllt sind und keine Schlupfvariable negativ ist, also die Nichtnegativitätsbedingung erfüllt ist, handelt es sich (nach meiner obigen Definition) auch rechnerisch um eine ausgeartete Ecke. Das Verfahren müsste ich jetzt noch auf die anderen (vermeintlichen) Ecken anwenden: Handele es sich um eine "normale" Ecke, dann würden alle Schlupfvariablen nichtnegativ sein und 2 0. Handele es sich um eine zulässige Ecke, dann würden alle Schlupfvariablen nichtnegativ sein und eine 0. Handele es sich um eine nicht zulässige Ecke, dann würde mindestens eine Schlupfvariable negativ sein und damit die Nichtnegativitätsbedingung nicht erfüllen! Habe ich das richtig verstanden? 
|
||
| 13.01.2020, 17:55 | hawe | Auf diesen Beitrag antworten » |
Bist Du Dir sicher mit den Nebenbedingungen x1 + x2 <= 9 3x1 + 3x2 <= 27 ist jetzt nicht wirklich eine sinnvolle Zusammenstellung. Wie in dem Tableau gezeigt berechnest Du die Schlupfvariablen si. Normalerweise beginnt das Standardtableau bei D=(0,0) dann müssten die si dem Vektor b (rechte Seite der NB) entsprechen. Das Tableau: A x = b ==> A (x,y,s1,s2,s3,s4,s5) = b (A,b kommen aus den NB+Schlupfvariablen si) Betrachte den Lösungsvektor x 2 xi = 0 Schnittpunkt (Ecke) alle weiteren xi >=0 gültige Ecke (da könnte man nach der Zielfunktion schauen und max als Lösung präsentieren) 1 xi=0 irgendwo auf dem Rand des Lösungsgebietes (auf einer NB Geraden oder Achse) - keine Ecke Es gibt xi<0 (betrifft si) irgendwo außerhalb des Lösungsgebietes Alle xi >0 irgendwo innerhalb des Lösungsgebietes Die si stellen die Restressoucen der durch die NB beschriebene Ressource dar. Das Verfahren ist übrigens in den Link auf die ggb-App umgesetzt. |
||
| 13.01.2020, 18:46 | Matrickser | Auf diesen Beitrag antworten » |
Ja, die Nebenbedingungen stimmen so, dient wahrscheinlich bei der Besprechung dann zur Veranschaulichung, dass man nur wirklich das Ergebnis beeinflussende NB benutzen sollte, um sich Rechenarbeit zu sparen. Die Schlupfvariablen habe ich ja jetzt für A berechnet und die richtige Schlussfolgerung daraus gezogen, oder? (x nichtnegativ , was du angibst, ist ja durch die Nichtnegativitätsbedingung bereits festgelegt
) |
||
| 13.01.2020, 20:14 | hawe | Auf diesen Beitrag antworten » |
Ja, deswegen braucht es auch keine Schlupfvariablen dafür, aber für das Auffinden der Ecken sind auch Achsenschnittpunkte x=0 V y=0 zu betrachten - z.B: (5,0) Dann würd ich eine der beiden doppelten NB/Grenzgeraden streichen, weil die die Auswertung stören Du bekommst identische Aussagen dafür. z.B: (4,5) die dann gedanklich immer zusammenzufassen sind und ggf. eine Ecke versprechen wo keine ist! |
||
| 13.01.2020, 20:41 | Matrickser | Auf diesen Beitrag antworten » |
Ok, also noch mal zu meinem Verständnis zusammengefasst: ich streiche die 5. Nebenbedingungen (weil 3mal die 3.) und Schlupfvariablen für die Nichtnegativitätsbedingungen an x sind nicht nötig, weil eh nur 0 möglich wäre. Ansonsten kann ich aber mein Verfahren für A (unter Ausschluss von y5) für alle weiteren Punkte anwenden: Punkt in Gleichungen mit Schlupfvariablen y1-y4 einsetzen - schauen, wie viele Nebenbedingungen mit Gleichheit erfüllt sind und ob Schlupfvariablen negativ - Fallunterscheidung für vermeintliche Ecken (siehe vorletzter Post unten) Stimmts?
|
||
| 13.01.2020, 21:04 | hawe | Auf diesen Beitrag antworten » |
Ich würde Ergänzungen anbringen: Schlupfvariablen für x>0 & y>0 sind nicht nötig, weil wir den Lösungsvektor im ganzen betrachten und das LP bei (0,0) starten, uns in Richtung auf eine Lösung si>=0 bewegen. NB in Gleichungen überführen durch Einbringen von Schlupfvariablen si , i=1..4. Gleichungen umstellen si=fi(x,y) Lösungsvektor zusammen bauen X={x,y,f1(x,y),f2(x,y),f3(x,y),f4(x,y)} A,B,C,D,E € X und auswerten wie besprochen... |
||
|
|
