Diskussion:Simplex-Verfahren

aus Wikipedia, der freien Enzyklopädie

Bitte etwas mehr Sorgfalt!

Die Algorithmen von Khashian und von Karmarkar haben absolut gar nichts mit dem Simplex-Verfahren zu tun. --Goswin

Dieser Artikel kann noch wesentlich verbessert und erweitert werden:

• mit der Beschreibung im Beispiel, wie man ein Pivotelement auswählt, bin ich nicht ganz glücklich.
• graphische Darstellung der Lösung
  Hier kann man mit Bildern zeigen, dass die Lösung in eineer Ecke liegt.
• Mathematische Darstellung und Hintergründe
  Da muss mit Vektoren und Matrizen gerechnet werden.
• duales Simplex-Problem
• Spezielle Formen der Simplex-Methode (revidierte Simplex-Methode)
• Anwendungen (vermutlich in eigenen Artikeln - Titelname?)
  • Transportproblem
  • ganzzahlige Nebenbedingungen

...

-- tsor 21:25, 17. Jan 2004 (CET)

Ich bin mit manchem dieser Punkte nicht einverstanden. Und ich würde mir auch in der Diskussion etwas mehr Sorgfalt wünschen:

• Ein "duales Simplex-Problem" existiert gar nicht. (Ist vielleicht das duale Simplex-Verfahren gemeint?)
• Die "revidierte Simplex-Methode" ist eine (inzwischen veralterte) Rechenimplementierung des ursprünglichen Simplexverfahrens. Wenn wir auf Rechenimplementierungen überhaupt eingehen wollen, dann bitte einen Gesamtüberblick, bei dem die wichtigsten nicht unter den Tisch fallen.
• Das Transportproblem gehört in den Artikel "Lineare Optimierung" und nicht hierher.
• Ganzzahligkeits-Nebenbenbedingungen (und nicht ganzzahlige Nebenbedingungen) als Anwendung verlangen derartig viele zusätzliche Erklärungen, dass sie die Beschreibung des Simplex-Verfahrens eher verdunkeln als verdeutlichen.

--Goswin

Inhaltsverzeichnis 1 Summen-Notation statt Vektor-Notation 2 Lösungen innerhalb des Polyeders 3 Beispielrechnung 4 Anwendungsgebiete 5 Dualer Simplexalg. 6 Dualer Simplexalgorithmus 7 Löschen von Vorschlägen 8 Name des Simplex-Verfahrens 9 Motivation für den dualen Simplex 10 Fehler in Formel 6 der Beschreibung der Simplex-Iteration? 11 Laufzeit 12 der Pseudocode ist ja wohl nicht ernst gemeint 13 Minimierung vs. Maximierung 14 Ecke

[Bearbeiten] Summen-Notation statt Vektor-Notation

Meine Vorlesungs-Erfahrung zeigt mir, dass "Mathematik-Omas" (:-) die Summen-Notation besser verstehen als die Vektor-Notation. --Goswin

Meine Vorlesungserfahrung zeigt mir, dass man immer mit einem kleinen Beispiel beginnen sollte, anhand dessen man die Notation usw. erklärt, etwa

Eine Unternehmung produziert zwei Güter X1 und X2. Ihre Gewinnfunktion ist

G = 36000 - 300x1-500x2.

Ihr Ziel ist es, diese Funktion zu maximieren, deshalb nennen wir sie Zielfunktion. In der Produktion ist sie jedoch gewissen Beschränkungen unterworfen

die Nebenbedingungen....

so dass wir das Standardproblem des Simplex erhalten:

Hier das ganze als Gleichungssystem.

Dann Zusammenfassung im Vektorkalkül.

Man kann speziell im Mathematik-Bereich eine gewisse Affinität mancher zur Profilierung nicht leugnen. ;-) --Philipendula 14:46, 22. Sep 2004 (CEST)

[Bearbeiten] Lösungen innerhalb des Polyeders

(Von Philipendula 00:33, 7. Jan 2005 (CET)aus ihrer Diskussionsseite übertragen) Natürlich kann es auch optimale Lösungen (Punkte mit maximalem payoff) geben, die nicht auf einer Ecke liegen.

Beispiel: x1,x2>=0; x1,x2 <= 1; Auszahlfunktion f(x1,x2) = x1;

Alle (x1,x2) mit x1=1 sind optimale Lösungen, aber nur (1,0), (1,1) sind Ecken.

Im (zugegeben entarteten) Fall, daß die Auszahlungsfunktion konstant ist, gibt es sogar optimale Lösungen im (topologischen) Innern des Polyeders. 217.81.145.134 15:03, 6. Jan 2005 (CET)

Ich hatte schon immer mal vor, auch entartete Lösungen hier mit einzubringen, aber ich war bisher zu bequem, weil ich erst mal die Art der Darstellung des Simplextableaus hätte analysieren müssen (es gibt vermutlich so viele wie C4-Lehrstühle bei uns). --Philipendula 00:33, 7. Jan 2005 (CET)

Vorsicht, das hat nichts mit entarteten Basislösungen zu tun, das entartet hier ist mehr umgangssprachlich und bezieht sich darauf, daß wohl kaum jemand absichtlich ein LP aufbaut und zu lösen versucht, wenn die Auszahlfunktion konstant ist. Das wird aber in der Definition des LPs im Artikel nicht ausgenommen, und dann ist jeder Punkt im Polyeder eine optimale Lösung. 217.81.145.134 01:34, 7. Jan 2005 (CET)

Die Aussage wie sie im Text stimmt, ist aber trotzdem richtig: es gibt eine Ecke, die optimale Lösung ist. Was soll die Diskussion? --DaTroll 18:21, 7. Jan 2005 (CET)

Nun, es werden hier zwei Sichtweisen vermanscht:

• Der Simplexalgorithmus als technisches Verfahren, das lediglich eine Ecke sucht und zufrieden ist
• Eine anwendungsorientierte Sicht, die versucht, ein beispielsweise betriebswirtschaftliches Optimum zu finden, eine Synthese zwischen produktionstechnischen Restriktionen und einer Zielfunktion. In diesem Fall sind eben Lösungen im Polyeder auch zulässig; sie sind eben nur nicht optimal, bis auf den durch den Benutzer 217.81.145.134 geschilderten, etwas pathologischen Fall. Der Simplexalgorithmus würde eine Lösung im Innern nicht finden, die pathologische Lösung vielleicht schon, weil ja die Restriktionen hier eine Ecke bilden, wenn ich die Angaben richtig verstanden habe. Die betriebswirtschaftliche Konstellation gehört aber vielleicht nicht hierher, sondern wäre eine Anwendung für Preisbildung bei Kostenrechnung o.ä. --Philipendula 22:06, 7. Jan 2005 (CET)

[Bearbeiten] Beispielrechnung

Hab da eine kleine Frage: falls ich das alles richtig verstanden habe, sollte doch in der Lösung der Beispielrechnung Maschine C 120 Stunden still stehen und 60 Stunden arbeiten (um nämlich genau 20 Einheiten von Produkt 2 herzustellen)? Ich will da jetzt nicht einfach drin rumpfuschen und frag deswegen.

Absolut korrekt! Werde im Laufe des Tages noch ein paar weitere Korrekturen und Verdeutlichungen einfügen. Das Beispiel kommt dann ans Ende des Artikel, damit die beiden kleinen aber interessanten Punkte - für die mathematisch nicht so interessierten Leser - nicht unter den Tisch fallen. --mirer 14:45, 2. Feb 2005 (CET)

[Bearbeiten] Anwendungsgebiete

• Ganzzahlige Nebenbedingungen

Wird von einer oder mehreren Variablen Ganzzahligkeit gefordert, dann löst man das Problem mit Hilfe des Simplex-Verfahrens zunächst ohne die Ganzzahligkeits-Bedingung. Ist die erhaltene Lösung nicht ganzzahlig, dann schneidet man diese Lösung weg, indem man geeignete Nebenbedingungen hinzufügt. Danach wiederholt man das Simplex-Verfahren. Bekannte Verfahren sind Cutting-Plane-Verfahren von Gomory und die Methode Branch and Bound.

• Transportprobleme
• Approximationstheorie

Probleme der diskreten linearen l₁-Approximation sowie Probleme der diskreten Tschbyscheff-Approximation lassen sich so umformulieren, dass man sie mit dem Simplex-Verfahren lösen kann.

Das habe ich so mal ganz aus dem Artikel rausgenommen. Sollte erst sinnvoll formuliert wieder eingestellt werden. Momentan ist am ehesten eine sinnfreie Sammlung von Stichpunkten, die man mit Sipmlex in Verbindung bringen kann. --mirer 16:03, 2. Feb 2005 (CET)

