Optimization problem:

\fis also a solution. To prove this claim, we need to verify that any such x is feasible with respect to the constraints Ax 2 b, x Z 0 in (3.1) and also that x achieves the same objective value as each of the solutions x', i = 1, 2, . . . , K . First, note that K K szztcngxi 3 20:,- bzb, 21 21 and so the inequality constraint is satised. Since x is a nonnegative combination of the nonnegative vectors x, it is also nonnegative, and so the constraint x 2 0 is also satised. Finally, since each x' is a solution, we have that p'x' = z for some scalar zap, and all i=l,2,...,K. Hence, K K r I 1' px: E aipx = E 011' ZoptZZopt- i=1 21 Since it is feasible for (3.1) and attains the optimal objective value zopt, we conclude that x is a solution, as claimed. Phase 11 can be extended to identify multiple solutions by performing additional pivots on columns with zero reduced costs after an optimal tableau has been identied. We illustrate the technique with the following simple example