Neste trabalho você deverá modelar alguns problemas usando GMPL (GNU MathProg Language) e resolvê-los utilizando o GLPK (GNU Linear Programming Kit), um dos melhores resolvedores gratuitos de Programação Linear Inteira disponíveis atualmente.
Dica: Antes de tentar implementar os problemas do trabalho, verifique alguns exemplos e escreva as formulações para alguns problemas vistos em sala de aula (PAR, BKP, STJ, TSP, etc).
O trabalho deverá ser feito individualmente. Você deverá implementar dois dos três problemas apresentados abaixo (escolha livre). A resolução de cada problema escolhido valerá 50% da nota do trabalho.
A versão final do trabalho deverá ser entregue por e-mail para o docente (zanoni@ic.unicamp.br) até o dia 17/06/2012 às 23:59h. Como assunto/subject da mensagem você deverá usar “[MC548] Trabalho Prático (RAXXXXXX)” (sem aspas), onde XXXXXX é o seu RA (com 6 dígitos). Os alunos cujos trabalhos não forem recebidos pelo docente até o horário fixado acima receberão nota zero (T = 0).
Sua mensagem deverá conter um único anexo: RAXXXXXX.zip (onde XXXXXX foi especificado acima). Este arquivo deverá conter os modelos para os problemas e um relatório (e nada mais). Ao ser descompactado o arquivo não deverá criar nenhum diretório.
O relatório deverá ter no máximo 3 páginas por problema implementado, e deverá ser entregue em formato PDF. Este arquivo deverá ser nomeado como RAXXXXXX.pdf. Para elaboração do relatório use, preferencialmente, LaTeX. O relatório deverá conter as seguintes informações para cada um dos problemas propostos:
Lembre de colocar seu nome e RA em um cabeçalho na primeira página do relatório.
Note que todos os problemas deverão ser resolvidos de forma exata. Os modelos em GMPL corresponderão a 60% da nota e o texto corresponderá aos outros 40%. No texto será avaliado a corretude das formulações propostas, a apresentação e a organização. Não use código GMPL no relatório. Defina as variáveis, restrições e função objetivo em termos matemáticos.
O código GMPL deverá ser bem comentado, isto é, os seus comentários devem ser curtos e precisos. Seu código deverá conter um cabeçalho contendo seu nome completo e RA. A ausência ou imprecisão de comentários no código será penalizada. Um código GMPL que não encontre a resposta correta para todos os casos de testes ou imprima a saída fora da padronização pré-estabelecida será considerado não entregue.
Os arquivos com os modelos devem ser nomeados como RAXXXXXX-1.mod, RAXXXXXX-2.mod e RAXXXXXX-3.mod, correspondendo, respectivamente, aos problemas 1, 2 e 3 listados abaixo. Relembrando que você só deverá entregar dois modelos. Se três modelos forem entregues, serão considerados para nota apenas os dois piores avaliados.
Siga estas instruções com cuidado. Os programas serão avaliados em termos de corretude de forma automática. Se algum modelo não seguir as especificações, ele será considerado não entregue.
No relatório não será avaliada qualquer informação sobre problemas não entregues, ou seja, problemas considerados não entregues receberão nota zero.
A “300 Picaretas Sociedade Anônima” (300 S/A) é uma empresa que preza pelo sigilo e pela eficiência em consultoria parlamentar.
Ela foi contratado por um grupo de empresário do ramo da construção civil interessados em fundar um novo partido político. Para evitar a necessidade de eleger parlamentares, os empresários estão interessados em “contratar” parlamentares que estejam dispostos em integrar o novo partido, que será denominado de Partido Monetário Habitacional (PaMonHa).
A 300 S/A possui uma lista atualizada com o valor necessário para aliciar cada parlamentar para o novo partido (como sabemos, todo parlamentar pode ser contratado por algum valor). Alguns parlamentares mais influentes garantem, pelo valor contratado, que tanto ele quanto os parlamentares sob sua influência, mudem para o novo partido.
Por motivos éticos, alguns parlamentares não aceitarão mudar para o novo partido se o novo partido tiver como afiliado algum dos seus inimigos políticos. Os conflitos são mais fortes que as influências. Ou seja, um parlamentar, mesmo influenciado que por um colega que irá integrar o novo partido recusará o convite caso um dos seus inimigos políticos já tenha se filiado ao partido.
Em posse do custo de cada parlamentar, de todas as listas de influência, de todas as listas de conflitos entre parlamentares e do número mínimo de parlamentares desejados para a fundação do novo partido, a 300 S/A gostaria de minimizar o custo da operação (de modo a poder maximizar seu lucro na negociação com os empresários).
Calcule o valor mínimo da operação e a lista dos parlamentares que participarão do negócio.
Veja detalhes sobre a entrada e saída deste problema
O ano é 2222. A colonização espacial é uma realidade graças às viagens interplanetárias utilizando “dobras espaço-temporais”.
Você é o gerente de logística da LittleRocket, uma uma pequena empresa de transporte interplanetário. Seu principal (e unico clinte) é a rede de lojas de conveniências Expresso que possui franquias localizada nos principais espaçoportos da Galáxia, cuja matriz está localizada na Terra (assim como a sede da LittleRocket).
A Expresso lhe enviou a lista de demanda de cada uma das n filiais da Expresso (em quilogramas).
Apesar de rápidas e relativamente baratas as viagens espaciais são bastante restritas, devido à alta procura. Sua empresa acabou de receber o direito de fazer k (2 ≤ k ≤ n+1) viagens, o que permitirá visitar k-1 filiais da Expresso e retornar à Terra. Por questões contratuais, a LittleRocket é obrigada a visitar tantas filiais quanto o possível (guardando uma viagem para retornar a Terra).
Sua espaçonave partirá da Terra em alguns dias para reabastecer os estoques de k-1 lojas Expresso. Eventualmente nem todas as filiais poderão ser atendidas.
Algumas filiais desejam enviar estoques excedentes de alguns produtos para outras filiais da empresa. Você possui a lista de todos os pares de lojas (origem-destino) interessadas em remanejar mercadorias, assim como o peso destas mercadorias.
Analisando o problema, você percebeu que se a loja X deseja mandar mercadorias para a loja Y e você visitar a loja X antes da Y, poderá aproveitar a viagem para fazer o transporte. Sua nave não tem problema de capacidade de transporte (ela é muito maior do que a demanda da Expresso).
O custo das viagens interplaterárias é fixo, independente da distância ou peso da espaçonave. A LittleRocket cobra “s” stars (unidade monetária) para cada quilo de mercadoria transportada (independente do trajeto executado).
Sua missão é organizar o itinerário da nave da LittleRocket que sairá da Terra para visitar as filiais da Expresso de tal forma a maximizar o faturamento da LittleRocket.
Veja detalhes sobre a entrada e saída deste problema
Ali é um grande especialista em jóias. Ele e seus comparsas já roubaram joalherias e colecionadores em todos os continentes.
Além de planejar e efetuar os assaltos, Ali, como chefe do grupo, tem a função de dividir os resultados financeiros do trabalho entre seus n-1 comparsas, tarefa esta que por várias vez já causou muitos problemas, inclusive levando a baixas em seu grupo.
Um item coletado não pode ser dividido. Todos os assaltantes receberão jóias inteiras. Uma jóia perde muito do seu valor se for dividida (destruída). Todos os itens devem ser distribuídos entre os comparsas.
Dado um conjunto de m itens auferidos em um assalto com valores distintos associados a cada item, a missão de Ali é distribuir os itens entre os integrantes do grupo de tal forma que cada um dos seus associados receba um valor próximo do “valor justo”.
O valor justo é calculado pela soma dos valores dos itens dividido pelo número de assaltantes (n). Para cada serviço é estabelecido a priori uma taxa de tolerância X (em termos porcentuais) em relação ao “valor justo”.
Ali (denominado também de “número 1”) não precisa respeitar a tolerância de valor justo para a sua cota, o que pode fazer com que ele receba bem menos que os companheiros (mas mantenha a integridade do grupo) ou mesmo muito mais. Por exemplo, se um serviço for executado por Ali e mais 9 companheiros, com taxa de tolerância de 10%, cada comparsa deve receber de 9% a 11% do valor auferido. Em compensação, Ali pode receber de 1% (caso todos os outros recebam o valor máximo) até 19% (caso todos recebam o valor mínimo).
Ali, que de bobo não tem nada, deseja garantir que sua parte seja a maior possível, sem ferir a regra previamente estabelecida.
Os participantes de cada trabalho são numerados de acordo com a hierarquia no grupo (Ali é o número 1, o ladrão número 2 é o segundo na hieraquia e assim por diante). Sendo assim, ainda sem desrespeitar as regras de divisão dos lucros, Ali gostaria de garantir que o companheiro número 2 receba um valor maior ou igual do que o número3, que por sua vez deve receber um valor maior ou igual do que o número 4, e assim sucessivamente.
Veja detalhes sobre a entrada e saída deste problema