De acordo com o Plano de Ensino do Currículo 215 ... · Princípios da Teoria de Grafos, problemas clássicos de transporte (equilibrado e desequilibrado), problemas de ... 2.5 Problemas

Engenharias CCE 1014 - Pesquisa Operacional II - 2018/1

Prof. Marcelo Sucena Página 1 de 41

De acordo com o Plano de Ensino do Currículo 215 apresentado na visita do MEC em 2016, no

Campus Niterói.

Disciplina: CCE1014 - PESQUISA OPERACIONAL II

PERFIL DO DOCENTE

Docente graduado em engenharia ou matemática, com pós-graduação em áreas das engenharias ou matemática. Preferência para mestrado ou doutorado. Deve ter domínio das técnicas da pesquisa operacional com ênfase em Teoria de Grafos, Análise Envoltória de Dados, Análise Hierárquica, Programação Linear e Programação Dinâmica.

CONTEXTUALIZAÇÃO

O processo decisório nas organizações é um tema abrangente e complexo, pois envolve variáveis controladas e não controladas, em ambientes que agem e reagem às mudanças nos cenários, com diversas tecnologias diferentes. Assim, os gestores necessitam ter embasamento sobre as condições de otimização e racionalização dos processos produtivos, permitindo desenvolver ações controláveis e calcadas em processos consistentes e seguros.

EMENTA

Princípios da Teoria de Grafos, problemas clássicos de transporte (equilibrado e desequilibrado), problemas de transporte, problemas de minimização de redes, caminho mínimo, problemas de designação, fluxo máximo, problemas do caixeiro viajante. PERT-CPM como grafo. Análise Hierárquica (AHP).

OBJETIVO GERAL

Desenvolver técnicas que possam subsidiar o engenheiro de produção na determinação de alternativas para o processo decisório complexo.

OBJETIVOS ESPECÍFICOS

Permitir ao aluno a aplicação de técnicas de pesquisa operacional em casos práticos da engenharia de produção.

CONTEÚDOS

UNIDADE 1 - Problemas de Conexão 1.1 Conceitos de Teoria de Grafos 1.2 Problemas de Minimização de Redes. 1.2.1. PRIM 1.2.2. Kruskal 1.3 Problemas do Caminho Mínimo - Dijkstra UNIDADE 2 - Fluxos em Redes 2.1 Características 2.2 Problemas de Transporte 2.3 Problema de Designação 2.4 Problema de Transbordo 2.5 Problemas do Caminho mais Curto ou PERT com CPM 2.6 Problemas de Fluxo Máximo – Ford-Fulkerson UNIDADE 3 - Problema do Caixeiro Viajante 3.1. Características 3.2. Problemas de Cobertura de nós 3.2.1. Método do Vértice Adjacente mais Próximo 3.2.2. Método da Inserção com Menor Encargo. 3.2.3. Método da Inserção com maior afastamento. UNIDADE 4 – Análise Multicritério à Decisão 4.1. Conceitos sobre Processo Decisório Multicritério 4.2. Análise Hierárquica - AHP

BIBLIOGRAFIA BÁSICA

Belfiore, Patrícia e Fávero, Luiz Paulo Pesquisa Operacional para os Cursos de Engenharia Ed. Campus, 2012. Goldbarg, Marco e Goldbarg Elizabeth Grafos - Conceitos, Algoritmos e Aplicações Ed. Campus, 2012 Costa, Helder Gomes Auxílio Multicrédito à Decisão - Método AHP Ed. ABEPRO,



LACHTERMACHER, Gerson. Pesquisa Operacional na Tomada de Decisões. Ed.Campus, 2006.

BIBLIOGRAFIA COMPLEMENTAR

Netto, Paulo Oswaldo Boaventura Grafos - Introdução e Prática Ed. Blucher, 2009.



UNIDADE 1 - Problemas de Conexão 1.1 Conceitos de Teoria de Grafos

Área contida na Pesquisa Operacional. Pode ser considerada como uma teoria

baseada na interligação de pontos e linhas, utilizada principalmente na solução de problemas de roteamento.

Em 1736, o matemático suíço Leonhard Euler (1707-1783) resolveu o primeiro problema (”O problema das pontes de Konigsberg”) cuja solução veio a originar a teoria dos grafos. O problema era análogo aos atuais quebra-cabeças, baseados em desenho, cujas linhas devem ser percorridas sem que se tire o lápis do papel e sem passar duas vezes sobre a mesma linha. Em 1847, o alemão, físico e matemático Gustav Robert Kirchhoff (1824-1887), iniciou o estudo de certo tipo de grafo chamado árvores quando estudava problemas de circuitos elétricos. Hamilton, em 1859, estudou problemas de caminhos.

Um Grafo é definido como sendo um par ordenado (V, A). Os elementos de V são denominados vértices ou nós do grafo e os pares ordenados de A, denominados de arestas ou arcos do grafo.

Quanto às características de seus arcos, um grafo pode ser: 1. Orientado (dígrafo) ou não orientado: são orientados quando os seus arcos

possuem uma orientação definida; e não orientados, quando não existe noção de direção. Quando os arcos não possuem direção, são denominados arestas e quando possuem são denominados arcos.

G1 (V1, A1) V1 = {n | n é uma pessoa da aula} A1 = {(v,w) | < v é amigo de w >} V1 = {Ciclano, Fulano, Beltrano} A1 = (Ciclano, Beltrano), (Fulano, Beltrano)}

Observar a Relação Simétrica (aresta não tem orientação):

se <v é amigo de w> então <w é amigo de v>

G2 (V2, A2) V2 = {n | n é uma pessoa da família} A2 = {(v,w) | < v é pai de w >} V2 = {Ciclano, Fulano, Beltrano} A2 = (Ciclano, Beltrano), (Beltrano, Fulano)}

2. Valorado e não valorado: é valorado quando existem valores atribuídos a cada um dos seus arcos.

G3 (V3, A3) V3 = {n | n é um cliente de certa loja}

A3 = {(v,w, ) | <há estrada ligando v a w, sendo o tempo efetivo de transporte entre eles>}

Ciclano Beltrano

Fulano

Ciclano Beltrano

Fulano



Quanto às características gerais tem-se que:

A ordem de um grafo G é dada pela quantidade de vértices de G. No Grafo G2 do exemplo de Ciclano, Fulano e Beltrano a ordem(G2) = 3.

Em um grafo dois vértices v e w são adjacentes se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w. No Grafo G2 do exemplo de Ciclano, Fulano e Beltrano, Ciclano e Beltrano são adjacentes.

Um vértice w é sucessor de v se há um arco que parte de v e chega em w. No Grafo G2 do exemplo de Ciclano, Fulano e Beltrano, Beltrano é sucessor de Ciclano.

Um vértice v é antecessor de w se há um arco que parte de v e chega em w. No Grafo G2 do exemplo de Ciclano, Fulano e Beltrano, Ciclano é antecessor de Beltrano.

O grau de um vértice é dado pela quantidade de arestas que lhe são incidentes. No Grafo G1 do exemplo de Ciclano, Fulano e Beltrano, o grau(Beltrano) = 2 e o grau(Fulano) = 1.

Para Grafo Orientado se avalia o Grau como: o Grau de emissão: o grau de emissão de um vértice v corresponde a

quantidade de arcos que partem de v. o Grau de recepção: o grau de recepção de um vértice v corresponde a

quantidade de arcos que chegam a v.

Um vértice v é uma fonte se grauDeRecepção(v) = 0.

Um vértice v é um sumidouro se grauDeEmissão(v) = 0.

Alguns outros aspectos importantes devem ser considerados em relação aos Grafos:

Quando um arco é incidente a um único vértice é denominado "laço".

Dois vértices são considerados "adjacentes" se eles estão interligados por um arco.

Uma "cadeia" é uma sequência de arcos (orientados ou não). O tamanho de uma cadeia está relacionada ao número de arcos que a compõe.

Um "caminho" é uma cadeia em que todos os arcos têm a mesma direção, ou seja, é um grafo com conjunto de vértices da forma {1, 2, 3, . . , k–1, k} e conjunto de arestas da forma {{1,2} , {2,3}} , . . , {k–1, k}}.

Um "ciclo" é uma cadeia cujo vértice inicial e final é o mesmo (cadeia fechada), isto é, é um grafo com conjunto de vértices da forma {1, 2, 3, . . , k–1, k} e conjunto de arestas da forma {{1,2} , {2,3}} , . . , {k–1, k}, {k,1}}

Um grafo é "conexo" quando existe um caminho entre cada par de vértices, ou seja, se para todo par x, y de vértices existe um caminho que liga x a y; caso contrário, o grafo é “desconexo”.

A figura a seguir mostra a representação gráfica de um grafo orientado. G(V,A) => V={V1,V2,V3,V4} e A={V1V2,V2V3,V3V4,V4V1}

V1 V2

V3 V4



Quando em um grafo existe a associação de um ou mais valores aos arcos e/ou nós, pode-se defini-lo como uma rede.

Sendo assim, pode-se representar uma rede como R={V,A,}, onde V e A são,

respectivamente, os conjuntos de nós e arcos que formam um grafo, e , os parâmetros associados aos elementos do conjunto A e/ou do conjunto V.

A seguir apresenta-se um exemplo de grafo com os parâmetros nos arcos e nós.

Podem-se citar alguns valores de associados aos arcos: a capacidade de fluxo, que corresponde ao limite que pode passar pelo arco; o custo no arco, que pode ser considerado como um valor monetário, a

distância percorrida ou o tempo de viagem no arco e o fluxo no arco.

Existem também os valores de associados aos nós: população de uma cidade; número de produtos fabricados em uma unidade e demanda de produtos em uma área geográfica.

Os problemas de otimização de redes podem ocorrer em várias áreas, mas

geralmente são encontrados nas áreas de transportes e comunicações. Um problema típico de transporte consiste em encontrar uma rota, partindo de uma origem para um destino, considerando que entre esses pontos existem diversas rotas alternativas e que necessita-se minimizar ou maximizar alguma medida associada aos arcos e/ou nós.

Existem outros problemas em que se necessita minimizar os valores associados aos arcos, de forma que possa atender todos os pontos de uma rede. A seguir serão relacionados vários algoritmos que objetivam a modelagem de redes.

1.2 Problemas de Minimização de Redes.

Os algoritmos de minimização de redes tratam da árvore de valor mínimo em problemas de interligação de redes não orientadas de comunicação, luz, água, esgoto, minerodutos, gasodutos etc. com o objetivo de atender todos os nós de uma rede, minimizando o consumo dos meios.

Goldbarg et al. (2000) destaca que os problemas de Steiner em grafos não direcionados é o problema de conectar, a custo mínimo, um conjunto de nós de um grafo. Em alguns problemas desses o problema se reduz a análise do caminho mais curto entre dois nós. Se todos os nós forem conectados, chega-se a solução de uma árvore geradora mínima.

1.2.1. PRIM

Este algoritmo compreende os seguintes passos:

V1 V2

V3 V4

α12

α23 α34

α41 α2

α3 α4

α1



1º passo: selecionar qualquer nó da rede e o inserir no conjunto C (árvore

mínima). O conjunto C* é formado pelos nós não conectados.

2º passo: identificar o nó do conjunto C* que está mais próximo de qualquer um

dos nós do conjunto C. Deve-se repetir este processo até que todos os nós

estejam conectados (C* = ).

Exemplo: Considere o grafo a seguir e avalie quais ligações que deverão ser implantadas visando a interligação de todos os nós, porém, considerando uma quilometragem total mínima. Os atributos dos arcos representam as distâncias entre as regiões.

C1 = { 4 } e C*1 = { 1,2,3,5,6 } => C2 = { 4,3 } e C*2 = { 1,2,5,6 } => C3 = { 4,3,2 } e C*3 = { 1,5,6 } => C4 = { 4,3,2,1 } e C*4 = { 5,6 } =>

C5 = { 4,3,2,1,5 } e C*5 = { 6 } => C6 = { 4,3,2,1,5,6 } e C*6 =

Resultado Final: 12Km

1.2.2. Kruskal

Deve-se construir uma árvore, selecionando-se arcos, iniciando-se pelo arco de menor atributo, adicionando-os em ordem crescente de atributos, de modo a não formar ciclos com os arcos já selecionados. O "ponto de parada" do algoritmo é identificado quando a árvore possuir n-1 arcos conectados, sendo "n" o número de nós do grafo.


1º passo: colocar os arcos em ordem crescente de valor. Estes arcos fazem parte

de um conjunto "A*" de arcos não conectados. Inicialmente A é vazio, ou seja,

A=.

1

2 6

3 5

4 3 5

3

3 6

2

9

3

7

1

1

2 6

3 5

4

3

3

2 3

1



2º passo: selecionar o menor dos arcos de A* que não forme um ciclo com os

demais e coloque-o no conjunto A. Um arco forma um ciclo quando os vértices

deste arco já fazem parte da árvore mínima em construção.

3º passo: se A possui n-1 arcos, sendo "n" o número de nós, deve-se parar o

algoritmo, pois os arcos de A compõem a árvore mínima. Caso contrário voltar

para o passo 2.

Exemplo: Utilizando o mesmo grafo do exemplo anterior, identifique a árvore mínima pelo algoritmo de Kruskal. Passo 1 A* = {(3,4),(3,2),(1,2),(3,5),(6,5),(1,4),(4,5),(3,6),(3,1),(2,6)}

A = Passo 2 A = {(3,4)} A* = {(3,2),(1,2),(3,5),(6,5),(1,4),(4,5),(3,6),(3,1),(2,6)} Passo 3 n = 6 e n-1 = 5

O número de elementos de A é igual a 1, e como n(A) < 5, deve-se retornar ao passo 2.

Passo 2 A = {(3,4), (3,2)} A* = {(1,2),(3,5),(6,5),(1,4),(4,5),(3,6),(3,1),(2,6)} Passo 3 n = 6 e n-1 = 5


Passo 2 A = {(3,4), (3,2), (1,2)} A* = {(3,5),(6,5),(1,4),(4,5),(3,6),(3,1),(2,6)} Passo 3 n = 6 e n-1 = 5


Passo 2 A = {(3,4), (3,2), (1,2), (3,5)} A* = {(6,5),(1,4),(4,5),(3,6),(3,1),(2,6)} Passo 3 n = 6 e n-1 = 5


Passo 2 A = {(3,4), (3,2), (1,2), (3,5), (6,5)} A* = {(1,4),(4,5),(3,6),(3,1),(2,6)} Passo 3 n = 6 e n-1 = 5



O número de elementos de A é igual a 5, e como n(A) = 5, deve-se parar o processo de análise. Resultado Final: 12Km 1.3 Problemas do Caminho Mínimo - Dijkstra

Em uma rede, dependendo das suas características construtivas, podem existir vários caminhos entre um par de nós (origem/destino). Entre os caminhos possíveis, aquele que possui menor "peso" é chamado de caminho mínimo. Este peso pode ser representado pela soma dos atributos dos arcos que formam o caminho, tais como, tempo de viagem, distância percorrida etc..

Para Goldbarg et al. (2000) o problema de caminho mínimo também é um problema de Emparelhamento. Eles destacam que o emparelhamento nada mais é que uma forma de reunião ou ligação entre dois elementos ou, no caso dos grafos, dois vértices.

Para resolver problemas desse tipo, há vários algoritmos (Ford, Faude, Bellman, Dijkstra, Floyd, Hasse dentre outros) que envolvem maior ou menor complexidade de cálculo (número de operações elementares, tais como adição, subtração, multiplicação etc.). O algoritmo de Dijkstra foi desenvolvido em 1959 e posteriormente Dantizg (1960) e Nicholson (1960) desenvolveram um algoritmo de duas árvores de Dijkstra, cuja idéia é construir árvores de caminhos mínimos de um nó de origem e de um nó de destino, simultaneamente.

O algoritmo de Dijkstra é utilizado para determinar o caminho mínimo de um nó para outro nó ou para todos os outros nós da rede, considerando que os atributos dos arcos são positivos. Todos os arcos devem ser orientados. Nele, considera-se que um nó é "fechado" quando se encontra o caminho mínimo da origem até este nó, e aqueles nós cujos caminhos mínimos ainda não foram encontrados são considerados "abertos". O conceito de fechado ou aberto está associado à impossibilidade de encontrar um caminho melhor do que o já encontrado, assim enquanto o nó não é fechado (ou rotulado) ainda é possível encontrar um caminho de menor valor até este nó.


1

2 6

3 5

4

3

3

2 3

1



1º passo: considerando que d( x )i = min { d( x )i - 1, d( y ) + d( y , x ) }, onde (1)

d( x )i é o tamanho do caminho da origem até o nó x.

i é o número de iterações.

d( y ) é o tamanho do caminho da origem até o nó fechado ( y ). d( y , x ) é o tamanho do arco ( y , x ). Atribui-se um valor d( x ) para cada um dos nós do grafo, sendo: d(origem) = 0

d(os outros nós) = Considerar "y" o último nó rotulado (fechado). No início do algoritmo o nó de origem é o único rotulado, ou seja y = origem.

2º passo: para cada nó x não fechado, redefine-se d( x ) conforme expressão 1.

O nó aberto que possuir o menor valor d( x ) é fechado e faz-se y = x.

3º passo: se o nó de destino foi fechado então se deve parar a execução do

algoritmo, senão, volte ao passo 2.

Observação: para determinar a sequência de nós que forma o caminho com

distância mínima, deve-se, retroceder a partir do nó de saída, procurar os nós com etiquetas definitivas cuja diferença é igual à distância associada ao arco que os une.

Exemplo: Utilizando o grafo a seguir, identifique o seu caminho mínimo utilizando o

algoritmo de Dijkstra:

1. d(O) = 0 e d(1), d(2), d(3), d(4), d(D) = 2. d(O) -> y = O i = 1, ou seja, 1ª iteração.

d(1)1 = min{d(1)0, d(O) + d(O,1)} = min { , 0+4} = 4

d(2)1 = min{d(2)0, d(O) + d(O,2)} = min { , 0+3} = 3

d(3)1 = min{ , 0+3} = 3

d(4)1 = min{ , 0+} =

d(D)1 = min{ , 0+} =

3. Identificar o mínimo entre as distâncias e definir y. Escolhe-se entre d(2) e d(3), pois esses apresentam atributos iguais a 3. Optou-se por y = 2 (nó fechado). Se y = D o problema está terminado, senão continuar do passo 2.

O

1 2

3 4

D

4

3 2

2

2

3

3

3



2. i = 2, ou seja, 2ª iteração.

d(1)2 = min{d(1)1, d(2) + d(2,1)} = min { 4, 3+} = 4

d(3)2 = min{d(3)1, d(2) + d(2,3)} = min { 3, 3+} = 3

d(4)2 = min{ , 3+} =

d(D)2 = min{ , 3+2} = 5

3. Mínimo entre as distâncias 4,3, e 5 é 3, ou seja, y = 3. O nó y é diferente de D, então continuar do passo 2. 2. i = 3, ou seja, 3ª iteração.

d(1)3 = min{d(1)2, d(3) + d(3,1)} = min { 4, 3+} = 4

d(4)3 = min{d(4)2, d(3) + d(3,4)} = min { , 3+3} = 6

d(D)3 = min{ 5, 3+} = 5

3. Mínimo entre as distâncias 4,6 e 5 é 4, ou seja, y = 1. O nó y é diferente de D, então continuar do passo 2. 2. i = 4, ou seja, 4ª iteração. d(4)4 = min{d(4)3, d(1) + d(1,4)} = min {6, 4+2} = 6

d(D)4 = min{ 5, 4+} = 5 3. Mínimo entre as distâncias 6 e 5 é 5, ou seja, y = D. O nó y agora é igual a D, então deve-se parar o processo de avaliação.

Perguntam-se: Em qual iteração foi encontrado o primeiro valor de D (d(D) = 5)? Na 2ª iteração. Qual era o valor de y nessa iteração? Na 2ª iteração, y é igual a 2. Identificou-se o nó anterior ao destino: nó 2. Em qual iteração foi encontrado o primeiro valor de 2 (d(2) = 3)? Na 1ª iteração. Qual era o valor de y nessa iteração? Na 1ª iteração, y é igual a O.

O

2

D

2

3



UNIDADE 2 - Fluxos em Redes 2.1 Características

É a possibilidade de transferência de algum produto quantificável e sujeito às restrições de equilíbrio, de uma origem para um destino, fluindo por uma Rede.

Uma Rede R = (V, A, α) é um grafo orientado onde cada aresta (u, v) ∈ A e tem uma capacidade não negativa c(u, v) ≥ 0. Se (u, v) ∉ A, se supõe que c(u, v) = 0. Essa análise de fluxo considera que existem dois vértices específicos, ou seja, uma origem (u) e um destino (v).

Como exemplo de aplicação tome um grafo onde cada arco representa uma rua em um centro urbano. O valor α de cada aresta indica a sua capacidade, ou seja, o maior fluxo possível ao longo da rua (veículos/hora). Uma possibilidade de questionamento é qual é a maior quantidade possível de veículos que pode viajar da origem u para o destino v em uma hora? 2.2 Problemas de Transporte

O Problema de Transporte constitui uma das principais aplicações da PL para auxiliar o planejamento e a operação de transportes.

O Problema pode ser formulado inicialmente da seguinte forma: considerando-se o transporte de produtos de m origens, onde estão estocados, para n destinos, onde são necessários.

Conhecendo-se os custos unitários de transporte de cada origem para cada destino (Cij – custo unitário de transporte da origem i para o destino j), deve-se decidir quanto transportar de cada origem para cada destino (Xij – quantidade a ser transportada da origem i para o destino j), de modo gastar o menos possível, ou seja, minimizar o custo total de transporte. Cada uma das origens é dotada de a i unidades disponíveis e, cada um dos destinos requer bj unidades, todos inteiros e positivos. 2.3 Problema de Designação

Um Problema de Designação é um caso especial dos Problemas de Transporte.

Ele consiste em designar cada uma das origens a cada um dos destinos, exclusivamente, de maneira a otimizar (minimizar ou maximizar) uma impedância, por isso, a quantidade de origens deve ser igual a de destinos.

Para demonstrar o algoritmo, usar-se-á um exemplo conforme a seguir. Para transportar máquinas de quatro origens para quatro destinos, devem-se

minimizar os custos totais de movimentação. A tabela a seguir expõe os custos das movimentações entre origens e destinos.

D1 D2 D3 D4

O1 10 12 15 16

O2 14 12 13 18

O3 10 16 19 15

O4 14 12 13 15

1º Passo - Subtrair em cada célula, de cada linha, o menor valor daquela linha.



2º Passo - Em seguida efetuar o mesmo procedimento para as colunas. Como resultado, uma nova tabela deverá expressar esses resultados, onde cada linha e cada coluna devem ter pelo menos um ZERO.

As próximas tabelas expressam os resultados, para subtração nas linhas e depois

nas colunas.

D1 D2 D3 D4

O1 0 2 5 6

O2 2 0 1 6

O3 0 6 9 5

O4 2 0 1 3

D1 D2 D3 D4

O1 0 2 4 3

O2 2 0 0 3

O3 0 6 8 2

O4 2 0 0 0

3º Passo – Deve-se designar as origens para os destinos nas células onde aparece

o elemento ZERO. Preferência para as linhas e colunas que tenham apenas um ZERO. Cada designação efetuada invalida os ZEROS existentes nas linhas e colunas designadas. O problema acaba se todas as origens forem designadas aos destinos existentes.

D1 D2 D3 D4

O1 0 2 4 3

O2 2 0 0 3

O3 0 6 8 2

O4 2 0 0 0

Verifica-se que a designação não terminou, pois a linha O3 não foi designada. 4º Passo – Deve-se então cobrir os ZEROS da tabela com a menor quantidade de

linhas possível. Faz-se o seguinte:

Marcar as linhas sem designação (em cinza); Nas linhas marcadas, marcar as colunas com zeros que não foram cobertos (linhas

tracejadas); Nas colunas marcadas, marcar as linhas com zeros que não foram cobertos (linhas

tracejadas); Nas linhas marcadas, voltar a marcar as colunas com zeros que não foram marcados

até que não seja possível marcar novas linhas ou colunas; Registrar as linhas não marcadas e as colunas marcadas (setas).



D1 D2 D3 D4

O1 0 2 4 3

O2 2 0 0 3

O3 0 6 8 2

O4 2 0 0 0

5º Passo – Encontrar o menor valor dentre os números não cobertos, de todos os

elementos da tabela. O valor é 2. Na próxima tabela, fazer: Os elementos não cobertos ficam diminuídos deste número; Os elementos no cruzamento de coberturas ficam aumentados desse número; Os outros elementos permanecem iguais.

D1 D2 D3 D4

O1 0 2-2=0 4-2=2 3-2=1

O2 2+2=4 0 0 3

O3 0 6-2=4 8-2=6 2-2=0

O4 2+2=4 0 0 0

Voltar ao 3º passo e designar as origens aos destinos, novamente.

D1 D2 D3 D4

O1 0 0 2 1

O2 4 0 0 3

O3 0 4 6 0

O4 4 0 0 0

Verifica-se, então, que todas as origens foram designadas aos seus destinos. O

resultado é: O1D1 - custo da tabela inicial = 10 O2D2 - custo da tabela inicial = 12 O3D4 - custo da tabela inicial = 15 O4D3 - custo da tabela inicial = 13 Custo total = 50

Para o caso de maximização, deve-se substituir o quadro por um de minimização.

O exemplo a seguir ilustra esse procedimento. A tabela a seguir apresenta as eficiências, ou seja, a capacidade de cada vendedor

de atingir o potencial da região (em %), de quatro vendedores, testados em quatro regiões. Os potenciais de vendas, em $, nas regiões são conhecidos. Designar um vendedor para cada região para maximizar o valor total das vendas.



% R1 R2 R3 R4

V1 70 60 80 90

V2 70 80 70 90

V3 60 90 60 70

V4 70 80 70 80

Potencial de vendas ($ x 103): R1 = 100; R2 = 80; R3 = 60; R4 = 90 A próxima tabela relaciona as vendas por região:

% x $ R1 R2 R3 R4

V1 70 x 100 60 x 80 80 x 60 90 x 90

V2 70 x 100 80 x 80 70 x 60 90 x 90

V3 60 x 100 90 x 80 60 x 60 70 x 90

V4 70 x 100 80 x 80 70 x 60 80 x 90

% x $ R1 R2 R3 R4

V1 70 48 48 81

V2 70 64 42 81

V3 60 72 36 63

V4 70 64 42 72

Para transformar em um modelo de minimização, deve-se identificar o maior valor,

subtraindo-o dos demais em cada célula, resultando em:

Minimização R1 R2 R3 R4

V1 11 33 33 0

V2 11 17 39 0

V3 21 9 45 18

V4 11 17 39 9

Agora deve-se aplicar o algoritmo conforme o exemplo anterior. Subtrair o menor número de cada linha.

R1 R2 R3 R4

V1 11 33 33 0

V2 11 17 39 0

V3 21-9=12 9-9=0 45-9=36 18-9=9

V4 11-9=2 17-9=8 39-9=30 9-9=0

Subtrair o menor número de cada coluna.

R1 R2 R3 R4

V1 11-2=9 33 33-30=3 0

V2 11-2=9 17 39-30=9 0

V3 12-2=10 0 36-30=6 9

V4 2-2=0 8 30-30=0 0



Designar os vendedores às regiões.

R1 R2 R3 R4

V1 9 33 3 0

V2 9 17 9 0

V3 10 0 6 9

V4 0 8 0 0

Deve-se continuar, pois não houve designação do vendedor 2 para a região 3.

R1 R2 R3 R4

V1 9 33 3 0

V2 9 17 9 0

V3 10 0 6 9

V4 0 8 0 0

Diminuir os valores contidos nas células não cobertas pelo menor valor entre eles

(neste caso, 3) e, nos cruzamentos de coberturas, adicionar o mesmo valor. Os demais elementos devem ficar iguais.

R1 R2 R3 R4

V1 6 30 0 0

V2 6 14 6 0

V3 10 0 6 12

V4 0 8 0 3

Deve-se designar novamente os vendedores às regiões.

R1 R2 R3 R4

V1 6 30 0 0

V2 6 14 6 0

V3 10 0 6 12

V4 0 8 0 3

A designação final fica: V1 para R3; V2 para R4; V3 para R2 e V4 para R1. A venda total ($ x 103) é: 48 +

81 + 72 + 70 = $ 271.000 2.4 Problema de Transbordo

Como exemplo, considerar a situação exposta a seguir onde existem dois pontos de produção e um ponto de consumo, sendo que há possibilidade de movimentação de produtos entre os pontos de produção.



Observa-se que para movimentar produtos entre a unidade de produção (UP)1 e o

ponto de consumo custa $10. Mas se a movimentação for efetuada por intermédio da UP2 o custo total será de $8. Nota-se, então, que existem custos diferenciados entre a mesma origem e destino.

Quando um nó serve de origem e/ou destino ele é denominado Transbordo. Para demonstrar este problema, pode-se observar na próxima figura que existem 5

nós, sendo 2 UP, 2 pontos de consumo (PC) e um nó central. Todos são denominados de pontos de transbordo, pois servem, simultaneamente, de origem e de destino.

O próximo quadro apresenta os custos de movimentação entre os nós e a

quantidade total produzida da UP1 e da UP2, além da capacidade máxima de consumo dos PC1 e do PC2.

UP1 UP2 Nó central

PC1 PC2 Total

UP1 0 7 20 25 M 10

UP2 7 0 5 M 25 10 Nó

central 20 5 0 6 18 ?

PC1 25 M 6 0 10 ?

PC2 M 25 18 10 0 ? Total ? ? ? 7 18 25/20

Produção 1 Produção 2

Consumo

Custo Unitário de

Movimentação: $5 Custo Unitário de

Movimentação: $3 Custo Unitário de

Movimentação: $10

UP 1 = 10 un. PC 1 = 7 un.

Nó central

$25

UP 2 = 10 un. PC 2 = 18 un.

$6

$5

$20

$7 $10

$25

$18



Considerações: Como não há ligação direta entre a UP1 e o PC2, como também entre a

UP2 e o PC1, utilizou-se um artifício no uso do custo MUITO GRANDE (M); Nos pontos de transbordo se considerou movimentação nula entre os

próprios, individualmente. Como há desequilíbrio entre o somatório das linhas e das colunas deve-se

incluir uma variável fictícia com custo nulo de movimentação. A tabela equilibrada está exposta a seguir.

UP1 UP2 Nó central

PC1 PC2 Total

UP1 0 7 20 25 M 10 UP2 7 0 5 M 25 10

Nó central

20 5 0 6 18 ?

PC1 25 M 6 0 10 ? PC2 M 25 18 10 0 ?

Fictícia 0 0 0 0 0 5

Total ? ? ? 7 18 25/25

A próxima tabela apresenta a colocação de 25 unidades (total nas linhas e nas

colunas) em todas as linhas e colunas. Essa inserção é denominada buffer do transbordo.

UP1 UP2 Nó central

PC1 PC2 Total

UP1 0 7 20 25 M 10+25

UP2 7 0 5 M 25 10+25

Nó central

20 5 0 6 18 25

PC1 25 M 6 0 10 25 PC2 M 25 18 10 0 25

Fictícia 0 0 0 0 0 5 Total 25 25 25 7+25 18+25 150/150

Desta forma, chega-se a um Problema Clássico de Transporte, ou seja, equilíbrio

entre oferta e demanda. Resolve-se este problema como exposto anteriormente.

Resolvendo-se por Vogel e um software proprietário chega-se ao custo total = $420 com a seguinte distribuição de transporte:



UP1 UP2 Nó central

PC1 PC2 Otimização Total

UP1 25 10 0 35 UP2 15 20 -7 35

Nó central 5 20 -12 25 PC1 12 13 -18 25

PC2 25 -28 25

Fictícia 5 -28 5 Otimização 0 7 12 18 28

Total 25 25 25 32 43

Interpretação dos resultados obtidos:

a) UP1: o Movimenta 25 unidades para a própria, o que significa que o buffer não foi utilizado, ou seja, este nó não foi usado como transbordo. o Movimenta 10 unidades para UP2.

b) UP2:

o Movimenta 15 unidades para a própria, o que significa que foram utilizadas 10 unidades do buffer, ou seja, este nó foi usado como transbordo de 10 unidades. o Movimenta 20 unidades para o Ponto Central, ou seja, 10 unidades de estoque mais 10 unidades de transbordo.

c) Nó Central: o Movimenta 5 unidades para o próprio, o que significa que foram utilizadas 20 unidades do buffer, ou seja, este nó foi usado como transbordo de 20 unidades. o Movimenta 20 unidades para o PC1, que na verdade são 20 unidades de transbordo da UP2.

d) PC1:

o Movimenta 12 unidades para o próprio, o que significa que foram utilizadas 13 unidades do buffer, ou seja, este nó foi usado como transbordo de 13 unidades. o Movimenta 13 unidades para o PC2 (deduzidas 20 unidades que vieram do Ponto Central, fica ainda com 7 unidades encomendadas).

e) PC2:

o Movimenta 25 unidades para o próprio, o que significa que não foram utilizadas 25 unidades do buffer, ou seja, este nó não foi usado como transbordo. o Recebe 13 unidades de encomenda do PC1.

Resumindo, o transbordo ocorreu de acordo com a movimentação exposta na figura a

seguir.



2.5 Problemas do Caminho mais Curto ou PERT com CPM

Para se avaliar o desenvolvimento de atividades utiliza-se o gráfico (ou diagrama) de Gantt. É uma técnica simples, mas importante, usada para auxiliar o planejador e o programador, pois apresenta facilidade em controlar o tempo e em reprogramá-lo. Ele foi desenvolvido em 1918, por Henry L.Gantt, e ainda hoje continua a ser uma ferramenta popular no agendamento de produção e de projeto. Sua simplicidade e exibição gráfica clara o tornaram um dispositivo útil para problemas de agendamento simples.

Apesar da sua vantagem, o gráfico de Gantt não possibilita responder algumas questões, como por exemplo: Quais tarefas atrasariam se uma tarefa se atrasar um dia? Como colocar de forma clara os custos no diagrama? Quais tarefas são críticas para a realização de todo o trabalho?

Neste ponto encaixam-se as técnicas PERT e CPM.

A técnica PERT (Program – Project - Evaluation Review Technique) foi desenvolvida no final dos anos 50 pela Navy Special Projects Office, em cooperação com a empresa de consultoria de gerenciamento Booz, Allen e Hamilton. Ela foi utilizada com êxito no desenvolvimento do complexo programa do míssil Polaris.

Já a técnica CPM (Critical Path Method) foi desenvolvida em 1957 por J. E. Kelly, da Remington Rand, e M. R.Walker, da Du Pont. Difere-se da técnica PERT principalmente quanto aos detalhes de como o tempo e o custo são tratados.

Mas, antes de mais nada, seguem alguns conceitos importantes, baseando-se no método americano:

a) Atividade: Na técnica PERT é considerada como um bloco ou etapa de um projeto que pode ser identificada e mensurada de acordo com o padrão que se deseje adotar, considerando as unidades de recursos empregados.

b) Evento (nó): É o início ou fim de uma ou mais atividades. Não consome recursos. Não tem representação gráfica no sistema de blocos, apenas é subentendido. Também conhecido por nó, por geralmente unir duas ou mais atividades.

c) Sequenciação: Constitui-se, basicamente, de uma tabela com quatro colunas: as atividades, as suas descrições, as atividades que antecedem àquelas da primeira

UP 1 = 10 un. PC 1 = 7 un.

Nó central

UP 2 = 10 un. PC 2 = 18 un.

20 un.

10 un. 13 un.

20 un.



coluna, as atividades que sucedem àquelas da primeira coluna. Deve representar a relação das atividades de um projeto bem como a relação de interdependência entre as mesmas. Alguns autores expõem a tabela de sequenciação com quatro outras colunas: a identificação codificada da atividade, a sua descrição, a dependência dela em relação a outras atividades e o tempo de duração de cada uma. Por exemplo, tomando a tabela de sequenciação a seguir pode-se elaborar o gráfico PERT como exposto.

Atividades Dependência Duração

Código Descrição

A Fazer isso - 10

B Fazer aquilo - 6

C Fazer isso A 7

D Fazer aquilo B 5

E Fazer isso B 9

F Fazer aquilo C/D 5

G Fazer isso E 4

d) Duração de cada atividade: geralmente o recurso principal atribuído à uma atividade é o tempo, e por ser difícil de se prevê-lo, deve-se estimá-lo. Para tanto, faz-se uso da próxima expressão onde constam os tempos mais provável (m), o mais otimista (a) e o mais pessimista (b). A estimativa otimista deve considerar que todos os fatores sejam favoráveis; a pessimista deve orientar-se pelo oposto, considerando tudo que é desfavorável, excetuando-se variáveis não previsíveis, tais como incêndios e catástrofes; a mais provável deve ser amparada na experiência, em fatos reais etc..

e) Atividade Fantasma: quando duas atividades têm os mesmos eventos como delimitadores é difícil identificá-las e representá-las no gráfico PERT. Por isso, utiliza-se a representação de uma atividade inerte, que não consome tempo ou qualquer outro recurso, mas servindo apenas para indicar a hierarquia de

A

C

F

G

E

B

D



precedência. Essas atividades, por não existirem de fato, são denominadas de “fantasmas”.

f) Cálculo dos Tempos das Atividades: o cálculo dos tempos só é possível após o calculo de duração das atividades uma vez que esses tempos correspondem justamente ao início ou fim das atividades. Eles definem os limites no tempo que as atividades que partem deste evento dispõem para serem iniciadas.

f.1) Tempo mais cedo (TMC): é o momento no qual é possível ter concluídas todas as atividades que condicionam um evento. TMC = MAX [TMC + Duração] Atividades dos eventos antecessores diretos Obs.: para o evento inicial TMC = 0 f.2) Tempo mais tarde (TMT): é o último momento possível para as atividades chegarem a um determinado evento sem atrasar o início das atividades que lhes sucedem. TMT = MIN [TMC - Duração] Atividades dos eventos posteriores diretos Obs.: para o evento final TMT = TMC

g) Cálculo do Tempo de Folga (TF): TF = TMTfim – TMCinício – Duração da

Atividade As folgas podem ser:

positivas: excesso de recursos ou o prazo é muito grande;

nulas: recursos e prazos para o projeto são adequados;

negativas: recursos são escassos ou o prazo estipulado para a duração da atividade é pequeno.

h) Caminho Crítico: é constituído pelas atividades (interligadas) de menor folga ou de

folga nula, entre o evento inicial e o evento final, o qual, inclusive, pode passar pelas atividades fantasmas. É formado pelas atividades mais relevantes do projeto para fins de controle, pois elas não podem sofrer qualquer tipo de atraso, e se isto acontecer irá refletir diretamente no prazo fixado para o término do projeto.

B

1 2 1

3

2 OU

1

3

2

B

A A

B A B*

A*



Exemplo 1: Tempo Crítico = 22 u.t

.

Exemplo 2: Tempo Crítico = 13 u.t.

Exemplo 3: Tempo Crítico = 22 u.t.

1

2 4

6

3 5

A

C

F

G

9

6

5

10

7

5

4

D

E

B

0/0

10/10

17/17

22/22

15/18 6/6

Cedo/tarde

11/

19/

/12

1

2

5

3 4

A E

F

2

3

7

3 5

3

D

C

B

0/0

3/3

13/13

10/10 3/8

Cedo/tarde

8/

5/

/8

Caminho crítico

Caminho crítico

1

2

4

3 5 5

4

4 3

8 2

0/0

3/3

7/7

Cedo/tarde

15/

3

3

7 6 8 2

/3

12/15

15/15

18/18

20/20

22/22

A

B

C

D

E

F

G

H I



Tempos de Folga (TF):

Exemplo 1 Exemplo 2 Exemplo 3

Ativ. Cálc. Folga Ativ. Cálc. Folga Ativ. Cálc. Folga

A 10-0-10 0 A 3-0-3 0 A 3-0-3 0

B 6-0-6 0 B 8-0-3 5 B 7-0-4 3

C 17-10-7 0 C 10-3-2 5 C 7-3-4 0

D 17-6-5 6 D 10-3-7 0 D 15-7-8 0

E 18-6-9 3 E 13-3-5 5 E 15-7-5 3

F 22-17-5 0 F 13-10-3 0 F 18-15-3 0

G 22-15-4 3 G 20-18-2 0

I 22-20-2 0

2.6 Problemas de Fluxo Máximo – Ford-Fulkerson

Neste tópico deve-se examinar um grafo orientado como uma Rede de Fluxo

usando-a para analisar o fluxo de materiais a partir de uma origem, onde o material é produzido ou retirado, até um destino, onde o material é consumido ou depositado. A origem produz o material a uma taxa fixa e o depósito consome o material na mesma taxa. O "fluxo" do material em qualquer ponto no sistema é intuitivamente a taxa na qual o material se move.

Cada aresta orientada pode ser imaginada como um canal, com uma capacidade estabelecida, com uma taxa máxima na qual o material pode fluir pelo canal. Os vértices são junções de canais, onde o material flui sem acumulação. Isto é, com exceção da origem e do destino, a taxa de entrada e de saída de material no vértice deve ser a mesma. Chamamos essa propriedade de "conservação do fluxo".

Deseja-se então calcular a maior taxa na qual o material pode ser enviado da origem até o destino, sem violar as capacidades máximas das arestas e mantendo a propriedade de conservação de fluxo.

Uma Rede de Fluxo G(V,A) é um grafo orientado em que cada aresta (u,v) A tem uma capacidade C(u,v) >= 0 (não negativa). Se uma dada aresta não está em A, então se supõe que a sua capacidade é zero (tais arestas não são desenhadas nos grafos). Numa rede de fluxo tem-se dois vértices especiais, uma origem "O" e um destino "D", e para todo vértice do grafo existe um caminho a partir de O passando por V que chega em D. O método de Ford-Fulkerson objetiva encontrar um fluxo máximo para uma rede de fluxos. É chamado de método por englobar diversas implementações com diferentes tempos de execução. O método é iterativo, começando com f(u,v) = 0. Este método é composto pelos seguintes passos:

1º passo: iniciar o fluxo f total com 0 e verificar a existência de caminhos de fluxo > 0.

2º passo: Escolher um caminho da origem até o destino com fluxo >0; identificar o fluxo

mínimo entre os fluxos presentes nos arcos (u,v) pertencentes ao caminho escolhido e

para todas as arestas pertencentes ao caminho escolhido fazer:

o f(u,v) = f(u,v) – f (decrementa o fluxo disponível) o f(v,u) = f(v,u) + f (incrementa o fluxo utilizado)

3º passo: Faz-se ftotal = ftotal + f. O processo deve ser repetido até que todos os

caminhos sejam analisados e enquanto existirem fluxos disponíveis.



Exemplo: Baseando-se no grafo a seguir, identifique o fluxo máximo que pode fluir entre a origem (O) e o destino (D), utilizando o método de Ford-Fulkerson.

1º caminho escolhido: O>16>A>12>C>20>D, sendo f=12 e ftotal=12 2º caminho escolhido: O>4>A>10>B>14>E>4>D, sendo f=4 e ftotal=16

3º caminho escolhido: O>13>B>10>E>7>C>8>D, sendo

O

A C 20 16

D

B E 14

12

4 9

7 4 10

13

O

A C 12/20 16/16

D

B E 4/14

12/12

4/4 9

7 4+4 4/10

13

O

A C 12/20 12/16

D

B E 14

12/12

4 9

7 4 10

13

Fluxo Limitador

Capacidade

O

A C 19/20 16/16

D

B E 11/14

12/12

4/4 9

7/7 8 4/10

7/13

23 23



UNIDADE 3 - Problema do Caixeiro Viajante

3.1. Características

Um problema de roteamento pode ser considerado como um conjunto organizado de meios que objetiva o atendimento de demandas localizadas nos arcos ou nos vértices de alguma rede de transporte. A ideia principal desse tipo de problema é a designação de pontos de paradas de veículos, bem como a determinação da sequência com que esses pontos de parada são visitados, estabelecendo assim, as rotas para os veículos.

Duas abordagens básicas para o roteamento de veículos têm sido adotadas, supondo que os veículos serão roteirizados em uma rede composta por nós e arcos: problemas de coberturas de nós e problemas de cobertura de arcos. 3.2. Problemas de Cobertura de nós

Estes tipos de problemas devem indicar uma rota de comprimento mínimo que visite cada nó uma única vez. Este problema implica no cálculo de um ciclo de Hamilton, em um grafo, de encargo total mínimo. O ciclo Hamiltoniano é caracterizado pela possibilidade da existência de uma rota, que passasse pelos nós, iniciando e terminando no mesmo nó, sem nunca repetir uma passagem. Este ciclo é denominado de Hamilton em homenagem Willian Rowan Hamilton, que em 1957 propôs um jogo denominado Around the World (figura 1.1). O problema do Caixeiro Viajante é um problema de otimização associado ao da determinação dos caminhos hamiltonianos em um grafo qualquer.

Figura 1.1 - Esquema do tabuleiro do jogo de Hamilton

Para solução desses problemas, principalmente em redes reais de grande porte,

necessita-se de apoio computacional. É importante observar que o tempo de solução computacional cresce exponencialmente com o aumento do número de nós. Somente o Método de Enumeração (identificação de todos os ciclos possíveis), garante o cálculo da solução ótima do problema, mas tal método é impraticável. Para ilustrar esta dificuldade observa-se que para um computador tratar em torno de 10.000 ciclos/segundo, ele necessitará de aproximadamente 18 segundos para finalizar a avaliação de uma solução ótima em um grafo com 10 vértices, 50 dias para um grafo com 15 vértices, 2 anos para um grafo com 16 vértices e 193.000 anos para um grafo com 20 vértices.

Serão apresentados três modelos heurísticos (utiliza experiências passadas): do vértice adjacente mais próximo, da inserção com menor encargo e da inserção com maior afastamento.



3.2.1. Método do Vértice Adjacente mais Próximo

Este método baseia-se nos seguintes passos para identificar a solução aproximada:

1- Seleciona-se arbitrariamente um nó Ni para o início do ciclo.

2- Dentre os nós não selecionados, seleciona-se o nó Nk que está a menor

distância de Ni, ficando a cadeia Ni,Nk. Repetem-se esses passos até que todos

os vértices possam ser utilizados.

Exemplo - Considerando a tabela a seguir que registra as distâncias em quilômetros entre os nós de um grafo orientado, determine uma rota com encargo total mínimo, utilizando o método em estudo, que passe pelos nós, iniciando e terminando no mesmo nó, sem repetir uma passagem.

A B C D E

A 16 12 18 16

B 10 18 20 20

C 18 20 18 16

D 14 18 10 8

E 8 12 12 12

Seleciona-se o nó inicial: A

O nó mais próximo de A que ainda não foi selecionado? C (12Km)

O nó mais próximo de C que ainda não foi selecionado? E (16Km)

O nó mais próximo de E que ainda não foi selecionado? B (12Km)

O nó mais próximo de B que ainda não foi selecionado? D (20Km)

O nó mais próximo de D que ainda não foi selecionado? A (14Km)

O circuito inicial então teria a seguinte configuração: A > C > E > B > D > A com a distância total de 74Km. 3.2.2. Método da Inserção com Menor Encargo.


1-Seleciona-se um subciclo "i,j,i" associado a Min {Cij + Cji} Obs.: se houver empate deve-se escolher arbitrariamente um subciclo. 2-No subciclo corrente, calcular para cada ligação do tipo (u,v), a inserção do nó "k"

(não selecionado) a que corresponda ao aumento mínimo da distância dado por Min {Cuk + Ckv - Cuv}. Repetir este procedimento até serem selecionados todos os nós do grafo.

Exemplo - Considerando a tabela a seguir que registra as distâncias em

quilômetros entre os nós de um grafo orientado, determine uma rota com encargo total mínimo, utilizando o método em estudo, que passe pelos nós, iniciando e terminando no mesmo nó, sem repetir uma passagem.



A B C D E

A 16 12 18 16

B 10 18 20 20

C 18 20 18 16

D 14 18 10 8

E 8 12 12 12

Inicialmente deve-se escolher o subciclo inicial. A tabela a seguir mostra as

distâncias equivalentes de cada subciclo.

A B C D E

A ABA=26Km ACA=30Km ADA=32Km AEA=24Km

B BCB=38Km BDB=38Km BEB=32Km

C CDC=28Km CEC=28Km

D DED=20Km

E

Então, o primeiro subcircuito será DED com distância total de 20Km. Agora, devem-se então verificar todas as inserções possíveis no subciclo anterior,

de acordo com o passo 2. Opções entre D e E: D > A = 14Km e A > E = 16Km >> 14 + 16 = 30Km - 8Km = 22Km D > B = 18Km e B > E = 20Km >> 18 + 20 = 38Km - 8Km = 30Km D > C = 10Km e C > E = 16Km >> 10 + 16 = 26Km - 8Km = 18Km Opções entre E e D

E > A = 8Km e A > D = 18Km >> 8 + 18 = 26Km - 12Km = 14Km

E > B = 12Km e B > D = 20Km >> 12 + 20 = 32Km - 12Km = 20Km E > C = 12Km e C > D = 18Km >> 12 + 18 = 30Km - 12Km = 18Km A menor quilometragem na inserção foi observada com o nó A entre E e D. O novo

circuito agora tem esta configuração. As próximas inserções possíveis são: Opções entre D e E: B > 18+20-8 = 30Km C > 10+16-8 = 18Km

D E D 8Km

12Km

D E D 8Km

18Km A

8Km



Opções entre E e A: B > 12+10-8 = 14Km C > 12+18-8 = 22Km Opções entre A e D: B > 16+20-18 = 18Km C > 12+18-18 = 12Km A menor quilometragem foi observada com a inserção do nó C entre A e D, ficando

o novo subciclo da seguinte forma: D > 8Km > E > 8Km > A > 12Km > C > 18Km > D Avaliando-se a última inserção possível (nó B), deve-se identificar em que trecho

deve ser efetuado. Opções de inserção: DBEACD = 76Km DEBACD = 60Km DEABCD = 68Km DEACBD = 68Km

Então o circuito teria a seguinte configuração por este método: D > E > B > A > C > D com a distância total de 60Km.

3.2.3. Método da Inserção com maior afastamento.


1-Seleciona-se o subciclo "i,j,i" associado a Max {Cij + Cji} Obs.: se houver empate deve-se escolher arbitrariamente um subciclo. 2-Seleciona-se um nó "k" dos não inseridos de acordo com os subpassos a seguir: 2.1-Avalia-se a menor distância entre os nós já pertencentes ao subciclo

atual, ao nó "k" a inserir. 2.2-Escolhe-se para inserção o nó "k" onde seja maior à distância registrada

(máximo dos mínimos) 3-No subciclo atual, calcular para cada ligação do tipo (u,v) a inserção do nó "k",

selecionado anteriormente, a que corresponda o aumento mínimo de distância dado por Min {Cuk+Ckv-Cuv}.

4-Selecionar novo nó até que todos estejam na solução inicial. Exemplo - Considerando a tabela a seguir que registra as distâncias em

quilômetros entre os nós de um grafo orientado, determine uma rota com encargo total mínimo, utilizando o método em estudo, que passe pelos nós, iniciando e terminando no mesmo nó, sem repetir uma passagem.



A B C D E

A 16 12 18 16

B 10 18 20 20

C 18 20 18 16

D 14 18 10 8

E 8 12 12 12

Inicialmente deve-se escolher o subciclo inicial. A tabela a seguir mostra as

distâncias equivalentes de cada subciclo.

A B C D E

A ABA=26Km ACA=30Km ADA=32Km AEA=24Km

B BCB=38Km BDB=38Km BEB=32Km

C CDC=28Km CEC=28Km

D DED=20Km

E

Então, o primeiro subciclo será BCB com distância total de 38Km. Agora, devem-se então verificar todas as inserções possíveis no subciclo anterior,

de acordo com o passo 2.

Distância entre os nós

A D E

B 10 20 20

C 18 18 16

Min. entre linhas 10 18 16

Máx. entre colunas 18

Opções de inserção para o nó D: 1-B > D > C = 20+10-18 (BC) = 12Km 2-C > D > B = 18+18-20 (CB) = 16Km

O menor encargo com a inserção do nó "D" é 12Km, ficando então o novo subciclo

é BDCB.

B C B

18Km 20Km

B C B 18Km 20Km

D D

18Km

18Km

20Km

10Km



Deve-se escolher um novo nó para inserção:

A E

B 10 20

C 18 16

D 14 8

Min. entre linhas 10 8

Máx. entre colunas 10

Opções de inserção: 1-B > A > D = 10+18-20 (BD) = 8Km 2-D > A > C = 14+12-10 (DC) = 16Km 3-C > A > B = 18+16-20 (CB) = 14Km

O menor encargo com a inserção do nó "A" é 8Km, ficando então o novo subciclo é

BADCB. O único nó que falta ser inserido no subciclo é o "E". Sendo assim, deve-se avaliar

as opções de encargos (distâncias). Opções de inserção: 1-BEADCB = 20+8+18+10+20 = 76Km 2-BAEDCB = 10+16+12+10+20 = 68Km 3-BADECB = 10+18+8+12+20 = 68Km 4-BADCEB = 10+18+10+16+12 = 66Km Então o circuito inicial teria a seguinte configuração por este método.

B > A > D > C > E > B com a distância total de 66Km.

Distância entre os nós

B C B 10Km

20Km

18Km

10Km

20Km

D

A A A

12Km

14Km

16Km

18Km



UNIDADE 4 – Análise Multicritério à Decisão 4.1. Conceitos sobre Processo Decisório Multicritério

Algumas atividades do cotidiano gerencial demandam decisões que, em muitos casos, não são decisões simples, pois envolvem vários critérios com características diferentes, interferindo no objetivo da decisão.

O processo de decidir entre várias alternativas, segundo certo conjunto de critérios, está associado à área da Análise Multicriterial (MCA – Multicriteria Analysis), tendo como um dos mais difundidos métodos o AHP (Analytical Hierarchy Process). 4.2. Análise Hierárquica – AHP

O método AHP foi desenvolvido por Thomas Saaty, professor da Pennsylvania’s Wharton School, no final da década de 1970. O método permite tratar variáveis quantitativas e qualitativas, além de possibilitar que as avaliações sejam feitas com base no conhecimento e em percepções (subjetividade) do tomador de decisão.

As etapas para a aplicação do AHP são as seguintes: a) Definir o Problema de Decisão: deve-se identificar o objetivo, os

critérios/subcritérios baseados nos valores, crenças e convicções do decisor, além das alternativas para a solução do problema;

b) Estruturações da hierarquia; c) Realização dos julgamentos comparativos para cada nível; d) Classificação das alternativas; e) Consistência.

Adiante seguem os detalhes do item b a d. b) Modelo com a Estruturação da Hierarquia do Problema: nesta etapa deve-se conectar o objetivo, os critérios e seus subcritérios, além das alternativas para que o objetivo seja alcançado e as alternativas. A próxima figura exemplifica uma hierarquia.

Objetivo

Criterio 1 Criterio 2

Subcritério 1.1 Subcritério 1.2 Subcritério 1.3 Subcritério 2.1 Subcritério 2.2

Alternativa 1

Alternativa 2

Alternativa 3

Recomenda-se utilizar subcritérios quando houver dificuldade do decisor em julgar o desempenho das alternativas à luz de um determinado critério. Do contrário, o nível de subcritérios é desnecessário.



c) Julgamentos Comparativos: para cada nível da hierarquia (critério, subcritério e alternativas) é realizada uma comparação aos pares. Para efetivar as comparações é necessário construir as Matrizes de Comparação Paritária (MCP), tal como os exemplos a seguir.

à luz do Objetivo C1 C2

C1 a11 a12

C2 a21 a22

à luz do Critério 1 SC1.1 SC1.2 SC1.3

SC1.1 a11 a12 a13

SC1.2 a21 a22 a23

SC1.3 a31 a32 a33

à luz do Subcritério 1 A1 A2 A3

A1 a11 a12 a13

A2 a21 a22 a23

A3 a31 a32 a33

Vale destacar o seguinte:

A análise dos Critérios deve ser efetuada à luz do Objetivo;

A análise dos Subcritérios deve ser efetuada à luz dos Critérios;

A análise das Alternativas deve ser efetuada à luz dos Subcritérios.

Para preenchimento das células das matrizes utiliza-se a Escala Fundamental de Saaty, conforme Quadro adiante, questionando-se a importância da opção da linha (i) em relação à coluna (j).

Intensidade Importância Forma de Avaliação

1 Igual importância As duas atividades contribuem igualmente para o objetivo.

3 Importância pequena de uma sobre outra

A experiência e o juízo favorecem uma atividade em relação à outra.

5 Importância grande ou essencial

A experiência ou juízo favorece fortemente uma atividade em relação à outra.

7 Importância muito grande ou demonstrada

Uma atividade é muito fortemente favorecida em relação à outra. Pode ser demonstrada na prática.

9 Importância absoluta A evidência favorece uma atividade em relação à outra, com o mais alto grau de segurança.

2, 4, 6, 8 Valores Intermediários Quando se procura uma condição de compromisso entre duas definições.

Os valores das células devem ser preenchidos considerando-se que aij = 1/aji e que

aii = 1, formando a matriz quadrada A, como a seguir.



c.1.) Quantidade de Julgamentos: a quantidade de julgamentos necessários para a construção de uma MCP é: n(n-1)/2, onde n é a quantidade de elementos da MCP.

c.2) Normalização da MCP: após o preenchimento das MCP é necessário

normalizá-las como segue:

Somar todos os elementos das colunas;

Dividir todos os elementos de cada coluna pelo respectivo somatório anterior.

A MCP adiante exemplifica a normalização.

à luz do SC1.1 A1 A2 A3

A1 a'11 a'12 a'13

A2 a'21 a'22 a'23

A3 a'31 a'32 a'33

Sendo a'ij = aij /

, para 1 ≤ i ≤ n e 1 ≤ j ≤ n

Por exemplo a'11 = a11 / (a11+ a21 + a31) c.3) Prioridade Média Local – PML: após o preenchimento das MCP e das

normalizações deverá ser obtido o vetor de pesos associado a essa matriz. Cada elemento do vetor está relacionado com a importância relativa de cada critério/subcritério/alternativa.

Calcula-se então a média aritmética (Prioridade Média Local – PML) de cada linha i da MCP, formando o vetor com o peso de cada nó do modelo (critério/subcritério/alternativa). O PML é calculado por:

PML =

, para 1 ≤ j ≤ n e 1 ≤ k ≤ n

Por exemplo, PMLA1 para SC1 = (a’11+ a’12 + a’13)/3 Dessa forma obtêm-se as relações entre as alternativas e os critérios, formando a

seguinte matriz, com o cálculo do exemplo anterior:

SC1.1 SC1.2 SC1.3 SC2.1 SC2.2

A1 PMLA1

A2

A3

c.4) Prioridade Média Global – PMG: deseja-se calcular um vetor com a PMG que

reflita a prioridade de cada Alternativa em relação ao Objetivo do modelo. Isso é feito usando-se os vetores locais de cada nó como peso em uma média ponderada no nó superior. O PMG é obtido por:



PMGd =

, onde nt é a quantidade de nós do modelo para a

Alternativa d; nl é a quantidade de níveis da hierarquia; t é o nó na hierarquia correspondente à Alternativa d; e a sequência t, nl-1, nl-2, ..., 1 é o caminho na hierarquia da Alternativa d até o Objetivo.

d) Classificação das Alternativas

Os valores obtidos no PMG, calculados anteriormente, refletem a hierarquia das

alternativas à luz do objetivo. f) Consistência

Faz-se necessário analisar a consistência do julgamento dos decisores, identificando o quanto o sistema de classificação utilizado consiste na classificação das alternativas viáveis.

Tal consistência é observada, por exemplo, que um decisor julgou 3 alternativas (A, B e C) em relação a 1 critério (X) da seguinte forma: aAB = 3; aBC = 3; aAC = 9. Observa-se que aAC = aAB . aBC. Isso denota Consistência no julgamento.

Para se medir a Intensidade da Consistência da MCP analisa-se o quanto o seu maior autovalor se afasta da sua ordem da matriz. Para tanto usa-se o Índice de

Consistência (IC) dado por: IC =

, onde N é a ordem da MCP e é o maior

autovalor da mesma MCP. Isso é feito, por exemplo, da seguinte forma: Primeiro, multiplica-se a MCP das Alternativas à luz de certo critério Subcritério, por

exemplo SC1.1, pelo vetor PML S.C1.1, que gerará a matriz SC’1.1. Em seguida somam-se as linhas de SC’1.1 para gerar um vetor novo.

Na sequência, divide-se cada elemento da matriz SC’1.1 pelo elemento correspondente do vetor PML S.C1.1, encontrando-se um novo vetor. O é determinado pela soma dos elementos do novo vetor, dividido pela ordem da matriz.

Calcula-se, então a Razão de Consistência (RC) que permite avaliar a inconsistência em função da ordem da MCP, dada por: RC = IC/IR, onde IR é o Índice Randômico, dado pela tabela apresentada por Saaty apresentada a seguir.

Ordem da Matriz (N) 1 2 3 4 5 6 7 8 9 10 11

IR 0 0 0,58 0,9 1,12 1,24 1,32 1,41 1,45 1,49 1,51

Saaty sugere que o aceitável é que RC < 0,10; do contrário será necessário revisar

as MCP. Para exemplificar o uso da AHP, o modelo a seguir expressa uma condição comum

na dúvida sobre a compra de certo bem, que nesse caso será utilizado certo automóvel. Observação importante: o método AHP pode ser usado para decisão em grupo,

ou seja, como o uso de mais de um decisor. Nesse caso resultarão MCP dos mesmos critérios/subcritérios/alternativas para cada decisor. Deve-se então gerar uma MCP que represente a sintetização dos julgamentos dos decisores. Cada elemento da MCP resultante é obtido pela média geométrica dos resultados, dados por aij-sintetizado:



A tabela adiante demonstra um exemplo da nova MCP das Alternativas, à luz de certo Critério.

à luz de certo Critério

A1 A2 A3

A1 a11-sintetizado a12-sintetizado a13-sintetizado



Como cada decisor pode ter um peso associado para expressar sua afinidade com

a variável analisada, agregam-se tais pesos e os julgamentos dos decisores também com o uso da média geométrica do peso, conforme expressão a seguir.

, sendo:

, onde é o peso associado ao critério j pelo decisor k.

, onde é o valor da alternativa associado ao critério j,

feito pelo decisor k. S é a quantidade de decisores no problema.

Para demonstrar o uso do AHP, nas próximas páginas está destacado um exemplo

sobre a compra de um automóvel, onde os dados coletados foram de apenas um decisor. Conforme o item b a estruturação da hierarquia, que representa o modelo, está

expressa na próxima Figura.

Como se pode observar, os critérios utilizados são Desenho, Potência, Economia e

Preço. As alternativas são Carros 1 a 3. Conforme o item c os julgamentos comparativos estão expostos nas MCP adiante.

À luz do Crit. Desenho

Carro 1 Carro 2 Carro 3

Carro 1 1 1/3 1/5

Carro 2 3 1 1/3

Carro 3 5 3 1

Determinar a melhor opção de

compra de certo automóvel

Desenho Potência Economia Preço




À luz do Crit. Potência


Carro 1 1 1/7 1/9

Carro 2 7 1 1/5

Carro 3 9 5 1

À luz do Crit. Economia


Carro 1 1 1 1/3

Carro 2 1 1 1/3

Carro 3 3 3 1

À luz do Crit. Preço


Carro 1 1 1/3 1/7

Carro 2 3 1 1/5

Carro 3 7 5 1

À luz do Objetivo


Desenho 1 1/3 1/5 1/9

Potência 3 1 1/3 1/5

Economia 5 3 1 1/7

Preço 9 5 7 1

Segundo o item c.2 é necessário normalizar as MCP. Essa operação está

apresentada a seguir.



Carro 1 1/9 (1/3)/4,33 (1/5)/1,53

Carro 2 3/9 1/4,33 (1/3)/1,53

Carro 3 5/9 3/4,33 1/1,53

Soma 9 4,33 1,53



Carro 1 1/17 (1/7)/6,14 (1/9)/1,31

Carro 2 7/17 1/6,14 (1/5)/1,31

Carro 3 9/17 5/6,14 1/1,31

Soma 17 6,14 1,31



Carro 1 1/5 1/5 (1/3)/1,66

Carro 2 1/5 1/5 (1/3)/1,66

Carro 3 3/5 3/5 1/1,66

Soma 5 5 1,66





Carro 1 1/11 (1/3)/6,33 (1/7)/1,34

Carro 2 3/11 1/6,33 (1/5)/1,34

Carro 3 7/11 5/6,33 1/1,34

Soma 11 6,33 1,34

À luz do Objetivo


Desenho 1/18 (1/3)/9,33 (1/5)/8,53 (1/9)/2,29

Potência 3/18 1/9,33 (1/3)/8,53 (1/5)/2,29

Economia 5/18 3/9,33 1/8,53 (1/7)/2,29

Preço 9/18 5/9,33 7/8,53 1/2,29

Soma 18 9,33 8,53 2,29

Os resultados das MCP normalizadas estão expostos na sequência.



Carro 1 0,11 0,08 0,13

Carro 2 0,33 0,23 0,22

Carro 3 0,56 0,69 0,65



Carro 1 0,06 0,02 0,08

Carro 2 0,41 0,16 0,15

Carro 3 0,53 0,81 0,76



Carro 1 0,2 0,2 0,20

Carro 2 0,2 0,2 0,20

Carro 3 0,6 0,6 0,60



Carro 1 0,09 0,05 0,10

Carro 2 0,27 0,16 0,15

Carro 3 0,64 0,79 0,75

À luz do Objetivo


Desenho 0,06 0,04 0,02 0,05

Potência 0,17 0,11 0,04 0,09

Economia 0,28 0,32 0,12 0,06

Preço 0,50 0,54 0,82 0,44



O item c.3 preconiza os cálculos para PML nas MCP normalizadas, para cada nó da hierarquia do modelo. A seguir estão apresentados esses cálculos.


Carro 1 Carro 2 Carro 3 Média da linha

(PML)

Carro 1 0,11 0,08 0,13 0,11

Carro 2 0,33 0,23 0,22 0,26

Carro 3 0,56 0,69 0,65 0,63



(PML)

Carro 1 0,06 0,02 0,08 0,05

Carro 2 0,41 0,16 0,15 0,24

Carro 3 0,53 0,81 0,76 0,70



(PML)

Carro 1 0,20 0,20 0,20 0,20

Carro 2 0,20 0,20 0,20 0,20

Carro 3 0,60 0,60 0,60 0,60



(PML)

Carro 1 0,09 0,05 0,10 0,08

Carro 2 0,27 0,16 0,15 0,19

Carro 3 0,64 0,79 0,75 0,73

À luz do Objetivo

Desenho Potência Economia Preço Média da linha

(PML)

Desenho 0,06 0,04 0,02 0,05 0,04

Potência 0,17 0,11 0,04 0,09 0,10

Economia 0,28 0,32 0,12 0,06 0,20

Preço 0,50 0,54 0,82 0,44 0,58

O resumo do cálculo do PML está apresentado adiante.

Os critérios à luz do Objetivo (0,04; 0,10; 0,20; 0,58)

As alternativas à luz dos critérios: Desenho – (0,11; 0,26; 0,63) Potência – (0,05; 0,24; 0,70) Economia – (0,20; 0,20; 0,60) Preço – (0,08; 0,19; 0,73)

Determinar a melhor opção de compra de certo automóvel





A PMG reflete a prioridade de cada alternativa em relação ao objetivo, conforme apresentado no item c.4 e deve seguir o seguinte vetor:

PMG = (PMGCarro1; PMGCarro2; PMGCarro3)

Sendo assim, apresentam-se os cálculos dos PMG de cada alternativa. PMGCarro1 = (0,04x0,11 + 0,10x0,05 + 0,20x0,20 + 0,58x0,08) = (0,0044+0,0050+0,0400+0,0464) = 0,0958

PMGCarro2 = (0,04x0,26 + 0,10x0,24 + 0,20x0,20 + 0,58x0,19) = (0,0104+0,0240+0,0400+0,1102) = 0,1846

PMGCarro3 = (0,04x0,63 + 0,10x0,70 + 0,20x0,60 + 0,58x0,73) = (0,0252+0,0700+0,1200+0,4234) = 0,6386

PMG = (0,0958; 0,1846; 0,6386) O vetor PMG representa a Classificação das Alternativas à luz do Objetivo, tal

como exposto no item d. Assim, o melhor automóvel para compra é o Carro 3 (0,6386); o segundo melhor é o Carro 2 (0,1846); e por último, o Carro 1 (0,0958).

Os PML para cada Critério avaliado pelo decisor são: Desenho – (0,110; 0,260; 0,630) Potência – (0,050; 0,24; 0,700) Economia – (0,200; 0,200; 0,600) Preço – (0,080; 0,190; 0,730)

Tomando-se as MCP dos decisores para cada critério e multiplicando-as pelos

vetores dos referidos, chega-se a:



Carro 1 1 x 0,11 1/3 x 0,26 1/5 x 0,63

Carro 2 3 x 0,11 1 x 0,26 1/3 x 0,63

Carro 3 5 x 0,11 3 x 0,26 1 x 0,63



Carro 1 1 x 0,05 1/7 x 0,24 1/9 x 0,70

Carro 2 7 x 0,05 1 x 0,24 1/5 x 0,70

Carro 3 9 x 0,05 5 x 0,24 1 x 0,70



Carro 1 1 x 0,20 1 x 0,20 1/3 x 0,60

Carro 2 1 x 0,20 1 x 0,20 1/3 x 0,60

Carro 3 3 x 0,20 3 x 0,20 1 x 0,60





Carro 1 1 x 0,08 1/3 x 0,19 1/7 x 0,73

Carro 2 3 x 0,08 1 x 0,19 1/5 x 0,73

Carro 3 7 x 0,08 5 x 0,19 1 x 0,73

Foram incluídas as somas das linhas, com os resultados dos cálculos anteriores.

Vale observar que os valores expostos nas diagonais de cada MCP referem-se aos PML para cada Critério avaliado pelo decisor.


Carro 1 Carro 2 Carro 3 Soma das

linhas

Carro 1 0,110 0,087 0,126 0,323

Carro 2 0,330 0,260 0,210 0,800

Carro 3 0,550 0,780 0,630 1,960



linhas

Carro 1 0,050 0,034 0,078 0,162

Carro 2 0,350 0,240 0,140 0,730

Carro 3 0,450 1,200 0,700 2,350



linhas

Carro 1 0,200 0,200 0,200 0,600

Carro 2 0,200 0,200 0,200 0,600

Carro 3 0,600 0,600 0,600 1,800



linhas

Carro 1 0,080 0,063 0,104 0,247

Carro 2 0,240 0,190 0,146 0,576

Carro 3 0,560 0,950 0,730 2,240

A última coluna (Soma das Linhas) das MCP forma um vetor auxiliar que deve ser

dividido pelos valores de PML. O resultado desse novo vetor, quando tirados a média de

seus elementos redundam no . Assim, adiante seguem os cálculos.


Soma das linhas

Resultado

Carro 1 0,323/0,110 2,936

Carro 2 0,800/0,260 3,077

Carro 3 1,960/0,630 3,111

Média ( ) 3,041




Soma das linhas

Resultado

Carro 1 0,162/0,050 3,240

Carro 2 0,730/0,240 3,042

Carro 3 2,350/0,700 3,357

Média ( ) 3,213


Soma das linhas

Resultado

Carro 1 0,600/0,200 3,000

Carro 2 0,600/0,200 3,000

Carro 3 1,800/0,600 3,000

Média ( ) 3,000


Soma das linhas

Resultado

Carro 1 0,247/0,080 3,088

Carro 2 0,576/0,190 3,032

Carro 3 2,240/0,730 3,068

Média ( ) 3,063

Dessa forma o Índice de Consistência (IC), dado por IC =

, onde N é a

ordem da MCP e é o maior autovalor da mesma MCP, pode ser calculado como a seguir.

ICDesenho =

= 0,021

ICPotência =

= 0,107

ICEconomia =

= 0

ICPreço =

= 0,031

O IR obtido na Tabela do Índice Randômico, para N = 3, é 0,58. Então o RC = IC/IR

é dado por: RCDesenho = 0,021/0,58 = 0,036 RCPotência = 0,107/0,58 = 0,184 RCEconomia = 0/0,58 = 0 RCPreço = 0,031/0,58 = 0,053 Como registra Saaty que a inconsistência é inerente ao ser humano, deve-se existir

uma tolerância para a sua aceitação. Sendo assim, o proposto pelo autor é que haja aceitação de julgamentos que gerem uma inconsistência com RC < 0,1.

Observando-se os resultados de RC nota-se que a inconsistência do Critério “Potência” está acima do tolerável, sendo necessário revisar as impressões dos Decisores quanto aos valores dados.

Documents

De acordo com o Plano de Ensino do Currículo 215 ... · Princípios da Teoria de Grafos, problemas clássicos de transporte (equilibrado e desequilibrado), problemas de ... 2.5 Problemas