Simplex

Método Simplex
V 1.1, V.Lobo, EN / ISEGI, 2008

Resolução de PL usando o método
Simplex

Método Simplex
„

Algoritmo para resolver problemas de programação linear „

George Dantzig, 1947

„

Muito utilizado
… Facilmente

implementado como programa de computador … Consegue resolver problemas com muitas variáveis
(milhares)
… Produz variáveis auxiliares para análise de sensibilidade
… Convém saber resolver “à mão”, para se compreender o seu funcionamento.

1

Método Simplex
V 1.1, V.Lobo, EN / ISEGI, 2008

Mais um problema de PL
„

Wyndor Glass Co.
…3

oficinas com alguma capacidade sobrante

Oficina nº1 – Trabalhos em Alumínio
„ Oficina nº2 – Carpintaria
„ Oficina nº3 – Montagem final
„

…2

propostas de novos produtos

1 - Portas de vidro com caixilho de alumínio
„ 2 - Janelas grandes com caixilho de madeira
„

… Que

dados é preciso recolher para tomar uma decisão “óptima” ?

Dados do problema
„

Quanta capacidade sobrante existe ?
… Oficina

1 (alumínios)
… Oficina 2 (madeiras)
… Oficina 3 (montagem)
„

4 horas/semana
12 horas/semana
18 horas/semana

Quanto tempo demora o fabrico das peças ?
…1

lote de portas – 1h nos alumínios, 3 na montagem
… 1 lote de janelas – 2h na carpintaria, 2 na montagem
„

Que lucro se consegue com as peças ?
…1

lote de portas – 3.000€
… 1 lote de janelas – 5.000€

2

Método Simplex
V 1.1, V.Lobo, EN / ISEGI, 2008

Formalização
„

Variáveis de decisão
– Nº de lotes de portas
… x2 - Nº de lotes de janelas
… x1

„

Função objectivo:
…Z

„

=3x1+5x2

Restrições
… x 1≤

4
2x2 ≤ 12
… x 1, x 2, x 3 ≥ 0

3x1+2x2 ≤ 18

Resolução gráfica x2 (janelas)

10

5

2
1
0

1

2

5

10 x1 (portas)

3

Método Simplex
V 1.1, V.Lobo, EN / ISEGI, 2008

Alguns pontos a considerar
„

A solução (caso exista) estará sempre na intercepção de duas restrições
… Basta

„

procurar uma solução nas intercepções

Para irmos de uma intercepção para outra, basta seguirmos uma das restrições
… Devemos

seguir aquela que provoque maior variação no valor da função