Linear Programming and the Simplex Method

Linear programming (LP) is the mathematics of making the best decision when resources are limited. Factories use it to plan production, airlines to schedule crews, and logistics companies to plan delivery routes. In this guide you will learn how to formulate an LP problem, solve it graphically, and then solve the same problem with the simplex method so you can see both approaches agree.

What Is a Linear Programming Problem?

Every LP problem has three parts:

1. Decision variables: the quantities you control, such as \( x \) units of product A and \( y \) units of product B.
2. An objective function: a linear expression to maximise (profit) or minimise (cost), e.g. \( Z = 3x + 5y \).
3. Constraints: linear inequalities describing limited resources, plus non-negativity \( x, y \ge 0 \).

The set of points satisfying all constraints is the feasible region. A central result of LP theory says that if an optimal solution exists, at least one occurs at a corner point (vertex) of the feasible region. Both methods below rely on this fact.

Formulating a Problem

A workshop makes two products. Each unit of product A earns Rs 3 thousand profit and each unit of B earns Rs 5 thousand. Three machines limit production:

• Machine 1 is available for 4 hours; each unit of A uses 1 hour, B uses none.
• Machine 2 is available for 12 hours; each unit of B uses 2 hours, A uses none.
• Machine 3 is available for 18 hours; A uses 3 hours and B uses 2 hours per unit.

Let \( x \) and \( y \) be the units of A and B. The model is:

$$ \text{Maximise } Z = 3x + 5y $$

$$ \text{subject to } \quad x \le 4, \quad 2y \le 12, \quad 3x + 2y \le 18, \quad x, y \ge 0. $$

Worked Example 1: The Graphical Method

The graphical method works when there are two variables.

Step 1: Draw each constraint as a line.

• \( x = 4 \) is a vertical line.
• \( 2y = 12 \) gives \( y = 6 \), a horizontal line.
• \( 3x + 2y = 18 \) passes through \( (6, 0) \) and \( (0, 9) \).

Step 2: Shade the feasible region. It is the area satisfying all inequalities in the first quadrant.

Step 3: Find the corner points.

• \( (0, 0) \)
• \( (4, 0) \): on \( x = 4 \) and the \( x \)-axis.
• \( (4, 3) \): \( x = 4 \) with \( 3x + 2y = 18 \) gives \( 12 + 2y = 18 \), so \( y = 3 \).
• \( (2, 6) \): \( y = 6 \) with \( 3x + 2y = 18 \) gives \( 3x + 12 = 18 \), so \( x = 2 \).
• \( (0, 6) \): on \( y = 6 \) and the \( y \)-axis.

Step 4: Evaluate \( Z \) at each corner.

The maximum is \( Z = 36 \) at \( x = 2, y = 6 \).

The Simplex Method

With three or more variables you cannot draw the feasible region, so we need an algebraic method. The simplex method, developed by George Dantzig, moves from one corner point to a better neighbouring corner until no improvement is possible.

Step-by-Step Procedure

1. Convert each \( \le \) constraint into an equation by adding a slack variable (unused resource).
2. Write the initial tableau, with the slack variables as the starting basic variables.
3. Choose the entering variable: the most negative coefficient in the \( Z \)-row.
4. Choose the leaving variable: the smallest non-negative ratio of right-hand side to the entering column's positive entries (the minimum ratio test).
5. Pivot: make the pivot element 1 and clear the rest of its column.
6. Repeat until no negative coefficients remain in the \( Z \)-row.

Worked Example 2: The Same Problem by Simplex

Step 1: Add slack variables \( s_1, s_2, s_3 \ge 0 \):

$$ R_1: \; x + s_1 = 4 $$

$$ R_2: \; 2y + s_2 = 12 $$

$$ R_3: \; 3x + 2y + s_3 = 18 $$

$$ Z\text{-row}: \; Z - 3x - 5y = 0 $$

Starting solution: \( x = y = 0 \), \( s_1 = 4, s_2 = 12, s_3 = 18 \), \( Z = 0 \). This is the corner \( (0, 0) \).

Step 2: First iteration.

• Entering variable: \( y \) (coefficient \(-5\) is most negative).
• Ratio test on the \( y \)-column: \( R_2: 12/2 = 6 \), \( R_3: 18/2 = 9 \). \( R_1 \) has no \( y \), so it is skipped. Smallest ratio is 6, so \( s_2 \) leaves and \( R_2 \) is the pivot row.

Divide \( R_2 \) by 2:

$$ R_2': \; y + \tfrac{1}{2}s_2 = 6 $$

Eliminate \( y \) from the other rows. \( R_3 - 2R_2' \):

$$ R_3': \; 3x - s_2 + s_3 = 6 $$

\( Z\text{-row} + 5R_2' \):

$$ Z - 3x + \tfrac{5}{2}s_2 = 30 $$

\( R_1 \) is unchanged. Current solution: \( x = 0, y = 6, Z = 30 \), the corner \( (0, 6) \).

Step 3: Second iteration.

• Entering variable: \( x \) (coefficient \(-3\)).
• Ratio test on the \( x \)-column: \( R_1: 4/1 = 4 \), \( R_3': 6/3 = 2 \). Smallest is 2, so \( s_3 \) leaves.

Divide \( R_3' \) by 3:

$$ R_3'': \; x - \tfrac{1}{3}s_2 + \tfrac{1}{3}s_3 = 2 $$

\( R_1 - R_3'' \):

$$ R_1': \; s_1 + \tfrac{1}{3}s_2 - \tfrac{1}{3}s_3 = 2 $$

\( Z\text{-row} + 3R_3'' \):

$$ Z + \tfrac{3}{2}s_2 + s_3 = 36 $$

Step 4: Check for optimality. All coefficients in the \( Z \)-row are now non-negative, so we stop. Setting the non-basic variables \( s_2 = s_3 = 0 \):

$$ x = 2, \quad y = 6, \quad s_1 = 2, \quad Z = 36. $$

This matches the graphical answer. The slack \( s_1 = 2 \) tells us Machine 1 has 2 unused hours, while Machines 2 and 3 are fully used.

Common Pitfalls

• Including negative or zero entries in the ratio test. Only positive entries in the pivot column count.
• Arithmetic slips during pivoting. Recheck each row against the original constraints at the end.
• Forgetting to interpret the answer. Examiners often award marks for explaining what slack values and the optimal \( Z \) mean.
• Mixing up maximisation and minimisation. For minimisation, either maximise \( -Z \) or adapt the entering rule, as your course specifies.

Key Takeaways

• An LP problem has decision variables, a linear objective and linear constraints.
• If an optimum exists, one occurs at a corner of the feasible region.
• The graphical method works for two variables; the simplex method works for any number.
• Simplex adds slack variables, picks entering and leaving variables, pivots, and stops when the \( Z \)-row has no negative coefficients.
• Always interpret the final solution, including the slack values.

Need help with an operations research or linear programming assignment? Amathify's subject experts and PhD scholars can provide fully worked, step-by-step solutions. Reach out on WhatsApp or use the "Ask a Question" form.