Exercício 10: Uma cidade executará quatro projetos de renovação habitacional urbana nos próximos cinco anos. Cada projeto será iniciado em um ano diferente e terá duração diferenciada.
Ano 1 Ano 2 Ano 3 Ano 4 Ano 5 Custo Total ($milhões)
Projeto 1 início fim 5
Projeto 2 início fim 8
Projeto 3 início fim 9
Projeto 4 início fim 4
Dentre o início e o fim, todos os projetos devem ser realizados na totalidade. A execução pode ser dividida entre os anos. Minimizar o maior valor gasto em um determinado ano.

Passo 1

O enunciado pede minimizar o maior valor gasto em um ano, dado que há quatro projetos com início e fim fixos e custos totais. Vou listar claramente o que foi dado e o que se pede.
Informações do enunciado (peguei todos estes dados da tabela):
  • Projetos e seus intervalos de execução (anos inclusivos) e custo total em milhões:
    • Projeto 1: início em 1, fim em 3, custo total 5.
    • Projeto 2: início em 2, fim em 5, custo total 8.
    • Projeto 3: início em 1, fim em 5, custo total 9.
    • Projeto 4: início em 3, fim em 4, custo total 4.
O que o problema pede:
  • Distribuir (possivelmente fracionando) a execução de cada projeto entre os anos em que ele pode ocorrer (entre início e fim, inclusive) de modo que cada projeto seja concluído (a soma dos gastos do projeto nos anos permitidos seja igual ao seu custo total).
  • Minimizar a maior despesa anual total entre os anos 1 a 5. Ou seja, se y_t for o gasto total no ano t, minimizar \max_{t=1,\dots,5} y_t.

Passo 2

Modelagem intuitiva e ideia de método (aula curta e didática).
  • Pensamento: cada projeto j tem um total de trabalho (ou custo) w_j que deve ser distribuído ao longo dos anos do seu intervalo [s_j,e_j]. Podemos dividir o custo de um projeto em pedaços fracionáveis entre os anos do intervalo. Em cada ano t haverá um limite superior M (o pico anual) que queremos minimizar, tal que a soma de todas as parcelas alocadas naquele ano seja ≤ M.
  • Forma matemática (sem entrar em notação pesada): definir x_{j,t}\ge0 como o gasto do projeto j no ano t. Condições:
    • \displaystyle \sum_{t=s_j}^{e_j} x_{j,t} = w_j para cada projeto j (soma dos gastos do projeto = custo total).
    • Para cada ano t: \displaystyle \sum_{j} x_{j,t} \le M.
    • Objetivo: minimizar M.
  • Observação didática: este é um problema linear (programação linear). Mas com poucas variáveis podemos raciocinar com limites óbvios (lower bounds) e construir uma alocação explícita que atinja o melhor limite. Isso é mais prático na prova sem computador.

Passo 3

Cálculo de um lower bound (limite inferior) para o pico M.
  • Soma total dos custos: \displaystyle 5 + 8 + 9 + 4 = 26 milhões.
  • 5 anos disponíveis. Mesmo que se distribua perfeitamente, a média por ano é \frac{26}{5} = 5,2.Portanto qualquer M viável deve satisfazer M \ge 5,2. Esse é um lower bound imediato (não dá para ter pico menor que a média).
  • Outro lower bound é o maior custo médio por projeto (custo dividido pelo número de anos em que o projeto pode ocorrer), mas aqui o maior desses é \max(5/3,\,8/4,\,9/5,\,4/2)=\max(1{,}666\ldots,2,1{,}8,2)=2, que é bem menor que 5,2. Assim o lower bound dominante é 5,2.
Conclusão desta etapa: a melhor possível é M_{\min}\ge 5,2. Agora vamos ver se M=5,2 é factível (se for, é ótimo).

Passo 4

Raciocínio sobre factibilidade de M=5,2.
  • Se tentarmos M=5,2, a capacidade total disponibilizada nos 5 anos é 5\cdot 5,2 = 26, exatamente igual à demanda total. Portanto, para M=5,2 ser viável precisamos usar toda essa capacidade (cada ano terá exatamente 5,2 de gasto).
  • Precisamos verificar se é possível distribuir os 26 milhões respeitando os intervalos de cada projeto e fazendo cada ano somar exatamente 5,2.
  • Uma maneira prática: construir explicitamente uma alocação x_{j,t} (mostro passo a passo uma alocação que funciona). Se encontrarmos uma, então M=5,2 é factível e, por ser igual ao lower bound, é ótimo.

Passo 5

Construção explícita da alocação (passo a passo, números simples).
Vou distribuir os gastos dos projetos pelos anos de forma a deixar cada ano com exatamente 5,2. A ideia é concentrar projetos que têm janelas curtas em anos diferentes para nivelar o total.
Escolhas (todas as quantias em milhões):
  • Projeto 1 ( w_1=5, anos 1 a 3): alocar quase todo em 1.
    • x_{1,1} = 5,\; x_{1,2}=0,\; x_{1,3}=0.
      (isso é permitido: um projeto pode ser concluído antes do seu ano de fim, desde que seja feito entre início e fim.)
  • Projeto 4 ( w_4=4, anos 3 a 4): alocar tudo no ano 4 para aliviar o ano 3.
    • x_{4,3}=0,\; x_{4,4}=4.
Agora vamos ajustar Projetos 2 e 3 e o que falta do Projeto 3 para preencher os anos restantes exatamente a 5,2.
  • Ano 1 já tem x_{1,1}=5. Para que ano 1 some 5,2, precisamos de 0,2 adicionais vindos do Projeto 3. Então:
    • x_{3,1}=0,2.
  • Olhe as equações ano a ano que ainda precisamos satisfazer (lembre: cada ano tem que somar 5,2):
    • Ano 2: x_{1,2}+x_{2,2}+x_{3,2} = 5,2. Como x_{1,2}=0, fica x_{2,2}+x_{3,2}=5,2.
    • Ano 3: x_{1,3}+x_{2,3}+x_{3,3}+x_{4,3} = 5,2. Com x_{1,3}=0 e x_{4,3}=0, fica x_{2,3}+x_{3,3}=5,2.
    • Ano 4: x_{2,4}+x_{3,4}+x_{4,4} = 5,2. Como x_{4,4}=4, fica x_{2,4}+x_{3,4}=1,2.
    • Ano 5: x_{2,5}+x_{3,5} = 5,2.
  • Também há as somas por projeto:
    • Projeto 2: x_{2,2}+x_{2,3}+x_{2,4}+x_{2,5} = 8.
    • Projeto 3: x_{3,1}+x_{3,2}+x_{3,3}+x_{3,4}+x_{3,5}=9. Já colocamos x_{3,1}=0,2, resta 8,8 para distribuir entre anos 2,3,4,5.
  • Observe que as três equações anuais para anos 2,3,5 são todas do tipo x_{2,t}+x_{3,t}=5,2. Se somarmos essas três equações, obtemos
    (x_{2,2}+x_{2,3}+x_{2,5}) + (x_{3,2}+x_{3,3}+x_{3,5}) = 3\cdot 5,2 = 15,6.
    Mas das somas por projeto sabemos que
    x_{2,2}+x_{2,3}+x_{2,4}+x_{2,5} = 8 \quad\Rightarrow\quad x_{2,2}+x_{2,3}+x_{2,5}=8-x_{2,4},
    e
    x_{3,2}+x_{3,3}+x_{3,4}+x_{3,5} = 9-x_{3,1}=8,8 \quad\Rightarrow\quad x_{3,2}+x_{3,3}+x_{3,5}=8,8-x_{3,4}.
    Somando essas duas linhas:
    (8-x_{2,4}) + (8,8-x_{3,4}) = 16,8 - (x_{2,4}+x_{3,4}).
    Para dar 15,6 (que é a soma necessária), precisamos de
    16,8 - (x_{2,4}+x_{3,4}) = 15,6 \quad\Rightarrow\quad x_{2,4}+x_{3,4}=1,2,
    que coincide com a equação do ano 4. Portanto o sistema é consistente e tem graus de liberdade: basta escolher x_{2,4} e x_{3,4} não-negativos com soma 1,2, e escolher x_{2,2},x_{2,3},x_{2,5} não-negativos somando 8-x_{2,4}; então x_{3,t}=5,2-x_{2,t} para t=2,3,5.
  • Para ser concreto e simples, escolho valores racionais iguais para distribuir o trabalho do Projeto 2 entre os anos 2,3,5 (lembrando que x_{2,4} foi escolhido abaixo):
    • Vamos tomar x_{2,4}=0,2 e, portanto, x_{3,4}=1,0 (pois precisam somar 1,2).
    • Então o total restante do Projeto 2 a distribuir entre anos 2,3,5 é 8-0,2=7,8. Divido igualmente: x_{2,2}=x_{2,3}=x_{2,5}=2,6.
    • Com isso, para cada ano t\in\{2,3,5\}, definimos x_{3,t}=5,2-x_{2,t}=5,2-2,6=2,6.
  • Resumo final da alocação (em milhões):
    • Projeto 1: x_{1,1}=5,\; x_{1,2}=0,\; x_{1,3}=0.
    • Projeto 2: x_{2,2}=2,6,\; x_{2,3}=2,6,\; x_{2,4}=0,2,\; x_{2,5}=2,6.
    • Projeto 3: x_{3,1}=0,2,\; x_{3,2}=2,6,\; x_{3,3}=2,6,\; x_{3,4}=1,0,\; x_{3,5}=2,6.
    • Projeto 4: x_{4,3}=0,\; x_{4,4}=4.

