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 ; na cidade 2 é deé$18 ; na cidade 3 é deé$ 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.

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é \,50 milhões de litros por dia.
  • Cada cidade necessita \,40 milhões de litros por dia; há três cidades, logo demandas: \,40, \,40 e \,40.
  • Multas por milhão de litros não fornecido por dia: Cidade 1 = \$\,20, Cidade 2 = \$\,18, Cidade 3 = \$\,23.
  • Custos de transporte (por milhão de litros) dados na tabela:
\begin{array}{c|ccc} & \text{Cidade 1} & \text{Cidade 2} & \text{Cidade 3}\\hline \text{Reservatório 1} & \$\,7 & \$\,8 & \$\,8\\\ \text{Reservatório 2} & \$\,9 & \$\,7 & \$\,8 \end{array}óó
  • Totais: oferta total \,50+50=100 (milhões), demanda total \,40+40+40=120 (milhões). Há portanto \,20 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 é \,20 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:
\text{Ofertas: }(50,\;50,\;20),\qquad \text{Demandas: }(40,\;40,\;40).
Matriz de custos (each entry em \$ por milhão):
\begin{array}{c|ccc} & C1 & C2 & C3\\hline R1 & 7 & 8 & 8\\\ R2 & 9 & 7 & 8\\\ D & 20 & 18 & 23 \end{array}

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 (7,8,8) ⇒ menores 7 e 8 ⇒ penalidade 7\!-\!8 = 1.
    • R2: custos (9,7,8) ⇒ menores 7 e 8 ⇒ penalidade 1.
    • D: custos (20,18,23) ⇒ menores 18 e 20 ⇒ penalidade 2.
  • Colunas:
    • C1: custos (7,9,20) ⇒ menores 7 e 9 ⇒ penalidade 2.
    • C2: custos (8,7,18) ⇒ menores 7 e 8 ⇒ penalidade 1.
    • C3: custos (8,8,23) ⇒ menores 8 e 8 ⇒ penalidade 0.
Maior penalidade é 2 (empate entre linha D e coluna C1). Podemos escolher uma; escolhemos a coluna C1. O menor custo em C1 é \$\,7 na célula (R1,C1). Demanda C1=40, oferta R1=50 → alocamos \,40 de R1 para C1.
Anotação de alocação: \,x_{R1,C1}=40.
Atualiza: oferta R1 passa a 50-40=10; demanda C1 fica 0.

Passo 4

Segunda iteração do VAM — atualizar penalidades com a coluna C1 esgotada:
Custos restantes (colunas C2,C3).
  • Linhas:
    • R1: agora só (8,8) ⇒ penalidade 0.
    • R2: (9,7,8) ⇒ penalidade 1 (menores 7 e 8).
    • D: (20,18,23) ⇒ penalidade 2.
  • Colunas:
    • C2: (8,7,18) ⇒ penalidade 1.
    • C3: (8,8,23) ⇒ penalidade 0.
Maior penalidade é 2 (linha D). Menor custo na linha D é \$\,18 em (D,C2). Oferta D=20, demanda C2=40 → alocamos \,20 de D para C2.
Anotação: \,x_{D,C2}=20.
Atualiza: oferta D passa a 0 (linha fictícia esgota), demanda C2 passa a 40-20=20.

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: (8,8) ⇒ penalidade 0.
    • R2: (9,7,8) ⇒ menores 7,8 ⇒ penalidade 1.
  • Colunas:
    • C2: (8,7) ⇒ penalidade 1.
    • C3: (8,8) ⇒ penalidade 0.
Maior penalidade 1 (pode escolher R2 ou C2). Escolhemos a linha R2. Menor custo em R2 é \$\,7 na célula (R2,C2). Oferta R2=50, demanda C2=20 → alocamos \,20 de R2 para C2.
Anotação: \,x_{R2,C2}=20.
Atualiza: oferta R2 passa a 50-20=30; demanda C2 fica 0.

Passo 6

Quarta e última iteração do VAM — sobra somente a coluna C3 com demanda 40 e ofertas R1=10, R2=30. Alocamos nas células de menor custo possível, mas há só C3 restante:
  • Alocação \,x_{R1,C3}=10 (esgota R1), custo \$\,8 por unidade.
  • Alocação \,x_{R2,C3}=30 (esgota R2), custo \$\,8.
