MastersForum

Wenn du Fragen hast, einfach stellen, gibt hier bestimmt einige, die das beantworten können.

Bei uns kam zuerst eine Beispielaufgabe wie diese:

Ein landwirtschaftlicher Betrieb besitzt Stallungen
für 50 Kühe und 200 Schafe. Außerdem verfügt er über 72 Morgen
Weideland und 10 000 Arbeitsstunden jährlich. Eine Kuh benötigt 1 Morgen,
ein Schaf 0.2 Morgen Weideland. Für eine Kuh sind jährlich 150 Arbeitsstunden,
für ein Schaf sind jährlich 25 Arbeitsstunden erforderlich. Der
jährliche Gewinn pro Kuh beträgt 250 EUR, der jährliche Gewinn pro Schaf
beträgt 45 EUR. Man maximiere den jährlichen Gesamtgewinn unter all diesen
Nebenbedingungen.

D.h. wie du geschrieben hast mit 2 Variablen, grafisch rel. einfach zu lösen.

Hast du das Simplexverfahren erklärt bekommen, bzw. kannst du mit dem
etwas anfangen?

Mit wirklich guten Quellen in dem Sinn kann ich eher nicht dienen, die meisten haben sich wohl nicht die Mühe gemacht Aufgaben mit so vielen Variablen per Hand durchzurechnen.

Und was meinst du mit mehreren Lösungsmethoden, bzw. wurden dir da welche genannt oder musst du dir das alles selbst aneignen?
Finde das fürs Abi auch rel. schwer ohne das genau erklärt zu bekommen.

ist auch wichtig zu wissen wie deine variablen aussehen und dein problem. diskret, obere und untere schranken, vorzeichenbeschränkt zb. je nachdem eignen sich dann andere methoden, wie das bereits genannte simplex-verfahren (mit tableau methode ist das einfach viel zu rechnen, würde ich nicht per hand machen sondern nen solver nehmen^^), innere punkte methode, duales simplex, dekomposition, ...

aber das kann man glaube ich nicht erwarten von nem gymnasiasten. von daher wirds wohl auf das simplexverfahren mit tableau hinauslaufen. ist viel zu rechnen aber weiß ja nicht was du für hilfsmittel zur verfügung hast.

ich meine 9 variablen können ja auch 4 NB => 4 schlupfvariablen + 5 "echte" variablen sein.

linke mal zu einführungsseite zum institut an dem ich studiere:
http://www.math.tu-bs.de/~degbers/mathopt0607/index.html

Transportproblem und erläutern ist schon wieder besser.

Das Simplexverfahren kann das zwar lösen, aber beim Simplexverfahren ist rel. viel zu erläutern und von den 9 Variablen ist das ziemlich unabhängig. D.h. es ist zu kompliziert und wie frantic schrieb nimmt man dann nen solver.

Wenn mit erläutern gemeint ist, dass du ein Transportproblem mit so vielen Variablen als Beispiel vorrechnen sollst würde ich hier erst mal ein paar Vorschläge abwarten.

Ich würde den Algorithmus von Ford und Fulkerson nehmen. Für das Vorrechnen wär der einigermaßen ok, müsstest dir halt ein paar Begriffe aneigenen. Aber vielleicht gibt es noch bessere Möglichkeiten.

Edit: oder vielleicht auch den Netzwerk Simplex.

transportproblem is von der darstellung auch wesentlich anschaulicher^^

bei transportproblem hast doch in der regel anbieter- und nachfragerknoten (mit jeweils angebot oder nachfrage - wobei summe(angebot) = summe (nachfrage)) und dazu ne kostenmatrix die dir transportwege beschreibt.

du kannst das problem dann natürlich als LP oder fluss problem umformulieren und dann für LP wieder simplex benutzen oder für fluss ford fulkerson. guckst du hier: http://de.wikipedia.org/wiki/Transportproblem

wir hatten in der vorlesung noch ne andere methode. suchst dir für das transportproblem ne zulässige anfangslösung. dann stellst diese als baum da und suchst kreise. findest du welche hängt man den baum dementsprechend um bis es keine mehr gibt. könnte dir dazu ne hausaufgabe von mir einscannen und auch den algorithmus einscannen. dazu hab ich aber auf wiki so schnell nichts gefunden.

