Introdução à programação linear

Disponível somente no TrabalhosFeitos
  • Páginas : 226 (56494 palavras )
  • Download(s) : 0
  • Publicado : 27 de fevereiro de 2011
Ler documento completo
Amostra do texto
PESQUISA OPERACIONAL

Mauricio Pereira dos Santos Departamento de Matemática Aplicada Instituto de Matemática e Estatística

UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO

ii Copyright c 2.003 por Mauricio Pereira dos Santos Editoração: O autor, criando arquivo texto no format LaTex. Compilador LaTex: Miktex Compiladores dos programas: Turbo Pascal e Visual Basic Fluxos e figuras: Visio eSmartDraw, incluídos no texto como EPS (Encapsulated Postscript File).

090826

iii

Prefácio
O objetivo deste trabalho é fornecer aos alunos da cadeira de Pesquisa Operacional da UERJ um referencial que os auxilie no estudo e acompanhamento da matéria. Os tópicos básicos da cadeira, contemplados neste trabalho, incluem o estudo dos 3 problemas clássicos de Redes quais sejam o do fluxo máximopossível de ser levado entre 2 nós de uma rede, o de encontrar o menor caminho entre 2 nós de uma rede e o de encontrar a árvore de tamanho mínimo em uma rede; a técnica de controle de projetos, genericamente chamada de PERT/CPM, que é apresentada em seus conceitos básicos; o estudo das filas de espera e de seus modelos básicos, cuja importância nos dias de hoje é marcante e fundamental e por fim masnão menos importante, a Simulação e suas aplicações nos problemas do dia a dia. Agradecemos a todos aqueles que nos ajudaram nesta tarefa, especialmente os alunos que foram cobaias no uso dos rascunhos deste trabalho. Um agradecimento especial ao ex-aluno do curso de Estatística, Leonardo Barroso Gonçalves que, quando cursou a cadeira em 1993, resolveu, detalhadamente, todos os exercícios docapítulo de Filas. Incorporamos suas soluções neste trabalho. De antemão agradeço desde já a todos aqueles que puderem apontar imperfeições e erros que possam ser corrigidos. O Autor

iv

Conteúdo

1 Redes 1.1 O problema do Fluxo Máximo . . . . . . . . . . . . . . . . . . . . . . . 1.2 Formulação como um modelo clássico de P.Linear . . . . . . . . . . . . 1.3 Técnica da Rotulação . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1.4 Fluxo máximo em redes com arcos não direcionados . . . . . . . . . . . 1.4.1 Adaptação para uso da Técnica de Rotulação . . . . . . . . . . . 1.5 O problema do caminho mínimo . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Formulação como um modelo clássico de P.Linear . . . . . . . . . 1.6 Etapas do algorítimo de Dijkstra . . . . . . . . . . . . . .. . . . . . . 1.7 Árvore de Tamanho Mínimo . . . . . . . . . . . . . . . . . . . . . . . . 1.7.1 Etapas do algorítimo para encontrar a árvore do tamanho mínimo 1.8 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8.1 Respostas dos exercícios . . . . . . . . . . . . . . . . . . . . . . 2 PERT/CPM 2.1 Construção da Rede . . . . . . . . . . . . . . . . . . . . . 2.1.1Representação gráfica da Rede . . . . . . . . . . . . 2.1.2 Representação das Atividades . . . . . . . . . . . . 2.1.3 Complicação na Construção da Rede . . . . . . . . . 2.2 Determinação do Caminho Crítico . . . . . . . . . . . . . . 2.3 O Modelo PERT . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Problemas do modelo PERT . . . . . . . . . . . . . 2.4 O Modelo CPM . . . . . . . . . . . . . .. . . . . . . . . . 2.4.1 Relação entre Durações/Custos Normal e Acelerado 2.4.2 Compressão da Rede . . . . . . . . . . . . . . . . . 2.4.3 Duração ótima para o projeto . . . . . . . . . . . . 2.4.4 Resolvendo por Programação Linear . . . . . . . . . 2.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Respostas dos exercícios . . . . . . . . . . . . . . . 3 Teoria das Filas3.1 Porque as filas são “estudadas” . . . . . . . . . . . . 3.2 Componentes básicos de um processo de fila . . . . . 3.2.1 A População . . . . . . . . . . . . . . . . . . . 3.2.2 O Processo de Chegada . . . . . . . . . . . . . 3.2.3 A Disciplina da Fila . . . . . . . . . . . . . . 3.2.4 O Mecanismo de Serviço . . . . . . . . . . . . 3.3 O Teste de Aderência . . . . . . . . . . . . . . . . . . 3.4...
tracking img