Programação linear

UNIVERSIDADE CATÓLICA DO SALVADOR ESCOLA DE ADMINISTRAÇÃO DE EMPRESAS DISCIPLINA: PESQUISA OPERACIONAL - POP PROFESSOR: ROBERTO IBRAHIM UEHBE

PROGRAMAÇÃO LINEAR

MODELO DAS ATRIBUIÇÕES – Problema de Designação

Milton Almeida

Este trabalho foi elaborado em dezembro de 2009, e destina-se ao cumprimento de créditos da disciplina de Pesquisa Operacional, da Escola de Administração da Universidade Católica do Salvador – UCSal. Orientador: Prof. Ibrahim Uehbe

Salvador, dezembro de 2009

SUMÁRIO

EMBASAMENTO TEÓRICO 4

OTIMIZAÇÃO COMBINATÓRIA 4
TEORIA DA COMPLEXIDADE 7
TÉCNICAS DE RESOLUÇÃO DE PROBLEMAS 10

PROGRAMAÇÃO LINEAR........................................................................................12

HEURÍSTICA E META-HEURÍSTICA 13
PROBLEMA DE DESIGNAÇÃO 15
PROBLEMA DE DESIGNAÇÃO COM GARGALO 18
ALGORITMO DE PESQUISA EM VIZINHANÇA VARIÁVEL 19

CONSIDERAÇÕES FINAIS........................................................................................20

REFERÊNCIA BIBLIOGRAFICA 21

ANEXO – ESTUDO DE CASO Problema de designação..............................................................................................22

Fundamentação Teórica

1. CONSIDERAÇÕES INICIAIS

Embasamento Teórico ao estudo de otimização e temas relacionados aos algoritmos propostos para dar ênfase a uma base conceitual sobre otimização combinatória, teoria da complexidade e técnicas de resolução de problemas. Também é descrito o problema de designação, problema de designação com gargalo e a meta-heurística VNS.

2. OTIMIZAÇÃO COMBINATÓRIA

Com a busca de otimizar os processos produtivos e gerenciais para um melhor aproveitamento de recursos e conseqüentemente a diminuição de custos, organizações têm utilizado ferramentas da Pesquisa Operacional e métodos de solução de problemas da Otimização