Dois reservatórios de água abastecem três cidades. Cada reservatório pode abastecer até 50 milhões de litros de água por dia. Cada cidade necessita receber 40 milhões de litros de água por dia. Associado a cada milhão de litros de água não fornecido por dia existe uma multa. A multa na cidade 1 é de
20
$18
$ 23$. Os custos do transporte entre reservatórios e cidades é dado pelo quadro
Cidade 1
Cidade 2
Cidade 3
Reservatório 1
7
$8
$ 8$
Reservatório 2
9
$7
$ 8$
Determine, através do método de transporte, a quantidade de água a ser transferida para cada cidade minimizando os custos devidos ao transporte e à multa.
| Cidade 1 | Cidade 2 | Cidade 3 | |
| Reservatório 1 |
|
||
| Reservatório 2 |
|
Passo 1
O enunciado pede que determinemos as quantidades de água a serem transferidas de cada reservatório para cada cidade de modo a minimizar o custo total composto por: custo de transporte e multa por milhão de litros não fornecido. Informações dadas relevantes:
- Existem dois reservatórios, cada um com capacidade de até
milhões de litros por dia. - Cada cidade necessita
milhões de litros por dia; há três cidades, logo demandas: , e . - Multas por milhão de litros não fornecido por dia: Cidade 1 =
, Cidade 2 = , Cidade 3 = . - Custos de transporte (por milhão de litros) dados na tabela:
- Totais: oferta total
(milhões), demanda total (milhões). Há portanto milhões de litros que não podem ser atendidos e incorrerão em multa. - Objetivo: minimizar soma dos custos de transporte mais multas, respeitando capacidades e demandas (quando houver falta, pagar multa correspondente por milhão).
Passo 2
Modelagem como problema de transporte (transformação padrão para faltas): para transformar em um problema balanceado, adicionamos uma linha fictícia (chamarei de “Não fornecido” ou linha dummy) com oferta igual ao total da falta, isto é
milhões. A interpretação é: qualquer quantidade alocada dessa linha para uma cidade corresponde a litros não fornecidos àquela cidade — e o custo por unidade desta linha para cada cidade é a multa daquela cidade.
Montamos a tabela de custos com três linhas (Reservatório 1, Reservatório 2, Dummy) e três colunas (Cidade 1, Cidade 2, Cidade 3). Ofertas e demandas:
Matriz de custos (each entry em
por milhão):
Passo 3
Vamos obter uma solução básica inicial usando o método de Vogel (VAM) — é um bom ponto de partida porque costuma produzir soluções com baixo custo inicial. Lembrete didático sobre VAM: para cada linha e coluna calculamos a penalidade igual à diferença entre os dois menores custos daquela linha/coluna. Em seguida escolhemos a linha/coluna com maior penalidade e fazemos a alocação máxima possível na célula de menor custo dessa linha/coluna; atualizamos ofertas/demandas e repetimos até balancear tudo.
Primeira iteração — calculando penalidades:
- Linhas:
- R1: custos
⇒ menores e ⇒ penalidade . - R2: custos
⇒ menores e ⇒ penalidade . - D: custos
⇒ menores e ⇒ penalidade .
- R1: custos
- Colunas:
- C1: custos
⇒ menores e ⇒ penalidade . - C2: custos
⇒ menores e ⇒ penalidade . - C3: custos
⇒ menores e ⇒ penalidade .
- C1: custos
Maior penalidade é
(empate entre linha
e coluna
). Podemos escolher uma; escolhemos a coluna
. O menor custo em
é
na célula
. Demanda
, oferta
→ alocamos
de
para
.
Anotação de alocação:
.
Atualiza: oferta passa a
; demanda
fica
.
Atualiza: oferta
Passo 4
Segunda iteração do VAM — atualizar penalidades com a coluna
esgotada:
Custos restantes (colunas
).
- Linhas:
- R1: agora só
⇒ penalidade . - R2:
⇒ penalidade (menores e ). - D:
⇒ penalidade .
- R1: agora só
- Colunas:
- C2:
⇒ penalidade . - C3:
⇒ penalidade .
- C2:
Maior penalidade é
(linha
). Menor custo na linha
é
em
. Oferta
, demanda
→ alocamos
de
para
.
Anotação:
.
Atualiza: oferta passa a
(linha fictícia esgota), demanda
passa a
.
Atualiza: oferta
Passo 5
Terceira iteração do VAM — linhas/colunas restantes: R1 (oferta 10), R2 (oferta 50), colunas C2 (demanda 20), C3 (demanda 40). Penalidades:
- Linhas:
- R1:
⇒ penalidade . - R2:
⇒ menores ⇒ penalidade .
- R1:
- Colunas:
- C2:
⇒ penalidade . - C3:
⇒ penalidade .
- C2:
Maior penalidade
(pode escolher R2 ou C2). Escolhemos a linha
. Menor custo em
é
na célula
. Oferta
, demanda
→ alocamos
de
para
.
Anotação:
.
Atualiza: oferta passa a
; demanda
fica
.
Atualiza: oferta
Passo 6
Quarta e última iteração do VAM — sobra somente a coluna
com demanda
e ofertas
,
. Alocamos nas células de menor custo possível, mas há só C3 restante:
- Alocação
(esgota ), custo por unidade. - Alocação
(esgota ), custo .
Agora todas ofertas e demandas estão balanceadas. Resumo das alocações iniciais (VAM):
Passo 7
Calculamos o custo total da solução inicial (verificação numérica):
-
. -
. -
. -
. -
(esta é a multa por não fornecimento).
Somando:
Portanto custo total inicial =
.
Passo 8
Agora verificamos otimalidade e, se necessário, melhoramos via método MODI (potenciais
e
). Regra: para cada célula básica devemos ter
. Escolhemos arbitrariamente
e determinamos os demais
's e
's pelas células básicas.
Células básicas são as alocações não nulas (temos
básicas):
.
Começando com
:
- Para
: ⇒ . - Para
: ⇒ . - Para
: ⇒ com ⇒ . - Para
: ⇒ . - Para
: ⇒ com ⇒ .
Resumo dos potenciais:
Passo 9
Calculamos os custos reduzidos (também chamados de avaliações) para todas as células não básicas. Fórmula:
. Para minimização, a solução é ótima se todas as
. Vamos calcular:
- Célula
: . . . - Célula
: . . . - Célula
: . . . - Célula
: . . .
Todas as
calculadas são positivas (
). Como não existe nenhuma
, a solução atual é ótima para o problema de minimização.
Interpretação didática:
significa que inserir fluxo adicional pela célula não-básica aumentaria o custo total; logo não vale a pena. Como todas são não-negativas, não há ciclo de melhora e a solução é ótima.
Passo 10
Interpretação final prática (o que isso significa para as cidades):
- A linha dummy tinha alocado
milhões para a Cidade 2, isto é, a Cidade 2 ficará com milhões de litros por dia a menos do que sua demanda de , e por isso pagamos a multa correspondente por esses milhões. - Todas as outras demandas são atendidas por combinações dos dois reservatórios conforme a solução ótima.
Resposta
Reservatório 1 → Cidade 1:
milhões de litros/dia
Reservatório 1 → Cidade 2: milhões de litros/dia
Reservatório 1 → Cidade 3: milhões de litros/dia
Reservatório 2 → Cidade 1: milhões de litros/dia
Reservatório 2 → Cidade 2: milhões de litros/dia
Reservatório 2 → Cidade 3: milhões de litros/dia
Não fornecido (multa) → Cidade 2: milhões de litros/dia
Custo total mínimo:
Reservatório 1 → Cidade 2:
Reservatório 1 → Cidade 3:
Reservatório 2 → Cidade 1:
Reservatório 2 → Cidade 2:
Reservatório 2 → Cidade 3:
Não fornecido (multa) → Cidade 2:
Custo total mínimo: