Uma empresa tem 2 fábricas e 3 depósitos de distribuição. Os custos de distribuição, demandas e capacidades estão no quadro a seguir. Quanto deve ser enviado de cada fábrica para cada depósito de modo a minimizar o custo total de transporte? Ache a solução ótima pelo método do canto noroeste.
Fábrica Depósito
Ofertas
6
7
5
140
4
5
9
250
Demandas
180
220
270
| Fábrica Depósito |
|
|
|
Ofertas |
|
|
6 | 7 | 5 | 140 |
|
|
4 | 5 | 9 | 250 |
| Demandas | 180 | 220 | 270 |
Passo 1
O enunciado pede: determinar quanto enviar de cada fábrica para cada depósito de forma a minimizar o custo total de transporte, usando o método do canto noroeste.
Dados fornecidos (copiados da tabela do enunciado):
Dados fornecidos (copiados da tabela do enunciado):
- Custos de transporte (custo por unidade):
- Ofertas (capacidades das fábricas):
- Demandas dos depósitos:
Observação importante (retirada estritamente dos dados acima): a soma das ofertas é
e a soma das demandas é
. Ou seja, o problema não está balanceado (oferta total diferente da demanda total). Para aplicar o método do canto noroeste e obter uma solução factível precisamos que o problema esteja balanceado. Logo, adicionarei uma origem fictícia (uma fábrica “dummy”) com oferta igual à diferença
e custos iguais a zero para todos os depósitos (técnica padrão para balanceamento). Este passo é necessário para que o método do canto noroeste gere uma solução básica factível.
O objetivo final: obter uma solução viável pelo canto noroeste e, como o enunciado pede a “solução ótima”, depois melhorar essa solução inicial usando o método de otimização MODI (ou stepping-stone) até verificar a otimalidade.
O objetivo final: obter uma solução viável pelo canto noroeste e, como o enunciado pede a “solução ótima”, depois melhorar essa solução inicial usando o método de otimização MODI (ou stepping-stone) até verificar a otimalidade.
Passo 2
Explicando o método do canto noroeste (passo-a-passo como se estivéssemos na prova):
- O método do canto noroeste constrói uma solução inicial básica e factível para o problema de transporte. “Canto noroeste” significa começar pela célula no canto superior esquerdo (Fábrica 1 — Depósito 1) e alocar o máximo possível ali; quando a oferta ou demanda dessa linha/coluna se esgota, move-se para a próxima linha ou coluna conforme apropriado, sempre ocupando a célula “noroeste” restante do subproblema.
- Para balancear oferta e demanda quando não são iguais, adicionamos uma fábrica ou depósito fictício com oferta/demanda igual à diferença. Aqui adicionamos uma fábrica fictícia (Fábrica 3 = dummy) com oferta
e custos para todos os depósitos. Isso permite aplicar o método de forma direta.
Passo 3
Montando a tabela balanceada (com a fábrica dummy). Agora temos 3 fábricas e 3 depósitos. Escrevendo as ofertas/demandas:
Soma oferta = soma demanda =
.
Passo 4
Aplicando o método do canto noroeste para obter a solução inicial (faça como eu: pegue o canto noroeste, coloque o máximo possível, atualize oferta/demanda e avance):
-
Célula
: oferta , demanda . Alocamos .
Atualiza: ofertafica (esgotada), demanda fica . -
Como
esgotou, descemos para mantendo a mesma coluna (canto noroeste do subproblema). Célula : oferta , demanda restante . Alocamos .
Atualiza: ofertafica , demanda fica (satisfeita). -
Agora
está satisfeita, movemos para a próxima coluna na mesma linha . Célula : oferta , demanda . Alocamos .
Atualiza: ofertafica (esgotada), demanda fica . -
esgotou, descemos para (dummy) e permanecemos na coluna . Célula : oferta , demanda . Alocamos .
Atualiza: ofertafica , demanda fica . -
satisfeita, vamos para a coluna na linha . Célula : oferta , demanda . Alocamos .
Atualiza: ofertafica , demanda fica .
Resultados das alocações iniciais pelo canto noroeste (solução básica inicial):
Passo 5
Calculando o custo total inicial (usar custos originais; custos do dummy são zero):
Custo inicial .
Calcule passo a passo: ,
,
. Soma:
.
Então custo inicial é .
Custo inicial
Calcule passo a passo:
Então custo inicial é
Passo 6
Explicando que o canto noroeste dá uma solução inicial; para obter a solução ótima precisamos testar e melhorar essa solução. Vou usar o método MODI (ou método dos potenciais) para verificar otimalidade e, se possível, melhorar. O procedimento do MODI (resumidamente):
- Para cada célula básica (onde há alocação), satisfazemos as equações
, atribuindo arbitrariamente uma potencial (por exemplo ) e resolvendo s e s. - Para cada célula não-básica calculamos o custo reduzido
. Se todos (em problema de minimização), a solução é ótima. Se existe , podemos melhorar a solução aumentando a variável não-básica correspondente, formando um ciclo fechado (stepping-stone), ajustando quantidades ao longo do ciclo com alternância + e -, e obtendo uma solução de custo menor. Repetimos até não haver .
Passo 7
Lista das células básicas da solução inicial e número de básicos: temos
básicos esperados. As células básicas atuais (não-nulas) são:
. Isso dá 5 básicos, ok (não degenerado neste momento).
Passo 8
Aplicando MODI na solução inicial: definimos
(convenção). Resolvendo
nas células básicas:
- Para
: - Para
: - Para
: - Para
: (custos dummy ). - Para
:
Potenciais obtidos:
Passo 9
Calculando os custos reduzidos
nas células não-básicas para verificar otimalidade:
-
: -
: (negativo!) -
:
Como existe uma célula não-básica com
(especificamente
com
), a solução inicial não é ótima e podemos melhorar. Iremos aumentar a variável da célula
.
Passo 10
Formando o ciclo fechado (stepping-stone) envolvendo a célula não-básica escolhida
. Para construir o ciclo, movemos ortogonalmente entre células e só viramos em células básicas. Um ciclo válido é:
Atribuímos sinais alternados
começando por
na célula não-básica que desejamos inserir.
As células com sinal
no ciclo são:
O máximo que podemos aumentar na célula
é o mínimo desses valores:
Passo 11
Atualizando as alocações pelo ciclo (somamos
nas células com sinal
e subtraímos
nas células com sinal
):
-
(antes ) recebe -
(antes ) recebe -
(antes ) recebe -
(antes ) recebe -
(antes ) recebe -
(antes ) recebe
Após a atualização, a nova solução (básica) é:
Observação:
ficou com alocação zero; agora é não-básica e foi substituída por
na base. Ainda temos 5 básicos (a contagem m+n-1 é mantida).
Passo 12
Calculando o novo custo total após a melhoria: considerar apenas custos não-nulos (custos dummy = 0):
Calcule:
Soma:
Então o custo diminuiu de
para
.
Passo 13
Verificação de otimalidade final pelo MODI na solução atual: obtemos os potenciais
usando as células básicas atuais
. Defina
.
Resolvendo:
Potenciais:
Agora calculamos
para as células não-básicas:
Todos os
, logo a solução atual é ótima.
Passo 14
Interpretando o resultado final (lembre-se que a fábrica dummy foi apenas para balancear; decisões reais envolvem somente Fábrica 1 e Fábrica 2): a solução ótima encontrada indica quanto cada fábrica real deve enviar para cada depósito. A solução ótima e o custo mínimo foram obtidos respeitando oferta e demanda.
Resposta
Fábrica 1 para Depósito 1:
Fábrica 1 para Depósito 2:
Fábrica 1 para Depósito 3:
Fábrica 1 para Depósito 2:
Fábrica 1 para Depósito 3:
Fábrica 2 para Depósito 1:
Fábrica 2 para Depósito 2:
Fábrica 2 para Depósito 3:
Fábrica 2 para Depósito 2:
Fábrica 2 para Depósito 3:
Custo total mínimo: