EAD 350 1 sem 2015 1ª e 2ª aula intr modelos redes cobertura minima Pajek e modelos

Prévia do material em texto

Modelos de Redes 
1ª e 2ª aulas 
EAD 350 
Prof. Nicolau Reinhard 
1º sem 2015 
Bibliografia Básica 
Hillier e Lieberman, Introdução à Pesquisa Operacional 8ª. Ed, Bookman, 2010 
Taha, A. H, Pesquisa Operacional, Pearson, 8ª ed, Pearson, 2008 
 
6. Bibliografia Complementar 
Vidal, A.G.V. Apostila de Modelos de Redes 
Pajek Wiki, Network analysis and visualization: R and Riddle, M. http://pajek.imfm.si/doku.php 
Hannemann, Introduction to social network methods: http://faculty.ucr.edu/~hanneman/nettext/ 
Waner, S., Finite Mathematics: everything, 5ª ed.: http://www.zweigmedia.com/tcpage.html#ed6#en#finite 
Estratégias de Ensino: 
Aulas expositivas com apresentação da teoria mesclada com 
exemplos e exercícios. 
Aulas práticas no laboratório de microinformática (UPD), 
com o uso dos softwares PAJEK, Netdraw, Google Docs 
Todo o material da disciplina será disponibilizado no 
Erudito e também no Google Docs. 
Exercícios e demais tarefas deverão ser entregues através do 
Erudito. 
EAD 350 Pesquisa Operacional – Segmento Modelos de Redes 
Prof. Nicolau Reinhard 
Cronograma das aulas 
Salvo aviso em contrário, todas as aulas serão ministradas no 
laboratório de informática no FEA 5 
Prof. Nicolau Reinhard - FEAUSP 
A 
B 
D 
C E 
Um grafo consiste de: 
• Um conjunto V de vértices 
• Um conjunto E de arestas 
• Uma função w: E -> P(V) que associa a cada aresta um subconjunto de dois ou de um elemento de V. 
Para um grafo com pesos há a função adicional E -> R, que associa um valor a cada aresta 
Aresta Extremos Peso 
1 A,B 10 
2 A,C 15 
3 B,D 20 
4 C,D 25 
5 C,E 10 
6 D,E 15 
25 
15 
20 
10 
10 
15 
Para mais definições veja: http://pt.wikipedia.org/wiki/Teoria_dos_grafos 
Modelos de Redes 
“Um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). 
Dependendo da aplicação, as arestas podem ser direcionadas, sendo então representadas por "setas". 
(Wikipedia) 
Prof. Nicolau Reinhard - FEAUSP 
Grafo orientado 
Prof. Nicolau Reinhard - FEAUSP 
Exemplo de Gráfico da rede de amigos do Facebook 
Produzido pelo software NameGenWeb 
Mostra a necessidade de se usar modelos 
matemáticos para analisar grandes redes 
As cores dos nós representam grupos na rede 
Prof. Nicolau Reinhard - FEAUSP 
Representação gráfica de Redes 
Exercício de uso do software Netdraw 
 
1. Criar sua rede de amigos do Facebook usando o NameGenWeb 
1. Instalar o NameGenWeb no seu Facebook 
2. Criar a rede de amigos usando o NameGenWeb 
3. Marque a opção “Include Ego” 
4. Exporte a Rede no formato UCINET para um diretório (sua área de trabalho) 
2. Visualizar a rede 
1. Abrir o programa Netdraw 
2. Abrir o arquivo de sua Rede gerada no passo anterior 
3. Para tornar o gráfico mais legível: Usar a sequencia de comandos 
“Options” ->“Display Options” ->desmarcar “Node Labels” 
1. Observação: o gráfico fica mais legível se você usar o comando de display: 
3. Analisar a rede 
1. Identificar os subgrupos com maior coesão entre si: 
1. “Analysis” -> “Subgroups” -> “Factions” -> “no. of groups desired” -> (escolha um valor 
– sugiro iniciar com 5) -> “GO” 
experimente vários valores para “no. of groups desired” até chegar num agrupamento 
satisfatório. 
4. Exporte os dados no formato Pajek: File-> Save Data as -> Pajek -> net file (para ser usado mais 
tarde no Pajek) 
Prof. Nicolau Reinhard - FEAUSP 
Qual o conjunto de 
arestas de peso total 
mínimo que mantém o 
grafo conexo? 
Grafo não orientado 
Prof. Nicolau Reinhard - FEAUSP 
Modelo: árvore de cobertura mínima 
(minimum spanning tree) 
Aplicações de “árvore de cobertura mínima” 
 
Arquitetura de redes: 
• de transporte - estradas 
• de comunicação (telefonia, computação) 
• elétricas, hidráulicas, transporte de líquidos 
Finanças – mercado de ações 
Biologia - análise genética 
 
Fonte: http://www.decom.ufop.br/marco/site_media/uploads/bcc204/15_aula_15.pdf 
Fonte: 
Árvore de cobertura mínima 
de correlações entre variação de cotação de ações BMF 
Fonte: 
Correlações entre Retornos das ações 
Correlações entre volatilidade das ações 
Para rever os conceitos básicos de grafos (redes) e os algoritmos de 
 
• árvore de cobertura mínima e 
• Distância mínima 
 
Consulte os capítulos 8 e 9 do site 
 
 
Practical Optimization: A Gentle Introduction 
John W. Chinneck 
Systems and Computer Engineering 
Carleton University 
Ottawa, Ontario K1S 5B6 
Canada 
http://www.sce.carleton.ca/faculty/chinneck/po.html 
Prof. Nicolau Reinhard - FEAUSP 
Comandos do PAJEK para a obtenção do caminho mais curto 
Prof. Nicolau Reinhard - FEAUSP 
Modelos de Redes - Algoritmo do Caminho mínimo (mais curto) 
Rede completa 
Caminho mais curto 
Prof. Nicolau Reinhard - FEAUSP 
Modelos de Redes – Exemplo de Transporte 
Algoritmo do Caminho mínimo 
Prof. Nicolau Reinhard - FEAUSP 
Prof. Nicolau Reinhard - FEAUSP 
Modelos de Redes 
Algoritmo do Caminho Mínimo (mais curto) 
Caminho mais curto 
Prof. Nicolau Reinhard - FEAUSP 
use os dados da rede no.4 (transporte) apresentada na aula para 
responder às seguintes perguntas: 
 
1. qual a rota de custo mínimo entre os nós 1 (SAO) e 7 (FOR)? 
 
2. em quanto deveriam ser reduzidos os custos de transporte de VIT 
para REC ou de REC para FOR para que REC passasse a fazer parte 
de uma rota de custo mínimo entre SAO e FOR? 
Exercício 1 redes 
Para ser entregue antes da próxima aula 
Erudito – pasta: redes exerc 1 
O exercício é individual 
Aviso importante: Você deve justificar suas respostas através de texto explicativo (isto é, 
figuras não são autoexplicativas) 
 
As respostas devem ser entregues em um texto no formato WORD. 
No texto devem ser inseridas as figuras das redes PAJEK que sustentam a sua resposta 
(para isto copie as figuras do PAJEK para o Word (nos formatos .jpeg ou .bmp) 
Prof. Nicolau Reinhard - FEAUSP 
Conceitos básicos de modelagem 
 
Nada no mundo real é um sistema, uma rede, ou um problema de Pesquisa 
operacional. 
Nós é que optamos por interpretar a realidade através destas representações 
 
Um modelo é uma representação da realidade projetado para algum 
propósito definido 
Um modelo é uma representação externa e explícita de parte da realidade 
vista pela pessoa que deseja usar aquele modelo para entender, mudar, 
gerenciar e controlar parte daquela realidade. 
Para que se constroem e usam modelos? 
Prof. Nicolau Reinhard - FEAUSP 
Tipos de modelos 
 
A. Modelos Físicos 
1. Icônicos – reproduzem imagem (simplificada) da realidade 
Ex: Fotografia, planta, maquete, etc. 
2. Analógicos – construir um outro sistema concreto que é similar 
ao fenômeno em estudo sob alguns aspectos 
Ex: Sistema hidráulico como representação de uma 
situação de transporte ou problema econômico 
B. Modelos Simbólicos 
1. Modelos Descritivos (permitem simulação) 
2. Modelos Explanatórios (representam relações causais) 
Prof. Nicolau Reinhard - FEAUSP 
Porque construir um modelo simbólico 
(matemático) de um problema real? (I) 
 
 
1. Facilita a experimentação – há vantagens de 
1. Custo de experimentar 
2. Tempo para realizar o experimento e analisar os resultados 
3. Experimentar sobre um modelo reduz 
1. O risco para o ambiente 
2. Problemas de legalidade 
4. Facilita a replicação 
Prof. Nicolau Reinhard - FEAUSP 
2. Para facilitar a comunicação entre pessoas 
 de acordo com a teoria de comunicação de Habermas, a comunicação entre 
pessoas pode ser: 
 1. Instrumental – paratransmitir instruções (não contestadas) 
 2. Estratégica – visando a vantagem de uma das partes (conflito possível) 
 3. Comunicacional 
» para transmitir conhecimento e 
» busca conjunta de novo conhecimento, 
» Exploração de possibilidades 
Porque construir um modelo simbólico 
(matemático) de um problema real? (II) 
Prof. Nicolau Reinhard - FEAUSP