Pivotelement Skript 1, Aufgabe 2.4

direkt zum allerersten Skript (Lineare Optimierung):

Bitte erkläre mir jemand, warum ab dem Teil "Übungsaufgabe 2.2 ergibt weiterhin:" die 5 als Pivotelement genommen wird?

Ich verstehewarum in Übungsaufgabe 2.2 in der 2. Matrix die -5 (x2 Spalte genommen wird). Laut dem Gauß Eliminationsalgorithmus geht man ja stets diagonal nach unten rechts und prüft on dieses Element ungleich null ist, was hier der Fall ist.

Aber Warum nun die -5 genommen wird ist mir schleierhaft.


Edit:
Das selbe Problem stellt sich mir in Übungsaufgabe 3.6
Hier sollen sämtliche Basislösungen zum LOP erstellt werden.
Keine Idee wie er die Pivotelemente auswählt. Willkühr ist es sicher nicht...


Ich bitte um Erleuchtung 🙂

Mattes

Hallo Mattes,

vorweg: es gibt mehrere Methoden, ein Pivotelement zu wählen (am Ende also doch Willkür 😉 ). Die verschiedenen Algorithmen dienen nur dem Zweck, die Lösung in möglichst wenigen Schritten zu finden bzw. mit einfachen Rechenschritten. Du könntest z.B. in ÜA 2.2 in der ersten Matrix auch als erstes die -5 wählen oder auch die 3 und würdest am Ende auf dasselbe Ergebnis kommen. Ggf. sind nur die Zeilen vertauscht. (Was für die Lösung keine Rolle spielt, solange du die Variablen richtig abliest 🙂. )

Nun zu der Frage, warum im zweiten Schritt die -5 gewählt wurde:
hier wird einfach stur von oben links angefangen immer das Element in der nächsten Zeile und Spalte gewählt (Bedingung ist nur, es muss <> 0 sein). Also:
1te Zeile / 1te Spalte -> 1. Da darunter schon alle 0 ist, ist x-1 schon Basisvariable.
2te Zeile / 2te Spalte -> 1. Da darunter schon alle 0 ist, ist x0 schon Basisvariable.
3te Zeile / 3te Spalte -> 1. Werte darüber und darunter elimieren, so dass x2 Basisvariable wird.
4te Zeile / 4te Spalte -> -5. Werte darüber und darunter elimieren, so dass x2 Basisvariable wird.
Fertig 🙂


Zu ÜA 3.6
Hier geht es nicht darum, die optimale Lösung zu finden, sondern alle möglichen Lösungen. In dem Fall brauchst du dich also gar nicht um die Wahl des besten Pivotelementes zu kümmern, da du ohnehin alle Lösungen brauchst. Also

- Die Aufgabe hat 3 Nebenbedingungen und 5 Variablen. Daraus folgt es gibt maximal "n über m" also n!/(m!-(n-m)!) Lösungen (siehe S. 19 Mitte). In dem Fall also maximal 10 Basislösungen.

- Da es drei Zeilen gibt (bzw. Rang der Matrix=3), hat jede Basislösung drei Basisvariable. Also muss es in jedem Tableau 3 Einheitsspalten (bzw. -vektoren) geben: (1,0,0), (0,1,0) und (0,0,1).

- Nun erzeugst du durch Zeilenoperationen einfach die unterschiedlichen Tableaus, so dass die Einheitsspalten immer an anderer Stelle stehen (wie und in welcher Reihenfolge du das machst ist egal).

- Die Basislösung ist dann immer xT=(mit dreimal unterstrichen und zwei mal 0), wobei die Basisvariablen (=unterstrichen) entsprechend den Einheitsspalten immer an unterschiedlichen Stellen stehen.

Die Aufgabe hat am Ende nur 8 Basislösungen. Es fehlen die Kombinationen:
xT=( _, 0, _, _, 0) und xT=(0,_, _, 0, _)
was bedeutet egal wie du das Tableau umstellst, du wirst es nicht hinbekommen, das die Einheitsspalten bei x1,x3,x4 oder x2,x3,x5 stehen.
Diese Kombinationen bilden also keine Basis.

Außerdem sind die Basislösungen x4=(2,2,-1,0,0) und x6=(0,3,0,2,-1) und x7=(3,0,0,-1,2) unzulässig, da nicht alle x>=0.
D.h. das LOP hat insgesamt 5 zulässige Basislösungen.

Falls eine Basisvariable (unterstrichenes x) = 0 wäre, wäre es übrigens eine entartete Basislösung, das kommt noch später im Skript 🙂.

(PS: Diese Ausführungen gelten natürlich nur, wenn die Aufgabe keine redundanten Bedingungen enthält, indem Fall würde sich die Zeilenanzahl entsprechend verringern)

So, ich hoffe, das hat dir weitergeholfen, ansonsten gerne melden 🙂
Viele Grüße
Birgit

Birgit,

erst einmal vielen Dank für Deine tolle Antwort.

Ich merke grade, dass ich total missversändlich gefragt habe. Sorry!

