The Everyday Problem

Imagine a small workshop that builds tables and chairs. Each table earns more profit than a chair, but it also hogs more wood and more hours at the saw. You have a fixed amount of wood and a fixed number of work hours each week. How many of each should you build to make the most money?

This is a linear program. There is a goal you want to push as high as possible (profit), and that goal grows in a straight line with how much you make. There are limits — wood, hours — and each limit is also a straight line: use too much and you cross it.

Almost every "do the best you can within the rules" question has this shape: cheapest diet that still meets your vitamins, the airline schedule that burns the least fuel, the blend of crude oils that yields the most gasoline. They all boil down to pushing one linear goal as far as it will go inside a region carved out by linear constraints.

Try It: Slide to the Best Corner

Below is the workshop problem drawn as a picture. The shaded polygon is every plan that respects your wood and hours; any point inside is allowed. The dashed line is your profit — all the plans that earn the same amount sit on it.

<p class="hint">The shaded polygon is every plan that fits your wood and hours. The dashed line is your <b>profit</b> — every plan on it earns the same. Slide it out as far as it still touches the region. The best plan is always a <b>corner</b>.</p>
<canvas id="lp" width="360" height="320"></canvas>
<div class="row">
  <label for="slider">Profit line</label>
  <input id="slider" type="range" min="0" max="100" value="30" />
</div>
<div class="status" id="status">Slide the line, then Solve.</div>
<div class="btns">
  <button id="solve" type="button">Solve (jump to best corner)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #fff; border: 1px solid #cdd9e3; border-radius: 8px; display: block; max-width: 100%; }
