MOQ – 43
PESQUISA
OPERACIONAL
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Programa do curso:
Semana
Conteúdo
1
Apresentação da disciplina. Formulação em programação matemática (PM).
2
Introdução à Programação Linear. (PL) Resolução de problemas de PL pelo Método Gráfico. Introdução ao
método simplex para resolução de PPL .
3
Resolução de problemas de PL pelo Método Simplex. A matemática do método simplex.
4
Problemas com soluções iniciais (Método das 2 fases e o Big-M). Degeneração, ciclagem e convergência do
método simplex.
5
Análise de Sensibilidade. Resolução computacional de problemas de programação matemática.
6
Prova 1
7
O problema dual. Formulação e Interpretação econômica do problema dual. Teoremas da dualidade.
8
Algoritmos simplex adicionais. Análise pós-otimização.
9
O Problema do Transporte.
10
O problema do Transbordo. O problema da Designação.
11
Programação Linear Inteira: Formulação, Método de Branch and Bound. Problemas de otimização combinatória.
12
Prova
13
Otimização em Redes. O problema do caixeiro viajante e do carteiro chinês. Os problemas do caminho mínimo e
do fluxo máximo.
14
Introdução à programação não-linear.
15
Princípios de otimização global. Métodos não exatos para resolução de problemas de PM.
16
Princípios de programação multiobjetivo. Fechamento da disciplina.
MOQ – 43
INTRODUÇÃO À
PROGRAMAÇÃO
LINEAR
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Programação Linear:
• Técnica que se propõe otimizar (maximizar ou minimizar) o valor
de uma função linear, respeitando um conjunto de restrições
(equações ou inequações) lineares.
• George B. Dantzig (1947): planejamento logístico (suprimentos)
• Objetivo: tratar problemas de alocação de recursos - determinar
o modo mais eficiente de utilizar os recursos limitados;
• Linear: implica que todas as funções do problema são lineares.
Um modelo de programação linear (PL) reduz um sistema real a
um conjunto de equações ou inequações em que pretendemos
otimizar uma função objetivo.
Problema de programação linear:
Considere o seguinte problema:
( Maximizar / Minimizar ) Z  a1 x1  a2 x2  ...  an xn
Sujeito a :
b11x1  b12 x2  ...  b1n xn   c1
b 21x1  b22 x2  ...  b2 n xn   c2




b k1x1  bk 2 x2  ...  bkn xn   ck
x1 ,
x 2 , .... ,
xn  0
Z: função objetivo (função critério)
ai: coeficientes da função objetivo (custo / lucro), i = 1,…,n
xi: variáveis de decisão, i = 1,…,n
bji: coeficientes tecnológicos, i = 1,…,n e j = 1,…,k
cj: constantes do lado direito (right-hand-side), j = 1,…,k
Exemplo de problema de PL (mix de produção):
Uma empresa fabrica 2 tipos de porta – de madeira e de alumínio.
Cada porta passa por 3 operações: corte, montagem e
acabamento. O tempo gasto em cada uma dessas etapas por
cada tipo de porta é:
Madeira
Alumínio
Disponibilidade
Corte
1,5 h/porta
4,0 h/porta
24 h
Montagem
3,0 h/porta
1,5 h/porta
21 h
Acabamento
1 h/porta
1 h/porta
h h
8,75
Determine a quantidade de portas (de madeira e de alumínio) a
serem fabricadas para maximizar o lucro da empresa, respeitando
os recursos disponíveis (horizonte do planejamento: 1 dia).
Lucro unitário: porta de madeira: R$4,00
porta de alumínio: R$6,00
Exemplo de problema de PL (mix de produção):
Variável de decisão:
xi  quantidade do produto i (i = madeira, alumínio) que serão fabricados
Função Objetivo:
Maximizar Lucro = Z = 4,0*xmadeira + 6,0*xalumínio
Restrições: capacidade produtiva
corte  1,5*xmadeira + 4,0*xalumínio  24
montagem  3,0*xmadeira + 1,5*xalumínio  21
acabamento  1,0*xmadeira + 1,0*xalumínio  8
Restrições: não negatividade
xmadeira, xalumínio  0
Hipóteses em Programação Linear:
 Proporcionalidade: todos os retornos / custos e recursos
utilizados variam proporcionalmente a variável de decisão (não há
economia de escala);
 Aditividade: o efeito total de quaisquer duas variáveis é a soma
dos efeitos individuais (não há sinergia ou efeito de substituição).
Exemplo: o custo total é a soma dos custos individuais;
 Divisibilidade: as variáveis de decisão podem assumir valores
fracionados. Se essas variáveis só puderem assimir valores
inteiros o problema é de programação inteira (PI);
 Certeza (Determinístico): todos os parâmetros do modelo são
constantes conhecidas (não são variáveis aleatórias);
MOQ – 43
PL – RESOLUÇÃO
PELO MÉTODO
GRÁFICO
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Objetivo:
 Descrever o procedimento gráfico / geométrico para
resolver problemas de programação linear
 Obter a solução ótima pelo gradiente da função objetivo
 Obter a solução ótima enumerando os pontos extremos
 Ilustrar condições especiais:
•
Múltiplas soluções ótimas
•
Restrições redundantes
•
Solução ilimitada
•
Solução inviável
Problema de mix de produção:
Uma empresa fabrica 2 tipos de porta – de madeira e de alumínio.
Cada porta passa por 3 operações: corte, montagem e
acabamento. O tempo gasto em cada uma dessas etapas por
cada tipo de porta é:
Madeira
Alumínio
Disponibilidade
Corte
1,5 h/porta
4,0 h/porta
24 h
Montagem
3,0 h/porta
1,5 h/porta
21 h
Acabamento
1 h/porta
1 h/porta
h h
8,75
Determine a quantidade de portas (de madeira e de alumínio) a
serem fabricadas para maximizar o lucro da empresa, respeitando
os recursos disponíveis (horizonte do planejamento: 1 dia).
Lucro unitário: porta de madeira: R$4,00
porta de alumínio: R$6,00
Problema de mix de produção:
Variável de decisão:
xi  quantidade do produto i (i = madeira, alumínio) que serão fabricados
Função Objetivo:
Maximizar Lucro = Z = 4,0*xmadeira + 6,0*xalumínio
Restrições: capacidade produtiva
corte  1,5*xmadeira + 4,0*xalumínio  24
montagem  3,0*xmadeira + 1,5*xalumínio  21
acabamento  1,0*xmadeira + 1,0*xalumínio  8
Restrições: não negatividade
xmadeira, xalumínio  0
5
10
xalumínio
Problema de mix de produção:
5
10
15
xmadeira
5
10
xalumínio
Problema de mix de produção:
corte  1,5*xmadeira + 4,0*xalumínio  24
5
10
15
xmadeira
montagem  3,0*xmadeira + 1,5*xalumínio  21
5
10
xalumínio
Problema de mix de produção:
5
10
15
xmadeira
10
xalumínio
Problema de mix de produção:
5
acabamento  1,0*xmadeira + 1,0*xalumínio  8
5
10
15
xmadeira
10
xalumínio
Problema de mix de produção:
5
Não-negatividade  xmadeira,xalumínio  0
5
10
15
xmadeira
10
xalumínio
Problema de mix de produção:
 POLÍGONO CONVEXO
5
REGIÃO (CONJUNTO) DE
SOLUÇÕES VIÁVEIS
5
10
15
xmadeira
Problema de mix de produção:
xalumínio
Solução por enumeração dos pontos extremos
 PONTOS EXTREMOS
5
5
xmadeira
xalumínio
Lucro (Z)
0
0
0
0
6
36
7
0
28
3,2
4,8
41,6
6
2
36
xmadeira
Problema de mix de produção:
Restrições ativas
xalumínio
xmadeira xalumínio
0
0
xmadeira, xalumínio  0
0
6
Xmadeira  0, corte:1,5*xmadeira+4,0*xalumínio24
7
0
xalumínio  0,
montagem:3,0*xmadeira+1,5*xalumínio21
3,2
4,8
corte: 1,5*xmadeira+4,0*xalumínio24,
acabamento: 1,0*xmadeira + 1,0*xalumínio  8
6
2
acabamento: 1,0*xmadeira + 1,0*xalumínio  8,
montagem: 3,0*xmadeira+1,5*xalumínio21
RESTRIÇÕES ATIVAS:
CORTE e ACABAMENTO
4,8
3,2
5
xmadeira
Obs:Montagem - tempo ocioso: 4,2 h/dia
Solução pelo gradiente da função objetivo
10
xalumínio
Problema de mix de produção:
5
Lucro = Z = 4,0*xmadeira + 6,0*xalumínio
5
10
15
xmadeira
5
10
xalumínio
Problema de mix de produção:
5
10
15
xmadeira
xalumínio
Problema de mix de produção:
Z = 41,6
4,8
3,2
5
xmadeira
Condições especiais – múltiplas soluções ótimas:
xalumínio
Maximizar Lucro = Z = 6,0*xmadeira + 6,0*xalumínio
6
6
xmadeira
10
xalumínio
Problema de mix de produção:
montagem  3,0*xmadeira + 1,5*xalumínio  21
5
Lucro = Z = 1*xmadeira + 2*xalumínio , 1,
2 > 0
acabamento  1,0*xmadeira + 1,0*xalumínio  8
corte  1,5*xmadeira + 4,0*xalumínio  24
5
10
15
xmadeira
xalumínio
Condições especiais – restrições redundantes:
Restrição adicional:
5
10
inspeção  1,75*xmadeira + 3,0*xalumínio  21
5
10
15
xmadeira
Condições especiais – solução ilimitada:
x2
10
Max x1 + x2
S.A. x1 + x2  4
- x1 + 2x2  4
5
x1, x2  0
5
10
x1
Condições especiais – solução inviável:
Max x1 + x2
x2
10
S.A. x1 + x2  8
x1 + x2  4
5
x1, x2  0
5
10
x1
MOQ – 43
RESOLUÇÃO DE
SISTEMAS LINEARES
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Eliminação Gaussiana (Pivotamento, Gauss-Jordan):
É um método direto para solução de sistemas de equações lineares.
Propriedade: A solução do sistema Ax = b não se altera se o submetermos a
uma seqüência de operações do tipo:
i. Multiplicação de uma equação por constante não-nula;
ii. Soma do múltiplo de uma equação à outra;
iii. Troca da ordem das equações.
Ex:
2x1 + 4x2 = 4
2x1 + 3x2 = 6
 2 4 4 1 0


 2 3 6 0 1
1 0 6  3 2 2 


1
 1
0 1  2
Eliminação Gaussiana (Pivotamento):
2x1 + 4x2 = 4
2x1 + 3x2 = 6
 2 4

A  
 2 3
 4
b   
6
 2 4 4 1 0  1 2 2 1/ 2 0  1 0 6  3 2 2 

  
  

1
 1
 2 3 6 0 1 0 1 2 1 1 0 1  2
 x1   6 
 x     

 x2    2 
A
1
3/ 2 2 

 
 1
 1
MOQ – 43
PL – INTRODUÇÃO AO
MÉTODO SIMPLEX
Professor: Rodrigo A. Scarpel
[email protected]
www.mec.ita.br/~rodrigo
Formas de Representação:
Formato padão: todas as restrições são igualdades e todas as
variáveis são não-negativas.
 Formato canônico: (problema de minimização) todas as
variáveis são não-negativas e todas as restrições são do tipo  .
Manipulação do problema:
 Inequações e Equações:
n
a
n
a
ij x j
 bi
ij x j
 bi
ij x j
 bi
j 1
n
j 1
a
j 1
n
n
a
ij x j
 bi 
j 1
n
a
ij x j
j 1
a
ij x j
 xn 1  bi
xn+1: variável de excesso
a
ij x j
 xn 1  bi
xn+1: variável de folga
j 1
n
 bi 
j 1
n
 Maximização e Minimização: Z   c j x j
j 1
Maximizar Z  Minimizar  Z
 Não-negatividade: x j (irrestrito)  x j  x j  x j
x j , x j  0
Problema de mix de produção:
FO: Maximizar Z = 4,0*xmadeira + 6,0*xalumínio
S.A. 1,5*xmadeira + 4,0*xalumínio  24
3,0*xmadeira + 1,5*xalumínio  21
1,0*xmadeira + 1,0*xalumínio  8
xmadeira, xalumínio  0
 a1,1 a1, 2

 a2,1 a2, 2
A



a
 m,1 am,2
1,5x1+ 4,0x2+ 1x3
= 24
3,0x1+ 1,5x2
+ 1x4
= 21
1,0x1+ 1,0x2
+ 1x5 = 8
x1,
x2, x3 , x4 , x5  0
 a1, n 
 x1 
 b1 
   24 
 
 1,5 4 1 0 0 
 a2 , n  

 b2   
 x2 
b

  21 
  3 1,5 0 1 0  , x    ,







   8 
 
  1 1 0 0 1 
b 
x 
 am, n 
 m
 n
Ax = b  sistema linear indeterminado com m equações e
n variáveis (n  m)
Variáveis básicas e variáveis não básicas:
 Definição: Uma base de uma matrix A (m x n) é uma matriz quadrada
de m vetores coluna linearmente independentes em m. As variáveis
associadas a essas colunas são denominadas variáveis básicas.
Assim, é possível decompor o vetor de variáveis em x = (xB, xR), em que:
xB representa o vetor das variáveis básicas de m componentes e
xR representa o vetor das n-m variáveis restantes (não-básicas).
No exemplo:
VARIÁVEIS BÁSICAS
FOLGACORTE, FOLGAMONTAGEM , FOLGAACABAMENTO
VARIÁVEIS NÃO BÁSICAS
XMADEIRA, XALUMÍNIO
XMADEIRA, FOLGAMONTAGEM , FOLGAACABAMENTO
XALUMÍNIO, FOLGAMONTAGEM , FOLGAACABAMENTO
FOLGACORTE, XALUMÍNIO
FOLGACORTE, XMADEIRA
FOLGACORTE, XMADEIRA, FOLGAACABAMENTO
FOLGAMONTAGEM , XALUMÍNIO
FOLGACORTE, XALUMÍNIO, FOLGAACABAMENTO
FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XALUMÍNIO
FOLGAACABAMENTO, XALUMÍNIO
FOLGAACABAMENTO, XMADEIRA
XMADEIRA, XALUMÍNIO, FOLGACORTE
FOLGAMONTAGEM , FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAMONTAGEM
FOLGACORTE, FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAACABAMENTO
FOLGACORTE, FOLGAMONTAGEM
Variáveis básicas e variáveis não básicas:
Se estendermos o raciocínio à matriz A, podemos dividi-lá em uma matriz
m x m, que denominaremos por matriz B, e outra m x (n-m), que
denominaremos matriz R. Assim:
B
R
No exemplo:
VARIÁVEIS BÁSICAS
FOLGACORTE, FOLGAMONTAGEM, FOLGAACABAMENTO
1,5 4 1 0 0 


A   3 1,5 0 1 0 
 1 1 0 0 1




B


1 0 0

0 1 0
0 0 1 
VARIÁVEIS NÃO BÁSICAS
XMADEIRA, XALUMÍNIO
1,5 4

R   3 1,5
1 1






Variáveis básicas e Soluções básicas
Como podemos solucionar o conjunto de equações m x m somente em
função das variáveis básicas, temos que x = (xB, 0), em que xB = B-1b
No exemplo:
VARIÁVEIS BÁSICAS
FOLGACORTE, FOLGAMONTAGEM, FOLGAACABAMENTO
 24 
 
b   21 
8
 
1,5 4

R   3 1,5
1 1

 FOLGACORTE   24 

  
 FOLGAMONTAGEM   21 
x   FOLGAACABAMENTO   8 

  
x MADEIRA

 0

  
x
ALUMÍNIO

 0





x2
1 0 0

0 1 0
0 0 1 
10
B 1
1 0 0


 0 1 0
0 0 1




B


5
1,5 4 1 0 0 


A   3 1,5 0 1 0 
 1 1 0 0 1


VARIÁVEIS NÃO BÁSICAS
XMADEIRA, XALUMÍNIO
5
10
15
x1
Variáveis básicas e Soluções básicas
No exemplo:
VARIÁVEIS BÁSICAS
XMADEIRA, XALUMÍNIO, FOLGAACABAMENTO
1,5 4 1 0 0 


A   3 1,5 0 1 0 
 1 1 0 0 1


1,5 4

B   3 1,5
1 1

  0,154 0,410 0 

1 
B   0,307  0,154 0 
  0,154  0,256 1 




R


0

0
1 
1 0
0 1
0 0





10
x2
xMADEIRA

  4,9 

 

x
4
,
1

 

ALUMÍNIO
x   FOLGAACABAMENTO    1,1

 

FOLGA

  0 
CORTE
 FOLGA
 

MONTAGEM   0 

5
 24 
 
b   21 
8
 
VARIÁVEIS NÃO BÁSICAS
FOLGACORTE, FOLGAMONTAGEM
5
10
15
x1
Soluções básicas e conjunto de soluções básicas
 Definição: Seja B uma base associada à matriz A. O vetor composto