Agora todas ofertas e demandas estão balanceadas. Resumo das alocações iniciais (VAM):
\begin{aligned} x_{R1,C1}&=40, & x_{R1,C2}&=0, & x_{R1,C3}&=10,\\\ x_{R2,C1}&=0, & x_{R2,C2}&=20, & x_{R2,C3}&=30,\\\ x_{D,C1}&=0, & x_{D,C2}&=20, & x_{D,C3}&=0. \end{aligned}

Passo 7

Calculamos o custo total da solução inicial (verificação numérica):
  • R1\to C1:\;40\times\$7=\$280.
  • R1\to C3:\;10\times\$8=\$80.
  • R2\to C2:\;20\times\$7=\$140.
  • R2\to C3:\;30\times\$8=\$240.
  • D\to C2:\;20\times\$18=\$360 (esta é a multa por não fornecimento).
Somando:
\$280+\$80+\$140+\$240+\$360 = \$1100.
Portanto custo total inicial = \$\,1100.

Passo 8

Agora verificamos otimalidade e, se necessário, melhoramos via método MODI (potenciais u_i e v_j). Regra: para cada célula básica devemos ter c_{ij}=u_i+v_j. Escolhemos arbitrariamente u_{R1}=0 e determinamos os demais u's e v's pelas células básicas.
Células básicas são as alocações não nulas (temos m+n-1=5 básicas): (R1,C1),(R1,C3),(R2,C2),(R2,C3),(D,C2).
Começando com u_{R1}=0:
  • Para (R1,C1): 7 = u_{R1}+v_{C1} v_{C1}=7.
  • Para (R1,C3): 8 = u_{R1}+v_{C3} v_{C3}=8.
  • Para (R2,C3): 8 = u_{R2}+v_{C3} ⇒ com v_{C3}=8 u_{R2}=0.
  • Para (R2,C2): 7 = u_{R2}+v_{C2} v_{C2}=7.
  • Para (D,C2): 18 = u_{D}+v_{C2} ⇒ com v_{C2}=7 u_{D}=11.
Resumo dos potenciais:
u_{R1}=0,\quad u_{R2}=0,\quad u_{D}=11;\qquad v_{C1}=7,\quad v_{C2}=7,\quad v_{C3}=8.

Passo 9

Calculamos os custos reduzidos (também chamados de avaliações) para todas as células não básicas. Fórmula: \Delta_{ij}=c_{ij}-(u_i+v_j). Para minimização, a solução é ótima se todas as \Delta_{ij}\ge 0. Vamos calcular:
  • Célula (R2,C1): c=9. u_{R2}+v_{C1}=0+7=7. \Delta=9-7=2.
  • Célula (D,C1): c=20. u_D+v_{C1}=11+7=18. \Delta=20-18=2.
  • Célula (D,C3): c=23. u_D+v_{C3}=11+8=19. \Delta=23-19=4.
  • Célula (R1,C2): c=8. u_{R1}+v_{C2}=0+7=7. \Delta=8-7=1.
Todas as \Delta_{ij} calculadas são positivas ( \,2,2,4,1). Como não existe nenhuma \Delta_{ij}<0, a solução atual é ótima para o problema de minimização.
Interpretação didática: \Delta_{ij}>0 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 \,20 milhões para a Cidade 2, isto é, a Cidade 2 ficará com \,20 milhões de litros por dia a menos do que sua demanda de \,40, e por isso pagamos a multa correspondente por esses \,20 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: 40 milhões de litros/dia
Reservatório 1 → Cidade 2: 0 milhões de litros/dia
Reservatório 1 → Cidade 3: 10 milhões de litros/dia
Reservatório 2 → Cidade 1: 0 milhões de litros/dia
Reservatório 2 → Cidade 2: 20 milhões de litros/dia
Reservatório 2 → Cidade 3: 30 milhões de litros/dia
Não fornecido (multa) → Cidade 2: 20 milhões de litros/dia
Custo total mínimo: \$\,1100

Exercícios relacionados