Suppose that, for the subproblems formulated in Exercise 5, we define a ray-finding subproblem as follows: b1 is set equal to 1 and moved to the righthand side; the resulting subproblem is solved by linear programming.

a) Formulate the ray-finding problem.

b) Find the dual of the ray-finding problem.

c) Show that a basis for the dual problem is triangular.

d) Write down a recursive method for calculating the optimal solution of the dual of the ray-finding problem. [Hint. Exploit the triangular property of the basis to solve for the dual variables by back-substitution.]

e) How is the solution of the primal ray-finding problem determined from the solution of the dual?