OTIMIZAÇAO NUMERICA PROGRAMAÇAO LINEAR ALGORITMO SIMPLEX

Prévia do material em texto

Tema 05 – Programação linear: 
algoritmo simplex
Bloco 1
Prof. Tarcísio Dantas
Otimização Numérica
W
B
A
0
5
1
3
_
V
1
_
0
Resumo
• Introdução.
• Método Simplex de programação linear.
• Aplicação do método.
Introdução
• Leonid Kantorovich (1939).
• Nobel de Economia em conjunto com 
Koopmans (1975).
• Simplex de Dantzig (1947).
• Downhill Simplex de Nelder e Mead (1965).
• Sequential Simplex de Spendeley (1962).
Método Simplex
Max 
ou Min:
𝑓 𝑥4, 𝑥5, 𝑥6 = 𝑐1𝑥4 + 𝑐2𝑥5 + 𝑐3𝑥6 = 𝑧
Sujeito a: 𝑎11𝑥4 + 𝑎12𝑥5 + 𝑎13𝑥6 < 𝑏1
𝑎21𝑥4 + 𝑎22𝑥5 + 𝑎23𝑥6 < 𝑏2
𝑎31𝑥4 + 𝑎32𝑥5 + 𝑎33𝑥6 < 𝑏3
𝑥4 ≥ 0
𝑥5 ≥ 0
𝑥6 ≥ 0
Método Simplex
• Permutação de colunas e linhas. 
• Introdução de folgas  “forma canônica”.
V. básicas Variáveis não-básicas Const
𝑥1
𝑥2
𝑥3
𝑎11𝑥4 + 𝑎12𝑥5 + 𝑎13𝑥6 =
𝑎21𝑥4 + 𝑎22𝑥5 + 𝑎23𝑥6 =
𝑎31𝑥4 + 𝑎32𝑥5 + 𝑎33𝑥6 =
𝑏1
𝑏2
𝑏3
Método Simplex
• Soluções intermediárias e função objetivo
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Tipo sol. Descrição.
Solução
básica
V. Ind = 0. Sistema de m eq. e m 
incógnitas. N=0
Solução
viável
Método Simplex
• Soluções intermediárias
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Tipo sol. Descrição.
Solução 
básica 
viável
É uma sol. básica, onde x (v. básicas e não-
básicas) satisfaz as restrições de não-
negatividade apenas. 
Solução 
ótima
Método simplex é um algoritmo de duas fases.
1. Caso exista, determinar uma solução 
básica e avaliar se é também básica viável 
ou ótima.
2. Caso o passo 1 resulte em uma solução 
básica viável:
• Determinar outra solução básica viável:
 Etapa 1.
 Etapa 2.
• Determinar se há infinitas soluções.
• Determinar a solução ótima, encerrando 
o algoritmo.
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Primeira solução básica (𝑥4, 𝑥5, 𝑥6 = 0)- escolher 
as variáveis de folga introduzidas inicialmente 
(𝑥1,𝑥2 e 𝑥3) como variáveis básicas.
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
10
Se as variáveis básicas satisfazerem as 
restrições de não-negatividade, 𝑏1 ≥ 0, 𝑏2 ≥
0, 𝑏3 ≥ 0, temos uma solução básica viável.
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Caso alguma constante 𝑏1, 𝑏1 ou 𝑏3 < 0:
tem-se uma solução básica.
As variáveis não-básicas já atendem aos 
requisitos da solução básica viável, pois todas 
são não-negativas ( 𝑥4= 𝑥5 = 𝑥6 = 0).
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Essa é a forma canônica viável.
A noção de variável de folga deixa de 
existir após a primeira iteração.
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Sinal dos coeficientes 𝑐1, 𝑐2, … , 𝑐𝑛 de 𝑓(𝑥).
No ponto ótimo 𝑐1, 𝑐2, … , 𝑐𝑛 > 0
similar as condições N&S.
Tema 05 – Programação linear: 
algoritmo simplex
Bloco 2
Prof. Tarcísio Dantas
Otimização Numérica
Método Simplex
• Por que no ponto ótimo 𝑐1, 𝑐2, … , 𝑐𝑛 > 0?
• Restrição de não-negatividade das variáveis 
básicas e não-básicas, 𝒙 ≥ 0.
• Função objetivo é função de variáveis não-
básicas apenas.
−𝑓 + 𝑐1𝑥4 + 𝑐2𝑥5 + 𝑐3𝑥6 = − 𝑏4
Método Simplex
• Só há um caminho para tentar minimizar 
𝑓(𝒙, incrementando o valor dessas 
variáveis não-básicas.
• Há também uma restrição de não-
negatividade para os coeficientes de 
𝑓(𝒙) no ponto ótimo:
-f+c1x4+c2x5+c3x6=-b4
Método Simplex
• Manipula-se as variáveis não-básicas 
cujos coeficientes são negativos, com o 
maior 𝑐 :
−𝑓 + 𝑐1𝑥4 + (−𝑐2)𝑥5 + (−𝑐3)𝑥6 = − 𝑏4
• Essa manipulação é realizada por 
substituição de uma variável básica pela 
variável não-básica com o maior |𝒄|, 
através de duas etapas.
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
Etapa 1: Escolher a variável não-básica que se 
torna variável básica. (”entra”)
Etapa 2: Escolher a variável básica que irá 
substituir a variável.
não-básica escolhida na etapa 1. (“sai”)
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
• A variável básica escolhida para “sair” da 
solução básica possui menor sensibilidade 
em relação à 𝑓(𝑥) e a v. que “entra”.
• Note que cada linha da matriz canônica 
viável possui apenas uma variável básica 
( 𝑥1, 𝑥2 𝑒 𝑥3).
Método Simplex
𝑥1 0 0 0 𝑎11𝑥4 𝑎12𝑥5 𝑎13𝑥6 = 𝑏1
0 𝑥2 0 0 𝑎21𝑥4 𝑎22𝑥5 𝑎23𝑥6 = 𝑏2
0 0 𝑥3 0 𝑎31𝑥4 𝑎32𝑥5 𝑎33𝑥6 = 𝑏3
0 0 0 −𝑓 𝑐1𝑥4 𝑐2𝑥5 𝑐3𝑥6 = −𝑏4
• Calcula-se o coeficiente 𝒔𝒊 para cada 
linha da matriz:
𝑠1 =
𝑏1
𝑎12
𝑠2 =
𝑏2
𝑎22
𝑠3 =
𝑏3
𝑎32
• Coluna 2 – var. que entra.
• Exemplo: Uma empresa produz pão 
fatiado e embalado dos tipos A e B e vende 
cada unidade com o lucro de 5 e 6 reais, 
respectivamente. Para produzir cada 
unidade é necessário um determinado 
tempo de processamento nas três 
principais etapas do processo: mistura, 
cozimento e empacotamento.
Exemplo
Tempo de processamento em cada etapa.
Mistura Cozimento Empacotamento
Pão fatiado A 1 min 5 min 3 min
Pão fatiado B 2 min 4 min 1 min
Exemplo
Disponibilidade em horas diárias de cada 
etapa de processamento.
Mistura Cozimento Empacotamento
Disponibilidade 7h 20h 8h
Exemplo
𝑥1 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑜 𝑝ã𝑜 𝐴
𝑥2 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑜 𝑝ã𝑜 𝐵
Max:
Sujeito à:
Exemplo
𝑓 𝑥1, 𝑥2 = 𝑙𝑢𝑐𝑟𝑜 (𝑅$)
𝑐1𝑥1 + 𝑐2𝑥2 = 𝑐1 𝑢𝑛𝑖𝑑. 𝐴 + 𝑐2 𝑢𝑛𝑖𝑑. 𝐵
𝑐1 =
𝑅$
𝑢𝑛𝑖𝑑𝑎𝑑𝑒
Exemplo
𝑓 𝑥1, 𝑥2 = 5
𝑅$
𝑢𝑛
𝑥1 + 6
𝑅$
𝑢𝑛
𝑥2
𝑓 𝑥1, 𝑥2 = 5𝑥1 + 6𝑥2
Mistura Cozimento Empacotamento
Pão fatiado A 1 min 5 min 3 min
Pão fatiado B 2 min 4 min 1 min
Mistura
Disponibilidade 7h
Cozimento
20 h
Empacotamento
8 h
Exemplo
Agora vamos 
tratar das 
restrições.
Exemplo
• Restrições:
𝑎11𝑥1 + 𝑎12𝑥2 < 𝑏1 𝑎 𝑢𝑛𝑖𝑑𝑎𝑑𝑒 = ℎ𝑜𝑟𝑎𝑠
𝑎 =
ℎ𝑜𝑟𝑎𝑠
𝑢𝑛𝑖𝑑.
=
𝑥 𝑚𝑖𝑛.
60𝑚𝑖𝑛 × 𝑢𝑛𝑖𝑑.
𝑌 ℎ𝑜𝑟𝑎𝑠 =
𝑥 𝑚𝑖𝑛.
60 𝑚𝑖𝑛
Exemplo
• Restrições: 𝑎11𝑥1 + 𝑎12𝑥2 < 𝑏1
1 𝑚𝑖𝑛.
60𝑚𝑖𝑛 × 𝑢𝑛𝑖𝑑.
𝑥1 +
2 𝑚𝑖𝑛.
60𝑚𝑖𝑛 × 𝑢𝑛𝑖𝑑.
𝑥2 < 7ℎ
1/60 𝑥1 + 2/60 𝑥2 < 7
5/60 𝑥1 + 4/60 𝑥2 < 20
3/60 𝑥1 + 1/60 𝑥2 < 8
Exemplo
Max:
Sujeito à:
Exemplo
32