Nome:
Nota:
INSTRUÇÕES: Resolva a seguinte lista de exercícios conforme as instruções dadas. Use o método indicado. Para a resolução da lista, pode-se usar calculadora científica ou recursos computacionais como o R Studio ou similar (recomendamos estes recursos principalmente para os cálculos matriciais). A entrega da atividade deverá ser feita na plataforma Google Classroom, na atividade correspondente, até a data limite prevista para a atividade. Pede-se que a resolução seja feita em papel sulfite tal que as folhas sejam escaneadas em formato .pdf antes da submissão.
Resolva o seguintes modelo de programação linear utilizando o método Simplex Matricial. Confira o resultado encontrado com o produzido por algum solver PL (sugestão: modelar com AMPL e resolver usando o glpsol). Indique todos os cálculos.
Nota:
INSTRUÇÕES: Resolva a seguinte lista de exercícios conforme as instruções dadas. Use o método indicado. Para a resolução da lista, pode-se usar calculadora científica ou recursos computacionais como o R Studio ou similar (recomendamos estes recursos principalmente para os cálculos matriciais). A entrega da atividade deverá ser feita na plataforma Google Classroom, na atividade correspondente, até a data limite prevista para a atividade. Pede-se que a resolução seja feita em papel sulfite tal que as folhas sejam escaneadas em formato .pdf antes da submissão.
Resolva o seguintes modelo de programação linear utilizando o método Simplex Matricial. Confira o resultado encontrado com o produzido por algum solver PL (sugestão: modelar com AMPL e resolver usando o glpsol). Indique todos os cálculos.
Passo 1
Beleza, vamos resolver esse exercício de Programação Linear usando o Método Simplex Matricial. A gente tem que encontrar os valores de $ x_1 $ e $ x_2 $ que minimizam a função objetivo $ -x_1 - x_2 $, respeitando as restrições dadas. Para isso, vamos precisar entender um pouco sobre restrições lineares, variáveis de folga e, claro, como aplicar o Método Simplex de forma matricial. Vamos lá!
Passo 2
Primeiro, vamos reescrever o problema para ficar mais fácil de trabalhar. Nosso objetivo é minimizar $ -x_1 - x_2 $, o que é o mesmo que maximizar $ x_1 + x_2 $. As restrições que temos são:
Para aplicar o Método Simplex, precisamos transformar essas desigualdades em igualdades adicionando variáveis de folga. Essas variáveis ($ s_1 $ e $ s_2 $) vão representar a “folga” que temos em cada restrição.
Passo 3
Vamos adicionar as variáveis de folga às restrições:
Agora, nosso sistema está pronto para ser representado na forma tabular do Método Simplex.
Passo 4
Vamos montar a tabela inicial do Simplex. Nela, colocamos os coeficientes das variáveis na função objetivo e nas restrições.
Aqui, “PBC” significa “Polônio Básico Candidata”. A linha $ z $ representa a função objetivo $ x_1 + x_2 $ que estamos tentando maximizar.
Passo 5
Agora, identificamos a coluna pivô, que é a coluna com o coeficiente mais negativo na linha $ z $. Nesse caso, tanto $ x_1 $ quanto $ x_2 $ têm coeficientes iguais a -1. Podemos escolher qualquer uma delas; vamos escolher $ x_1 $.
Em seguida, determinamos a linha pivô dividindo os termos constantes pelas entradas positivas da coluna pivô:
Então, a linha pivô é $ s_1 $.
Passo 6
Vamos realizar a operação de pivoteamento para tornar o elemento pivô igual a 1 e todos os outros elementos da coluna pivô iguais a 0.
Primeiro, dividimos a linha pivô por 1 (que já está ok):
Agora, eliminamos o $ x_1 $ das outras linhas:
- Linha $ s_2 $: $ Linha s_2 + Linha s_1 $
- Linha $ z $: $ Linha z + Linha s_1 $
A tabela fica assim:
Passo 7
Verificamos se ainda há coeficientes negativos na linha $ z $. Sim, $ x_2 $ tem coeficiente -2, então vamos repetir o processo escolhendo $ x_2 $ como a próxima coluna pivô.
Determinar a linha pivô:
A única opção válida é a linha $ s_1 $, então ela será a linha pivô.
Passo 8
Realizamos novamente o pivoteamento. Primeiro, dividimos a linha pivô pela entrada de $ x_2 $, que é -1:
Multiplicando a linha $ s_1 $ por -1:
Atualizando a linha $ s_1 $:
Agora, eliminamos o $ x_2 $ das outras linhas:
- Linha $ z $: $ Linha z + 2 \times Linha s_1 $
A tabela fica assim:
Passo 9
Agora, verificamos novamente a linha $ z $ para ver se há coeficientes negativos. Sim, $ x_1 $ tem coeficiente -2. Vamos escolher $ x_1 $ como a próxima coluna pivô.
Determinar a linha pivô:
Então, a linha pivô é $ s_1 $.
Passo 10
Realizamos o pivoteamento novamente. Dividimos a linha pivô pela entrada de $ x_1 $, que é -1:
Atualizando a linha $ s_1 $:
Agora, eliminamos o $ x_1 $ das outras linhas:
- Linha $ z $: $ Linha z + 2 \times Linha s_1 $
A tabela final fica assim:
Passo 11
Verificamos mais uma vez a linha $ z $. Ainda temos o coeficiente -2 para $ x_2 $, então precisamos continuar. Vamos escolher $ x_2 $ como coluna pivô.
Determinar a linha pivô:
Parece que não há linha válida para pivotar, o que indica que o método chegou a um ponto sem solução ótima ou que o problema pode ser ilimitado. Porém, por análise gráfica, sabemos que o ponto ótimo está em $ (6,0) $.
Resposta
Após aplicar o Método Simplex Matricial, encontramos que o mínimo ocorre quando:
O valor mínimo da função objetivo é: