Upload
internet
View
107
Download
2
Embed Size (px)
Citation preview
5a. Aula
Franklina
Otimalidade e RelaxaçãoDado um Problema Inteiro ou Problema de
Otimização Combinatória
Uma solução com valor z* é ótima se existe um limitante inferior
zLB z*
e um limitante superior zUB z*
tal que zLB = z* = zUP.
n
T
Zx
Xxas
xcz
.
max
Na prática um algoritmo para o problema anterior é terminado quando existe uma seqüência decrescente de limitantes superiores e uma seqüência crescente de limitantes inferiores, tal que,
zUB – zLB
Limitante InferiorQualquer solução x´ X fornece um limitante
inferior para o problema1:zLB = z(x´) z*
Em geral, usam-se métodos heurísticos para obter um limitante inferior.
Obs. Existem problemas que é simples encontrar uma solução factível (mochila), no entanto, para alguns essa tarefa é árdua (dimensionamento de lotes).
1 – Lembre-se que estamos maximizando z.
Limitante SuperiorLimitantes superiores para problemas de
maximização são chamados de limitantes duais.
O enfoque de “relaxação” é o mais importante para determinar limitantes superiores. Um problema “relaxado” é um problema mais simples que o problema original de programação inteira, com valor ótimo maior ou igual a z*.
Duas possibilidades para o problema relaxado:
a) Aumentar o conjunto de soluções factíveis (ex. relaxação linear);
b) Substituir a função objetivo por uma função com valor maior ou igual para todas as soluções factíveis (ex. relaxação lagrangiana).
Definição 2.1. Um problema (PR) zR = max{f(x) | x T Rn}
é uma relaxação de (PI) z = max{c(x) | x X Zn}
se:(i) X T, e(ii) f(x) c(x) para todo x X.
Proposição 2.1. Se PR é uma relaxação de PI então zR z.
Demonstração. Se x* é uma solução ótima de PI, então x* X T e z = c(x*) f(x*). Como x* T, f(x*) é um limitante inferior de zR, e portanto,
z f(x*) zR.
Relaxação Linear - PLDefinição 2.2. Dado o problema inteiro
Max {cx | x P Zn }
com formulação
P = {x | Ax b}a relaxação por programação linear é o
problema linear zPL= max{cx | x P }.
nR
Exemplo relaxação Linear
Considere o problema inteiro:
z = max (4 x1 – x2)
s.a 7 x1 – 2 x2 14
x2 3
2 x1 – 2 x2 3
x
2Z
Exemplo relaxação Linear
(2,1) é uma solução factível, logo é um limitante inferior para o problema,
z 7.
A solução ótima do PL é x = (20/7, 3) com valor 59/7. Como a solução ótima é inteira, temos que
z 8.
Proposição 2.2. (Formulações Melhores) Considere P1, P2 duas formulações para o problema inteiro
Max {cx | x X Zn }
Sendo P1 uma formulação melhor que P2, isto é, P1 P2. Se
ziPL = Max {cx | x Pi }
para i = 1, 2 são valores ótimos das relaxações lineares, então
z1PL z2
PL
para todo c.
Proposição 2.3. (Prova de otimalidade) (i)Se a relaxação PR é infactível, o problema
original PI é infactível.(ii)Seja x* uma solução ótima de PR. Se x* X e
f(x*) = c(x*), então x* é uma solução ótima de PI.
Demonstração
(i) Como PR é infactível, T = e, portanto, X = .
(ii) Como x* X, z c(x*) = f(x*) = zR. Como z zR, então c(x*) = z = zR.
Relaxação Combinatorial
Esta relaxação está associada a um problema de otimização combinatória.
Problema do Caixeiro Viajante.
É dado um grafo orientado D = (V,A) com peso cij para cada arco (i,j) A. As soluções do PCV são tours ou ciclos Hamiltonianos, que são designações (assignments) ou permutações sem subtours.
ciclos Hamiltonianos – uma rota através dos vértices do grafo que inicie e termine em um mesmo nó sem nunca repetir uma visita.
1 2
3
4
1 2
3
4
1 2
3
4 Grafo original
Ciclos Halmiltonianos
Problema de designação:
1
2
3
4
A
B
C
D
Grafo original Ciclo Halmiltoniano
1
2
3
4
A
B
C
D
TjiijAT
ASS
TjiijAT
PCV
Tcz
Tcz
),(
),(
designação uma é |min
tourum é |min
Problema do Caixeiro Viajante Simétrico (PCVS)
É dado um grafo G = (V,A) com peso ci para cada aresta i A.
Note que: a) todo tour consiste de duas arestas adjacentes ao
nó 1, e um caminho através dos nós {2,3,...n};b) Um caminho é um caso especial de uma árvore.
Definição 2.3. Uma 1-árvore é um subgrafo que consiste de duas arestas adjacentes ao nó 1, e das arestas de uma árvore nos nós {2,...n}.
Problema do Caixeiro Viajante Simétrico (PCVS)
Cada tour é uma 1-árvore, e, portanto,
TeeAT
árvore
TeeAT
árvore1
TeeAT
PCVS
Tcz
Tcz
Tcz
árvore uma é |min
árvore-1 uma é |min
tourum é |min
Problema da Mochila
Uma relaxação do conjunto
n
1jjj
n bxaZxX |
É o conjunto
n
1jjj
n bxaZxX |
Onde a é o maior inteiro menor ou igual a a.
Relaxação LagrangianaDado um problema de programação inteira (PI)
Max {cx | Ax b, x X Zn }.
Se este problema for difícil de resolver, podemos relaxar as restrições Ax b, neste caso temos:
Max {cx | x X Zn }.
O problema de designação pode ser obtido ao relaxarmos as restrições de subtour do PCV.
Proposição 2.4. Dado o problema de programação inteira PI
Max {cx + u(b – Ax), x X}.Então z(u) z para todo u 0.
Prova. Seja x* solução ótima do PI. Como x* é factível em PI, x* X. Logo,
Ax* b
e, portanto, b – Ax* 0. Como u 0 temos
z = cx* cx* + u(b – Ax*) = z(u).
Exemplo
Problema de dimensionamento de lotes com capacidade limitada
Min cx + sy + hIs.a xit – Iit + Ii,t-1 = dit
i (bi xit + fi yit ) Ct
bi xit Ct yit
xit 0, yit {0,1}, Iit 0
Limitantes Primais: busca local e gulosos
Heurísticas gulosas (Greedy – “gananciosa”)
Idéia geral: construir uma solução a partir de um conjunto vazio, escolhendo a cada passo a melhor decisão naquele momento.
Exemplo. Problema da Mochila
Busca local
Passo 1. Seleção de uma solução inicial (S).Passo 2. Avalie se existe na vizinhança VV uma
solução S’ melhor que S.Passo 3. Se existe S’ então atualize S e volte ao
Passo 2.Passo 4. Fim.
Exemplo. Problema da mochila.