Coloque o problema linear a seguir na forma padrão.
\min _{\mathbf{x}}\left(3 x_{1}-a x_{2}+2 x_{3}+b\right) \text { sujeito a }\left\{\begin{array}{c} 5 x_{1}+x_{2} \geq 3 \\\ x_{2}-c x_{3} \geq 1 \\\ x_{1}+x_{2}+x_{3} \geq-2 \end{array}\right\}

Passo 1

O enunciado pede: “Coloque o problema linear a seguir na forma padrão.” Vou listar claramente o que o problema dá e o que é pedido.
Dados do problema:
\text{Minimizar}\quad 3x_{1}-a x_{2}+2x_{3}+b
sujeito a
\begin{cases} 5x_{1}+x_{2}\ge 3,\\[4pt] x_{2}-c x_{3}\ge 1,\\[4pt] x_{1}+x_{2}+x_{3}\ge -2, \end{cases}
onde a, b, c são parâmetros (constantes) fornecidos no enunciado.
O que se pede: reescrever esse problema na forma padrão (igualdades e variáveis não-negativas).
Informações relevantes extraídas:
  • Há três variáveis originais: x_{1},x_{2},x_{3}.
  • As três restrições são do tipo `` \ge’’ (maior-igual).
  • Não há indicação de que x_{1},x_{2},x_{3} sejam não-negativas; portanto cada x_{j} é, em princípio, variável livre (pode ser negativa).
  • O termo constante b na função objetivo é um termo independente de x.]

Passo 2

Decisão sobre a forma padrão a usar (e por quê). A forma padrão que vou adotar é a usual em programação linear:
\text{minimizar}\quad \mathbf{c}^{T}\mathbf{z} + \text{constante} \qquad\text{s.a.}\qquad A\mathbf{z}=\mathbf{d},\quad \mathbf{z}\ge 0,
ou seja: todas as restrições como igualdades e todas as variáveis não-negativas. Para chegar a isso é necessário:
  1. transformar cada variável livre x_{j} em diferença de duas variáveis não-negativas;
  2. transformar cada desigualdade em igualdade introduzindo variáveis de folga (slack) ou surplus conforme o sinal da desigualdade; eventualmente multiplicar por -1 para obter RHS positivo e facilitar a forma padrão.
Vou aplicar essas duas transformações passo a passo.

Passo 3

Transformação das variáveis livres em variáveis não-negativas. Para cada j=1,2,3 escrevo
x_{j}=x_{j}^{+}-x_{j}^{-},
com x_{j}^{+}\ge 0 e x_{j}^{-}\ge 0. Assim introduzo seis variáveis não-negativas:
x_{1}^{+},\;x_{1}^{-},\;x_{2}^{+},\;x_{2}^{-},\;x_{3}^{+},\;x_{3}^{-}.
Substituindo nas expressões, qualquer coeficiente multiplicará x_{j}^{+} com sinal direto e x_{j}^{-} com sinal invertido.

Passo 4

Tratar as desigualdades. As duas primeiras restrições são do tipo \ge; para \ge é comum subtrair uma variável surplus (que é não-negativa) para obter igualdade. A terceira restrição tem RHS negativo (-2); para obter RHS positivo e uma forma padrão simples vou multiplicar a terceira restrição por -1, transformando-a em uma desigualdade do tipo \le, e depois adiciono uma variável de folga (slack) não-negativa.
Introduzo:
  • surplus s_{1}\ge 0 para a restrição 1,
  • surplus s_{2}\ge 0 para a restrição 2,
  • slack t_{3}\ge 0 para a (multiplicada) restrição 3.
Agora escrevo cada restrição em igualdade, após substituir x_{j}=x_{j}^{+}-x_{j}^{-}.

Passo 5

Escrever as igualdades após substituições (cada fórmula está em termos das variáveis não-negativas). Ordem escolhida das variáveis não-negativas para montar o vetor \mathbf{z}:
\mathbf{z}=\bigl(x_{1}^{+},\;x_{1}^{-},\;x_{2}^{+},\;x_{2}^{-},\;x_{3}^{+},\;x_{3}^{-},\;s_{1},\;s_{2},\;t_{3}\bigr)^{T}.
Agora as três igualdades:
  1. Da restrição 5x_{1}+x_{2}\ge 3 (subtrai-se s_{1}):
5(x_{1}^{+}-x_{1}^{-})+(x_{2}^{+}-x_{2}^{-})-s_{1}=3.
  1. Da restrição x_{2}-c x_{3}\ge 1 (subtrai-se s_{2}):
(x_{2}^{+}-x_{2}^{-})-c(x_{3}^{+}-x_{3}^{-})-s_{2}=1.
  1. Da restrição x_{1}+x_{2}+x_{3}\ge -2 multiplico por -1 e adiciono slack t_{3}:
-\,\bigl(x_{1}^{+}-x_{1}^{-}\bigr)-\bigl(x_{2}^{+}-x_{2}^{-}\bigr)-\bigl(x_{3}^{+}-x_{3}^{-}\bigr)+t_{3}=2.
(isto resulta de -x_{1}-x_{2}-x_{3}\le 2 e então acrescentar t_{3}\ge 0.)

Passo 6

Colocar a forma matricial A\mathbf{z}=\mathbf{d} explicitando A, \mathbf{d} e o vetor objetivo \mathbf{c}.
As igualdades acima correspondem à matriz A (cada linha é uma restrição) com as colunas na ordem de \mathbf{z}. Escrevendo coeficientes:
  • Linha 1 (restrição 1):
(5,\;-5,\;1,\;-1,\;0,\;0,\;-1,\;0,\;0)
= coefs de x_{1}^{+},x_{1}^{-},x_{2}^{+},x_{2}^{-},x_{3}^{+},x_{3}^{-},s_{1},s_{2},t_{3} e RHS =3.
  • Linha 2 (restrição 2):
(0,\;0,\;1,\;-1,\;-c,\;c,\;0,\;-1,\;0)
e RHS =1.
  • Linha 3 (restrição 3, após multiplicar por -1):
(-1,\;1,\;-1,\;1,\;-1,\;1,\;0,\;0,\;1)
e RHS =2.
Logo
A= \begin{pmatrix} 5 & -5 & 1 & -1 & 0 & 0 & -1 & 0 & 0\\[4pt] 0 & 0 & 1 & -1 & -c & c & 0 & -1 & 0\\[4pt] -1 & 1 & -1 & 1 & -1 & 1 & 0 & 0 & 1 \end{pmatrix}, \qquad \mathbf{d}=\begin{pmatrix}3\\[4pt]1\\[4pt]2\end{pmatrix}.]

Passo 7

Construir o vetor objetivo na nova variável \mathbf{z}. A função objetivo original é
3x_{1}-a x_{2}+2x_{3}+b.
Substituindo x_{j}=x_{j}^{+}-x_{j}^{-} obtemos
3x_{1}^{+}-3x_{1}^{-}-a x_{2}^{+}+a x_{2}^{-}+2x_{3}^{+}-2x_{3}^{-}+b.
Portanto o termo linear da função objetivo em \mathbf{z} tem coeficientes
\mathbf{c}=(3,\;-3,\;-a,\;a,\;2,\;-2,\;0,\;0,\;0)^{T},
e existe a constante aditiva b que não depende de \mathbf{z}. Note que b não altera a localização do ótimo (apenas o valor objetivo).

Passo 8

Escrever finalmente o problema na forma padrão procurada:
\text{minimizar}\quad \mathbf{c}^{T}\mathbf{z}+b
sujeito a
A\mathbf{z}=\mathbf{d},\qquad \mathbf{z}\ge 0,
onde \mathbf{z}, A, \mathbf{d} e \mathbf{c} são os definidos nos passos anteriores (repito-os aqui de forma compacta):
\mathbf{z}=\bigl(x_{1}^{+},x_{1}^{-},x_{2}^{+},x_{2}^{-},x_{3}^{+},x_{3}^{-},s_{1},s_{2},t_{3}\bigr)^{T},
\mathbf{c}=\begin{pmatrix}3\\[4pt]-3\\[4pt]-a\\[4pt]a\\[4pt]2\\[4pt]-2\\[4pt]0\\[4pt]0\\[4pt]0\end{pmatrix}, \qquad \mathbf{d}=\begin{pmatrix}3\\[4pt]1\\[4pt]2\end{pmatrix},
A= \begin{pmatrix} 5 & -5 & 1 & -1 & 0 & 0 & -1 & 0 & 0\\[6pt] 0 & 0 & 1 & -1 & -c & c & 0 & -1 & 0\\[6pt] -1 & 1 & -1 & 1 & -1 & 1 & 0 & 0 & 1 \end{pmatrix},
com \mathbf{z}\ge 0 e constante na função objetivo igual a b.]

Resposta

\displaystyle \text{minimizar}\quad \mathbf{c}^{T}\mathbf{z}+b\n
\displaystyle \text{sujeito a}\quad A\mathbf{z}=\mathbf{d},\quad \mathbf{z}\ge 0,\n
com\n
\displaystyle \mathbf{z}=\bigl(x_{1}^{+},x_{1}^{-},x_{2}^{+},x_{2}^{-},x_{3}^{+},x_{3}^{-},s_{1},s_{2},t_{3}\bigr)^{T},\n
\displaystyle \mathbf{c}=(3,\,-3,\,-a,\;a,\;2,\,-2,\;0,\;0,\;0)^{T},\n
\displaystyle \mathbf{d}=(3,\;1,\;2)^{T},\n
\displaystyle A= \begin{pmatrix} 5 & -5 & 1 & -1 & 0 & 0 & -1 & 0 & 0\\[6pt] 0 & 0 & 1 & -1 & -c & c & 0 & -1 & 0\\[6pt] -1 & 1 & -1 & 1 & -1 & 1 & 0 & 0 & 1 \end{pmatrix}.]

Exercícios relacionados