Aula 09 - Gabarito

Prévia do material em texto

Aula 9 – Gabarito 
Nos exercícios da Aula 09, foi pedido que se aplicasse o algoritmo simplex nos modelos 
dos exercícios da Aula 02. 
Modelo do Exercício 2.1 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a. −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
Solução: Modelo com as variáveis de folga: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a. −2𝑥1 + 𝑥2 + 𝑅1 = 3 
𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Para este modelo, não existe a necessidade de criação de variáveis artificiais. Portanto, o 
mesmo pode ser resolvido em uma única fase: 
 
Como o problema é de maximização e não existem variáveis não básicas com coeficientes 
positivos na linha 𝑧, este dicionário representa a solução ótima, que é (𝑥1, 𝑥2) = (
14
3
, 0) 
gerando um valor ótimo 𝑧 = 14. 
Modelo do Exercício 2.2 
 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 
s.a. 𝑥1 + 𝑥2 = 9 
−2𝑥1 + 𝑥2 ≤ 6 
−𝑥1 + 𝑥2 ≥ 2 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
Solução 
Modelo da Fase I: 
𝑀𝑖𝑛 𝑧′ = 𝐴1 + 𝐴2 
s.a. 𝑥1 + 𝑥2 + 𝐴1 = 9 
−2𝑥1 + 𝑥2 + 𝑅1 = 6 
−𝑥1 + 𝑥2 − 𝑅2 + 𝐴2 = 2 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝐴1, 𝐴2 ≥ 0 
Dicionários da Fase I: 
 
Na Fase II, excluímos as variáveis artificiais e voltamos para a função objetivo original: 
 
Como o problema é de minimização e não existem variáveis não básicas com coeficientes 
negativos na linha 𝑧, este dicionário representa a solução ótima, que é (𝑥1, 𝑥2) = (
7
2
,
11
2
) 
gerando um valor ótimo 𝑧 =
47
2
. 
Modelo do Exercício 2.3 
 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a. −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
𝑥1 , 𝑥2 ≥ 0 
 
Solução: Modelo com as variáveis de folga: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a. −2𝑥1 + 𝑥2 + 𝑅1 = 3 
𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Para este modelo, não existe a necessidade de criação de variáveis artificiais. Portanto, o 
mesmo pode ser resolvido em uma única fase: 
 
Note que 𝑥1 é candidata a entrar na base e em nenhuma linha de restrição no dicionário 
aparece com coeficientes negativos. Assim, o modelo é ilimitado uma vez que 𝑥1 pode 
ser aumentado infinitamente sem deixar o problema inviável. 
 
 
Modelo do Exercício 2.4 
𝑀𝑎𝑥 𝑧 = 9𝑥1 + 6𝑥2 
s.a. −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
Solução: Modelo com as variáveis de folga: 
𝑀𝑎𝑥 𝑧 = 9𝑥1 + 6𝑥2 
s.a. −2𝑥1 + 𝑥2 + 𝑅1 = 3 
𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Para este modelo, não existe a necessidade de criação de variáveis artificiais. Portanto, o 
mesmo pode ser resolvido em uma única fase: 
 
Como o problema é de maximização e não existem variáveis não básicas com coeficientes 
positivos na linha 𝑧, este dicionário representa uma solução ótima, que é (𝑥1, 𝑥2) =
(
14
3
, 0) gerando um valor ótimo 𝑧 = 42. 
Por outro lado, 𝑥2 é variável não básica e possui coeficiente nulo na linha 𝑧. Isto indica 
que se ela fosse colocada na base, o custo ótimo 𝑧 = 42 não se alteraria. Em outras 
palavras, o modelo possui múltiplas soluções ótimas. Experimente como exercício incluir 
𝑥2 na base e comprovar tal fato.