Aula 04 - Gabarito

Prévia do material em texto

Aula 4 – Método Simplex (Fundamentação Teórica) – Gabarito 
Exercício 4.1 (Solução) 
O modelo associado ao Exercício 2.1 já na forma padrão é: 
𝑀𝑎𝑥 𝑧 = 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 
O modelo na forma padrão possui 𝑛 = 5 variáveis e 𝑚 = 3 restrições. Assim, o número de 
soluções básicas é 
(
5
5 − 3
) =
5!
3! 2!
= 10 
Cada uma destas 10 soluções pode ser obtida zerando-se 5-3=2 variáveis e resolvendo o sistema 
resultante. 
Nº Variáveis 
Não 
básicas 
(zeradas) 
Variáveis 
básicas 
Solução do sistema resultante Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) 
Solução 
básica 
viável ou 
inviável? 
Valor da 
função 
objetivo 𝑧 
1 𝑥1, 𝑥2 𝑅1, 𝑅2, 𝑅3 𝑅1 = 3, 𝑅2 = 10, 𝑅3 = 14 (0, 0, 3, 10, 14) Viável 𝑧 = 0 
2 𝑥1, 𝑅1 𝑥2, 𝑅2, 𝑅3 𝑥2 = 3, 𝑅2 = 7, 𝑅3 = 8 (0, 3, 0, 7, 8) Viável 𝑧 = 3 
3 𝑥1, 𝑅2 𝑥2, 𝑅1, 𝑅2 𝑥2 = 10, 𝑅1 = −7, 𝑅3 = −6 (0, 10, -7, 0, -6) Inviável - 
4 𝑥1, 𝑅3 𝑥2, 𝑅1, 𝑅2 𝑥2 = 7, 𝑅2 = 3, 𝑅1 = −4 (0, 7, -4, 3, 0) Inviável - 
5 𝑥2, 𝑅1 𝑥1, 𝑅2, 𝑅3 
𝑥1 = −
3
2
, 𝑅2 = 10, 𝑅3 =
37
2
 (-
3
2
, 0, 0, 10, 
37
2
) Inviável - 
6 𝑥2, 𝑅2 𝑥1, 𝑅1, 𝑅3 Inconsistente - Inviável - 
7 𝑥2, 𝑅3 𝑥1, 𝑅1, 𝑅2 
𝑥1 =
14
3
, 𝑅1 =
37
3
, 𝑅2 = 10 (
14
3
, 0, 
37
3
, 10, 0) Viável 𝑧 = 14 
8 𝑅1, 𝑅2 𝑥1, 𝑥2, 𝑅3 
𝑥1 =
7
2
, 𝑥2 = 10, 𝑅3 = −
33
2
 (
7
2
, 10, 0,0, −
33
2
) Inviável - 
9 𝑅1, 𝑅3 𝑥1, 𝑥2, 𝑅2 
𝑥1 =
8
7
, 𝑥2 =
37
7
, 𝑅2 =
53
7
 (
8
7
,
37
7
, 0,
53
7
, 0) 
Viável 
𝑧 =
61
7
 
10 𝑅2, 𝑅3 𝑥1, 𝑥2, 𝑅1 𝑥1 = −2, 𝑥2 = 10, 𝑅1 = −1 (-2, 10, -1, 0, 0) Inviável - 
 
Uma vez que o problema é de maximização, a solução ótima é a solução básica viável com maior 
valor na função objetivo 𝑧. Assim, a solução ótima é a de número 7, com valores 𝑥1 = 14, 𝑥2 =
0, 𝑅1 =
37
7
, 𝑅2 = 10, 𝑅3 = 0 e que gera um valor 𝑧 = 14. 
No Exercício 2.1, desenhamos a região de soluções viáveis do modelo: 
 
Reparemos que cada solução básica que não gerou um sistema inconsistente está associada a um 
ponto extremo (interseção de restrições) e, quando a solução básica é viável, o ponto extremo 
associado também é viável. 
Nº Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) 
Solução básica viável 
ou inviável? 
Ponto extremo 
associado 
(𝑥1, 𝑥2) 
1 (0, 0, 3, 10, 14) Viável 𝐴 = (0,0) 
2 (0, 3, 0, 7, 8) Viável 𝐷 = (0,3) 
3 (0, 10, -7, 0, -6) Inviável (0,10) 
4 (0, 7, -4, 3, 0) Inviável (0,7) 
5 (-
3
2
, 0, 0, 10, 
37
2
) Inviável (-
3
2
, 0) 
6 Sistema inconsistente Inviável - 
7 (
14
3
, 0, 
37
3
, 10, 0) Viável 
𝐵 = (
14
3
, 0) 
8 (
7
2
, 10, 0,0, −
33
2
) Inviável 
(
7
2
, 10) 
9 
(
8
7
,
37
7
, 0,
53
7
, 0) 
Viável 
𝐶 = (
8
7
,
37
7
) 
10 (-2, 10, -1, 0, 0) Inviável (−2,10) 
 
O modelo associado ao Exercício 2.2 já na forma padrão é: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 
s.a. 𝑥1 + 𝑥2 = 9 
−2𝑥1 + 𝑥2 + 𝑅1 = 6 
−𝑥1 + 𝑥2 − 𝑅2 = 2 
𝑥1 , 𝑥2, 𝑅1, 𝑅2 ≥ 0 
O modelo na forma padrão possui 𝑛 = 4 variáveis e 𝑚 = 3 restrições. Assim, o número de 
soluções básicas é 
(
4
4 − 3
) =
4!
3! 1!
= 4 
Cada uma destas 10 soluções pode ser obtida zerando-se 4-3=1 variável e resolvendo o sistema 
resultante. 
Nº Variáveis 
Não 
básicas 
(zeradas) 
Variáveis 
básicas 
Solução do sistema resultante Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) 
Solução 
básica 
viável ou 
inviável? 
Valor da 
função 
objetivo 𝑧 
1 𝑥1 𝑥2, 𝑅1, 𝑅2 𝑥2 = 9, 𝑅1 = −3, 𝑅2 = 7 (0, 9, -3, 7) Inviável - 
2 𝑥2 𝑥1, 𝑅1, 𝑅2 𝑥1 = 9, 𝑅1 = 24, 𝑅2 = −11 (9, 0, 24, -11) Inviável - 
3 𝑅1 𝑥1, 𝑥2, 𝑅2 𝑥1 = 1, 𝑥2 = 8, 𝑅2 = 5 (1, 8, 0, 5) Viável 𝑧 = 26 
4 𝑅2 𝑥1, 𝑥2, 𝑅1 
𝑥1 =
7
2
, 𝑥2 =
11
2
, 𝑅1 =
15
2
 (
7
2
,
11
2
,
15
2
, 0) 
Viável 𝑧 = 23,5 
 
Uma vez que o problema é de minimização, a solução ótima é a solução básica viável com menor 
valor na função objetivo 𝑧. Assim, a solução ótima é a de número 4, com valores 𝑥1 =
7
2
, 𝑥2 =
11
2
, 𝑅1 =
15
2
, 𝑅2 = 0 e que gera um valor 𝑧 = 23,5.