O Expresso Rápido Faxina é uma empresa de transporte com quatro grandes terminais localizados em Curitiba, Cascavel, Londrina e Campo Mourão. Os pneus utilizados pela frota dessa empresa são padronizados. A empresa fez uma tomada de preços em três grandes revendedores de pneus e obteve as seguintes cotações:
LOCAL Revendedor A Revendedor B Revendedor C Pneus Necessários
Curitiba 70 64 68 4000
Londrina 74 62 65 8000
Cascavel 62 68 64 3000
Campo Mourão 62 72 66 5000
Pneus Disponíveis 12000 6000 4000
Se o objetivo da empresa Expresso Rápido Faxina é minimizar o custo total de aquisição dos pneus, quanto ela deverá comprar de cada revendedor? Ache a solução inicial pelo método de Vogel.

Passo 1

Vou primeiro deixar claro o que o enunciado dá e o que ele pede, sem começar a resolver ainda.
  • Pedem que a empresa minimize o custo total de aquisição dos pneus e querem a solução inicial obtida pelo método de Vogel.
  • Custos por pneu (peguei os valores da tabela do enunciado): \begin{array}{c|cccc} & \text{Curitiba} & \text{Londrina} & \text{Cascavel} & \text{Campo Mourão} \\\ \hline \text{Rev. A} & 70 & 74 & 62 & 62 \\\ \text{Rev. B} & 64 & 62 & 68 & 72 \\\ \text{Rev. C} & 68 & 65 & 64 & 66 \\\ \end{array}
  • Demandas (pneus necessários em cada terminal), também da tabela: \text{Curitiba}=4000,\quad \text{Londrina}=8000,\quad \text{Cascavel}=3000,\quad \text{Campo Mourão}=5000.ã
  • Ofertas (pneus disponíveis em cada revendedor), da tabela: \text{Rev. A}=12000,\quad \text{Rev. B}=6000,\quad \text{Rev. C}=4000.
  • Observação importante: soma das ofertas =12000+6000+4000=22000 e soma das demandas =4000+8000+3000+5000=20000. Como as ofertas excedem as demandas em 2000, para aplicar o método de Vogel equilibramos o problema adicionando uma coluna “demanda fictícia” (dummy) com demanda 2000 e custo zero (custos 0 de todos os revendedores para essa coluna). Essa coluna representa a sobra que não será utilizada.
A resolução começa no próximo passo.

Passo 2

Breve explicação do método de Vogel (aula rápida, passo a passo e intuitiva):
  • O método de Vogel é uma heurística para obter uma solução inicial “bom” para problemas de transporte. A ideia é, a cada iteração, olhar para cada linha (fornecedor) e cada coluna (demanda) e calcular uma “penalidade”: a diferença entre os dois menores custos daquela linha/coluna. Penalidades grandes mostram lugares onde errar pode custar caro, então priorizamos alocações onde a penalidade é maior.
  • Passos operacionais em cada iteração:
    1. Para cada linha e coluna ainda não satisfeita, calcule a penalidade = (2ª menor custo) − (menor custo).
    2. Escolha a linha ou coluna com maior penalidade. Se houver empate, quebraremos o empate escolhendo a linha/coluna cujo menor custo entre as opções seja o menor (isso favorece a menor despesa imediata).
    3. Na linha/coluna escolhida, faça a alocação máxima possível na célula de menor custo (ou seja, aloque mínimo entre oferta disponível do fornecedor e demanda restante do cliente).
    4. Atualize oferta/demanda e risque (ou marque) linhas/colunas com oferta ou demanda zeradas; volte ao passo 1 até todas as demandas reais estarem satisfeitas (a coluna dummy também deve ser tratada).
  • Sempre que eu usar uma célula da coluna dummy significa simplesmente que essa parcela de oferta não será utilizada para atender demanda real.
Agora aplico o método, mostrando as contas detalhadamente.

Passo 3

Montagem inicial da tabela de custos incluindo a coluna dummy (custo 0 para todos) e os vetores oferta/demanda:
\begin{array}{c|ccccc|c} & \text{Curitiba} & \text{Londrina} & \text{Cascavel} & \text{Campo Mourão} & \text{Dummy} & \text{Oferta} \\\ \hline \text{Rev. A} & 70 & 74 & 62 & 62 & 0 & 12000 \\\ \text{Rev. B} & 64 & 62 & 68 & 72 & 0 & 6000 \\\ \text{Rev. C} & 68 & 65 & 64 & 66 & 0 & 4000 \\\ \hline \text{Demanda} & 4000 & 8000 & 3000 & 5000 & 2000 & 20000 \end{array}
Começo a aplicar Vogel: calculo penalidades iniciais (para cada linha e cada coluna, usando apenas colunas ainda com demanda):
  • Linhas:
    • Rev. A: custos \{0,62,62,70,74\} → dois menores 0 e 62 → penalidade =62-0=62.
    • Rev. B: custos \{0,62,64,68,72\} → penalidade =62-0=62.
    • Rev. C: custos \{0,64,65,66,68\} → penalidade =64-0=64.
  • Colunas:
    • Curitiba: \{70,64,68\} → penalidade =68-64=4.
    • Londrina: \{74,62,65\} → penalidade =65-62=3.
    • Cascavel: \{62,68,64\} → penalidade =64-62=2.
    • Campo Mourão: \{62,72,66\} → penalidade =66-62=4.
    • Dummy: \{0,0,0\} → penalidade =0.
