Knapsack-Problem

Hallo Leute,
ich habe ein mehrperiodisches Modell des Knapsack-Problems aufgestellt. Das Modell ist mehrperiodisch, lässt Entnahmen aus dem Knapsack zu und basiert auf sicheren Plangrößen.
Damit sollen wie im "klassischen" Knapsack-Problem Güter gewählt werden, welche in der Summe den größsten Nutzen bringen aber mit ihrem kumulierten Gewicht nicht die Kapazitätsrestriktion des Knapsack überschreiten (das ist ein Zwischenschritt).
Dieser Zwischenschritt ist also ein Maximierungsproblem, welches meine Kosten maximiert, die durch die Auswahl und den Eingang der Güter in den Knapsack vermieden werden.
Ich möchte aber aus Gründen der Kostenoptimierung ein Minimierungsproblem aufzeigen, welches somit die Kosten minimiert die entstehen, wenn Güter nicht in den Knapsack aufgenommen werden.
Da sich quasi nur die Betrachtungsperspektive auf die Kosten ändert, habe ich nur die Zielfunktion angepasst, aber die Nebenbedingungen in ihrer ursprünglichen Form beibehalten. Wenn ich das Modell anhand von Daten teste (mittels Excel-Solver) funktioniert es auch alles wunderbar.
Nun ist meine Frage, ist dieses Vorgehen mathematisch korrekt??

