Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Simplex-Algorithmus - allgemeine Fragen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Simplex-Algorithmus - allgemeine Fragen
werdas34
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.04.2018
Mitteilungen: 61
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-04-04


Hallo,

erst mal kurz vorneweg. Ich soll einen Vortrag halten über den Simplex Algorithmus. Dieser soll 45 min lang sein. Dazu bin ich Informatik Student(FH) und werde diesen Vortrag vor meinen Kommilitonen halten, diese ebenfalls Informatikstudenten sind.
Daher möchte ich den Vortrag auch nicht zu sehr mathematisch machen, sondern mehr praktisch halten.

Ich möchte meinen Vortrag so gestalten, dass man jede Form des Simplex anwenden kann. Heißt man soll von Maximierungs-Problem in Minimierungs-Problem umwandeln können. Genauso wenn die Nichtnegativitätsbedingung nicht erfüllt wird, oder die Nebenbedingungen nicht passend zum Problem formuliert sind. Ich habe einige Literatur und auch Internetrecherche durchgeführt und glaube alle wichtigen und notwendigen Regeln gefudnen zu haben.
Könnt ihr mir sagen, ob das wirklich alle relevanten Regeln sind und manch meiner Fragen noch benatworten?
Werde nicht die Zeit haben, die Erfahrung zu sammeln, um zu wissen welche Problematiken auftreten können.

fed-Code einblenden


Vielen Dank.

mfg werdas34



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1444
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-05


Hallo werdas34,
du hast eine Reihe verschiedener Fragen augeworfen!

2020-04-04 16:17 - werdas34 im Themenstart schreibt:
Ich habe einige Literatur und auch Internetrecherche durchgeführt und glaube alle wichtigen und notwendigen Regeln gefunden zu haben.

Es wundert mich etwas, dass du dabei nicht auf "meinen" Wikipedia-Artikel Pivotverfahren gestoßen bist (unter anderem die Abschnitte Dualität und Spezielle Pivotverfahren), welcher deine Fragen 2,6,7 zum großen Teil beantwortet.

Behalte immer im Auge, dass es nicht nur ein, sondern viele verschiedene Simplexverfahren gibt.

2020-04-04 16:17 - werdas34 im Themenstart schreibt:
fed-Code einblenden

Das ist alles mathematisch korrekt und auch machbar. Sei dir aber bewusst, dass käufliche Software (deren genaue Algorithmen zurückgehalten werden) im Namen der Effizienz ziemlich sicher nicht so vorgeht.

2020-04-04 16:17 - werdas34 im Themenstart schreibt:
2) Sei A eine Matrix welche das Minimierungsproblem darstellt (hoffe es ist klar was gemeint ist) dann kann ich mit $A^T$ dies zu einem Maximierungsproblem konvertieren.
Warum erreiche ich durch das transponieren die gegenteilige Aussage?

Du erreichst durch die negative Transposition nicht die gegenteilige Aussage sondern dieselbe Aussage: Maximierung wird zu Maximierung (Minimierung zu Minimierung funktioniert so nicht). Im Anschluss darauf wird oft deine Regel (1) angewandt, um die duale Aufgabe in ein Minimierungsproblem zu verwandeln. Warum man das tut ist mir rätselhaft.

2020-04-04 16:17 - werdas34 im Themenstart schreibt:
6) nicht eindeutig Pivotzeile -spalte wählbar? Wie da vorgehen? Kann man einfach eins auswählen, solange es die Bedingungen erfüllt?
7) Wenn auf der rechten Seite mindestens ein negativer Wert steht, dann wird der Duale Simplex oder Big M angewendet und dann der primale Simplex.

Natürlich kann man nicht "einfach eins auswählen, solange es die Bedingungen erfüllt", sonst kann man in eine Endlosschleife geraten. Es gibt mehrere Möglichkeiten das zu verhindern. Und wie so oft im Leben, ist die einfachste Möglichkeit (siehe Artikel) nicht die effizienteste.

Wenn keine zulässige Startbasis vorhanden ist, gibt es viele Methoden, eine solche zu finden, und den dualen Simplex dafür anzuwenden ist eine gute Idee. Aber wie bereits gesagt, machen Softwarefirmen ihre Algorithmen nicht öffentlich.


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
werdas34
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.04.2018
Mitteilungen: 61
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-04-05


Vielen Dank.

Mir gehts auch weniger darum, den effizientesten Fall zu finden. Mir gehts darum, dass man eine "allgemeingültige Lösung" hat. Also ich bekomme die Aufgabe und kann anhand meiner Informationen, dies lösen. Egal wie effizient die Lösung erstmal ist.

Eine abschließende Frage habe ich noch:
Wenn ich den Dualen Simplex anwende, dann bekomme ich eine zulässige Lösung. Um die optimale Lösung zu erhalten nutze ich den primalen Simplex.

Ich habe mal theoretisch den Dualen Simplex angewendet. Wende ich einfach auf dem Endtableau vom Dualen den Primalen Simpelx an ?

