Introduction

Suppose you are a factory manager. You choose how many units of each product to make in order to maximize profit, subject to limits on raw materials. That is a linear program: maximize a linear objective over variables constrained by linear inequalities.

Now suppose a supplier knocks on your door and says: "I'll buy all your raw materials. What's the minimum price per unit I must pay so you'd rather sell me the materials than run the factory?" Remarkably, that second question — minimize total payment subject to not undercutting any product's profit — has the exact same optimal value as the first. They are duals of each other.

This is not a coincidence or an approximation. It is the Strong Duality Theorem, proven in 1947 by John von Neumann and refined by David Gale, Harold Kuhn, and Albert Tucker. Every feasible linear program that is bounded has a dual that is also feasible and bounded, and primal optimum = dual optimum exactly. The dual is a built-in certificate: it says "you cannot possibly do better" and it proves it.

Watch the Bounds Meet

Below is a two-variable primal LP: maximize c1x1+c2x2c_1 x_1 + c_2 x_2 subject to two resource constraints. Adjust the objective coefficients with the sliders. The shaded region is the feasible set; the red dot is the primal optimum. The dual provides an upper bound — drag to see it descend and meet the primal value exactly.

<p class="hint">Primal LP: <b>maximize c₁x₁ + c₂x₂</b> subject to x₁ + 2x₂ ≤ R₁, 3x₁ + x₂ ≤ R₂, x₁,x₂ ≥ 0.<br>
    Adjust the objective and resources. The <span class="dot-primal">●</span> is the primal optimum; the dual bound always meets it.</p>
<div class="controls">
  <label>c₁ = <span id="lc1">3</span> <input type="range" id="c1" min="1" max="9" value="3"></label>
  <label>c₂ = <span id="lc2">5</span> <input type="range" id="c2" min="1" max="9" value="5"></label>
  <label>R₁ = <span id="lr1">8</span> <input type="range" id="r1" min="2" max="12" value="8"></label>
  <label>R₂ = <span id="lr2">9</span> <input type="range" id="r2" min="2" max="12" value="9"></label>
</div>
<canvas id="cv" width="320" height="280"></canvas>
<div class="vals">
  <div class="val-box primal-box">Primal optimum: <b id="vprimal">—</b></div>
  <div class="val-box dual-box">Dual bound: <b id="vdual">—</b></div>
  <div class="val-box gap-box">Gap: <b id="vgap">—</b></div>
</div>
<div class="optimum-detail" id="detail"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .5rem; line-height: 1.5; }
.dot-primal { color: #e63946; }
.controls { display: grid; grid-template-columns: 1fr 1fr; gap: .35rem .8rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .82rem; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 0; accent-color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f7f9fb; margin-bottom: .55rem; max-width: 100%; }
.vals { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
.val-box { flex: 1; min-width: 90px; padding: .35rem .6rem; border-radius: 7px; font-size: .82rem; text-align: center; }
.primal-box { background: #fde8ea; color: #7a111b; }
.dual-box   { background: #e0ecff; color: #0d2a5e; }
.gap-box    { background: #e6fae9; color: #0a5c23; font-weight: 700; }
.optimum-detail { font-size: .8rem; color: #555; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Primal LP (P):  max  c1*x1 + c2*x2
//   s.t.   x1 + 2*x2 <= R1   (y1 dual var)
//          3*x1 +  x2 <= R2  (y2 dual var)
//          x1, x2 >= 0
//
// Dual LP (D):    min  R1*y1 + R2*y2
//   s.t.   y1 + 3*y2 >= c1   (x1 constraint)
//          2*y1 + y2  >= c2   (x2 constraint)
//          y1, y2 >= 0
//
// Corner points of primal feasible region:
//   O  = (0,0)
//   A  = (R2/3, 0)           [3x1+x2=R2 meets x2=0]
//   B  = (R1/2, 0) — only valid if R1/2 <= R2/3? No: (R2/3,0) first.
//   Actually corners: O, (R2/3,0), intersection, (0, R1/2)
//   Intersection of x1+2x2=R1 and 3x1+x2=R2:
//     x2 = (3*R1 - R2)/5, x1 = (2*R2 - R1)/5  (if both >=0)
//
// Strong Duality: primal opt == dual opt (both solvable, both bounded).
// The dual optimum is found by checking dual corner points:
//   Dual feasible region corners: intersection of: y1+3y2=c1, 2y1+y2=c2 etc.
//   Dual corners: (0, c1/3), (c2/2, 0), and intersection of both binding:
//     y1+3y2=c1, 2y1+y2=c2 => y1=(2c2-c1)/5, y2=(2c1-c2)/5 (if >=0, else degenerate)
//   Dual objective at each corner evaluated and minimum taken.

function solve(c1, c2, R1, R2) {
  // Primal corners
  const corners = [];
  corners.push({ x1: 0, x2: 0 });
  corners.push({ x1: R2 / 3, x2: 0 });
  corners.push({ x1: 0, x2: R1 / 2 });
  // Intersection: x1+2x2=R1, 3x1+x2=R2 => 5x1=2R2-R1, 5x2=3R1-R2
  const ix1 = (2 * R2 - R1) / 5;
  const ix2 = (3 * R1 - R2) / 5;
  if (ix1 >= -1e-9 && ix2 >= -1e-9) corners.push({ x1: Math.max(0, ix1), x2: Math.max(0, ix2) });

  let bestP = -Infinity, bestX1 = 0, bestX2 = 0;
  for (const { x1, x2 } of corners) {
    if (x1 < -1e-9 || x2 < -1e-9) continue;
    if (x1 + 2 * x2 > R1 + 1e-9) continue;
    if (3 * x1 + x2 > R2 + 1e-9) continue;
    const obj = c1 * x1 + c2 * x2;
    if (obj > bestP) { bestP = obj; bestX1 = x1; bestX2 = x2; }
  }

  // Dual corners (minimization over y1,y2>=0 s.t. y1+3y2>=c1, 2y1+y2>=c2)
  const dCorners = [];
  dCorners.push({ y1: c1, y2: 0 });              // A+D: y2=0, y1=c1
  dCorners.push({ y1: 0, y2: c2 });              // B+C: y1=0, y2=c2
  dCorners.push({ y1: c2 / 2, y2: 0 });          // B+D: y2=0, 2y1=c2 => y1=c2/2
  dCorners.push({ y1: 0, y2: c1 / 3 });          // A+C: y1=0, 3y2=c1 => y2=c1/3
  // A+B intersection: y1+3y2=c1, 2y1+y2=c2 => y1=(3c2-c1)/5, y2=(2c1-c2)/5
  const dy1 = (3 * c2 - c1) / 5;
  const dy2 = (2 * c1 - c2) / 5;
  if (dy1 >= -1e-9 && dy2 >= -1e-9) dCorners.push({ y1: Math.max(0, dy1), y2: Math.max(0, dy2) });

  let bestD = Infinity, bDy1 = 0, bDy2 = 0;
  for (const { y1, y2 } of dCorners) {
    if (y1 < -1e-9 || y2 < -1e-9) continue;
    if (y1 + 3 * y2 < c1 - 1e-9) continue;
    if (2 * y1 + y2 < c2 - 1e-9) continue;
    const obj = R1 * y1 + R2 * y2;
    if (obj < bestD) { bestD = obj; bDy1 = y1; bDy2 = y2; }
  }

  return { primal: bestP, dual: bestD, x1: bestX1, x2: bestX2, y1: bDy1, y2: bDy2 };
}

const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
const PAD = 36;
const SCALE = (W - PAD * 2) / 13; // 0..13 in each axis

function toCanvas(x, y) {
  return [PAD + x * SCALE, H - PAD - y * SCALE];
}

function drawScene(c1, c2, R1, R2, result) {
  ctx.clearRect(0, 0, W, H);

  // Axes
  ctx.strokeStyle = '#aab'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(...toCanvas(0, 0)); ctx.lineTo(...toCanvas(13, 0)); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(...toCanvas(0, 0)); ctx.lineTo(...toCanvas(0, 13)); ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#666'; ctx.font = '11px system-ui';
  ctx.fillText('x₁', toCanvas(13, 0)[0] - 12, toCanvas(13, 0)[1] + 12);
  ctx.fillText('x₂', toCanvas(0, 13)[0] - 16, toCanvas(0, 13)[1] + 4);

  // Tick marks
  for (let v = 2; v <= 12; v += 2) {
    ctx.fillStyle = '#999'; ctx.font = '9px system-ui';
    const [px] = toCanvas(v, 0); ctx.fillText(v, px - 4, H - PAD + 12);
    const [, py] = toCanvas(0, v); ctx.fillText(v, PAD - 18, py + 4);
  }

  // Feasible region (filled polygon)
  const corners = [];
  corners.push([0, 0]);
  // x2=0: x1 from 0 to min(R2/3, R1)
  corners.push([Math.min(R2 / 3, R1), 0]);
  // Intersection if exists
  const ix1 = (2 * R2 - R1) / 5;
  const ix2 = (3 * R1 - R2) / 5;
  if (ix1 > 1e-9 && ix2 > 1e-9 && ix1 < R2 / 3 + 1e-9) corners.push([ix1, ix2]);
  // x1=0: x2 from 0 to min(R1/2, R2)
  corners.push([0, Math.min(R1 / 2, R2)]);

  ctx.fillStyle = 'rgba(29,53,87,0.12)';
  ctx.beginPath();
  corners.forEach(([x, y], i) => {
    const [cx, cy] = toCanvas(x, y);
    i === 0 ? ctx.moveTo(cx, cy) : ctx.lineTo(cx, cy);
  });
  ctx.closePath(); ctx.fill();

  // Constraint lines
  ctx.setLineDash([4, 3]);
  // x1 + 2x2 = R1: x2=(R1-x1)/2
  ctx.strokeStyle = '#457b9d'; ctx.lineWidth = 1.5;
  ctx.beginPath();
  ctx.moveTo(...toCanvas(0, R1 / 2));
  ctx.lineTo(...toCanvas(R1, 0));
  ctx.stroke();
  // 3x1 + x2 = R2: x2=R2-3x1
  ctx.strokeStyle = '#2a9d8f'; ctx.lineWidth = 1.5;
  ctx.beginPath();
  ctx.moveTo(...toCanvas(0, R2));
  ctx.lineTo(...toCanvas(R2 / 3, 0));
  ctx.stroke();
  ctx.setLineDash([]);

  // Objective iso-line through optimum: c1*x1+c2*x2 = primal
  if (result.primal > 0) {
    const z = result.primal;
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 1.5;
    ctx.setLineDash([3, 3]);
    const pts = [];
    if (c2 > 0) pts.push([0, z / c2]);
    if (c1 > 0) pts.push([z / c1, 0]);
    if (pts.length >= 2) {
      ctx.beginPath();
      ctx.moveTo(...toCanvas(pts[0][0], pts[0][1]));
      ctx.lineTo(...toCanvas(pts[1][0], pts[1][1]));
      ctx.stroke();
    }
    ctx.setLineDash([]);
  }

  // Legend labels on lines
  ctx.font = '10px system-ui';
  ctx.fillStyle = '#457b9d';
  ctx.fillText('x₁+2x₂=R₁', toCanvas(1, (R1 - 1) / 2)[0], toCanvas(1, (R1 - 1) / 2)[1] - 5);
  ctx.fillStyle = '#2a9d8f';
  ctx.fillText('3x₁+x₂=R₂', toCanvas(R2 / 3 - 1.2, 0.4)[0], toCanvas(R2 / 3 - 1.2, 0.4)[1] - 4);

  // Primal optimum dot
  const [ox, oy] = toCanvas(result.x1, result.x2);
  ctx.fillStyle = '#e63946';
  ctx.beginPath(); ctx.arc(ox, oy, 5, 0, 2 * Math.PI); ctx.fill();

  // Coordinates label
  ctx.fillStyle = '#e63946'; ctx.font = 'bold 10px system-ui';
  ctx.fillText(`(${result.x1.toFixed(1)}, ${result.x2.toFixed(1)})`, ox + 7, oy - 6);
}

function update() {
  const c1 = +document.getElementById('c1').value;
  const c2 = +document.getElementById('c2').value;
  const R1 = +document.getElementById('r1').value;
  const R2 = +document.getElementById('r2').value;
  document.getElementById('lc1').textContent = c1;
  document.getElementById('lc2').textContent = c2;
  document.getElementById('lr1').textContent = R1;
  document.getElementById('lr2').textContent = R2;

  const result = solve(c1, c2, R1, R2);
  drawScene(c1, c2, R1, R2, result);

  const gap = Math.abs(result.dual - result.primal);
  document.getElementById('vprimal').textContent = result.primal.toFixed(2);
  document.getElementById('vdual').textContent = result.dual.toFixed(2);
  document.getElementById('vgap').textContent = gap < 0.001 ? '0 ✓' : gap.toFixed(3);
  document.getElementById('detail').textContent =
    fmt('Primal: x₁=x₁=%x1%, x₂=%x2% | Dual: y₁=y₁=%y1%, y₂=%y2%', { x1: result.x1.toFixed(2), x2: result.x2.toFixed(2), y1: result.y1.toFixed(2), y2: result.y2.toFixed(2) });
  console.log('LP solve: primal=', result.primal.toFixed(4), 'dual=', result.dual.toFixed(4), 'gap=', gap.toFixed(6));
}

['c1','c2','r1','r2'].forEach(id => document.getElementById(id).addEventListener('input', update));
update();
Result
Console

Every position of the sliders produces a different LP, but the gap between the primal and dual is always zero. That closing gap is the Strong Duality Theorem made visible.

The Strong Duality Theorem

The precise status of LP duality: proven true (not a conjecture, not a Millennium Prize problem — a textbook theorem proven in 1947).

Here is the chain of results that makes duality work:

  • Weak Duality (always holds): any feasible dual solution gives an upper bound on the primal optimum. This is trivial to prove — multiply the dual variables by the constraint rows and the bound falls out of the arithmetic.
  • Strong Duality (the hard part): if the primal has an optimum, the dual does too, and they are equal. The original proof used the minimax theorem; later proofs go through the simplex method or Farkas' lemma.
  • Complementary Slackness: at the optimum, for every primal variable either it is zero or its dual constraint is tight, and vice versa. This gives a practical test for optimality without re-solving the dual.

The key proof ingredient is Farkas' Lemma (1902): exactly one of two linear systems is feasible. From it you can show that if the primal optimum is bounded, the dual is feasible at the same value — no gap.

Contrast with integer programming: the moment you require variables to be whole numbers, the LP relaxation and its dual may have values strictly between the LP relaxation's optimum and the integer optimum. That gap — the integrality gap — is why integer programming is NP-hard while linear programming is polynomial. See also P vs NP for where that hardness barrier sits.

Where It Matters

LP duality is not just theory — it is the engine inside many practical algorithms:

  • Game theory: von Neumann's minimax theorem for zero-sum games is equivalent to LP duality. The optimal mixed strategy for each player is the primal/dual solution.
  • Max-flow min-cut: the famous theorem (Ford-Fulkerson, 1956) is exactly the LP duality statement applied to a network flow LP. The minimum cut is the dual certificate for the maximum flow.
  • Simplex pricing: the simplex method's "pricing" step uses the dual to decide which variable to enter the basis — without solving two programs separately.
  • Support Vector Machines: training an SVM is a quadratic program whose dual reveals the support vectors and enables the kernel trick that powers modern ML classifiers.
  • Sensitivity analysis: shadow prices — the dual variables at the optimum — measure how much the objective changes per unit of each resource. Operations researchers read these directly off the dual to guide decisions.
  • Approximation algorithms: for many NP-hard problems (like set cover), the LP relaxation and its dual yield the best known approximation ratios, with the gap certified by duality.

Conclusion

Linear programming duality is one of the most satisfying results in optimization: every feasible bounded LP contains, hidden inside it, a second problem whose optimal value exactly equals the first. The strong duality theorem — proven in 1947 — is not a conjecture waiting to be resolved; it is a fact that you can use as a guarantee.

The deeper reason to care is what breaks when you leave the LP world. Require integer solutions and the dual gap can open up; require nonconvexity and even weak duality can fail. LP duality sits at the precise boundary where optimization becomes provably easy, and understanding that boundary is the first step toward understanding why harder problems are hard. As P vs NP reminds us, that boundary matters enormously.

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-duality/Content licensed under CC BY-NC 4.0.