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
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):
Ofertas (capacidades das fábricas):
.
Demandas (depósitos): .
Demandas (depósitos):
Verificação de balanço: soma ofertas
e soma demandas
. 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 -
(MODI).
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
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
para representar a quantidade enviada da fábrica para o depósito . Por exemplo é o fluxo Juarez→Frankfurt. - O custo total é
, onde são os custos da matriz. Nosso objetivo é atribuir valores 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
- usa uma solução básica viável e verifica otimalidade através de potenciais (por linhas) e (por colunas). Para cada célula não básica calcula-se . Se todos a solução é ótima; se existir 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:
-
Célula
: oferta Juarez , demanda Frankfurt . Aloco .
Resultado parcial:. Agora Juarez sobra , Frankfurt demanda . -
Juarez zerou, passo para a linha abaixo, célula
: oferta Seoul , demanda Frankfurt . Aloco .
. Agora Seoul sobra , Frankfurt demanda . -
Frankfurt zerou, passo para a coluna à direita (New York), célula
: oferta Seoul , demanda New York . Aloco .
. Seoul sobra , New York demanda . -
New York zerou, vou para Phoenix: célula
: oferta Seoul , demanda Phoenix . Aloco .
. Seoul sobra , Phoenix demanda . -
Seoul zerou, desço para TelAviv, mesma coluna Phoenix:
: oferta TelAviv , demanda Phoenix . Aloco .
. TelAviv sobra , Phoenix demanda . -
Phoenix zerou, vou para Yokohama na linha TelAviv:
: oferta TelAviv , demanda Yokohama . Aloco .
. TelAviv sobra , Yokohama demanda .
Todas demandas e ofertas satisfeitas. Solução básica (células com alocação):
Cálculo do custo total (soma
):
Somando:
.
Portanto, solução inicial (Canto Noroeste) tem custo total
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):
Alocações sequenciais:
-
custo : aloco . . Juarez 0, Phoenix demanda . -
custo : aloco . . Seoul 150, Yokohama 0. -
custo : aloco . . TelAviv 50, Frankfurt 0. -
custo : NY demanda , TelAviv oferta . Aloco . . TelAviv 0, NY demanda . -
Próximo custo relevante que ainda pode alocar é
custo ou custo mas Frankfurt já zerada; escolhemos custo : Phoenix demanda , Seoul tem . Aloco . . Seoul 50, Phoenix 0. -
Restante: NY demanda
, Seoul oferta . Só célula possível custo : aloco . . Seoul 0, NY 0.
Solução obtida (células básicas):
Cálculo do custo total:
Somando:
Portanto a solução inicial pelo método do Custo Mínimo tem custo total
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:
→ penalidade . - Seoul:
→ penalidade . - TelAviv:
→ penalidade .
Custos por coluna (ordenados) e penalidades:
- Frankfurt:
→ penalidade . - New York:
→ penalidade . - Phoenix:
→ penalidade . - Yokohama:
→ penalidade .
Maior penalidade é coluna Yokohama (15). Nessa coluna o menor custo é
com custo
. Aloco
.
Logo . Agora Seoul
restante, Yokohama
.
Logo
Removendo coluna Yokohama e recomputando penalidades:
Linhas (sem Yokohama):
- Juarez: custos
→ penalidade . - Seoul: custos
→ penalidade . - TelAviv: custos
→ penalidade .
Colunas restantes: Frankfurt (penalidade
), New York (penalidade
), Phoenix (penalidade
).
Maior penalidade agora é linha Juarez (14). Na linha Juarez o menor custo é
com custo
. Aloco
.
. Juarez
, Phoenix demanda agora
.
Removendo linha Juarez, restam linhas Seoul (150) e TelAviv (200), colunas Frankfurt (150), New York (100), Phoenix (100).
Recalculo penalidades:
- Seoul: custos
→ penalidade . - TelAviv: custos
→ penalidade .
Colunas: Frankfurt→ penalidade . New York → penalidade . Phoenix → penalidade .
Maior penalidade é New York coluna (7). Na coluna New York o menor custo é
custo
. Aloco
.
. TelAviv sobra
, New York
.
Removendo coluna New York; restam Seoul (150), TelAviv (100); colunas Frankfurt (150), Phoenix (100).
Penalidades:
- Seoul:
→ . - TelAviv:
→ . - Frankfurt:
→ . - Phoenix:
→ .
Escolho maior penalidade 4 (pode ser coluna Frankfurt ou linha TelAviv). Tomando a coluna Frankfurt (opção válida), menor custo em Frankfurt é
com custo
. Aloco
.
. TelAviv sobra
, Frankfurt demanda
.
Removendo linha TelAviv; resta apenas Seoul (150) para satisfazer Frankfurt
e Phoenix
. Aloco accordingly:
Solução Vogel (células básicas e alocações):
Cálculo do custo total:
Somando:
Portanto a solução inicial pelo método de Vogel tem custo total
Passo 9
Método
-
(MODI) — explicação do método e estratégia para checar otimalidade:
- Dada uma solução básica viável (com exatamente
células básicas, aqui ), atribuímos potenciais (para cada linha/fábrica) e (para cada coluna/depósito) de forma que para toda célula básica tenhamos . Isso é um sistema linear que podemos resolver atribuindo arbitrariamente um potencial (por exemplo ) e obtendo os demais. - Para cada célula não básica calculamos
. Se todos , a solução é ótima. Se existe , escolhemos a célula com 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 . - 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
-
sobre a solução de Vogel:
Solução básica (relembrando os pares básicos e custos):
Básicas e custos:
Básicas e custos:
Defino os potenciais
para linhas
e
para colunas
. Fixarei
(pode-se escolher qualquer referência).
Agora escrevo as equações
para cada célula básica e resolvo:
-
Para
: . Com segue . -
Para
: . Assim . -
Para
: . Logo . -
Para
: . Como , obtemos . -
Para
: . Assim . -
Para
: . Logo .
Resumo dos potenciais obtidos:
Agora calculo os
para todas as células não básicas:
Células não básicas e seus
:
Observação: todos os
calculados são
(valores
). Pelo critério do método
-
, 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
-
: 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):
Resposta
(a) Canto Noroeste:
Custo total
(b) Custo Mínimo:
Custo total
(c) Vogel:
Custo total
(d) Método
-
(MODI): a solução de Vogel é ótima (todos
). Solução ótima igual à de Vogel acima. Custo ótimo