Simplex Tableau $C_j - Z_j = 0$ Indicates Multiple Solutions

In the context of the simplex method for linear programming problems (maximization), the final simplex tableau provides information about the optimality of the current solution.

Optimality Conditions

• The current basic feasible solution is optimal if all the $C_j - Z_j$ values (also known as net evaluation coefficients) in the final tableau are less than or equal to zero ($C_j - Z_j \le 0$) for all variables.
• If $C_j - Z_j < 0$ for all nonbasic variables, the current optimal solution is unique.
• If $C_j - Z_j = 0$ for one or more nonbasic variables, it means that introducing any of these nonbasic variables into the basis will not change the objective function's value. This indicates that alternative optimal solutions exist.

Reasoning for Multiple Optimal Solutions

When a nonbasic variable has a $C_j - Z_j = 0$ in the final tableau, it implies that we can potentially increase the value of this variable from zero (its current nonbasic value) without decreasing the objective function value. If the rules of the simplex method allow this variable to enter the basis (i.e., it's not a situation of degeneracy that prevents improvement), a new basic feasible solution will be found. This new solution will have the same optimal objective function value as the current one, thus confirming the existence of Multiple Optimal Solutions.

Evaluating Other Options

• Unique Solution: Occurs when all $C_j - Z_j < 0$ for nonbasic variables.
• Unbounded Solutions: Identified during the pivoting process if a variable to enter the basis has no positive coefficients in the constraint rows.
• Infeasible Solution: Occurs if the problem has no feasible region or if artificial variables remain in the basis with positive values in the final tableau.

Therefore, a zero $C_j - Z_j$ entry for a nonbasic variable in the final simplex tableau specifically points towards multiple optimal solutions.