Graphical method and simplex

Why it matters

With two decision variables you can draw an LP and see its answer. That picture explains the single most important fact about linear programming: if an LP has an optimal solution, one of them sits at a corner of the feasible region. The simplex method, which solvers have used since the 1940s, is a clever way to walk from corner to corner in many dimensions. Understanding it lets you read solver output, spot unbounded or infeasible models, and explain results with confidence.

The graphical method

Take the workshop from the last lesson:

maximize   70x + 50y
subject to 4x + 3y <= 240   (carpentry)
           2x +  y <= 100   (painting)
           x >= 0, y >= 0

1. Draw each constraint as a line. Replace <= with =. The carpentry line crosses the axes at (60, 0) and (0, 80). The painting line crosses at (50, 0) and (0, 100).
2. Shade the side that satisfies the inequality. Test the origin: 0 <= 240 is true, so the feasible side contains (0, 0).
3. The feasible region is where all the shaded parts overlap, including x >= 0 and y >= 0. Here it is a four-sided shape.
4. Find the corners by intersecting pairs of lines and keeping only the points that satisfy every constraint.
5. Evaluate the objective at each corner and pick the best.

Where do the two resource lines cross? Solve 4x + 3y = 240 and 2x + y = 100. From the second, y = 100 - 2x. Substitute: 4x + 300 - 6x = 240, so x = 30 and y = 40.

Build 30 tables and 40 chairs for a profit of 4,100. The point (60, 0) is a crossing of the carpentry line with the x-axis, but it breaks the painting limit, so it is not a corner of the region.

Why corners? Draw the iso-profit line 70x + 50y = k. Increasing k slides the line outward, parallel to itself. The last point of the region it touches is a corner (or a whole edge, when the objective is parallel to a constraint: then there are many optimal solutions).

Special cases to recognise

• Infeasible: the constraints have no point in common. For example x + y <= 2 and x + y >= 5.
• Unbounded: the region is open in the direction of improvement, so the objective can grow forever. In practice this almost always means a missing constraint.
• Multiple optima: the objective is parallel to a binding edge. Any point on that edge is optimal.

The simplex method in one page

Enumerating every corner works for two variables but explodes with more: m constraints in n variables can have up to "m + n choose n" corners. Simplex is smarter.

1. Turn each <= into an equation with a slack variable: 4x + 3y + s1 = 240. Slack is unused capacity.
2. Start at the origin, where the slacks are the basic variables (s1 = 240, s2 = 100) and x = y = 0.
3. Choose an entering variable: one whose increase improves the objective. A common rule picks the most negative entry in the objective row of the tableau.
4. Ratio test: increase it until the first constraint becomes tight. For each row with a positive entry in that column, compute right-hand side / entry; the smallest ratio wins, and that row's basic variable leaves.
5. Pivot: rewrite the equations so the entering variable is basic. Geometrically, you have moved along an edge to a neighbouring corner.
6. Repeat until no variable improves the objective. That corner is optimal.

For the workshop, x enters first (70 is the larger profit). Ratios: carpentry 240 / 4 = 60, painting 100 / 2 = 50. Painting is tighter, so we move to (50, 0). In the next step y enters and we arrive at (30, 40). Two pivots, done.

The tableau for the start looks like this (bottom row holds the negated objective):

        x    y   s1   s2 | rhs
s1      4    3    1    0 | 240
s2      2    1    0    1 | 100
obj   -70  -50    0    0 |   0

You will write the full tableau method in numpy in the next lesson.

Common mistakes

• Keeping intersection points that are not feasible. Every candidate corner must satisfy every constraint.
• Forgetting the axes. x = 0 and y = 0 are constraints too, and they create corners.
• Using negative entries in the ratio test. Only positive column entries limit how far a variable can increase.
• Reading "unbounded" as good news. It means the model is missing a real-world limit.

Quick recap

• An LP's optimum (if one exists) is at a corner of the feasible region.
• Graphical method: draw lines, find feasible corners, evaluate the objective.
• Simplex moves from corner to better corner using slack variables, an entering variable, the ratio test and a pivot.
• Watch for infeasible, unbounded and multiple-optimum models.

Try it

In the Do tab, write Python that finds every feasible corner of a two-variable LP and picks the best one.