MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 330 - Programação Inteira - MAC 5780

Segundo semestre de 2002

Lista de Exercício 4

1. Considere uma instância do problema da localização de armazéns com $6$ clientes, $5$ possíveis armazéns, custos fixos $f=(4,8,11,7,5)$ e custos de transporte dados por
   
   $$c_{ij} = \left( \begin{array}{ccccc} 6 & 2 & 1 & 3 & 5 \\ 4 ... ...\ 1 & 8 & 6 & 2 & 5 \\ 3 & 2 & 4 & 8 & 1 \end{array}\right)$$
   
   
   Usando o vetor de penalidades $u = (5, 6, 3, 2, 6, 4)$ resolva a relaxação de Lagrange PI($u$), obtendo um limitante dual. Encontre um limitante primal para o problema.

2. Resolva o problema do caixeiro viajante, com a matriz de distâncias abaixo como feito em sala de aula, usando relaxação de Lagrange.
   
   $$c_e = \left( \begin{array}{cccccc} -- & 8 & 2 & 14 & 26 & 1... ...& -- & 12 & 6 \\ -- & --& --& -- & -- & 5 \end{array}\right)$$
   
   

3. Mostre como reformular o problema do caixeiro viajante para resolvê-lo usando a estratégia de geração de colunas.

4. Considere uma heurística gulosa para o problema da cana de açúcar. Teste sua heurística com diferentes ordens para considerar as fazendas: crescente, decrescente e aleatória.

5. Implemente uma heurística de busca local para o problema da cana de açúcar e teste com as soluções iniciais obtidas no exercício anterior.