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 \mathbf{1} \mathbf{2} \mathbf{3} Ofertas
\mathbf{1} 6 7 5 140
\mathbf{2} 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):
  • Custos de transporte (custo por unidade):
\begin{matrix} & \text{Depósito 1} & \text{Depósito 2} & \text{Depósito 3}\\\ \text{Fábrica 1} & 6 & 7 & 5\\\ \text{Fábrica 2} & 4 & 5 & 9 \end{matrix}óóóáá
  • Ofertas (capacidades das fábricas): \text{Fábrica 1}:140,\\ \text{Fábrica 2}:250.áá
  • Demandas dos depósitos: \text{Depósito 1}:180,\\ \text{Depósito 2}:220,\\ \text{Depósito 3}:270.óóó
Observação importante (retirada estritamente dos dados acima): a soma das ofertas é \,140+250=390 e a soma das demandas é \,180+220+270=670. 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 \,670-390=280 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.

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 280 e custos 0 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:
\begin{array}{c|ccc|c} & D1 & D2 & D3 & \text{Oferta}\\hline F1 & 6 & 7 & 5 & 140\\\ F2 & 4 & 5 & 9 & 250\\\ F3(\text{dummy}) & 0 & 0 & 0 & 280\\hline \text{Demanda} & 180 & 220 & 270 & \end{array}
Soma oferta = soma demanda = 390+280=670.

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):
  1. Célula (F1,D1): oferta 140, demanda 180. Alocamos \min(140,180)=140.
    Atualiza: oferta F1 fica 0 (esgotada), demanda D1 fica 180-140=40.
  2. Como F1 esgotou, descemos para F2 mantendo a mesma coluna D1 (canto noroeste do subproblema). Célula (F2,D1): oferta 250, demanda restante 40. Alocamos \min(250,40)=40.
    Atualiza: oferta F2 fica 250-40=210, demanda D1 fica 0 (satisfeita).
  3. Agora D1 está satisfeita, movemos para a próxima coluna D2 na mesma linha F2. Célula (F2,D2): oferta 210, demanda 220. Alocamos \min(210,220)=210.
    Atualiza: oferta F2 fica 0 (esgotada), demanda D2 fica 220-210=10.
  4. F2 esgotou, descemos para F3 (dummy) e permanecemos na coluna D2. Célula (F3,D2): oferta 280, demanda 10. Alocamos \min(280,10)=10.
    Atualiza: oferta F3 fica 280-10=270, demanda D2 fica 0.
  5. D2 satisfeita, vamos para a coluna D3 na linha F3. Célula (F3,D3): oferta 270, demanda 270. Alocamos \min(270,270)=270.
    Atualiza: oferta F3 fica 0, demanda D3 fica 0.
Resultados das alocações iniciais pelo canto noroeste (solução básica inicial):
\begin{array}{c|ccc|c} & D1 & D2 & D3 & \text{Oferta}\\hline F1 & 140 & 0 & 0 & 140\\\ F2 & 40 & 210 & 0 & 250\\\ F3 & 0 & 10 & 270 & 280\\hline \text{Demanda} & 180 & 220 & 270 & \end{array}

Passo 5

Calculando o custo total inicial (usar custos originais; custos do dummy são zero):
Custo inicial =140\cdot 6 + 40\cdot 4 + 210\cdot 5 + 10\cdot 0 + 270\cdot 0.
Calcule passo a passo: 140\cdot 6 = 840, 40\cdot 4 = 160, 210\cdot 5 = 1050. Soma: 840+160+1050=2050.
Então custo inicial é \,2050.

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 u_i+v_j=c_{ij}, atribuindo arbitrariamente uma potencial (por exemplo u_1=0) e resolvendo us e vs.
  • Para cada célula não-básica calculamos o custo reduzido \Delta_{ij}=c_{ij}-(u_i+v_j). Se todos \Delta_{ij}\ge 0 (em problema de minimização), a solução é ótima. Se existe \Delta_{ij}<0, 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 \Delta_{ij}<0.

Passo 7

Lista das células básicas da solução inicial e número de básicos: temos m+n-1=3+3-1=5 básicos esperados. As células básicas atuais (não-nulas) são: (F1,D1)=140,\\ (F2,D1)=40,\\ (F2,D2)=210,\\ (F3,D2)=10,\\ (F3,D3)=270. Isso dá 5 básicos, ok (não degenerado neste momento).

Passo 8

Aplicando MODI na solução inicial: definimos u_1=0 (convenção). Resolvendo u_i+v_j=c_{ij} nas células básicas:
  • Para (F1,D1): u_1+v_1=6 \Rightarrow v_1=6.
  • Para (F2,D1): u_2+v_1=4 \Rightarrow u_2=4-v_1=4-6=-2.
  • Para (F2,D2): u_2+v_2=5 \Rightarrow v_2=5-u_2=5-(-2)=7.
  • Para (F3,D2): u_3+v_2=0 \Rightarrow u_3=-v_2=-7 (custos dummy =0).
  • Para (F3,D3): u_3+v_3=0 \Rightarrow v_3=-u_3=7.
