Dados os programas lineares abaixo, coloque-os na forma canônica
\begin{array}{cc}
\text { Minimizar } & c^{T} x \\\ \text { sujeito a } & A x \leq b \\\ & x \geq 0
\end{array}
Em cada caso, após colocá-los nesse formato, identifique o vetor de custos c, a matriz de restrição A, o vetor das variáveis decisórias e o vetor de requerimentos mínimos b.
Maximizar \quad-x_{1}+9 x_{2}
sujeito a \quad 2 x_{1}-4 x_{2} \leq 5
O enunciado dá um problema de programação linear e pede que ele seja colocado na forma canônica
\begin{array}{rl} \text{Minimizar} & c^{T}x \\\ \text{sujeito a} & A x \le b \\\ & x \ge 0 \end{array}
e que, após a transformação, sejam identificados: o vetor de custos c, a matriz de restrição A, o vetor das variáveis decisórias e o vetor de requerimentos mínimos b.
Dados fornecidos (copiados do enunciado):
Objetivo: maximizar -x_{1}+9x_{2}.
Restrições:
2x_{1}-4x_{2} \le 5.
x_{1}+x_{2} \ge 1.
x_{2} \ge 2.
x_{1} \le 9.
Domínios: x_{1}\ge 0,\; x_{2}\in\mathbb{R}.
O que precisamos entregar:
Escrever o problema na forma canônica (minimizar, todas as restrições do tipo \le, e todas as variáveis não-negativas).
Identificar c, A, o vetor de variáveis decisórias e b.
Passo 2
Converter o objetivo de maximização para minimização.
Regra: maximizar g(x) é equivalente a minimizar -g(x). Aqui g(x)=-x_{1}+9x_{2}. Logo uma forma equivalente em minimização é minimizar
x_{1}-9x_{2}.
Explicação didática rápida: se uma solução maximiza g, ela minimiza -g; por isso basta trocar o sinal da função objetivo.
Passo 3
Tratar as restrições para que fiquem todas no formato \le.
A restrição 2x_{1}-4x_{2} \le 5 já está no formato \le.
A restrição x_{1}+x_{2} \ge 1 transformamos multiplicando por -1:-x_{1}-x_{2} \le -1.
A restrição x_{2} \ge 2 pode ser escrita como -x_{2} \le -2. Porém ainda temos o problema de que x_{2} é, originalmente, variável livre (x_{2}\in\mathbb{R}), e a forma canônica exige variáveis não-negativas. Vamos tratar isso no próximo passo.
A restrição x_{1}\le 9 já está no formato \le.
Passo 4
Tornar todas as variáveis não-negativas (transformação necessária).
Observação: x_{1}\ge 0 já é não-negativa. Para x_{2} havia x_{2}\in\mathbb{R} mas existe a restrição x_{2}\ge 2. Isso significa que, após considerar as restrições, x_{2} efetivamente tem limite inferior 2. Uma técnica prática e simples é fazer uma mudança de variável que traduza essa cota inferior para a não-negatividade:
Defina a nova variável
y = x_{2}-2.
Então x_{2}=y+2 e a restrição x_{2}\ge 2 vira y\ge 0. Assim as variáveis no problema serão x_{1} (já \ge0) e y (também \ge0).
Explicação didática: quando uma variável tem limite inferior L, podemos escrever a variável como nova = antiga - L. A nova variável fica com limite inferior zero, o que satisfaz a exigência x\ge0. Isso evita ter que representar x_{2} como diferença de duas variáveis não-negativas (técnica alternativa).
Passo 5
Reescrever objetivo e restrições em termos de x_{1} e y.
Objetivo (minimizar):
x_{1}-9x_{2} = x_{1}-9(y+2) = x_{1}-9y-18.
Uma constante (-18) não altera o minimizador, só desloca o valor objetivo; portanto podemos ignorá-la ao escrever a forma canônica. Assim o objetivo útil é minimizar
x_{1}-9y.
Restrições, substituindo x_{2}=y+2:
2x_{1}-4x_{2} \le 5 torna-se2x_{1}-4(y+2)\le 5 \quad\Rightarrow\quad 2x_{1}-4y \le 13.(Aqui fiz a conta: -4\cdot2=-8 e ao passar para o outro lado: 5+8=13.)
x_{1}+x_{2} \ge 1 torna-sex_{1}+y+2 \ge 1 \quad\Rightarrow\quad x_{1}+y \ge -1.Em forma \le: multiplicando por -1,-x_{1}-y \le 1.Observação: essa restrição, de fato, é redundante no contexto já que x_{1}\ge0 e y\ge0 implicam x_{1}+y\ge 0\ge -1, mas mantivemos a restrição transformada para a forma canônica consistente.
A restrição x_{2}\ge 2 foi tratada pela substituição e virou y\ge 0, que faz parte da condição x\ge0.
x_{1}\le 9 permanece x_{1}\le 9.
Portanto, em termos das variáveis x_{1} e y (ambas \ge0), as desigualdades do tipo \le são: