Dynamische Programmierung

16.01.2014, 10:55	MatheA01	Auf diesen Beitrag antworten »
Dynamische Programmierung Meine Frage: Das folgende 3- dimensionale Rucksackproblem soll mittels Dynamischer Programmierung gelöst werden. 5u + 7v + 4w -> max bzgl. 3u + 4v + 2w kleinergleich 7 Ich habe u,v,w gewählt eigentlich ist es u1,u2,u3, aber das sah verwirrend aus Meine Ideen: Ich weiß das man es mit 2 Variablem zeichnen kann, aber hier bin ich überfragt.
16.01.2014, 11:34	HAL 9000	Auf diesen Beitrag antworten »
Ich gehe mal davon aus, dass es hier um ganzzahlige Optimierung geht, d.h. $\begin{eqnarray} u,v,w \end{eqnarray}$ sind natürliche Zahlen. Offensichtlich ist mit $\begin{eqnarray} (u,v,w) \end{eqnarray}$ auch $\begin{eqnarray} (u,0,2v+w) \end{eqnarray}$ zulässig, letzteres besitzt wegen $\begin{eqnarray} f(u,0,2v+w) = 5u + 8v + 4w > 5u +7v +4w = f(u,v,w) \end{eqnarray}$ im Fall $\begin{eqnarray} v>0 \end{eqnarray}$ aber sicher einen höheren Ertrag. Ergo kann man sich auf das zweidimensionale Problem $\begin{eqnarray} 5u + 4w \to \max \end{eqnarray}$ mit Restriktion $\begin{eqnarray} 3u+2w\leq 7 \end{eqnarray}$ zurückziehen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »