Neste trabalho você deverá modelar alguns problemas usando Programação Linear Inteira (PLI) e resolvê-los utilizando o Xpress, um dos melhores resolvedores comerciais de programação matemática disponíveis no mercado atualmente. Para poder ter acesso à uma versão estudantil do software, compatível apenas com sistema operacional Windows, siga os seguintes passos:
Acesse o site www.dashoptimization.com, entre no menu Users e escolha Academics e então Free Student Edition.
Siga as instruções para baixar e instalar esta versão gratuita do resolvedor de programação linear na sua máquina.
Leia o manual Xpress-MP Essentials dando atenção especial para os capítulos Xpress-IVE, Modeling with Xpress-MP e Further Mosel Topics.
O manual citado no item acima mais os exemplos do item seguinte devem ser suficientes para você conseguir fazer o trabalho. Contudo, considere a possibilidade de ler também algumas partes do manual Xpress-Mosel User’s Guide.
Execute os exemplos com modelos PLI para os problemas do “Conjunto Independente Máximo” (IS), da “Cobertura por Vétices Mínima” (CV), da “Clique Máxima” e da “Colocaração Mínima” usando como entrada os arquivos de testes (XX.dat) localizados neste mesmo diretório. Veja com cuidado os códigos destes exemplos. Note que para executar uma instância cujos dados estão num arquivo “exemplo.dat”, você deve passar este mesmo nome como resposta da pergunta feita pelo programa. Este mecanismo de entrada do nome do arquivo contendo os dados da instância a ser resolvida deverá ser implementado nos programas feitos neste trabalho.
Dica: Antes de tentar implementar os problemas do trabalho, escreva em Mosel as formulações para alguns problemas conhecidos, como, por exemplo, o “Conjunto Dominante Mínimo” (DS), o “Problema do Caixeiro Viajante” (TSP) e o “Problema da Partição” (PAR).
O trabalho deverá ser feito individualmente ou em duplas. Caso seja feito individualmente, a avaliação considerará a nota dos quatro melhores problemas entregues. Em caso de duplas, todos os problemas deverão ser resolvidos.
Abaixo estão enunciados os problemas que fazem parte do trabalho. Para modelá-los, utilize a linguagem Mosel do Xpress. Os seus códigos devem ser testados com a versão gratuita do Xpress-MP disponível no site da Dash Optimization conforme discutido acima. A versão final do trabalho deverá ser entregue por e-mail para o docente (zanoni@ic.unicamp.br) até o dia 13/06/2006 às 23:59h. Como subject da mensagem coloque “Trabalho de MC548: raXXXXXX/raYYYYYY”, onde raXXXXXX e raYYYYYY são os RA’s dos integrantes do grupo e XXXXXX é numericamente menor que YYYYYY (se só houver um, omita o segundo RA do subject da mensagem). 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 deve conter os modelos (código Mosel) para os problemas e um relatório. O nome do arquivo correspondente ao i-ésimo problema deverá ter a forma raXXXXXX-i.mos. Por exemplo, a formulação do problema 3 para a dupla de alunos com RA’s 234567 e 123456 deverá estar no arquivo ra123456-3.mos (incluso no arquivo ra123456.zip).
No anexo da mensagem deverá ser incluído ainda um relatório de no mínimo 4 e no máximo 10 páginas, em formato PDF. Este arquivo deve ser nomeado como ra123456.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:
Coloque o nome e o RA de todos integrantes do grupo em um cabeçalho na primeira página do relatório. Note que todos os problemas deverão ser resolvidos de forma inteira (restrições is_binary, is_integer sobre variáveis mpvar). Os códigos Mosel corresponderão a 50% da nota e o texto corresponderá aos outros 50%. No texto será avaliado a corretude das formulações propostas, a apresentação e a organização. Não use código Mosel no relatório. Defina as variáveis, restrições e função objetivo em termos matemáticos.
O código Mosel deverá ser bem comentado, isto é, os seus comentários devem ser curtos e precisos. A ausência ou imprecisão de comentários no código será penalizada. Um código Mosel que capote ou imprima a saída fora da padronização pré-estabelecida 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 nota do trabalho será proporcional ao número de problemas entregues. Por exemplo, suponha uma dupla que tentou resolveu 4 problemas, sendo que 1 deles foi considerado não entregue por não respeitar a formatação de saída, sua nota máxima então será 6.0, caso receba nota total em todos os critérios de avaliação.
A “300 Picaretas Sociedade Anônima” é uma empresa que preza pelo sigilo e pela eficiência em consultoria parlamentar.
Entre seus serviços mais populares está o de compra de votações em diversas instâncias do Congresso Nacional.
O serviço é simples: após ser contactada por um cliente, a “300 Picaretas S/A” faz o levantamento de quanto custa o voto de cada parlamentar para a causa em questão. Alguns parlamentares mais influentes garantem, pela quantia combinada, o seu voto e de outros sob sua influência.
Em posse do custo de cada parlamentar, de todas as listas de influência e do número mínimo de votos necessário para garantir o sucesso do cliente na votação, a empresa gostaria de minimizar o custo da operação (de modo a poder maximizar seu lucro na negociação com o cliente).
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 Expresso, uma rede de lojas de conveniências localizada nos principais espaçoportos da Galáxia.
Sua espaçonave partirá da Terra em alguns dias para reabastecer os estoques de n-1 lojas Expresso.
Apesar de rápidas e relativamente baratas as viagens espaciais são bastante restritas, devido à alta procura. Toda viagem tem um custo distinto e cada empresa tem um número limitado de autorizações de viagens por mês. Sua empresa acabou de receber o direito de fazer n viagens, o que permitirá visitar todas as filiais e retornar à Terra.
Algumas filiais desejam enviar estoques excedentes de alguns produtos para outras filiais da empresa. Estes excedentes são sempre menores do que a quantidade de produtos que a filial receberá da matriz.
Você possui a lista de todos os pares de lojas (origem-destino) interessadas em remanejar mercadorias e os custo dos transportes entre estas filiais. A princípio estes transportes extras serão realizados por empresas terceirizadas.
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 economizar totalmente o custo de transporte de mercadorias entre estas duas lojas.
Sua missão é organizar o itinerário da nave da Expresso que sairá da Terra para visitar as filiais de tal forma a minimizar o custo desta viagem mais o custo dos transportes extras de mercadorias entre as filiais que ainda serão necessários.
Veja detalhes sobre a entrada e saída deste problema
A cadeia de fastfood Mc Fireball, especializada em espetinhos de animais de pequeno porte, acabou de desembarcar no Brasil.
A empresa pretende estabelecer suas primeiras franquias no país, onde, após um levantamento de mercado inicial, recebeu n propostas de possíveis franquias.
Cada proposta inclui o lucro anual obtido por cada franquia e a distância mínima necessária para qualquer outra franquia da rede para permitir que o negócio obtenha o sucesso desejado. Adicionalmente foi calculada a distância entre todos os pares de pontos de franquias candidatas.
Deseja-se saber qual o lucro máximo que pode ser obtido, por ano, pela operação da Mc Fireball e quais propostas de franquias devem ser aprovadas para se alcançar o objetivo da empresa.
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 muita confusão, 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 da quadrilha de tal forma que ninguém receba um valor mais do que X% distante do “valor justo”. Note que eventualmente não existirá uma forma de garantir esta restrição, logo o problema não terá uma solução ótima válida.
O valor justo é calculado pela soma dos valores dos itens dividido pelo número de assaltantes (n).
Ali (denominado também de “número 1”) que não é bobo nem nada, deseja garantir que sua parte seja a maior de todas, sem ferir a regra previamente estabelecida. O valor da margem de erro X é estabelecido a priori, serviço a serviço.
Veja detalhes sobre a entrada e saída deste problema
A empresa Petrolívia, “Petróleo e Gás Bolivia S/A” (antigamente conhecida como Petrobrás), é uma multinacional com 51% de capital boliviano e 49% brasileiro.
A divisão de combustíveis líquidos da empresa distribui k tipos diferentes de combustíveis, cada um com um lucro específico por litro.
Para transporte do combustível, a empresa conta com uma frota um tanto quanto sucateada, formada por m caminhões-tanque de marcas, modelos, anos e capacidades de transporte distintos.
A utilização de um caminhão implica num custo fixo diário, que é específico para cada caminhão.
A empresa atualmente possui n clientes com demandas diárias próprias para cada tipo de combustível. A demanda para cada tipo de combustível é especificada por um número inteiro não negativo de litros.
Um caminhão pode atender mais de um cliente, mas obviamente só pode transportar um tipo de combustível de cada vez, caso contrário estaria configurado crime de adulteração. Por questões de segurança, um caminhão não deve ser carregado com quantidade maior de combustível do que o necessário para atender os clientes.
A Petrolívia pode, por contrato, para cada tipo de combustível solicitado por cada um dos cliente, decidir entre não entregar nada ou entregar exatamente a quantidade solicitada (eventualmente utilizando mais de um caminhão). Por exemplo, se um cliente solicitar 1000 litros do combustível A, 2000 do B e 2500 do C, a Petrolívia pode decidir entregar apenas os combustíveis A e C, mas neste caso terá que fornecer exatamente a quantidade solicitada (1000 e 2500 litros).
O custo de transporte é desprezível e todo caminhão, por questões operacionais, pode ser abastecido no máximo uma vez por dia.
Maximize o lucro da operação, considerando os dados para um dia específico, decidindo que caminhões utilizar, quanto e qual combustível transportar em cada caminhão e quanto da demanda de cada cliente atender em cada caminhão.
Veja detalhes sobre a entrada e saída deste problema