Lineare Optimierung

Neue Frage »

Mazze Auf diesen Beitrag antworten »
Lineare Optimierung
originial Klausuraufgabe:

Käptn Blaubär muß Matrosen anheuern. Auf seinem Schiff ist Platz für höchstens zehn Matrosen und der Koch kann diese mit höchstens 40 Tellern Suppe verköstigen.

Käptn Blaubär hat die Auswahl zwischen Leichtmatrosen und Schwermatrosen. Ein Leichtmatrose isst nur zwei teller Suppe am Tag und kann 4 Stunden täglich arbeiten. Ein Schwermatrose braucht 7 Teller Suppe, arbeitet dafür auch 12 Stunden am Tag.

Natürlich möchte Käptn Blaubär, daß seine Matrosen möglichst viel arbeiten. Wieviel Leichtmatrosen und wieviel Schwermatrosen soll er anheuern?

(Ich fand die Aufgabe so klasse da sich des erstmal aufschreiben musste ^^)

Soo der Ansatz

L = Leichtmatrosen
S = Schwermatrosen
H = Summe der Arbeitszeit

L + S = 10
2L + 7S = 40
4L + 12S = H

Wir wollen max(H) haben, und jetzt hakts bei mir. Es wäre gut wenn ich H als Funktion von L und S ausdrücken kann, aber irgendwie fehlt mir die Idee wie ich das machen kann -.-
flixgott Auf diesen Beitrag antworten »

also eigentlich sollte das problem ganz leicht sein.
du hast als zielfunktion eine funktion die die gesamtarbeitszeit berechnet. die hast du doch auch schon aufgeschrieben:

maximiere 12s+4l

dazu gelten folgende nebenbedingungen:

s+l<=10
2l+7s<=40

(ich würde das kleinergleich nehmen, weil es ja nicht gesagt ist, dass er optimal arbeitet wenn allle grenzen erfüllt sind. in der aufgabe steht ja auch 'höchstens' und nicht 'genau')

jetzt solltest du das problem in standardform bringen:

min -12s-4l
NB s+l+x=10
2l+7s+y=40
s,l,x,y>=0

naja und jetzt kannst du es in matlab ganz leicht mit der funktion linprog lösen (ich glaub da brauchst du nicht mal zwnagsweise standard form)
ansonsten kann man bei diesem einfachen problem auch den simplexalgorithmus zu fuss ausrechnen.
Mazze Auf diesen Beitrag antworten »

Hm, Simplexalgorithmus sagt mir garnichts, und ist auch das erste mal das ich sowas mache. Die Randbedingungen leuchten ein, mein Problem ist eher wie ich dadurch das maxima der Funktion bekomme.
flixgott Auf diesen Beitrag antworten »

ok das simplexverfahren ist eine methode zu berechnung von solchen problemen, allerdings kann man deins auch zu fuss ausrechnen, da es handlich ist. ich glaube so sollte es gehen:

forme dein problem um:

min -12s-4l
NB -s-l>=-10; -2l-7s>=-40
(dass dieses problem zu deinem äquivalent ist sollte klar sein)

F:={(s,l) | s,l erfüllen die nebenbedingung und sind nichtnegativ}
in einem koordinatensystem sollte F eine konvexe abgeschlossene menge beschreiben, ein stück der s- und der l-achse begrenzen diese.

jetzt legst du deine die geradenschaar -12s-4l=-h (für jede h ergibt sich eine gerade) über diese menge. das h für die die gerade eine ecke oder ein randstück von F mit F gemeinshat hat beschriebt die lösung. lösung des problem sind jetzt alle punkte die die gerade mit F gemeinsam hat (sollte im regelfall nur eine ecke sein) allerdings mußt du (s,l)=(0,0) auschließen, da das ja keine sinnvolle lösung.

ich hab dir jetzt hier grob das graphische lösungsverfahren von (linearen) optimierungsproblemen beschrieben. das problem bei deiner aufgabe ist, dass als bedinung noch hinzu kommt, das l und s natürliche zahlen sein sollten. ich weiss nicht genau wie man das einbindet, aber ich hab zwei ideen:
1.) vielleicht sollte man es mal versuchen auf was man kommt, wenn man h nur ganzzahlig annimmt und sich die gerade sucht, die einfach die wenigsten gemeinsamen punkte mit F hat und da nach ganz zahligen lösungen sucht.
2.) bestimme einfach die reele lösung und such in der nähren umgebung nach ganzzahligen lösungen.

bei einer klausur ist es aber bestimmt eh so, dass die lösungsecke auch ganzzahlig ist.
Mazze Auf diesen Beitrag antworten »

Über eine graphische Lösung hab ich ja schon nachgedacht. Die Lösungen mit natürlichen zahlen werden ja Teilmenge aller Lösungen sein, deswegen reicht es ja diese dann zu filtern.

Die Geraden sollte ich dann wohl an die minimal/maximal Stellen legen richtig?
flixgott Auf diesen Beitrag antworten »

was meinst du mit minimal / maximal stellen?
 
 
Mazze Auf diesen Beitrag antworten »

naja die "hervorstechenden" Randpunkte der Menge.
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
deswegen reicht es ja diese dann zu filtern.


Im Allgemeinen ist dies falsch. (Zumindest im ganz allgemeinen, wenn man keine Linearität hat) Dann muss nicht die ganzzahlige Lösung optimal sein, die am nächsten an der Lösung ist, wenn man das Problem reell betrachtet (der sogenannten Relaxation). Es kann eine ganzzahlige Kombination optimal sein, die ganz weit vom Optimum der Relaxation weg liegt.

Das ist aber hier ein bisschen OT. Hast du eine graphische Lösung versucht? Du musst zuerst den zulässigen Bereich einzeichnen, also die Nebenbedingungen. Das Gebilde, was entsteht nennt man Polyeder (dieser ist konvex, wie flixgott richtig gesagt hat, muss aber nicht unbedingt abgeschlossen sein). Nun zeichnest du einen Repräsentanten der Zielfunktion ein, suchst dir also ein h aus, für das du die Zielfunktion zeichnest, möglichst so, dass sie mitten durch den zulässigen Bereich geht. Diese verschiebst du dann bis du einen Optimalpunkt erreichst, also so, dass du die Zielfunktion nicht weiter verschieben kannst (optimal kann u.U. auch eine ganze Gerade sein). Mach dir klar, in welche Richtung du schieben musst. Das ist das Verfahren, die Zielfunktion an die "Minimal- Maximalstellen zu legen", wie du es nennst.

Wenn du jetzt Glück hast (in welchem Rahmen wurde die Aufgabe denn gestellt?), dann ist die Optimallösung ganzzahlig Augenzwinkern

Gruß vom Ben
Mazze Auf diesen Beitrag antworten »

Also mit filtern meinte ich nicht die optimale Lösung filtern sondern die ganzzahligen. Ich habs mal aufgezeichnet und bekam für s =4 und l = 6. Jemand ne bessere Lösung?
Passant Auf diesen Beitrag antworten »

Wenn das wirklich "original Klausuraufgabe" zum Thema Lineare Optimierung ist, dann wäre der analytische Lösungsweg interessant, und nicht "S=4 und L=6".
Schließlich kann S nur 5, 4, 3, 2, 1 oder 0 sein und entsprechend L: 2, 6, 7, 8, 9 oder 10. Und bei den Zahlen braucht man nicht einmal einen Taschenrechner.

Also, wie sieht das Vorgehen aus?
Mazze Auf diesen Beitrag antworten »

eigentlich muss ich für deinen Weg nur noch prüfen ob die Randbedingungen gelten und ob es maximal ist. Sicher besser als graphische Lösung da diese Fehler birgt!
Ben Sisko Auf diesen Beitrag antworten »

Ehrlich gesagt vermute ich, dass bei dieser Aufgabe die Ganzzahligkeitsforderung nicht unbedingt zu beachten war, sondern einfach das graphische Lösungsverfahren gefragt war (da du ja scheinbar kein Vorwissen hast, oder?). Nochmal die Frage, wo hast du die Aufgabe denn her?
Mazze Auf diesen Beitrag antworten »

Eine etwas ältere Klausuraufgabe war das, genauer von 95

http://user.cs.tu-berlin.de/~jensb/root/..._klausur.pdf.gz
(sind 2 Klausuren die Aufgabe die ich hatte ist im unteren Teil)

Ich kann mir schon Vorstellen das der Inhalt jetzt anders ist, aber scheinbar war die Aufgabe ja nicht so schwer das sie nicht schaffbar wäre.

was lineare Optimierung angeht, da weiß ich so gut wie nichts.
Passant Auf diesen Beitrag antworten »

Soviel ich weiß, wenn graphische Lösungen nicht ausdrücklich erwünscht sind, müssen Aufgaben analytisch gelöst werden.
Damit unterscheidet sich die Mathematik von der bildenden Kunst.

Habe ich Recht?
Ben Sisko Auf diesen Beitrag antworten »

Das kommt natürlich drauf an, was man in der Vorlesung behandelt hat, oder? In der Regel wird das graphische Lösungsverfahren bei 2-dim. Problemen behandelt, bevor man in die Lineare Optimierung einsteigt. Wenn es gar nicht um Lin. Opt. gehen soll, wird trotzdem oft ausschließlich die graphische Lösungsmethode im 2-dim. "mal angeschnitten".

Für eine analytische Lösung würde ich eine Aufgabe mit mehr Dimensionen erwarten.

Gruß vom Ben
therisen Auf diesen Beitrag antworten »

Zitat:
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. Bekannt sind das Verfahren Cutting-Plane-Verfahren von Gomory und die Methode Branch and Bound.

Zu dem Cutting-Plane-Verfahren ist im Moment noch kein Artikel vorhanden.

Gruß, therisen
Oudeis Auf diesen Beitrag antworten »

Hallo,

Zitat:
Original von Ben Sisko
Das kommt natürlich drauf an, was man in der Vorlesung behandelt hat, oder? In der Regel wird das graphische Lösungsverfahren bei 2-dim. Problemen behandelt, bevor man in die Lineare Optimierung einsteigt.


Gibt es mathematische Vorlesungen, in denen solche Verfahren "behandelt" werden? Ich bin im Laufe meines Studiums [lästermodus an] nur zwei Vorlesungen begegnet, von denen man hätte behaupten können, daß das zutraf, und über die Frage, ob das noch Mathematikvorlesungen waren, liesse sich trefflich streiten. [lästermodus aus] Ansonsten passiert es meiner Erfahrung nach allenfalls mal, daß eine Skizze an die Tafel gepinselt wird für Motivation oder Vorstellung, aber nicht um wirklich mathematisch etwas zu tun.

Zitat:

Für eine analytische Lösung würde ich eine Aufgabe mit mehr Dimensionen erwarten.


Für eine Klausuraufgabe würde ich zuallererst eine mathematisch korrekte Lösung erwarten (total off-topic: vorzugsweise natürlich eine algebraische Big Laugh ). Da die Zahlen klein sind, ist die Aufgabe ohne Kenntnisse in linearer Optimierung auch sicherlich im für eine Klausur gewünschten Zeitrahmen sauber zu lösen.

Grüße,
Oudeis
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von Oudeis
Gibt es mathematische Vorlesungen, in denen solche Verfahren "behandelt" werden?


Also in meiner Optimierung I-Vorlesung (Lineare Optimierung und Optimierung auf Graphen) wurden die ersten 2 Sitzungen ausschliesslich motiviert (allerdings für Optimierung allgemein, quasi auch für spätere Veranstaltungen, ganzzahlige, kombinatorische, nichtlineare, nichtdifferenzierbare Optimierung) und dabei wurde auch das graphische Lösen im 2.-dim. Fall behandelt. Dazu gab´s sogar ne Übungsaufgabe. Augenzwinkern Und die Vorlesung wurde durchaus danach zu einer vollwertigen Mathe-Vorlesung.

Ich halte das Ganze in diesem Bereich einer sehr angewandten Mathematik auch für sehr sinnvoll.

Gruß vom Ben
Neue Frage »
Antworten »



Verwandte Themen

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