Es ein paar weitere Varianten der Lösung des Simplex Algorithmus. Alle mir bekannten führen letzten Endes zum selben Ergebnis. Ich halte Folgende Variante für sehr leicht anwendbar: Auswahl des Pivotelements 1. In der Zielfunktionszeile sucht man den niedrigsten Wert (hier: -500). Die Spalte, in der sich dieser Wert befindet ist die Pivot-Spalte (Pivotspalte im Beispiel: -500, 2, 1, 3). 2. Jetzt teilt man die bi durch die zugehörigen Elemente der Pivotspalte (also b1:2= 170:2= 85; b2:1= 150:1= 150; b3:3= 180:3= 60). Der niedrigste Wert hier ist b3:3= 60. Die Zeile, in der sich dieser Wert befindet ist die Pivot-Zeile. Wichtig: Werte bi:i < 0 oder bi:i ohne Lösung dürfen nicht bei der Auswahl der Pivotzeile berücksichtigt werden. Nur der kleinste positive Wert bi:i "markiert" die Pivotzeile. 3. Das Pivotelement der Kreuzungspunkt von Spalte und Zeile. Im Beispiel ist die Pivotspalte die x2-Spalte, die Pivotzeile ist die b3-Zeile. Also ist das Pivotelement der Wert 3.

Das Pivotelement weicht von dem im Beispiel ab - das tut der richtigen Lösung jedoch keinen Abbruch. Der Weg verläuft auch etwas anders, ist aber nach meiner Ansicht etwas leichter anzuwenden, für den Fall dass man die Lösung per Stift und Taschenrechner sucht.

[Bearbeiten] Dualer Simplexalg.

Fehlt nicht der duale Simplexalgorithmus??? Kann jemand dazu etwas schreiben, auch wann man statt des primalen den dualen Simplex verwendet?

[Bearbeiten] Dualer Simplexalgorithmus

Der duale Simplexalgorithmus unterscheidet sich vom primalen Simplexalgorithmus, nur darin, ob die reduzierten Kosten (der Vektor oben im Tableau) und die aktuelle Basislösung (der Vektor rechts im Tableau) gewissen Nichtnegativitätseigenschaften genügen. Ein Tableau heisst primal zulässig, wenn die aktuelle Lösung nicht negativ ist, und dual zulässig, wenn die reduzierten Kosten nicht negativ sind. Optimal ist eine Lösung genau dann, denn sie primal und dual zulässig ist. Geometrisch bedeutet das, dass der primale Algorithmus über Ecken (Schnitt von n unabhängigen Gleichungen) läuft, die zum Polyeder gehören, und der duale Simplexalgorithmus über solche Schnitte läuft, welche ausserhalb liegen. Dazu schreibe ich vieleicht noch etwas konkreteres, wenn ich Zeit finde.

Im ersten Kommentar steht, dass es kein duales Problem gibt. Das ist nicht korrekt. Zu einem linearen Optimierungsproblem erhält man das duale Problem, wenn man die Problemmatrix transponiert, Zielfunktion und rechte Seite vertauscht. Aus vorzeichenbeschränkten Variablen werden Ungleichungen, ansonsten Gleichungen. Aus Ungleichungen werden vorzeichenbeschränkte Variablen, ansonsten nicht Vorzeichenbeschränkte. Das Duale des dualen Problems ist wieder das Primale. Wenn eines der beiden Probleme ein (endliches) Optimum besitzt, dann besitzt auch das andere ein endliches Optimum und die Zielfunktionswerte sind gleich. Ist ein Problem unbeschränkt, dann ist das andere leer. Dann gibt es da noch ein Paar Sachen mit dem sogenannten komplementären Schlupf. Auch das kann ich mal genauer erläutern und ein Beispiel angeben.

[Bearbeiten] Löschen von Vorschlägen

alle meine bisherigen Linkvorschläge wurden von Wikipedia kommentarlos gelöscht.

Und einem solchen Verein sollte ich doch bitte beitreten und unterstützen.

Offenbar steht Eigennutz im Vordergrund.

Im Gegenzug werde ich alle anderen Links von Wikepedia zu mir nicht mehr zulassen

Heinz Becker

Einfach mal Wikipedia:Weblinks lesen. Wir listen nur das beste vom Besten und der Beispielrechner zur Lösung von Simplex-Verfahren gehört da nicht unbedingt zu. --DaTroll 17:52, 29. Jan 2006 (CET)

Hallo Heinz, der Link wurde nicht von Wikipedia gelöscht, sondern von mir. Das ist nicht geschehen, um dich zu ärgern, sondern die Begründung hat DaTroll schon geliefert. Abgesehen davon, dass in der Beschreibung des Links Vorschlag, ansonsten löschen stand, was ich einfach mal ernst genommen habe, bringt die verlinkte Seite keine neuen Erkenntnisse. Weblinks in WP-Artikeln sollen aber weiterführende Informationen bereitstellen. Gruß, -- Sdo 18:27, 29. Jan 2006 (CET)

hbnweb.de steht für Wiki nicht mehr zur Verfügung 01.02.06 HB

[Bearbeiten] Name des Simplex-Verfahrens

"Der Name rührt daher, dass die Gleichungen des Problems ein Simplex beschreiben, dessen Rand zum Auffinden der Lösung beschritten wird." Aber die Gleichungen beschreiben doch i.A. gar kein Simplex, sondern ein Polyeder. Natürlich gibt es diesen Spezialfall, aber es gibt doch überhaupt keinen Grund, warum die Ecken des zulässigen Bereichs affin unabhängig sein sollten. Dann wäre das Problem ja gleich viel einfacher...

Ja, stimmt, danke für den Hinweis. Ich habe das erstmal auskommentiert und werde versuchen herauszufinden, wo der Name genau herkommt. -- Sdo 11:31, 14. Feb 2006 (CET)

Hallo. Bin mir ziemlich sicher, dass bei Danzig zu der geometrischen Interpretation des Simplexverfahrens steht, dass der Schritt, bei dem während der Pivotoperation die neue Basisvariable aus der Zielfunktionszeile entfernt (und damit die anderen relativen Kostenkoeffizienten verändert werden) geometrisch der Aufstellung der Lösungsgraden(im 2dim) oder Lösungsebene (im 3dim)und anschliessendem Einsetzen der Basisvariablen zur Bestimmung der relativen Lage anderer Basislösungen gleichkommt. Dies ist dann geometrisch ein Ndimensionaler Simplex...also im 2dim bilden Lösungsgerade und die jeweilige betrachtete Basislösung ein Dreieck, im 3dim die Lösungsebene und eine jeweilige betrachtete Basislösung ein Tetraeder. Ich könnte mir gut vorstellen, dass der Name daher kommt, dass man in den Einzelschritten des Verfahrens eben diese Ndimensionalen Simplizes überprüft.

Das habe ich zwar gerade nicht genau verstanden, aber ich habe den Satz trotzdem wieder einkommentiert: in Gleichungsform beschreiben die Beschränkungen wirklich einen Simplex. Dass das Problem trotzdem nicht trivial zu lösen ist, liegt vermutlich an der hohen Anzahl der Ecken dieses Simplex. -- Sdo 21:25, 18. Apr 2006 (CEST)

[Bearbeiten] Motivation für den dualen Simplex

(hierher verschoben von Diskussion:Lineare Optimierung)

Welche Gründe gibt es eigentlich, in einem Solver statt des primalen den dualen Simplex zu benutzen? Zunächst entsteht ja durch die Transformation vom primalen zum dualen Problem Mehraufwand. Ist der duale Simplex in bestimmten Fällen schneller oder benötigt er weniger Speicherplatz? M.E. müsste die Anzahl der Nullen in beiden Matrizen gleich groß sein. Oder gibt es andere Gründe, die ich übersehe? Vielen Dank! Signaturnachtrag: Benutzer:145.254.110.41 -- Sdo 23:30, 1. Mär 2006 (CET)

Da gibt es mehrere Gründe. Erstmal muss das Problem nicht transformiert werden, sondern der duale Simplex läuft im selben Tableau ab wie der primale (auch wenn das in richtigen Implementierungen nicht wirklich im Tableau passiert). Gegenüber dem primalen Simplex sind dann Zeilen und Spalten vertauscht, ansonsten läuft im wesentlichen alles gleich ab. Der primale Simplex behält immer eine zulässige Primallösung und versucht, die duale Lösung zulässig zu machen; beim dualen Simplex ist es andersherum. Zum Lösen eines einzelnen LPs ist der duale Simplex in der Praxis oft schneller als der primale. Warum das so ist, weiß ich auch nicht, aber das steht schon auf meiner Liste der rauszukriegenden Dinge. Den größten Vorteil hat der duale Simplex aber im Zusammenhang mit Schnittebenenverfahren oder Branch-and-Bound: dabei wird eine zusätzliche Bedingung ins LP geschrieben oder eine Variablenschranke verändert, so dass die aktuelle Primallösung unzulässig wird, während die Duallösung zulässig bleibt. Mit dem primalen Simplex müsste man jetzt von vorne starten, während man mit dem dualen Simplex meist nur ein paar Schritte von der aktuellen Basis aus machen muss, um wieder zu einer zulässigen Primallösung zu kommen. Ich hoffe, das hilft dir weiter. Gruß, -- Sdo 23:30, 1. Mär 2006 (CET)

[Bearbeiten] Fehler in Formel 6 der Beschreibung der Simplex-Iteration?

Sollte da statt nicht stehen? IANAM aber ich wüsst nicht, wo ich hier ein a_is herbekommen soll ;) Wenn mich niemand eines besseren belehrt, werd ichs in den nächsten Tagen mal ändern...

Klingt sinnvoll, danke. Ich hab's gleich mal geändert. -- Sdo 13:48, 20. Mär 2006 (CET)

---

Moin, muss da nicht anstatt dem arj ein ajs hin???

Hab da nicht wirklich Ahnung von, häng da aber jetzt 2h vor und kann mir das nur so erklären...

Grüße, Ole

Moin Ole, nach meinen alten Aufzeichungen aus der LinOpt-Vorlesung und nach dem, was ich mir gerade auf einem Blatt Papier zusammengebastelt habe, stimmt weder deine Version noch die im Artikel. Es sollte meiner Meinung nach

heißen. Das passt auch mit dem Beispiel zusammen, sowie mit der Bemerkung zur Berechnung von G direkt unter Formel (6). Ich habe das im Artikel entsprechend geändert. Gruß, -- Sdo 00:15, 5. Jun 2006 (CEST)

[Bearbeiten] Laufzeit

Sollte im Artikel nicht erwaähnt werden, dass der Algorithmus im worst-case exponentiellen Aufwand erfordert ? (Vorstehender nicht signierter Beitrag stammt von 89.57.159.208 (Diskussion • Beiträge) -- Sdo 23:44, 2. Jul 2006 (CEST))

Ja, auf jeden Fall – danke für den Hinweis! Hab's eingebaut. -- Sdo 23:44, 2. Jul 2006 (CEST)

[Bearbeiten] der Pseudocode ist ja wohl nicht ernst gemeint

ich habe mir mal den pseudocode angesehen - der ist ja wohl ein witz! das ist nicht das Simplex verfahren, sondern EINE EINZELNE pivotisierung der matrix

das wird zwar bei den verschiedenen Simplex verfahren ständig gemacht, aber die kunst ist, die pivot elemente auszuwählen!

das ist in etwa so, als würde man eine zeilen-addition als gauss algorithmus bezeichnen oder als würde man eine modulo-rechnung als euklidischen algorithmus bezeichnen... (Vorstehender nicht signierter Beitrag stammt von AlgorithMan (Diskussion • Beiträge) 20:13, 3. Sep 2006)

Ja, da hast du vollkommen recht. Ich bin gerade dabei, den Artikel offline gründlich zu überarbeiten. Entweder fliegt der Pseudocode dabei raus oder ich benenne ihn richtigerweise als einzelnen Simplexschritt, das weiß ich noch nicht genau. Ich werde die überarbeitete Version einstellen, sobald ich sie als Artikel bezeichnen kann (spätestens in ein paar Tagen). -- Sdo 21:00, 3. Sep 2006 (CEST)

[Bearbeiten] Minimierung vs. Maximierung

hierher verschoben von Portal_Diskussion:Mathematik -- Sdo 22:09, 14. Okt. 2006 (CEST)

Wollte gerade mal gucken, was es in der Wikipedia so Schönes zum Thema Simplex-Algorithmus gibt. Fand z.b. das hier. Jetzt dachte ich eigentlich immer, dass das Standardproblem des Simplex-Verfahrens durch die Maximierung der Zielfunktion beschrieben wird, nicht die Minimierung. Jaaa, ich weiß, das man mit der dualen Form immer auch ein Minimum hinkriegt. Oder hab ich die Formel im Artikel falsch aufgefasst? Für einen Normalstudenten ist so ein Durcheinander jedenfalls eine Katastrophe. --Philipendula 22:21, 13. Okt. 2006 (CEST)

Als ich mich noch damit befasst habe [1] war von einer Maximierung die Rede. Naja, wenn Du die zu minimierende Zielfunktion mit -1 multiplizierst erhaltst Du auch ein Maximierungsproblem. -- tsor 22:29, 13. Okt. 2006 (CEST)

Ja, scho klar. Es hat bestimmt auch seinen Sinn, ein Minimierungsproblem draus zu machen. --Philipendula 22:40, 13. Okt. 2006 (CEST)

