Olá,
tentando fazer as provas antigas eu fiquei com duvidas sobre os conceitos de restrição ativa e solução basica,
eu nao sei como a partir das restrições do poliedro eu identifico quais são as restrições ativas e como eu encontro as soluções basicas, inviaveis e degeneradas..
os exercicios que eu fiquei em duvida foram o 1 das provas C e D.
Olá Bruno,
Estou certo de que degeneração é um conceito que ainda não vimos e não cairá nesta P1. Como o professor nos avisou, algumas das provas antigas eram de anos que tinham apenas 2 provas no semestre, e portanto a quantidade de matéria abordada na P1 era maior.
Ainda estou estudando então posso estar errado, mas acredito que para identificar uma restrição ativa em um ponto x basta verificar se essa restrição satisfaz a igualdade em x, ou seja, se vale que ax =bi. Isto está redigido de forma muito melhor (mais formal e correta) nas notas de aula. Graficamente ela pode ser identificada como o ponto que na "fronteira" do poliedro. Por exemplo, no poliedro x1 +x2+x3 = 1, xi >= 0 (em R3), no ponto (0,0,0) as restrições x1 >=1, x2>=0 e x3 >= 0 são ativas. Já no ponto (1, 0, 0) x1 deixa de ser ativa pois, apesar da restrição ser "satisfeita" (x1 >= 0 é verdade para x1 = 1), ela não satisfaz x1 = 0 (a igualdade).
"no poliedro x1 +x2+x3 = 1, xi >= 0 (em R3), no ponto (0,0,0) as restrições x1 >=1, x2>=0 e x3 >= 0 são ativas. Já no ponto (1, 0, 0) x1 deixa de ser ativa pois, apesar da restrição ser "satisfeita" (x1 >= 0 é verdade para x1 = 1), ela não satisfaz x1 = 0 (a igualdade)."
Não entendi pq x1 >= 1 eh ativa em ( 0, 0, 0 ), se eu entendi oq vc falou, pra ela ser ativa deveria ser x1 = 1
Acredito que ele quis dizer "x1>=0", e no ponto (1, 0, 0) apenas as restrições x2>=0 e x3>=0 são ativas, a x1>=0 não é pois (conforme explicado) não satisfaz a igualdade.
É, desculpe, escrevi errado. Quis dizer que x1 >= 0 era ativa em (0,0,0).
Olá, Bruno, Daniel, Felipe e demais alunos!
Acho que vocẽs já resolveram tudo sozinhos: o que o Daniel escreveu estava certinho, a menos do lapso que ele corrigiu depois. O mais importante, retomando o formato da pergunta inicial, é entender que não existem restrições ativas ou inativas em si mesmas; este conceito da restrição estar ativa ou inativa sempre se refere a um ponto em particular, e a mesma restrição pode ser ativa em um ponto x e inativa em outro ponto y.
Marcelo
Um P.S. em relação à minha mensagem anterior: os exercícios 1 da prova C e 1 da prova D são úteis pra gente, mesmo que não tenhamos ainda falado em degenerescência, basta ignorar este aspecto e resolver o resto. Sobre as soluções básicas inviáveis, o poliedro do Daniel fornece um bom exemplo: se P={x1+x2+x3=1, x≥0} então x=(0,0,0)' é uma solução básica inviável (pra verificar, basta considerar as 3 restrições de sinal, que são l.i., e o fato de que x1+x2+x3≠1 mostra a inviabilidade).
Marcelo
e quanto ao ponto (1,0,0)? Seria uma solução básica tbm? Já que deixa 3 restrições ativas: x1+x2+x3=1, x2≥0 e x3≥0...
Sim. A restrição de igualdade x1 +x2 +x3 =1 é satisfeita e, como estamos lidando com R3, as 3 restrições ativas (evidentemente LI) definem o ponto como solução básica (definição 2.9 capitulo 2 das notas de aula).
E mais, é uma solução básica viável pois ela satisfaz também as restrições inativas no ponto (não em igualdade, é claro).
Já o ponto (0,0,0) não seria uma solução básica pois, apesar de satisfazer as três restrições ativas no ponto, ela não satisfaz a restrição de igualdade do PL x1 +x2 +x3 =1.
Acho que, nesse exemplo não há uma solução básica inviável... Não vejo como termos um ponto que satisfaz a restrição de igualdade e mais duas outras restrições ativamente, mas não satisfaz a restrição inativa. Ele teria de pertencer ao plano x1+x2+x3=1, ser negativo em apenas um dos eixos xi, e satisfazer em igualdade os demais (por exempo negativo em x1 e x2 =x3 =0). O que é impossivel já que 0+0+negativo != 1 (restrição de igualdade).
Me parece que precisariamos de mais restrições redundantes (LD) nesse caso para gerarmos tais soluções básicas inviáveis.
Mayara: sim, o ponto (1,0,0) é solução básica também, mas não apenas porque tem 3 restrições ativas, mas sim porque tem 3 restrições ativas *e linearmente independentes*. Ou seja, não apenas valem as 3 igualdades x1+x2+x3=0, x2=0 e x3=0, mas também os vetores de coeficientes (1,1,1), (0,1,0) e (0,0,1) associados a estas restrições são l.i., o que é fácil de verificar *mas precisa ser dito*.
Daniel: excelente observação! De fato eu me confundi no exemplo que quis dar! Como a definição de solução básica exige que as restrições de igualdade sejam verificadas, no poliedro P={x | x1+x2+x3=1, x≥0} as únicas soluções básicas são (1,0,0), (0,1,0) e (0,0,1), todas viáveis! (0,0,0) possui 3 restrições ativas e l.i. (as restrições de sinal), mas não é solução básica pois não satisfaz a restrição de igualdade... isso é uma tecnicalidade daquela definição, e a justificativa para esta tecnicalidade é algorítmica, mas vamos guardar essa discussão para depois.
Para consertar o meu exemplo, podíamos considerar o mesmo poliedro através da representação Q={x | x1+x2+x3≥1, x1+x2+x3≤1, x≥0}. É fácil ver que P=Q, que é o triângulo associado ao casco convexo dos pontos (1,0,0), (0,1,0) e (0,0,1). Este poliedro está na forma geral (não há restrições de igualdade), e portanto uma solução básica precisa apenas possuir 3 restrições ativas e l.i. O ponto (0,0,0) possui as 3 restrições de sinal ativas e l.i. e portanto é solução básica, e é inviável porque não satisfaz a restrição x1+x2+x3≥1 (embora satisfaça x1+x2+x3≤1). Os pontos (1,0,0), (0,1,0) e (0,0,1), que já eram soluções básicas viáveis na representação anterior, permanecem sendo agora, e todos possuem 4 restrições ativas (x1+x2+x3≥1, x1+x2+x3≤1 e mais duas restrições de sinal). Observem que "o conjunto das restrições ativas" nestes pontos não pode ser l.i. (estamos em R3!), mas cada um destes conjuntos de 4 restrições possui algum subconjunto de 3 restrições que são ao mesmo tempo ativas e l.i. (cada ponto terá exatamente dois subconjuntos com esta propriedade, um escolhendo a desigualdade x1+x2+x3≥1 e as duas restrições de sinal, e outro subconjunto escolhendo x1+x2+x3≤1 e as duas restrições de sinal).
Este exemplo ilustra um fato importante: por exigir a verificação das restrições de igualdade, a definição de solução básica é *dependente* da representação (afinal P=Q, mas (0,0,0) é solução básica em Q e não em P). Como veremos depois da prova, essa dependência só afeta as soluções básicas inviáveis, pois o conceito de solução básica viável é equivalente ao de vértice e de ponto extremo, e estes dois últimos não dependem da representação adotada, mas apenas da geometria do conjunto.
Marcelo
Em resposta à Marcelo Queiroz
Re: Restrição ativa e solução basica
Boa tarde prof.
Então estou com dúvida no exercício 1 C. Como eu indentifico as soluções básicas inviáveis? Eu li o forum, mas ainda não está muito claro..
Em resposta à Felipe Gilvan Silva de Oliveira
Re: Restrição ativa e solução basica
POderia dizer que as soluções básicas viáveis são os vertices e que as não viáveis estão dentro do poliedro?
Em resposta à Felipe Gilvan Silva de Oliveira
Re: Restrição ativa e solução basica
por Brielen Madureira -
Oi, Felipe!
Todos os pontos dentro do poliedro são viáveis, mas nem todos são chamados solução básica. Para ser solução básica, é preciso atender à definição da página 18 da apostila: todas as restrições de igualdade satisfeitas e, entre as retrições ativas tem que haver n linearmente independentes. Solução básica viável satisfaz todas as retrições (inclusive x_i >=0, às vezes há um ponto que atende todas as igualdades e não atende essa...).
Na figura da página 19 dá para ver bem. Os pontos A e B, embora satisfaçam duas igualdades, portanto tem n=2 restrições li, não satisfazem outras restrições (veja que estão fora do poliedro), isto é, são soluções básicas mas inviáveis.
Olá, Felipe!
A Brielen já respondeu a sua pergunta, mas deixa eu complementar só um detalhe. Aparentemente você estava preocupado com a identificação de soluções básicas inviáveis; é importante ressaltar que a definição de solução básica e a definição de viabilidade são totalmente independentes: uma solução básica é um ponto x do R^n que satisfaz as restrições de igualdade e que possui n restrições l.i. dentre as restrições ativas em x; já viabilidade é sinônimo de respeitar todas as restrições, sejam elas de igualdade ou desigualdade (informalmente é o que você chamou de "estar dentro" do poliedro).
Então ao invés de pensar "vou identificar as soluções básicas inviáveis" e procurar condições que as caracterizem, talvez fosse mais didático pensar "vou identificar as soluções básicas, e depois vou verificar para cada uma delas se é viável ou não".
Graficamente, você vai verificar que as soluções básicas em R^2 correspondem a interseções de duas retas (fronteiras de restrições do poliedro) não paralelas, em R^3 são interseções de três planos cuja interseção é somente aquele ponto, etc. Estas "interseções" podem ser atravessadas por mais do que N hiperplanos, sem prejudicar a definição de solução básica. Se além disso este ponto-interseção estiver "dentro" do poliedro, será uma solução básica viável, do contrário (desde que respeite todas as restrições de igualdade) será uma solução básica inviável.
Quanto à relação entre solução básica viável e vértice, isso é verdade, mas ainda não vimos essa demonstração, é matéria para depois da prova.
Marcelo