\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\usepackage{epsf}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 330 - Programação Inteira - MAC 5780 }
\end{center}

\begin{center}
{\bf Segundo semestre de 2002}
\end{center}

\begin{center}
{\large  Lista de Exercício 4}

\vspace{0.3cm}
\end{center}

\begin{enumerate}

\item 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 &10 & 2 & 6 & 1 \\
3 & 2 & 4 & 1 & 3 \\
2 & 0 & 4 & 1 & 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. 

\item 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 & 13 \\
-- & --& 7 & 4  & 16 & 8 \\
-- & --& --& 23 & 14 & 9 \\
-- & --& --& -- & 12 & 6 \\
-- & --& --& -- & -- & 5 
\end{array}
\right)
\]
\item Mostre como reformular o problema do caixeiro viajante para resolvê-lo
usando a estratégia de geração de colunas. 

\item 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. 

\item 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. 

\end{enumerate}

\end{document}

