Reference no: EM131032092

Part A-

1. 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:

(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 t_i 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 teh longest or shortest path problem corresponds to the solution of the problem itself.

2. The Star Box Company sells boxes of seven types. They range in volume from as small as 17 to as large as 33 cubic feet. The demand and size of each box is given in Table 1. The variable cost (in dollars) of producing each box is equal to the box's volume. A fixed cost of $1000 is incurred to produce any of a particular box. If the company desires, demand for a box may be satisfied by a box of larger size. Formulate a shortest path problem whose solution will minimize the cost of meeting the demand for boxes. Identify nodes, arcs and costs.

3. Formulate the multi-commodity minimum cost flow (MMCF) problem as a linear program (with integer variables if needed). Recall that in the MMCF you are given a set of nodes N = 1, 2, ... , n and a set of arcs connecting these nodes. Each arc is associated with a cost cii and capacity u23. There are K commodities, and for each node you are given the values b2k representing the supply (or demand) of the commodity k at node i. The problem is to find a flow through this network that satisfies balancing constraints as well as combined capacity constraint that has minimum cost. Give an LP formulation for the general problem statement above.

4. For the graph below, solve minimum spanning tree problem using Prim's algorithm.

5. Extra credit: Another simple, yet popular method for solving the minimum spanning tree problem is the Kruskal's algorithm. A detailed description can be found in Anuja's book, chapter 13.4. Alternatively, this brief wild page contains all of the information you would need for this problem: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm (there also are numerous other on-line sources you could look into). Show the steps Kruskal's algorithm when applied to the graph in the previous problem.

Part B-

1. A spy wants to send a message to the headquarters, but she does not have a direct link to it. Instead, she has to send it through a network of agents. Some of the connections are not reliable and could be bugged. Suppose that you have all of the information about the structure of the network of the agents, and you also know the probability pii that the communication between agent i and j is bugged. Suppose also that these probabilities are independent, i.e., if you send a message to agent A with probability of failing 0.1 and agent A sends it to agent B with probability of failing 0.2, then the probability that the message will reach B and will not be intercepted is (1-0.1) (1-0.2) = 0.72. Given that the spy wants to minimize the probability of interception, formulate this problem as a regular shortest path problem. Give an example of a problem with at least 4 agents, draw the corresponding graph and show your solution.

2. Minimum flow problem. In a variation of the maximum flow problem in addition to upper bounds u_ij on the flow along each arc (i, j) (capacities) you are also given lower bounds: l_i,j. The problem is to find minimum flow from s to t which satisfies both lower and upper bounds on each arc, as well as flow balance constraints. Show how this problem can be solved by using two applications of any maximum flow algorithm that applies to problems with zero lower bounds on arc flows. Give an example of a network with at least seven nodes and non-trivial l_ij and u_ij illustrating your method.

3. Prove max-flow-min-cut theorem by applying strong duality of linear programming to the regular LP formulation of the maximum flow problem. By regular LP formulation I mean the formulation that is based on variables xii representing the flow along arc (i, j), which was given in class (during the discussion of LP modeling techniques). Either show the primal and dual in general, or provide the primal and dual LPs for network.