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

\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  Exercício 2 -- Entrega: {\bf 16 de outubro de 2002}}

\vspace{0.3cm}
Limitantes primais e limitantes duais
\end{center}

\noindent
Considere o seguinte problema (já presente no exercício anterior). 
\begin{itemize}
\item \textbf{Produção de álcool } \\
Uma das principais atividades agrícolas do interior de São Paulo durante a
década de 80 foi a produção de álcool de cana de açúcar. Vários usineiros e
fazendeiros uniram-se em esquema de cooperativa, com vistas a baratear o custo
total da produção. Uma cooperativa reúne $n$ fazendas e $m$ usinas de cana. 
Cada fazenda de cana $i=1,\dots,n$ produz uma quantidade $f_i$ de 
toneladas de cana, e uma usina $k=1,\dots,m$ é capaz de processar $F_k$
toneladas do produto. São também dadas as distâncias entre as fazendas e
usinas através de uma matriz $d_{ij}$. \textbf{Uma fazenda deve entregar toda
sua produção para uma mesma usina\footnote{Isso não estava muito claro no
exercício anterior}.}
O custo que desejamos minimizar é proporcional à
distância que separa a fazenda da usina onde sua produção será processada e ao
número de caminhões necessários para transportar sua produção (cada caminhão
pode transportar $C$ toneladas do produto). O objetivo é
encontrar uma distribuição das fazendas às usinas que minimize o custo total
da cooperativa.     
\end{itemize}
O objetivo deste exercício é obter limitantes primais (soluções viáveis) e
duais (vindos de relaxações) para instâncias deste problema. As instâncias têm o
formato abaixo e estão disponíveis em
\texttt{http://www.ime.usp.br/$\sim$cef/mac330/ep2/exemplos/}. 
Você pode fazer programas para calcular estes limitantes ou
mesmo usar pacotes que você conheça. Faça um relatório com seus resultados.
\begin{verbatim}
n             /* número de fazendas */
m             /* número de usinas   */
f1 f2 ... fn  /* produção de cada fazenda */
F1 F2 ... Fm  /* capacidade de cada usina */
C             /* capacidade de um caminhão */
d11           /* distância entre fazenda 1 à usina 1 */
...
d1m           /* distância entre fazenda 1 à usina m */
d21
...
dn1
...
dnm           /* e assim por diante até a dist entre a fazenda n e usina m */
\end{verbatim}

\end{document}
