The Bound

Weak Duality

A dual-feasible point is an upper-bound certificate for a primal maximization problem. This lesson uses an easy feasible price vector before the optimum is known. The number it produces is not guessed; it is recomputed from the primal right sides.

highlighted = computed this step

A feasible price vector

The point y=(1/2, 1/2) is dual feasible. Why: its prices cover each primal objective coefficient.

y=(1/2,1/2)y=(1/2, 1/2)
Weak duality boundA dual-feasible point gives an exact upper bound on the primal maximum.dual feasible bound1/21/24

Upper bound

Those prices give b dot y=4. Why: weak duality says every dual-feasible value is an upper bound on the primal max.

b⋅y=4b\cdot y=4
Weak duality boundA dual-feasible point gives an exact upper bound on the primal maximum.dual feasible bound1/21/24

Loose but valid

The bound 4 is above the optimal value 8/3. Why: a certificate can be valid before it is tight.

c⋅x∗≤b⋅yc\cdot x^*\le b\cdot y
Weak duality boundA dual-feasible point gives an exact upper bound on the primal maximum.dual feasible bound1/21/24

Diagram note

The diagram shows a recomputed dual-feasible point and its recomputed bound. Pixel positions are rounded for layout; every number shown is exact.

dual feasible means upper bound\text{dual feasible means upper bound}
Weak duality boundA dual-feasible point gives an exact upper bound on the primal maximum.dual feasible bound1/21/24