Por que, para um primal do tipo Max \(cx\) sujeito a \(Ax\le b,\;x\ge0\), qualquer vetor dual viável \(y\) satisfaz \(yb \ge cx\) para todo \(x\) viável?

Porque \(yA\ge c\) e \(Ax\le b\) com \(y\ge0,\;x\ge0\) implicam \( (yA-c)x\ge0\Rightarrow yAx\ge cx\) e, como \(y\ge0\) e \(Ax\le b\), tem-se \(yAx\le yb\); logo \(cx\le yb\).

Detalhamento:
Partindo de \(yA\ge c\) e \(x\ge0\) segue \( (yA-c)x\ge0\).
Assim \(yAx\ge cx\).
Como \(Ax\le b\) e \(y\ge0\), multiplica-se por \(y\) obtendo \(yAx\le yb\).
Combinando as duas desigualdades vem \(cx\le yb\), que mostra que \(yb\) é um limite superior para o valor primal \(cx\).

Exemplo:
Considere o primal: maximize \(Z=3x_1+2x_2\) sujeito a
\( \begin{pmatrix}1 & 2\\[4pt]2 & 1\end{pmatrix}\begin{pmatrix}x_1\\[4pt]x_2\end{pmatrix}\le\begin{pmatrix}4\\[4pt]3\end{pmatrix},\; x\ge0.\)
O dual é minimizar \(W=4y_1+3y_2\) sujeito a
\( (y_1,y_2)\begin{pmatrix}1 & 2\\[4pt]2 & 1\end{pmatrix}\ge(3,2),\; y\ge0.\)
Escolha viáveis: \(x=(0,1)\) (pois \(Ax=(2,1)\le(4,3)\)) e \(y=(1,1)\) (pois \(yA=(3,3)\ge(3,2)\)).
Calcula-se \(cx=3\cdot0+2\cdot1=2\) e \(yb=4\cdot1+3\cdot1=7\).
Verifica-se \(cx=2\le7=yb\), ilustrando a desigualdade geral \(cx\le yb\).