MBA DE LOGÍSTICA | FCAP- UPE

11

Métodos Quantitativos Aplicados a Logística Métodos Quantitativos Aplicados a Logística

MBA DE LOGÍSTICA | FCAP- UPEMBA DE LOGÍSTICA | FCAP- UPE

Prof. Carlos Alberto Martins

22

- MÉTODOS QUANTITATIVOS -- MÉTODOS QUANTITATIVOS - Programação linear aplicada à LogísticaProgramação linear aplicada à Logística

Dado um sistema real,o modelo emprega símbolos matemáticos para representar Dado um sistema real,o modelo emprega símbolos matemáticos para representar as variáveis de decisão do sistema real.as variáveis de decisão do sistema real.

Essas variáveis são relacionadas por funções matemáticas que expressão o Essas variáveis são relacionadas por funções matemáticas que expressão o funcionamento do sistema. funcionamento do sistema.

A solução consiste em encontrar valores adequados das variáveis de decisão que A solução consiste em encontrar valores adequados das variáveis de decisão que otimizem o desempenho do sistema, segundo o critério desejado.otimizem o desempenho do sistema, segundo o critério desejado.

Modelos de programação linear são identificado pelas seguintes características:Modelos de programação linear são identificado pelas seguintes características:

a)a) Uma função objetiva de (maximização ou minimização) que deve ser Uma função objetiva de (maximização ou minimização) que deve ser otimizada.otimizada.

a)a) Um conjunto de equações e/ou inequações lineares (restrições)Um conjunto de equações e/ou inequações lineares (restrições)

a)a) As variáveis de decisão que são não negativas, ou seja,positivas ou nulas. As variáveis de decisão que são não negativas, ou seja,positivas ou nulas.

33

MÉTODOS QUANTITATIVOS -MÉTODOS QUANTITATIVOS - Programação linear aplicada à Logística – cont.Programação linear aplicada à Logística – cont.

Considere o modelo geral de programação linearConsidere o modelo geral de programação linear

Max.Z = cMax.Z = c11xx1 1 + c+ c22xx2 2 + .....+ c+ .....+ cnnxxnn,, s.a s.a

aa1111xx11 + a + a1212xx22 + ....+ a + ....+ a1n1n <= b <= b11

aa2121xx11 + a + a2222xx2 2 + .... + a+ .... + a2n 2n <= b<= b22

............................................................................................ aam1m1xx1 1 + a+ am2m2xx2 2 + ... + a+ ... + amnmnxxn n <= b<= bn n

xx1.1.>= 0 ; x>= 0 ; x22>=0; .....;x>=0; .....;xnn>=0>=0

Onde:Onde:

XXjj = nível de produção do produto j. ( j =1,2,...,n ) incógnitas do problema = nível de produção do produto j. ( j =1,2,...,n ) incógnitas do problemaCCjj = lucro ou custo do produto j. = lucro ou custo do produto j.bi = quantidade disponível do recurso i (bbi = quantidade disponível do recurso i (b i i >= 0)>= 0)aij =quantidade de recurso i consumida na produção de uma unidade do produtoaij =quantidade de recurso i consumida na produção de uma unidade do produto j. j.

44

Programação linear aplicada à Logística – cont.Programação linear aplicada à Logística – cont.

construção de modelos construção de modelos Exercício1: A Cia forjas minas produz dois produtos A e B que utilizam os mesmos Exercício1: A Cia forjas minas produz dois produtos A e B que utilizam os mesmos recursos produtivos:matéria-prima, forja e polimento. recursos produtivos:matéria-prima, forja e polimento. Cada unidade do produto A requer 4 horas de forjaria e 2 horas de polimento, Cada unidade do produto A requer 4 horas de forjaria e 2 horas de polimento, enquanto que cada unidade do produto B exige 2 horas de forjaria e 3 horas de enquanto que cada unidade do produto B exige 2 horas de forjaria e 3 horas de polimento.A capacidade produtiva equivalente diária é de 220 horas na seção de polimento.A capacidade produtiva equivalente diária é de 220 horas na seção de forjaria e 250 horas no polimento.O preço unitário de venda do produto A é de forjaria e 250 horas no polimento.O preço unitário de venda do produto A é de R$1.900,00 e do produto B é R$2.100,00 e toda a produção tem mercado garantido. R$1.900,00 e do produto B é R$2.100,00 e toda a produção tem mercado garantido. Pede-se:Pede-se:a)a)Formule o modelo matemático que maximize a receita da empresa;Formule o modelo matemático que maximize a receita da empresa;b)b)Determine a solução pelo método gráfico. Determine a solução pelo método gráfico.

Solução – O cSolução – O ca a e ce cbb são respectivamente os preços de venda dos produtos A e B são respectivamente os preços de venda dos produtos A e B aa1111 , a , a1212 , a , a21 21 e ae a22 22 são as horas de forjaria e polimento respectivamente. são as horas de forjaria e polimento respectivamente. bb11 e b e b2 2 são as capacidades diária produtiva de forjaria e polimento. são as capacidades diária produtiva de forjaria e polimento. Assim, o modelo tem o seguinte aspecto Assim, o modelo tem o seguinte aspecto

55


Máx Z = 1.900,00XMáx Z = 1.900,00Xaa + 2.100,00X + 2.100,00Xbb , s.a , s.a

4 x4 xaa + 2 x + 2 xbb <= 220 <= 220

2 x2 xaa + 3 x + 3 xbb <= 250 <= 250

xxa a , x, xbb > = 0 > = 0

Exercício 2: Considere o seguinte problema: Uma empresa fabrica dois produtos, A e B. O Exercício 2: Considere o seguinte problema: Uma empresa fabrica dois produtos, A e B. O lucro unitário do produto A é de R$ 1.000,00 e de B é R$1.500,00. A empresa precisa de 20 lucro unitário do produto A é de R$ 1.000,00 e de B é R$1.500,00. A empresa precisa de 20 horas para fabricar uma unidade do produto A e de 30 horas para fabricar uma unidade do horas para fabricar uma unidade do produto A e de 30 horas para fabricar uma unidade do produto B. O tempo anual de produção disponível é de 1.200 horas. As demandas produto B. O tempo anual de produção disponível é de 1.200 horas. As demandas esperadas para os dois produtos levaram à decisão de que o montante do produto A esperadas para os dois produtos levaram à decisão de que o montante do produto A produzido não deve ultrapassar 40 unidades anuais e o montante de B não deve ultrapassar produzido não deve ultrapassar 40 unidades anuais e o montante de B não deve ultrapassar 30 unidades anuais. A empresa deseja maximizar o lucro do ano.30 unidades anuais. A empresa deseja maximizar o lucro do ano.

Solução: Máx Z = 1.000 xSolução: Máx Z = 1.000 xaa + 1.500 x + 1.500 xb b , s.a, s.a

20x20xaa + 30x + 30xbb <= 1.200 <= 1.200

xxaa <= 40 <= 40

xxbb <= 30 <= 30

xxaa , x , xbb >= 0 >= 0

66


Solução GráficaSolução GráficaExemplo1:Exemplo1:Para conseguir fundo para a festa de formatura, Jose, Carlos e izabel vão produzir 2 Para conseguir fundo para a festa de formatura, Jose, Carlos e izabel vão produzir 2 tipos brinquedos (A e B), cujos lucros por unidade são R$ 300,00 e R$ 400,00 tipos brinquedos (A e B), cujos lucros por unidade são R$ 300,00 e R$ 400,00 respectivamente. Na linha de produção cada brinquedo passa por 3 etapas: Modelagem, respectivamente. Na linha de produção cada brinquedo passa por 3 etapas: Modelagem, Pintura e Acabamento. Jose , encarregado da modelagem , dispõe de 20 horas por Pintura e Acabamento. Jose , encarregado da modelagem , dispõe de 20 horas por semana , Carlos encarregado a pintura dispõe de 30 horas por semana e Izabel semana , Carlos encarregado a pintura dispõe de 30 horas por semana e Izabel encarregado do acabamento dispõe de 16 horas semanais.Use os dados da tabela para encarregado do acabamento dispõe de 16 horas semanais.Use os dados da tabela para determinar o lucro Maximo.determinar o lucro Maximo.

x1 = n° de brinquedos do tipo A na semanax2 = n° de brinquedos do tipo B na semana

77


Lucro (Max) = 300(4) +400(6) = R$ 3600,00 Lucro (Max) = 300(4) +400(6) = R$ 3600,00

Lucro (Max) = 300(4) +400(6) = R$ 3600,00Lucro (Max) = 300(4) +400(6) = R$ 3600,00

88

Programação linear aplicada à Logística – cont.Programação linear aplicada à Logística – cont.Exemplo 2: As Caravanas Marco Polo Llda. usam dromedários (1 bossa) e camelos (2 bossas) para transportar figos secos de Bagda para Meca. Um camelo pode levar no máximo 1000 lbs e um dromedário 500 lbs. Durante a viagem um camelo consome 3 fardos de feno e 100 galões de água. Um dromedário consome 4 fardos de feno e 80 galões de água. As estações da Marco Polo, situadas em vários oásis ao longo do caminho, apenas têm disponíveis 1600 galões de água e 60 fardos de feno.

Os camelos e os dromedários são alugados a um pastor perto de Bagda a 11 pazuzas por camelo e 5 pazuzas por dromedário. Se as Caravanas Marco Polo Llda. tiverem uma carga de 10000 lbs de figos para transportar, quantos camelos e dromedários devem ser usados para minimizar a renda a pagar ao pastor ?

Variáveis de decisão : quantidade de camelos a usar (x1) quantidade de dromedários a usar (x2)

Restrições : capacidade da caravana disponibilidade de feno disponibilidade de água

99


CamelosCamelos DromedáriosDromedários Capacidade Capacidade disponíveldisponível

CapacidadeCapacidade 10001000 500500 1000010000

FenoFeno 33 44 6060

àguaàgua 100100 8080 16001600

Renda a pagarRenda a pagar 1111 55

Minimizar Z = 11 x1 + 5 x2 (renda) sujeito a 1 000 x1 + 500 x2 ≥ 10 000 (capacidade) 3 x1 + 4 x2 ≤ 60 (feno) 100 x1 + 80 x2 ≤ 1 600 (água) x1, x2 ≥ 0 (não negatividade)

1010


1111


Solução Algébrica - Método Simplex

O método simplex é um método interativo (algoritmo) utilizado para encontrar Algebricamente, a solução ótima de um problema de PL.

PASSOS DO SIMPLEX1. Achar uma solução básica inicial;2. Verificar se a solução é ótima. Se for pare.caso contrario, siga para o passo 33. Determinar a variável não básica que deve entra na base.4. Determinar a variável básica que deve sair da base;5. Achar a nova solução compatível básica e voltar ao passo 2.

Seja o Problema

Máximizar z = 3x1 + 2x2 + 5x3 s.a. x1 + 2x2 + x3 <= 430 3x1 + 2x3 <= 460 x1 + 4x2 <= 420 x1, x2, x3 >= 0

1212


Primeiro passo: Transformar o sistema de M desigualdades lineares restritivasEm um sistema de M equações lineares.

Assim; x1 + 2x2 + x3 + x4 = 430 3x1+ 2x2 + x5 = 460 x1+ 4x2 + x6 = 420

Segundo passo: Colocar as equações em forma de tabelaSegundo passo: Colocar as equações em forma de tabela

Z – 3x1 - 2x2 – 5x3 = 0Z – 3x1 - 2x2 – 5x3 = 0 x1 + 2x2 + x3 + x4 = 430x1 + 2x2 + x3 + x4 = 430 3x1 + 2x3 x5 = 4603x1 + 2x3 x5 = 460 x1 + 4x2 + x6 = 420x1 + 4x2 + x6 = 420

1313


Terceiro passo: Determinar uma solução inicial viável

VBVB zz x1x1 x2x2 X3X3 X4X4 x5x5 x6x6 bb

ZZ 11 -3-3 -2-2 -5-5 00 00 00 00

X4X4 00 11 22 11 11 00 00 430430

X5X5 00 33 00 22 00 11 00 460460

x6x6 00 11 44 00 00 00 11 420420

X1=x2=x3=0

X4 =430; x5 = 460; x6 = 420

1414



ZZ 11 -3-3 -2-2 -5-5 00 00 00 00

X4X4 00 11 22 11 11 00 00 430430

X5X5 00 33 00 22 00 11 00 460460

x6x6 00 11 44 00 00 00 11 420420

Quarto passo: Verificar se a solução é ótima

A solução não é ótima,porque as variáveis x1,x2 e x3 assume valor zero.

Quinto passo:Determinar a variável que entra xi , e

Sexto passo: Determinar a variável que saí xi

1515



ZZ 11 -3-3 -2-2 -5-5 00 00 00 00

X4X4 00 11 22 11 11 00 00 430430

X5X5 00 33 00 22 00 11 00 230230

x6x6 00 11 44 00 00 00 11 indind

No caso, entra x3 e sai x5. A intercessão x3 ^ x5 é o pivô

Sétimo passo: Calcular a nova matriz de coeficientes, executando as Sétimo passo: Calcular a nova matriz de coeficientes, executando as operações convenientes nas linhas da matriz.operações convenientes nas linhas da matriz.

1616

Programação linear aplicada à Logística – contProgramação linear aplicada à Logística – cont..VBVB ZZ X1X1 X2X2 x3x3 X4X4 X5X5 X6X6 BB

ZZ 11 4.54.5 -2-2 00 00 2.52.5 00 11501150

X4X4 00 -0,5-0,5 22 00 11 -0,5-0,5 00 200200

X3X3 00 1.51.5 00 11 00 0,50,5 00 230230

x6x6 00 11 44 00 00 00 11 420420

Oitavo passo: Repetir todos os passos, do 4 ao 7, tantas vezes quanto foremNecessárias, até que a solução ótima seja encontrada.

VBVB zz x1x1 x2x2 x3x3 x4x4 x5x5 x6x6 BB

ZZ 11 44 00 00 11 22 00 13501350

X2X2 00 -0,25-0,25 11 00 0.50.5 -0,25-0,25 00 100100

X3X3 00 1.51.5 00 11 00 0,50,5 00 230230

X6X6 00 22 00 00 -2-2 11 11 2020

O máximo de z é 1350, para x2 = 100, x3 =230 e x6 = 20

1717


Método simplex – Casos especiaisMétodo simplex – Casos especiais

Serão estudados em seguida alguns casos que podem ocorrer nos modelos de Serão estudados em seguida alguns casos que podem ocorrer nos modelos de programação linear e que não foram considerados anteriormente.programação linear e que não foram considerados anteriormente.

1) Problemas de Minimização1) Problemas de Minimização Foram resolvidos, até agora, modelos com função objetiva a ser maximizadas. Foram resolvidos, até agora, modelos com função objetiva a ser maximizadas.

Quando a função objetivo for de minimização pode-se fazer duas coisas:Quando a função objetivo for de minimização pode-se fazer duas coisas:

a)a) Inverter o teste de otimização e o critério de entrada na base.Inverter o teste de otimização e o critério de entrada na base.b)b) Transformar o problema de minimização num problema de maximização.por Transformar o problema de minimização num problema de maximização.por

exemplo, Min W = 2x1 + 3x2 - 5x3 equivale a: exemplo, Min W = 2x1 + 3x2 - 5x3 equivale a: Máx Z = -2x1 - 3x2 + 5x3 e na solução final fazer W = - ZMáx Z = -2x1 - 3x2 + 5x3 e na solução final fazer W = - Z

2) Empate na entrada2) Empate na entrada Quando houver empate na escolha da variável que entra na base, deve-se Quando houver empate na escolha da variável que entra na base, deve-se

escolher a variável arbitrariamente. A única implicação envolvida na escolha é escolher a variável arbitrariamente. A única implicação envolvida na escolha é um caminho mais longo ou mais curto para se obter a solução ótima.um caminho mais longo ou mais curto para se obter a solução ótima.

1818


3) Empate na saída – Degeneração3) Empate na saída – Degeneração

Como no caso anterior, a decisão deve ser arbitraria. Apresenta-se um exemplo para Como no caso anterior, a decisão deve ser arbitraria. Apresenta-se um exemplo para analise das implicações desse empate.analise das implicações desse empate.

Máx Z = 5x1 + 2x2 s.aMáx Z = 5x1 + 2x2 s.a x1 <= 3x1 <= 3 x2 <= 4x2 <= 4 4x1 + 3x2 <= 124x1 + 3x2 <= 12 x1 , x2 >= 0 x1 , x2 >= 0

VBVB zz x1x1 x2x2 x3x3 x4x4 X5X5 bb

X3X3 11 11 00 11 00 OO 33

X4X4 00 00 11 00 11 00 44

x5x5 00 44 33 00 00 11 1212

F.0F.0 00 -5-5 -2-2 00 00 00 00

1919


Escolhendo a variável que saí,vem:Escolhendo a variável que saí,vem: linha 1 : x1 <= 3/1 = 3linha 1 : x1 <= 3/1 = 3 linha 2 : x1 <= 4/0 = indlinha 2 : x1 <= 4/0 = ind linha 3 : x1 <= 12/4 = 3linha 3 : x1 <= 12/4 = 3

VBVB zz x1x1 x2x2 x3x3 x4x4 X5X5 bb

X1X1 11 11 00 55 00 OO 33

X4X4 00 00 11 11 11 00 44

X5X5 00 00 33 -4-4 00 11 00

F.0F.0 00 00 -2-2 55 00 00 1515

Obs:Note que a variável básica x5 é nula. Isso sempre ocorrerá quando houver umempate na saída. Neste caso, as variáveis x3 e x5 se anularam ao mesmo tempo.Quando isso ocorrer diz-se que a solução fatível básica é degenerada.

2020


A próxima tabela será:A próxima tabela será:

VBVB zz X1X1 x2x2 x3x3 x4x4 x5x5 bb

X1X1 00 11 00 11 00 00 33

X4X4 00 00 00 4/34/3 11 -1/3-1/3 44

X2X2 00 00 11 -4/3-4/3 00 1/31/3 00

F.0F.0 11 00 00 7/37/3 00 2/32/3 1515

Obs: Se na ocasião do empate fosse escolhido x5 em vez de x3, para sair da base, obter-se-ia:

VBVB zz X1X1 x2x2 x3x3 x4x4 x5x5 bb

X3X3 00 00 -3/4-3/4 11 00 -1/4-1/4 00

X4X4 00 00 11 00 11 00 44

X1X1 00 11 3/43/4 00 00 1/41/4 33

F.0F.0 11 00 7/47/4 00 00 5/45/4 1515

2121


Obs: Neste caso conseguiu-se chegar à solução ótima com uma interação a Obs: Neste caso conseguiu-se chegar à solução ótima com uma interação a menos.menos. Problemas Propostos:Problemas Propostos:

1) Máx Z = 2x1 + 3x2 , s.a1) Máx Z = 2x1 + 3x2 , s.a -x1 + 2x2 <= 4-x1 + 2x2 <= 4 x1 + x2 <= 6x1 + x2 <= 6 x1 + 3x2 <= 9x1 + 3x2 <= 9 x1, x2 >=0 Achar a solução gráfica.x1, x2 >=0 Achar a solução gráfica.

2) Máx Z = 7x1 + 9x2 , s.a2) Máx Z = 7x1 + 9x2 , s.a x1 - x2 >= - 2x1 - x2 >= - 2 3x1 + 5x2 <= 153x1 + 5x2 <= 15 5x1 + 4x2 <= 205x1 + 4x2 <= 20 x1, x2 >= 0 achar a solução gráfica x1, x2 >= 0 achar a solução gráfica

2222


3) Máx z = 3x1 + x2 + 5x3 , s.a3) Máx z = 3x1 + x2 + 5x3 , s.a x1 - 2x2 + 4x3 + x4 = 12x1 - 2x2 + 4x3 + x4 = 12 2x1 + x2 + 3x3 + x5 = 152x1 + x2 + 3x3 + x5 = 15 x1, x2, x3, x4, x5 >= 0 x1, x2, x3, x4, x5 >= 0 a)a) Qual a solução básica inicial óbvia e qual o valor de Z?Qual a solução básica inicial óbvia e qual o valor de Z?b)b) Supor que a variável x3 passe de 0 a 1, mantidos x1 = x2 = 0. Qual o valor resultante Supor que a variável x3 passe de 0 a 1, mantidos x1 = x2 = 0. Qual o valor resultante de x4, x5 e de Z?de x4, x5 e de Z?

Casos de Dificuldades Casos de Dificuldades Suponha que todos os bj sejam >=0. Haverá dificuldade quando o modelo apresentar Suponha que todos os bj sejam >=0. Haverá dificuldade quando o modelo apresentar uma restrição do tipo >=. Nesses casos, usa-se o processo da função objetiva artificial uma restrição do tipo >=. Nesses casos, usa-se o processo da função objetiva artificial ou método de duas fases. ou método de duas fases. A fase I consiste em abandonar ou não a função objetiva e trabalhar com a função A fase I consiste em abandonar ou não a função objetiva e trabalhar com a função objetivo artificial, formada pela variável artificial.objetivo artificial, formada pela variável artificial.Se o modelo requerer mais de uma variável artificial para completar a base inicial, a Se o modelo requerer mais de uma variável artificial para completar a base inicial, a função objetiva Z será igual a soma dessas variáveis artificiais. Assim, o objetivo na fase função objetiva Z será igual a soma dessas variáveis artificiais. Assim, o objetivo na fase I é fazer com que a ou as variáveis artificiais sejam igual a zero, excluindo-se da base a I é fazer com que a ou as variáveis artificiais sejam igual a zero, excluindo-se da base a função artificial, antes de se passar para a II fase. Seja o problema de programação função artificial, antes de se passar para a II fase. Seja o problema de programação linear. linear.

2323


Min Z = - x1 + 2x2 , s.aMin Z = - x1 + 2x2 , s.a 6x1 + 5x2 >= 906x1 + 5x2 >= 90 - x1 + x2 <= 8- x1 + x2 <= 8 2x1 - x2 <= 202x1 - x2 <= 20 x1, x2 >= 0 Resolver pelo simplex.x1, x2 >= 0 Resolver pelo simplex.

VBVB x1x1 x2x2 x3x3 x4x4 x5x5 A1A1 BB

A1A1 66 55 -1-1 00 00 11 9090

X4X4 -1-1 11 00 11 00 00 88

x5x5 22 -1-1 00 00 11 00 2020

F.0F.0 -1-1 22 00 00 00 00 00

F.AF.A -6-6 -5-5 11 00 00 -1-1 -90-90

2424


VBVB X1X1 X2X2 X3X3 X4X4 X5X5 A1A1 bb

X2X2 00 11 -1/8-1/8 00 -3/8-3/8 1/81/8 30/830/8

X4X4 00 00 1/161/16 11 11/1611/16 -1/16-1/16 258/16258/16

X1X1 11 00 -1/16-1/16 00 5/165/16 1/161/16 190/16190/16

F.0F.0 00 00 3/163/16 00 17/1617/16 -3/16-3/16 70/1670/16

F.AF.A 00 00 00 00 00 00 00

VBVB X1X1 X2X2 X3X3 X4X4 X5X5 A1A1 bb

A1A1 00 88 -1-1 00 -3-3 11 3030

X4X4 00 1/21/2 00 11 1/21/2 00 1818

X1X1 11 -1/2-1/2 00 00 1/21/2 00 1010

F.0F.0 00 3/23/2 00 00 1/21/2 00 1010

F.AF.A 00 -8-8 11 00 33 -1-1 -30-30

2525


Solução Final:Solução Final:X1 = 190/16X1 = 190/16X2 = 30/8 X2 = 30/8 X3 = 0X3 = 0X4 = 258/16X4 = 258/16X5 = 0X5 = 0A1 = 0A1 = 0 Z = - x1 + 2x2 Z = - x1 + 2x2 Z = -190/16 + 2.30/8 = - 70/16Z = -190/16 + 2.30/8 = - 70/16

Resolução de problemas de programação Linear utilizando Excel através da ferramenta “Solver”

2626

Resolução de PL usando a ferramenta solverResolução de PL usando a ferramenta solver

O software Excel resolve problemas de Programação linear através da O software Excel resolve problemas de Programação linear através da ferramenta “Solver”.ferramenta “Solver”.Seja o problema de programação Linear:Seja o problema de programação Linear: Maximizar o lucro Z = x1 + 1.5 x2, s.aMaximizar o lucro Z = x1 + 1.5 x2, s.a

2 x1 + 2 x2 <= 160 2 x1 + 2 x2 <= 160 x1 + 2 x2 <= 120x1 + 2 x2 <= 120 4 x1 + 2 x2 <= 2804 x1 + 2 x2 <= 280 x1, x2 >= 0 x1, x2 >= 0

Para resolver qualquer problema de PL utilizando o Excel, deve-se montar a Para resolver qualquer problema de PL utilizando o Excel, deve-se montar a seguinte planilha: seguinte planilha:

2727


2828


Na célula D2 é digitada a seguinte fórmula:Na célula D2 é digitada a seguinte fórmula:=SOMARPRODUTO(B2:C2;$B$6:$C$6), idem para as células D3, D4,D5.=SOMARPRODUTO(B2:C2;$B$6:$C$6), idem para as células D3, D4,D5.uma vez adicionadas estas fórmulas à planilha pode-se alterar os valores das células uma vez adicionadas estas fórmulas à planilha pode-se alterar os valores das células B6 e C6 que correspondem aos valores de x1 e x2 e verifica-se que os valores das B6 e C6 que correspondem aos valores de x1 e x2 e verifica-se que os valores das células D2, D3,D4 e D5 (coluna total) são alterados automaticamente. Agora, a células D2, D3,D4 e D5 (coluna total) são alterados automaticamente. Agora, a planilha esta pronta para utilizar a ferramenta “solver”, que irá resolver o problema de planilha esta pronta para utilizar a ferramenta “solver”, que irá resolver o problema de programação linear. programação linear.

Para ativar o comando Solver deve-se clicar sobre a célula D5, que corresponde ao Para ativar o comando Solver deve-se clicar sobre a célula D5, que corresponde ao valor da função objetivo, e após em ferramentas solver. A janela “parâmetros do valor da função objetivo, e após em ferramentas solver. A janela “parâmetros do solver “então irá aparecer sobre a planilha. A figura mostra a planilha neste estágio.solver “então irá aparecer sobre a planilha. A figura mostra a planilha neste estágio.

Nesta janela o campo “definir célula de destino“ aparece o valor $D$5, Nesta janela o campo “definir célula de destino“ aparece o valor $D$5, correspondente ao valor da função objetivo.correspondente ao valor da função objetivo.O campo “células variáveis” corresponde aos valores de x1 e x2. Assim,seleciona-se O campo “células variáveis” corresponde aos valores de x1 e x2. Assim,seleciona-se com o mouse as células (B6 e C6). com o mouse as células (B6 e C6).

2929


Após a seleção das células B6 e C6,deve-se clicar na caixa “adicionar” para Após a seleção das células B6 e C6,deve-se clicar na caixa “adicionar” para inserir as restrições. Em seguida clicar na caixa “adicionar” onde irá aparecer inserir as restrições. Em seguida clicar na caixa “adicionar” onde irá aparecer outra janela denominada “adicionar restrição”.outra janela denominada “adicionar restrição”.Nesta janela o campo “referencia de célula”, deve-se selecionar as células D2, Nesta janela o campo “referencia de célula”, deve-se selecionar as células D2, D3 e D4 e no campo “restrição deve-se selecionar as células F2, F3 e F4 D3 e D4 e no campo “restrição deve-se selecionar as células F2, F3 e F4 conforme mostra a figura.conforme mostra a figura.

3030


Após estas seleções deve-se clicar na caixa “opções” na janela “parâmetros do Após estas seleções deve-se clicar na caixa “opções” na janela “parâmetros do solver” e verificar se o campo “presumir modelo linear”bem como “presumir solver” e verificar se o campo “presumir modelo linear”bem como “presumir não negativos”.não negativos”.Retornando a janela “parâmetros do solver” clica-se na caixa “resolver”, que irá Retornando a janela “parâmetros do solver” clica-se na caixa “resolver”, que irá então resolver o PL. A figura abaixo mostra a planilha com o resultado ótimo.então resolver o PL. A figura abaixo mostra a planilha com o resultado ótimo.

3131


Como pode-se observar, os valores das células B6 e C6 são iguais a 40 Como pode-se observar, os valores das células B6 e C6 são iguais a 40 (valores ótimos). A célula D5, com valor igual a 100 correspondendo ao valor (valores ótimos). A célula D5, com valor igual a 100 correspondendo ao valor da função objetiva. da função objetiva.

3232

Problemas do transporte aplicado à logísticaProblemas do transporte aplicado à logística

IntroduçãoIntrodução

O modelo de transporte tem como objetivo minimizar o custo total do transporte O modelo de transporte tem como objetivo minimizar o custo total do transporte necessário para abastecer n centros consumidores(destinos) a partir de m centros necessário para abastecer n centros consumidores(destinos) a partir de m centros fornecedores (origens). fornecedores (origens).

O modelo tem o seguinte aspecto:O modelo tem o seguinte aspecto:

m

i 1

n

j 1

m

i 1

n

j 1

m

i 1

n

j 1

m

i 1

n

j 1

m

i 1

n

j 1

m

i 1

n

j 1

3333


Exemplo1: considere situação onde há 3 fábricas produzindo o mesmo produto Exemplo1: considere situação onde há 3 fábricas produzindo o mesmo produto e 4 depósitos onde estes produtos são estocados para posterior venda. As e 4 depósitos onde estes produtos são estocados para posterior venda. As produções nas fábricas são:a1 = 40, a2 = 80, a3 = 110. Nos depósitos devem produções nas fábricas são:a1 = 40, a2 = 80, a3 = 110. Nos depósitos devem ser atendidas as seguintes demandas:b1 = 20, b2 = 30, b3 = 100, b4 = 80. Os ser atendidas as seguintes demandas:b1 = 20, b2 = 30, b3 = 100, b4 = 80. Os custos unitários de transporte do produto são dados por:custos unitários de transporte do produto são dados por:

Achar um modelo de PL para determinar o programa de entregas do produto com mínimo Achar um modelo de PL para determinar o programa de entregas do produto com mínimo custo de transporte.custo de transporte.

D1D1 D2D2 D3D3 D4D4

0101 1010 55 1212 44

0202 22 00 11 99

0303 1313 1111 1414 66

3434


Regra do canto esquerdo ou canto Noroeste:Regra do canto esquerdo ou canto Noroeste:

Consiste em, iniciando pelo arco (1, 1) ou trajeto O1D1 associado ao canto superior Consiste em, iniciando pelo arco (1, 1) ou trajeto O1D1 associado ao canto superior esquerdo da tabela usada pelo algoritmo, e através de deslocamentos sucessivos para a esquerdo da tabela usada pelo algoritmo, e através de deslocamentos sucessivos para a direita e para baixo, atingir o canto inferior direito da tabela, distribuindo a produção direita e para baixo, atingir o canto inferior direito da tabela, distribuindo a produção disponível nas origens pelos arcos (chamados disponível nas origens pelos arcos (chamados arcos básicosarcos básicos) de forma a atender as ) de forma a atender as demandas demandas nos destinos.nos destinos.

Nota:Uma linha (ou coluna) é explorada até que a produção (ou demanda) desta linha Nota:Uma linha (ou coluna) é explorada até que a produção (ou demanda) desta linha (ou coluna) seja esgotada (ou atendida). (ou coluna) seja esgotada (ou atendida). Em Em cada arco deve-se alocar a maior cada arco deve-se alocar a maior quantidade de produto possível.quantidade de produto possível.

D1D1 D2D2 D3D3 D4D4 ProduçãoProdução

0101 2020 2020 4040

0202 1010 7070 8080

0303 3030 8080 110110

DemandaDemanda 2020 3030 100100 8080 230/230230/230

Custo da solução: 20.10 + 20.5 + 10.0 + 70.1 + 30.14 + 80.6 = 1270.

3535


Casos especiaisOfertas e demandas desbalanceadas Podem ocorrer duas situações:

Obs:Custos de transporte nos trajetos fictícios são nulos. Em seguida, aplica-se o método do canto noroeste normalmente.

Exemplo2:Resolva o seguinte problema de transporte

AA BB CC OfertaOferta

0101 66 88 44 2020

0202 44 55 88 2020

DemandaDemanda 3030 2020 1010

Custo total: 20*6 + 10*4 + 10*50 + 10*0 + 10*0 = 660

3636


Regra do Custo Mínimo

Este processo fornece uma solução inícial que depende não só dos valores das ofertas e das demandas, como também,dos custos dos transportes, objetivando obter uma solução mais próxima da ótima.

Os seguintes passos devem ser seguidos nos quadros de soluções:1) Localize no quadro de custos o menor cij que não tenha oferta ou

demanda nula;2) Aloque na célula correspondente do quadro de soluções a maior

quantidade permitida pela oferta e demanda correspondente;3) Atualize os valores da oferta e da demanda que foram modificados pelo

passo 2 e volte ao passo 1;4) Este processo se repete até esgotar-se todas as origens e suprimirem

todos os destinos. Exercício: Resolver o problema dado no exemplo 1.

3737


11 22 33 44 OfertaOferta

11 1010 55 1212 44 4040

22 22 00 11 99 8080

33 1313 1111 1414 66 110110

DemandaDemanda 2020 3030 100100 8080 230/230230/230

11 22 33 44 OfertaOferta

11 99 4040

22 66 44 8080

33 11 66 11 110110

DemandaDemanda 2020 3030 100100 8080 230/230230/230

Custo total = 13*20 +11*30 + 14*20 + 6*40 + 80*1 + 40*4 = 1.350

3838

Problemas de Designação aplicado à logísticaProblemas de Designação aplicado à logística

Problema de designaçãoProblema de designação Partindo do principio de que o problema de transporte tem como Partindo do principio de que o problema de transporte tem como

modelo:modelo:

Então, fazendo bj = 1, j=1,2,...,n e ai = 1 i=1,2,...,m podemos garantirQue os somatórios acima só terão um xij = 1 para cada par (i,j). Esse fluxoUnitário estabelece a ligação entre uma única origem a um único destino.Esse caso particular de problema de transporte é conhecido como problemade designação, pois designa cada origem a um único destino

3939


Dessa forma o problema toma o seguinte aspecto: Dessa forma o problema toma o seguinte aspecto:

O método consiste dos seguintes passos:

1) Subtrair o menor elemento de cada linha dos elementos restantes dessa linha;2) Subtrair o menor elemento de cada coluna dos outros elementos dessa mesma Coluna;3) Testar se a solução é ótima. i)Traça-se o número mínimo de retas que cubra todos os zeros do quadro de

soluções (horizontal ou vertical); ii) Se o número de retas for igual a m, número de linhas ou colunas, pode-se

fazer uma atribuição ótima. Vá para o passo 6, caso contrario, vá para o passo 4.

4040


4) Procura-se o menor elemento não coberto pelas linhas e subtraia esse elemento dos 4) Procura-se o menor elemento não coberto pelas linhas e subtraia esse elemento dos demais não coberto. Some depois esse elemento (o menor não coberto) aos demais não coberto. Some depois esse elemento (o menor não coberto) aos elementos que estão na interseção das retas. Todos os demais elementos devem elementos que estão na interseção das retas. Todos os demais elementos devem permanecer inalterados. Vá para o passo 3. permanecer inalterados. Vá para o passo 3.

5) Faça uma atribuição ótima. Esta atribuição é feita achando-se onde os zeros estão 5) Faça uma atribuição ótima. Esta atribuição é feita achando-se onde os zeros estão situados no quadro final.situados no quadro final.

OBS: OBS: a)a) O problema de designação exige uma matriz m x n.O problema de designação exige uma matriz m x n.b)b) Se o número de linhas é menor que o número de colunas a matriz é completada Se o número de linhas é menor que o número de colunas a matriz é completada

com linhas com elementos nulos, é equivalente a dizer que alguns dos com linhas com elementos nulos, é equivalente a dizer que alguns dos pretendentes não serão designado.pretendentes não serão designado.

c)c) Se o número de colunas é menor que o número de linhas acrescenta-se colunas Se o número de colunas é menor que o número de linhas acrescenta-se colunas fictícias e isso significa que alguns dos elementos não serão designados. fictícias e isso significa que alguns dos elementos não serão designados.

Considere o exemplo:

Uma fábrica possui quatro locais, designados por (1,2,3,4) para receber três máquinas novas (A,B,C) o local 4 não é permitido à máquina A por restrições físicas. O custo de manuseio de materiais, em $/hora, envolvendo cada máquina com a respectiva posição, é dado no quadro abaixo.

4141


11 22 33 44

AA 55 11 33 XX

BB 33 11 44 33

CC 33 33 44 22

11 22 33 44

AA 55 11 33 XX

BB 33 11 44 33

CC 33 33 44 22

DD 00 00 00 00

(1)(1)(2)

4242


11 22 33 44

AA 44 00 22 XX

BB 22 00 33 22

CC 11 11 22 00

DD 00 00 00 00

(2)

11 22 33 44

AA 22 00 00 XX

BB 00 00 11 00

CC 11 33 22 00

DD 00 22 00 00

Designação ótima: MáquinaMáquina LocalLocal

AA 22

BB 1 1

CC 44

4343


Problemas Propostos:Problemas Propostos:1)Quatro construções A, B, C e D devem ser levantadas em um campus 1)Quatro construções A, B, C e D devem ser levantadas em um campus universitário por quatro empreiteiras 1, 2, 3, e 4. Cada uma delas deve construir um universitário por quatro empreiteiras 1, 2, 3, e 4. Cada uma delas deve construir um edifício. As propostas financeira das construtoras estão indicadas no quadro abaixo.edifício. As propostas financeira das construtoras estão indicadas no quadro abaixo.

ConstruçõesConstruções 11 22 33 44

EmpreiteirasEmpreiteiras

AA 4848 4848 5050 4444

BB 5656 6060 6060 6868

CC 8686 5454 9090 8585

DD 4242 4444 5454 4646

2)Resolver o seguinte problema de designação: Caminhões devem se deslocar para cidades cujas distancias são dadas na tabela abaixo. Designe cada caminhão de forma que a quilometragem seja mínima.

4444


CidadesCidades

caminhõescaminhões 11 22 33 44 55 66

AA 2020 1515 2626 4040 3232 1212

BB 1515 3232 4646 2626 2828 2020

CC 1818 1515 22 1212 66 1414

DD 88 2424 1212 2222 2222 2020

EE 1212 2020 1818 1010 2222 1515Resposta:Temos duas atribuições, a 1 é.

Da Cidade A envia um caminhão para a Da Cidade A envia um caminhão para a cidadecidade

66

Da Cidade B envia um caminhão para a Da Cidade B envia um caminhão para a cidadecidade

11

Da Cidade C envia um caminhão para a cidadeDa Cidade C envia um caminhão para a cidade 55

Da Cidade D envia um caminhão para a cidadeDa Cidade D envia um caminhão para a cidade 33

Da Cidade E envia um caminhão para a cidadeDa Cidade E envia um caminhão para a cidade 44

A Cidade 2 não recebe caminhõesA Cidade 2 não recebe caminhões --

A quilometragem total para esta atribuição é deA quilometragem total para esta atribuição é de 12 + 15 +6 +12 +10 + 0 = 55 milhas12 + 15 +6 +12 +10 + 0 = 55 milhas

Documents

MBA DE LOGÍSTICA | FCAP- UPE