Dado o sistema A x=b, x \geq 0.
(1) Defina uma solução viável básica para esse sistema.
(2) Considere o sistema
\begin{array}{r} 2 x_{1}+x_{2}+x_{3}=6 \\\ x_{2}+x_{4}=4 \\\ x_{1}, x_{2}, x_{3}, x_{4} \geq 0 \end{array}
Encontre todas as soluções viável básica associada a esse sistema.

Passo 1

O enunciado pede dois itens. No item (1) queremos a definição de solução viável básica para um sistema da forma
A x = b,\quad x\ge0,
que é parte da teoria de programação linear. No item (2) temos um caso concreto com duas equações e quatro variáveis, e precisamos listar todas as soluções viáveis básicas possíveis.

Passo 2

Uma solução viável básica para
A x = b,\quad x\ge0,
é obtida assim: escolhe-se um subconjunto B de índices de variáveis de tamanho m (número de equações) tal que a submatriz A_B (colunas de A correspondentes a B) seja invertível; define-se as variáveis não-básicas x_N=0 e resolve-se
A_B\,x_B = b
para obter x_B = A_B^{-1}b. Se todas as componentes de x_B forem \ge0, então esse x é chamado de solução viável básica.

Passo 3

No sistema dado
\begin{cases} 2x_{1}+x_{2}+x_{3}=6,\\\ x_{2}+x_{4}=4,\\\ x_{1},x_{2},x_{3},x_{4}\ge0, \end{cases}
podemos escrever
A = \begin{pmatrix}2 & 1 & 1 & 0\\[6pt]0 & 1 & 0 & 1\end{pmatrix},\quad b = \begin{pmatrix}6\\\ 4\end{pmatrix},
com m=2 equações e n=4 variáveis. Devemos examinar todos os subconjuntos de 2 índices em \{1,2,3,4\}.]

Passo 4

Listamos os candidatos B de tamanho 2 e verificamos \det A_B:
  • B=\{1,2\}:
A_B=\begin{pmatrix}2&1\\\ 0&1\end{pmatrix},\quad\det=2\ne0.
  • B=\{1,3\}:
A_B=\begin{pmatrix}2&1\\\ 0&0\end{pmatrix},\quad\det=0\\ (\text{descarta}).
  • B=\{1,4\}:
A_B=\begin{pmatrix}2&0\\\ 0&1\end{pmatrix},\quad\det=2\ne0.
  • B=\{2,3\}:
A_B=\begin{pmatrix}1&1\\\ 1&0\end{pmatrix},\quad\det=-1\ne0.
  • B=\{2,4\}:
A_B=\begin{pmatrix}1&0\\\ 1&1\end{pmatrix},\quad\det=1\ne0.
  • B=\{3,4\}:
A_B=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\quad\det=1\ne0.

Passo 5

Para cada base invertível fazemos x_N=0 e resolvemos A_Bx_B=b, exigindo x_B\ge0:
  • B=\{1,2\}: x_3=x_4=0,
2x_1+x_2=6,\quad x_2=4\;\Rightarrow\;x_1=1,\quad x=(1,4,0,0).
  • B=\{1,4\}: x_2=x_3=0,
2x_1=6\;\Rightarrow\;x_1=3,\quad x_4=4,\quad x=(3,0,0,4).
  • B=\{2,3\}: x_1=x_4=0,
x_2+x_3=6,\quad x_2=4\;\Rightarrow\;x_3=2,\quad x=(0,4,2,0).
  • B=\{2,4\}: x_1=x_3=0,
x_2=6,\;x_4=-2\;(<0)\quad\text{não viável}.ãá
  • B=\{3,4\}: x_1=x_2=0,
x_3=6,\;x_4=4,\quad x=(0,0,6,4).

Resposta

(1) Uma solução viável básica é a solução x obtida escolhendo-se m variáveis básicas cujo submatriz A_B seja invertível, definindo x_N=0 e x_B=A_B^{-1}b, com x_B\ge0.
(2) As soluções viáveis básicas do sistema são
(1,4,0,0),\quad (3,0,0,4),\quad (0,4,2,0),\quad (0,0,6,4).

Exercícios relacionados