Finde nichts wo der gesamte Prozess beschrieben wird, sondern nur der Duale oder der Primale, aber nicht beides.

Habe nun online Rechner genutzt und da heißt es immer nach dem Dualen Simpelx der Zielwert oder die optimale Lösung wurde erreicht. Und weiß nicht genau wie ich das am besten überprüfen kann?
Verwendet wurden: und

mfg werdas34



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1444
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-04-06


2020-04-05 16:56 - werdas34 in Beitrag No. 2 schreibt:
Wenn ich den Dualen Simplex anwende, dann bekomme ich eine zulässige Lösung. Um die optimale Lösung zu erhalten nutze ich den primalen Simplex.
Ich habe mal theoretisch den Dualen Simplex angewendet. Wende ich einfach auf dem Endtableau vom Dualen den Primalen Simplex an?
Finde nichts wo der gesamte Prozess beschrieben wird, sondern nur der Duale oder der Primale, aber nicht beides.

Du wendest den Algorithmus zweimal an:

In Phase_1 ersetzt du die Zielfunktion durch $z=0$ oder durch ein beliebiges $z=\sum_{j\in D} d_jx_j$ mit $d_j\le0$ für alle $j\in D$. Somit hast du eine dual-zulässige Basislösung und kannst das duale Simplexverfahren anwenden. Entweder du findest nun eine primal-zulässige Basislösung oder es gibt keine solche und somit auch kein Optimum.
In Phase_2, falls du eine zulässige Basis gefunden hast, setzt du die ursprüngliche Zielfunktion ein, die du dafür als Funktion der unabhängigen Variablen (also der Nichtbasis-Variablen) ausdrücken musst. Dann machst mit dem primalen Simplexverfahren weiter.

So eine Aufteilung in zwei Phasen entspricht der ursprünglichen Idee von George Dantzig, und ist somit das eigentliche "Simplexverfahren". Es gibt aber auch die "Criss-Cross-Verfahren", welche viel einfacher zu beschreiben und nicht unbedingt langsamer sind.

Ein wichtiger Rat:
Arbeite in deinem Vortrag mit Gleichungssystemen und nicht mit Tableaus, sonst versteht 70% deiner Zuhörer nur noch 30% von dem was du sagst.

2020-04-05 16:56 - werdas34 in Beitrag No. 2 schreibt:
Habe nun online Rechner genutzt und da heißt es immer nach dem Dualen Simplex der Zielwert oder die optimale Lösung wurde erreicht. Und weiß nicht genau wie ich das am besten überprüfen kann?
Verwendet wurden: und

Danke für die Hinweise auf diese Weborte; ich werde sie mir ansehen und melde mich dann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
werdas34
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.04.2018
Mitteilungen: 61
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-04-23


Vielen Dank für deine Antwort.

Mein Vortrag soll den Simplex Algorithmus beschreiben. Daher wird das Criss-Cross Verfahren höchstens erwähnt.

Wie genau meinst du das mit dem Gleichungssystem ? Worin siehst du da den Vorteil ?
Z.B wenn ich die "Gauss-Elementationen" anwende, dann habe ich eine ähnliche  "Tabelle". Denke mal das führt nicht zur Verwirrungen. Solange man die Schlupfvariablen nicht mit x benennt, da man sonst zu den anderen nicht mehr unterscheiden kann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1444
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-04-24


2020-04-23 11:05 - werdas34 in Beitrag No. 4 schreibt:
Mein Vortrag soll den Simplex Algorithmus beschreiben. Daher wird das Criss-Cross Verfahren höchstens erwähnt.

Für einige Menschen (nicht für mich) ist jedes Basisaustauschverfahren ein "Simplexalgorithmus". Frag deinen Übungsleiter doch einmal, wo er die Grenze zieht.

2020-04-23 11:05 - werdas34 in Beitrag No. 4 schreibt:
Wie genau meinst du das mit dem Gleichungssystem ? Worin siehst du da den Vorteil?
Z.B wenn ich die "Gauss-Elementationen" anwende, dann habe ich eine ähnliche  "Tabelle". Denke mal das führt nicht zur Verwirrungen. Solange man die Schlupfvariablen nicht mit x benennt, da man sonst zu den anderen nicht mehr unterscheiden kann.

Wenn Tableaus für dich klarer sind, dann verwende sie. Wenn ich (und einige meiner Studenten) durch solche Datenstrukturen verwirrt wurden bedeutet das nicht unbedingt, dass es anderen auch so geht. Nur definiere deine Tableaus immer vorher, und setze nicht voraus dass sie allen bekannt sind.

Schlupfvariablen unterscheidet man von den Strukturvariablen indem man ihnen verschiedene Indizes gibt. Für die Schritte von Simplex-Algorithmen ist oft eine Reihenfolge der Variablen relevant, nicht die Unterscheidung zwischen den Arten von Variablen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
werdas34 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]