Idee zum Modell
$$\begin{gathered} {\displaystyle \mathrm{Z<mspace\; width="0.12em"></mspace>}\mathrm{w<mspace\; width="0.12em"></mspace>}\mathrm{i<mspace\; width="0.12em"></mspace>}\mathrm{s<mspace\; width="0.12em"></mspace>}\mathrm{c<mspace\; width="0.12em"></mspace>}\mathrm{h<mspace\; width="0.12em"></mspace>}\mathrm{e<mspace\; width="0.12em"></mspace>}\mathrm{n<mspace\; width="0.12em"></mspace>}\mathrm{s<mspace\; width="0.12em"></mspace>}\mathrm{c<mspace\; width="0.12em"></mspace>}\mathrm{h<mspace\; width="0.12em"></mspace>}\mathrm{r<mspace\; width="0.12em"></mspace>}\mathrm{i<mspace\; width="0.12em"></mspace>}\mathrm{t<mspace\; width="0.12em"></mspace>}\mathrm{t<mspace\; width="0.12em"></mspace>}: \\ \sum _{\mathrm{j<mspace\; width="0.12em"></mspace>}=1}^{\mathrm{N<mspace\; width="0.12em"></mspace>}}{\mathrm{c<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}\to \mathrm{max<mspace\; width="0.12em"></mspace>} \\ \sum _{\mathrm{i<mspace\; width="0.12em"></mspace>}\le \mathrm{j<mspace\; width="0.12em"></mspace>}}^{}{\mathrm{a<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}-\sum _{\mathrm{i<mspace\; width="0.12em"></mspace>}+{\mathrm{n<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}\le \mathrm{j<mspace\; width="0.12em"></mspace>}}^{}{\mathrm{a<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}\le \mathrm{b<mspace\; width="0.12em"></mspace>},\mathrm{f<mspace\; width="0.12em"></mspace>}\mathrm{ü<mspace\; width="0.12em"></mspace>}\mathrm{r<mspace\; width="0.12em"></mspace>}\mathrm{j<mspace\; width="0.12em"></mspace>}=1,\mathrm{...},\mathrm{N<mspace\; width="0.12em"></mspace>} \\ {\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}\in \{0,1\}\mathrm{f<mspace\; width="0.12em"></mspace>}\mathrm{ü<mspace\; width="0.12em"></mspace>}\mathrm{r<mspace\; width="0.12em"></mspace>}\mathrm{j<mspace\; width="0.12em"></mspace>}=1,\mathrm{...},\mathrm{N<mspace\; width="0.12em"></mspace>} \\ \mathrm{E<mspace\; width="0.12em"></mspace>}\mathrm{n<mspace\; width="0.12em"></mspace>}\mathrm{d<mspace\; width="0.12em"></mspace>}\mathrm{mod<mspace\; width="0.12em"></mspace>}\mathrm{e<mspace\; width="0.12em"></mspace>}\mathrm{l<mspace\; width="0.12em"></mspace>}\mathrm{l<mspace\; width="0.12em"></mspace>}: \\ \sum _{\mathrm{j<mspace\; width="0.12em"></mspace>}=1}^{\mathrm{N<mspace\; width="0.12em"></mspace>}}({\mathrm{c<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}{[1-{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}])}_{}\to \mathrm{min<mspace\; width="0.12em"></mspace>} \\ \sum _{\mathrm{i<mspace\; width="0.12em"></mspace>}\le \mathrm{j<mspace\; width="0.12em"></mspace>}}^{}{\mathrm{a<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}-\sum _{\mathrm{i<mspace\; width="0.12em"></mspace>}+{\mathrm{n<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}\le \mathrm{j<mspace\; width="0.12em"></mspace>}}^{}{\mathrm{a<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}{\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{i<mspace\; width="0.12em"></mspace>}}\le \mathrm{b<mspace\; width="0.12em"></mspace>},\mathrm{f<mspace\; width="0.12em"></mspace>}\mathrm{ü<mspace\; width="0.12em"></mspace>}\mathrm{r<mspace\; width="0.12em"></mspace>}\mathrm{j<mspace\; width="0.12em"></mspace>}=1,\mathrm{...},\mathrm{N<mspace\; width="0.12em"></mspace>} \\ {\mathrm{x<mspace\; width="0.12em"></mspace>}}_{\mathrm{j<mspace\; width="0.12em"></mspace>}}\in \{0,1\}\mathrm{f<mspace\; width="0.12em"></mspace>}\mathrm{ü<mspace\; width="0.12em"></mspace>}\mathrm{r<mspace\; width="0.12em"></mspace>}\mathrm{j<mspace\; width="0.12em"></mspace>}=1,\mathrm{...},\mathrm{N<mspace\; width="0.12em"></mspace>}} \end{gathered}$$

Annahmen:

Die Güter kommen in der Reihenfolge j = 1, ..., N zu fest bekannten Terminen an und sind später aus dem KP zu fest bekannten Terminen zu entnehmen. Eine Teilmenge j =1, ..., n dieser Güter liegt tatsächlich schon auf dem KP; ihre Ankunftstermine sind als ?heute? zu interpretieren, deswegen gelten sie als ?früheste? Lieferungen und stehen immer am Anfang der gesamten Reihenfolge (ihre Anordnung untereinander ist unwichtig).

Bezeichungen:

a_j - Gewicht des j-ten Gutes

c_j - Kostenwert

n_j - verbleibende (Verweil-/Lager-)Dauer für eine bereits auf dem Knapsack befindliches Gut bzw. komplette (Verweil-/Lager-)Dauer für ein anzukommendes Gut. Genauer: bevor Eintreffen des (j+n_j)-ten Gutes verlässt die j-te das Knapsack.

b - Kapazität des Knapsack

Entscheidungsvariablen:

x_j = 0 bedeutet für eine bereits im Knapsack liegendes (j-te) Gut, dass es entnommen wird, und für eine neu anzukommendes Gut, dass es nicht gewählt wird.

x_j = 1 bedeutet für eine bereits im Knapsack liegendes (j-te) Gut, dass es weiterhin im Knapsack bleibt, und für eine neu anzukommendes Gut, dass es im Knapsack aufgenommen wird.

Danke schön für eure Ideen im Voraus!!
Viele Grüße :-)

sorry... ist eine rückfrage :)

Stimmt schon. Meine Frage war aber viel mehr in Bezug auf das Vorgegen. Sprich ich mache aus der Maximierung eine Minimierung in der Zielfunktion, belasse aber die Nebenbedingung in ihrem ursprünglichen Zustand.

und somit die Frage, darf man das einfach so? ist das mathematisch korrekt?

Grüße

Linda