Uma fábrica necessita fabricar e distribuir iPods para o período natalino. Ela possui três fábricas (A, B e C) com capacidades de
e 150.000 unidades respectivamente. Há três centros mundiais de distribuição (N, S, E e W) com capacidades de distribuição de
e 100.000 unidades respectivamente. Os custos de transporte unitário são
16
13
22
17
14
13
15
9
20
23
10
Devido problemas políticos, não há possibilidade da fábrica B enviar iPods para o centro de distribuição E. Determine o plano ótimo de transporte das fábricas aos centros de distribuição tal que o custo seja mínimo.
|
|
|
|
|
|
|
|
16 | 13 | 22 | 17 |
|
|
14 | 13 |
|
15 |
|
|
9 | 20 | 23 | 10 |
Passo 1
O enunciado pede: encontrar o plano de transporte das fábricas
para os centros de distribuição
que minimize o custo total, sabendo que a fábrica
não pode enviar para
. Dados fornecidos:
- Capacidades das fábricas (oferta):
- Capacidades (demandas) dos centros:
- Custos unitários de transporte (em cada célula da tabela):
Pergunta direta: qual é a quantidade enviada de cada fábrica a cada centro (plano de transporte) que minimize o custo total, respeitando a proibição
?
Passo 2
Verificação de balanceamento da tabela e tratamento de rota proibida:
- Soma das ofertas:
- Soma das demandas:
Há excesso de oferta de
unidades. Para transformar o problema numérico em balanceado, adicionamos uma demanda fictícia
de
unidades com custo unitário zero a partir de qualquer fábrica (células
custo
). A rota proibida
é tratada impondo
(ou custo muito grande), portanto não estará disponível.
Após adicionar
, temos demandas totais igualando a oferta total:
Passo 3
Escolha do método e estratégia intuitiva (explicada passo a passo, sem pular etapas):
- Observação importante (decisiva): como
não pode enviar para , todas as unidades exigidas por só podem ser supridas por e . As ofertas de e somam
ou seja, há capacidade suficiente, mas isso impõe uma restrição:
com
e
. Para minimizar custo em uma coluna onde só há duas fontes possíveis, compare os custos unitários:
e
. Como
, é mais barato deslocar o máximo possível de
para
(respeitando a oferta de
). Assim, convém escolher
o mais alto possível, até
, e o restante
(porque
). Esta é uma regra simples: quando apenas certas fábricas podem atender uma demanda, aloque a partir daquelas com menor custo primeiro.
- Depois de fixar a cobertura de
por e , verificaremos o resto das demandas usando o critério de menor custo disponível, lembrando que toda alocação deve respeitar a oferta remanescente de cada fábrica.
Vou aplicar essa estratégia concreta, mostrando contas e verificações de viabilidade.
Passo 4
Alocação inicial baseada na observação anterior sobre
:
- Atender
com o máximo possível de (menor custo ):
- Como
exige , e deu , o restante vira de :
Após essas alocações, as ofertas remanescentes são:
Passo 5
Atender as outras demandas com as ofertas remanescentes, escolhendo custos menores e respeitando capacidades:
Demandas restantes:
Custos relevantes (somente para fábricas com oferta remanescente):
- A tem oferta
— não pode enviar mais. - B (oferta
): custos . - C (oferta
): custos .
Procedimento lógico:
- C tem custos muito baixos para
e ( e ). Mas lembre-se que já forneceu para e só tem sobrando; escolha onde aplicar esses de forma a reduzir custo total máximo. O menor custo é com , então alocamos:
- Atualiza demanda
: ainda faltando. - Agora as ofertas remanescentes:
continua com (não usada ainda), com . - As demandas restantes são exatamente:
. A soma é , que coincide com a oferta remanescente de . Como é a única fábrica com oferta restante, ela atenderá todas essas demandas (e permanece proibido, mas não precisamos de já que está coberto). Portanto:
Agora verificamos todas as igualdades oferta = soma saídas e demanda = soma entradas:
- Para
: (soma saídas oferta). - Para
: . - Para
: . - Demandas:
. Tudo conferido.
Passo 6
Cálculo explícito do custo total do plano encontrado (mostrar todas as contas, sem pular etapas). Para cada célula ocupada calculamos
:
Somando tudo:
Portanto o custo total deste plano é
(unidades monetárias).
Passo 7
Verificação de otimalidade pelo método MODI (método dos potenciais) — explicação e execução passo a passo:
No método MODI introduzimos potenciais
para linhas (fábricas) e
para colunas (centros), tais que para toda célula básica (usada) vale
Escolhemos uma base de
alocações básicas. As células básicas aqui (com alocações positivas) são exatamente 7, que é
:
Fixamos arbitrariamente
(ponto de partida). A partir das igualdades:
Agora calculamos os custos reduzidos (custo marginal) para todas as células não básicas
:
Se todos
(em problema de minimização), a solução é ótima.
Calculamos rapidamente os não básicos principais:
-
-
-
-
-
-
- A célula proibida
é inatingível (imposta como proibida).
Todos os
são não negativos, logo a solução é ótima segundo o critério do método dos potenciais. Assim, não há melhoria possível por ciclos alternantes.
Passo 8
Resumo final (plano ótimo explicitado por arcos com quantidades) — já verificamos que é factível e ótimo e mostramos o custo total.
Resposta
Custo mínimo total: