Opimierungeproblem

06/06/2008 - 16:01 von Lula | Report spam
Hallo Leute,

ich stehe vor einem Selektionsproblem mit Optimierung unter
verschiedenen Kriterien und suche einen (schnellen) Algorithmus (der
am besten noch gut IT-technisch umgesetzt werden kann)

Zunàchst einmal das Problem:

Ich habe einen große Anzahl von Schiffen mit verschiedenen
Eigenschaften (z.B. Gewicht, Kaufpreis, Doppelwandig, ). Aus
dieser Gesamtmenge muß nun eine Untermenge (ein sog. Pool) ausgewàhlt
werden, wobei mehrere Kriterien berücksichtigt werden sollen und der
Pool am Ende bestimmte Eingenschaften aufweisen soll.

Diese sind z.B.:
- Durschnittliches Gewicht > 100 tonnen
- Summe Kaufpreise = 200 Mio. EUR (+/- 5%)
- die X teuersten Schiffe im Pool sollen max Y% des gesamtpoolwertes
ausmachen

Das ganze soll dann noch optimiert werden. Zb: Minimiere Anzahl der
Schiffe im Pool oder Maximiere Anzahl der Doppelwandigen Schiffe.

Es handelt sich natürlich um ein ganzzahliges Problem (ich kann kein
halbes Schiff in den Pool geben!)

Problem soweit verstanden? Im ersten Moment habe ich an Simplex-
Algorithmus gedacht. Allerdings weiß ich nicht, wie ich das Kriterium
"die X teuersten Schiffe sollen max Y% des gesamtpoolwertes ausmachen"
umsetzten soll.

Ferner soll der Algorithmus am Ende ausgeben, welche Nebenbedingung zu
veràndern ist, um das Optimum zu verbessern (Sensitivitàtsanalyse).
Dieses soll aber auch gehen, wenn der Pool nicht zustande gekommen
ist! Sprich es kein Ergebnis gab. Dann soll man direkt wissen, welche
NB wie angepaßt werden muß, um ein Ergebnis zu bekommen. Auch hier bin
komme ich mit Simplex glaube ich nicht weiter...

Ich bin für jeden Hinweis dankbar.

grüße,
Lula
 

Lesen sie die antworten

#1 Thomas Plehn
06/06/2008 - 20:49 | Warnen spam
ich kann nichts genaueres sagen, aber du solltest versuchen, das ganze auf
eine Form zu bringen, dass es mit einem
"successive quadratic programming solver" (SQP) lösbar ist.
Dafür gibt es nàmlich genügend Tools, die dir das Ergebnis liefern.

Siehe beispielsweise hier:
http://www.gnu.org/software/octave/...rogramming

"Lula" schrieb im Newsbeitrag
news:
Hallo Leute,

ich stehe vor einem Selektionsproblem mit Optimierung unter
verschiedenen Kriterien und suche einen (schnellen) Algorithmus (der
am besten noch gut IT-technisch umgesetzt werden kann)

Zunàchst einmal das Problem:

Ich habe einen große Anzahl von Schiffen mit verschiedenen
Eigenschaften (z.B. Gewicht, Kaufpreis, Doppelwandig, ). Aus
dieser Gesamtmenge muß nun eine Untermenge (ein sog. Pool) ausgewàhlt
werden, wobei mehrere Kriterien berücksichtigt werden sollen und der
Pool am Ende bestimmte Eingenschaften aufweisen soll.

Diese sind z.B.:
- Durschnittliches Gewicht > 100 tonnen
- Summe Kaufpreise = 200 Mio. EUR (+/- 5%)
- die X teuersten Schiffe im Pool sollen max Y% des gesamtpoolwertes
ausmachen

Das ganze soll dann noch optimiert werden. Zb: Minimiere Anzahl der
Schiffe im Pool oder Maximiere Anzahl der Doppelwandigen Schiffe.

Es handelt sich natürlich um ein ganzzahliges Problem (ich kann kein
halbes Schiff in den Pool geben!)

Problem soweit verstanden? Im ersten Moment habe ich an Simplex-
Algorithmus gedacht. Allerdings weiß ich nicht, wie ich das Kriterium
"die X teuersten Schiffe sollen max Y% des gesamtpoolwertes ausmachen"
umsetzten soll.

Ferner soll der Algorithmus am Ende ausgeben, welche Nebenbedingung zu
veràndern ist, um das Optimum zu verbessern (Sensitivitàtsanalyse).
Dieses soll aber auch gehen, wenn der Pool nicht zustande gekommen
ist! Sprich es kein Ergebnis gab. Dann soll man direkt wissen, welche
NB wie angepaßt werden muß, um ein Ergebnis zu bekommen. Auch hier bin
komme ich mit Simplex glaube ich nicht weiter...

Ich bin für jeden Hinweis dankbar.

grüße,
Lula

Ähnliche fragen