A standard maximization problem has the form maximize z = c1x1 + c2x2 + ... + cnxn subject to linear constraints and x1, x2, ..., xn >= 0. Slack variables turn <= constraints into equations, such as a1x1 + a2x2 + s1 = b. In the tableau method, the entering variable is chosen from the most negative objective-row coefficient for the z-row convention, and the leaving variable is chosen by the smallest nonnegative ratio b / positive pivot-column entry.
The solution is optimal when no negative coefficients remain in the objective row.
Key Facts
- For a standard maximization problem, write the objective as z - c1x1 - c2x2 - ... - cnxn = 0 before forming the tableau.
- A <= constraint becomes an equation by adding a slack variable, such as 2x + 3y <= 12 becoming 2x + 3y + s1 = 12.
- In the common z-row tableau convention, the entering variable is the column with the most negative coefficient in the objective row.
- The leaving row is found using the minimum nonnegative ratio RHS / pivot-column entry, using only rows with positive pivot-column entries.
- The pivot entry must be changed to 1 by dividing the entire pivot row by the pivot value.
- All other entries in the pivot column must be changed to 0 using row replacement operations.
- A basic feasible solution is read by setting nonbasic variables to 0 and taking each basic variable from its row RHS value.
- For maximization with the z-row convention, the tableau is optimal when every coefficient in the objective row is greater than or equal to 0.
Vocabulary
- Linear programming
- Linear programming is the process of optimizing a linear objective function subject to linear constraints.
- Simplex tableau
- A simplex tableau is a table that stores the objective equation, constraint equations, variable coefficients, and right-hand-side values.
- Slack variable
- A slack variable is a nonnegative variable added to a <= constraint to turn it into an equality.
- Pivot
- A pivot is the selected entry used to swap one variable into the basis and one variable out of the basis.
- Basic variable
- A basic variable is a variable whose column acts like a unit column and whose value is read from the right-hand side.
- Optimality condition
- The optimality condition is the rule that tells when no further improving pivot is available.
Common Mistakes to Avoid
- Choosing the most negative number from the entire tableau is wrong because the entering variable is selected only from the objective row.
- Using negative or zero pivot-column entries in the ratio test is wrong because only positive entries can safely determine the leaving variable.
- Forgetting to divide the pivot row by the pivot entry is wrong because the entering variable column must become a unit column.
- Changing only the constraint rows and not the objective row is wrong because the objective equation must be updated by the same row-operation logic.
- Reading nonbasic variables from the RHS is wrong because nonbasic variables are set to 0 in the current basic feasible solution.
Practice Questions
- 1 Maximize z = 3x + 2y subject to x + y <= 4, 2x + y <= 5, x >= 0, y >= 0. Write the initial simplex tableau using slack variables s1 and s2.
- 2 For the objective row z - 5x - 3y + 0s1 + 0s2 = 0, which variable enters first under the most negative coefficient rule?
- 3 In a pivot column, the constraint entries are 2, 1, and 4, and the RHS values are 10, 6, and 12. Compute the ratio test values and identify the leaving row.
- 4 Explain why the simplex method moves from one basic feasible solution to another instead of checking every point in the feasible region.