Pesquisa Operacional I - Objetivos Ementa e Conteúdo Programático

Pesquisa Operacional I Prof Tadeu Ap Martins 1 Objetivos Apresentar aos discentes a Pesquisa Operacional como a ciência aplicada para a tomada de decisões Facilitar aos alunos competências diversas para Identificar e caracterizar problemas de decisão de otimização e de gestão associados a sistemas do mundo real Representar os problemas através de diferentes formas como modelos matemáticos gráficos e simulação Aplicar algoritmos para obtenção de soluções para alguns tipos de problemas Analisar criticamente as soluções obtidas 2 Ementa Introdução à Pesquisa Operacional Revisão de Matrizes e Sistemas Lineares Otimização Matemática Programação Linear PL Algoritmo Simplex Analise de Sensibilidade Problema de Transportes Redes Apresentação dos problemas clássicos 3 Conteúdo Programático 1 Introdução à Pesquisa Operacional 11 O que é PO 12 Problemas típicos 13 Revisão de Matrizes Determinantes e Sistemas Lineares 2 Problemas de decisão de otimização simulação e outros a considerar 3 Otimização Matemática 4 Programação Linear PL 41 Solução Gráfica 5 PL Algoritmo Simplex 51 Método das penalidades Big M 6 Dualidade 4 Conteúdo Programático 8 Solução por softwares 9 Análise de Sensibilidade 7 Problemas de Transportes 71 Definição e apresentação sob a forma de rede Formulação de caso equilibrado e não equilibrado Exemplos Propriedades fundamentais 72 Resolução do problema de transporte Obtenção de uma SBA inicial método do Canto do NE método do mínimo dos custos método de Vogel Obtenção da solução ótima 73 O problema de transporte Casos particulares degenerescência método das perturbações soluções óptimas alternativas 74 O problema de designação Formulação e resolução pelo método Húngaro 8 Redes Apresentação dos problemas clássicos 81 Problema de Fluxo Máximo 82 Problema de Caminho Mínimo 83 Problema de Transbordo 5 Metodologia de Ensino Aulas teóricas expositivas aulas práticas a fim de auxiliar na resolução dos métodos e aulas práticas em microcomputadores Utilização do Solver do Excel para a resolução de problemas de otimização 6 Metodologia de Avaliação 2 Avaliações 70 da nota 2 Trabalhos 30 da nota T A 100 Atividades Extraclasses Modelagem de exemplos didáticos modelagem de casos práticos e apresentações de seminários com os resultados obtidos trabalhos poderão ser desenvolvidos de forma individual ou em grupo 8 Referências Bibliográficas ANDRADE Eduardo Leopoldino Introdução à Pesquisa Operacional Métodos e Modelos para Análise de decisão Editora LTC 2004 ARENALES M ARMENTANO V MORABITO R e YANASSE H Pesquisa Operacional para cursos de engenharia Editora Elsevier Rio de Janeiro 2007 HILLIER F S LIEBERMAN G J Introdução à Pesquisa Operacional 8ª Edição São Paulo McGrawHill 2006 LACHTERMACHER Gerson Pesquisa operacional na tomada de decisões Editora Prentice Hall 2009 TAHA H A 2007 Pesquisa Operacional 8ª Edição Editora Pearson São Paulo 2007 CAIXETAFILHO José Vicente Pesquisa Operacional técnicas de otimização aplicadas a sistemas agroindustriais 2ª Edição São Paulo Editora Atlas 2004 DA SILVA Ermes Medeiros DA SILVA Elio Medeiros GONÇALVES Valter MUROLO Afrânio Carlos Pesquisa Operacional 3ª Edição São Paulo Editora Atlas 2008 9 Contato tamartinsuniaraedubr A Pesquisa Operacional PO como ciência surgiu para resolver de uma forma mais eficiente os problemas na administração das organizações originados pelo acelerado desenvolvimento provocado pela revolução industrial Para quê a Pesquisa Operacional PO Origem da Pesquisa Operacional Origem da Pesquisa Operacional Produção Distribuição de recursos Utilização ótima de recursos Gestão da Organização Mais desenvolvimento mais complexidade na PO e Gestão A partir da Revolução Industrial aumentam os problemas na gestão das organizações as diferentes componentes dentro duma organização são sistemas autônomos com objetivos e gestão próprios os objetivos cruzamse o que pode ser melhor para uns pode ser prejudicial para outros O Problema Como gerir para obter uma melhor eficácia dentro de toda a organização A origem da PO como ciência é atribuído à coordenação das operações militares durante a 2ª Guerra Mundial quando os líderes militares solicitaram que cientistas estudassem problemas como posicionamento de radares armazenamento de munições e transporte de tropa etc A aplicação do método científico e de ferramentas matemáticas em operações militares passou a ser chamado de Pesquisa Operacional Quando é que surgiu a PO Surgimento da PO Em 1947 George Dantzig e outros cientistas do Departamento da Força Aérea Americana apresentaram um método denominado Simplex para a resolução dos problemas de Programação Linear PL Outros cientistas que dedicaram os seus estudos a PO à pesquisa do ótimo foram na Antiguidade Euclides Newton Lagrange no século XX Leontief Von Neumann Kantarovich Surgimento da PO Pesquisa estudo das Operações atividades O que é a Pesquisa Operacional Pesquisa das operações atividades de uma organização Natureza da PO 1 Uma abordagem científica na tomada de decisões O que é a Pesquisa Operacional Um conjunto de métodos e modelos matemáticos aplicados à resolução de complexos problemas nas operações atividades de uma organização Natureza da PO 2 A PO tem provocado um significativo impacto na gestão e administração de empresas em diferentes organizações Os serviços militares dos EUA continuaram a trabalhar ativamente nesta área Com o desenvolvimento da informática nas últimas décadas a PO tem sido estendida a numerosas organizações Impacto da PO PO Ciência da Administração Denominada a ciência da administração a sua utilização e implementação tem sido estendida à business economia industria industria militar engenharia civil governos hospitais etc Quais são os ramos mais importantes desenvolvidos na PO Os Ramos da PO PROGRAMAÇÃO MATEMÁTICA Programação Linear LP Problemas de distribuição de recursos Problemas de transporte Problemas de planejamento da produção Problemas de corte de materiais etc Programação Não Linear Programação Dinâmica Programação Inteira otimização Global Programação planejamento de atividades Outros Ramos da PO Quais são outros ramos da PO OUTROS RAMOS DA PO são Análise Estatística Teoria de Jogos Teoria de Filas organização do tráfego aéreo Construção de barragens etc Simulação Gestão de estoques etc Exemplos de Problemas de Decisão Se existem vários caminhos que ligam duas cidades qual é a que propicia o mínimo de gasto de combustível Se um dado combustível é obtido de uma mistura de produto de preços variados qual a composição de menor custo com poder calorífico suficiente Se tanto a Matéria Prima quanto a Mão de Obra são limitados qual a quantidade produtos que maximiza o lucro da empresa Se em uma região existem casas que devem ser interconectados com uma rede de água qual a que minimiza o gasto com tubulação Se existem vários ativos financeiros qual a combinação que melhor reflete o compromisso entre o risco e o retorno Se o espaço para armazenamento é limitado de quanto deve ser o pedido de material para atender a demanda de um certo período Exemplos de Problemas de Decisão Tomada de Decisão É o processo de identificar um problema específico e selecionar uma linha de ação para resolvêlo Tomada de Decisão Um Problema ocorre quando o estado atual de uma situação é diferente do estado desejado Uma Oportunidade ocorre quando as circunstâncias oferecem a chance do indivíduoorganização ultrapassar seus objetivos eou metas Tomada de Decisão Fatores Relevantes Tempo disponível para tomada de decisão A importância da decisão O ambiente Certezaincerteza e risco Agentes decisores Conflito de interesses Tomada de Decisão Um Problema ocorre quando o estado atual de uma situação é diferente do estado desejado Uma Oportunidade ocorre quando as circunstâncias oferecem a chance do indivíduoorganização ultrapassar seus objetivos eou metas Tomada de Decisão Fatores Relevantes Tempo disponível para tomada de decisão A importância da decisão O ambiente Certezaincerteza e risco Agentes decisores Conflito de interesses Tomada de Decisão Individual são menos complexas de serem tomadas Autoritária Participativa Tomada de Decisão Classificação Nº de Decisores Tomada de Decisão Individual Modelo Racional Decisor Consistente Racional Maximizador de utilidade Método de Resolução do Problema Identificar o problema Gerar alternativas Escolher a melhor alternativa Tomada de Decisão Classificação Nº de Decisores Tomada de Decisão em Grupo Maior Complexidade Comunicação Conflito Convencimento Diferenças culturais ABC Novo Manter Tomada de Decisão Estágios do Processo Identificação do Problema Criação de Alternativas Seleção de Alternativa Implementação e Monitoração Conceitos Iniciais Definição de Matrizes Matriz Tabela de elementos dispostos em linhas e colunas Amxn aijmxn matriz A de m linhas e n colunas Elemento da linha i e coluna j Elemento da 2 ª linha e 1ª coluna TIPOS DE MATRIZES Matriz quadrada m n x linhas x colunas Esta é uma matriz quadrada de ordem 3 3 x 3 Diagonais Só tem sentido falar de diagonais em matrizes quadradas Diagonal principal i j Diagonal secundária n 1 i j Elementos da diagonal principal 1 1 e 2 Elementos da diagonal secundária 2 1 e 4 Matriz triangular superior Matrizes Triangulares Matriz triangular inferior Elementos acima ou abaixo da diagonal principal são todos nulos Lembrese o ou da matemática não é exclusivo ou seja vale também quando ambos são verdade Esta também é uma matriz triangular Falou em diagonal falou em matriz quadrada Todas as triangulares são quadradas Casos especiais de Matrizes Triangulares Matriz identidade Matriz diagonal Apenas os elementos da diagonal principal são diferentes de zero A identidade é uma matriz diagonal cujo elementos da diagonal principal são todos iguais a um Falou em diagonal falou em matriz quadrada Todas as triangulares são quadradas Chatice hein Todas as Triangulares são quadradas logo a diagonal e a identidade são quadradas Chamamos a matriz acima de I3 identidade de ordem 3 No geral In onde n é a ordem da matriz Matriz nula Todos os elementos são nulos Chamamos a matriz nula de Omxn Então essa é O3x4 A Matriz nula não precisa ser quadrada Igualdade de Matrizes Duas matrizes são ditas idênticas quando seus elementos correspondentes são iguais Caso ao olhar essas duas matrizes e não ver que elas são iguais favor procurar o oculista Transposta troca de linha por coluna m x n n x m Matriz A transposta Simétrica Matriz quadrada tal que At A Matriz A transposta AntiSimétrica Matriz quadrada tal que At A Os elementos da transposta são os opostos da original OPERAÇÕES COM MATRIZES Adição Dadas duas matrizes A e B somaremos os elementos de A com seus correspondentes em B ou seja se tomarmos um elemento na primeira linha e primeira coluna de A devemos somálos com o elemento na primeira linha e primeira coluna de B É sempre possível somar matrizes Não Somente quando estas forem de mesma ordem Se liguem o mesmo vale pra subtração Multiplicação por escalar Multiplicação por escalar número real qualquer multiplicamos todos os elementos da matriz por este número Matriz A Matriz 2A Multiplicação de matriz por matriz CONDIÇÃO Só podemos efetuar o produto de duas matrizes Amxn e Blxp se o número de colunas da primeira for igual ao número de linhas da segunda n l A matriz C AB será de ordem m x p Em geral AB BA ou seja o produto de matrizes não comutativo Pode ser possível efetuar AB e não ser possível efetuar BA O produto da primeira linha pela primeira coluna gera o elemento C11 O produto da primeira linha pela segunda coluna gera o elemento C12 21 10 21 14 41 20 41 24 51 30 51 34 Observe multiplicamos ordenadamente os termos ou seja multiplicamos o primeiro elemento da elemento com o primeiro da coluna e por aí vai EXEMPLO 1 1 Seja A 1 0 2 3 4 1 e seja B 1 1 4 2 1 0 Calcule A B EXEMPLO 2 2 Seja A 1 0 2 3 4 1 e seja B 1 1 4 2 1 0 Calcule A B EXEMPLO 3 3 Calcule o produto das matrizes 1 2 3 2 0 1 1 2 0 2 1 3 5 0 2 EXEMPLO 4 4 A matriz A de ordem 2 x 3 definida por aij ij é dada por a 2 4 6 1 2 3 b 1 2 6 2 4 12 c 1 2 3 2 4 6 d 1 1 1 1 2 3 e 2 4 6 1 2 3 EXEMPLO 5 5 Dadas as matrizes A 1 2 3 4 5 6 B 1 3 2 2 0 1 calcule a matriz A Bt é Sistemas Lineares Prof Tadeu Ap Martins 49 Equação linear Equação linear é toda equação da forma a11x1 a12x2 a13x3 a1nxn b1 em que a11 a12 a13 a1n são números reais que recebem o nome de coeficientes das incógnitas x1 x2x3 xn são as incógnitas e b1 é um número real chamado termo independente quando b0 a equação recebe o nome de linear homogênea 50 Solução de uma equação linear Uma sequência de números reais r1r2r3rn é solução da equação linear a11x1 a12x2 a13x3 a1nxn b1 se trocarmos cada xi por ri na equação e este fato implicar que o membro da esquerda é identicamente igual ao membro da direita isto é a11r1 a12r2 a13r3 a1nrn b1 51 Um conjunto de equações lineares da forma é um sistema linear de m equações e n incógnitas A solução de um sistema linear é a nupla de números reais ordenados r1 r2 r3 rn que é simultaneamente solução de todas as equações do sistema Sistema linear 52 Matrizes associadas a um sistema linear matriz incompleta a matriz A formada pelos coeficientes das incógnitas do sistema 53 matriz completa matriz B que se obtém acrescentando à matriz incompleta uma última coluna formada pelos termos independentes das equações do sistema Matrizes associadas a um sistema linear 54 Classificação de um sistema quanto ao número de soluções SPD sistema possível e determinado solução única SPI sistema possível e indeterminado infinitas soluções SI sistema impossível não tem solução 55 Sistema normal Um sistema é normal quando tem o mesmo número de equações m e de incógnitas n e o determinante da matriz incompleta associada ao sistema é diferente de zero Se m n e det A 0 então o sistema é normal 56 Todo sistema normal tem uma única solução dada por em que i 123n D det A é o determinante da matriz incompleta associada ao sistema e Dxi é o determinante obtido pela substituição na matriz incompleta da coluna i pela coluna formada pelos termos independentes Regra de Cramer 57 Regra de Cramer Exemplo Discussão de um sistema linear Se um sistema linear tem n equações e n incógnitas ele pode ser aSPD bSPI cSI 59 Discussão de um sistema linear a possível e determinado se D det A 0 caso em que a solução é única 60 b possível e indeterminado se D Dx1 Dx2 Dx3 Dxn 0 para n 2 Se n 3 essa condição só será válida se não houver equações com coeficientes das incógnitas respectivamente proporcionais e termos independentes nãoproporcionais Um sistema possível e indeterminado apresenta infinitas soluções Discussão de um sistema linear 61 Exemplo D0 Dx 0 Dy0 e Dz0 Assim o sistema é possível e indeterminado tendo infinitas soluções Discussão de um sistema linear 62 c impossível se D 0 e existe Dxi 0 1 i n caso em que o sistema não tem solução Como D 0 e Dx 0 o sistema é impossível e não apresenta solução Discussão de um sistema linear 63 Sistemas Equivalentes Dois sistemas são equivalentes quando possuem o mesmo conjunto solução verificamos que o par ordenado x y 1 2 satisfaz ambos e é único Logo S1 e S2 são equivalentes S1 S2 64 Sistemas Equivalentes Propriedades a Trocando de posição as equações de um sistema obtemos outro sistema equivalente b Multiplicando uma ou mais equações de um sistema por um número K K IR obtemos um sistema equivalente ao anterior c Adicionando a uma das equações de um sistema o produto de outra equação desse mesmo sistema por um número k K IR obtemos um sistema equivalente ao anterior 65 Resolução de Sistemas Lineares por Escalonamento A regra de Cramer pode ser utilizada para discutir e resolver sistemas lineares em que o número de equações m é igual ao número de incógnitas n Quando m e n são maiores que três tornase muito trabalhoso utilizar essa regra Por isso usamos a técnica do escalonamento que facilita a discussão e resolução de quaisquer sistemas lineares Para tanto vamos usar as três Operações Elementares sobre linhas 66 Dizemos que um sistema em que existe pelo menos um coeficiente nãonulo em cada equação está escalonado se o número de coeficientes nulos antes do primeiro coeficiente não nulo aumenta de equação para equação Para escalonar um sistema adotamos o seguinte procedimento Sistemas escalonados 67 a Fixamos como 1º equação uma das que possuem o coeficiente da 1º incógnita diferente de zero b Utilizando as propriedades de sistemas equivalentes anulamos todos os coeficientes da 1ª incógnita das demais equações c Repetimos o processo com as demais incógnitas até que o sistema se torne escalonado Sistemas escalonados 68 Sistemas escalonados 3x y z 20 2x y z 15 4x y 5z 41 Exemplo 69 Um sistema é homogêneo quando todos os termos independentes das equações são nulos A nupla 0 0 00 é sempre solução de um sistema homogêneo com n incógnitas e recebe o nome de solução trivial Quando existem as demais soluções são chamadas nãotriviais Sistemas homogêneos 70 Uma companhia de navegação tem três tipos de recipientes A B e C que carrega cargas em containers de três tipos I II e III As capacidades dos recipientes são dadas pela matriz Quais são os números de recipientes x1 x2 e x3 de cada categoria A B e C se a companhia deve transportar 42 containers do tipo I 27 do tipo II e 33 do tipo III Exemplo Tipo do Recipiente I II III A 4 3 2 B 5 2 3 C 2 2 3 71 4 x1 5 x2 2 x3 42 3 x1 2 x2 2 x3 27 2 x1 3 x2 3 x3 33 Exemplo Tipo do Recipiente I II III A 4 3 2 B 5 2 3 C 2 2 3 72