Pesquisa Operacional:

O modelo do transporte

Pesquisa Operacional: O modelo do transporte

•A todo modelo físico, biológico, químico, econômico, etc. está associado um modelo matemático.

•Em pesquisa operacional estamos sempre interessados em tornar mais eficientes certas ações, como, por exemplo, maximizar lucros e minimizar custos.

•A um problema de pesquisa operacional está associado um modelo matemático que é basicamente a resolução de um sistema de equações ou inequações

Pesquisa Operacional: O modelo do transporte

Exemplo:

Uma fábrica produz dois produtos, A e B. Cada um deles deve ser processado por duas máquinas, M e N.

Devido à programação de outros produtos, que também utilizam essas máquinas, a máquina M tem 24 horas de tempo disponível para os produtos A e B, enquanto a máquina N tem 16 horas de tempo disponível.

Pesquisa Operacional: O modelo do transporte

Para produzir uma unidade do produto A, gastam-se 4 horas em cada uma das máquinas M e N. Para produzir uma unidade do produto B, gastam-se 6 horas na Máquina M e 2 horas na máquina N.

Cada unidade vendida do produto A gera um lucro de $ 80 e cada unidade do produto B, um lucro de $ 60.

Existe uma previsão máxima de demanda para o produto B de 3 unidades, não havendo restrições quanto à demanda do produto A.

Deseja-se saber quantas unidades de A e de B devem ser produzidas, de forma a maximizar o lucro.

Pesquisa Operacional: O modelo do transporte

Formulação matemática do problema:Maximizar f (x,y) = 80x + 60 y (lucro)Sujeito à

4x + 6y ≤ 24 restrição relativa ao tempo da máquina M4x + 2y ≤ 16 restrição relativa ao tempo da máquina N0x + 1y ≤ 3 restrição relativa à demanda do produto Bx ≥ 0 condição de não negatividade de xy ≥ 0 condição de não negatividade de y

sendo x o número de unidades do produto A e y o número de unidades do produto B.

Pesquisa Operacional: O modelo do transporte

f (P) = 0 ; f (Q) = 320 ;f (R) = 360 ; f (S) = 300R é então o ponto onde ocorre o máximo.Prova-se que se existe um máximo ou mínimo ele está sempre em um dos vértices, embora possa haver outros no interior que também sejam máximos ou mínimos.

Método algébrico:Temos de resolver um conjunto de Cn,p sistemas de equações lineares onde n é o número de equações e p é o número de variáveis. Cada solução de cada sistema tem de ser verificada nas outras inequações. O conjunto de todas as soluções formam os vértices da região e candidatos à máximo ou mínimo.

O método algébrico resolve qualquer problema de programação linear porém torna-se exaustivo quando o número de inequações ou variáveis for muito grande. Este fato justifica o Método Simplex.

O método geométrico obviamente está limitado a duas ou três variáveis.

Pesquisa Operacional: O modelo do transporte

O algoritmo Simplex supõe sempre a condição de não negatividade de suas variáveis e a partir dele, do Simplex, foi desenvolvido um programa de computador. No Excel nós temos o Solver.O método Simplex resolve um sistema de “equações” e as desigualdades são substituídas por igualdades com o acréscimo das variáveis de folga, de excesso e das variáveis artificiais.≤ → acrescenta-se uma variável de folga≥ → acrescenta-se uma variável de excesso e uma variável artificial= → acrescenta-se uma variável artificial

Pesquisa Operacional: O modelo do transporte

Reescrevendo o sistema:

Maximizar 80x + 60 y + 0.S1 + 0.S2 + 0.S3

Sujeito a

4x + 6y + 1.S1 + 0.S2 + 0.S3 = 24

4x + 2y + 0.S1 + 1.S2 + 0.S3 = 16

0x + 1y + 0.S1 + 0.S2 + 1.S3 = 3

Variável que entra na base: x, pois é a que mais contribui com a função objetivo

Variável que sai da base: S2, pois é a que mais se opõe ao crescimento da função objetivo

Variável que entra: yVariável que sai: S1

O Problema do Transporte:

Pode ser resolvido através do Simplex.Aparece quando há a necessidade de distribuição de bens e serviços de várias fontes de suprimento (como fábricas) para várias localizações de demanda, com armazéns (destinos).O objetivo é minimizar o custo do transporte.

Exemplo:

Três fontes de suprimentos de um dado produto:F1: 10.000 unidades mensaisF2: 15.000 unidades mensaisF3: 5.000 unidades mensais

Quatro armazéns:D1: 8.000 unidades mensaisD2: 4.000 unidades mensaisD3: 7.000 unidades mensaisD4: 11.000 unidades mensais

Custo do transporte:

13X11+ 8X12 + 9X13 + 12X14 + 12X21 + 9X22+ 10X23 + 14X24 + 8X31 + 8X32 + 9X33 + 6X34

Restrições relativas às fontes:X11+ X12 + X13 + X14 ≤ 10.000 fonte F1X21+ X22 + X23 + X24 ≤ 15.000 fonte F2X31+ X32 + X33 + X34 ≤ 5.000 fonte F3

Restrições relativas às demandas:X11+ X12 + X13 = 8.000 destino D1X11+ X12 + X13 = 4.000 destino D2X11+ X12 + X13 = 7.000 destino D3X11+ X12 + X13 = 11.000 destino D4

Xij ≥ 0 condição de não negatividade

São 12 variáveis e 7 restrições !!!!Levando o problema para o Solver (Excel) encontramos o mínimo em

$ 300.000,00.

Método de Aproximação de Vogel

O tempo de computador é cerca de cem vezes menor que o do Simplex;Requer menos memória;Produz soluções inteiras.

Custo = 8 x 4.000 + 12 x 6.000 + 12 x 8.000 + 10 x 7.000 + 6 x 5.0000 = $ 300.000,00

Pode ser ou não que a solução inicial obtida pelo Método de Vogel seja a solução ótima. Para chegarmos à solução ótima utilizamos o Método da Distribuição Modificada (M.O.D.I.)

Método da Distribuição Modificada• Fundamentalmente o

M.O.D.I. opera por meio de realocação de carga.

• Define-se um valor Li para cada linha i e um valor Kj para cada coluna j da matriz de transporte, de maneira que:

• Li + Kj = Cij , onde Cij é o custo do transporte associado à célula do cruzamento da linha i com a coluna j.

• Efetuamos esses cálculos somente usando-se as células ocupadas com carga.

Células ocupadas:

F1 D2 , F1 D4 , F2 D1 , F2 D3 , F3 D4

L1 + K4 = C14 = 12

L1 + K2 = C12 = 8

L2 + K1 = C21 = 12

L2 + K3 = C23 = 10

L3 + K4 = C34 = 6

Temos um sistema de 5 equações e 7 variáveis. Fazendo-se

L1 = 0 e L2 = 0, vem:

K4 = 12

K2 = 8

L3 = -12

K1 = 12

K3 = 10

Índice de melhoria: Cij – Li + Ki

F1 D2 = 12 – 0 – 12 = 0

F1 D4 = 8 – 0 – 8 = 0

F2 D1 = 12 – 0 – 12 = 0

F2 D3 = 10 – 0 – 10 = 0

F3 D4 = 6 – (-12) – 12 = 6

Observações:

a) a presença de um índice de melhoria igual a zero indica que existe solução alternativa;

b) a presença de um índice de melhoria negativo indica que será interessante uma realocação de carga para esta célula. Transferir-se-ia carga para esta célula através de uma anel de realocação efetuando-se uma compensação no anel de forma a restabelecer o balanço na linha e na coluna.