Hallo,
ich weiss das es zu diesem Thema jede menge Beiträge schon gibt.
Ich habe Sie alle durchgeschaut, nur verstehe ich diese Methode immer noch nicht.
Ich hoffe das bei mir noch nicht alles verloren ist.
Wir nehmen dieses Thema gerade durch und haben auch dazu ein Script mit den Austauschregeln erhalten.
Aufgabeeckungsbetrag Produkt A -300 und Produkt B -500
und mein 1. Tableau sieht folgendermaßen aus:
X1 X2
Z -300 -500
Y1 1 2 170
Y2 1 1 150
Y3 0 3 180
Forum
Lineare Optimierung - Simplex Methode
Gesperrt
Seite: 1
Autor | Beitrag |
---|---|
#1 13.01.2009 00:42 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
|
#2 13.01.2009 00:46 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
1. Pivotelement auswählen:
Pivotspalte: Der grösste Negative Wert der Zielfunktion gibt die Pivotspalte an also -500 Pivotzeile: Nach Bildung des Quotienten (rechte Spalte dividiert mit Pivotspalte) Der kleinste Wert gibt die Pivotzeile also 180 / 3 = 60 |
#3 13.01.2009 00:51 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Somit ist die 3 bei X2 und Y3 mein Pivotelement
Nun zu den Autauschregeln: (Ich habe ein Komma als Spaltentrennzeichen eingefügt!!) 1. Das Pivotelement geht in seinen Kehrwert über 3= 1/3 X1, X2 Z -300, -500, 0, Quotient (Q) Y1 1, 2, 170, 85 Y2 1, 1, 150, 150 Y3 0, 1/3, 180, 60 Muss man nun X2 unbd Y3 tauschen? 2. Die übrigen Elemente der Pivotzeile sind mit dem Pivot zu dividieren: Diese Zahlen werden unter das Tableau geschrieben und Kellerzeile genannt. X1, Y3, Z -300, -500, 0, Quotient (Q), Y1 1, 2, 170, 85, Y2 1, 1, 150, 150, X2 0, 3, 180, 60, Kellerzeile 0, 1/3, 60, Muss hier auch etwas getauscht werden? |
#4 13.01.2009 00:58 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
3. Die übrigen Elemente der Pivotspalte sind mit dem Pivot zu dividieren und mit den entgegengesetzten Vorzeichen zu versehen:
X1, Y3, Z -300, -500/3 Vorz. = 500/3, 0, Quotient (Q) Y1 1, 2 / 3 =Vorz. = -2/3, 170, 85 Y2 1, 1 / 3 =1 Vorz. = -1, 150, 150 X2 0, 3, 180, 60, Kellerzeile 0, 1/3, 60 Ergebnis: X1, Y3, Z -300, 500/3, 0, Quotient (Q) Y1 1, -2/3, 170, 85, Y2 1, -1, 150, 150, X2 0, 3, 180, 60, Kellerzeile 0, 1/3, 60, |
#5 13.01.2009 01:02 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Wie geht es nun weiter?
Die 4. Regel besagt : Alle übrigen Elemente werden wie folgt transformiert: Man subtrahiert von Ihnen das produkt, welches aus dem zugehörigen Element der Kellerzeile und dem in gleicher Höhe stehenden Element der Pivotspalte gebildet wird. Hier weiss ich nicht mehr weiter. Bis hier weiss ich auch nicht, ob nach jeder Regel auch die Variablen X und Y getauscht werden. Ich denke das nach der 4. Regel der Pivot neu gebildet wird, solange ausgeführt bist in der Zielfunktion keine negativen Werte mehr enthalten sind. Falls mir jemand helfen kann, wäre ich sehr dankbar. Gruß |
#6 13.01.2009 10:22 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
Hast Du Dir denn mein Skript und mein Simplex-Programm angeschaut? Das Programm macht es Dir doch Schritt für Schritt vor!
BItte schreibe Dein Optimierungsproblem hier erstmal in Gestalt von Gleichungen auf; aus den Zahlen oben werde ich nicht schlau. Wie gesagt habe ich den Verdacht, daß Du eigentlich nicht Simplex, sondern was ganz Anderes machst... |
#7 13.01.2009 20:59 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Ich habe den Kurs Prduktionswirtschaft und das Thema ist
Lineare Optimierung - Simplexmethode Die Gleichúng ist: Zielfunktion: Z - 300 X1 - 500 X2 = 0 Restriktion 1 X1 + 2X2 kleiner gleich 170 1 X1 + 1X2 kleiner gleich 150 + 3X2 kleiner gleich 180 Nun gibt es die 4 Austauschregeln, die ich schon oben erwähnt habe. Pivotelement bilden, übrige elmente der pivotzeile, übrige elmente der pivotspalte, alle übrigen elemente es werden mit dieser austauschregel auch die variablen x und y getauscht. wieviele möglichkeiten, Lösungen gibt es den? Ich denke das wir von der gleichen Methode sprechen. Die Beispiele habe ich mir angeschaut. Leider kan ich den Lösungsweg nicht erkennen. Nachdem ich den Button Pivotelement auswählen gedrückt habe bekomme ich bei Z auch die Zahl 3 als Pivotelement bei nächsten Schritt berechnen schreibt er mir auch das richtige Ergebnis in die Zielfunktion. Deshalb denke ich wir reden von dem gleichen Thema. |
#8 13.01.2009 21:41 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
Hi,
wir scheinen nicht von derselben Sache zu sprechen, oder Du hast etwas seltsame Sprachregelungen. Ich kenne auch keien "Kellerzeile", aber das scheint die Zielzeile zu sein? Bei Deiner ersten Gleichung fehlt das Wichtigste:
Eine Zielfunktion in SImplex ist nie gleich null, sondern stets --> Min! oder --> Max. Wenn es sich im Deckungsbeiträge handelt, mußt Du maximieren, und bei Kosten, Materialeinsatz oder dergleichen minimieren. Hier solltest Du Dich für eine Lösung entscheiden, denn alles Weitere hängt davon ab. Ferner:
Das wären also offenbar Gleichungen: [code:1]X1 + 2X2 + Y1 = 170 X1 + X2 + Y2 = 150 3X2 + Y3 = 180[/code:1]
Ich kenne keine AUstauschregeln im Zusammenhang mit SImplex – nie gehört. Und ich habe sowas programmiert, ich hätte es also hören müssen. Es kann aber sein, daß das hier wieder ein seltsames Sprachproblem ist? ich kennen ämlich sehr wohl die Dualkonversion, aber reden wir hier von derselben Sache? Also: 1. Entscheide Dich, ob eine Minimierung oder eine Maximierung vorliegt (ich vermute eine Maximierung) 2. Wenn es wirklich eine Maximierung ist, dann lautet Dein Gleichungssystem: [code:1]X1 + 2X2 + Y1 = 170 X1 + X2 + Y2 = 150 3X2 + Y3 = 180 DB = 300 X1 - 500 X2 --> Max![/code:1] Du hast also ein Gleichungssystem mit 6 Unbekannten. Wegen der Maximierung ist eine Dualkonversion hier nicht erforderlich. Dies kannst Du mit meinem Programm häppchenweise lösen; in meinem Skript ist genau beschrieben, wie das funktioniert und was man warum machen muß. |
#9 13.01.2009 22:56 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Hallo,
leider kann ich nur das wiedergeben was ich von meinem Dozent gehört habe. Die Gleichung ist richtig, es ist eine Maximierung. Ich habe mir das Excel-Sheet z.B LPG1 angeschaut. Wie gesagt, nach dem betätigen von dem Button"Nächsten Schritt berechnen" bekomme ich auch das richtige Ergebnis. Da ich jeden Schritt einzeln durchrechnen möchte, müsste ich wissen was in dem Moment passirt wo ich den Button betätige. Z1 S1=1 Z1 S2=2 Z1 R= 170 Z2 S1=1 Z2 S2=1 Z2 R= 150 Z3 S1 =0 Z3 S2 =3 Z3 R= 180 Z S1 -300 Z S2 -500 Button Pivot auswählen betätigt Pivot =3 Nun Button "Nächsten Schritt...." Wie wird in dem moment berechnet? Ich weiss das dieser Bereich in der Programmierung ist, falls der Weg nicht angegeben werden kann verstehe ich das natürlich. Leider muss ich bei der Prüfung jeden einzelnen Schritt berechnen auch mit der Erkenntnis das es jede menge Tools und Software für die Berechnung gibt. « Zuletzt durch scadaad am 13.01.2009 23:08 Uhr bearbeitet. » |
#10 13.01.2009 23:04 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
Hi,
OK, gehen wir davon aus, daß es eine Maximierungsaufgabe ist. In diesem Fall ist keine Dualkonversion notwendig. Austauschregeln kenne ich nicht (und ich müßte sie kennen, gäbe es sie), doch wie gesagt, das kann ein Problem mit irgendwelchen seltsamen Benennungen sein. Die Ausgangstabelle in dem Programm muß sein: [code:1] 1 2 1 0 0 0 ... 170 1 1 0 1 0 0 ... 150 0 3 0 0 1 0 ... 180 ... -300 -500 0 0 0 1 ... 0[/code:1] Unverwendete Zeilen und Spalten sind hier durch ... angedeutet. Bittte verstehe, daß es nicht möglich ist, die Sache hier nochmal darzustellen. Es steht alles im Skript, Schritt-für-Schritt. Dazu mache ich solche Skripte! Bitte das Skript neben das Programm legen und die Sache einzeln rechnen. Im Skript sind auch die Divisoren hinter der Restruktions-Spalte erläutert, die das Programm berechnet und ausweist (sie dienen der Auswahl des Pivot-Elementes). Du kannst eine Bildschirmkopie des Programmes auf einen FreeProvider laden und hier verlingen. Auf diese Art kannst Du konkrete Fragen stellen. |
#11 15.01.2009 22:50 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Ich möchte mich erst einmal für die Unterstützung bedanken.
Ich weiss ja selbst das ich in meiner Noch-Unwissenheit blöde fragen stelle, aber aller Anfang ist schwer. Ich mache mich mal an das Script und melde mich dann. Gruß « Zuletzt durch scadaad am 15.01.2009 22:52 Uhr bearbeitet. » |
#12 15.01.2009 22:52 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
Bitte einfach den Links weiter oben in dieser Diskussion folgen, hatte ich schon am 12. Januar für Dich gepostet. Die ZIP-Datei ist das Programm und die PDF-Datei ist das Skript. Dort die Erläuterung Schritt für Schritt nachvollziehen, und danach hier weiterfragen...
|
#13 16.01.2009 23:12 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Hallo,
ich bin gerade am durcharbeiten vom Script und ich muss sagen es ist mir vieles klarer geworden. Nun bin ich bei der 2. Verbesserung. Der Pivot ist in Spalte X1 und Zeile wo die Restiktion den niedrigsten Wert 60 hat. Um in der ersten Spalte einen Einheitsvektor mit der 1 an der zweiten stelle zu erzeugenm muss man (-5/3) fache der zweiten zeile zur ersten, das (-1/3)fache der 2. zur dritten, das 1-fache zur vierten vorher waren es -1 und 3 wie kommen diese zahlen zustande? |
#14 16.01.2009 23:14 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
Bitte mal eine genaue Seitenangabe, damit ich auch weiß, um was es geht!
|
#15 16.01.2009 23:24 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
Sorry, Seite 9
bei der 1. Verbesserung bzw. Optimierung wird um den Pivot mit 1 zu haben alle anderen werte in der zeile mit dem kehrwert vom Pivot multipliziert. Im nächsten Schritt werden viefache der neuen dritten Zeile....... Diesen Schritt verstehe ich nicht, woher das (-1) fache von der dritten zeile zur ersten und 2. und 3 fache zur vierten zeile Bei der 2. Verbesserung ist es das (-5/3) fache von der 2. zeile zur ersten und (-1/3) fache zur dritten und das 1 fache zur letzten zeile. Woher die Zahlen und welches vielfache zur welchen Zeile. |
#16 16.01.2009 23:30 Uhr
|
|
Mitglied
Registriert: Apr 2004
Beiträge: 7407
Ort: Erfurt
|
OK, S. 9, linke Spalte, oben: erst die 2. Spalte X2 ausgewählt (wegen –3), dann durch die Divisionen S. 8 rechts unten bestimmt, daß die 3. Zeile das Pivot-Element enthalten soll. Also die 3. Zeile durch die dort an der 2. Stelle stehende 3 dividiert; Ergebnis ist die Tabelle S. 9 links oben.
Jetzt müssen in den anderen Stellen der 2. Spalte Nullen her, sonst ist das ja kein Einheitsvektor. Die restlichen Zellen der 2. Spalte sind Multiplikatoren. Also die neue 3. Zeile, die ja an der 2. Stelle schon die 1 enthält, je 1 mal von der alten 1. und der alten 2. Zeile subtrahieren und drei Mal zu der alten letzten Zeile addieren, um dort jeweils in der 2. Spalte Nullen zu zaubern. Das produziert die Zwischenlösugn auf S. 9 linke Spalte unten. Also kurze Antwort: nach der Herstellugn der 1 in der Zeile, die das Pivot-Element enthalten soll, sidn alle anderen Stellen der Spalte des Pivot-Elementes Multiplikatoren zu dieser neuen Zeile mit dem Pivot. |
#17 17.01.2009 03:01 Uhr
|
|
Mitglied
Registriert: Sep 2007
Beiträge: 17
|
So,
habe nun den Rechnungsweg mit meinem Beispiel durchgearbeitet. Das Ergebnis passt auch mit meinem Zwischenergebnis und auch dem Excel Sheet. Vielen Dank nochmal für die freundliche Unterstützung. |
Gesperrt
Seite: 1
Parse-Zeit: 0.0701 s · Memory usage: 1.50 MB · Serverauslastung: 2.18 · Vorlagenbereich: 2 · SQL-Abfragen: 9