UNIVERSIDADE DO ESTADO DE MATO GROSSO – UNEMAT

UNIVERSIDADE DO ESTADO DE MATO GROSSO – UNEMAT

CAMPUS BARRA DO BUGRES

Método Simplex

Jarcio Alves de Sousa

2019

Ementa        

• O que é Pesquisa Operacional;
• Problema de Programação Linear;
• O algoritmo Simplex.

---

1. PESQUISA OPERACIONAL

Para Shamblin e Stevens Jr. (1979), Pesquisa Operacional (PO) é um método científico de tomada de decisões nas mais diversas áreas de atuação humana através de estudos, desenvolvimentos e aplicação de métodos analíticos. Seu início se dá em descrever um sistema por intermédio de um modelo, posteriormente ocupa-se com este para alcançar a melhor maneira de operar o sistema.

---

1. PROBLEMA DE PROGRAMAÇÃO LINEAR (PPL)

Segundo Shamblin e Stevens Jr (1979), a programação linear é um meio matemático de designar um montante fixo de recursos que satisfaça certa demanda de tal modo que alguma função-objetivo seja otimizada e ainda se satisfaça a outras condições definidas.

O termo PPL se relaciona ao planejamento de recursos escassos visando atender as condições operacionais em estudo, onde são representadas por funções e equações lineares. A aplicação PPL em apoio à tomada de decisão ocorre na condição que se decide para atingir um objetivo, onde este, por sua vez, é resultante da alocação ótima dos recursos. É por isso que a PPL é caracterizada como uma técnica de otimização.

Para Lachtermacer (2004), um PPL está em sua forma padrão se tivermos uma Maximização da função-objetivo e se todas as restrições forem do tipo menor ou igual, bem como os termos constantes e variáveis de decisão não-negativos.

A construção de um modelo de PPL segue três passos básicos, segundo Montevechi (2006,):

I. Identificação das variáveis desconhecidas a serem determinadas, (denominadas como variáveis de decisão) representadas através de símbolos algébricos (x e y ou  e ). [pic 1][pic 2]

II. Deve-se listar todas as restrições do problema e expressa-las em forma de equações (=) ou inequações (≤) lineares em termos das variáveis de decisão definidas no passo I.

III. Identificação do objetivo ou critério de otimização do problema, devendo ser representando como uma função linear das variáveis de decisão. Podendo ser o objetivo do tipo maximizar ou minimizar.

---

Exemplo – O problema do mix de produção.

A empresa Dalai-Lama deseja planejar a produção de incensos. Os produtos requerem dois tipos de recursos: mão-de-obra e materiais. A empresa fabrica três tipos do produto, cada qual com diferentes necessidades de mão de-obra e materiais.

Vejamos a tabela abaixo:

	Modelo
	A	B
Mão-de-obra (h/unidade)	2	4
Materiais (g/unidade)	6	1
Lucro (unidade)	3	5

A disponibilidade de materiais é de 200g/dia.

A mão-de-obra disponível é de 100h.

Determinar quanto deve ser produzido de cada tipo de incenso, tal que o lucro total seja maximizado.

Seguindo os 3 passos temos:

1. Identificação das variáveis:

: Produção diária modelo A[pic 3]

: Produção diária modelo B[pic 4]

1. Listagem de todas as restrições do problema e expressa-las em forma de equações (=) ou inequações (≤) lineares:

Modelo A:

• Tempo: 2h/unidade;
• Quantidade: ;[pic 5]

= 2 [pic 6]

Modelo B:

• Tempo: 4h/unidade;
• Quantidade: ;[pic 7]

= 4[pic 8]

O tempo total utilizado para a produção dos 3 modelos é representada como:

 + 4 [pic 9][pic 10]

Como o tempo disponível é de 200h, o tempo total de produção não poderá ultrapassá-lo, ficando a restrição da mão de obra da seguinte forma:

 + 4  ≤ 100[pic 11][pic 12]

Para a restrição dos materiais, temos:

 + 1  ≤  200[pic 13][pic 14]

1. Supondo que o objetivo é maximizar o lucro total e que toda produção será destinada a consumidores finais, temos que o lucro total resultante será:

Z = 3 + 5 [pic 15][pic 16]

Sujeito às restrições:

 + 4 ≤ 100[pic 17][pic 18]

 + 1 ≤ 200[pic 19][pic 20]

---

1. Método Simplex.

Para FOGLIATTO (2011), o método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de um modelo de PPL, sendo o maior ou menor valor possível, finalizando quando não é possível continuar melhorando este valor, para que todas as restrições sejam satisfeitas.

O Método Simplex compreenderá, portanto, os seguintes passos:

1. Achar uma solução factível básica inicial;
2. Verificar se a solução atual é ótima. Se for, pare. Caso contrário, siga para o passo iii).
3. Determinar a variável não básica que deve entrar na base;
4. Determinar a variável básica que deve sair da base;
5. Atualizar o sistema à fim de determinar a nova solução factível básica, e voltar ao passo ii).

Resolvendo a PPL exemplo: O problema do mix de produção.

Determinar quanto deve ser produzido de cada tipo de incenso, tal que o lucro total seja maximizado.