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 200.000,350.000 e 150.000 unidades respectivamente. Há três centros mundiais de distribuição (N, S, E e W) com capacidades de distribuição de 100.000,140.000,300.000 e 100.000 unidades respectivamente. Os custos de transporte unitário são
\mathbf{N} \mathbf{S} \mathbf{E} \mathbf{W}
\mathbf{A} 16 13 22 17
\mathbf{B} 14 13 X 15
\mathbf{C} 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.

Passo 1

O enunciado pede: encontrar o plano de transporte das fábricas A,B,C para os centros de distribuição N,S,E,W que minimize o custo total, sabendo que a fábrica B não pode enviar para E. Dados fornecidos:
  • Capacidades das fábricas (oferta):
\text{A: }200000,\quad \text{B: }350000,\quad \text{C: }150000.
  • Capacidades (demandas) dos centros:
\text{N: }100000,\quad \text{S: }140000,\quad \text{E: }300000,\quad \text{W: }100000.
  • Custos unitários de transporte (em cada célula da tabela):
\begin{array}{c|cccc} & N & S & E & W\\hline A & 16 & 13 & 22 & 17\\\ B & 14 & 13 & \text{(impossível)} & 15\\\ C & 9 & 20 & 23 & 10 \end{array}í
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 B\to E?

Passo 2

Verificação de balanceamento da tabela e tratamento de rota proibida:
  • Soma das ofertas:
200000+350000+150000=700000.
  • Soma das demandas:
100000+140000+300000+100000=640000.
Há excesso de oferta de 700000-640000=60000 unidades. Para transformar o problema numérico em balanceado, adicionamos uma demanda fictícia D de \;60000 unidades com custo unitário zero a partir de qualquer fábrica (células A\!-\!D,B\!-\!D,C\!-\!D custo 0). A rota proibida B\to E é tratada impondo x_{B,E}=0 (ou custo muito grande), portanto não estará disponível.
Após adicionar D, temos demandas totais igualando a oferta total:
100000+140000+300000+100000+60000=700000.

Passo 3

Escolha do método e estratégia intuitiva (explicada passo a passo, sem pular etapas):
  • Observação importante (decisiva): como B não pode enviar para E, todas as 300000 unidades exigidas por E só podem ser supridas por A e C. As ofertas de A e C somam
200000+150000=350000,
ou seja, há capacidade suficiente, mas isso impõe uma restrição: x_{A,E}+x_{C,E}=300000 com 0\le x_{A,E}\le200000 e 0\le x_{C,E}\le150000. Para minimizar custo em uma coluna onde só há duas fontes possíveis, compare os custos unitários: c_{A,E}=22 e c_{C,E}=23. Como 22<23, é mais barato deslocar o máximo possível de E para A (respeitando a oferta de A). Assim, convém escolher x_{A,E} o mais alto possível, até 200000, e o restante x_{C,E}=100000 (porque 200000+100000=300000). 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 E por A e C, 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 E:
  1. Atender E com o máximo possível de A (menor custo 22):
x_{A,E} = 200000 \quad(\text{toda a oferta de }A).
  1. Como E exige 300000, e A deu 200000, o restante vira de C:
x_{C,E} = 300000-200000=100000.
Após essas alocações, as ofertas remanescentes são:
\text{A remanescente: }200000-200000=0,\qquad \text{C remanescente: }150000-100000=50000,\qquad \text{B remanescente: }350000.

Passo 5

Atender as outras demandas com as ofertas remanescentes, escolhendo custos menores e respeitando capacidades:
Demandas restantes:
N:100000,\quad S:140000,\quad W:100000,\quad D:60000.
Custos relevantes (somente para fábricas com oferta remanescente):
  • A tem oferta 0 — não pode enviar mais.
  • B (oferta 350000): custos N:14,\\ S:13,\\ W:15,\\ D:0.
  • C (oferta 50000): custos N:9,\\ S:20,\\ W:10,\\ D:0.
