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: \1 para 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.)
  • Fórmula usada: \text{lucro}_{ij} = \text{preço}_j - \text{custo\_produção}_i - \text{transporte}_{ij}ççã.
  • Cálculo (tabela dos lucros unitários):
Da \mathrm{F}_1:
\begin{array}{l} \text{lucro}_{11}=100-50-43=7,\\\ \text{lucro}_{12}=110-50-57=3,\\\ \text{lucro}_{13}=105-50-33=22,\\\ \text{lucro}_{14}=125-50-60=15. \end{array}
Da \mathrm{F}_2:
\begin{array}{l} \text{lucro}_{21}=100-30-30=40,\\\ \text{lucro}_{22}=110-30-49=31,\\\ \text{lucro}_{23}=105-30-25=50,\\\ \text{lucro}_{24}=125-30-47=48. \end{array}
Da \mathrm{F}_3:
\begin{array}{l} \text{lucro}_{31}=100-40-44=16,\\\ \text{lucro}_{32}=110-40-58=12,\\\ \text{lucro}_{33}=105-40-33=32,\\\ \text{lucro}_{34}=125-40-64=21. \end{array}
  • Para o cliente dummy D (estocagem) o lucro por unidade enviada de \mathrm{F}_i é
\text{lucro}_{iD} = -(\text{custo produção}_i+\text{custo estocagem}_i).çã
Assim:
\text{lucro}_{1D}=-(50+1)=-51,\quad \text{lucro}_{2D}=-(30+2)=-32,\quad \text{lucro}_{3D}=-(40+3)=-43.
  • 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.
Passo a passo da alocação:
  • Em (1,1): alocar min(capacidade \mathrm{F}_1=85, demanda \mathrm{C}_1=100) = 85. Resta demanda \mathrm{C}_1=15, \mathrm{F}_1 esgota.
  • Ir para (2,1): alocar min( 90,\;15) = 15. Resta \mathrm{F}_2=75, \mathrm{C}_1 satisfeita.
  • Ir para (2,2): alocar min( 75,\;80) = 75. Resta \mathrm{C}_2=5, \mathrm{F}_2 esgota.
  • Ir para (3,2): alocar min( 75,\;5) = 5. Resta \mathrm{F}_3=70, \mathrm{C}_2 satisfeita.
  • Ir para (3,3): alocar min( 70,\;20) = 20. Resta \mathrm{F}_3=50, \mathrm{C}_3 satisfeita.
  • Ir para (3,4): alocar min( 50,\;40) = 40. Resta \mathrm{F}_3=10, \mathrm{C}_4 satisfeita.
  • Resta demandar D = 10; alocar (3,D)=10. Agora todas demandas e capacidades balanceiam.
Assim a solução inicial (canto esquerdo) tem as alocações:
\begin{array}{l} x_{11}=85,\; x_{21}=15,\; x_{22}=75,\; x_{32}=5,\\\ x_{33}=20,\; x_{34}=40,\; x_{3D}=10, \end{array}
todas as outras x_{ij}=0.

Passo 5

Custo total da solução inicial (lembrando que estamos minimizando \sum c_{ij} x_{ij}; lucro será o negativo desse valor).
Calcular a contribuição de cada alocação usando c_{ij} (peguei c_{ij} da tabela do Passo 3):
\begin{aligned} &x_{11}=85\Rightarrow 85\cdot c_{11}=85\cdot(-7)=-595,\\\ &x_{21}=15\Rightarrow 15\cdot(-40)=-600,\\\ &x_{22}=75\Rightarrow 75\cdot(-31)=-2325,\\\ &x_{32}=5\Rightarrow 5\cdot(-12)=-60,\\\ &x_{33}=20\Rightarrow 20\cdot(-32)=-640,\\\ &x_{34}=40\Rightarrow 40\cdot(-21)=-840,\\\ &x_{3D}=10\Rightarrow 10\cdot 43=430. \end{aligned}
Somando:
\text{custo inicial}=-595-600-2325-60-640-840+430=-4630.
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:
\begin{aligned} &\Delta_{1,2}= -3 - (0+2) = -5,\\\ &\Delta_{1,3}= -22 - (0-18) = -4,\\\ &\Delta_{1,4}= -15 - (0-7) = -8,\\\ &\Delta_{1D}= 51 - (0+57) = -6,\\\ &\Delta_{2,3}= -50 - (-33-18) = 1,\\\ &\Delta_{2,4}= -48 - (-33-7) = -8,\\\ &\Delta_{3,1}= -16 - (-14-7) = 5. \end{aligned}
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:
\begin{aligned} &v_1=-7,\quad u_2=-33,\quad v_2=2,\quad u_3=-14,\\\ &v_3=-18,\quad v_4=-15,\quad v_D=57. \end{aligned}
Calculo alguns \Delta:
\begin{aligned} &\Delta_{1,2}=-3-(0+2)=-5,\\\ &\Delta_{1,3}=-22-(0-18)=-4,\\\ &\Delta_{1D}=51-(0+57)=-6,\\\ &\Delta_{2,3}=-50-(-33-18)=1,\\\ &\Delta_{2,4}=-48-(-33-15)=0,\\\ &\Delta_{3,1}=-16-(-14-7)=5. \end{aligned}
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:
\begin{aligned} &v_1=-7,\quad v_2=-3\\ (\text{pois }c_{12}=-3),\quad v_4=-15,\quad v_D=51,\\\ &u_2=-33,\quad u_3=-9,\quad v_3=-23. \end{aligned}
Agora calculo \Delta para células vazias restantes:
\begin{aligned} &\Delta_{1,3}=-22-(0-23)=1,\\\ &\Delta_{2,2}=-31-(-33-3)=5,\\\ &\Delta_{2,3}=-50-(-33-23)=6,\\\ &\Delta_{2,4}=-48-(-33-15)=0,\\\ &\Delta_{3,1}=-16-(-9-7)=0,\\\ &\Delta_{3,4}=-21-(-9-15)=3,\\\ &\Delta_{3D}=43-(-9+51)=1. \end{aligned}
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:
\begin{aligned} &x_{11}=10,\quad x_{12}=25,\quad x_{13}=0,\quad x_{14}=40,\quad x_{1D}=10,\\\ &x_{21}=90,\quad x_{22}=0,\quad x_{23}=0,\quad x_{24}=0,\quad x_{2D}=0,\\\ &x_{31}=0,\quad x_{32}=55,\quad x_{33}=20,\quad x_{34}=0,\quad x_{3D}=0. \end{aligned}
Verificação rápida das somas:
  • Linhas (capacidades): \mathrm{F}_1 envia 10+25+0+40+10=85, \mathrm{F}_2 envia 90, \mathrm{F}_3 envia 55+20=75. OK.
  • Colunas (demandas): \mathrm{C}_1 recebe 10+90+0=100, \mathrm{C}_2 recebe 25+0+55=80, \mathrm{C}_3 recebe 20, \mathrm{C}_4 recebe 40, dummy recebe 10. OK.
Agora calcule o lucro total usando as parcelas de lucro unitário que calculamos no Passo 3:
\begin{aligned} &\text{Total lucro} = \sum_{i,j} \text{lucro}_{ij}\, x_{ij} \\\ &= \underbrace{10\cdot 7}_{F_1C_1} + \underbrace{25\cdot 3}_{F_1C_2} + \underbrace{40\cdot 15}_{F_1C_4} + \underbrace{10\cdot(-51)}_{F_1D}\\\ &\quad + \underbrace{90\cdot 40}_{F_2C_1} + \underbrace{55\cdot 12}_{F_3C_2} + \underbrace{20\cdot 32}_{F_3C_3}. \end{aligned}
Calculemos termo a termo:
\begin{aligned} &F_1\text{ contribui }=10\cdot7+25\cdot3+40\cdot15+10\cdot(-51)=70+75+600-510=235,\\\ &F_2\text{ contribui }=90\cdot40=3600,\\\ &F_3\text{ contribui }=55\cdot12+20\cdot32=660+640=1300. \end{aligned}
Somando:
\text{lucro total} =235+3600+1300=5135.
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.

Resposta

x_{11}=10
x_{12}=25
x_{13}=0
x_{14}=40
x_{1D}=10
x_{21}=90
x_{22}=0
x_{23}=0
x_{24}=0
x_{2D}=0
x_{31}=0
x_{32}=55
x_{33}=20
x_{34}=0
x_{3D}=0
Lucro máximo =\$5135.

Exercícios relacionados