Questão 15

Considere o sistema
x1+x2 & <= 4 x2 & <= 2 x1, x2 & >= 0
(1) Encontre todas as soluções viáveis básicas do sistema.
(2) Em um sistem A x=b, x >= 0, onde A in R^m times n, b in R^m e rank(A, b)= rank(A)=m. Qual é o maio número de soluções viáveis básicas para o sistema?

Passo 1

O enunciado nos dá o sistema de desigualdades
x1+x2<=4, x2<=2, x1,x2>=0,
e pede (1) todas as soluções viáveis básicas (BFS) e (2) em geral para Ax=b,;x>=0 com rank(A)=m, qual o maior número de BFS. Para achar as BFS do item (1) vamos passar o sistema à forma padrão com variáveis de folga.

Passo 2

Introduzimos as variáveis de folga
Agora temos variáveis . Cada BFS corresponde a escolher um conjunto de 2 variáveis básicas, zerar as não-básicas e resolver as igualdades.

Passo 3

Precisamos escolher em cada equação uma variável básica. Na segunda equação só podem ser básicas [\implies(x_{1},x_{2},s_{1},s_{2})=(2,2,0,0).)
  1. Base :
  • Se é básica então e . Na primeira equação sobram :
    3. Base :
    1. Base :

Passo 4

Das 4 bases válidas obtivemos exatamente 4 pontos extremos (BFS). Em termos de (x1,x2) são:
(2,2),(0,2),(4,0),(0,0)

Passo 5

Para o item (2), em geral um sistema Ax=b,;x>=0 com AinR^mtimes n e rank(A)=m admite no máximo tantas BFS quanto escolhas de m variáveis básicas dentre n. Logo, o número máximo de soluções viáveis básicas é
binomnm

Resposta

As soluções viáveis básicas (contando (x1,x2,s1,s2)) são
(2,2,0,0),;(0,2,2,0),;(4,0,0,2),;(0,0,4,2),
isto é, em (x1,x2): (2,2),(0,2),(4,0),(0,0).
O maior número de BFS em um sistema Ax=b,;x>=0 com rank(A)=m é binomnm.

Exercícios relacionados