warte erstmal ab was deine quelle so für methoden beinhaltet.

btw: die älteren verfahren sind meist die einfachen also freu dich^^. außerdem ist das transportproblem an sich ja schon sehr sehr alt (bzw lange bekannt).

Transportprobleme sind aber weitaus hässlicher zu lösen als einfache lineare Optimierungsprobleme.

Die Frage ist, ob der Algorithmus in allen nicht-entarteten Fällen eine Optimallösung gefunden haben soll oder ob du auch nur Heuristiken beschreiben darfst, welche unter Umständen bei einer schlechteren Lösung abbrechen.

Grundsätzlich ist das Problem lösbar, aber nicht notwendigerweise eindeutig.
Wenn du keien weiteren Vorgaben hast, so nimm als Aufgabe für das Transportproblem eine zu verteilende Flüssigkeit, bspw. Treibstoff auf Tankstellen. So sind die Güter teilbar und nicht nur ganzzahlige Lösungen erlaubt. Das Problem bei vielen realen Fragestellungen ist, dass man nur ganzzahle Güter hat, das Optimum aber oft rational sein wird. Man müsste dann nach der eigentlichen Optimierung noch eine zweite durchfühen, um eine beste ganzzahlige Lösung zu finden. Bspw. könnte man kurz das Schnittebenenverfahren von Gomory erläutern, aber dies würde wohl den Umfang sprengen.

Ich glaube Ford, Fulkerson (1956) veröffentlichen einen max flow min cut Algorithmus.
Wenn du das Transportproblem zu einem Zuordnungsproblem einschränken würdest (n Aufgaben auf n Arbeiter), so könntest du die Ungarische Methode zur Lösung benutzen. Allerdings ist sie auch recht hässlich.

Man kann das ganze Graphentheoretisch recht gut lösen, aber ob das für einen Nicht-Mathematiker so sinnvoll ist? Den Algorithmus für n>=9 Variablen zu beschreiben ist schon nicht so einfach.

Ich hatte mal eine Transformation aufgeschrieben, welche ein Transportproblem in die Simplex-Standardform bringt, welche dann recht einfach lösbar ist. Um Entartung (uneindeutigkeiten) muss man sich allerdings bei manchen Problemklassen explizit kümmern. Dies merkt man aber nur, wenn man entweder von der Sache was versteht oder wirklich allgemeine Beispiele damit in der Praxis lösen will - ansonsten ist es kein Problem, man kann beliebige Beispiele finden, welche sofort lösbar sind.

Da du "Lehrer" meintest, so nehme ich mal Schule an. Obige Umformulierung ist straight forward in linearer Algebra.

Beim Simplex wird eine skalare Zielfunktion minimiert. Um das Produkt aus Kosten- und Zuordnungsmatrix zu minimieren, summiert man über alle Hauptdiagonalelemente, denn nur diese sind entscheident. Dies wäre die Zielfunktion.
Die Nebenbedingungen haben 2 Formen: Wieviele Einheiten maximal von eienr Quelle weggehen sollen und wieviele Einheiten maximal eine "Senke" aufnehmen kann. Beide lassen sich, jeweils mit Einführung einer "Hilfsvariable" für jede Nebenbedingung, aufstellen.
Rein praktisch ist dies nicht wirklich, weil die Größe des Problems so exorbitant durch die Einführung der Hilfsvariablen anwächst, aber das sind ja nur praktische Überlegungen.

Ich habe einige Bücher zum Thema da, in wieweit sie für die Schule geeignet sind, kann ich allerdings nicht sagen. Aber gerade das originalwerk von Dantzig ist extrem einfach geschrieben, da er kaum abstrahiert. Melde dich mal,, wenn sie dich interessieren.
Wenn ich etwas Zeit habe (so in 14 Tagen), kann ich auch mal die Transformation des Transportproblems in die allgemeine Simplex-Form aufschreiben, aber nach meinen Erläuterungen solllte dies kein größeres Problem sein.