Procedimento lógico:
  • C tem custos muito baixos para N e W ( 9 e 10). Mas lembre-se que C já forneceu 100000 para E e só tem 50000 sobrando; escolha onde aplicar esses 50000 de forma a reduzir custo total máximo. O menor custo é C\to N com 9, então alocamos:
x_{C,N}=50000.
  • Atualiza demanda N: 100000-50000=50000 ainda faltando.
  • Agora as ofertas remanescentes: B continua com 350000 (não usada ainda), C com 0.
  • As demandas restantes são exatamente: N:50000,\\ S:140000,\\ W:100000,\\ D:60000. A soma é 350000, que coincide com a oferta remanescente de B. Como B é a única fábrica com oferta restante, ela atenderá todas essas demandas (e B\to E permanece proibido, mas não precisamos de B\to E já que E está coberto). Portanto:
x_{B,N}=50000,\quad x_{B,S}=140000,\quad x_{B,W}=100000,\quad x_{B,D}=60000.
Agora verificamos todas as igualdades oferta = soma saídas e demanda = soma entradas:
  • Para A: x_{A,E}=200000 (soma saídas =200000= oferta).
  • Para B: 50000+140000+100000+60000=350000.
  • Para C: x_{C,E}+x_{C,N}=100000+50000=150000.
  • Demandas: N:50000+50000=100000,\\ S:140000,\\ E:200000+100000=300000,\\ W:100000,\\ D:60000. 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 \text{custo unitário}\times \text{quantidade}á:
  • A\to E:\;22\times 200000 = 4400000.
  • C\to E:\;23\times 100000 = 2300000.
  • C\to N:\;9\times 50000 = 450000.
  • B\to N:\;14\times 50000 = 700000.
  • B\to S:\;13\times 140000 = 1820000.
  • B\to W:\;15\times 100000 = 1500000.
  • B\to D\\ (\text{demanda fictícia}):\;0\times 60000 = 0.í
Somando tudo:
4400000+2300000+450000+700000+1820000+1500000+0 = 11170000.
Portanto o custo total deste plano é \;11170000 (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 u_i para linhas (fábricas) e v_j para colunas (centros), tais que para toda célula básica (usada) vale
u_i+v_j=c_{ij}.
Escolhemos uma base de m+n-1 alocações básicas. As células básicas aqui (com alocações positivas) são exatamente 7, que é 3+5-1:
(A,E),\\ (C,E),\\ (C,N),\\ (B,N),\\ (B,S),\\ (B,W),\\ (B,D).
Fixamos arbitrariamente u_A=0 (ponto de partida). A partir das igualdades:
  • u_A+v_E=22 \Rightarrow v_E=22.
  • u_C+v_E=23 \Rightarrow u_C=1.
  • u_C+v_N=9 \Rightarrow v_N=8.
  • u_B+v_N=14 \Rightarrow u_B=6.
  • u_B+v_S=13 \Rightarrow v_S=7.
  • u_B+v_W=15 \Rightarrow v_W=9.
  • u_B+v_D=0 \Rightarrow v_D=-6.
Agora calculamos os custos reduzidos (custo marginal) para todas as células não básicas (i,j):
\text{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.
Calculamos rapidamente os não básicos principais:
  • \Delta_{A,N}=16-(u_A+v_N)=16-(0+8)=8\ge0.
  • \Delta_{A,S}=13-(0+7)=6\ge0.
  • \Delta_{A,W}=17-(0+9)=8\ge0.
  • \Delta_{C,W}=10-(u_C+v_W)=10-(1+9)=0\ge0.
  • \Delta_{C,S}=20-(1+7)=12\ge0.
  • \Delta_{C,D}=0-(1-6)=5\ge0.
  • A célula proibida B\to E é inatingível (imposta como proibida).
Todos os \Delta_{ij} 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

A\to E:\;200000
B\to N:\;50000
B\to S:\;140000
B\to W:\;100000
B\to D\\ (\text{demanda fictícia}):\;60000í
C\to E:\;100000
C\to N:\;50000
Custo mínimo total: \;11170000

Exercícios relacionados