Linear Programming and Duality Intuition TODO
Concept
Linear programming (LP) maximizes or minimizes a linear objective function subject to linear inequality constraints; the feasible region is a convex polytope, and if an optimum exists, it's achieved at one of its vertices. Every LP has a paired dual problem: weak duality says any feasible dual solution bounds the primal optimum, and strong duality says that when both sides are feasible, the two optimal values coincide. A dual variable represents the shadow price of its constraint — how much the objective improves if that constraint is relaxed by one unit. Complementary slackness ties the two together: a constraint with slack left over has a shadow price of 0, and any constraint with a positive price must be tight. So in an allocation problem, the primal answers who gets how much, while the dual simultaneously produces the prices that support that allocation.
In problems that divide up a scarce resource — auctions, blockspace allocation — the proof that an allocation is optimal and the price charged to participants come out of the same dual structure, and knowing that is what lets you settle an argument with numbers instead of opinions.
Code & Formula
# Day 13: 선형계획과 쌍대성 직관 — 경매·배분 문제의 원문제/쌍대문제
# 2변수 LP를 꼭짓점 열거로 풀고, 쌍대 LP도 같은 방식으로 풀어 강쌍대성(최적값 일치)을 확인한다.
def line_intersections(constraints):
pts = []
for i in range(len(constraints)):
for j in range(i + 1, len(constraints)):
a1, b1, _, c1 = constraints[i]
a2, b2, _, c2 = constraints[j]
det = a1 * b2 - a2 * b1
if abs(det) < 1e-9:
continue
pts.append(((c1 * b2 - c2 * b1) / det, (a1 * c2 - a2 * c1) / det))
return pts
def feasible(pt, constraints, tol=1e-6):
x, y = pt
for a, b, op, c in constraints:
val = a * x + b * y
if op == "<=" and val > c + tol:
return False
if op == ">=" and val < c - tol:
return False
return True
def solve_lp_2d(constraints, obj, maximize):
candidates = [p for p in line_intersections(constraints) if feasible(p, constraints)]
key = lambda p: obj[0] * p[0] + obj[1] * p[1]
best = max(candidates, key=key) if maximize else min(candidates, key=key)
return best, key(best)
# 원문제: maximize x + 2y s.t. x+y<=4, x+3y<=6, x,y>=0 (자원 배분: 두 재화를 두 제약 아래 최대화)
primal_constraints = [(1, 1, "<=", 4), (1, 3, "<=", 6), (1, 0, ">=", 0), (0, 1, ">=", 0)]
p_pt, p_val = solve_lp_2d(primal_constraints, (1, 2), maximize=True)
# 쌍대문제: minimize 4u + 6v s.t. u+v>=1, u+3v>=2, u,v>=0 (쌍대변수 = 각 제약의 잠재가격)
dual_constraints = [(1, 1, ">=", 1), (1, 3, ">=", 2), (1, 0, ">=", 0), (0, 1, ">=", 0)]
d_pt, d_val = solve_lp_2d(dual_constraints, (4, 6), maximize=False)
print(f"원문제 최적해 (x,y) = ({p_pt[0]:.2f}, {p_pt[1]:.2f}), 최적값 = {p_val:.2f}")
print(f"쌍대문제 최적해 (u,v) = ({d_pt[0]:.2f}, {d_pt[1]:.2f}), 최적값 = {d_val:.2f}")
print(f"강쌍대성 확인 (원문제 최적값 == 쌍대문제 최적값): {abs(p_val - d_val) < 1e-6}")
docs/code/algorithms/algorithms-13.py
Exercise
Formulate a small allocation problem with 5 to 10 bids as an LP, solve it with a solver, extract the dual values, then slightly relax one constraint and confirm the change in the objective matches its dual value.
Practical Connection
Batching orders and matching them at a single uniform clearing price can be expressed as an LP where the dual price is exactly that clearing price — a useful exercise for re-reading Verex's CLOB matching logic through an optimization lens.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.