Den Artikel habe ich neulich zusammen mit der Linearen Optimierung gründlich überarbeitet und erweitert. Ich will nicht ausschließen, dass mir dabei irgendwelche Fehler unterlaufen sind. Aber ich verstehe gerade euer Problem nicht. Ob man maximiert oder minimiert, ist doch letztlich egal, siehe Anmerkung von Tsor. Mit dem dualen Problem hat das erstmal nichts zu tun, nur mit dem Vorzeichen der Zielfunktion. Ich gebe allerdings zu, dass der Artikel etwas konsequenter eine Variante beibehalten könnte. Ich schreibe es auf meine todo-Liste... -- Sdo 01:09, 14. Okt. 2006 (CEST)

Ok, das geht wirklich durcheinander. Ich kümmere mich morgen darum. -- Sdo 01:12, 14. Okt. 2006 (CEST)

Es ist so, dass man überall liest, dass das Standardproblem des SA Maximierung der Zielfunktion und nach oben beschränkte Nebenbedingungen sind. Jede andere Fragestellung kann man mit Hilfe von Hilfsvariablen auf diese Art zurückführen. --Philipendula 14:16, 14. Okt. 2006 (CEST)

Ich habe schon sowohl Darstellungen mit Minimierung als auch welche mit Maximierung gesehen. Insbesondere verwendet das Vorlesungsskript, das ich als Spickzettel benutzt habe, die Minimierungsvariante, und auch die Beispielrechnung führt das Problem letztendlich auf Minimierung zurück, so dass ich mich für diese Variante entschieden habe. -- Sdo 18:42, 14. Okt. 2006 (CEST)

Na, wenn das Beispiel eine Minimierung der Zielfunktion darstellt, dann habe ich offensichtlich große Verständnisdefizite. Ich habe jedenfalls schon x Bücher über Operations Research und Artverwandtes gelesen, da war Maximierung immer der Standardfall. Aber eigentlich ist mir so etwas mittlerweile gleichgültig :-). Lass es ruhig so. --Philipendula 19:00, 14. Okt. 2006 (CEST)

Das Beispiel sah auf den ersten Blick wie Maximierung aus, hatte aber das Negative der Zielfunktion in der obersten Zeile des Tableaus stehen und war damit zum Minimierungsproblem mutiert, bei dem die reduzierten Kostenkoeffizienten am Ende nichtnegativ sein mussten. Das war auch verwirrend. Ich habe jetzt den ganzen Artikel inklusive Beispiel auf Maximierung umgestellt, um die Sache zu vereinheitlichen. -- Sdo 22:09, 14. Okt. 2006 (CEST)

Die Zielfunktion ist ja der Gewinn. Die Koeffizienten sind die Stückgewinne. Da im Tableau die Variablen links stehen und die Konstanten (hier die Fixkosten) rechts stehen, ergeben sich die negativen Vorzeichen durch Umstellung. --Philipendula 00:27, 15. Okt. 2006 (CEST)

In den meisten Mathematik-Büchern wird das Minimierungsproblem behandelt, z.B. in Geiger/Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben oder in Jarre/Stoer: Optimierung. In OR-Büchern für Wirtschaftswissenschaftlicher wird das Problem meistens als Maximierungsproblem behandelt. Andim 12:37, 15. Okt. 2006 (CEST)

Es ist ja auch völlig egal, welche Variante man nun betrachtet. Man muss nur die reduzierten Kosten entsprechend anpassen. @Philipendula: Die reduzierten Kosten geben die Veränderung der Zielfunktion pro Einheit der Noch-nicht-Basisvariablen an und sollten daher bei einem Maximierungsproblem positiv sein, wenn die Variable ein Kandidat für die Spaltenauswahl sein soll. Durch die Umstellung der Zielfunktion im Beispieltableau waren sie negativ. Geht zwar auch, ist aber etwas unintuitiv. Aber ist ja auch egal, ich habe es ja jetzt geändert. Wir führen hier gerade eine Pseudo-Diskussion. Gruß, -- Sdo 13:09, 15. Okt. 2006 (CEST)

[Bearbeiten] Ecke

Die Definition einer Ecke, bzw. ein Verweise auf den Artikel Ecke taucht hier nirgends auf. -- (Vorstehender nicht signierter Beitrag stammt von 85.212.174.128 (Diskussion • Beiträge) 11:15, 23. Nov. 2006)

Danke – hab's [geändert] -- Sdo 12:00, 23. Nov. 2006 (CET)