Übungsaufgabe 2.2 ist vollkommen klar.

Meine erste Frage bezog sich auf Seite 78 oben. Das ist der zweite Teil von Aufgabe 2.4
Hier steht "Übungsaufgabe 2.2 ergibt weiterhin"
Ich sehe, dass hier ersteinmal die zweite Matrix von Aufgabe 2.2 übernommen wurde aber nun die 5 als Pivotelement genommen wurde.
und das weiß ich weder, warum er das aufgerechnet dieses Element wählt, noch was er damit bezweckt. Die Lösung der Aufgabe 2.4 ist doch schon auf Seite 77 abgeschlossen, oder nicht?


Zu Deinen Ausführungen bezüglich Ü3.6:
Super erklärt. Alles verstanden und mehr als deutlich
...Aber😉 ...Klar dass noch was kommt. haha...
Es gibt theoretische bei dieser spalten/zeilenkombination maximal 10 Basislösungen. Verstanden!
Einige sind davon ungültig (RHS<0). Verstanden!
Und einige können gar nicht erstellt werden. Auch verstanden.

Aber woher weiß ich denn welche nicht erstellt werden können? Da muss ich ja ewig rumtüfteln, oder gibts da nen "Trick" oder sowas?

Ansonste perfekto erklärt. Daumen hoch!

Mattes

Hallo Mattes,

ÜA 2.4:
Die Aufgabe lautet "Bestimmen Sie zwei Basislösungen..."
Die erste Basislösung kannst du aus dem Endtableau von ÜA 2.2 direkt ablesen.
Für die zweite Basislösung musst du eine Basisvariable austauschen (also eine nicht Einheitsspalte zu einer Einheitsspalte machen). Welche du nimmst, bleibt dir überlassen! In der Lösung wurde x4 gewählt, du kannst aber genausogut x2 oder x3 wählen. In der Lösung könnte es also besser heißen. "eine weitere Basislösung ist z.B. ..."

ÜA3.6:
Also solange es nicht 100 mögliche Basislösungen gibt, musst du nicht lange tüfteln, sondern kannst es sehen.
Es fehlt ja z.B. die Kombination xT=( _, 0, _, _, 0).
Nun gucke ich mir die bereits vorhandenen Basislösungen an, um eine auszuwählen, bei der ich möglichst wenig Variable tauschen muss (weil das Rechenarbeit spart 😉 ), also z.B:
xo=(0,0,3,2,2), denn hier sind bereits zwei Basisvariable richtig, nämlich x3 und x4.
D.h. ich muss nur noch x5 und x1 tauschen.
Um x1 zur Basisvariablen zu machen, kann ich zwischen den beiden 1en als Pivot wählen:
Wähle ich die zweite Zeile als Pivot, mache ich mir aber x3 "kaputt" , wähle ich dir dritte Zeile als Pivot, mache ich mir x4 "kaputt". Wobei "kaputt" heißt, dass die Spalte danach keine Einheitsspalte mehr ist.
Und so ist es auch bei den anderen vorhandenen Basislösungen. Durch einen Pivotschritt bekommst du zwar eine gewünschte Basisvariable, verlierst aber eine andere.
(Probier es zur Übung ruhig mal aus 🙂 )

Wenn du dir nun die Tableaus mal anguckst, kannst du auch sehen, woran das liegt:
Es gibt keine Pivotzeile, wo alle Elemente in den Einheitsspalten, die verbleiben sollen, 0 sind.

Dazu noch ein Bsp. wo es klappt:
Von xo=(0,0,3,2,2) zu x1=(2,0,1,0,2) kann man die Variablen x4 und x1 tauschen, denn
Einheitsspalten die beiben sollen = x3 und x5
neue gewünschte Einheitsspalte = x1
Gibt es in Spalte x1 eine Zeile, bei der an der Stellen x3 und x5 eine 0 steht? Ja, in der dritten Zeile.
Also Tausch möglich.

Viel Spaß beim probieren und wenn noch was unklar ist, melde dich 🙂
PS: Eine MathEditor wäre an dieser Stelle schön 😉

Gruß aus Kölle, Birgit

Jau nun ist alles klar.

Hey... Willst Du nicht so ein Skript schreiben. Ich kaufe es auch! hahaha

Machst Du den Kurs zum ersten mal?

Wenn ja, wann beginnst Du mit der EA? ist ja noch sehr sehr früh, aber ich wollte langsam starten. Wenn Du magst können wir dann ja abgleichen!

LG,
Mattes

Danke für die Blumen 🙂

Ja, mache den Kurs zum ersten Mal. Habe im SS 2010 den Bachelor gemacht und wollte niiiiieeee wieder Klausuren schreiben 😉. Nach vier Jahren Pause hat es mich aber doch wieder gepackt und OR und Mathe waren einfach schon immer meine Lieblingsfächer 🙂.

EA hab ich mir gerade runtergeladen und schau ich mir über Ostern mal an. Können dann gerne vergleichen. Was man hat, das hat man 🙂

Viele Grüße
Birgit