.row { display: flex; align-items: center; gap: .6rem; margin: .7rem 0 .3rem; }
.row label { font-size: .85rem; font-weight: 600; color: #1d3557; }
input[type=range] { flex: 1; accent-color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Linear program (the workshop):  maximize  P = 3x + 2y
//   subject to   x + y <= 8      (work hours)
//                2x + y <= 12     (wood)
//                x >= 0, y >= 0
// The feasible region is a polygon; the optimum is ALWAYS at one of its corners (vertices). Checking a corner is instant; the simplex method just walks the corners — and the whole problem is in P (Khachiyan 1979).
const C = { x: 3, y: 2 };                 // objective coefficients
const CONS = [                             // a*x + b*y <= c
  { a: 1, b: 1, c: 8 },
  { a: 2, b: 1, c: 12 },
];
const profit = (p) => C.x * p.x + C.y * p.y;
const feasible = (p) =>
  p.x >= -1e-9 && p.y >= -1e-9 &&
  CONS.every(k => k.a * p.x + k.b * p.y <= k.c + 1e-9);

// Candidate vertices = intersections of every pair of boundary lines (including the two axes), kept only if feasible.
function vertices() {
  const lines = [
    { a: 1, b: 0, c: 0 },   // x = 0
    { a: 0, b: 1, c: 0 },   // y = 0
    ...CONS,
  ];
  const pts = [];
  for (let i = 0; i < lines.length; i++)
    for (let j = i + 1; j < lines.length; j++) {
      const L = lines[i], M = lines[j];
      const det = L.a * M.b - M.a * L.b;
      if (Math.abs(det) < 1e-9) continue;
      const x = (L.c * M.b - M.c * L.b) / det;
      const y = (L.a * M.c - M.a * L.c) / det;
      const p = { x, y };
      if (feasible(p)) pts.push(p);
    }
  return pts;
}
function solveLP() {
  const v = vertices();
  let best = v[0];
  for (const p of v) if (profit(p) > profit(best)) best = p;
  return best;
}

// ---- drawing ----
const cv = document.getElementById('lp'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, PAD = 36;
const SX = 7.5, SY = 7.5;                  // axis range 0..7.5 in data units
const px = (x) => PAD + (x / SX) * (W - 2 * PAD);
const py = (y) => H - PAD - (y / SY) * (H - 2 * PAD);

function hull(pts) {                        // order vertices around centroid
  const cx = pts.reduce((s, p) => s + p.x, 0) / pts.length;
  const cy = pts.reduce((s, p) => s + p.y, 0) / pts.length;
  return pts.slice().sort((a, b) =>
    Math.atan2(a.y - cy, a.x - cx) - Math.atan2(b.y - cy, b.x - cx));
}

function draw(targetProfit, marked) {
  ctx.clearRect(0, 0, W, H);
  // axes
  ctx.strokeStyle = '#aab4c0'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(px(0), py(0)); ctx.lineTo(px(SX), py(0));
  ctx.moveTo(px(0), py(0)); ctx.lineTo(px(0), py(SY)); ctx.stroke();
  // feasible polygon
  const poly = hull(vertices());
  ctx.beginPath();
  poly.forEach((p, i) => i ? ctx.lineTo(px(p.x), py(p.y)) : ctx.moveTo(px(p.x), py(p.y)));
  ctx.closePath();
  ctx.fillStyle = 'rgba(29,53,87,.12)'; ctx.fill();
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 1.6; ctx.stroke();
  // corners
  for (const p of poly) {
    ctx.beginPath(); ctx.arc(px(p.x), py(p.y), 3.5, 0, 7); ctx.fillStyle = '#1d3557'; ctx.fill();
  }
  // profit line 3x + 2y = targetProfit
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2; ctx.setLineDash([6, 5]);
  const x0 = 0, y0 = targetProfit / C.y;
  const y1 = 0, x1 = targetProfit / C.x;
  ctx.beginPath(); ctx.moveTo(px(x0), py(y0)); ctx.lineTo(px(x1), py(y1)); ctx.stroke();
  ctx.setLineDash([]);
  // marked optimum
  if (marked) {
    ctx.beginPath(); ctx.arc(px(marked.x), py(marked.y), 6, 0, 7);
    ctx.fillStyle = '#0a7d33'; ctx.fill();
    ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();
  }
}

const slider = document.getElementById('slider');
const maxP = profit(solveLP());            // profit at the true optimum
function sliderProfit() { return (slider.value / 100) * (maxP + 6); }
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }

function update() {
  const tp = sliderProfit();
  const touches = tp <= maxP + 1e-9;
  draw(tp, null);
  setStatus(fmt('Profit line = %tp%%v%', { tp: tp.toFixed(1), v: ' — ' + (touches
    ? 'still reachable.'
    : 'too high, the line has left the region.') }), touches ? '' : '');
}
slider.addEventListener('input', update);
document.getElementById('solve').addEventListener('click', () => {
  const best = solveLP();
  slider.value = Math.round(profit(best) / (maxP + 6) * 100);
  draw(profit(best), best);
  setStatus(fmt('Best plan: %round% tables, %round2% chairs → profit %profit% (a corner).', { round: Math.round(best.x), round2: Math.round(best.y), profit: profit(best).toFixed(0) }), 'ok');
  console.log('optimum', best, 'profit', profit(best));
});
document.getElementById('reset').addEventListener('click', () => { slider.value = 30; update(); });
update();
Result
Console

Push the profit line outward with the slider. As long as it still touches the polygon you can earn that much; the best plan is the last point it touches before leaving — and that point is always a corner. Press Solve to jump straight there. Notice the asymmetry: once a corner is proposed, checking that it beats its neighbors is instant, and unlike many puzzles on this site, finding it is fast too.

The Real Complexity

Here is the surprise that makes linear programming special among optimization problems: it is genuinely easy. It lives in the class P — solvable in time polynomial in the size of the input.

  • The geometry helps. The optimum of a linear goal over a polygon (or its higher-dimensional version, a polytope) always sits at a corner. So you never search the whole region — only the corners.
  • Simplex (George Dantzig, 1947) walks corner to corner, always uphill, and in practice reaches the answer astonishingly fast. But in the worst case it can visit exponentially many corners — the famous Klee–Minty cube (1972) forces it through all 2n2^{n} of them.
  • It's in P. In 1979 Leonid Khachiyan proved linear programming polynomial with the ellipsoid method, and in 1984 Narendra Karmarkar gave a fast interior-point method that cuts through the polygon instead of crawling its edges. Modern solvers use both ideas.
  • The integer twist. Demand that the answer be whole numbers — 3 tables, not 3.5 — and the problem becomes integer programming, which is NP-hard. The same rules, one extra word, and easy turns into intractable.

That last jump is the heart of the matter: continuous optimization slides smoothly to a corner, but forcing the answer onto a grid of whole numbers drops you straight into the world of P vs NP.

Where It Matters

Linear programming is one of the most quietly profitable inventions in all of computing. Whenever an organization squeezes the most out of limited resources, an LP is usually running underneath:

  • Airlines schedule crews and routes to burn the least fuel and pay the least overtime.
  • Refineries blend crude oils into fuels to maximize the value of every barrel.
  • Supply chains decide what to ship from which warehouse to meet demand at the lowest cost.
  • Diet and nutrition find the cheapest food basket that still hits every nutrient target — the original "diet problem" from the 1940s.
  • Machine learning uses LP at the core of support vector machines and many robust-fitting methods.

It also serves as a relaxation: hard problems like integer programming or the traveling salesman tour are often attacked by first solving an easy LP, then nudging the fractional answer toward a whole-number one.

Conclusion

Linear programming is the rare optimization problem that is both wildly useful and provably easy. Draw your goal and your limits as straight lines, and the best plan is guaranteed to sit at a corner of the region they enclose — a corner that the ellipsoid and interior-point methods reach in polynomial time.

But the moment you insist the answer come in whole units, the smooth slide to a corner is gone and you fall into the NP-hard world of integer programming. That clean break is one of the sharpest illustrations of P vs NP we have: the same picture, a single extra rule, and the difference between minutes and millennia.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/linear-programming/Content licensed under CC BY-NC 4.0.