(1) Encontre todas as soluções viáveis básicas do sistema.
(2) Em um sistem , onde e . 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
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).)
Base :
Se é básica então e . Na primeira equação sobram :
3. Base :
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.