Uma companhia aérea regional pode comprar seu combustível para jato a partir de qualquer um dentre três fornecedores. As necessidades da companhia aérea para o mês entrante em cada um dos três aeroportos em que ela opera são: 100.000 galões no aeroporto 1; 180.000 galões no aeroporto 2 e 300.000 no aeroporto 3 . Cada fornecedor pode abastecer cada um dos aeroportos de acordo com os preços (em $ por galão) dados no seguinte quadro:
Aeroporto 1 Aeroporto 2 Aeroporto 3
Fornecedor 1 92 89 90
Fornecedor 2 91 91 95
Fornecedor 3 87 90 92
Cada fornecedor, contudo, está limitado pelo número total de galões que ele pode abastecer por mês. Estas capacidades são 320.000 galões para o fornecedor 1,270.000 galões para o fornecedor 2 e 150.000 galões para o fornecedor 3 . Determine a política de aquisição que suprirá as necessidades da companhia em cada aeroporto a um custo total mínimo. Ache a solução inicial pelo método do custo mínimo.

Passo 1

O enunciado pede que a companhia satisfaça as necessidades mensais dos três aeroportos gastando o mínimo possível, comprando dos três fornecedores sujeitos às capacidades de cada fornecedor. Precisamos achar uma política de aquisição (quantos galões comprar de cada fornecedor para cada aeroporto) que seja factível e de custo mínimo. O enunciado dá:
  • Necessidades (demandas) nos aeroportos:
    • Aeroporto 1: 100000 galões
    • Aeroporto 2: 180000 galões
    • Aeroporto 3: 300000 galões
  • Capacidades (oferta) dos fornecedores:
    • Fornecedor 1: 320000 galões
    • Fornecedor 2: 270000 galões
    • Fornecedor 3: 150000 galões
  • Preço por galão ($) de cada fornecedor para cada aeroporto:
    • Fornecedor 1: Aeroporto 1 = 92, Aeroporto 2 = 89, Aeroporto 3 = 90
    • Fornecedor 2: Aeroporto 1 = 91, Aeroporto 2 = 91, Aeroporto 3 = 95
    • Fornecedor 3: Aeroporto 1 = 87, Aeroporto 2 = 90, Aeroporto 3 = 92
O objetivo imediato desta tarefa é: “Ache a solução inicial pelo método do custo mínimo.” Ou seja, construa uma solução factível inicial (satisfazendo oferta e demanda) usando o procedimento guloso do método do custo mínimo.

Passo 2

Verificação de balanceamento (importante antes de aplicar o método):
  • Soma das demandas: 100000 + 180000 + 300000 = 580000.
  • Soma das ofertas: 320000 + 270000 + 150000 = 740000.
Há excesso de oferta: 740000-580000 = 160000 galões. Para poder aplicar o método de transporte (que exige que oferta total = demanda total), introduzimos uma demanda fictícia (coluna “demanda dummy”) com necessidade igual ao excesso: 160000. O custo de enviar para essa demanda fictícia é 0 para todos os fornecedores (porque é apenas um meio de absorver excedente). Assim a nova lista de demandas passa a ser: Aero1 100000, Aero2 180000, Aero3 300000, Dummy 160000.

Passo 3

Explicação didática do método do custo mínimo (como operar na prova):
  • Você olha a tabela de custos e escolhe o menor custo disponível entre todas as células (incluindo a coluna dummy).
  • Nessa célula escolhida, aloca-se a maior quantidade possível, ou seja: \text{alocação} = \min(\text{oferta do fornecedor}, \text{demanda do aeroporto}).çãIsso garante que ou a oferta do fornecedor zera (linha é eliminada) ou a demanda do aeroporto é satisfeita (coluna é eliminada), pelo menos uma das duas.
  • Atualiza-se as ofertas e demandas subtraindo a quantidade alocada.
  • Remove-se linhas/colunas com valor zero restante e repete-se o processo até que todas as demandas (incluindo dummy) sejam satisfeitas.
  • Se houver empate de custos, pode-se escolher qualquer célula empatada; é comum usar um critério simples (por exemplo, escolher a célula da linha com maior oferta ou coluna com maior demanda) — o método ainda produz uma solução inicial válida.
Agora aplicamos o procedimento passo a passo com os números do problema.

Passo 4

Listagem inicial (ofertas e demandas) antes de alocar:
  • Ofertas: Fornecedor 1: 320000, Fornecedor 2: 270000, Fornecedor 3: 150000.
  • Demandas: Aeroporto 1: 100000, Aeroporto 2: 180000, Aeroporto 3: 300000, Dummy: 160000.
Identificamos a célula de menor custo na tabela original (incluindo dummy). O menor custo real é 87 (Fornecedor 3 → Aeroporto 1). Então começamos por ela.

Passo 5

Alocação 1 — célula com menor custo real:
  • Célula escolhida: Fornecedor 3 → Aeroporto 1, custo 87.
  • Oferta do Fornecedor 3: 150000. Demanda do Aeroporto 1: 100000.
  • Alocação: x_{3,1} = \min(150000,100000) = 100000.
  • Atualização:
    • Fornecedor 3 passa a ter oferta restante 150000-100000 = 50000.
    • Aeroporto 1 fica satisfeito: demanda restante 0.

Passo 6

Depois dessa alocação, as ofertas/demandas são:
  • Ofertas: F1: 320000, F2: 270000, F3: 50000.
  • Demandas: A1: 0, A2: 180000, A3: 300000, Dummy: 160000.
Agora escolhemos a célula de menor custo entre as que ainda têm oferta e demanda. A coluna dummy tem custo 0 (menor possível) e está disponível para todos os fornecedores. Seguindo um critério de desempate simples (escolher uma linha com grande oferta para agilizar), vamos alocar primeiro da Fornecedor 1 para o dummy.

Passo 7

Alocação 2 — atender demanda dummy com Fornecedor 1:
  • Célula escolhida: Fornecedor 1 → Dummy, custo 0.
  • Oferta F1: 320000. Demanda Dummy: 160000.
  • Alocação: x_{1,\text{dummy}} = \min(320000,160000) = 160000.
  • Atualização:
    • Fornecedor 1 restante: 320000-160000 = 160000.
    • Dummy fica satisfeito: demanda 0.

Passo 8

Atualização após alocação 2:
  • Ofertas: F1: 160000, F2: 270000, F3: 50000.
  • Demandas: A1: 0, A2: 180000, A3: 300000, Dummy: 0.
Agora o dummy está satisfeito; resta atender A2 e A3. Procuramos a menor custo entre células com demanda positiva:
  • Custos relevantes restantes: F1→A2 = 89, F1→A3 = 90; F2→A2 = 91, F2→A3 = 95; F3→A2 = 90, F3→A3 = 92.
    O menor custo é 89 (Fornecedor 1 → Aeroporto 2). Vamos alocar aí.

Passo 9

Alocação 3 — Fornecedor 1 → Aeroporto 2:
  • Célula: F1 → A2, custo 89.
  • Oferta F1: 160000. Demanda A2: 180000.
  • Alocação: x_{1,2} = \min(160000,180000) = 160000.
  • Atualização:
    • Fornecedor 1 restante: 160000-160000 = 0.
    • Aeroporto 2 restante: 180000-160000 = 20000.

Passo 10

Atualização após alocação 3:
  • Ofertas: F1: 0, F2: 270000, F3: 50000.
  • Demandas: A1: 0, A2: 20000, A3: 300000, Dummy: 0.
Agora Fornecedor 1 está esgotado, removemos sua linha. Procuramos o menor custo entre as células possíveis:
  • Células disponíveis com demanda positiva: F2→A2 ( 91), F2→A3 ( 95), F3→A2 ( 90), F3→A3 ( 92).
    Menor custo é 90 (Fornecedor 3 → Aeroporto 2). Usamos essa célula.

Passo 11

Alocação 4 — Fornecedor 3 → Aeroporto 2:
  • Célula: F3 → A2, custo 90.
  • Oferta F3: 50000. Demanda A2: 20000.
  • Alocação: x_{3,2} = \min(50000,20000) = 20000.
  • Atualização:
    • Fornecedor 3 restante: 50000-20000 = 30000.
    • Aeroporto 2 fica satisfeito: 0.

Passo 12

Atualização após alocação 4:
  • Ofertas: F1: 0, F2: 270000, F3: 30000.
  • Demandas: A1: 0, A2: 0, A3: 300000, Dummy: 0.
Só resta atender A3 com demanda 300000. As ofertas disponíveis somam 270000 + 30000 = 300000, perfeito. Agora escolhemos as células de menor custo para A3 entre fornecedores com oferta positiva. Custos para A3: F2→A3 = 95, F3→A3 = 92. O menor é 92 (Fornecedor 3 → Aeroporto 3). Alocamos.

Passo 13

Alocação 5 — Fornecedor 3 → Aeroporto 3:
  • Célula: F3 → A3, custo 92.
  • Oferta F3: 30000. Demanda A3: 300000.
  • Alocação: x_{3,3} = \min(30000,300000) = 30000.
  • Atualização:
    • Fornecedor 3 restante: 30000-30000 = 0.
    • Aeroporto 3 restante: 300000-30000 = 270000.

Passo 14

Atualização após alocação 5:
  • Ofertas: F1: 0, F2: 270000, F3: 0.
  • Demandas: A3: 270000 restante (as A1,A2,dummy já 0).
Só resta Fornecedor 2 com oferta 270000 para suprir A3 com 270000. Alocamos o restante.

Passo 15

Alocação 6 — Fornecedor 2 → Aeroporto 3:
  • Célula: F2 → A3, custo 95.
  • Oferta F2: 270000. Demanda A3: 270000.
  • Alocação: x_{2,3} = \min(270000,270000) = 270000.
  • Atualização:
    • Fornecedor 2 restante: 0.
    • Aeroporto 3 restante: 0.
Agora todas as demandas (incluindo dummy) estão satisfeitas e todas as ofertas foram usadas (algumas ofertas foram totalmente utilizadas, outras parcialmente). Temos uma solução básica factível obtida pelo método do custo mínimo.

Passo 16

Resumo das alocações obtidas:
  • x_{3,1} = 100000 (Fornecedor 3 → Aeroporto 1) custo por galão 87.
  • x_{1,\text{dummy}} = 160000 (Fornecedor 1 → demanda fictícia) custo 0.
  • x_{1,2} = 160000 (Fornecedor 1 → Aeroporto 2) custo 89.
  • x_{3,2} = 20000 (Fornecedor 3 → Aeroporto 2) custo 90.
  • x_{3,3} = 30000 (Fornecedor 3 → Aeroporto 3) custo 92.
  • x_{2,3} = 270000 (Fornecedor 2 → Aeroporto 3) custo 95.
Verificações rápidas:
  • Somatória por aeroportos = demandas: \begin{aligned} A1 &: 100000 \\\ A2 &: 160000 + 20000 = 180000 \\\ A3 &: 30000 + 270000 = 300000 \\\ \text{Dummy} &: 160000 \end{aligned}
  • Somatória por fornecedores = ofertas: \begin{aligned} F1 &: 160000 + 160000 = 320000 \quad(\text{o segundo termo é dummy})\\\ F2 &: 270000 \\\ F3 &: 100000 + 20000 + 30000 = 150000 \end{aligned}é
Tudo confere.

Passo 17

Cálculo do custo total da solução (somando \text{quantidade} \times \text{custo por galão}ã para cada alocação não fictícia — a alocação ao dummy tem custo zero e não contribui):
  • Para x_{3,1}: 100000 \times 87 = 8700000.
  • Para x_{1,2}: 160000 \times 89 = 14240000.
  • Para x_{3,2}: 20000 \times 90 = 1800000.
  • Para x_{3,3}: 30000 \times 92 = 2760000.
  • Para x_{2,3}: 270000 \times 95 = 25650000.
Somando todos:
8700000 + 14240000 + 1800000 + 2760000 + 25650000 = 53150000.
Portanto o custo total da solução inicial obtida pelo método do custo mínimo é \$53150000.

Resposta

Fornecedor 1 → Aeroporto 2: 160000
Fornecedor 1 → Demanda fictícia (dummy): 160000
Fornecedor 2 → Aeroporto 3: 270000
Fornecedor 3 → Aeroporto 1: 100000
Fornecedor 3 → Aeroporto 2: 20000
Fornecedor 3 → Aeroporto 3: 30000
Custo total: \$53150000

Exercícios relacionados