Uma companhia faz esquis em 3 fábricas através do mundo. As fábricas suprem 4 depósitos que distribuem os esquis diretamente às lojas. O problema é achar quantos pares de esquis devem ser transportados de cada fábrica para os vários depósitos para minimizar o custo total
a) Ache a solução inicial pelo método do Canto Noroeste
b) Ache a solução inicial pelo método do Custo Mínimo
c) Ache a solução inicial pelo método de Vogel
d) Ache a solução do problema pelo método u-v
Fábr Depósito Frankfurt New York Phoenix Yokohama Capac. da fábrica
Juarez 19 17 3 21 100
Seoul 15 21 18 6 300
TelAviv 11 14 15 22 200
Demanda 150 100 200 150 600

Passo 1

O enunciado pede que determinemos quantos pares de esquis devem ser transportados de cada fábrica para cada depósito de forma a minimizar o custo total. As informações dadas são as seguintes.
Custos unitários (matriz custo):
\begin{array}{c|cccc} & \text{Frankfurt} & \text{New York} & \text{Phoenix} & \text{Yokohama} \\\ \hline \text{Juarez} & 19 & 17 & 3 & 21 \\\ \text{Seoul} & 15 & 21 & 18 & 6 \\\ \text{TelAviv} & 11 & 14 & 15 & 22 \end{array}
Ofertas (capacidades das fábricas): \text{Juarez}=100,\\ \text{Seoul}=300,\\ \text{TelAviv}=200.
Demandas (depósitos): \text{Frankfurt}=150,\\ \text{New York}=100,\\ \text{Phoenix}=200,\\ \text{Yokohama}=150.
Verificação de balanço: soma ofertas 100+300+200=600 e soma demandas 150+100+200+150=600. São iguais, portanto o problema está balanceado e existe solução viável que usa exatamente todas as ofertas e satisfaça todas as demandas.
As tarefas pedidas:
a) solução inicial pelo método do Canto Noroeste;
b) solução inicial pelo método do Custo Mínimo;
c) solução inicial pelo método de Vogel;
d) solução final (ótima) pelo método u- v (MODI).

Passo 2

Breve explicação prática dos métodos e das notações que vou usar (aula-mão-na-massa antes de resolver):
  • Vou usar variáveis x_{i,j} para representar a quantidade enviada da fábrica i para o depósito j. Por exemplo x_{\text{Juarez},\text{Frankfurt}} é o fluxo Juarez→Frankfurt.
  • O custo total é \sum_{i}\sum_{j} c_{ij}x_{ij}, onde c_{ij} são os custos da matriz. Nosso objetivo é atribuir valores x_{ij} respeitando as ofertas e demandas e minimizando esse somatório.
  • Cada método gera uma solução inicial (básica viável). O método u- v usa uma solução básica viável e verifica otimalidade através de potenciais u_i (por linhas) e v_j (por colunas). Para cada célula não básica calcula-se \Delta_{ij}=c_{ij}-(u_i+v_j). Se todos \Delta_{ij}\ge 0 a solução é ótima; se existir \Delta_{ij}<0 podemos melhorar fazendo um ciclo fechado e ajustando quantidades.
Agora aplico cada método passo a passo mostrando alocações e cálculos de custo.

Passo 3

Canto Noroeste — explicação do método:
  • Começamos na célula no canto superior esquerdo (Juarez–Frankfurt). Alocamos o máximo possível sem violar oferta ou demanda (mínimo entre oferta restante da linha e demanda restante da coluna).
  • Quando uma oferta ou demanda zera, movemo-nos para a célula à direita (se a oferta zerou) ou abaixo (se a demanda zerou), e repetimos até preencher todas as demandas.
    Vou aplicar exatamente esse procedimento.

Passo 4

Canto Noroeste — aplicação passo a passo e resultado:
  1. Célula (\text{Juarez},\text{Frankfurt}): oferta Juarez =100, demanda Frankfurt =150. Aloco \min(100,150)=100.
    Resultado parcial: x_{\text{Juarez},\text{Frankfurt}}=100. Agora Juarez sobra 0, Frankfurt demanda 150-100=50.
  2. Juarez zerou, passo para a linha abaixo, célula (\text{Seoul},\text{Frankfurt}): oferta Seoul =300, demanda Frankfurt =50. Aloco \min(300,50)=50.
    x_{\text{Seoul},\text{Frankfurt}}=50. Agora Seoul sobra 250, Frankfurt demanda 0.
  3. Frankfurt zerou, passo para a coluna à direita (New York), célula (\text{Seoul},\text{New York}): oferta Seoul =250, demanda New York =100. Aloco \min(250,100)=100.
    x_{\text{Seoul},\text{New York}}=100. Seoul sobra 150, New York demanda 0.
  4. New York zerou, vou para Phoenix: célula (\text{Seoul},\text{Phoenix}): oferta Seoul =150, demanda Phoenix =200. Aloco \min(150,200)=150.
    x_{\text{Seoul},\text{Phoenix}}=150. Seoul sobra 0, Phoenix demanda 200-150=50.
  5. Seoul zerou, desço para TelAviv, mesma coluna Phoenix: (\text{TelAviv},\text{Phoenix}): oferta TelAviv =200, demanda Phoenix =50. Aloco \min(200,50)=50.
    x_{\text{TelAviv},\text{Phoenix}}=50. TelAviv sobra 150, Phoenix demanda 0.
  6. Phoenix zerou, vou para Yokohama na linha TelAviv: (\text{TelAviv},\text{Yokohama}): oferta TelAviv =150, demanda Yokohama =150. Aloco \min(150,150)=150.
    x_{\text{TelAviv},\text{Yokohama}}=150. TelAviv sobra 0, Yokohama demanda 0.
Todas demandas e ofertas satisfeitas. Solução básica (células com alocação):
\begin{aligned} x_{\text{Juarez},\text{Frankfurt}}&=100,\\\ x_{\text{Seoul},\text{Frankfurt}}&=50,\\\ x_{\text{Seoul},\text{New York}}&=100,\\\ x_{\text{Seoul},\text{Phoenix}}&=150,\\\ x_{\text{TelAviv},\text{Phoenix}}&=50,\\\ x_{\text{TelAviv},\text{Yokohama}}&=150. \end{aligned}
Cálculo do custo total (soma c_{ij}x_{ij}):
\begin{aligned} 100\cdot 19 &= 1900,\\\\ 50\cdot 15 &= 750,\\\\ 100\cdot 21 &= 2100,\\\\ 150\cdot 18 &= 2700,\\\\ 50\cdot 15 &= 750,\\\\ 150\cdot 22 &= 3300. \end{aligned}
Somando: 1900+750+2100+2700+750+3300 = 11500.
Portanto, solução inicial (Canto Noroeste) tem custo total \;11500.

Passo 5

Método do Custo Mínimo — explicação do método:
  • Em cada passo escolhemos a célula com menor custo unitário dentre as ainda disponíveis. Alocamos o máximo possível naquela célula (mínimo entre oferta restante e demanda restante). Depois atualizamos oferta/demanda e repetimos, sempre ignorando linhas/colunas já esgotadas.
  • É um método guloso que muitas vezes dá boa solução inicial.
Agora aplico o procedimento.

Passo 6

Custo Mínimo — aplicação ordenando custos e alocando:
Ordenando custos (do menor ao maior):
\text{Juarez–Phoenix }(3),\\ \text{Seoul–Yokohama }(6),\\ \text{TelAviv–Frankfurt }(11),\\ \text{TelAviv–NewYork }(14),\\ \text{Seoul–Frankfurt }(15),\\ \text{TelAviv–Phoenix }(15),\\ \dots
Alocações sequenciais:
  1. (\text{Juarez},\text{Phoenix}) custo 3: aloco \min(100,200)=100. x_{\text{Juarez},\text{Phoenix}}=100. Juarez 0, Phoenix demanda 100.
  2. (\text{Seoul},\text{Yokohama}) custo 6: aloco \min(300,150)=150. x_{\text{Seoul},\text{Yokohama}}=150. Seoul 150, Yokohama 0.
  3. (\text{TelAviv},\text{Frankfurt}) custo 11: aloco \min(200,150)=150. x_{\text{TelAviv},\text{Frankfurt}}=150. TelAviv 50, Frankfurt 0.
  4. (\text{TelAviv},\text{New York}) custo 14: NY demanda 100, TelAviv oferta 50. Aloco \min(50,100)=50. x_{\text{TelAviv},\text{New York}}=50. TelAviv 0, NY demanda 50.
  5. Próximo custo relevante que ainda pode alocar é (\text{Seoul},\text{Phoenix}) custo 18 ou (\text{Seoul},\text{Frankfurt}) custo 15 mas Frankfurt já zerada; escolhemos (\text{Seoul},\text{Phoenix}) custo 18: Phoenix demanda 100, Seoul tem 150. Aloco 100. x_{\text{Seoul},\text{Phoenix}}=100. Seoul 50, Phoenix 0.
  6. Restante: NY demanda 50, Seoul oferta 50. Só célula possível (\text{Seoul},\text{New York}) custo 21: aloco 50. x_{\text{Seoul},\text{New York}}=50. Seoul 0, NY 0.
Solução obtida (células básicas):
\begin{aligned} x_{\text{Juarez},\text{Phoenix}}&=100,\\\ x_{\text{Seoul},\text{Yokohama}}&=150,\\\ x_{\text{TelAviv},\text{Frankfurt}}&=150,\\\ x_{\text{TelAviv},\text{New York}}&=50,\\\ x_{\text{Seoul},\text{Phoenix}}&=100,\\\ x_{\text{Seoul},\text{New York}}&=50. \end{aligned}
Cálculo do custo total:
\begin{aligned} 100\cdot 3 &= 300,\\\\ 150\cdot 6 &= 900,\\\\ 150\cdot 11 &= 1650,\\\\ 50\cdot 14 &= 700,\\\\ 100\cdot 18 &= 1800,\\\\ 50\cdot 21 &= 1050. \end{aligned}
Somando: 300+900+1650+700+1800+1050 = 6400.
Portanto a solução inicial pelo método do Custo Mínimo tem custo total \;6400.

Passo 7

Método de Vogel — explicação do método (VAM):
  • Para cada linha e coluna calculamos uma “penalidade” que é a diferença entre os dois menores custos daquela linha/coluna. A penalidade indica o “custo de não usar” a célula de menor custo.
  • Em cada passo escolhe-se a linha ou coluna com maior penalidade e dentro dela aloca-se na célula com custo mínimo disponível. Atualiza-se ofertas/demandas, elimina-se linhas/colunas esgotadas e recomputa-se penalidades.
  • Geralmente dá uma excelente solução inicial.
Vou aplicar passo a passo.

Passo 8

Vogel — aplicação passo a passo e resultado:
Custos iniciais por linha (ordenados) e penalidades:
  • Juarez: [3,17,19,21] → penalidade 17-3=14.
  • Seoul: [6,15,18,21] → penalidade 15-6=9.
  • TelAviv: [11,14,15,22] → penalidade 14-11=3.
Custos por coluna (ordenados) e penalidades:
  • Frankfurt: [11,15,19] → penalidade 15-11=4.
  • New York: [14,17,21] → penalidade 17-14=3.
  • Phoenix: [3,15,18] → penalidade 15-3=12.
  • Yokohama: [6,21,22] → penalidade 21-6=15.
Maior penalidade é coluna Yokohama (15). Nessa coluna o menor custo é (\text{Seoul},\text{Yokohama}) com custo 6. Aloco \min(300,150)=150.
Logo x_{\text{Seoul},\text{Yokohama}}=150. Agora Seoul =150 restante, Yokohama =0.
Removendo coluna Yokohama e recomputando penalidades:
Linhas (sem Yokohama):
  • Juarez: custos [3,17,19] → penalidade 17-3=14.
  • Seoul: custos [15,18,21] → penalidade 18-15=3.
  • TelAviv: custos [11,14,15] → penalidade 14-11=3.
Colunas restantes: Frankfurt (penalidade 4), New York (penalidade 3), Phoenix (penalidade 12).
Maior penalidade agora é linha Juarez (14). Na linha Juarez o menor custo é (\text{Juarez},\text{Phoenix}) com custo 3. Aloco \min(100,200)=100.
x_{\text{Juarez},\text{Phoenix}}=100. Juarez =0, Phoenix demanda agora 100.
Removendo linha Juarez, restam linhas Seoul (150) e TelAviv (200), colunas Frankfurt (150), New York (100), Phoenix (100).
Recalculo penalidades:
  • Seoul: custos [15,18,21] → penalidade 18-15=3.
  • TelAviv: custos [11,14,15] → penalidade 14-11=3.
    Colunas: Frankfurt [15,11] → penalidade 15-11=4. New York [21,14] → penalidade 21-14=7. Phoenix [18,15] → penalidade 18-15=3.
Maior penalidade é New York coluna (7). Na coluna New York o menor custo é (\text{TelAviv},\text{New York}) custo 14. Aloco \min(200,100)=100.
x_{\text{TelAviv},\text{New York}}=100. TelAviv sobra 100, New York =0.
Removendo coluna New York; restam Seoul (150), TelAviv (100); colunas Frankfurt (150), Phoenix (100).
Penalidades:
  • Seoul: [15,18] 18-15=3.
  • TelAviv: [11,15] 15-11=4.
  • Frankfurt: [15,11] 15-11=4.
  • Phoenix: [18,15] 18-15=3.
Escolho maior penalidade 4 (pode ser coluna Frankfurt ou linha TelAviv). Tomando a coluna Frankfurt (opção válida), menor custo em Frankfurt é (\text{TelAviv},\text{Frankfurt}) com custo 11. Aloco \min(100,\;150)=100.
x_{\text{TelAviv},\text{Frankfurt}}=100. TelAviv sobra 0, Frankfurt demanda 50.
Removendo linha TelAviv; resta apenas Seoul (150) para satisfazer Frankfurt =50 e Phoenix =100. Aloco accordingly:
x_{\text{Seoul},\text{Frankfurt}}=50 e x_{\text{Seoul},\text{Phoenix}}=100. Seoul fica 0, e tudo fecha.
Solução Vogel (células básicas e alocações):
\begin{aligned} x_{\text{Seoul},\text{Yokohama}}&=150,\\\ x_{\text{Juarez},\text{Phoenix}}&=100,\\\ x_{\text{TelAviv},\text{New York}}&=100,\\\ x_{\text{TelAviv},\text{Frankfurt}}&=100,\\\ x_{\text{Seoul},\text{Frankfurt}}&=50,\\\ x_{\text{Seoul},\text{Phoenix}}&=100. \end{aligned}
Cálculo do custo total:
\begin{aligned} 150\cdot 6 &= 900,\\\\ 100\cdot 3 &= 300,\\\\ 100\cdot 14 &= 1400,\\\\ 100\cdot 11 &= 1100,\\\\ 50\cdot 15 &= 750,\\\\ 100\cdot 18 &= 1800. \end{aligned}
Somando: 900+300+1400+1100+750+1800 = 6250.
Portanto a solução inicial pelo método de Vogel tem custo total \;6250.

Passo 9

Método u- v (MODI) — explicação do método e estratégia para checar otimalidade:
  • Dada uma solução básica viável (com exatamente m+n-1 células básicas, aqui 3+4-1=6), atribuímos potenciais u_i (para cada linha/fábrica) e v_j (para cada coluna/depósito) de forma que para toda célula básica (i,j) tenhamos c_{ij}=u_i+v_j. Isso é um sistema linear que podemos resolver atribuindo arbitrariamente um potencial (por exemplo u_{\text{Juarez}}=0) e obtendo os demais.
  • Para cada célula não básica calculamos \Delta_{ij}=c_{ij}-(u_i+v_j). Se todos \Delta_{ij}\ge 0, a solução é ótima. Se existe \Delta_{ij}<0, escolhemos a célula com \Delta mais negativo e formamos um ciclo fechado alternando sinais + e - sobre as células básicas envolvidas, ajustamos quantidades (aumentamos na célula escolhida e subtraímos por um valor mínimo em posições com sinal -) e repetimos até que todos \Delta\ge 0.
  • Vou aplicar MODI sobre a melhor solução inicial que obtivemos (Vogel), porque é boa para chegar rapidamente à solução ótima.

Passo 10