A maior penalidade é da linha Rev. C = 64. Pelo critério do método, escolhemos a linha Rev. C e alocamos na célula de menor custo nessa linha. O menor custo da Rev. C é 0 na coluna Dummy.
Alocação:
  • (\text{Rev. C}, \text{Dummy}) = \min(\text{oferta Rev. C}=4000,\; \text{demanda Dummy}=2000)=2000.
Custo dessa alocação é 2000\cdot 0=0.
Atualizo: oferta Rev. C passa de 4000 para 2000. Demanda Dummy vira 0 (satisfeita). Removo a coluna Dummy das próximas considerações.

Passo 4

Recalculo penalidades com a coluna dummy removida.
Ofertas atuais: Rev. A =12000, Rev. B =6000, Rev. C =2000. Demandas restantes: Curitiba 4000, Londrina 8000, Cascavel 3000, Campo Mourão 5000.
Penalidades novas:
  • Linhas:
    • Rev. A: custos \{70,74,62,62\} → dois menores 62,62 → penalidade =0.
    • Rev. B: custos \{64,62,68,72\} → dois menores 62,64 → penalidade =2.
    • Rev. C: custos \{68,65,64,66\} → dois menores 64,65 → penalidade =1.
  • Colunas:
    • Curitiba: \{70,64,68\} → penalidade =4.
    • Londrina: \{74,62,65\} → penalidade =3.
    • Cascavel: \{62,68,64\} → penalidade =2.
    • Campo Mourão: \{62,72,66\} → penalidade =4.
Maior penalidade é 4 (duas colunas: Curitiba e Campo Mourão). Quebra de empate: escolho a coluna cujo menor custo entre as duas colunas empatadas seja o menor (isso tende a reduzir custo). Para Curitiba o menor custo é 64 (Rev. B); para Campo Mourão o menor custo é 62 (Rev. A). Como 62<64, escolho a coluna Campo Mourão.
Na coluna Campo Mourão, menor custo é na célula (\text{Rev. A},\text{Campo Mourão})ã com custo 62. Aloco:
  • (\text{Rev. A}, \text{Campo Mourão})=\min(\text{oferta Rev. A}=12000,\; \text{demanda Campo Mourão}=5000)=5000ãã.
Custo: 5000\cdot 62=310000.
Atualizo: Rev. A oferta passa para 12000-5000=7000. Demanda Campo Mourão vira 0 (satisfeita). Removo essa coluna.

Passo 5

Agora demandas restantes: Curitiba 4000, Londrina 8000, Cascavel 3000.
Ofertas: Rev. A 7000, Rev. B 6000, Rev. C 2000.
Calculo penalidades:
  • Rev. A: custos \{70,74,62\} (Curitiba,Londrina,Cascavel) → menores 62,70 → penalidade =8.
  • Rev. B: custos \{64,62,68\} → menores 62,64 → penalidade =2.
  • Rev. C: custos \{68,65,64\} → menores 64,65 → penalidade =1.
  • Colunas:
    • Curitiba: \{70,64,68\} → penalidade =4.
    • Londrina: \{74,62,65\} → penalidade =3.
    • Cascavel: \{62,68,64\} → penalidade =2.
A maior penalidade é da linha Rev. A = 8. Então escolhemos a linha Rev. A e alocamos na sua célula de menor custo entre as colunas restantes. Na Rev. A o menor custo é 62 na coluna Cascavel.
Alocação:
  • (\text{Rev. A},\text{Cascavel})=\min( \text{oferta Rev. A}=7000,\; \text{demanda Cascavel}=3000)=3000.
Custo: 3000\cdot 62=186000.
Atualizo: Rev. A oferta 7000-3000=4000. Demanda Cascavel vira 0. Removo coluna Cascavel.

Passo 6

Restam apenas as colunas (demandas) Curitiba 4000 e Londrina 8000. Ofertas: Rev. A 4000, Rev. B 6000, Rev. C 2000. Somatório das ofertas =4000+6000+2000=12000 igual à soma das demandas restantes =4000+8000=12000, bom.
Penalidades (com duas colunas é rápido):
  • Rev. A: custos \{70,74\} → penalidade =74-70=4.
  • Rev. B: custos \{64,62\} → penalidade =64-62=2.
  • Rev. C: custos \{68,65\} → penalidade =68-65=3.
  • Colunas:
    • Curitiba: custos \{70,64,68\} → penalidade =4.
    • Londrina: custos \{74,62,65\} → penalidade =3.