Passo 6

Verificação numérica (mostrando que cada ano fica com 5,2 e cada projeto soma seu total).
  • Ano 1: x_{1,1}+x_{3,1}=5 + 0,2 = 5,2.
  • Ano 2: x_{1,2}+x_{2,2}+x_{3,2}=0 + 2,6 + 2,6 = 5,2.
  • Ano 3: x_{1,3}+x_{2,3}+x_{3,3}+x_{4,3}=0 + 2,6 + 2,6 + 0 = 5,2.
  • Ano 4: x_{2,4}+x_{3,4}+x_{4,4}=0,2 + 1,0 + 4 = 5,2.
  • Ano 5: x_{2,5}+x_{3,5}=2,6 + 2,6 = 5,2.
Verificação por projeto:
  • Projeto 1: 5 + 0 + 0 = 5.
  • Projeto 2: 2,6 + 2,6 + 0,2 + 2,6 = 8.
  • Projeto 3: 0,2 + 2,6 + 2,6 + 1,0 + 2,6 = 9.
  • Projeto 4: 0 + 4 = 4.
Tudo confere: distribuição válida e em cada ano o gasto máximo é exatamente 5,2.

Passo 7

Interpretação final e conclusão didática.
  • Encontramos uma alocação factível com pico anual M=5,2 milhões, que coincide com o lower bound obtido pela média total.
  • Por isso M_{\min}=5,2 milhões de dólares por ano é o valor ótimo: não se pode ter pico menor que a média total, e conseguimos igualar o pico à média, então é ótimo.
  • Dica prática para prova: primeiro calcule a média total (soma dos custos dividida pelo número de anos) — isso dá um lower bound. Em seguida, tente construir uma alocação ou usar um argumento de capacidade por intervalos; com poucos projetos você costuma conseguir uma construção explícita como a acima. Se conseguir alcançar o lower bound, está ótimo. Se não, aumente o candidato M e verifique novamente (pode ser feito via max-flow/LP para casos maiores).

Resposta

\,5,2\\ \text{milhões de dólares por ano}õó

Exercícios relacionados