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
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.
| Aeroporto 1 | Aeroporto 2 | Aeroporto 3 | |
| Fornecedor 1 | 92 | 89 | 90 |
| Fornecedor 2 | 91 | 91 | 95 |
| Fornecedor 3 | 87 | 90 | 92 |
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:
galões - Aeroporto 2:
galões - Aeroporto 3:
galões
- Aeroporto 1:
-
Capacidades (oferta) dos fornecedores:
- Fornecedor 1:
galões - Fornecedor 2:
galões - Fornecedor 3:
galões
- Fornecedor 1:
-
Preço por galão ($) de cada fornecedor para cada aeroporto:
- Fornecedor 1: Aeroporto 1 =
, Aeroporto 2 = , Aeroporto 3 = - Fornecedor 2: Aeroporto 1 =
, Aeroporto 2 = , Aeroporto 3 = - Fornecedor 3: Aeroporto 1 =
, Aeroporto 2 = , Aeroporto 3 =
- Fornecedor 1: Aeroporto 1 =
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:
- Soma das ofertas:
Há excesso de oferta:
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:
. O custo de enviar para essa demanda fictícia é
para todos os fornecedores (porque é apenas um meio de absorver excedente). Assim a nova lista de demandas passa a ser: Aero1
, Aero2
, Aero3
, Dummy
.
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:
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:
, Fornecedor 2: , Fornecedor 3: . - Demandas: Aeroporto 1:
, Aeroporto 2: , Aeroporto 3: , Dummy: .
Identificamos a célula de menor custo na tabela original (incluindo dummy). O menor custo real é
(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
. - Oferta do Fornecedor 3:
. Demanda do Aeroporto 1: . - Alocação:
- Atualização:
- Fornecedor 3 passa a ter oferta restante
. - Aeroporto 1 fica satisfeito: demanda restante
.
- Fornecedor 3 passa a ter oferta restante
Passo 6
Depois dessa alocação, as ofertas/demandas são:
- Ofertas: F1:
, F2: , F3: . - Demandas: A1:
, A2: , A3: , Dummy: .
Agora escolhemos a célula de menor custo entre as que ainda têm oferta e demanda. A coluna dummy tem custo
(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
. - Oferta F1:
. Demanda Dummy: . - Alocação:
- Atualização:
- Fornecedor 1 restante:
. - Dummy fica satisfeito: demanda
.
- Fornecedor 1 restante:
Passo 8
Atualização após alocação 2:
- Ofertas: F1:
, F2: , F3: . - Demandas: A1:
, A2: , A3: , Dummy: .
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 =
, F1→A3 = ; F2→A2 = , F2→A3 = ; F3→A2 = , F3→A3 = .
O menor custo é(Fornecedor 1 → Aeroporto 2). Vamos alocar aí.
Passo 9
Alocação 3 — Fornecedor 1 → Aeroporto 2:
- Célula: F1 → A2, custo
. - Oferta F1:
. Demanda A2: . - Alocação:
- Atualização:
- Fornecedor 1 restante:
. - Aeroporto 2 restante:
.
- Fornecedor 1 restante:
Passo 10
Atualização após alocação 3:
- Ofertas: F1:
, F2: , F3: . - Demandas: A1:
, A2: , A3: , Dummy: .
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 (
), F2→A3 ( ), F3→A2 ( ), F3→A3 ( ).
Menor custo é(Fornecedor 3 → Aeroporto 2). Usamos essa célula.
Passo 11
Alocação 4 — Fornecedor 3 → Aeroporto 2:
- Célula: F3 → A2, custo
. - Oferta F3:
. Demanda A2: . - Alocação:
- Atualização:
- Fornecedor 3 restante:
. - Aeroporto 2 fica satisfeito:
.
- Fornecedor 3 restante:
Passo 12
Atualização após alocação 4:
- Ofertas: F1:
, F2: , F3: . - Demandas: A1:
, A2: , A3: , Dummy: .
Só resta atender
com demanda
. As ofertas disponíveis somam
, perfeito. Agora escolhemos as células de menor custo para A3 entre fornecedores com oferta positiva. Custos para A3: F2→A3 =
, F3→A3 =
. O menor é
(Fornecedor 3 → Aeroporto 3). Alocamos.
Passo 13
Alocação 5 — Fornecedor 3 → Aeroporto 3:
- Célula: F3 → A3, custo
. - Oferta F3:
. Demanda A3: . - Alocação:
- Atualização:
- Fornecedor 3 restante:
. - Aeroporto 3 restante:
.
- Fornecedor 3 restante:
Passo 14
Atualização após alocação 5:
- Ofertas: F1:
, F2: , F3: . - Demandas: A3:
restante (as A1,A2,dummy já 0).
Só resta Fornecedor 2 com oferta
para suprir
com
. Alocamos o restante.
Passo 15
Alocação 6 — Fornecedor 2 → Aeroporto 3:
- Célula: F2 → A3, custo
. - Oferta F2:
. Demanda A3: . - Alocação:
- Atualização:
- Fornecedor 2 restante:
. - Aeroporto 3 restante:
.
- Fornecedor 2 restante:
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:
-
(Fornecedor 3 → Aeroporto 1) custo por galão . -
(Fornecedor 1 → demanda fictícia) custo . -
(Fornecedor 1 → Aeroporto 2) custo . -
(Fornecedor 3 → Aeroporto 2) custo . -
(Fornecedor 3 → Aeroporto 3) custo . -
(Fornecedor 2 → Aeroporto 3) custo .
Verificações rápidas:
- Somatória por aeroportos = demandas:
- Somatória por fornecedores = ofertas:
Tudo confere.
Passo 17
Cálculo do custo total da solução (somando
para cada alocação não fictícia — a alocação ao dummy tem custo zero e não contribui):
- Para
: - Para
: - Para
: - Para
: - Para
:
Somando todos:
Portanto o custo total da solução inicial obtida pelo método do custo mínimo é
.
Resposta
Fornecedor 1 → Aeroporto 2:
Fornecedor 1 → Demanda fictícia (dummy):
Fornecedor 2 → Aeroporto 3:
Fornecedor 3 → Aeroporto 1:
Fornecedor 3 → Aeroporto 2:
Fornecedor 3 → Aeroporto 3:
Custo total:
Fornecedor 1 → Demanda fictícia (dummy):
Fornecedor 2 → Aeroporto 3:
Fornecedor 3 → Aeroporto 1:
Fornecedor 3 → Aeroporto 2:
Fornecedor 3 → Aeroporto 3:
Custo total: