Universidade Federal de Campina Grande
Centro de Ciências e Tecnologia
Unidade Acadêmica de Engenharia Química
Programa de Pós-Graduação
Otimização Numérica de Processos
Problemas Multidimensionais com
Restrição – Programação Linear
De volta ao Problema Simples
0.5x2  x4  0.7 x2
Solvente leve (x3),
$53/bbl
Solvente médio (x4),
$68/bbl
0.3x2  x5  0.5x2
x3  0.4x1
200  x4  400
Nafta (x1),
$42/bbl
x1  2000
Solvente pesado (x5),
$42/bbl
Solvente (x2)
Como obter o maior lucro?
Custo _ Op  1.25x1  1.25x2
Generalidades

Um dos métodos mais utilizados em
otimização

Uma ciência relativamente nova (1947)

George Dantzig

Função objetivo e restrições: lineares
Introdução
Maximizar f ( x)  x1  x2
x2
•Cada reta tracejada
representa uma curva de
nível
f=3
Direção do
aumento de f
f=2
•As retas são paralelas
f=1
•A 1a derivada de f nunca
será zero
•Não existe máximo (ou
mínimo) finito
x1
Continuando com a Introdução
Maxim izar f ( x)  x1  x2
Sujeitoa
x1  2
x2  1

Com as restrições, a
região viável fica limitada

O extremo sempre
ocorrerá na intersecção
das restrições

É a base da Programação
Linear
x2
f=3
f=2
f=1
x1  2
x2  1
x1
Refinaria de Petróleo
Óleo 1 ($24/bbl)
Gasolina ($36/bbl)
Querosene ($24/bbl)
Refinaria
Combustível ($21/bbl)
Residual ($10/bbl)
Óleo 2 ($15/bbl)
Composição em massa (%)
Produção maxima bb/dia
Óleo 1
Óleo 2
Gasolina
80
44
24000
Querosene
5
10
2000
Combustível
10
36
6000
Resíduo
5
10
Custo de Processo ($/bbl)
0.50
1
Formulando o Problema

Definição das variáveis
x1  bbl / dia de óleo1
x2  bbl / dia de óleo 2
x3  bbl / dia de gasolina
x4  bbl / dia de querosene
x5  bbl / dia de combust ível
x6  bbl / dia de resíduo
Continuando com a Formulação

Definiçao da função objetivo
•
Maximizar lucro
f  receita  despesa($/dia)
receita  36x3  24x4  21x5  10x6
despesa  24x1  15x2  0.5 x1  1x2

Despesa inclui a matéria-prima e custo
com operação
Finalizando a Formulação

Restrições
•
Balanço de massa (rendimento)
0.8 x1  0.44x2  x3
0.05x1  0.10x2  x4
0.10x1  0.36x2  x5
•
0.05x1  0.10x2  x6
De mercado
x3  24000
x4  2000
x5  6000
Manipulações Algébricas

Função objetivo: substituição das igualdades
dentro da função objetivo inicial
f  8.1x1  10.8x2

Restrições: idem
0.8 x1  0.44x2  24000
0.05x1  0.10x2  2000
0.10x1  0.36x2  6000
x1  0
x2  0
Solução Gráfica
20

Plotar as restrições no
plano x1-x2
Determinar a região
possível
15
Óleo 2, 1000 bbl

10
5

Localizar o ponto onde a
função é máxima
•
•
Dentro da região possível
Em uma das intersecções
das restrições
0
0
10
20
Óleo 1, 1000 bbl
Rest riçã o 1
Rest riçã o 2
Ret riçã o 3
f = 18 0
f = 24 3
f = 25 6.5
f = 28 6.7
30
Determinando a Intersecção

Determinar cada ponto de intersecção

Calcular o valor de f em cada intersecção
20
Re strição1 e x 2  0
Re strição 3 e x1  0
x1  0 e x2  16667 f  180000
Re strições1 e 2
x1  26000 e x2  7000 f  286700
Re strições 2 e 3
x1  15000 e x2  12500 f  256500
15
Óleo 2, 1000 bbl
x1  30000 e x2  0  f  243000
10
5
0
0
10
20
Óleo 1, 1000 bbl
Rest riçã o 1
Rest riçã o 2
Ret riçã o 3
30
No Mathcad
f( x  y)   8 .1 x  1 0.8 y
30
 2 40 00
b    2 00 0 


 6 00 0 
 .8 x  .4 4 y 


x
M    b   5 . 1 0-2 x  .1 0 y 
 y


 .1 0 x  .3 6 y 
 2 40 00
  2 00 0 


 6 00 0 
20
y/1000
 0 .8 0 .44
M    0 .05 0 .10


 0 .10 0 .36
10
0
x   1 00 0
y   2 00 00
x
b
 y
x0
 2 .62 1 1 04 


3
 6 .89 7 1 0 
Ma xim ize( f x  y)  
10
20
x/1000
G iven
M 
0
y0
30
Solução Degenerada I

Não existe solução única
6
Maximizar f ( x)  2 x1  0.5 x2
6x1  5 x2  30
4x1  x2  12
x1 , x2  0
4
x2
Sujeito
2
0

Restrição 2 e f são
linearmente dependentes
0
2
4
x1
Rest riçã o 1
Rest riçã o 2
f =2
f =4
f =6
6
Solução Degenerada II

Ótimo sem restrição
6
Minimizar f ( x)   x1  x2
3x1  x2  0
x2  3
x1 , x2  0

x1 não impede a
diminuição de f
x2
Sujeito
4
2
0
0
2
4
x1
Rest riçã o 1
Rest riçã o 2
f = -4
f = -6
6
Solução Degenerada III

Ausência de região possível
10
5
Sujeito
x1  x2  2
x2
Minimizar f ( x)   x1  x2
10
5
x1  2 x2  0
0
5
x1 , x2  0
10
x1
Rest riçã o 1
Rest riçã o 2
f = -2
f = -6
5
10
Método Simplex

Antes, a solução gráfica
6
Minimizar f ( x)   x1  x2
2x1  x2  2
- x 1  3 x 2  2
- x 1  x 2  4
4
x2
Sujeito
2
x1 , x2  0
0

O ótimo ocorre na
intersecção das
restrições 2 e 3
0
1
2
Rest riçã o 1
Rest riçã o 2
Rest riçã o 3
f =2
f =0
f = -3
3
x1
4
5
6
Passos 1 e 2 do Simplex

Converter o lado direito das restrições em números
positivos
- 2x  x  2
1
2
x 1  3 x2  2
x 1  x2  4
x 1 , x2  0

Converter todas as desigualdades das restrições em
igualdades
•
Variáveis de folga: x3, x4 e x5
- 2x1  x2  x3  2
x 1  3 x2  x4  2
x1  x2  x5  4
x1 , x2 , x3 , x4 , x5  0
Passo 3 do Simplex


Temos agora n (5) variáveis e m (3) equações
•
NF=n-m=2; O sistema não tem solução única
Solução básica (possível)
•
•
•
Fixar o valor de n-m variáveis (igual a zero); resolver
Variável não básica (x1 e x2): igual a zero
Variável básica (x3, x4 e x5): diferente de zero
- 2x1  x2  x3  2
x3 - 2 x1  x2  2  x3  2
x 1  3 x2  x4  2
x4  x1  3x2  2  x4  2
x1  x2  x5  4
x1 , x2 , x3 , x4 , x5  0
x5  x1  x2  4  x5  4
f  x1  x2  0  f  0
Passo 4 do Simplex

A solução básica inicial não corresponde ao mínimo; necessário
mudar a solução básica

Examinando f (lembrar que é uma minimização)
•
•
O aumento de x1 provoca diminuição (maior coeficiente positivo)
O aumento de x2 provoca o aumento
x3 - 2 x1  x2  2

Nova variável básica: x1
x4  x1  3 x2  2

Nova variável não básica: x3, x4 ou x5
x5  x1  x2  4
•
•
•
Restrição 1: x1 pode aumentar indefinidamente
Restrição 2: x1 pode aumentar até 2
Restrição 3: x1 pode aumentar até 4
Dica de como detectar a restrição
com a nova variável não básica?
f  x1  x2  0
Nova variável não básica: x4
Passo 5 do Simplex

Novas equações, em função das novas variáveis não básicas (x2
e x4)
•
•
A partir da restrição 2, explicitar x1 e substituir nas outras equações
Observe que o valor de f diminuiu para -2
x1  2  3x2  x4 
x3  2  2 x1  x2  6  2 x4  5 x2
x5  4  x1  x2  2  x4  4 x2
f   x1  x2  2  x4  2 x2
x3  2 x4  5 x2  6
x1  x4  3 x2  2
x5  x4  4 x2  2
f  x 4  2 x 2  2
Continuar …
Eliminação e Simplex

Usar eliminação (Gaussiana) no lugar da substituição
algébrica
 2 1
 1 3

1
1

 1 1
1 0 0
0 1 0
0 0 1
0 0 0
Pivô
 2 1
 1 3

1
1

 1 1
1
0
0
0
0
1
0
0
 x1 
0  x2  2
0  x3  2
 
0   x4   4 

 
1  x5  0
 
 f 
0
0
1
0
0
0
0
1
2
2
4

0

Gauss: aumentar a matriz

Três 1as linhas: restrições

Última linha: função objetivo

Como escolher o pivô?
• Coluna: maior positivo de f
• Linha: menor quociente positivo
Eliminando …
x1
x2
x3  2 1
x4  1  3
x5  1
1

 1 1
x1
x2
x3
x4
x5
f
b
1 0 0 0 2
0 1 0 0 2
0 0 1 0 4

0 0 0 1 0
x3
x4
x3 0  5 1 2
x1 1  3 0 1
x5 0 4 0  1

0 2 0  1
x5
f
b
6
0 0 2 
1 0 2

0 1  2

Transformar a coluna do
pivô em [0 1 0 0]T:
operação com matriz

Novo pivô: a32

Nova variável básica: x2

Nova variável não básica:
x5
0 0
Finalizando a Eliminação
x1
x3 0
x1 1
x2 0

0

x2
x3
x4
x5
f
b
1.25 0 8.5
0 0 0.25 0.75 0 3.5
1 0  0.25 0.25 0 0.5

0 0  0.5  0.5 1  3
0 1
0.75
x3  0.75x4  1.25x5  8.5
x1  0.25x4  0.75x5  3.5
x2  0.25x4  0.25x5  0.5
f  0.5 x4  0.5 x5  3
Os coeficientes em f são
negativos: processo terminado
x3  8.5
x1  3.5
x 2  0 .5
f  3
Finalizando PL

Problema na forma padrão
•
•
•

x é o vetor das variáveis
c é o vetor de coeficientes
de f
A é a matriz de coeficientes
das restrições
Solução básica impossível
•
•
•
x1=x2=0
X3=-5 (impossível)
Procedimento das duas
fases
minimizar f  cT x
sujeito a Ax  b
x  0, b  0
Minimizar f  x1  2 x2
Sujeito a
3x1  4 x2  5  3x1  4 x2  x3  5
x1  x2  4  x1  x2  x4  4
Exercícios


Mathcad
Matlab (função linprogr)
• Problema 7.3 do livro do Himmelblau. Usar o
Mathcad
• Problema 7.17 do livro do Himmelblau.
• Problema 7.23 do livro do Himmelblau. Usar o
Matlab.