Aplicação do método u- v sobre a solução de Vogel:
Solução básica (relembrando os pares básicos e custos):
Básicas e custos:
\begin{aligned} x_{\text{Seoul},\text{Yokohama}}&=150\quad(c=6),\\\ x_{\text{Juarez},\text{Phoenix}}&=100\quad(c=3),\\\ x_{\text{TelAviv},\text{New York}}&=100\quad(c=14),\\\ x_{\text{TelAviv},\text{Frankfurt}}&=100\quad(c=11),\\\ x_{\text{Seoul},\text{Frankfurt}}&=50\quad(c=15),\\\ x_{\text{Seoul},\text{Phoenix}}&=100\quad(c=18). \end{aligned}
Defino os potenciais u_i para linhas \{\text{Juarez},\text{Seoul},\text{TelAviv}\} e v_j para colunas \{\text{Frankfurt},\text{New York},\text{Phoenix},\text{Yokohama}\}. Fixarei u_{\text{Juarez}}=0 (pode-se escolher qualquer referência).
Agora escrevo as equações c_{ij}=u_i+v_j para cada célula básica e resolvo:
  1. Para (\text{Juarez},\text{Phoenix}): 3 = u_{\text{Juarez}} + v_{\text{Phoenix}}. Com u_{\text{Juarez}}=0 segue v_{\text{Phoenix}}=3.
  2. Para (\text{Seoul},\text{Phoenix}): 18 = u_{\text{Seoul}} + v_{\text{Phoenix}}. Assim u_{\text{Seoul}} = 18 - v_{\text{Phoenix}} = 18-3 = 15.
  3. Para (\text{Seoul},\text{Frankfurt}): 15 = u_{\text{Seoul}} + v_{\text{Frankfurt}}. Logo v_{\text{Frankfurt}} = 15 - u_{\text{Seoul}} = 15 - 15 = 0.
  4. Para (\text{TelAviv},\text{Frankfurt}): 11 = u_{\text{TelAviv}} + v_{\text{Frankfurt}}. Como v_{\text{Frankfurt}}=0, obtemos u_{\text{TelAviv}} = 11.
  5. Para (\text{TelAviv},\text{New York}): 14 = u_{\text{TelAviv}} + v_{\text{NewYork}}. Assim v_{\text{NewYork}} = 14 - 11 = 3.
  6. Para (\text{Seoul},\text{Yokohama}): 6 = u_{\text{Seoul}} + v_{\text{Yokohama}}. Logo v_{\text{Yokohama}} = 6 - 15 = -9.
Resumo dos potenciais obtidos:
\begin{aligned} u_{\text{Juarez}}&=0,\quad u_{\text{Seoul}}=15,\quad u_{\text{TelAviv}}=11,\\\ v_{\text{Frankfurt}}&=0,\quad v_{\text{NewYork}}=3,\quad v_{\text{Phoenix}}=3,\quad v_{\text{Yokohama}}=-9. \end{aligned}
Agora calculo os \Delta_{ij}=c_{ij}-(u_i+v_j) para todas as células não básicas:
Células não básicas e seus \Delta:
\begin{aligned} \Delta_{\text{Juarez},\text{Frankfurt}} &= 19 - (0+0) = 19,\\\ \Delta_{\text{Juarez},\text{NewYork}} &= 17 - (0+3) = 14,\\\ \Delta_{\text{Juarez},\text{Yokohama}} &= 21 - (0-9) = 30,\\\ \Delta_{\text{Seoul},\text{NewYork}} &= 21 - (15+3) = 3,\\\ \Delta_{\text{TelAviv},\text{Phoenix}} &= 15 - (11+3) = 1,\\\ \Delta_{\text{TelAviv},\text{Yokohama}} &= 22 - (11-9) = 22 - 2 = 20. \end{aligned}
Observação: todos os \Delta_{ij} calculados são \ge 0 (valores 19,14,30,3,1,20). Pelo critério do método u- v, isso significa que não existe célula não básica com custo reduzido negativo, então a solução atual é ótima.
Conclusão do método u- v: a solução fornecida pelo método de Vogel já é ótima. Não é necessário realizar ciclos de melhoria.
Custo ótimo final (já calculado na Vogel): \;6250.

Resposta

(a) Canto Noroeste: x_{\text{Juarez},\text{Frankfurt}}=100,\;x_{\text{Seoul},\text{Frankfurt}}=50,\;x_{\text{Seoul},\text{New York}}=100,\;x_{\text{Seoul},\text{Phoenix}}=150,\;x_{\text{TelAviv},\text{Phoenix}}=50,\;x_{\text{TelAviv},\text{Yokohama}}=150. Custo total =11500.
(b) Custo Mínimo: x_{\text{Juarez},\text{Phoenix}}=100,\;x_{\text{Seoul},\text{Yokohama}}=150,\;x_{\text{TelAviv},\text{Frankfurt}}=150,\;x_{\text{TelAviv},\text{New York}}=50,\;x_{\text{Seoul},\text{Phoenix}}=100,\;x_{\text{Seoul},\text{New York}}=50. Custo total =6400.
(c) Vogel: x_{\text{Seoul},\text{Yokohama}}=150,\;x_{\text{Juarez},\text{Phoenix}}=100,\;x_{\text{TelAviv},\text{New York}}=100,\;x_{\text{TelAviv},\text{Frankfurt}}=100,\;x_{\text{Seoul},\text{Frankfurt}}=50,\;x_{\text{Seoul},\text{Phoenix}}=100. Custo total =6250.
(d) Método u- v (MODI): a solução de Vogel é ótima (todos \Delta_{ij}\ge 0). Solução ótima igual à de Vogel acima. Custo ótimo =6250.

Exercícios relacionados