LOP - Basislösungen

Neue Frage »

Don Cartagena Auf diesen Beitrag antworten »
LOP - Basislösungen
Hallo.

Ich hab eine kleines Problem und bräuchte eure Hilfe.

Folgendes Optimierungsproblem liegt vor:

max! F(x1,x2) = 4 x1 + 3 x2

i) 2 x1 + 5 x2 <= 30
ii) 2 x1 + 2 x2 <= 15
iii) x1 <= 5

a) wie viele basislösungen sind maximal möglich?
b) wie viele basislösungen gibt es insgesamt?
c) wie viele basislösungen sind im zulässigen bereich?
d) welche Kombi von NBV ergibt keine lösung?

zu a) hab ich mit kombinatorik gelöst. ergebnis von 10 stimmt mit meinen musterantworten überein.
zu b) ??? laut lösung: 9, aber wieso?
zu c) hab ich graphisch gelöst: ergebnis von 5 stimmt mit meinen musterantworten überein. ginge es auch rechnerisch?
zu d) ??? laut lösung: x1, x5, aber wieso?


wo ist überhaupt der unterschied zwischen frage a) und b) ?

würde mich über tipps sehr freuen.

danke schon mal

gruß
don cartagena

PS. Simplex habe ich bereits durchgeführt und komme auch auf die optimale lösung, aber an b) und d) hänge ich dennoch...
Reksilat Auf diesen Beitrag antworten »
RE: LOP - Basislösungen
Die zugehörige Matrix sieht ja so aus:

Ein wenig merkwürdig ist die Aufgabe schon formuliert, aber ich denke ich kann sie interpretieren.
a) OK.
b) Du wählst doch immer drei der fünf Spalten von A aus (deswegen ist die Antwort bei a) ja 10), um dann mit eine Basislösung zu erhalten. Nun gibt es aber Kombinationen von Spalten, bei denen die 3x3-Matrix nicht invertierbar ist (in diesem Fall nur eine) und dann ergibt sich ja auch keine Basislösung.
c) Du rechnest einfach alle Basislösungen aus und schaust, ob für alle i erfüllt ist.
d) Folgt dann, wenn Du b) hast.
Don Cartagena Auf diesen Beitrag antworten »
RE: LOP - Basislösungen
herzlichen dank für deine antwort.
ich werd´s nochmal durchrechnen, aber ich denk ich hab´s verstanden.
Don Cartagena Auf diesen Beitrag antworten »

jetzt muß ich leider doch nachhaken...

ich wollte grad alle basislösungen ermitteln, aber mir ist nicht ganz klar wie. ich hatte den simplex ja bereits einmal durchgeführt und die optimallösung sowie zwei weitere basislösungen gefunden. die drei basislösungen liegen ja nun alle im zulässigen bereich (xi >=0)

..aber wie komme ich auf die anderen?

die ausgangsbasis verändern und erneut simplex?

erhalte ich nicht immer nur zulässige ecken?
Reksilat Auf diesen Beitrag antworten »

Jetzt muss ich aber mal nachfragen, wie Du die erste Teilaufgabe gelöst hast.
Zitat:
Wikipedia sagt:
In der Phase II des Simplex-Verfahrens spielt der Begriff der Basis eine wesentliche Rolle. Eine Basis von ist eine Teilmenge der Spalten von , die eine reguläre, also invertierbare Untermatrix bilden. wird dabei als Indexvektor über die Spalten von dargestellt.

Ich habe das oben genannt, und auch gesagt, wie man eine Basislösung erhält. Ob eine Basislösung zulässig ist, sieht man ja dann, wenn man sie hat.

Wenn Du eine andere Definition von Basislösung hast, oder nicht verstehst, was etwas bedeutet, dann frag' doch einfach nach. Augenzwinkern
Don Cartagena Auf diesen Beitrag antworten »

Ich hab die Teilaufgaben, die ich gelöst habe, überwiegend grafisch ermittelt, außerdem per Kombinatorik. Außerdem habe ich den Simplex angewendet um ausgehend von dem Ursprung über zwei Ecken die Optimallösung zu finden.
Damit hab ich alle Aufgabenstellungen beantwortet (die 9 möglichen Basislösungen lassen sich auch inzwischen auch graphisch ermittelt Augenzwinkern ) außer die nach der Kombi der NBV.

Das was du zu Aufgabe b) geschrieben hast verstehe ich nur zum Teil...mir war bis eben nicht klar was du mit A Tilde meintest. Und die Basislösungen hab ich mir bisher eher als Ecke eines Polyeder vorgestellt, weniger als Inverse einer Teilmatrix von A. Darauf geht das Buch was ich benutze ein bischen zu wenig ein...aber das hole ich nach..

Wie auch immer. Wenn ich dich jetzt richtig verstehe muß ich mit Gauß-Jordan die verschiedenen Teilmatrix auf Invertierbarkeit prüfen...oder?

Sorry für meine Unwissenheit verwirrt ..aber ist schon ein bischen her, dass ich mich damit mal beschäftigt habe..und danke für deine Mühe
 
 
Reksilat Auf diesen Beitrag antworten »

Zitat:
Sorry für meine Unwissenheit

Das ist ja nicht das Problem. Ich gehe aber immer von dem aus, was ich selbst gelernt habe oder schaue im Netz (meistens wiki). Wenn dann die Definitionen der Hilfesuchenden von meinen abweichen, bin ich erstmal verwirrt und mache mir dann später Gedanken über äquivalente Definitionen.
Das ist natürlich nicht die optimale Lösung. Wenn Du nicht weißt, wie man eine Basislösung bestimmt, so solltest Du meiner Meinung nach auch die Definition von Basislösung mit dazuschreiben, denn sonst sage ich Dir, wie ICH eine Basislösung bestimme und das hilft Dir hier eben nicht.

Zitat:
mit Gauß-Jordan die verschiedenen Teilmatrix auf Invertierbarkeit prüfen

Oder besser die Determinante bestimmen. Die Teilmatrizen enthalten so viele Nullen, dass es nahezu immer offensichtlich ist, ob die Matrix invertierbar ist. Anschließend wie oben beschrieben die Basislösungen ausrechnen, dann siehst Du auch d).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »