AULA 5 - Resolvendo Problemas de Programação Matemática:
Métodos de Busca
•
•
•
•
•
•
Métodos de Resolução
– Solução Analítica
– Solução Numérica
Solução Numérica - Idéia Geral
Exemplo: Problema de Localização
Ótimo Local e Ótimo Global
Busca Local: uma iteração
Cálculo da Direção de Caminhada
–
–
–
•
•
Direção Factível e Direção de Melhoria
Gradiente de f(x)
Direção de crescimento e de decrescimento.
Busca Unidimensional
Observações:
–
–
–
Função Unimodal
Função Unimodal, Conjuntos Convexos e Ótimo Global
Direção de Caminhada em Problemas com restrições
5-1
Solução de Problemas de Otimização
Métodos de Resolução
• Obtenção da Solução
– Método Analítico (solução fechada)
• Exemplo : Problema EOQ (Aula 2)
– Lote Ótimo : q* = (2fD/h)1/2
– Método Numérico
• Solução obtida através de processo numérico iterativo
5-2
Métodos Numéricos
Algoritmos de Busca
IDÉIA GERAL:
– Obter uma solução inicial factível.
– Repetir enquanto a condição de parada não é satisfeita :
• Numa vizinhança da solução atual procurar uma nova solução factível com
melhor valor da função objetivo (Busca Local ou em vizinhança)
• Atualizar solução.
• Realizar teste de parada.
5-3
Exemplo: Problema de Localização
Uma empresa pretende abrir um novo supermercado em uma região
com 3 cidades, conforme mostrado na figura a seguir.
• Problema : Determinar em que local da região deve ser localizada
a nova loja.
• Restrição : As prefeituras das 3 cidades não permitem que se
localize a nova loja dentro de numa zona delimitada por um raio
de 1/2 quilômetro a partir do centro das cidades, com o propósito
de evitar congestionamentos na área central.
5-4
Problema de Localização
Os centros populacionais e número de habitantes.
5-5
O Problema de Localização: Formulação
Função Objetivo : adota um perfil gravitacional, ou seja, supõe que
a loja tem uma capacidade de atrair clientes que é proporcional à
população da região e inversamente proporcional ao quadrado (1+)
distância que a separa dos clientes.
Maximizar
p=(60/[1+(x1 + 1)2 + ( x2 - 3)2 ] +
20/[1+(x1 - 1)2 + ( x2 - 3)2 ] +
30/[1+(x1)2 + ( x2 + 4)2 ]
Restrições :
(x1 + 1)2 + ( x2 - 3)2 >= (1/2)2
(x1 - 1)2 + ( x2 - 3)2 >= (1/2)2
(x1 - 1)2 + ( x2 - 3)2 >= (1/2)2
5-6
Problema de Localização
Visão espacial da função objetivo
Uma Solução: é uma escolha de valores para as variáveis de decisão.
Ex. : x1 = 1 , x2 = 0,5. Equivale a um ponto no espaço n, onde n é o
número de variáveis de decisão.
5-7
Problema de Localização
Processo Iterativo (visão espacial)
Cada passo do processo iterativo gera uma nova solução factível
5-8
Ótimo Local e Ótimo Global
• O processo de busca local termina em uma solução conhecida
como ótimo local.
• Nem sempre um ótimo local é um ótimo global (a melhor de
todas as soluções). Um ótimo local é sempre um ótimo global só
quando o problema apresenta características específicas, tais
como convexidade.
• Dependendo da solução inicial, pode-se obter diferentes ótimos
locais.
• Procedimento Heurístico: determinar vários ótimos locais e
escolher o melhor deles (não garante achar o ótimo global).
5-9
Busca Local: Uma iteração
Problema: A partir de x(3) determinar uma nova solução factível
x(4) com valor da função objetivo maior.
Graficamente:
Numericamente: x(4) = x(3) + α.x
•Onde:
• x é uma direção de melhoria
• α é o tamanho do passo na direção x
Um procedimento para busca local :
1) Cálculo da direção de caminhada (Direção de melhoria)
2) Busca unidimensional (Quanto caminhar nesta direção ?)
5-10
Cálculo da Direção de Caminhada:
Direção Factível e Direção de Melhoria
• Direção Factível : x(k+1) = x(k) + α.x
– Uma direção x é dita factível a partir de um ponto x(k)  CSF se
existir algum α > 0 tal que o novo ponto x(k+1) também pertença ao
CSF.
• Direção de Melhoria :
– A direção x é de melhoria se ela é uma direção factível a partir de
um ponto x(k) e se existir algum α > 0 tal que o novo ponto x(k+1) é
também factível e apresente um valor de função objetivo melhor que
o ponto x(k) .
5-11
Cálculo da Direção de Caminhada:
Direção Factível e Direção de Melhoria
Supondo um problema de minimização e o CSF definido por x1 0 e x2 0,
então todas as direções indicadas na figura abaixo são factíveis, porém
somente a direção d1 é uma direção de melhoria.
d1
5-12