1. Considere o seguinte problema: Um fabricante de computadores prevê a demanda nos próximos n meses como sendo d₁,    d2, ... ,    d_n. Em qualquer mês ele é capaz de produzir r unidades utilizando sua produção normal onde o custo por unidade é R$ b. Usando hora extra ele produz unidades adicionais a um custo de R$ c por unidade, onde c>b. A firma pode estocar unidades de um mês para o outro a um custo de de R$ s por unidade por mês. Encontre o número de unidades a serem produzidas por mês que minimiza o custo de produção (e atende a todas as demandas, é claro).
   1. Proponha uma representação para as soluoedo problema acima. Como você calcula o valor da função objetivo ?
   2. Proponha um método para a construção de uma solução(viável).
   3. Discuta as intuioeem que se baseia o seu método. Como, no seu entender, seria um algoritmo guloso para este problema ?
   4. Discuta a qualidade da solução gerada por seu método. Existe garantia de qualidade ?
   5. Defina uma vizinhança para as soluoedeste problema.
   6. (Cultura) Que método resolve este problema exatamente ?
   Uma instância exemplo deste problema é: n = 10, d = { 150, 250, 600, 600, 450, 200, 100, 300, 600, 350 }, r = 300, b = 1500, c = 2250, s = 85.
   
   
2. Considere o problema K-color(K-coloração de grafos): Dado um grafo G=(N,E) e um inteiro K encontre uma atribuição de até K cores aos nós do grafo que minimize o número de conflitos (i.e. o número de arestas em E que possuem nas suas extremidades vértices com cores iguais). Considere também a vizinhança de uma solução como sendo as soluoeobtidas pela troca da cor de um único vértice.
   1. Descreva a representação de uma solução e mostre que se o número de conflitos é maior que zero não existe ótimo local em que menos de K cores são utilizadas na atribuição correspondente.
   2. Encontre um ótimo local que não seja ótimo global, i.e. uma instância de K-color e uma solução(um grafo e uma atribuição de côres aos vértices) cujos vizinhos tenham pelo menos tantos conflitos quanto a solução dada e exista uma solução com menos conflitos. Esta instância deve ser o menor possível.
   3. Proponha para este problema uma heurística equivalente à de Lin e Kernighan para o Problema do Caixeiro Viajante (TSP). Em que difere a otimalidade local neste algoritmo da descrita no enunciado desta questão ?
   4. Encontre uma instância em que o algoritmo que você descreveu no item anterior não encontre a solução ótima (você pode escolher a solução inicial de todas as iteraoee basta uma iteração).
   
   
3. Considere o problema CVRP(Roteamento de veículos com restrioede capacidade): Dados um depósito, n pontos de coleta, as respectivas quantidades q₁ , q₂ , ... , q_n a serem coletadas nestes pontos, a capacidade C dos veículos, e as distâncias entre os pontos de coleta e entre estes e o depósito; determine as rotas a serem efetuadas pelos veículos que minimize a distância total percorrida.
   1. Descreva uma família de instâncias onde é trivial encontrar a solução ótima (e provar que é ótima).
   2. Proponha um método para construção de uma solução (viável). Descreva sua intuição.
   3. Descreva uma forma de randomização para o seu método. Qual o objetivo da sua proposta.
   4. Proponha uma metaeurística para este problema. (Defina todos seus ``ingredientes'' e a forma como o controle é efetuado).
   5. Proponha uma instância (pequena) e experimente o seu método (este exemplo deve ser não-trivial, i.e. dever ser possível mostrar que o seu método é melhor que uma simples construção de solução viável).

This document was translated from L^AT_EX by H^EV^EA.