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.
| 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 |
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
, fim em , custo total . - Projeto 2: início em
, fim em , custo total . - Projeto 3: início em
, fim em , custo total . - Projeto 4: início em
, fim em , custo total .
- Projeto 1: início em
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
a . Ou seja, se for o gasto total no ano , minimizar .
Passo 2
Modelagem intuitiva e ideia de método (aula curta e didática).
- Pensamento: cada projeto
tem um total de trabalho (ou custo) que deve ser distribuído ao longo dos anos do seu intervalo . Podemos dividir o custo de um projeto em pedaços fracionáveis entre os anos do intervalo. Em cada ano haverá um limite superior (o pico anual) que queremos minimizar, tal que a soma de todas as parcelas alocadas naquele ano seja ≤ . - Forma matemática (sem entrar em notação pesada): definir
como o gasto do projeto no ano . Condições: -
para cada projeto (soma dos gastos do projeto = custo total). - Para cada ano
: . - Objetivo: minimizar
.
-
- 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
.
- Soma total dos custos:
milhões. - Há
anos disponíveis. Mesmo que se distribua perfeitamente, a média por ano é Portanto qualquer viável deve satisfazer . 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 é
, que é bem menor que . Assim o lower bound dominante é .
Conclusão desta etapa: a melhor possível é
. Agora vamos ver se
é factível (se for, é ótimo).
Passo 4
Raciocínio sobre factibilidade de
.
- Se tentarmos
, a capacidade total disponibilizada nos anos é , exatamente igual à demanda total. Portanto, para ser viável precisamos usar toda essa capacidade (cada ano terá exatamente de gasto). - Precisamos verificar se é possível distribuir os
milhões respeitando os intervalos de cada projeto e fazendo cada ano somar exatamente . - Uma maneira prática: construir explicitamente uma alocação
(mostro passo a passo uma alocação que funciona). Se encontrarmos uma, então é 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 . A ideia é concentrar projetos que têm janelas curtas em anos diferentes para nivelar o total.
Vou distribuir os gastos dos projetos pelos anos de forma a deixar cada ano com exatamente
Escolhas (todas as quantias em milhões):
- Projeto 1 (
, anos a ): alocar quase todo em . -
.
(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 (
, anos a ): alocar tudo no ano para aliviar o ano . -
.
-
Agora vamos ajustar Projetos 2 e 3 e o que falta do Projeto 3 para preencher os anos restantes exatamente a
.
-
Ano
já tem . Para que ano some , precisamos de adicionais vindos do Projeto . Então: -
.
-
-
Olhe as equações ano a ano que ainda precisamos satisfazer (lembre: cada ano tem que somar
): - Ano
: . Como , fica . - Ano
: . Com e , fica . - Ano
: . Como , fica . - Ano
: .
- Ano
-
Também há as somas por projeto:
- Projeto 2:
. - Projeto 3:
. Já colocamos , resta para distribuir entre anos .
- Projeto 2:
-
Observe que as três equações anuais para anos
são todas do tipo . Se somarmos essas três equações, obtemos Mas das somas por projeto sabemos queeSomando essas duas linhas:Para dar(que é a soma necessária), precisamos de que coincide com a equação do ano. Portanto o sistema é consistente e tem graus de liberdade: basta escolher e não-negativos com soma , e escolher não-negativos somando ; então para . -
Para ser concreto e simples, escolho valores racionais iguais para distribuir o trabalho do Projeto
entre os anos (lembrando que foi escolhido abaixo): - Vamos tomar
e, portanto, (pois precisam somar ). - Então o total restante do Projeto
a distribuir entre anos é . Divido igualmente: . - Com isso, para cada ano
, definimos .
- Vamos tomar
-
Resumo final da alocação (em milhões):
- Projeto 1:
. - Projeto 2:
. - Projeto 3:
. - Projeto 4:
.
- Projeto 1:
Passo 6
Verificação numérica (mostrando que cada ano fica com
e cada projeto soma seu total).
- Ano
: . - Ano
: . - Ano
: . - Ano
: . - Ano
: .
Verificação por projeto:
- Projeto
: . - Projeto
: . - Projeto
: . - Projeto
: .
Tudo confere: distribuição válida e em cada ano o gasto máximo é exatamente
.
Passo 7
Interpretação final e conclusão didática.
- Encontramos uma alocação factível com pico anual
milhões, que coincide com o lower bound obtido pela média total. - Por isso
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
e verifique novamente (pode ser feito via max-flow/LP para casos maiores).