Quote (Necroman87 @ 25 Apr 2012 10:42)
Eine Firma plant in 20 Monaten ein Produkt mit einem sehr hohen Verkaufspotential auf den
Markt zu bringen. Nun hat sie aber herausgefunden, dass ein Konkurrenzanbieter ein ähnliches
Produkt herausbringen wird. Die Firma ist daher gezwungen, die Fertigstellung des Produkts
zu beschleunigen, damit es so früh wie möglich auf den Markt kommen kann.
Insgesamt müssen nacheinander vier Phasen durchlaufen werden, ehe das Produkt Marktreife
erreicht: Konzeption, Design, Entwicklung und Fertigung. Jede dieser vier Phasen kann mit
drei unterschiedlichen Prioritätsstufen (normal, hoch, sehr hoch) durchlaufen werden, wobei
bereits beschlossen wurde, die letzten drei Phasen nicht auf normaler Stufe durchzuführen. Im
Folgenden sehen Sie die Zeiten, die jeweils benötigt werden, wenn man eine Phase auf einer
bestimmten Prioritätsstufe durchführt:
Stufe Konzeption Design Entwicklung Fertigung
Normal 5 Monate (4 Monate) (7 Monate) (4 Monate)
Hoch 4 Monate 3 Monate 5 Monate 2 Monate
Sehr hoch 2 Monate 2 Monate 3 Monate 1 Monat
Das Management hat insgesamt ein Budget von 50 Millionen Euro zur Verfügung gestellt. Die
Kosten, die für die einzelnen Phasen auf den Prioritätsstufen jeweils anfallen, sind wie folgt:
Stufe Konzeption Design Entwicklung Fertigung
Normal 5 Mio. — — —
Hoch 9 Mio. 10 Mio. 14 Mio. 6 Mio.
Sehr hoch 14 Mio. 15 Mio. 19 Mio. 12 Mio.
Es ist nun zu entscheiden, auf welcher Stufe welche Phase auszuführen ist, sodass die insgesamt
benötigte Zeit minimal wird, wobei das vorgegebene Budget auf keinen Fall überschritten
werden darf.
Modellieren Sie das Problem als kürzeste-Wege-Problem unter Einhaltung des Budgets.
Welche Bedeutung haben die Knoten und Kanten?
Bemerkung: Beachten Sie bitte, dass das Hinzufügen eines zweiten Kantengewichts und
Anpassung eines kürzeste-Wege-Algorithmus keiner Modellierung als kürzeste-Wege-
Problem (wie wir es definiert haben) entspricht.
Help :/ steh grad bissl aufm schlauch, für kürzeste Wege hab ich Label correcting und Djikstra aus der VL im Angebot.
Ausserdem noch ne Aufgabe wo ich ne "nichtstauwahrscheinlichkeitstabelle" gegeben hab (nichttauwahrscheinlichkeit eines Pfades multiplikativ über Teilpfade) wo ich den bestmöglichen weg über Djikstra finden soll (hinweis ist logarithmusregel log(xy) = log(x)+log(y) bin aber noch nicht ganz durchgestiegen wie mir das helfen soll grösstes problem ist wohl dass man für djikstra nichtnegative kantengewichte braucht und log x < 0 für x<1 )
okay lol, die lösung vom 1. war tatsächlich exponentiell viele knoten zu nehmen, da hab ich mit NP-Vollständigkeit also doch den richtigen Riecher gehabt -.- nur wer kommt auf so ne Idee...