Weak Duality Theorem

Recall the standard-form primal LP and its dual:

$$\text{(P):}\quad \max\ \mathbf{c}^\top\mathbf{x}\quad \text{s.t.}\quad A\mathbf{x}\le \mathbf{b},\ \mathbf{x}\ge \mathbf{0}.$$ $$\text{(D):}\quad \min\ \mathbf{b}^\top\mathbf{y}\quad \text{s.t.}\quad A^\top\mathbf{y}\ge \mathbf{c},\ \mathbf{y}\ge \mathbf{0}.$$

The Weak Duality Theorem states that for every primal feasible $\mathbf{x}$ and every dual feasible $\mathbf{y}$,

$$\mathbf{c}^\top\mathbf{x}\ \le\ \mathbf{b}^\top\mathbf{y}.$$

Proof. Since $\mathbf{x}\ge\mathbf{0}$ and $A^\top\mathbf{y}\ge \mathbf{c}$, we have $\mathbf{c}^\top\mathbf{x}\le (A^\top\mathbf{y})^\top\mathbf{x}=\mathbf{y}^\top(A\mathbf{x})$. Since $\mathbf{y}\ge\mathbf{0}$ and $A\mathbf{x}\le\mathbf{b}$, we have $\mathbf{y}^\top(A\mathbf{x})\le \mathbf{y}^\top\mathbf{b}=\mathbf{b}^\top\mathbf{y}$. Chaining the two gives the result. $\blacksquare$

Tiny illustration. Let $\mathbf{c}=\begin{bmatrix}3\\2\end{bmatrix}$, $\mathbf{b}=\begin{bmatrix}4\\5\end{bmatrix}$, $A=\begin{bmatrix}1&1\\1&2\end{bmatrix}$. Take $\mathbf{x}=\begin{bmatrix}1\\1\end{bmatrix}$ (primal feasible: $A\mathbf{x}=\begin{bmatrix}2\\3\end{bmatrix}\le\mathbf{b}$) and $\mathbf{y}=\begin{bmatrix}2\\1\end{bmatrix}$ (dual feasible: $A^\top\mathbf{y}=\begin{bmatrix}3\\4\end{bmatrix}\ge\mathbf{c}$). Then

$$\mathbf{c}^\top\mathbf{x}=3+2=5,\qquad \mathbf{b}^\top\mathbf{y}=8+5=13,$$

and indeed $5\le 13$.