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}-5 x_{2}-4 x_{3}+x_{4}
sujeito a \quad x_{1}-x_{2} \geq 1
O enunciado dá o problema de otimização e pede que o coloquemos na forma canônica
\text{Minimizar } c^{T}x \quad\text{sujeito a}\quad A x \leq b,\qquad x\ge 0.
Os dados do problema são (copiando do enunciado):
Objetivo (a ser maximizado): \;x_{1}-5x_{2}-4x_{3}+x_{4}.
Restrições:
\;x_{1}-x_{2}\ge 1.
\;x_{2}+5x_{3}+2x_{4}\le 4.
-x_{1}-6x_{2}-2x_{3}\ge 7.
Condição sobre variáveis: \;x_{1},x_{2},x_{3},x_{4}\ge 0.
O que é pedido explicitamente:
Colocar esse problema na forma canônica \min c^{T}x com Ax\le b e x\ge0.
Identificar os vetores/matriz c, A, x e b.
Passo 2
Vamos recordar duas coisas simples (explicando por que fazemos cada passo):
Trocar maximização por minimização: maximizar uma função f(x) é equivalente a minimizar -f(x). Isso porque o ponto que maximiza f minimiza -f.
Exemplo curto: maximizar \;2x é mesmo que minimizar -2x.
Converter restrições do tipo \ge para \le: multiplicar ambos os lados da desigualdade por -1 inverte o sinal da desigualdade. Assim \;g(x)\ge h vira -g(x)\le -h.
Exemplo curto: x\ge 3 vira -x\le -3.
Essas duas operações não mudam a região viável, apenas reescrevem-na de forma que cada restrição fique no formato \le, exigido pela forma canônica.
Passo 3
Aplicando a troca de maximização para minimização no objetivo:
Objetivo original (maximizar): \;x_{1}-5x_{2}-4x_{3}+x_{4}.
Objetivo convertido (minimizar): multiplicamos por -1, obtendo
\text{Minimizar }\; -x_{1}+5x_{2}+4x_{3}-x_{4}.
Portanto os coeficientes do vetor de custos c serão os coeficientes dessa expressão de minimização (veremos isso explicitamente depois).
Passo 4
Converter as restrições para o formato \le, uma a uma:
Da restrição \;x_{1}-x_{2}\ge 1, multiplicando por -1 temos
-x_{1}+x_{2}\le -1.
A restrição \;x_{2}+5x_{3}+2x_{4}\le 4 já está no formato \le; mantemos:
x_{2}+5x_{3}+2x_{4}\le 4.
Da restrição -x_{1}-6x_{2}-2x_{3}\ge 7, multiplicando por -1 temos
x_{1}+6x_{2}+2x_{3}\le -7.
Observação didática: é perfeitamente aceitável que componentes do vetor b fiquem negativos (a forma canônica não exige b\ge0). O importante é que todas as desigualdades estejam escritas como \le.
Passo 5
Agora escrevemos o sistema na forma matricial \;A x \le b, com x=(x_{1},x_{2},x_{3},x_{4})^{T}.
Cada linha de A contém os coeficientes das variáveis \;x_{1},x_{2},x_{3},x_{4} numa restrição.
Das restrições convertidas temos as linhas:
Primeira linha (da restrição 1 convertida): coeficientes \;-1,\,1,\,0,\,0 e lado direito -1.
Segunda linha (restrição 2): coeficientes \;0,\,1,\,5,\,2 e lado direito 4.
Terceira linha (restrição 3 convertida): coeficientes \;1,\,6,\,2,\,0 e lado direito -7.
x = \begin{pmatrix}x_{1}\\[4pt]x_{2}\\[4pt]x_{3}\\[4pt]x_{4}\end{pmatrix},\qquad x\ge 0 \text{ (condição já satisfeita no enunciado).}çãá
Vetor de custos c: são os coeficientes do objetivo na forma de minimização -x_{1}+5x_{2}+4x_{3}-x_{4}, logo
c = \begin{pmatrix}-1\\[4pt]5\\[4pt]4\\[4pt]-1\end{pmatrix}.
Matriz de restrição A e vetor b já obtidos no passo anterior.
Prontinho — o problema está na forma canônica \min c^{T}x sujeito a Ax\le b, x\ge0. Força aí, isso é exatamente o que costuma pedir a prova: trocar maximização por minimização e transformar todo \ge em \le por multiplicação por -1.]