BACHARELADO EM
PESQUISA OPERACIONAL CIÊNCIAS DA COMPUTAÇÃO
[Link]
ALGORITMO SIMPLEX
UNIVERSIDADE FEDERAL DE JATAÍ
Prof. Dr. Thiago Borges de Oliveira
[Link]
thborges@[Link]
MÉTODO SIMPLEX
É um algoritmo para solução de modelos de Programação Linear (PL)
O Simplex evita a exploração exaustiva de soluções básicas, assumindo alguns
princípios:
1
MÉTODO SIMPLEX
É um algoritmo para solução de modelos de Programação Linear (PL)
O Simplex evita a exploração exaustiva de soluções básicas, assumindo alguns
princípios:
• Só pesquisa por soluções básicas compatíveis (observando as restrições);
1
MÉTODO SIMPLEX
É um algoritmo para solução de modelos de Programação Linear (PL)
O Simplex evita a exploração exaustiva de soluções básicas, assumindo alguns
princípios:
• Só pesquisa por soluções básicas compatíveis (observando as restrições);
• Melhora a cada etapa o valor da função objetivo, tentando aumentar
(maximização) ou diminuir (minimização) o valor da função objetivo;
1
MÉTODO SIMPLEX
É um algoritmo para solução de modelos de Programação Linear (PL)
O Simplex evita a exploração exaustiva de soluções básicas, assumindo alguns
princípios:
• Só pesquisa por soluções básicas compatíveis (observando as restrições);
• Melhora a cada etapa o valor da função objetivo, tentando aumentar
(maximização) ou diminuir (minimização) o valor da função objetivo;
• Utiliza regras de parada que testam as situações:
• A solução ótima foi encontrada;
• A solução ótima é ilimitada;
• Existe uma solução viável;
1
PROBLEMA NA FORMA PADRÃO
O Simplex só consegue resolver um problema se ele estiver em uma forma
padrão, ou seja:
• com a restrição de não negatividade de todas variáveis;
• com os valores da “mão direita” nas restrições não negativos;
• com variáveis de folga/auxiliares.
2
O PROBLEMA DA REDDY MIKKS
A Reddy Mikks produz tintas para interiores e exteriores com base em duas
matérias-primas, M1 e M2. Dados básicos:
Toneladas matéria prima Disponibilidade
T. Exteriores T. Interiores
M1 6 4 24
M2 1 2 6
Lucro p/ ton 5.000 4.000
Uma pesquisa de mercado indica que a demanda diária de tintas para interiores
não pode ultrapassar a de tintas para exteriores por mais de 1 tonelada. Além
disso, a demanda máxima diária de tinta para interiores é 2t.
A Reddy Mikks quer determinar o mix ótimo de tintas a produzir para maximizar o
lucro. 3
FORMULAÇÃO DO PROBLEMA
Maximizar: 5𝑥1 + 4𝑥2
Sujeito a: 6𝑥1 + 4𝑥2 ≤ 24
𝑥1 + 2𝑥2 ≤ 6
−𝑥1 + 𝑥2 ≤ 1
𝑥2 ≤ 2
𝑥1 ≥ 0
𝑥2 ≥ 0
4
COLOCANDO NA FORMA PADRÃO
Para usar o algoritmo Simplex, deve-se transformar as restrições ≤ em equações,
usando uma variável de folga:
6𝑥1 + 4𝑥2 ≤ 24 ⇒ 6𝑥1 + 4𝑥2 +𝑠1 =24
E adicionar a restrição: 𝑠1 >= 0
Explicação: 𝑠1 assumirá o valor que falta para chegar em 24 na inequação.
5
MODELO TRANSFORMADO COM VARIÁVEIS DE FOLGA
Maximizar 𝑧: 5𝑥1 + 4𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4
Sujeito a: 6𝑥1 + 4𝑥2 + 𝑠1 = 24
𝑥1 + 2𝑥2 + 𝑠2 = 6
−𝑥1 + 𝑥2 + 𝑠3 = 1
𝑥2 + 𝑠4 = 2
𝑥1 ≥ 0
𝑥2 ≥ 0
𝑠1 , 𝑠 2 , 𝑠 3 , 𝑠 4 ≥ 0
6
IDENTIFICANDO A SOLUÇÃO INICIAL
Neste modelo, com todas as restrições no formato ≤, uma solução básica inicial
aparece, na forma de matriz identidade, observando o valor das variáveis de folga.
𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 =
6 4 1 0 0 0 24
1 2 0 1 0 0 6
-1 1 0 0 1 0 1
0 1 0 0 0 1 2
Variáveis básicas: 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4
Variáveis não-básicas (iguais a zero): 𝑥1 , 𝑥2
7
COLOCANDO NO TABLEAUX
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧
𝑠1
𝑠2
𝑠3
𝑠4
8
COLOCANDO NO TABLEAUX
Função z é alterada para o formato de equação, igualada a zero:
𝑧 ∶ 5𝑥1 + 4𝑥2 ⇒ 𝑧 − 5𝑥1 − 4𝑥2 = 0
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24 linha 𝑠1
𝑠2 0 1 2 0 1 0 0 6 linha 𝑠2
𝑠3 0 -1 1 0 0 1 0 1 linha 𝑠3
𝑠4 0 0 1 0 0 0 1 2 linha 𝑠4
Solução inicial viável: 𝑥1 = 0, 𝑥2 = 0, 𝑠1 = 24, 𝑠2 = 6, 𝑠3 = 1, 𝑠4 = 2
9
COLOCANDO NO TABLEAUX
Função z é alterada para o formato de equação, igualada a zero:
𝑧 ∶ 5𝑥1 + 4𝑥2 ⇒ 𝑧 − 5𝑥1 − 4𝑥2 = 0
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24 linha 𝑠1
𝑠2 0 1 2 0 1 0 0 6 linha 𝑠2
𝑠3 0 -1 1 0 0 1 0 1 linha 𝑠3
𝑠4 0 0 1 0 0 0 1 2 linha 𝑠4
Solução inicial viável: 𝑥1 = 0, 𝑥2 = 0, 𝑠1 = 24, 𝑠2 = 6, 𝑠3 = 1, 𝑠4 = 2
A solução não é ótima, porque há valores negativos na linha z (𝑥1 e 𝑥2 ) e o
problema é de maximização. Pode-se melhorar aumentando o valor de 𝑥1 ou 𝑥2 . 9
VARIÁVEL QUE ENTRA NA BASE E VARIÁVEL QUE SAI
Observando a função objetivo (linha 𝑧), a variável que tem coeficiente mais
positivo deve entar na base (𝑥1 ). Para maximização, observamos os valores
originais da função z, ou seja, antes de inverter os coeficientes. Isto se chama
condição de otimalidade.
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
10
VARIÁVEL QUE ENTRA NA BASE E VARIÁVEL QUE SAI
A determinação da variável que sai com base na tabela exige o cálculo das razões
não negativas entre o lado direito das equações (coluna solução) e o coeficiente
de restrição correspondente da variável que entra, 𝑥1 , como a seguir:
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24 24/6 = 4
𝑠2 0 1 2 0 1 0 0 6 6/1 = 6
𝑠3 0 -1 1 0 0 1 0 1 1/ − 1 = −1
𝑠4 0 0 1 0 0 0 1 2 2/0 = 𝑒𝑟𝑟𝑜
10
VARIÁVEL QUE ENTRA NA BASE E VARIÁVEL QUE SAI
Conclusão: 𝑥1 entra e 𝑠1 sai porque tem o menor coeficiente.
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
10
RECALCULANDO A SOLUÇÃO BÁSICA
1. Linha do pivô:
1.1 Substituir a variável que sai da base na coluna Base pela variável que entra
1.2 Nova linha do pivô: Linha do pivô atual / Elemento pivô
2. Todas as outras linhas, incluindo 𝑧:
Nova linha = Linha atual - Coeficiente de coluna do pivô x Nova linha do pivô
11
NOVA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
Nova linha do pivô: Linha do pivô atual / Elemento pivô
NL𝑥1 = [0,6,4,1,0,0,0,24] / 6
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
2 1
𝑥1 0 1 3 6 0 0 0 4
12
NOVA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
NL = Linha atual - Coeficiente coluna pivô x Nova linha pivô
NL𝑧 = [1,-5,-4,0,0,0,0,0] - (-5) * [0,1, 32 , 16 ,0,0,0,4]
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 0 - 32 5
6 0 0 0 20 linha 𝑧
2 1
𝑥1 0 1 3 6 0 0 0 4
12
NOVA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
NL = Linha atual - Coeficiente coluna pivô x Nova linha pivô
NL𝑠2 = [0,1,2,0,1,0,0,6] - (1) * [0,1, 23 , 61 ,0,0,0,4]
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 0 - 32 5
6 0 0 0 20 linha 𝑧
2 1
𝑥1 0 1 3 6 0 0 0 4
4
𝑠2 0 0 3 - 16 1 0 0 2
12
NOVA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
NL = Linha atual - Coeficiente coluna pivô x Nova linha pivô
NL𝑠3 = [0,-1,1,0,0,1,0,1] - (-1) * [0,1, 23 , 16 ,0,0,0,4]
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 0 - 32 5
6 0 0 0 20 linha 𝑧
2 1
𝑥1 0 1 3 6 0 0 0 4
4
𝑠2 0 0 3 - 16 1 0 0 2
5 1
𝑠3 0 0 3 6 0 1 0 5
12
NOVA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 -5 -4 0 0 0 0 0 linha 𝑧
𝑠1 0 6 4 1 0 0 0 24
𝑠2 0 1 2 0 1 0 0 6
𝑠3 0 -1 1 0 0 1 0 1
𝑠4 0 0 1 0 0 0 1 2
NL𝑠4 = [0,0,1,0,0,0,1,2] - (0) * [0,1, 23 , 16 ,0,0,0,4]
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 0 - 32 5
6 0 0 0 20 linha 𝑧
2 1
𝑥1 0 1 3 6 0 0 0 4
4
𝑠2 0 0 3 - 16 1 0 0 2
5 1
𝑠3 0 0 3 6 0 1 0 5
𝑠4 0 0 1 0 0 0 1 2
12
REPETINDO
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
𝑧 1 0 - 23 5
6 0 0 0 20 linha 𝑧
2 1
𝑥1 0 1 3 6 0 0 0 4 4 / ( 23 ) = 6
4
𝑠2 0 0 3 - 16 1 0 0 2 2 / ( 43 ) = 1,5
5 1
𝑠3 0 0 3 6 0 1 0 5 5 / ( 53 ) = 3
𝑠4 0 0 1 0 0 0 1 2 2/1=2
Maior coeficiente da função 𝑧 é 𝑥2 (Otimimalidade). A variável que sai é 𝑠2 (menor
coeficiente).
13
ÚLTIMA SOLUÇÃO BÁSICA
Base 𝑧 𝑥1 𝑥2 𝑠1 𝑠2 𝑠3 𝑠4 Solução
3 1
𝑧 1 0 0 4 2 0 0 21 linha 𝑧
1
𝑥1 0 1 0 4 - 12 0 0 3
𝑥2 0 0 1 - 81 3
4 0 0 3
2
3
𝑠3 0 0 0 8 - 54 1 0 5
2
1
𝑠4 0 0 0 8 - 34 0 1 1
2
Ótima! Porque todos os coeficientes de 𝑧 são positivos (maximização).
14
LISTA DE EXERCÍCIOS
Exercícios Propostos no livro Pesquisa Operacional (Lorsch, Claudio. Hein,
Nelson):
Página 104. Número 2.
15
EXERCÍCIO TAHA
Encontre a solução para o seguinte modelo, usando o método simplex.
Maximizar z = 2𝑥1 + 𝑥2 − 3𝑥3 + 5𝑥4
Sujeito a: 𝑥1 + 2𝑥2 + 2𝑥3 + 4𝑥4 ≤ 40
2𝑥1 − 𝑥2 + 𝑥3 + 2𝑥4 ≤ 8
4𝑥1 − 2𝑥2 + 𝑥3 − 𝑥4 ≤ 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
16
FONTES CONSULTADAS
• LORSCH, CLAUDIO. HEIN, NELSON. Pesquisa Operacional. Editora Saraiva. 2009.
• BAZARAA, MOKHTAR S. et al. Linear Programming and Network Flows. Wiley.
2010.
• MOREIRA, DANIEL A. Pesquisa Operacional Curso Introdutório. 2a. Ed.
Cengage Learning. 2013.
• SOTTINEN, TOMMI. Operations Research with GNU Linear Programming Kit.
2009.
17