Wer weiß was Ganzzahlige Optimierungen sind?

**csae2557** · 26.06.2003, 14:26

Wer kann mir weiterhelfen. In BWL2 hat er mal nach Ganzzahligen Optimierungen gefragt. Was ist das und welche Bsp kann man da geben?

mfg

**bach99** · 26.06.2003, 15:49

hi,

das ist, wenn man ein optimierungsproblem löst und da dürfen nur ganze zahlen rauskommen
d.h. es gäbe vielleicht noch eine bessere lösung als die die raus kommt, aber die du ausrechnen sollst, ist die beste lösung in ganzen zahlen (also ohne nachkommastellen)

z.b. wäre es nicht sehr sinnvoll, optimalerweise 22,56358 stühle und 26,1253 bänke zu machen. das ganzahlige optimum wäre in dem fall vielleicht bei 22 stühle und 27 bänke, 23 stühle und 26 bänke oder 22 stühle und 26 bänke (beides aufrunden geht nie

)

lgb

**xxx** · 26.06.2003, 18:08

Zitat von bach99

hi,

das ist, wenn man ein optimierungsproblem löst und da dürfen nur ganze zahlen rauskommen
d.h. es gäbe vielleicht noch eine bessere lösung als die die raus kommt, aber die du ausrechnen sollst, ist die beste lösung in ganzen zahlen (also ohne nachkommastellen)

z.b. wäre es nicht sehr sinnvoll, optimalerweise 22,56358 stühle und 26,1253 bänke zu machen. das ganzahlige optimum wäre in dem fall vielleicht bei 22 stühle und 27 bänke, 23 stühle und 26 bänke oder 22 stühle und 26 bänke (beides aufrunden geht nie

)

lgb

...das ist allerdings nicht richtig!!!
Dass man nicht z.B 22.56358 Stühle produzieren kann, hat nichts mit ganzzahliger Optimierung zu tun, das ist einfach Logik!
Die Ganzzahlige Optimierung findet zum Beispiel beim sog. "Travelling-Salesman-Problem" Anwendung: Dabei stehen die beiden Variablen "1" und "0" z.B für folgendes:

1 -> Fahrt von A nach B
0 -> Keine Fahrt von A nach B

...und da die Variablen 1 und 0 ganzzahlig sind nennt man das Ganze ganzzahlige Optimierung!!!

**bach99** · 26.06.2003, 18:31

tja also die ganzzahlige optimierung kann mit verschiedenen verfahren gelöst werden. eines davon ist z.b.
das branch and bound verfahren
und das geht so:
Allgemeine Form des Verfahrens

Das lineare Optimierungsproblem wird mit P0 bezeichnet.
Der Index i wird auf 0 gesetzt.

[1] Löse das Problem Pi mit dem Simplex-Algorithmus.

[2] Ist die Lösung ganzzahlig und i = 0, so beende das Verfahren.
Gib die berechnete (letzte) Lösung aus.

[3a] Ist die Lösung ganzzahlig und besser als alle Schranken bzw. gleich der besten Schranke, so beende das Verfahren.
Gib die berechnete (letzte ganzzahlige) Lösung aus.

[3b] Ist die Lösung ganzzahlig und schlechter als die "beste" Schranke, so berechne als Schranke des Problems den Zielfunktionswert der Lösung des Problems Pi.
(Füge das Problem der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste (noch nicht abgearbeitete) Problem Pk, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Wurde für das Problem Pi bereits eine ganzzahlige Lösung ermittelt, so gib diese Lösung aus und beende das Verfahren.
Im anderen Fall gehe zu [1].

[3c] Ist die Lösung nicht ganzzahlig, so berechne als Schranke S den Zielfunktionswert der Lösung des Problems Pi.
Zerlege das Problem Pi in zwei Teilprobleme Pi1 und Pi2
(jeweils mit obiger Schranke S).
Sei dabei k der erste Index mit einer nichtganzzahligen Lösung xk* .
Setze uk = int(xk) und ok = uk + 1.
Das Problem Pi1 entspricht dem Problem Pi mit der zusätzlichen Nebenbedingung xk < uk .
Das Problem Pi2 entspricht dem Problem Pi mit der zusätzlichen Nebenbedingung xk > ok.
(Füge die beiden Probleme der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste Problem Pk, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Ist Pi bereits gelöst, so gehe zu [3a] sonst gehe zu [1].

und wie man darin (meiner meinung nach, es kann natürlich schon sein, dass ich die sache nicht richtig verstehe) sehen kann, geht es sehr wohl um ganze zahlen in der lösung!!

man das ganze auch noch mal anders erklärt:

Die ganzzahlige Optimierung behandelt Optimierungsprobleme in denen alle – teils einige– Freiheitsgrade diskret, d. h. z. B. auf die ganzen Zahlen , beschränkt sind. Die Ganzzahligkeitsbedingungen rühren bei praktischen Fragestellungen z. B. daher, daß Null-Eins Entscheidungen zu treffen sind, oder zu bestimmende Entscheidungsvariablen nur ganzzahlige oder nur bestimmte diskrete Werte annehmen können.

meine erklärung ist also durchaus richtig
lgb