de xB = B-1b e xR=0 é chamado de solução básica.
No exemplo:
FOLGACORTE, XALUMÍNIO
FOLGACORTE, XMADEIRA
FOLGACORTE, XMADEIRA, FOLGAACABAMENTO
FOLGAMONTAGEM , XALUMÍNIO
FOLGACORTE, XALUMÍNIO, FOLGAACABAMENTO
FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XALUMÍNIO
FOLGAACABAMENTO, XALUMÍNIO
FOLGAACABAMENTO, XMADEIRA
XMADEIRA, XALUMÍNIO, FOLGACORTE
FOLGAMONTAGEM , FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAMONTAGEM
FOLGACORTE, FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAACABAMENTO
FOLGACORTE, FOLGAMONTAGEM
 CONJUNTO DE SOLUÇÕES BÁSICAS
...
XMADEIRA, FOLGAMONTAGEM , FOLGAACABAMENTO
XALUMÍNIO, FOLGAMONTAGEM , FOLGAACABAMENTO
 FOLGACORTE   24 

  
 FOLGAMONTAGEM   21 
x   FOLGAACABAMENTO   8 

  
x MADEIRA

 0

  
x ALUMÍNIO

 0
...
VARIÁVEIS NÃO BÁSICAS
XMADEIRA, XALUMÍNIO
...
VARIÁVEIS BÁSICAS
FOLGACORTE, FOLGAMONTAGEM , FOLGAACABAMENTO
xMADEIRA

  4,9 

 

x

  4,1 
ALUMÍNIO
x   FOLGAACABAMENTO    1,1

 

 FOLGACORTE   0 
 FOLGA
 

MONTAGEM   0 

VARIÁVEIS BÁSICAS
FOLGACORTE, FOLGAMONTAGEM , FOLGAACABAMENTO
VARIÁVEIS NÃO BÁSICAS
XMADEIRA, XALUMÍNIO
XMADEIRA, FOLGAMONTAGEM , FOLGAACABAMENTO
XALUMÍNIO, FOLGAMONTAGEM , FOLGAACABAMENTO
FOLGACORTE, XALUMÍNIO
FOLGACORTE, XMADEIRA
FOLGACORTE, XMADEIRA, FOLGAACABAMENTO
FOLGAMONTAGEM , XALUMÍNIO
FOLGACORTE, XALUMÍNIO, FOLGAACABAMENTO
FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XMADEIRA
FOLGACORTE, FOLGAMONTAGEM , XALUMÍNIO
FOLGAACABAMENTO, XALUMÍNIO
FOLGAACABAMENTO, XMADEIRA
XMADEIRA, XALUMÍNIO, FOLGACORTE
FOLGAMONTAGEM , FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAMONTAGEM
FOLGACORTE, FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAACABAMENTO
FOLGACORTE, FOLGAMONTAGEM
5
10
xalumínio
Conjunto de soluções básicas
5
10
15
xmadeira
Soluções básicas viáveis (bfs)
 Definição: Uma solução básica sem componentes negativos é
denominada solução básica viável (bfs).
10
x2
xMADEIRA

  4,9 

 

x
4
,
1

 

ALUMÍNIO
x   FOLGAACABAMENTO    1,1

 

 FOLGACORTE   0 
 FOLGA
 

0
MONTAGEM  


5
 FOLGACORTE   24 

  
 FOLGAMONTAGEM   21 
x   FOLGAACABAMENTO   8 

  
x MADEIRA

 0

  
x
ALUMÍNIO

 0
5
10
15
x1
 Solução básica viável: Ax=b, x0
Solução básica viável  Ponto Extremo
Conjunto de soluções viáveis
 Propriedade: O conjunto de soluções viáveis de um
PPL é um conjunto convexo.
5
10
xalumínio
 Definição: O conjunto C = {x tal que Ax=b, x0] denomina-se conjunto
de soluções viáveis.
5
10
15
xmadeira
Para casa:
• Leitura: - Taha: 2.2 (Graphical LP Solutions)
3.1 e 3.2 (LP Model,…)
- Winston: 2.3 (Gauss-Jordan Method …)
3.2 e 3.3 (The Graphical Solution …)
4.1 e 4.3 (How to convert …)
• Lista de Exercícios 2
OBSERVAÇÃO
Este material refere-se às notas de aula do curso
MOQ-43 (Pesquisa Operacional) do Instituto
Tecnológico de Aeronáutica (ITA). Não substitui o
livro texto, as referências recomendadas e nem as
aulas expositivas. Este material não pode ser
reproduzido sem autorização prévia do autor.
Quando autorizado, seu uso é exclusivo para
atividades de ensino e pesquisa em instituições
sem fins lucrativos.