Potenciais obtidos: u_1=0,\\ u_2=-2,\\ u_3=-7,\\ v_1=6,\\ v_2=7,\\ v_3=7.

Passo 9

Calculando os custos reduzidos \Delta_{ij}=c_{ij}-(u_i+v_j) nas células não-básicas para verificar otimalidade:
  • (F1,D2): c=7,\\ u_1+v_2=0+7=7 \Rightarrow \Delta=0.
  • (F1,D3): c=5,\\ u_1+v_3=0+7=7 \Rightarrow \Delta=5-7=-2. (negativo!)
  • (F2,D3): c=9,\\ u_2+v_3=-2+7=5 \Rightarrow \Delta=9-5=4.
Como existe uma célula não-básica com \Delta<0 (especificamente (F1,D3) com \Delta=-2), a solução inicial não é ótima e podemos melhorar. Iremos aumentar a variável da célula (F1,D3).

Passo 10

Formando o ciclo fechado (stepping-stone) envolvendo a célula não-básica escolhida (F1,D3). Para construir o ciclo, movemos ortogonalmente entre células e só viramos em células básicas. Um ciclo válido é:
(1,3)\\ (+) \rightarrow (3,3)\\ (-) \rightarrow (3,2)\\ (+) \rightarrow (2,2)\\ (-) \rightarrow (2,1)\\ (+) \rightarrow (1,1)\\ (-) \rightarrow \text{volta em }(1,3).
Atribuímos sinais alternados +,-,+,-,\dots começando por + na célula não-básica que desejamos inserir.
As células com sinal - no ciclo são: (3,3)=270,\\ (2,2)=210,\\ (1,1)=140. O máximo que podemos aumentar na célula (1,3) é o mínimo desses valores: \theta=\min(270,210,140)=140.

Passo 11

Atualizando as alocações pelo ciclo (somamos \theta=140 nas células com sinal + e subtraímos \theta nas células com sinal -):
  • (F1,D3) (antes 0) recebe +140 \Rightarrow 140.
  • (F3,D3) (antes 270) recebe -140 \Rightarrow 130.
  • (F3,D2) (antes 10) recebe +140 \Rightarrow 150.
  • (F2,D2) (antes 210) recebe -140 \Rightarrow 70.
  • (F2,D1) (antes 40) recebe +140 \Rightarrow 180.
  • (F1,D1) (antes 140) recebe -140 \Rightarrow 0.
Após a atualização, a nova solução (básica) é:
\begin{array}{c|ccc|c} & D1 & D2 & D3 & \text{Oferta}\\hline F1 & 0 & 0 & 140 & 140\\\ F2 & 180 & 70 & 0 & 250\\\ F3 & 0 & 150 & 130 & 280\\hline \text{Demanda} & 180 & 220 & 270 & \end{array}
Observação: (F1,D1) ficou com alocação zero; agora é não-básica e foi substituída por (F1,D3) 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):
\text{Custo novo} = 140\cdot 5 + 180\cdot 4 + 70\cdot 5 + 150\cdot 0 + 130\cdot 0.
Calcule: 140\cdot5=700,\\\ 180\cdot4=720,\\\ 70\cdot5=350. Soma: 700+720+350=1770. Então o custo diminuiu de 2050 para \,1770.

Passo 13

Verificação de otimalidade final pelo MODI na solução atual: obtemos os potenciais u_i,v_j usando as células básicas atuais (F1,D3),(F2,D1),(F2,D2),(F3,D2),(F3,D3). Defina u_1=0.
Resolvendo:
  • (F1,D3): u_1+v_3=5 \Rightarrow v_3=5.
  • (F3,D3): u_3+v_3=0 \Rightarrow u_3=-5.
  • (F3,D2): u_3+v_2=0 \Rightarrow v_2=5.
  • (F2,D2): u_2+v_2=5 \Rightarrow u_2=0.
  • (F2,D1): u_2+v_1=4 \Rightarrow v_1=4.
Potenciais: u_1=0,\\ u_2=0,\\ u_3=-5,\\ v_1=4,\\ v_2=5,\\ v_3=5.
Agora calculamos \Delta para as células não-básicas:
  • (F1,D1): c=6,\\ u_1+v_1=0+4=4 \Rightarrow \Delta=6-4=2\ge0.
  • (F1,D2): c=7,\\ u_1+v_2=0+5=5 \Rightarrow \Delta=7-5=2\ge0.
  • (F2,D3): c=9,\\ u_2+v_3=0+5=5 \Rightarrow \Delta=9-5=4\ge0.
Todos os \Delta_{ij}\ge0, 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: 0
Fábrica 1 para Depósito 2: 0
Fábrica 1 para Depósito 3: 140
Fábrica 2 para Depósito 1: 180
Fábrica 2 para Depósito 2: 70
Fábrica 2 para Depósito 3: 0
Custo total mínimo: 1770

Exercícios relacionados