Métodos de Análise de Sistemas Produtivos

Modelos matemáticos para resolução de problemas

de afectação de operações a recursos produtivos

17 de Maio de 2002

Alunos:

Álvaro Magalhães

Bernardo Ribeiro

João Bessa

José Lúcio

Teresa Marques

Docentes:

Fernando Manuel Ferreira Lobo Pereira

Gil Manuel Magalhães de Andrade Gonçalves

Modelos Matemáticos

17-05-02 Masp – grupo 1 1

Índice:

Introdução 2

O Grafo 3

Algoritmo de Dijkstra 4

Dijkstra com variável de ocupação da rede 8

Método ‘ k shortest path’ 10

Algoritmo A star 16

Modelos Matemáticos

17-05-02 Masp – grupo 1 2

Introdução

Este documento pretende enumerar vários modelos matemáticos para

resolução de problemas de afectação de operações a recursos produtivos. Os

diversos métodos existentes apoiam-se nos algoritmos de caminho mínimo, em

especial o algoritmo de dijkstra.

Cada método é apresentado pretende demostrar o funcionamento do

algoritmo para um dos grafos construídos para o enunciado.

Deste documento resultará a escolha de um modelo a seguir de acordo

com as vantagens e desvantagens de cada modelo.

Modelos Matemáticos

17-05-02 Masp – grupo 1 3

O Grafo

De seguida é apresentado o grafo escolhido como principal e que foi

utilizado para demonstração dos vários métodos e para o qual foram

calculados os algoritmos matemáticos particulares.

Legenda: Tempo , Custo

Modelos Matemáticos

17-05-02 Masp – grupo 1 4

Algoritmo de Dijkstra

Forma Tabelar de resolver o nosso problema especifico:

Letra representa recursos e algarismos representam operação;

Dentro de ( ) está atribuição a cada recurso de um valor, para que possa ser

identificado como um nó; um mesmo recurso pode então estar representado

por mais de um nó diferente;

I (0) A1 (1) F1 (2) E1 (3) C2 (4) B2 (5) D2 (6) D3 (7) C3 (8) B3 (9) F4 (10) A4 (11) F (12)

10 7 5 21 15 12 17 31 16 21 25

E 12 11 18 19 35 26 18

22

Valor mínimo até ao nó respectivo (cada operação tem apenas um valor mínimo)

Valor mínimo dos nós associados às últimas operações possíveis

Valor mínimo óptimo final, calculado através do mínimo dos valores a

Valor que não o mínimo

E >>> valor mínimo

A solução deste problema é a seguinte sequência: E1 >> D2 >> C3

Esta solução apenas considera um valor fixo para cada arco,

considerando para tal que tanto a variável Custo como Tempo têm um peso

unitário;

Em seguida demonstra-se a resolução do mesmo problema mas

considerando o valor de cada ramo em função das duas variáveis já referidas;

W = T*x + C*y

I (0) A1 (1) F1 (2) E1 (3) C2 (4) B2 (5) D2 (6)

5x + 5y 4x + 3y 3x + 2y 10x + 11y 7x + 8y 6x + 6y

E 8x + 5y 6x + 5y

8<10 6=6

5<11 5<6

Modelos Matemáticos

17-05-02 Masp – grupo 1 5

D3 (7) C3 (8) B3 (9) F4 (10) A4 (11) F (12)

11x + 7y 17x + 14y 10x + 7y 13x + 9y 16x + 10y

11x + 7y 11x + 8y 18x + 17y 16x + 10y 11x + 7y

15x + 8y

11<17 10<11 13<18 15<16 11<13<15

7<14 7<8 9<17 8<10 7<8<9

Resolvendo então o nosso problema em função dos “pesos” das

variáveis Tempo e Custo, verifica-se que a solução do problema se mantém a

mesma independente dos referidos parâmetros;

Em seguida passa-se apresentar um modelo matemático para este

problema, em que primeiramente temos uma solução orientada ao nosso

problema especifico, e em seguida em função disso se tenta retirar um modelo

generalizado que sirva para qualquer outro problema deste tipo;

ESPECIFICAÇÕES:

W = X*T + Y*C em que...

W >> Peso total do arco;

T >> Tempo de operação;

C >> Custo de operação;

X,Y >> pesos das variáveis que estão em jogo;

Wi [j] >> Peso do arco com origem em i e destino em j; i,j e [0,12]

Ek >> valor mínimo até ao nó k; k e [0,12]

E [0] = 0 >> Ponto de partida;

E [12] >> solução óptima a encontrar;

Pode existir mais de que um nó associado a uma mesmo recurso, por

isso convém ter presente quais os nós respectivos para cada recurso, para que

depois de encontrada a solução óptima se poder fazer o escalonamento em

Modelos Matemáticos

17-05-02 Masp – grupo 1 6

termos temporais dos diversos recursos; a identificação através dos nós só

serve para resolução do problema, já que um recurso pode aparecer mais de

que uma vez na rede, e nessa altura terá que ser tratado como se diferentes

recursos se tratassem,

1ª OPERAÇÃO (1)

E1 = min { E0 + W0 [1] } // só entra um arco em cada um destes nós por

E2 = min { E0 + W0 [2] } isso a solução até aqui é imediata;

E3 = min { E0 + W0 [3] }

2ª OPERAÇÃO (2)

E4 = min { E1 + W1 [4] ; E2 + W2 [4] }

E5 = min { E1 + W1 [5] }

E6 = min { E2 + W2 [6] ; E3 + W3 [6] }

3ª OPERAÇÃO (3)

E7 = min { E4 + W4 [7] }

E8 = min { E5 + W5 [8] ; E6 + W6 [8] }

E9 = min { E4 + W4 [9] ; E6 + W6 [9] }

4ª OPERAÇÃO (4)

E10 = min { E7 + W7 [10] ; E5 + W5 [10] }

E11 = min { E7 + W7 [11] ; E8 + W8 [11] ; E9 + W9 [11] }

SOLUÇÃO FINAL:

E12 = min { E8 ; E10 ; E11 } >>> solução óptima

Modelos Matemáticos

17-05-02 Masp – grupo 1 7

Modelo matemático generalizado:

Para todas as operações que compõem a rede calcula-se o valor

mínimo (E) para todos os nós que lhe estão associados, em que o valor mínimo

de cada nó é encontrado da seguinte forma:

Sendo h = [0,...,r] o conjunto de nós pertencentes à rede, “m” o índice

do nó para o qual se está a calcular o valor mínimo ( m e h ), e [n,...,t] o

intervalo de índices associados aos nós precedentes, que têm arcos a “entrar”

no nó “m”...

Em = min { En + Wn [m] ; .... ; Et + Wt [m] }, para m e [0,r-1]

Tendo que para inicializar E0 = 0;

E que a solução óptima é encontrada quando se encontrar o valor

mínimo para Er e que é calculado da seguinte forma:

Er = min { Ey ;...; Ex } em que [y,...,x] e [0,...,r-1] e que define o

conjunto de nós que têm arcos com destino ao nó “r”;

De referir que o nó 0 e “r” não estão associados a recursos mas sim a

marcas que representam o início e fim da rede;

NOTA:

A fim de se entender este raciocínio, é aconselhável ter presente um dos

esquemas das redes que foram criadas;

Tendo em conta que objectivo é implementar este sistema em MATLAB, é

possível que este modelo tenha que ser revisto e completado a fim de se ter

toda a rede representada em forma matemática.

Modelos Matemáticos

17-05-02 Masp – grupo 1 8

Dijkstra com variável de ocupação da rede

Este método é idêntico ao método de dijktra simples para apenas um

grafo. A sua aplicação para apenas um grafo é idêntica à acima mencionado

tendo por isso sido decidido apenas apresentar o modelo matemático.

Função objectivo:

[ ]

+∑ ∑∑

= ==

N

i

N

qij

qijiJij

qijiJ

N

J

pxtpxcMIN1 1

_2_11

)**()**(

Restrições:

1. ∑∑==

−N

k

qik

N

k

qki xx

11

; i=1,...,N q=1,...,N (Assegura a continuidade da

rede )

2. ij

ij

p

ptd

_2

_1= ;

101

011

111

_2_1_2_1

_2_1_2_1

_2_1_2_1

=∧=⇒<⇒<

=∧=⇒>⇒>

=∧=⇒=⇒=

ijijijij

ijijijij

ijijijij

pppptd

pppptd

pppptd

3. ( )1,0∈qkix

Definição de variáveis:

v iJc -custo de processamento (i,j)

v 1≠qijx se (i,j) encontrar-se ocupado no processamento de um produto,

caso contrário 0=qijx

v ijp _1 - Peso da decisão em se optar pelo peso do custo 1_1 =⇒ ijp

v ijp _2 - Peso da decisão em se optar pelo peso do tempo 1_2 =⇒ ijp

v td – taxa de decisão

Modelos Matemáticos

17-05-02 Masp – grupo 1 9

A ideia subjacente a este modelo será a do operador definir à partida um

determinado peso para o custo e para o tempo, de forma a permitir uma melhor

decisão, tendo sempre em conta a ocupação das máquinas.

Modelos Matemáticos

17-05-02 Masp – grupo 1 10

Método ‘ k shortest path’

Introdução ao ‘ k shortest path’

Este algoritmo é uma generalização do problema de caminho mínimo

em que são obtidos não um mas vários caminhos mínimos unindo um nó

inicial s e um nó de destino t. O objectivo é listar k caminhos que unem

dois pontos de um grafo com o menor comprimento total.

A ideia essencial deste algoritmo é calcular vários caminhos mínimos

partindo não do nó inicial mas do final. Dessa forma é sempre possível

conhecer o valor ao ponto inicial em qualquer ponto da rede. È por isso o

contrário do normal algoritmo de Dijkstra.

Resolver do problema especifico usando a forma tabular:

Letra representa recursos e algarismos representam operação;

Dentro de ( ) está atribuição a cada recurso de um valor, para que possa

ser identificado como um nó; um mesmo recurso pode então estar

representado por mais de um nó diferente;

Analisando o grafo e considerando a soma dos diferentes parâmetros

tempo e custo, considerando-os unitários ou seja com a mesma importância

para o problema, obtêm-se a seguinte tabela :

F (12) A4 (11) F4 (10) B3 (9) C3 (8) D3 (7) D2 (6) B2 (5) C2 (4) E1 (3) F1 (2) A1 (1) I (0)

0 0 6 8 4 14 16 9 13 12 21 30

E 0 8 7 20 10 15 20 18

↑ ↑ ↑ 19

Valor mínimo até ao nó respectivo (cada operação tem apenas um valor mínimo)

Valor mínimo óptimo final, calculado através do mínimo dos valores a mínimos

Valor que não o mínimo

E>>> valor mínimo

Modelos Matemáticos

17-05-02 Masp – grupo 1 11

A solução deste problema é a seguinte sequência: E1 >> D2 >> C3

Em seguida demonstra-se a resolução do mesmo problema mas

considerando o valor de cada ramo em função das duas variáveis já referidas;

W = T*x + C*y

F (12) A4 (11) F4 (10) B3 (9) C3 (8) D3 (7) D2 (6)

0x + 0y 0x + 0y 5x + 1y 5x + 3y 2x + 2y 10x + 4y

E 0x + 0y 5x+ 3y 5x + 2y

B2 (5) C2 (4) E1 (3) F1 (2) A1 (1) I (0)

10x + 6y 7x + 3y 8x + 5y 7x + 5y 12x + 9y 11x+ 12y

11x+ 9y 5x + 4y 11x + 5y 12x + 9y 11x + 7y

9x+ 11y 10x + 10y 17x+ 14y

15x+15y

Resolvendo então o nosso problema em função dos “pesos” das variáveis

Tempo e Custo, verifica-se que a solução do problema se mantém a mesma

independente dos referidos parâmetros.

No entanto vê-se que os melhores caminhos alternativos podem variar de

acordo com os pesos atribuídos aos diferentes parâmetros.

O grande interesse deste método é reconhecer para cada nó qual é o

valor mais curto de chegada ao nó final e qual o melhor caminho para o fazer.

Caminho óptimo E1 -> 13 D2 ->7 C3 -> 0 Final 18

F1-> 12 D2->7 C3->0 Final 19

A1->20 C2->9 D4->4 F5->0 Final 30

Modelos Matemáticos

17-05-02 Masp – grupo 1 12

Grafo do caminho óptimo e caminhos totais alternativos considerando os tempos e

custos com pesos iguais

Poderemos ver que estes são caminhos directos mas podem ser

calculadas as distâncias para caminhos não directos através da inserção de

outro caminho da rede. Para o cálculo da perda de distância poder-se-á utilizar

a fórmula:

δ(e)= l(e) + d(head(e),t)-d(tail(e),t)

em que:

δ(e) : corresponde à variação no caminho total com a inclusão do novo

braço e.

l(e) : valor de percorrer o novo braço e

d(head(e),t): distância mínima associada ao nó que separa o Início do

arco e e o nó final

d(tail(e),t): distância mínima associada ao nó que separa o fim do arco de

e o nó final

por exemplo, se quisermos não passar pelo nó C3 por alguma

impossibilidade e em vez disso formos por B3 temos um acrescento ao

caminho mínimo de:

δ(D2->B3) = -(5+3) +7-6=7

Modelos Matemáticos

17-05-02 Masp – grupo 1 13

Daqui se pode concluir que alterando o percurso para incluir o nó B3 em

vez de C3 gastamos mais 7 unidades de distância.

De notar que se o nó a incluir já pertencer ao caminho óptimo temos que a

variação terá o valor zero.

Modelo Matemático

Em seguida passa-se apresentar um modelo matemático para este

problema:

- primeiramente temos uma solução orientada ao nosso problema

especifico

- em seguida e em função disso tenta-se retirar um modelo generalizado

que sirva para qualquer outro problema deste tipo;

ESPECIFICAÇÕES:

W = X*T + Y*C

em que...

W → Peso total do arco;

T → Tempo de operação;

C → Custo de operação;

X,Y → pesos das variáveis que estão em jogo;

Wi [j] → Peso do arco com origem em i e destino em j; i,j ε [0,12]

Ek → Valor mínimo até ao nó k; k e [0,12]

E [12] = 0 → Ponto de partida;

E [0] → Solução óptima a encontrar;

1ª OPERAÇÃO (4)

E12 = min { E11 + E10 + E8 } // o nó final é único e o valor inicial será

neste caso é sempre 0

E12 = E11 = E10 = E8 // devido à forma como estamos a

considerar o problema

Modelos Matemáticos

17-05-02 Masp – grupo 1 14

2ª OPERAÇÃO (3)

E9 = min { E11 + W9 [11] }

E8 = min { E12 ; E11 + W8 [11] }

E7 = min { E10 + W7 [10] ; E11 + W7 [11] }

3ª OPERAÇÃO (2)

E6 = min { E9 + W6 [9] ; E8 + W6 [8] }

E5 = min { E8 + W5 [8] ; E10 + W5 [10] }

E4 = min { E9 + W4 [9] ; E7 + W7 [7] }

4ª OPERAÇÃO (1)

E3 = min { E6 + W3 [6] }

E2 = min { E6 + W2 [6] ; E4 + W2 [4] }

E1 = min { E4 + W1 [4] ; E5 + W1 [5] }

SOLUÇÃO FINAL:

E0 = min { E1+ W0 [1] ; E2 + W0 [2]; E3 + W0 [3] } >>> solução óptima

Modelo matemático generalizado:

Para todas as operações que compõem a rede calcula-se o valor

mínimo (E) para todos os nós que lhe estão associados, em que o valor mínimo

de cada nó é encontrado da seguinte forma:

Em = min { En + Wm [n] ; .... ; Et + Wm [t] }

para m e [0,r-1] e m anterior a n

Sendo:

h = [0,...,r] o conjunto de nós pertencentes à rede

m, o índice do nó para o qual se está a calcular o valor mínimo ( m e h ),

Modelos Matemáticos

17-05-02 Masp – grupo 1 15

[n,...,t] o intervalo de índices associados aos nós precedentes, que têm

arcos a “entrar” no nó “m”...

A inicialização ocorre para Er = 0;

A solução óptima é encontrada quando se encontrar o valor mínimo para

Er e que é calculado da seguinte forma:

E0 = min { Ey ;...; Ex }

em que [y,...,x] e [0,...,r-1] e que define o conjunto de nós que têm arcos

com destino ao nó “0”;

De referir que o nó 0 e “r” não estão associados a recursos mas sim a

marcas que representam o início e fim da rede;

Um algoritmo de trocas englobado neste modelo foi já referido e é

formulado matematicamente através de:

δ (em[n])= Wm[n] + Em - En)

em que:

em[n] : novo braço a incluir no grafo partindo de um nó inicial m e

terminando no nó final n

δ(em[n]) : corresponde à variação no caminho total com a inclusão do

novo braço Em.

Modelos Matemáticos

17-05-02 Masp – grupo 1 16

Algoritmo A star

A teoria do A* é relativamente simples. Basicamente, cada nó (posição)

no gráfico tem três atributos principais: f, g e h .

g é o custo de chegar ao ponto. Este normalmente é o custo de mudar

um nó mais o custo do nó pai.

h é a distância à meta - não tem que ser a distância real (A * tem muitas

aplicação - pathfinder é um).

Podemos definir uma classe de heurísticas admissíveis de estratégias

de procura usando a função evolução:

f(n) =g(n)+h(n). f(n)

representa uma estimativa do custo total do caminho desde o início, por n até

ao objectivo.

Também há duas listas, Aberto e Fechado. Na lista aberta estão todos

os nó que não foram explorados. Por explorar, quero dizer todas as posições

adjacentes que foram abertas (também passou para a lista Aberta), ou não

podem ser aberto. Na lista fechada estão todos os nós que foram explorados.

O algoritmo de A* pode ser definido da seguinte forma:

1. Iniciar no primeiro nó;

2. Se o nó actual é o objectivo então, deve-se parar a pesquisa;

3. Se o nó actual não é o nó final, então escolhe-se o caminho com

a menor estimativa;

4. Repetir o ponto 2.

Desta forma temos que calcular todos os caminhos conhecidos desde o

início até ao fim. Com esta informação da estimativa vamos escolher o melhor

caminho.

Modelos Matemáticos

17-05-02 Masp – grupo 1 17

Aplicação do método - Atribuição do valores aos nós

Resultado final

O caminho mínimo está demarcado por uma linha vermelha.