Restriktionen im Knapsack-Prob < Politik/Wirtschaft < Geisteswiss. < Vorhilfe
|
| Aufgabe | Es geht um die Modellierung von Restriktionen eines gewönhlichen Knapsack-Problems:
a) Wenn ein Exemplar von Gegenstand X3 mitgeführt wird, so ist auch mind. ein Exemplar von Gegenstand X4 mitzuführen.
b) Die Gegenstände 1 und 5 dürfen nicht gemeinsam eingepackt werden |
Hallo,
komme irgendwie nicht auf die Lösung.. Geht aber sicher mit Binärvariablen, oder?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hi du,
erst einmal herzlich ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]") *smile* !!!
> Es geht um die Modellierung von Restriktionen eines gewönhlichen Knapsack-Problems:
> a) Wenn ein Exemplar von Gegenstand X3 mitgeführt wird, so ist auch mind. ein Exemplar von Gegenstand X4 mitzuführen.
> b) Die Gegenstände 1 und 5 dürfen nicht gemeinsam eingepackt werden
> Geht aber sicher mit Binärvariablen, oder?
Auf jedenfall  ! Setzen wir folgende Notation voraus:
Maximalgewicht: G
Gegenstand : j
Gewicht eines Gegenstandes: gj
Nutzen je Gegenstand: uj
Binärvariable: xj
Jeder Gegenstand j = 1, ..., n besitzt ein Gewicht gj und verursacht einen Nutzen in Höhe von uj. Mit Hilfe von Binärvariablen xj, die den Wert 1 haben, falls Gegenstand j mitgenommen wird, lässt sich das Knapsack-Problem wie folgt als binäres Optimierungsmodell formulieren:
Im Prinzip musst du dir jetzt "nur" noch Gedanken machen, wie denn dieses Zuorndungsproblem aufgestellt wird. Wenn deine Ausgangsstellung linearer Natur ist, dann hast du ein ganz "normales" Transportsystem, welche du mit den üblichen Heuristiken lösen kannst. Ist der Sachverhalt ein wenig komplexer, und du musst ein nicht-lineares Zuordnungsproblem lösen, dann wirst du neben den Nebenbedingungen des linearen Zuordnungsproblems eine quadratische Zielfunktion benötigen. Wir suchen also in deinem Fall nach einer Art Regressionsansatz, der alle pareto-effizienten Allokationen (hier Gegenstände) verbindet. Dazu habe ich dir mal einen kleinen, aber feinen Link bereit gestellt:
-> ![[]](/images/popup.gif) Klick mich !
Wenn du noch Fragen hast, bezüglich der Restriktionen, dann meld dich einfach nochmal !
Liebe Grüße
Analytiker
![[lehrer]](/images/smileys/lehrer.gif "[lehrer]")
|
|
|
| |
|
Also ehrlich gesagt interessiert mich lediglich das bloße Aufstellen dieser nur zu trivial anmutenden Restriktionen.. Denn das anschließende Lösen mittels Brach&Bound ist nicht das Problem.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:25 Sa 02.02.2008 | | Autor: | fausto |
Guten Tag
Allgemeine Aussagen zum Knapsack-Problem hast du ja bereits gekriegt.
Nun zu den Einschränkungen:
Eine offensichtliche Art mit den Einschraenkungen umzugehen ist das Problem jeweils für jede Einschraenkung zu verdoppeln:
- Wenn Gegenstand A dann auch auch Gegenstand B:
Löse das Problem X ohne Gegenstände vom Typ A
Löse das Problem Y indem du vorab je einen Gegenstand A und B in den Rucksack füllst.
Die bessere (Nutzwert) der beiden Lösungen gewinnt.
Aehnliches gilt fuer die Einschraenkung:
- Wenn Gegenstand C dann nicht Gegenstand D
Loese das Problem ohne Gegenstaende C und dasjenige ohne Gegenstaende D...
Gesamthaft loest du also 4 Probleme und pickst dir dann die beste Loesung raus.
...ist nicht sehr effizient...vielleicht gibt es auch was Besseres?
Gruss
|
|
|
| |
|
also die lösungen zu den aufgaben habe ich nun:
2x4>=x3
x1<=2z
x5<=2(1-z)
, mit z element aus {0,1}
aber ich verstehe es leider immer noch nicht so ganz.. wäre super, wenn ihr es mir anhand der lösungen nochmal leicht veranschaulichen könnten... danke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Fr 08.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
