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 1 - Entrega: 11 de setembro de 2002

Modelagem

Escreva modelos matemáticos baseados em programação inteira (ou outros modelos) para os seguintes problemas. Estes modelos serão usados nos próximos exercícios do semestre.

• 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}$. 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.

• Postos de observação
  Uma galeria de arte está enfrentando um sério problema financeiro e precisa cortar o número de funcionários contratados para fazer a segurança de suas salas. Esta galeria tem $n$ salas. Para cada uma de suas salas foram verificadas quais outras salas poderiam ser fiscalizadas a partir da primeira. De posse de todas estes dados, o objetivo é encontrar o menor número possível de guardas que podem tomar conta de todas as salas da galeria.

• O problema dos 7 pesos
  Em uma viagem à Amazonia foi descoberta uma tribo de índios com um estranho ritual. Neste, cada membro da tribo (com idade maior ou igual a um ano) deveria trazer para a festa uma quantidade de milho proporcional à sua idade. As ofertas eram medidas usando 7 pesos rituais, porém em cada medição no máximo três deles poderiam ser usados (não necessariamente do mesmo lado da balança). Uma lenda da tribo diz que se alguém vivesse tanto que fosse impossível medir sua contribuição usando os pesos rituais, os deuses se irritariam e as colheitas de milho seriam escassas para sempre. Coincidentemente, semanas antes da festa desse ano o mais velho da tribo morreu, para grande alívio do cacique e todos na tribo. Determine quais são os sete pesos rituais e qual a idade crítica que o ancião havia atingido.