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

Exercício 2 - Entrega: 16 de outubro de 2002

Limitantes primais e limitantes duais

Considere o seguinte problema (já presente no exercício anterior).

• 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}$. Uma fazenda deve entregar toda sua produção para uma mesma usina¹. 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.

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

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 */