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
\begin{gathered} x_{1}+x_{2} \geq 1 \\\ x_{2} \geq 2 \\\ x_{1} \leq 9 \\\ x_{1} \geq 0, x_{2} \in \mathbb{R} \end{gathered}

Passo 1

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:
    1. 2x_{1}-4x_{2} \le 5.
    2. x_{1}+x_{2} \ge 1.
    3. x_{2} \ge 2.
    4. 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:
  1. 2x_{1}-4x_{2} \le 5 torna-se 2x_{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.)
  2. x_{1}+x_{2} \ge 1 torna-se x_{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.
  3. 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.
  4. 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:
\begin{array}{rcl} 2x_{1}-4y &\le& 13,\\[4pt] - x_{1}-y &\le& 1,\\[4pt] x_{1} &\le& 9. \end{array}]

Passo 6

Montar a forma canônica \min c^{T}x sujeito a A x \le b,\; x\ge0.
Escolhendo o vetor de variáveis como
x = \begin{pmatrix} x_{1} \\[4pt] y \end{pmatrix},\qquad\text{onde } y = x_{2}-2 \text{ e } x_{1},y\ge0,
a função objetivo (linha) é
\text{minimizar }\; c^{T}x \quad\text{com}\quad c = \begin{pmatrix}1\\[4pt]-9\end{pmatrix},
pois o objetivo é minimizar 1\cdot x_{1} + (-9)\cdot y (descartando a constante -18).
A matriz A e o vetor b correspondem às três desigualdades listadas (na mesma ordem):
A = \begin{pmatrix} 2 & -4\\[4pt] -1 & -1\\[4pt] 1 & 0 \end{pmatrix},\qquad b = \begin{pmatrix}13\\[4pt]1\\[4pt]9\end{pmatrix}.
Verificação rápida (cada linha de A x \le b corresponde a uma das desigualdades):
  • Linha 1: 2x_{1}-4y \le 13.
  • Linha 2: -x_{1}-y \le 1.
  • Linha 3: x_{1}+0\cdot y \le 9.]

Resposta

c=\begin{pmatrix}1\\[4pt]-9\end{pmatrix}
A=\begin{pmatrix}2 & -4\\[4pt]-1 & -1\\[4pt]1 & 0\end{pmatrix}
x=\begin{pmatrix}x_{1}\\[4pt]y\end{pmatrix},\quad\text{onde }y=x_{2}-2\text{ e }x_{1},y\ge0
b=\begin{pmatrix}13\\[4pt]1\\[4pt]9\end{pmatrix}

Exercícios relacionados