Uma empresa tem 3 fábricas e 4 clientes, referentes a um determinado produto, e conhece-se os dados abaixo:
Fábrica
Capacidade mensal da produção
Custo de produção ($/unidade)
Cliente
Demanda mensal
Preço de venda ($/unidade)
\mathrm{F}_{1}
85
50
\mathrm{C}_{1}
100
100
\mathrm{F}_{2}
90
30
\mathrm{C}_{2}
80
110
\mathrm{F}_{3}
75
40
\mathrm{C}_{3}
20
105
\mathrm{C}_{4}
40
125
Total
250
Total
240
Conhecem-se os custos de se manter o produto em estoque ($/unidade estocada) em cada Fábrica:\1para estocagem na Fábrica 1, \2 para estocagem na Fábrica 2 e $3 para estocagem na Fábrica 3. Os custos de transporte ($/unidade) são:
Local de
Locais de Venda
\mathrm{C}_{1}
\mathrm{C}_{2}
\mathrm{C}_{3}
\mathrm{C}_{4}
\mathrm{~F}_{1}
43
57
33
60
\mathrm{~F}_{2}
30
49
25
47
\mathrm{~F}_{3}
44
58
33
64
Encontrar o programa de distribuição que proporcione lucro máximo. Formule o modelo de PL e aplique o Stepping Stone Algorithm. Inicialize o algoritmo pela Regra do canto Esquerdo.
Passo 1
Vou listar claramente o que o enunciado nos dá e o que ele pede (peguei todos os números do enunciado):
Fábricas (capacidades, custo de produção por unidade e custo de estocagem por unidade):
\mathrm{F}_1: capacidade 85, custo produção \$50/\text{un}, custo estocagem \$1/\text{un}.
\mathrm{F}_2: capacidade 90, custo produção \$30/\text{un}, custo estocagem \$2/\text{un}.
\mathrm{F}_3: capacidade 75, custo produção \$40/\text{un}, custo estocagem \$3/\text{un}.
Clientes (demandas e preço de venda por unidade):
\mathrm{C}_1: demanda 100, preço \$100/\text{un}.
\mathrm{C}_2: demanda 80, preço \$110/\text{un}.
\mathrm{C}_3: demanda 20, preço \$105/\text{un}.
\mathrm{C}_4: demanda 40, preço \$125/\text{un}.
Custos de transporte ($/unidade) da fábrica i para o cliente j:
Da \mathrm{F}_1: para \mathrm{C}_1, \mathrm{C}_2, \mathrm{C}_3, \mathrm{C}_4 são 43,57,33,60.
Da \mathrm{F}_2: 30,49,25,47.
Da \mathrm{F}_3: 44,58,33,64.
Totais: capacidade total 85+90+75=250, demanda total 100+80+20+40=240.
O enunciado pede:
Formular o modelo de Programação Linear (maximizar lucro) e
Aplicar o Stepping Stone Algorithm, iniciando pela Regra do Canto Esquerdo (Northwest corner rule), até obter a solução ótima.
Passo 2
Formulação do modelo (variáveis, objetivo e restrições).
Variáveis: seja x_{ij} a quantidade enviada da fábrica \mathrm{F}_i para o cliente \mathrm{C}_j, com i=1,2,3 e j=1,2,3,4.
Como a soma das capacidades é maior que a demanda, é possível produzir unidades que não sejam vendidas e fiquem em estoque. Para balancear o problema em transporte (Stepping Stone funciona em problema balanceado) eu incluo um cliente artificial “dummy” que absorve a produção não vendida. Para esse cliente fictício j = “D” a venda é zero e o envio para ele equivale a produzir e deixar estocado na fábrica — então o lucro por unidade enviada para o dummy será negativo (custo produção + custo de estocagem).
Objetivo: maximizar o lucro total. Para cada rota (i,j) o lucro unitário é\text{lucro}_{ij} = \text{preço}_j - \text{custo produção}_i - \text{transporte}_{ij}.Para o dummy temos \text{preço}_D=0 e \text{transporte}_{iD}=0, então\text{lucro}_{iD} = 0 - \text{custo produção}_i - \text{custo estocagem}_i = -(\text{custo produção}_i+\text{custo estocagem}_i).
Restrições:
Atender exatamente cada demanda real j=1,2,3,4:\sum_{i=1}^3 x_{ij} = \text{demanda}_j,\qquad j=1,\dots,4.
Não exceder capacidade de cada fábrica (a soma das saídas de i pode ir parcialmente para o dummy):\sum_{j=1}^{4} x_{ij} + x_{iD} \le \text{capacidade}_i,\qquad i=1,2,3.
Não-negatividade x_{ij}\ge0.
Observação didática rápida: é mais prático transformar esse problema de maximização do lucro em um problema de minimização de custo definindo
c_{ij} = -\text{lucro}_{ij}.
A solução que minimiza o custo total com esses c_{ij} maximiza o lucro original. O Stepping Stone é normalmente explicado para minimização, por isso eu vou trabalhar com c_{ij}.
Passo 3
Calcular lucros unitários \text{lucro}_{ij} e custos equivalentes c_{ij}=-\text{lucro}_{ij}. (Peguei preços, custos e transporte do enunciado.)
Agora os custos para minimizar (que são c_{ij}=-\text{lucro}_{ij}) tornam-se:
Tabela c_{ij} (minimização):
Da \mathrm{F}_1: c_{11}=-7,\; c_{12}=-3,\; c_{13}=-22,\; c_{14}=-15,\; c_{1D}=51.
Da \mathrm{F}_2: c_{21}=-40,\; c_{22}=-31,\; c_{23}=-50,\; c_{24}=-48,\; c_{2D}=32.
Da \mathrm{F}_3: c_{31}=-16,\; c_{32}=-12,\; c_{33}=-32,\; c_{34}=-21,\; c_{3D}=43.
Demanda do dummy D é igual à folga entre capacidade total e demanda total: 250-240=10.
Resumo: temos um problema de transporte balanceado com abastecimentos (85,90,75) e demandas (100,80,20,40,10) para (C_1,C_2,C_3,C_4,D), e custos c_{ij} listados acima.
Passo 4
Inicialização pelo Método do Canto Esquerdo (Northwest corner rule). Vou preencher as células seguindo a regra: começar em (\mathrm{F}_1,\mathrm{C}_1), alocar o máximo possível, depois avançar conforme esgotam linha/coluna.
Como lucro = - custo (pois c_{ij}=-lucro), o lucro correspondente é
\text{lucro inicial}=4630.
Passo 6
Explicando o Stepping Stone (o método que vamos aplicar): a ideia é avaliar, para cada célula vazia, quanto muda o custo total se eu inserir 1 unidade nessa célula e ajustar um ciclo fechado (loop) alternando sinais +,- entre células ocupadas. Para poupar trabalho manual repetitivo, é comum usar os potenciais u_i (para linhas) e v_j (para colunas) resolvendo u_i+v_j=c_{ij} nas células básicas; então a “oportunidade” (ou custo reduzido) de uma célula vazia (i,j) é
\Delta_{ij} = c_{ij} - (u_i+v_j).
Se \Delta_{ij} < 0 (minimização), existe uma possibilidade de diminuir o custo total alocando nessa célula (ou seja, melhorar a solução).
Se \Delta_{ij}\ge0 para todas as células vazias, a solução é ótima.
Vou aplicar esse procedimento: calcular u_i,v_j a partir da base atual e então os \Delta para as células vazias.
Passo 7
Cálculo dos potenciais (u_i,v_j) e \Delta na solução inicial.
Escolho arbitrariamente u_1=0 e uso as células ocupadas para encontrar os demais:
Da célula (1,1): u_1+v_1=c_{11}=-7 \Rightarrow v_1=-7.
Da célula (2,1): u_2+v_1=c_{21}=-40 \Rightarrow u_2=-40-v_1=-40-(-7)=-33.
De (2,2): u_2+v_2=c_{22}=-31 \Rightarrow v_2=-31-u_2=-31-(-33)=2.
De (3,2): u_3+v_2=c_{32}=-12 \Rightarrow u_3=-12-v_2=-12-2=-14.
De (3,3): u_3+v_3=c_{33}=-32 \Rightarrow v_3=-32-u_3=-32-(-14)=-18.
De (3,4): u_3+v_4=c_{34}=-21 \Rightarrow v_4=-21-u_3=-21-(-14)=-7.
De (3,D): u_3+v_D=c_{3D}=43 \Rightarrow v_D=43-u_3=43-(-14)=57.
Agora calculo \Delta_{ij}=c_{ij}-(u_i+v_j) para as células vazias; listo apenas as mais relevantes:
Interpretação: células com \Delta<0 indicam possibilidade de melhoria; as menores \Delta (mais negativas) são \Delta_{1,4}=-8 e \Delta_{2,4}=-8. Vou escolher (1,4) para a primeira melhoria (poderia escolher (2,4) também; ambos têm mesma melhoria teórica).
Passo 8
Primeiro pivô: melhorar pela célula vazia (1,4) com \Delta_{1,4}=-8.
Monte o ciclo fechado (Stepping Stone path) que começa em (1,4), passa por células ocupadas alternando + e - e fecha. Um ciclo possível:(1,4)\;(+)\;\rightarrow\;(1,1)\;(-)\;\rightarrow\;(2,1)\;(+)\;\rightarrow\;(2,2)\;(-)\;\rightarrow\;(3,2)\;(+)\;\rightarrow\;(3,4)\;(-)\rightarrow\text{volta }(1,4).
Nos lugares marcados - reduzimos alocações; nos + aumentamos. O máximo que podemos aumentar em (1,4) é o mínimo entre as quantidades nas posições marcadas -: mínimo de \{x_{11}=85,\; x_{22}=75,\; x_{34}=40\} = 40.
Atualizações (adicionando \theta=40 nas posições + e subtraindo \theta nas -):\begin{aligned} &x_{14}\gets 0+40=40,\\\ &x_{11}\gets 85-40=45,\\\ &x_{21}\gets 15+40=55,\\\ &x_{22}\gets 75-40=35,\\\ &x_{32}\gets 5+40=45,\\\ &x_{34}\gets 40-40=0\\ (\text{remove-se da base}). \end{aligned}
Variação do custo total: \Delta_{1,4}\cdot \theta = (-8)\cdot 40 = -320. Assim o custo total diminui de -4630 para -4950, e o lucro sobe de 4630 para 4950.
Passo 9
Recalcular potenciais u_i,v_j na nova base e procurar nova célula com \Delta<0.
Com a nova base ocupada (1,1),(1,4),(2,1),(2,2),(3,2),(3,3),(3,D), tomo u_1=0 e encontro:
O menor \Delta negativo agora é \Delta_{1D}=-6 (enviar unidades da \mathrm{F}_1 para o dummy, isto é, estocar em \mathrm{F}_1 em lugar de em \mathrm{F}_3 que antes armazenava). Vou fazer esse pivô.
Passo 10
Segundo pivô: célula vazia (1,D) com \Delta_{1D}=-6.
Encontrar ciclo fechado para (1,D). Um ciclo possível:(1,D)\;(+)\rightarrow(1,1)\;(-)\rightarrow(2,1)\;(+)\rightarrow(2,2)\;(-)\rightarrow(3,2)\;(+)\rightarrow(3,D)\;(-)\rightarrow\text{volta }(1,D).
Quantidades nas posições -: x_{11}=45,\; x_{22}=35,\; x_{3D}=10. Theta é o mínimo = 10.
Atualizações com \theta=10:\begin{aligned} &x_{1D}\gets 0+10=10,\\\ &x_{11}\gets 45-10=35,\\\ &x_{21}\gets 55+10=65,\\\ &x_{22}\gets 35-10=25,\\\ &x_{32}\gets 45+10=55,\\\ &x_{3D}\gets 10-10=0\\ (\text{remove-se da base}). \end{aligned}
Variação do custo: (-6)\cdot 10 = -60. Custo total fica -4950-60=-5010. Lucro sobe para 5010.
Passo 11
Recalcular u_i,v_j e buscar mais melhorias.
Base atual ocupada: (1,1),(1,4),(1,D),(2,1),(2,2),(3,2),(3,3). Tomo u_1=0 e obtenho:
Aqui vemos que todas as \Delta_{ij}\ge0 (algumas iguais a zero). Isso significa que NÃO há custo decrescente possível — a solução é ótima para o problema de minimização com nossa base atual. Zeros indicam alternativas ótimas equivalentes, não melhoria estrita.
Passo 12
Registrar solução final (todas as alocações finais) e calcular o lucro final.
As alocações finais obtidas nos passos de pivô são:
Conclusão: a solução é ótima (Stepping Stone deu \Delta_{ij}\ge0 para todas as células vazias) e o lucro máximo é \$5135 mensais com a distribuição encontrada.
Dica prática para a prova: no Stepping Stone é conveniente usar as potenciais u_i,v_j (sistema u_i+v_j=c_{ij}) para calcular \Delta rapidamente; e sempre rodar pivôs com \theta igual ao menor dos ocupados com sinal - no ciclo. Se a soma dos suprimentos for maior que a demanda, usar um cliente dummy com custo igual a produção+estocagem do respectivo fornecedor equilibra o problema sem forçar produzir além do que é lucrativo.