1. Once again consider human resource management problem discussed in class. Namely, a company is planning their hiring strategy for the next T time periods. They estimate that Dt worker-hours will be required at time period t and they currently have Y employees, who work a hours per time period. New workers can be hired and trained, and it takes one time period and bt experienced worker-hours to train a new hire. Regular workers and trainees are paid ct and dt per time period. At any given time period rt proportion of the existing workers (rounded up) will quit.

(a) Assuming that the company does not want to have more than Y employees at any time period, formulate a shortest path problem for determining the optimal hiring strategy.

(b) Estimate the number of nodes and arcs in your model. Recall that earlier in the semester we have given an LP and IP formulations (depending on whether integer values for the numbers of new trainees are required). Can you say anything about the efficiency of the shortest path formulation compared to the LP and IP?

2. Consider the shortest path problem from s to t for a given network. Let us call an arc a vital arc if its removal causes the shortest distance between s and t to increase. We will call an arc the most vital if its removal yields the greatest increase in the shortest distance. Assume that the network is directed, arc lengths are positive, and some arc is vital. Verify whether the following is true. Explain your answers: give a specific example showing that the statement is wrong, or prove otherwise.

(a) The most vital arc is an arc with the maximum value of cost cij in the network

(b) The most vital arc is an arc with the maximum value of cij on some shortest path from node s to node t

(c) A network might contain several most vital arcs.