In a 3 * 3 transportation problem, let xij be the amount shipped from source i to destination j, and let cij be the corresponding transportation cost per unit. The amounts of supply at sources 1, 2, and 3 are 15, 30, and 85 units, respectively, and the demands at destinations 1, 2, and 3 are 20, 30, and 80 units, respectively. Assume that the starting northwest-corner solution is optimal and that the associated values of the multipliers are given as u1 = -2, u2 = 3, u3 = 5, v 1 = 2, v 2 = 5, and v 3 = 10.

(a) Find the associated optimal cost.

(b) Determine the smallest value of cij for each nonbasic variable that will maintain the optimality of the northwest-corner solution.