Uma companhia locadora de automóveis se defronta com um problema de alocação resultante dos contratos de locação que permitem que os automóveis sejam devolvidos em localidades outras que aquelas onde foram originalmente alugados. Atualmente há 2 agências de locação com, respectivamente, 15 e 13 carros excedentes e 4 outras agências necessitando de 9 , 6, 7 e 9 carros, respectivamente. Os custos unitários de transporte entre as locadoras são os apresentados no quadro abaixo. Determine um plano de transporte ótimo que minimize o custo de transporte.
L. Dest. 1
L. Dest. 2
L. Dest. 3
L. Dest. 4
L. Or. 1
45
17
21
30
L. Or. 2
14
18
19
31
Passo 1
O problema pede: determinar um plano de transporte (quantidades a enviar de cada agência de origem para cada agência de destino) que minimize o custo total de transporte, dado o estoque excedente nas duas agências de origem e as necessidades das quatro agências destino, além da tabela de custos unitários entre origens e destinos.
Informações dadas (peguei diretamente do enunciado):
Observação importante (da soma das quantidades acima): a oferta total é
15+13=28,
enquanto a demanda total é
9+6+7+9=31.
Como a demanda excede a oferta, o problema está originalmente “desbalanceado” (não há carros suficientes nos dois excedentes para satisfazer toda a demanda). Para poder aplicar os métodos padrões de transporte e obter uma solução factível, vamos balancear o problema acrescentando uma origem fictícia (dummy) que representa a diferença entre demanda e oferta. Esta é uma técnica padrão para obter uma tabela balanceada; colocamos custo zero nas células do dummy (isso permite a obtenção de uma solução factível; interpretar estas unidades como demandas que não podem ser atendidas pelas origens reais ou como fornecimento extra sem custo de transporte — na prática, se se quisesse penalizar atendimento externo, usar-se-ia custo alto). Aqui usaremos custo zero por simplicidade didática.
Assim, adicionamos uma origem fictícia O3 com oferta
3 \quad (\text{pois }31-28=3),
e custos para todos os destinos iguais a 0.
Agora o problema está balanceado: oferta total 15+13+3=31 = demanda total 31. A resolução começa a partir daqui.]
Passo 2
Vou encontrar uma solução inicial factível pelo método de Vogel (é um bom método porque geralmente produz uma solução inicial com baixo custo). Depois vou otimizar essa solução com o método de potenciais (MODI), que me diz se a solução é ótima e, se não for, mostra como melhorar.
Primeiro apresento a matriz completa de custos com o dummy O3:
Agora aplico Vogel passo a passo. Explico o que é cada cálculo: a “penalidade” de uma linha (ou coluna) é a diferença entre os dois menores custos nessa linha (ou coluna). A ideia é priorizar linhas/colunas com penalidade alta, porque aí deixar de escolher o menor custo pode custar caro.
Cálculo inicial das penalidades:
Para O1: custos \{17,21,30,45\} (ordenados) \Rightarrow penalidade 21-17=4.
Para O2: custos \{14,18,19,31\}\Rightarrow penalidade 18-14=4.
Para O3: custos \{0,0,0,0\}\Rightarrow penalidade 0-0=0.
Para colunas (D1 a D4), usando os três custos por coluna:
D1:\{0,14,45\}\Rightarrow penalidade 14-0=14.
D2:\{0,17,18\}\Rightarrow penalidade 17-0=17.
D3:\{0,19,21\}\Rightarrow penalidade 19-0=19.
D4:\{0,30,31\}\Rightarrow penalidade 30-0=30.
A maior penalidade é para D4 (valor 30). Então alocamos na célula de menor custo da coluna D4: os custos na coluna D4 são 30 (O1), 31 (O2) e 0 (O3). O menor é 0 em O3D4. A demanda em D4 é 9, oferta de O3 é 3. Alocamos:
x_{O3,D4}=3.
Atualiza-se: oferta O3 fica 0, demanda D4 fica 6.
Passo 3
Continuo com Vogel após a primeira alocação. Atualizo a tabela removendo O3 (oferta esgotada). Restam origens O1 com 15 e O2 com 13; demandas D1:9,\\ D2:6,\\ D3:7,\\ D4:6.
Recalculo penalidades:
Linha O1: custos restantes \{45,17,21,30\}\Rightarrow menores 17,21\Rightarrow penalidade 21-17=4.
Linha O2: \{14,18,19,31\}\Rightarrow penalidade 18-14=4.
Colunas:
D1:\{45,14\}\Rightarrow penalidade 45-14=31.
D2:\{17,18\}\Rightarrow penalidade 18-17=1.
D3:\{21,19\}\Rightarrow penalidade 21-19=2.
D4:\{30,31\}\Rightarrow penalidade 31-30=1.
Maior penalidade é 31 na coluna D1. Nessa coluna, o menor custo é 14 em O2D1. Demanda D1=9, oferta O2=13. Alocamos:
x_{O2,D1}=9.
Atualiza: O2 fica com oferta 13-9=4. D1 fica satisfeito (0).
Número de células básicas = número de origens + número de destinos - 1 = (3+4-1=6]. Temos 6 alocações básicas, condizente com uma base não degenerada.]
Passo 7
Calculo o custo total da solução inicial (mostro passo a passo as multiplicações):
Agora vamos verificar otimalidade com o método de potenciais (MODI). A ideia: para cada célula básica (i,j) existe uma equação
u_i+v_j=c_{ij},
onde u_i é o potencial da origem i e v_j o potencial do destino j. Escolho arbitrariamente u_{O1}=0 (padrão) e determino os outros potenciais a partir das células básicas. Se para todas as células não-básicas o “custo reduzido”
\Delta_{ij}=c_{ij}-(u_i+v_j)
for maior ou igual a zero, a solução é ótima. Se existir \Delta_{ij}<0, podemos melhorar a solução.
Equações das células básicas (uso O1,O2,O3 para origens e D1,D2,D3,D4 para destinos):
Observação: as células básicas já satisfazem c_{ij}=u_i+v_j por construção. Todos os \Delta calculados para células não-básicas são não negativos:
\Delta_{ij}\in\{29,3,3,14,13,9\}\ge 0.
Como não existe \Delta_{ij}<0, a solução é ótima segundo o critério MODI.
Passo 9
Interpretação final e resumo didático (como fazer isso na prova):
Verifique oferta total e demanda total; se desbalanceadas, adicione origem ou destino “dummy” para balancear (oferta extra ou demanda extra), atribuindo custo adequado (muitas vezes 0 para permitir feasibilidade; se quiser penalizar estes envios, use custo alto).
Encontre solução inicial (Vogel é uma boa escolha prática; também existe Canto Noroeste e Custo Mínimo).
Use o método de potenciais (MODI) para testar otimalidade: determine u_i,v_j a partir das celulas básicas (fixe um u arbitrariamente) e calcule \Delta_{ij}=c_{ij}-(u_i+v_j). Se todos \Delta_{ij}\ge0, a solução é ótima; se existe \Delta_{ij}<0, construa o ciclo fechado (loop) e ajuste quantidades alternando sinais + e - para melhorar a solução e repita.
No caso desta questão, a solução inicial obtida por Vogel já era ótima (todos os \Delta_{ij}\ge0).
Resposta
x_{O1,D2}=6
x_{O1,D3}=3
x_{O1,D4}=6
x_{O2,D1}=9
x_{O2,D3}=4
x_{O3,D4}=3 (origem dummy de quantidade 3)
Custo total mínimo =547.