Maior penalidade =4 (empate entre Rev. A e coluna Curitiba). Quebra de empate: olho o menor custo associado: para Rev. A o menor custo entre as duas colunas é 70 (Curitiba); para a coluna Curitiba o menor custo é 64 (Rev. B). Como 64<70, escolho a coluna Curitiba.
Na coluna Curitiba a célula de menor custo é (\text{Rev. B},\text{Curitiba}) com custo 64. Aloco:
  • (\text{Rev. B},\text{Curitiba})=\min(\text{oferta Rev. B}=6000,\; \text{demanda Curitiba}=4000)=4000.
Custo: 4000\cdot 64=256000.
Atualizo: Rev. B oferta 6000-4000=2000. Demanda Curitiba vira 0. Removo coluna Curitiba.

Passo 7

Só resta a coluna Londrina com demanda 8000. Ofertas restantes: Rev. A 4000, Rev. B 2000, Rev. C 2000 — total 8000 exatamente. Preenchemos essa coluna alocando pelas menores células disponíveis, ou simplesmente alocando conforme oferta remanescente:
  • Menor custo em Londrina é Rev. B = 62. Aloco:
    • (\text{Rev. B},\text{Londrina})=\min( \text{oferta Rev. B}=2000,\; \text{demanda Londrina}=8000)=2000.
    • Custo 2000\cdot 62=124000.
    • Atualizo: oferta Rev. B =0. Demanda Londrina passa a 6000.
  • Próximo menor custo em Londrina é Rev. C = 65. Aloco:
    • (\text{Rev. C},\text{Londrina})=\min( \text{oferta Rev. C}=2000,\; \text{demanda Londrina}=6000)=2000.
    • Custo 2000\cdot 65=130000.
    • Atualizo: oferta Rev. C =0. Demanda Londrina passa a 4000.
  • Restante da demanda Londrina =4000 será atendida por Rev. A (único com oferta sobrando), custo 74:
    • (\text{Rev. A},\text{Londrina})=\min( \text{oferta Rev. A}=4000,\; \text{demanda Londrina}=4000)=4000.
    • Custo 4000\cdot 74=296000.
    • Atualizo: oferta Rev. A =0. Demanda Londrina =0.
Agora todas as demandas reais e a coluna dummy estão satisfeitas. Temos uma solução inicial completa obtida pelo método de Vogel.

Passo 8

Resumo das alocações obtidas (cada célula mostra quantidade alocada):
\begin{array}{c|ccccc|c} & \text{Curitiba} & \text{Londrina} & \text{Cascavel} & \text{Campo Mourão} & \text{Dummy} & \text{Oferta inicial}\\\ \hline \text{Rev. A} & 0 & 4000 & 3000 & 5000 & 0 & 12000\\\ \text{Rev. B} & 4000 & 2000 & 0 & 0 & 0 & 6000\\\ \text{Rev. C} & 0 & 2000 & 0 & 0 & 2000 & 4000\\\ \hline \text{Demanda} & 4000 & 8000 & 3000 & 5000 & 2000 & 20000 \end{array}
Interpretação prática (importante): a coluna Dummy recebeu 2000 da Rev. C; isso significa que desses 2000 a Rev. C tinha disponível, a empresa não os comprou para atender demanda real. Portanto as quantidades efetivamente compradas de cada revendedor (envios para demandas reais) são:
  • Rev. A: 5000+3000+4000 = 12000.
  • Rev. B: 4000+2000 = 6000.
  • Rev. C: 2000 (somente para Londrina; os outros 2000 ficaram não utilizados — dummy).
Cálculo do custo total da solução (somando custos de cada alocação):
\begin{aligned} &5000\cdot 62 \;(\text{A}\to\text{Campo}) &&=310000,\\\ &3000\cdot 62 \;(\text{A}\to\text{Cascavel}) &&=186000,\\\ &4000\cdot 74 \;(\text{A}\to\text{Londrina}) &&=296000,\\\ &4000\cdot 64 \;(\text{B}\to\text{Curitiba}) &&=256000,\\\ &2000\cdot 62 \;(\text{B}\to\text{Londrina}) &&=124000,\\\ &2000\cdot 65 \;(\text{C}\to\text{Londrina}) &&=130000,\\\ &2000\cdot 0 \;(\text{C}\to\text{Dummy}) &&=0. \end{aligned}
Somando:
310000+186000+296000+256000+124000+130000 = 1302000.
Assim o custo total da solução inicial pelo método de Vogel é 1{,}302{,}000.

Resposta

Revendedor A: comprar 12000 pneus (alocações: \text{Londrina}=4000,\; \text{Cascavel}=3000,\; \text{Campo Mourão}=5000ã)
Revendedor B: comprar 6000 pneus (alocações: \text{Curitiba}=4000,\; \text{Londrina}=2000)
Revendedor C: comprar 2000 pneus (alocação: \text{Londrina}=2000; os 2000 restantes foram não utilizados - dummy)
Custo total da solução inicial (Vogel): 1{,}302{,}000

Exercícios relacionados