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.
& min -x1-x2 & st x1+x2 & x1-x2 <= 6 &-x1+x2 <= 4 & x1, x2 & >= 0

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:
-x1 - x2
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:
x1 - x2 + s1 = 6 - x1 + x2 + s2 = 4 x1, x2, s1, s2 >= 0
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.
c|cccc|c & x1 & x2 & s1 & s2 & PBC hline s1 & 1 & -1 & 1 & 0 & 6 s2 & -1 & 1 & 0 & 1 & 4 hline z & -1 & -1 & 0 & 0 & 0
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ô:
z é
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):
c|cccc|c & x1 & x2 & s1 & s2 & PBC hline s1 & 1 & -1 & 1 & 0 & 6 s2 & -1 & 1 & 0 & 1 & 4 hline z & -1 & -1 & 0 & 0 & 0
Agora, eliminamos o $ x_1 $ das outras linhas:
  • Linha $ s_2 $: $ Linha s_2 + Linha s_1 $
x1
  • Linha $ z $: $ Linha z + Linha s_1 $
s2
A tabela fica assim:
Linha s2 + Linha s1

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ô:
z éãá
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:
x2
Multiplicando a linha $ s_1 $ por -1:
c|cccc|c & x1 & x2 & s1 & s2 & PBC hline s1 & 1 & -1 & 1 & 0 & 6 s2 & 0 & 0 & 1 & 1 & 10 hline z & 0 & -2 & 1 & 0 & 6
Atualizando a linha $ s_1 $:
s1
Agora, eliminamos o $ x_2 $ das outras linhas:
  • Linha $ z $: $ Linha z + 2 \times Linha s_1 $
s1: -1 times (1) = -1 s1: -1 times (-1) = 1 s1: -1 times (1) = -1 s1: -1 times (0) = 0 s1: -1 times (6) = -6
A tabela fica assim:
s1

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ô:
z ãá
Então, a linha pivô é $ s_1 $.

Passo 10

Realizamos o pivoteamento novamente. Dividimos a linha pivô pela entrada de $ x_1 $, que é -1:
x1
Atualizando a linha $ s_1 $:
s1: -1-1 = 1 s1: 1-1 = -1 s1: -1-1 = 1 s1: 0-1 = 0 s1: -6-1 = 6
Agora, eliminamos o $ x_1 $ das outras linhas:
  • Linha $ z $: $ Linha z + 2 \times Linha s_1 $
s1
A tabela final fica assim:
s1: 1 -1 1 0 6

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ô:
z ãá
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:
x1 = 6 e x2 = 0
O valor mínimo da função objetivo é:
min (-x1 - x2) = -6 - 0 = -6

Exercícios relacionados