Agent Smith (the character from The Matrix movies) has a special power: he can self-replicate, so if he needs to do more than one task at a time, he can create a few copies of himself and perform the tasks simultaneously (we do assume that only one Agent is needed to perform each task, and adding more of him does not shorten the time it takes to finish each task). He has been has been freed from the Machines' control and is on his way to defeat his enemies and rule the world. Some enemies can only be defeated after some other quests are finished, for example, before he can defeat the Oracle or the Architect, he has to find the Keymaker in order to be able to access their locations. The table below summaries the data:
|
Task
|
Duration (Hours)
|
Prerequisites
|
|
Become free from the machines
|
0
|
-
|
|
Defeat Trinity
|
2
|
Become free
|
|
Defeat Morpheus
|
4
|
Become free
|
|
Defeat The Oracle
|
1
|
Become free, find the keymaker
|
|
Find the Keymaker
|
1
|
Become free
|
|
Defeat the Architect
|
3
|
Find the Keymaker
|
|
Defeat Neo
|
5
|
Defeat Trinity, the oracle and Morpheus
|
|
Destroy the Machines
|
10
|
Defeat the Architect
|
|
Rule the World
|
0
|
Defeat Neo and Destroy the Machines
|
(a) Formulate a linear programming problem in order to determine how long before Agent Smith will rule the world. Hint: even though the problem may look like the scheduling models that we have discussed when talking about integer programming, it is much simpler and does not require any integer variables or advanced techniques. Define variables ti representing the time each quest should be started at and determine the necessary constraints.
(b) Can you rephrase this model as a longest (or shortest) path problem? Show the corresponding graph and identify how the solution to the longest or shortest path problem corresponds to the solution of the problem itself.