Optimization and Linear Programming

You run a small workshop. Product A earns $40 per unit. Product B earns $30 per unit. Every instinct says: make as many A’s as possible. By the end of this lesson you will see exactly why that instinct is wrong — and how a method called linear programming finds the true best mix in seconds.

Two kinds of analytics

The analytics world has four types. Two of them tell you what happened or what will happen. The third, prescriptive analytics — also called optimization — goes further: it tells you the best decision to make, not just what the outcome might be.

Optimization needs two ingredients:

• An objective — the number you want to maximize (profit, throughput) or minimize (cost, waste).
• Constraints — the real-world limits you must stay within (hours, materials, budget).

Without constraints the answer is trivial (“make infinite units”). Without an objective the answer is vague (“make more”). Together they define a real decision problem.

The product-mix problem

Here are the exact numbers for our workshop.

Decision variables (the quantities you control):

• A = units of Product A to make
• B = units of Product B to make

Objective function (maximize total profit): 40A + 30B

Constraints (the limits):

Labour:   2A + B  <= 100   (A needs 2 hrs, B needs 1 hr; 100 hrs available)
Material: A  + B  <=  80   (each product uses 1 unit; 80 units available)
Non-neg:  A >= 0,  B >= 0

This is an example of linear programming (LP) — optimization where every constraint and the objective are linear, meaning they graph as straight lines (or flat planes). “Linear” is the key word: no squares, no products of variables, just additions and multiplications by constants.

The feasible region

Every point (A, B) that satisfies all four constraints at once belongs to the feasible region — the set of all mixes the workshop can legally produce. When you draw the two constraint lines on a graph, the feasible region is the area below both lines and above the axes.

For our problem the feasible region is a four-sided polygon (quadrilateral) with these corner points (also called vertices):

The crossing point deserves a close look. Where do 2A + B = 100 and A + B = 80 meet? Subtract the second from the first:

(2A + B) - (A + B) = 100 - 80
A = 20

Substitute back: 20 + B = 80, so B = 60. Confirmed: the two constraints cross at (20, 60).

The feasible region diagram

The corner-point theorem — why it works

Here is the most important theorem in LP, stated without jargon:

The optimal solution to any LP is always found at a corner (vertex) of the feasible region.

Why? Imagine walking in the direction of increasing profit across the feasible region. Profit increases in a fixed direction (toward more A and more B). You keep walking until the boundary stops you. The last point you can reach before leaving the feasible region is always a corner — never a point in the middle of an edge, never an interior point.

This matters enormously in practice. A real LP might have millions of feasible points. The theorem says you only need to check the corners — a finite, enumerable list.

Evaluating the corners

The winner is (20, 60): make 20 units of A and 60 units of B for a profit of $2,600.

Notice that both constraints are binding at this corner — meaning both inequalities are satisfied with equality (2(20) + 60 = 100 exactly, and 20 + 60 = 80 exactly). A binding constraint is one that is tight; it is actually limiting you. A non-binding constraint has slack — you could do more but some other constraint stops you first.

What makes a constraint “binding”

A binding constraint is actively limiting your profit — remove or relax it and your optimal profit rises. In this problem, both constraints are binding at the optimum. If you could get just 10 more labour-hours (100 to 110), the feasible region would expand and you could earn more. Knowing which constraints bind tells you where to invest: buying extra capacity on a non-binding constraint wastes money; buying it on a binding one has direct payoff.

Quiz

Next

A/B testing — deciding which change actually works, with statistical evidence rather than gut feel.