Considere o PPL a seguir.
\begin{aligned} \max & c^{T} x \\\ & A x \leq b \\\ & x \geq 0 \end{aligned}
e o seu dual.
\begin{aligned} & \min u^{T} b \\\ & \qquad u^{T} A \geq c^{T} \\\ & u \geq 0 \end{aligned}
onde A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}, c \in \mathbb{R}^{n}, x \in \mathbb{R}^{n} e u \in \mathbb{R}^{m}.
(1) Seja \bar{x} uma solução viável para o problema (12)-(14) e \bar{u} uma solução viável para o problema (15)-(17). Mostre que c^{T} \bar{x} \leq \bar{u}^{T} b.

Passo 1

O enunciado traz o problema primal
\max c^T x,\quad A x\le b,\;x\ge0
e o dual
\min u^T b,\quad u^T A\ge c^T,\;u\ge0.
Queremos mostrar que, para qualquer viável \bar x e \bar u, vale a desigualdade de dualidade fraca
c^T\bar x\le\bar u^T b.

Passo 2

Como \bar u\ge0 e A\bar x\le b, podemos multiplicar A\bar x\le b por \bar u^T à esquerda sem inverter o sinal, obtendo
\bar u^T A\bar x \le \bar u^T b.

Passo 3

Pela viabilidade dual temos
\bar u^T A \ge c^T.
Como \bar x\ge0, multiplicamos termo a termo e somamos, o que dá
\bar u^T A\bar x \ge c^T\bar x.

Passo 4

Unindo as desigualdades dos passos anteriores, chega-se a
c^T\bar x \le \bar u^T A\bar x \le \bar u^T b,
portanto
c^T\bar x \le \bar u^T b.

Resposta

c^T\bar x \le \bar u^T b.

Exercícios relacionados