Certa empresa do ramo de mármores, pedras e granitos possui um escritório central em Venâncio Aires e possui fábricas em Ametista do Sul, Soledade e em Bossoroca, com as seguintes capacidades de produção, respectivamente: 40; 100; e 10. Recentemente, a empresa recebeu um pedido para enviar pacotes com várias peças e pedras lapidadas para as cidades de Porto Alegre, Uruguaiana e Santa Maria, nas seguintes quantidades, respectivamente: \underline{50}; 40; e 60.
Os custos unitários de transporte, de cada fábrica para cada destino, são mostrados na tabela a seguir:
Porto Alegre Uruguaiana Santa Maria
Ametista do Sul 10 15 20
Soledade 12 25 18
Bossoroca 16 14 24
Pede-se: Determinar as quantidades que devem ser despachadas de cada fábrica para cada armazém de forma a minimizar o custo de transporte. Use o método de Vogel para realizar a solução.

Passo 1

O problema é um transporte balanceado com três fábricas (Ametista do Sul, Soledade e Bossoroca) e três destinos (Porto Alegre, Uruguaiana e Santa Maria). As capacidades e demandas são
\text{Suprimentos: }s_A=40,\;s_S=100,\;s_B=10,
\text{Demandas: }d_{PA}=50,\;d_{UR}=40,\;d_{SM}=60.
Os custos unitários c_{ij} (fábrica i para destino j) formam a matriz
\begin{pmatrix} 10 & 15 & 20\\\\ 12 & 25 & 18\\\\ 16 & 14 & 24 \end{pmatrix},
nas colunas Porto Alegre (PA), Uruguaiana (UR) e Santa Maria (SM).
Vamos obter uma solução inicial via método de Vogel, calculando penalidades e alocando sucessivamente.

Passo 2

Calculemos as penalidades iniciais (diferença entre os dois menores custos) em cada linha e coluna:
\begin{aligned} \text{Linha A: }&\{10,15,20\}\to 15-10=5,\\\ \text{Linha S: }&\{12,18,25\}\to 18-12=6,\\\ \text{Linha B: }&\{14,16,24\}\to 16-14=2,\\\ \text{Col PA: }&\{10,12,16\}\to 12-10=2,\\\ \text{Col UR: }&\{15,14,25\}\to 15-14=1,\\\ \text{Col SM: }&\{18,20,24\}\to 20-18=2. \end{aligned}
Maior penalidade é da linha Soledade (6). Nessa linha o menor custo é para PA ( c_{S,PA}=12).
Alocamos
x_{S,PA}=\min(s_S=100,\;d_{PA}=50)=50.
Atualizamos s_S\leftarrow50,\;d_{PA}\leftarrow0 e eliminamos a coluna PA.

Passo 3

Recalculamos penalidades sem PA:
\begin{aligned} \text{Linha A: }\{15,20\}\to5,\quad \text{Linha S: }\{25,18\}\to7,\quad \text{Linha B: }\{14,24\}\to10,\\\ \text{Col UR: }\{15,25,14\}\to1,\quad \text{Col SM: }\{20,18,24\}\to2. \end{aligned}
Maior penalidade é da linha Bossoroca (10). Menor custo nessa linha é para UR ( c_{B,UR}=14).
Alocamos
x_{B,UR}=\min(s_B=10,\;d_{UR}=40)=10.
Atualizamos s_B\leftarrow0,\;d_{UR}\leftarrow30 e eliminamos a linha B.

Passo 4

Agora só linhas A, S e colunas UR, SM:
\begin{aligned} \text{Linha A: }\{15,20\}\to5,\quad \text{Linha S: }\{25,18\}\to7,\\\ \text{Col UR: }\{15,25\}\to10,\quad \text{Col SM: }\{20,18\}\to2. \end{aligned}
Maior penalidade é da coluna UR (10). Nela o menor custo é em Ametista ( c_{A,UR}=15).
Alocamos
x_{A,UR}=\min(s_A=40,\;d_{UR}=30)=30.
Atualizamos s_A\leftarrow10,\;d_{UR}\leftarrow0 e eliminamos a coluna UR.

Passo 5

Restam as células A–SM e S–SM, com demandas d_{SM}=60, suprimentos s_A=10, s_S=50. Penalidade da coluna SM é 2.
Alocamos primeiro no menor custo que é Soledade–SM ( c_{S,SM}=18):
x_{S,SM}=\min(s_S=50,\;d_{SM}=60)=50.
Atualizamos s_S\leftarrow0,\;d_{SM}\leftarrow10 e eliminamos a linha S.

Passo 6

Só resta Ametista–SM com s_A=10, d_{SM}=10.
Alocamos
x_{A,SM}=10,
e assim zeramos todos os suprimentos e demandas.

Resposta

As quantidades despachadas x_{i,j} e o custo total são:
\begin{array}{c|ccc|c} & \text{PA} & \text{UR} & \text{SM} & \text{Suprimento}\\hline Ametista & 0 & 30 & 10 & 40\\\ Soledade & 50 & 0 & 50 & 100\\\ Bossoroca& 0 & 10 & 0 & 10\\hline \text{Demanda}&50&40&60&150 \end{array}
Custo total
50\cdot12+50\cdot18 +30\cdot15+10\cdot20 +10\cdot14 =600+900+450+200+140=2290.

Exercícios relacionados