Kurs 853

Andy,

zum Beispiel 4.1 (Seite 72/73) hatte ich mal irgendwo was geschrieben, eventuell hilft Dir das ja schon ein wenig weiter... :dafuer:

FranzK schrieb:

Zunächst mal zu den Bezeichnungen

Rucksackproblem allgemein:
- Gegenstände 1,..,n
- jeweilige Mengen [tex]x_1,..,x_n[/tex]
- jeweilige Gewichte [tex]a_1,..,a_n[/tex]
- jeweiliger Nutzen [tex]c_1,..,c_n[/tex]
- Gesamtkapazität [tex]b[/tex]

Es kommen jetzt noch hinzu:
- Teilkapazitäten [tex]0 \le j \le b[/tex]
- Auswahl Gegenstände [tex]0 \le k \le n[/tex]

OK 😎

Was ist in der Tabelle für [tex]F(k,y)[/tex] dargestellt? => Der maximal erreichbare Gesamtnutzen (z) bei gegebenen y und k. Also: Welcher Gesamtnutzen ist für welche Teilkapazität mit welchen ausgewählten Gegenständen erreichbar.

Von praktischer Relevanz ist nur die letzte Spalte, da hier alle theoretisch möglichen Gegenstände einfließen. Die anderen Spalten werden nur für die rekursive Berechnung der Lösung benötigt.

Wie Du schon richtig erkannt hast, sind die Einträge für y=0 sowie k=0 sämtlich 0. Wo die einzelnen Gewichte größer sind als die Teilkapazitäten, also
[tex]y - a_k < 0[/tex],
kannst Du generell den Eintrag der Vorgänger-Spalte (jeweils links) übernehmen.

Alles weitere erledigen die Schritte 2. bis 4. Hier muss man sich nur stur an die jeweiligen Formeln und Einträge halten und möglichst sauber rechnen 🙄 Achtung, hoher Verkasper-Faktor 😀

Falls es da noch bei Dir haken sollte, können wir auch noch gemeinsam ein Beispiel durchgehen...

Was ist in der Tabelle für [tex]j(k,y)[/tex] dargestellt? => Der größte Index einer positiven Variablen in der Lösung.

Die Berechnung der Einträge erfolgt parallel zu den Einträgen der anderen Tabelle...

Wenn Du irgendwann die Tabellen komplett und fehlerfrei durchgerechnet hast, können wir die optimale Lösung schrittweise aus den Tabellen ermitteln.

Für den Zielfunktionswert ergibt sich:

[tex]z = F(5,10) = 25[/tex]

Die Gewichte der einzelnen Gegenstände ermitteln wir sukzessive:

Vorab:

[tex]x_1 = x_2 = x_3 = x_ 4 = x_5 = 0[/tex]

Aktuell verbleibende Kapazität (Gesamtkapazität]:

[tex]b = 10[/tex]

Höchster Index einer Variablen für y=b=10 ist 4 - siehe j(10,5):

[tex]x_4 = x_4 + 1 = 1[/tex]

Restkapazität ermitteln:

[tex]b = b - a_4 = 10 - 2 = 8[/tex]

Höchster Index einer Variablen für y=b=8 ist 4 - siehe j(8,5):

[tex]x_4 = x_4 + 1 = 2[/tex]

Restkapazität ermitteln:

[tex]b = b - a_4 = 8 - 2 = 6[/tex]

Höchster Index einer Variablen für y=b=6 ist 4 - siehe j(6,5):

[tex]x_4 = x_4 + 1 = 3[/tex]

Restkapazität ermitteln:

[tex]b = b - a_4 = 6 - 2 = 4[/tex]

Höchster Index einer Variablen für y=b=4 ist 4 - siehe j(4,5):

[tex]x_4 = x_4 + 1 = 4[/tex]

Restkapazität ermitteln:

[tex]b = b - a_4 = 4 - 2 = 2[/tex]

Höchster Index einer Variablen für y=b=2 ist 4 - siehe j(2,5):

[tex]x_4 = x_4 + 1 = 5[/tex]

Restkapazität ermitteln:

[tex]b = b - a_4 = 2 - 2 = 0[/tex]

=> Der Algorithmus terminiert!

Optimale Lösung:

[tex]x_1 = x_2 = x_3 = x_5 = 0, \quad x_4 = 5[/tex]

Zum Vergrößern anklicken....

Gruß Franz

Danke

Hallo Franz und Danke nochmal,

ich glaub jetzt hab ich es verstanden. Man muss wirklich total aufpassen beim Rechnen. Ist eigentlich nicht wild, aber es schleichen sich schnell Fehler ein.

Momenant sitze ich an den Mehrzielentscheidungen, die haben es auch in sich. Vielleicht macht es da ja auch bald klick...

Gruß

Andy