Pesquisa Operacional II - Faculdade Multivix

PESQUISA OPERACIONAL II FACULDADE MULTIVIX ENSINO A DISTÂNCIA A Faculdade Multivix está presente de norte a sul do Estado do Espírito Santo com unidades presenciais em Cachoeiro de Itapemirim Cariacica Castelo Nova Venécia São Mateus Serra Vila Velha e Vitória e com a Educação a Distância presente em todo estado do Espírito Santo e com polos distribuídos por todo o país Desde 1999 atua no mercado capixaba destacandose pela oferta de cursos de graduação técnico pósgraduação e extensão com qualidade nas quatro áreas do conhecimento Agrárias Exatas Humanas e Saúde sempre primando pela qualidade de seu ensino e pela formação de profissionais com consciência cidadã para o mercado de trabalho Atualmente a Multivix está entre o seleto grupo de Instituições de Ensino Superior que possuem conceito de excelência junto ao Ministério da Educação MEC Das 2109 instituições avaliadas no Brasil apenas 15 conquistaram notas 4 e 5 que são consideradas conceitos de excelência em ensino Estes resultados acadêmicos colocam todas as unidades da Multivix entre as melhores do Estado do Espírito Santo e entre as 50 melhores do país MISSÃO Formar profissionais com consciência cidadã para o mercado de trabalho com elevado padrão de quali dade sempre mantendo a credibilidade segurança e modernidade visando à satisfação dos clientes e colaboradores VISÃO Ser uma Instituição de Ensino Superior reconhecida nacionalmente como referência em qualidade educacional R E I T O R GRUPO MULTIVIX R E I 2 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 3 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 BIBLIOTECA MULTIVIX Dados de publicação na fonte Érica Marques da Silva Santos Pesquisa Operacional II SANTOS SILVA ME Multivix 2020 Catalogação Biblioteca Central Multivix 2020 Proibida a reprodução total ou parcial Os infratores serão processados na forma da lei 4 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 LISTA DE FIGURAS UNIDADE 1 Figura 1 Representação de função por meio do diagrama de flechas 15 Figura 2 Representação da função composta por meio do diagrama de flechas 20 Figura 3 Representação para os elementos de um grafo 21 Figura 4 Notações utilizadas para representação dos elementos de um grafo 21 Figura 5 Caminho mais curto em intervalo de tempos indica para caminhos válidos ligando v a w devem ter uma duração de no mínimo três unidades e no máximo seis unidades de tempo 23 Figura 6 Caminho mais curto com vértices de passagem obrigatória 24 Figura 7 Caminho mais curto com vértices de reabastecimento 25 Figura 8 Grafos G1 G2 G3 e G4 e seus respectivos númerosclique 26 Figura 9 Grafo G com 16 conjuntos independentes de vértices e 35 conjuntos independentes de arestas 28 Figura 10 Representação geométrica do grafo e a representação por lista de adjacência do grafo 29 Figura 11 Matriz de adjacências de grafo não direcionado 30 Figura 12 Matriz de adjacência de grafo direcionado 31 Figura 13 Matriz de incidência de um grafo não direcionado 32 Figura 14 Matriz de incidência de um grafo direcionado 33 Figura 15 Tipos de árvores 34 UNIDADE 2 Figura 1 Grafo de um ecossistema de floresta 38 Figura 2 Grafo de relacionamento de uma rede social 39 Figura 3 Grafo de influência de uma rede de ecommerce 40 Figura 4 Representação de um modelo de grafo para web 41 Figura 5 Grafo de distância estático 42 5 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 LISTA DE FIGURAS Figura 6 Fluxo máximo st com 7 unidades 43 Figura 8 a As 7 pontes de Königsberg b Grafo de Euler 46 Figura 9 Exemplo de balanceamento de aletas em turbina a jato 48 Figura 10 Imagem ilustrativa de um grafo de sequenciamento de genoma 49 Figura 11 Esquema do problema do satélite de exploração 50 Figura 12 Sólidos de Platão e seus respectivos grafos tetraedro Hexaedro cubo dodecaedro e icosaedro 51 Figura 13 a Grafo planar dado que seu isomorfo b é plano 52 Figura 14 a Grafos G1 G2 e G3 e suas faces b Grafo G2 conectado 54 Figura 15 Grafo G com 14 vértices 13 arestas 5 faces e 5 componentes conexos 55 Figura 16 Grafo planar G e seus grafos planos isomorfos G1 e G2 55 Figura 17 Grafo ponderado 59 Figura 18 Exemplo de grafo ponderado 60 Figura 19 Exemplo de heurística de inserção FITSP 61 UNIDADE 3 Figura 1 Áreas de aplicação da PL 65 Figura 2 Obstáculos para solução de problemas de PL 66 Figura 3 Ilustração do uso computacional do método simplex 68 Figura 4 Tipos de variáveis de decisão 70 Figura 5 Hipóteses do modelo de programação linear 80 Figura 6 Etapas da solução gráfica de um modelo de programação linear 81 Figura 7 Fluxograma do algoritmo do Método Simplex 84 Figura 8 Interface do Solver no Excel 88 Figura 9 Resultados do modelo LCL Motores 89 Figura 10 Ilustração do resultada da análise de sensibilidade 90 6 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 LISTA DE FIGURAS UNIDADE 4 Figura 1 Exemplo de rede não direcionada 95 Figura 2 Exemplo de rede direcionada 96 Figura 3 a Mapa rodoviário que liga as cidades de Lambari a Baependi b Representação em rede do problema 99 Figura 4 Variáveis de decisão representadas por ligações da rede 100 Figura 5 Esquema do processo de fluxo mínimo 101 Figura 6 Solução ótima para o problema 102 Figura 7 Menor caminho entre fornecedor e consumidor 103 Figura 8 Rede de capacidades de fluxos 105 Figura 9 Rede de capacidades de fluxos 106 Figura 10 Rede de capacidades de fluxos 107 Figura 11 Rede de capacidades de fluxos 108 Figura 12 Rede de capacidades de fluxos 109 Figura 13 Caminho que indica o fluxo máximo 110 Figura 14 Característica do fluxo no problema de transporte 112 Figura 15 Caminho mais curto em modelo de redes 115 Figura 16 Modelagem em redes do problema de designação de tarefas como um problema de transporte 116 UNIDADE 5 Figura 1 Isaac Newton o maior precursor das Ciências Exatas 121 Figura 2 A tangência da superfície superior com o espaço de restrições no centro representa a solução 122 Figura 3 Funções suaves e derivadas 124 Figura 4 Classificação de métodos de solução para problemas com uma única variável 127 Figura 5 Classificação de métodos de solução para problemas com múltiplas variáveis 128 7 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 LISTA DE FIGURAS Figura 6 Exemplo de função côncava e convexa 133 Figura 7 Exemplo de modelo convexo 136 UNIDADE 6 Figura 1 Otimização de vendas 141 Figura 2 Exemplo de curva de elasticidade da demanda 142 Figura 3 Ilustração de maximização de margem 144 Figura 4 Tecnologia da Star Mobile 145 Figura 5 Mercado de ações 149 Figura 6 Retorno mensal de cada ativo nos últimos 12 meses 151 Figura 7 Representação em Excel do problema da empresa MDC Pactual 152 Figura 8 Solução ótima obtida pelo Solver para o problema da corretora MDC Pactual 153 Figura 9 Linha de produtos da Scorp 155 Figura 10 Exemplo de uma curva de resposta esforço de vendas 157 Figura 11 Principais produtores importadores e exportadores de açúcar no mundo em 2000 158 Figura 12 Módulos do SAP R3 160 Figura 14 Estrutura do sistema de distribuição de trigo na Australia 164 8 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 1 UNIDADE SUMÁRIO APRESENTAÇÃO DA DISCIPLINA 10 1 INTRODUÇÃO À TEORIA DOS GRAFOS 13 INTRODUÇÃO DA UNIDADE 13 11 O QUE VOCÊ PRECISA SABER 13 12 ELEMENTOS DO GRAFO 25 2 MODELAGEM E PROBLEMAS COM GRAFOS 37 INTRODUÇÃO DA UNIDADE 37 21 MODELOS E PROBLEMAS COM GRAFOS 37 22 O QUE MAIS VOCÊ PRECISA SABER 45 1 INTRODUÇÃO À PROGRAMAÇÃO LINEAR 64 INTRODUÇÃO DA UNIDADE 64 11 PROGRAMAÇÃO LINEAR UMA TÉCNICA PODEROSA 64 12 SOLUÇÃO GRÁFICA 80 1 PROBLEMAS ESPECIAIS EM REDES 93 INTRODUÇÃO DA UNIDADE 93 11 FLUXO DE REDES 93 12 PROBLEMAS ESPECIAIS 111 1 PROGRAMAÇÃO NÃO LINEAR 120 INTRODUÇÃO DA UNIDADE 120 11 CONHECENDO SOBRE PROGRAMAÇÃO NÃO LINEAR 120 12 TIPOS DE PROBLEMA DE PROGRAMAÇÃO NÃO LINEAR 129 1 PROGRAMAÇÃO NÃO LINEAR QUADRÁTICA 140 INTRODUÇÃO DA UNIDADE 140 11 PROGRAMAÇÃO QUADRÁTICA UM CASO ESPECIAL 140 12 CASOS EM PROGRAMAÇÃO NÃO LINEAR 154 2 UNIDADE 3 UNIDADE 4 UNIDADE 5 UNIDADE UNIDADE 6 9 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 ATENÇÃO PARA SABER SAIBA MAIS ONDE PESQUISAR DICAS LEITURA COMPLEMENTAR GLOSSÁRIO ATIVIDADES DE APRENDIZAGEM CURIOSIDADES QUESTÕES ÁUDIOS MÍDIAS INTEGRADAS ANOTAÇÕES EXEMPLOS CITAÇÕES DOWNLOADS ICONOGRAFIA 10 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 APRESENTAÇÃO DA DISCIPLINA Bemvindos à disciplina de Pesquisa Operacional II Aqui você irá adquirir uma base objetiva e quantitativa para solução de problemas e tomada de decisão Você como muitas outras pessoas em algum momento da sua vida profissional já passou ou ainda vai passar por situações que exijam tomada de decisões Em gestão a tomada de decisão é uma tarefa básica e consiste em decidir entre as possíveis soluções viáveis aplicáveis a determinados problemas Com o propósito de capacitar você para o processo de tomada de decisão esta disciplina foi organizada em seis unidades com temas e subtemas que por sua vez são subdivididos em seções tópicos atendendo aos objetivos do processo de ensinoaprendizagem Esperamos que até o final da disciplina vocês possam Compreender os conhecimentos básicos de grafos com ênfase na aplicação em pesquisa operacional Aplicar os conhecimentos no desenvolvimento implementação e análise dos algoritmos aplicados na programação linear e não linear Fornecer ferramentas quantitativas que auxiliem o processo de tomada de decisões utilizando para tal a Programação Linear e Programação Não Linear Conhecer e demonstrar aplicações em problemas reais Mas antes de iniciarmos nossos estudos convido você a pensar nas seguintes situações Você é proprietário de uma transportadora e precisa organizar suas entregas encontrar a melhor rota minimizar o tempo e tudo isso otimizando as despesas com combustível Agora você está no comando uma empresa de internet e uma nova região será cabeada Nesta região haverá 30 pontos por onde o cabeamento deve passar O problema é como conectar todos os pontos utilizando a menor quantidade possível de cabo 11 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Bom acho que já deu para ter uma ideia dos problemas que você consegue resolver através dos métodos analíticos que esta disciplina irá fornecer Então é fundamental que você tenha consciência que a pesquisa operacional é utilizada para te ajudar no processo de tomada de decisão UNIDADE 1 OBJETIVO Ao final desta unidade esperamos que possa 12 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Adquirir conceitos básicos de grafos Ampliar o conhecimento envolvendo Teoria dos Grafos 13 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 INTRODUÇÃO À TEORIA DOS GRAFOS INTRODUÇÃO DA UNIDADE A pesquisa operacional é uma ciência que tem como finalidade fornecer ferramentas quantitativas ao processo de tomada de decisões para obter soluções objetivas e otimizadas Teoricamente ela se sustenta em quatro campos do conhecimento científico a matemática a economia a computação e a estatística Quando é realizado um estudo de caso em pesquisa operacional de forma completa este processo corresponde à realização de testes numéricos com modelos lógicomatemáticos A utilização de modelos torna o processo mais simples e experimental Desta forma nesta unidade abordaremos os conceitos e resultados ligados a funções e relações que são relevantes para o estudo da Teoria dos Grafos A teoria dos grafos nos permite traçar modelos e definir caminhos que são fundamentais para a redução dos riscos de um projeto e para aferir o desempenho operacional visando o alcance da máxima performance Desse modo esta unidade proporcionará um conhecimento inicial sobre grafos que servirá de aporte para sua evolução Este conteúdo está organizado em dois tópicos O que você precisa saber Elementos do Grafo 11 O QUE VOCÊ PRECISA SABER Vamos começar revendo alguns conceitos importantes sobre funções e relações matemáticas que servirão de base para a compreensão e aplicação da Teoria dos Grafos na Pesquisa Operacional 111 REVISÃO DE CONCEITOS BÁSICOS DE FUNÇÕES E RELAÇÕES Tomemos dois conjuntos não vazios A e B A associação de um elemento do conjunto A a um elemento do conjunto B por meio de uma regra ou condição chamamos de relação e quando algumas condições especiais são adicionadas 14 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 à uma relação temos uma função que pode ser definida como f A B Lê se função f de A em B É uma regra ou conjunto de instruções que diz como associar cada elemento x A a um único elemento y f x B Lêse f de x BOAVENTURA 2012 Não fique parado Para saber um pouco mais sobre funções acesse o link Dados dois conjuntos não vazios A e B o produto cartesiano de A por B denotado por A B é A B x y x A y B onde x y é o par ordenado tendo x como primeiro elemento e y como segundo elemento Já uma relação R de A em B é todo subconjunto do produto cartesiano A B Podemos identificar uma função a partir do diagrama de flechas 15 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 1 REPRESENTAÇÃO DE FUNÇÃO POR MEIO DO DIAGRAMA DE FLECHAS Fonte Elaborada pela autora 2021 PraCegoVer A figura representa por meio do Diagrama de Venn situações nas quais podemos verificar se uma relação é ou não função O primeiro diagrama tem no conjunto A que é o conjunto do Domínio os elementos 1 2 1 4 O Conjunto B que é o contradomínio têm os elementos 3 5 e 7 A flecha liga o 2 do conjunto A ao 5 do conjunto B e outra flecha liga o 4 do conjunto A ao 7 do conjunto B Como o elemento 1 do conjunto A sobra ou seja não se liga a nenhum elemento de B temos que a relação representada neste diagrama não é uma Função O segundo diagrama tem no conjunto A que é o conjunto do Domínio os elementos 1 2 1 4 O Conjunto B que é o contradomínio têm os elementos 3 5 e 7 A flecha liga o 2 do conjunto A ao 5 do conjunto B e outra flecha liga o 4 do conjunto A ao 7 e ao 5 simultaneamente do conjunto B E o elemento 1 do conjunto A se liga ao 3 do conjunto B Neste caso não sobra elemento do domínio sem ligação porém o número 4 se liga a dois elementos de B temos então que a relação representada neste diagrama não é uma Função O terceiro diagrama tem no conjunto A que é o conjunto do Domínio os elementos 1 2 1 4 O Conjunto B que é o contradomínio têm os elementos 3 5 e 7 A flecha liga o 2 do conjunto A ao 5 do conjunto B e outra flecha liga o 4 do conjunto A ao 7 do conjunto B e o 1 se conecta ao 3 no conjunto B Como cada elemento do conjunto A se liga a apenas um elemento de B temos que a relação representada neste diagrama é uma Função O quarto diagrama tem no conjunto A que é o conjunto do Domínio os elementos 1 2 1 4 O Conjunto B que é o contradomínio têm os elementos 3 5 e 7 A flecha liga o 2 do conjunto A ao 5 do conjunto B e outra flecha liga o 4 do conjunto A ao 5 do conjunto B e o 1 se conecta ao 3 no conjunto B Neste caso apesar de dois elementos se ligaram ao mesmo elemento do conjunto B no caso 2 e 4 se ligam ao 5 temos que a relação representada neste diagrama é uma Função pois no contradomínio é permitido repetir ou sobrar elementos 16 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Uma função matemática utiliza de alguns conjuntos e termos com definições especiais são eles Domínio O domínio de uma função é o conjuntos dos elementos x A para os quais vai existir y B de modo que y f x Ele é representado por D f Contradomínio Representado por CD f é todo conjunto B Imagem Este conjunto é formado pelos elementos do conjunto B que foram associados aos elementos do conjunto A Desta forma podese dizer que o conjunto imagem é um subconjunto de B Ele é representado por Im f Lei de Formação ou de Correspondência É uma regra ou condição que admite associar a cada elemento de A um elemento em B Ou seja é uma expressão matemática que irá permitir definir como a função será representada Para saber um pouco mais sobre funções acesse o link httpsintegradaminhabiblioteca c o m b r r e a d e r b o o k s 9 7 8 8 5 2 1 6 3 47 7 5 e p u b c f i 6 2 2 5 B 3 B v n d v s t idref3Dchapter015D4943315B20 se2C20e205D 17 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Agora que já definimos função vamos entender os conceitos de função injetora sobrejetora e bijetora Aprenderemos a identificar tais funções a partir do diagrama de flechas e pela análise de seus gráficos Vem comigo Função injetora Uma função f A B é considerada injetora ou injetiva se e somente se quaisquer que sejam 1 2 x e x em A se 1 x 2 x então 1 2 f x f x Representação da função injetora por meio do diagrama de flechas Fonte Elaborada pela autora 2021 PraCegoVer A figura representa uma função injetora por meio do diagrama de flechas no diagrama os elementos do domínio 1 2 4 6 8 se ligam aos elementos 1 3 5 7 9 formando o conjunto imagem e o elemento 9 do contradomínio sobra sem formar par 18 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Função Sobrejetora Uma função f A B é sobrejetora ou sobrejetiva se e somente se para todo y pertecente a B existe um elemento x em A tal que f x y ou seja a imagem de f é igual ao contradomínio B Im f B Representação da função sobrejetora por meio do diagrama de flechas Fonte Elaborada pela autora 2021 PraCegoVer A figura representa uma função sobretora por meio do diagrama de flechas no diagrama os elementos do domínio 1 2 4 6 8 se ligam aos elementos 3 5 7 9 formando o conjunto imagem ou seja não há sobre de elementos do contradomínio que neste caso pode ser usado mais de uma vez 19 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Função Bijetora Uma função f A B é bijetora ou bijetiva se e somente se ela é injetora e sobrejetora Ou seja todo elemento do contradomínio corresponde um único elemento do qual o primeiro elemento é imagem no domínio Representação da função bijetora por meio do diagrama de flechas Fonte Elaborada pela autora 2021 PraCegoVer A figura representa uma função Bijetora por meio do diagrama de flechas no diagrama os elementos do domínio 1 2 4 6 8 se ligam aos elementos 1 3 5 7 9 formando o conjunto imagem igual ao contradomínio assim todos os elemento do contradomínio são utilizados apenas uma vez Vamos supor que temos duas funções f e g definidas como f A Be g B C Perceba que dado um elemento x A usando a função f obteremos um elemento y f x B e usando a função g teremos um elemento z g x C Assim podemos obter assim uma função h A C que associa a cada x A elemento z h x C Este tipo de função recebe um nome especial de função composta A figura 2 mostra no digrama de flechas a representação de uma função composta SZWARCFITER 2018 20 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 2 REPRESENTAÇÃO DA FUNÇÃO COMPOSTA POR MEIO DO DIAGRAMA DE FLECHAS Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o diagrama de flechas de uma composição de funções O conjunto A tem seu elemento X ligado por flecha ao elemento do conjunto B por meio da função f assim o conjunto A é domínio de f O elemento y do conjunto B por sua vez se liga por meio de flechas ao elemento z do conjunto C por meio da função g Com isso temos que o elemento y é a imagem de fx e z a imagem de gy Logo existe uma função h que relaciona as funções fx e gy formando a função composta h gfx 112 CONCEITOS BÁSICOS DE GRAFOS A Teoria dos Grafos TG é uma área de conhecimento voltada ao estudoanálise das estruturas matemáticas chamadas grafos Um grafo é uma estrutura de abstração muito útil na representação e solução de diversos tipos de problema Do ponto de vista da Matemática um grafo formaliza relações de interdependência existentes entre os elementos de um conjunto Um grafo possui representação gráfica bastante prática e funcional SZWARCFITER 2018 Um grafo é composto de vértices e arestas A Figura 3a mostra as representações para os vértices de um grafo A Figura 3b exibe as formas de ligação e a Figura 3c como vértices se unem através de arestas ou arcos 21 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 3 REPRESENTAÇÃO PARA OS ELEMENTOS DE UM GRAFO Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o elementos de um grafo A figura a mostra que o vértice ou nó pode ser presentado por um círculo sólido ou um quadrado a figura b mostra que a aresta ou arco é uma linha já a figura c mostra a ligação entre dois vértices sendo feita por uma aresta indicando um grafo orientado ou não no caso de grafo ser orientado a aresta indica a direção com uma seta na A Figura 4 apresenta as notações que serão utilizadas de forma indistinta nesta unidade BOAVENTURA 2012 FIGURA 4 NOTAÇÕES UTILIZADAS PARA REPRESENTAÇÃO DOS ELEMENTOS DE UM GRAFO Fonte Elaborada pela autora 2021 PraCegoVer A figura representa as notações dos grafos indicando os conjuntos de vértices e arestas A primeira figura mostra o conjunto de vértices do grafo G VG rotulados com os números 1 2 3 e 4 e as arestas EG indicadas por a1 a2 a3 e a4 Na segunda figura o conjunto de vértices VG tem seu elementos indicados pelas variáveis x1 x2 x3 e x4 e as arestas EG por a14 a24 a23 e a34 onde a numeração subscrita das arestas indicam a ligação entre os vértices Na última figura os vértices e arestas são valorados e formam os pares de adjacência assim temos para o conjunto de vértices VG 14 são adjacentes pois possuem uma aresta que os conecta o par de vértices 12 são também adjacentes assim como os pares de vértices 23 2 34 Ainda nesta figura as arestas conectam vértices valorados então o par de arestas 1 4 conecta os vértices que possuem valor 1 e 4 respectivamente o mesmo temos para os pares de arestas 1 2 2 3 34 22 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Além de aceitar formalizações distintas são comuns notações especiais O laço é uma notação dada quando uma aresta parte de um vértice e volta nele mesmo sem passar por outra aresta Quando duas arestas representam ligações diferentes entre vértices idênticos elas são denominadas arestas paralelas 113 CAMINHOS Os caminhos ou percursos em grafos podem ser associados a várias restrições principalmente quando representam problemas reais As restrições mais comuns dizem respeito à presença ou ausência de determinados vértices ou arestas na solução e ao tempo Os caminhos se associam aos problemas de roteamento caracterizandose muitas situações como restrições de disponibilidade de combustível capacidade dos veículos trabalho nos vértices pagamento de pedágio recolhimento de bônus etc Vamos caracterizar alguns desses modelos 1 Caminho mais Curto com Custos nos Vértices O caminho mais curto entre os vértices a e b de um grafo G ponderado em vértices e arestas é aquele cuja soma dos pesos das arestas e dos vértices tem o menor valor possível dentre todos os caminhos existentes entre a e b 2 Caminho Disjunto em Arestas Dois caminhos 12 são ditos disjuntos em arestas quando não possuem aresta em comum 3 Caminho mais curto Grafo Ponderado O caminho mais curto entre os vértices v e w de um grafo G não ponderado é aquele que acumula o menor número de arestas entre os referidos vértices httpsyoutube pbDHIMFGgLk 23 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Vamos a um exemplo sobre grafo com caminho mais curto com janelas de tempo A Figura 5 exemplifica este tipo de grafo FIGURA 5 CAMINHO MAIS CURTO EM INTERVALO DE TEMPOS INDICA PARA CAMINHOS VÁLIDOS LIGANDO V A W DEVEM TER UMA DURAÇÃO DE NO MÍNIMO TRÊS UNIDADES E NO MÁXIMO SEIS UNIDADES DE TEMPO a Intervalos de visita b Tempo de percurso c Custos das arestas Fonte Elaborada pela autora 2021 PraCegoVer A figura 61 representa um grafo dos intervalos de visita O grafo possui 7 vértices com os valores indicados entre colchetes sendo eles 00 35 45 36 26 05 ocupando as extremidades de hexágono e na ordem do sentido horário e um par central 25 A figura 62 indica os tempos de percurso entre dois vértices os vértices estão rotulados pelas letras a b w e d v nos extremos do hexágono girando no sentido horário e o vértice central rotulado com a letra c Os vértices v e w são respectivamente os pontos de partida e chegada do percurso As arestas representam o tempo que leva para ir de um vértice a outro sendo os valores no sentido horário de a até b igual a 1 de b até w igual a 1 de w até e igual a 1 de e até b igual d 1 de d até b igual v 1 de v até a igual a 2 e em relação ao vértice central temos de v até c igual a 2 de a até c igual a 2 de b até c igual a 1 de w até c igual a 2 de e até c igual a 2 de d até c igual a 1 Na Figura 63 as arestas representam os custos assim temos os vértices estão rotulados pelas letras a b w e d v nos extremos do hexágono girando no sentido horário e o vértice central rotulado com a letra c Os vértices v e w são respectivamente os pontos de partida e chegada do percurso As arestas representam o tempo que leva para ir de um vértice a outro sendo os valores no sentido horário de a até b igual a 1 de b até w igual a 1 de w até e igual a 3 de e até d igual d 2 de d até v igual 2 de v até a igual a 3 e em relação ao vértice central temos de v até c igual a 5 de a até c igual a 2 de b até c igual a 2 de w até c igual a 4 de e até c igual a 1 de d até c igual a 3 Aqui dividimos nosso raciocínio em partes A Figura 5a mostra os intervalos de tempo em que cada vértice pode ser visitado O rótulo do vértice w indica que os caminhos válidos ligando v a w devem ter uma duração de no mínimo três unidades e no máximo seis unidades de tempo Os caminhos entre v e w acumulam as unidades de tempo exibidas na Figura 5b O caminho mais curto com Vértices de Passagem Obrigatória exige que o caminho entre determinado par de vértices inclua obrigatoriamente outros vértices denominados vértices de passagem obrigatória como mostra a Figura 6 24 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 6 CAMINHO MAIS CURTO COM VÉRTICES DE PASSAGEM OBRIGATÓRIA a Grafo G b Caminho mais curto tradicional10 c Caminho mais curto restrito 11 Fonte Elaborada pela autora 2021 PraCegoVer A figura 61 representa o grafo com 8 vértices e arestas valoradas A figura 62 indica o caminho mais curto tradicional igual a 10 começando do vértice 1 passando pela aresta de valor 2 chegando ao vértice 2 a partir daí através da aresta de valor 2 chega no vértice 4 e dele vai para o vértice 6 pela aresta de valor 2 e do vértice 6 chegase ao vértice 8 A figura 63 indica o caminho mais curto restrito igual 11 sendo o vértice 3 o de reabastecimento começando do vértice 1 passando pela aresta de valor 4 chegando ao vértice 3 a partir daí através da aresta de valor 1 chega no vértice 4 e dele vai para o vértice 6 pela aresta de valor 2 e do vértice 6 chegase ao vértice 8 O caminho mais curto com Vértices de Reabastecimento é o caso em que o deslocamento entre determinado par de vértices é realizado por um veículo que possui uma autonomia limitada e menor que o caminho mais curto entre os pontos que serão ligados Dessa forma o veículo deverá reabastecer durante o trajeto passando por tantos pontos de reabastecimento quantos se fizerem necessários Vamos considerar o grafo da Figura 7a o caminho mais curto irrestrito entre os vértices 1 e 8 está exibido na Figura 7b Considerando que o veículo tem uma autonomia de 7 unidades e os pontos de reabastecimento estão localizados nos vértices 3 e 7 o caminho mais curto possível é apresentado na Figura 7c 25 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 7 CAMINHO MAIS CURTO COM VÉRTICES DE REABASTECIMENTO b Caminho mais curto tradicional10 c Caminho mais curto restrito 11 a Grafo G Fonte Elaborada pela autora 2021 PraCegoVer A figura 71 representa o grafo com 8 vértices e arestas valoradas A figura 72 indica o caminho mais curto tradicional igual a 10 começando do vértice 1 passando pela aresta de valor 2 chegando ao vértice 2 a partir daí através da aresta de valor 2 chega no vértice 4 e dele vai para o vértice 6 pela aresta de valor 2 e do vértice 6 chegase ao vértice 8 A figura 73 indica o caminho mais curto restrito igual 11 sendo o vértice 3 o de reabastecimento começando do vértice 1 passando pela aresta de valor 4 chegando ao vértice 3 a partir daí através da aresta de valor 1 chega no vértice 4 e dele vai para o vértice 6 pela aresta de valor 2 e do vértice 6 chegase ao vértice 8 com os vértices 3 e 7 de reabastecimento Agora que você já conhece os conceitos iniciais sobre grafos vamos conhecer elementos interessantes e com muitas aplicações no mundo real 12 ELEMENTOS DO GRAFO Os grafos são elementos fundamentais para o processo de tomada de decisões Uma de suas representações mais práticas são as matrizes de incidência e adjacência Neste tópico vamos aprender sobre esta representação matricial bem como alguns casos de aplicação prática dos grafos em problemas reais 26 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 121 SUBCONJUNTOS DE VÉRTICES E ARESTAS Dado um grafo G VE qualquer um subgrafo completo de G VE é chamado de clique de G VE Como exemplo considere os grafos G1 G2 G3 e G4 apresentados na Figura 8 O grafo G1 tem 6 cliques com 1 vértice 9 cliques com 2 vértices e 2 cliques com 3 vértices O grafo G2 tem 6 cliques com 1 vértice 9 cliques com 2 vértices e 4 cliques com 3 vértices O G3 tem 7 cliques com 1 vértices 12 cliques com 2 vértices 5 cliques com 3 vértices e 1 clique com 4 vértices No G4 tem 6 cliques com 1 vértice e 5 cliques com 2 vértices SZWARCFITER 2018 FIGURA 8 GRAFOS G1 G2 G3 E G4 E SEUS RESPECTIVOS NÚMEROSCLIQUE Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um subgrafo completo de G VE chamado de clique de G VE O grafo G1 tem 6 cliques com 1 vértice 9 cliques com 2 vértices e 2 cliques com 3 vértices O grafo G2 tem 6 cliques com 1 vértice 9 cliques com 2 vértices e 4 cliques com 3 vértices O G3 tem 7 cliques com 1 vértices 12 cliques com 2 vértices 5 cliques com 3 vértices e 1 clique com 4 vértices No G4 tem 6 cliques com 1 vértice e 5 cliques com 2 vértices Vamos a uma definição a partir do que vimos na fig 8 Considere o grafo simples básico G VE a partir dele podemos dizer que 1 Conjunto estável de vértices Um subconjunto de vértices W é chamado de conjunto estável de vértices ou independente se nenhum par de vértices em W é adjacente um ao outro 27 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 2 Maior conjunto independente de vértices Um subconjunto de vértices MW é chamado de maior conjunto independente de vértices se não existir um conjunto independente de vértices W em G tal que W MW O número de vértices em MW é o número de independência ou número de estabilidade interna notado por αG 3 Conjunto independente de arestas Um subconjunto de arestas Z é chamado de conjunto independente de arestas ou estável se nenhum par de arestas em Z é tal que uma seja adjacente à outra 4 Maior conjunto independente de arestas Um subconjunto de arestas MZ é chamado de maior conjunto independente de arestas ou estável se não existir um conjunto independente de arestas Z em G tal que Z MZ Uma cobertura de vértices de G é um subconjunto de vértices V1 V tal que se vivj E então ou vi V1 ou vj V1 ou ambos Dizse então que o conjunto V1 cobre as arestas de G ou seja o conjunto de vértices V1 V é uma cobertura de vértices de G se toda aresta de E é incidente a pelo menos um vértice de V1 Quando nos referimos à cobertura de vértices é comum trabalhar com a cobertura de vértice mínima Uma cobertura de vértices VM de G é uma cobertura de vértices mínima se não existe uma cobertura de vértices V1 tal que V1 VM O número de vértices em uma cobertura de vértices mínima é chamado de número de cobertura de vértices notado por τG NICOLETTI 2017 E por fim temos um subconjunto de vértices DM V denominado de conjunto dominante de vértices mínimo A condição para a existência deste é se nenhum conjunto dominante de vértices D1 for tal que D1 DM O número de vértices em um conjunto dominante de vértices mínimo é chamado de número de dominação de vértices notado por σG Um exemplo para compreender pode ser visto a partir da figura 9 28 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 9 GRAFO G COM 16 CONJUNTOS INDEPENDENTES DE VÉRTICES E 35 CONJUNTOS INDEPENDENTES DE ARESTAS Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo G com 7 vértices v1 v2 v3 v4 v5 v6 v7 e arestas e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 O vértice v1 liga ao v2 pela aresta e1 e ao v3 pela aresta e2 o v2 liga a v3 por e3 ao v4 por e4 e v5 por e6 O v4 liga a v7 por e7 v5 liga v7por e9 v3 liga v6 por e8 v6 liga v7 por e10 Este grafo possui 16 conjuntos independentes de vértices e 35 conjuntos independentes de arestas Nesse grafo temos 1 Caso 1 um conjunto dominante de vértices que não é independente o conjunto v2 v3 v4 2 Caso 2 um conjunto independente que não é um conjunto dominante de vértices o conjunto v1 v5 3 Caso 3 um conjunto independente o conjunto v1 v7 e também um conjunto dominante de vértices 122 REPRESENTAÇÃO MATRICIAL DE GRAFOS Sendo os grafos uma poderosa ferramenta computacional existem algumas formas de representálos matematicamente com a finalidade de aplicação computacional Vamos abordar duas maneiras diferentes de representação computacional de um grafo que são relevantes via matriz de adjacência e via matriz de incidência do grafo NICOLETTI 2017 Existem diversas formas de se organizar os dados sobre um grafo de modo que eles possam ser inseridos em um computador A mais intuitiva delas e uma das mais usadas consiste em dizer para cada vértice quais outros vértices estão ligados a ele ou adjacentes a ele Uma maneira é utilizando rótulos a Figura 10 mostra um grafo rotulado e a forma como ele pode ser representado computacionalmente 29 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 10 REPRESENTAÇÃO GEOMÉTRICA DO GRAFO E A REPRESENTAÇÃO POR LISTA DE ADJACÊNCIA DO GRAFO Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo G com 7 vértices enumerados de 1 a 7 Os vértices 1 3 5 e 6 são de grau 2 O vértice 2 tem grau 3 o vértice 4 tem grau 4 e o vértice 7 tem grau 1 Ao lado temos a lista de adjacência do grafo a primeira coluna temos os vértices enumerados de 1 a 7 na segunda coluna a direita estão os vértices adjacentes na seguinte sequência vértice 1 possui os vértices 2 e 4 adjacentes vértice 2 possui os vértices 1 3 e 4 adjacentes vértice 3 possui os vértices 2 e 4 adjacentes vértice 4 possui os vértices 1 2 3 e 4 adjacentes vértice 5 possui os vértices 4 e 6 adjacentes vértice 6 possui os vértices 5 e 7 adjacentes vértice 7 possui os vértices 6 adjacentes 1221 MATRIZ DE ADJACÊNCIA A representação matricial nos dá um conceito de organização e posicionamento que possibilita o computador identificar os parâmetros de forma clara e objetiva Neste caso podemos considerar os rótulos dos vértices e associá los às linhas e às colunas de uma matriz quadrada matriz de adjacência NICOLETTI 2017 Entretanto se quisermos apenas indicar que existe uma ligação podemos escrever x ou 1 e deixar em branco as casas que não correspondam a ligações ou escrever 0 nelas No computador usamos os números As figuras 11 e 12 apresentam exemplos de matrizes de adjacências para grafos não direcionados e direcionados respectivamente As matrizes são quadradas de ordem n 30 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 11 MATRIZ DE ADJACÊNCIAS DE GRAFO NÃO DIRECIONADO a Grafo Direcionado G b Matriz de adjacência de G Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o grafo não direcionado com 6 vértices sendo o vértice 1 de grau 1 os vértices 2 3 5 e 6 de grau 2 e o vértice 4 com grau 5 O grafo tem as seguintes adjacências de vértices vértice 1 é adjacente ao vértice 4 que é adjacente aos vértices 2 3 5 e 6 O vértice 5 é adjacente ao 6 e o vértice 2 é adjacente ao vértice 3 Ao lado do grafo temos a matriz de adjacência quadrada 6 por 6 A matriz é composta de 0 e 1 onde as posições que correspondem a uma adjacência entre dois vértices é atribuída o valor 1 e caso contrário o valor zero é atribuído Assim temos o elemento a14 da matriz com valor 1 correspondendo ao vértice 1 ligado no 4 o elemento a23 da matriz com valor 1 correspondendo ao vértice 2 ligado no 3 o elemento a24 da matriz com valor 1 correspondendo ao vértice 2 ligado no 4 o elemento a32 da matriz com valor 1 correspondendo ao vértice 3 ligado no 2 o elemento a34 da matriz com valor 1 correspondendo ao vértice 3 ligado no 4 o elemento a41 da matriz com valor 1 correspondendo ao vértice 4 ligado no 1 o elemento a42 da matriz com valor 1 correspondendo ao vértice 4 ligado no 2 o elemento a43 da matriz com valor 1 correspondendo ao vértice 4 ligado no 3 o elemento a45 da matriz com valor 1 correspondendo ao vértice 4 ligado no 5 o elemento a46 da matriz com valor 1 correspondendo ao vértice 4 ligado no 6 o elemento a54 da matriz com valor 1 correspondendo ao vértice 5 ligado no 4 o elemento a56 da matriz com valor 1 correspondendo ao vértice 5 ligado no 6 o elemento a64 da matriz com valor 1 correspondendo ao vértice 6 ligado no 4 o elemento a65 da matriz com valor 1 correspondendo ao vértice 6 ligado no 5 E os demais elementos são atribuídos valor zero 31 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 12 MATRIZ DE ADJACÊNCIA DE GRAFO DIRECIONADO a Grafo Direcionado G b Matriz de adjacência de G Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o grafo direcionado com 6 vértices O grafo tem as seguintes adjacências de vértices do vértice 4 podemos ir para os vértices 1 2 e 3 Do vértice 5 pode para os vértices 4 e 6 Do vértice 3 podese ir apenas para o vértice 2 e do vértice 6 apenas para o vértice 4 Ao lado do grafo temos a matriz de adjacência quadrada 6 por 6 A matriz é composta de 0 e 1 onde as posições que correspondem a uma adjacência entre dois vértices é atribuída o valor 1 e caso contrário o valor zero é atribuído Assim temos o elemento a41 da matriz com valor 1 correspondendo ao vértice 4 ligado na direção do 1 o elemento a42 da matriz com valor 1 correspondendo ao vértice 4 ligado na direção do 2 o elemento a43 da matriz com valor 1 correspondendo ao vértice 4 ligado na direção do 3 o elemento a54 da matriz com valor 1 correspondendo ao vértice 5 ligado na direção do 4 o elemento a56 da matriz com valor 1 correspondendo ao vértice 5 ligado na direção do 6 o elemento a44 da matriz com valor 1 correspondendo ao vértice 4 ligado na direção do 4 E os demais elementos são atribuídos valor zero Note que na Figura 11 o valor 1 é atribuído onde há adjacência entre os vértices Já na Figura 12 a adjacência entre os vértices segue a orientação do grafo 1222 MATRIZ DE INCIDÊNCIA Esta matriz é vérticeligação lembrese que a matriz de adjacência é vértice vértice Na matriz de incidência cada linha corresponde a um vértice e em cada coluna são assinalados os dois vértices associados a uma determinada ligação Se o grafo for direcionado são atribuídos aos valores os sinais de positivo e negativo ou da seguinte forma o vértice de saída da aresta k é marcado com 1 e o de entrada com 1 Se o grafo é não direcionado as duas posições recebem valor unitário Portanto apenas duas posições de cada coluna são utilizadas o que eventualmente permite a compactação da matriz do ponto de vista computacional GOLDBARG 2012 As figuras 13 e 14 apresentam exemplos de matrizes de incidência para grafos não direcionados e direcionados respectivamente 32 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 13 MATRIZ DE INCIDÊNCIA DE UM GRAFO NÃO DIRECIONADO a Grafo não Direcionado G b Matriz de incidência Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o grafo não direcionado com 6 vértices sendo o vértice 1 de grau 1 os vértices 2 3 5 e 6 de grau 2 e o vértice 4 com grau 3 O grafo tem as seguintes incidências de vértices vértice 1 é incidente ao vértice 4 que é incidente aos vértices 2 e 5 O vértice 5 é incidente ao 6 o vértice 2 é incidente ao vértice 3 e o vértice 6 incidente ao vértice 3 As arestas u1 u2 u3 u4 u5 e u6 conectam os vértices na seguinte ordem u3 liga 1 e 4 u2 4 e 2 u1 2 e 3 u6 3 e 6 u5 5 e 6 u4 5 e 4 Ao lado do grafo temos a matriz de incidência quadrada 6 por 6 onde as linhas representam as arestas u1 u2 u3 u4 u5 u6 e as colunas os vértices 1 a 6 A matriz é composta de 0 e 1 onde as posições que correspondem a uma incidência entre dois vértices é atribuída o valor 1 e caso contrário o valor zero é atribuído Assim temos o elemento a12 da matriz com valor 1 correspondendo a aresta u1 incidindo no vértice 2 o elemento a13 da matriz com valor 1 correspondendo a aresta u1 incidindo no vértice 3 o elemento a22 da matriz com valor 1 correspondendo a aresta u2 incidindo no vértice 2 o elemento a24 da matriz com valor 1 correspondendo a aresta u2 incidindo no vértice 4 o elemento a31 da matriz com valor 1 correspondendo a aresta u3 incidindo no vértice 1 o elemento a34 da matriz com valor 1 correspondendo a aresta u3 incidindo no vértice 4 o elemento a43 da matriz com valor 1 correspondendo a aresta u4 incidindo no vértice 3 o elemento a44 da matriz com valor 1correspondendo a aresta u4 incidindo no vértice 4 o elemento a45 da matriz com valor 1 correspondendo a aresta u4 incidindo no vértice 5 o elemento a55 da matriz com valor 1 correspondendo a aresta u5 incidindo no vértice 5 o elemento a55 da matriz com valor 1 correspondendo a aresta u5 incidindo no vértice 6 o elemento a63 da matriz com valor 1 correspondendo a aresta u6 incidindo no vértice 3 o elemento a66 da matriz com valor 1 correspondendo a aresta u6 incidindo no vértice 6E os demais elementos são atribuídos valor zero Na Figura 13 o valor 1 na coluna i da matriz de incidência corresponde ao número de arestas incidentes no iésimo vértice Por exemplo na coluna 2 da matriz observase que apenas duas arestas incidem no vértice 2 Na Figura 15 o grafo orientado ao ser representado por sua matriz de incidência tem os valores 1 atribuído aos vértices de chegada e 1 aos vértices de saída Por exemplo u1 é uma aresta de chegada no vértice 2 enquanto de ela é uma aresta de saída no vértice 3 33 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 14 MATRIZ DE INCIDÊNCIA DE UM GRAFO DIRECIONADO a Grafo Direcionado G b Matriz de incidência Fonte Elaborada pela autora 2021 PraCegoVer A figura representa o grafo direcionado com 6 vértices O grafo tem as seguintes direções de 1 para 4 de 4 para 2 de 5 para 4 e para 6 de 3 para 2 e de 6 para 3 Ao lado do grafo temos a matriz de incidência quadrada 6 por 6 onde as linhas representam as arestas u1 u2 u3 u4 u5 u6 e as colunas os vértices 1 a 6 A matriz é composta de 0 1 e 1 onde as posições que correspondem a chegada recebem valor 1 saída valor 1 e 0 os demais Assim temos o elemento a12 da matriz com valor 1 correspondendo a aresta u1 chegando no vértice 2 o elemento a13 da matriz com valor 1 correspondendo a aresta u1 saindo do vértice 3 o elemento a22 da matriz com valor 1 correspondendo a aresta u2 chegando no vértice 2 o elemento a24 da matriz com valor 1 correspondendo a aresta u2 saindo do vértice 4 o elemento a31 da matriz com valor 1 correspondendo a aresta u3 saindo no vértice 1 o elemento a34 da matriz com valor 1 correspondendo a aresta u3 chegando no vértice 4 o elemento a44 da matriz com valor 1correspondendo a aresta u4 chegando no vértice 4 o elemento a45 da matriz com valor 1 correspondendo a aresta u4 saindo no vértice 5 o elemento a55 da matriz com valor 1 correspondendo a aresta u5 incidindo no vértice 5 o elemento a55 da matriz com valor 1 correspondendo a aresta u5 saindo no vértice 6 o elemento a56 da matriz com valor 1 correspondendo a aresta u5 chegando no vértice 6 o elemento a63 da matriz com valor 1 correspondendo a aresta u6 chegando no vértice 3 o elemento a66 da matriz com valor 1 correspondendo a aresta u6 saindo no vértice 6E os demais elementos são atribuídos valor zero 123 ÁRVORES Alguns grafos não admitem ciclos por isso são chamados de acíclicos A classe mais importante destes grafos é composta pelas árvores Elas modelam uma série de aplicações do mundo real De forma bem simples podemos dizer que uma árvore é um grafo conexo e acíclico Em uma árvore o vértice que possui grau 1 é chamado de folha ou vértice terminal e quando o número de vértices terminais de um grafo é 2 chamamos de vértices extremos do grafo GOLDBARG 2012 34 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Definição Árvore é um grafo conexo T em que existe um e somente um caminho entre qualquer par de vértice de T Se um subgrafo é conexo e acíclico de um grafo temos uma subárvore GOLDBARG 2012 A Figura 17 mostra alguns tipos árvores utilizadas na formação de estruturas de dados e na solução de problemas reais FIGURA 15 TIPOS DE ÁRVORES a Árvore ponderada b Árvore não ponderada c Estrela Fonte Elaborada pela autora 2021 PraCegoVer A figura representa tipos de árvores ponderadas A primeira árvore possui 6 vértices enumerados de 1 a 7 com duas arestas de peso 1 três arestas de peso 2 e uma aresta de peso 4 O vértice 1 se liga a duas arestas de valor 1 e 4 cada uma o vértice 2 tem três arestas sendo duas de peso 1 e uma de peso 2 o vértice 3 se liga a uma aresta de peso 1 o vértice 4 se liga a três arestas de peso 2 o vértice 5 a uma aresta 5 de peso 2 o vértice 6 a uma aresta de peso 2 e o vértice 7 a aresta de peso 4 A outra figura é o tipo de árvore não ponderada onde os vértices são enumerados de 1 a 7 e suas arestas não possuem peso Este grafo tem os vértices 1 3 6 e 1 de grau 1 o vértice 4 de grau 2 e os vértices 2 e 5 de grau 3 A última figura apresenta uma árvore do tipo estrela com 7 vértices sendo 6 deles de grau 1 e o central de grau 6 Quer saber mais sobre estes tipos de árvores Veja aqui httpsintegradaminhabibliotecacombrreader books9788521211327pageid77 35 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II CONCLUSÃO Esta unidade teve por objetivo apresentar os conceitos iniciais imprescindíveis para a aprendizagem e a aquisição de novos conceitos Aqui discutimos os conceitos de funções e relações matemáticas bem como suas aplicações A Teoria dos Grafos e a matemática constituem uma base sólida para sucesso e compreensão de todo processo de tomada de decisões que envolve a disciplina de pesquisa operacional O estudo construiu de forma objetiva clara e coerente o raciocínio lógico sobre os conceitos básicos que é necessário para compreensão dos processos de otimização e tomadas de decisão UNIDADE 2 OBJETIVO Ao final desta unidade esperamos que possa 36 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Adquirir conceitos básicos de grafos Demonstrar que a modelagem em grafos pode ser utilizada em uma enorme gama de aplicações 37 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 2 MODELAGEM E PROBLEMAS COM GRAFOS INTRODUÇÃO DA UNIDADE A teoria dos grafos estuda objetos combinatórios pois eles são bons modelos para muitos problemas em vários ramos da matemática da computação da engenharia da química da psicologia e da indústria Segundo a história dos grafos os primeiros registros científicos vieram com o artigo de Leonhard Euler publicado em 1736 Nesse artigo ele relatou o problema das sete pontes de Königsberg que até hoje é considerado por muitos estudiosos como o primeiro problema sobre grafos Assim como o problema das pontes muitos outros problemas sobre grafos tornaramse famosos e entraram para história isso porque são um interessante desafio intelectual e têm importantes aplicações práticas Nesta unidade conheceremos um pouco mais sobre esse fantástico universo da teoria dos grafos e suas aplicações em modelos O objetivo do presente trabalho é integrar problemas reais com soluções através de representações por grafos mostrando que a modelagem em grafos pode ser utilizada em uma vasta gama de aplicações 21 MODELOS E PROBLEMAS COM GRAFOS Modelos são representações formais de problemas reais visto pelo profissional que deseja empregar seus conhecimentos para por meio do modelo interpretar modificar gerenciar implementar resolver ou controlar o problema de alguma outra maneira Problemas modelados por meio de grafos são considerados uma forma clássica e simplificada de encontrar a solução de forma prática e objetiva 211 MODELOS DE APLICAÇÃO A modelagem em grafos pode ser utilizada em muitas aplicações tanto no que diz respeito à solução de problemas do mundo real como para aplicações na matemática discreta Nesta seção vamos abordar alguns exemplos de modelos de aplicação em gafos As aplicações que iremos conhecer e discutir abrangem diversas áreas do conhecimento 38 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 2111 GRAFOS NA BIOLOGIA Em ciências biológicas é comum utilizar modelos que envolvem a interação entre espécies de animais distintas Como exemplo podemos considerar a competição entre espécies em um ecossistema que pode ser modelada usando um grafo de superposição de nicho em que o vértice representa cada espécie e as arestas não direcionadas ligam dois vértices se duas espécies representadas pelos vértices usam as mesmas fontes de alimentos SZWARCFITER 2018 O tipo de grafo de superposição de nicho possui características de um grafo simples ou seja não são necessários nem laços e nem arestas múltiplas O grafo da figura 1 modela o ecossistema de uma floresta os vértices são espécimes e animais que vivem na floresta as arestas fazem a ligação desses elementos em relação à cadeia alimentar existente no ecossistema FIGURA 1 GRAFO DE UM ECOSSISTEMA DE FLORESTA Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo com seis vértices Os vértices são rotulados O Vértice com rótulo Plantas Aquáticas é conectado por arestas aos vértices peixes herbívoro e Caramujo O Vértice com rótulo peixes herbívoro é conectado por arestas aos vértices peixes carnívoro e Ave O Vértice com rótulo Ave é conectado por aresta ao vértice Rã O Vértice com rótulo Caramujo é conectado por aresta ao vértice peixes carnívoro 39 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 2112 GRAFOS NA REPRESENTAÇÃO DE ESTRUTURAS DE RELACIONAMENTOS SOCIAIS Acredite é possível usar grafos para modelagem de relações entre pessoas Por exemplo Ana e Patrícia são amigas de faculdade assim elas possuem um relacionamento e um grafo simples representa o relacionamento entre Ana e Patrícia Cada pessoa é representada por um vértice e uma aresta não orientada é usada para conectar duas pessoas quando elas se conhecem Nesse tipo de grafo de relacionamento não são necessários laços e arestas múltiplas Um pequeno grafo de relacionamento de redes sociais pode ser visto na figura 2 em que as pessoas são conectadas por arestas que representam a relação de amizade entre elas SZWARCFITER 2018 FIGURA 2 GRAFO DE RELACIONAMENTO DE UMA REDE SOCIAL Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo com 12 vértices Os vértices são rotulados O Vértice com rótulo Vinícius é conectado por arestas aos vértices Carol Gustavo e Érica O Vértice com rótulo Gustavo é conectado por arestas aos vértices Carol e Érica O Vértice com rótulo Érica é conectado por arestas aos vértices Camila e Myrian O Vértice com rótulo Myrian é conectado por arestas aos vértices Carlos e Fernanda O Vértice com rótulo Fernanda é conectado por aresta ao vértice Jéssica O Vértice com rótulo Jéssica é conectado por arestas aos vértices Elias e Carla O Vértice com rótulo Carla é conectado por aresta ao vértice Camila O Vértice com rótulo Camila é conectado por aresta ao vértice Jefinny O Vértice com rótulo Jefinny é conectado por aresta ao vértice Elias 40 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 113 GRAFOS DE INFLUÊNCIA Os grafos de influência são responsáveis por representar o comportamento de um grupo Aqui podemos pensar como certas pessoas podem influenciar o pensamento de outras A relação e o poder de influência podem ser representados por um grafo orientado chamado de grafo de influência Nele cada indivíduo do grupo é representado por um vértice e uma aresta orientada exibe quando uma pessoa representada pelo vértice a influencia outra pessoa representada pelo vértice b BOAVENTURA 2017 A figura 3 mostra um exemplo de um grafo de influência entre pessoas de um sistema de ecommerce em que de acordo com as características e ocupações um indivíduo influencia outros FIGURA 3 GRAFO DE INFLUÊNCIA DE UMA REDE DE ECOMMERCE Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo orientado com 8 vértices Os vértices são rotulados O Vértice com rótulo José é conectado pelas arestas de incidência aos vértices Kátia e Renato O Vértice com rótulo Kátia é conectado por arestas de incidência aos vértices Renato e Márcio O Vértice com rótulo Lia é conectado por arestas de incidência aos vértices Kátia Pietro Bianca e Márcio O Vértice com rótulo Pietro é conectado por aresta de incidência ao vértice Bianca O Vértice com rótulo Márcio é conectado por aresta de incidência ao vértice Pietro O Vértice com rótulo Jéssica é conectado por arestas aos vértices Elias e Carla O Vértice com rótulo Márcio é conectado por aresta de incidência ao vértice Felipe 41 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 2114 GRAFOS NA WEB No século XXI a web é uma das fontes de dados heterogêneas mais completa e em constante evolução A web abarca vários tipos de dados como multimídia texto dados não estruturados dados semiestruturados entre outros Por essas características a web se tornou uma rede complexa Como forma de simplificação ela pode ser modelada como um grafo ou seja a rede complexa é representada por meio de um objeto matemático cujos nós também denominados vértices modelam elementos que podem ser páginas web pessoas computadores e as arestas modelam relacionamentos entre os vértices Algo muito importante a ser destacado é que os grafos que representam problemas reais ligados a web tendem a apresentar estruturas irregulares e por isso eles são denominados de redes complexas A figura 4 ilustra de forma simplificada um modelo de grafo de web GOLDBARG 2012 FIGURA 4 REPRESENTAÇÃO DE UM MODELO DE GRAFO PARA WEB Fonte Pixabay 2018 PraCegoVer A figura representa uma rede formada por vértices e arestas de tamanhos diferentes que se conectam por meio de arestas que representam os links ou conexões Você deve se inteirar mais sobre o assunto pois as aplicações são essenciais para esta disciplina então acesse este link e aprenda tudo que você precisa saber sobre modelagem de grafos httpsbit ly3KaUPbY 42 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 212 PROBLEMA DO FLUXO MÁXIMO COM GRAFOS Como é de conhecimento é possível que os grafos sejam ponderados ou seja são grafos nos quais se atribui algum tipo de valor aos vértices ou às arestas Há diversas possibilidades de valoração para um grafo e o uso de uma ou mais delas depende do modelo com o qual se trabalha Nesse momento da nossa discussão o foco é trabalhar com valores ou ponderações estáticas ou seja os valores atribuídos aos vértices ou arestas estarão associados apenas àquele elemento com a ressalva de valores coincidentes é claro Para entender essa natureza estática vamos supor que a distância entre duas cidades A e B seja de 413 km como mostra a figura 5 Assim o valor referente à distância de 413 km está associado exclusivamente à aresta que liga as cidades A e B exceto que haja coincidência de tamanhos mas então os dois valores iguais estarão atribuídos aos dois trechos e a mais nenhum outro GOLDBARG 2012 FIGURA 5 GRAFO DE DISTÂNCIA ESTÁTICO Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo com dois vértices um deles representando a cidade A o outro a cidade B A aresta que liga as cidades representa a distância sinalizada entre elas que é de 413 km Mencionar a existência de valores estáticos é importante pois existe a valoração dinâmica ou seja agora os valores podem mudar de acordo com a situação por exemplo se contarmos o número de veículos que passam por uma praça de pedágio num determinado tempo seja por exemplo 150 veículos em um quarto de hora é possível estimar que naqueles momentos estariam passando por lá 600 veículos por hora observe a diferença na unidade em relação aos exemplos anteriores Estamos falando aqui de um certo número de veículos por unidade de tempo GOLDBARG 2012 Os problemas de fluxo tratam a questão de fazer circular determinado 43 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II produto por meio dos vértices e das arestas de uma rede Portanto esse tipo de problema associa aos já conhecidos componentes de um grafo um novo elemento denominado fluxo Os problemas de fluxo são associados às várias situações reais de distribuição de água eletricidade produtos industriais tráfego de veículos etc GOLDBARG 2012 A distribuição dos produtos de uma rede não é feita obrigatoriamente de um ponto de produção a um ponto de demanda ou seja é permitido que pontos intermediários como depósitos ou centros de concentração e distribuição sejam utilizados Esses pontos de interligação podem possuir restrições como limite na capacidade de tráfego e custos variados Falaremos do problema de fluxo máximo que consiste em fazer circular em uma rede representada por R V E F U o maior fluxo possível entre os vértices s e t sempre respeitando as restrições que são impostas nos limites do conjunto U A figura 6 apresenta um exemplo cujos valores em vermelho na valoração referemse ao fluxo máximo na rede proposta GOLDBARG 2012 FIGURA 6 FLUXO MÁXIMO ST COM 7 UNIDADES Fonte Goldbarg 2012 PraCegoVer A figura representa um grafo valorado e direcionado de fluxo máximo com início no vértice s e fim no vértice t A aresta de incidência que liga o vértice S ao vértice x1 tem os valores entre colchetes 044 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice S ao vértice x2 tem os valores entre colchetes 033 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x1 ao vértice x2 tem os valores entre colchetes 002 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x1 ao vértice x4 tem os valores entre colchetes 022 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x1 ao vértice x3 tem os valores entre colchetes 022 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x2 ao vértice x3 tem os valores entre colchetes 004 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x3 ao vértice t tem os valores entre colchetes 026 sendo o valor central o valor de fluxo máximo da aresta A aresta de incidência que liga o vértice x4 ao vértice t tem os valores entre colchetes 0510 sendo o valor central o valor de fluxo máximo da aresta 44 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 121 ALGORITMO DE FORD E FULKERSON UM ALGORITMO BASEADO NO CAMINHO DE AUMENTO DE FLUXO Uma explicação bem plausível sobre em que consiste o algoritmo baseado no caminho de aumento de fluxo pode ser vista a seguir Uma das estratégias mais antigas utilizadas para a determinação de fluxo máximo em redes é encontrar uma sequência de caminhos de aumento de fluxo entre s e t caminhos definidos no grafo de aumento de fluxo Para cada caminho de aumento de fluxo encontrado esses algoritmos fazem circular um fluxo entre s e t que esgota seu arco de menor capacidade e atualiza as capacidades dos arcos da rede percorridos pelo fluxo Quando não for mais possível encontrar um caminho de aumento de fluxo entre s e t o fluxo máximo é alcançado GOLDBARG 2012 p 376 Um dos algoritmos que melhor representa essa estratégia é o de Ford e Fulkerson Veja a explicação a seguir 213 COLORAÇÃO E GRAFOS PERFEITOS A coloração de grafos de forma simplificada consiste em colorir os vértices ou arestas de um grafo simples e conexo de forma que dois vértices ou arestas adjacentes não tenham a mesma cor A padronização do uso de cores decorre da ação de colorir os países de um mapa Os grafos com coloração são amplamente empregados em situações em que é necessário destacar regiões classes grupos ou turnos horários etc NICOLETTI 2017 Devido ao fato de arestas ou vértices adjacentes não poderem tem as mesmas cores colorir um grafo é denominado problema de coloração Esse problema é simples se o número de cores é igual ao número de vértices ou arestas aos quais se deseja colorir entretanto há casos em que o número de cores é o menor possível então colorir um grafo tornase uma tarefa um pouco mais desafiadora Aqui você vai ver como determinar o fluxo máximo por meio do algoritmo de Ford e Fulkerson https youtubexC2tYIZvmgc 45 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 22 O QUE MAIS VOCÊ PRECISA SABER A teoria dos grafos é muito rica em aplicações e informações relevantes e não podemos deixar de falar sobre os ciclos e suas aplicações pois elas deram forma a origem da teoria dos grafos Os grafos planares oferecem uma forma simples de resolver problemas complexos e o clássico problema do caixeiro viajante representa a teoria dos grafos aplicada em soluções de problemas em diversas áreas 221 CICLOS E APLICAÇÕES Como na história há momentos em que interessa voltar ao início para prosseguir da mesma forma vamos voltar na origem da teoria dos grafos falando sobre o primeiro problema da teoria dos grafos o da ponte de Königsberg que foi resolvido por Euler quando de sua visita à cidade As figuras 8 a e b mostram a ponte e seu respectivo grafo NICOLETTI 2017 O estudo de coloração foi iniciado com o problema das quatro cores acesse este link e fique por dentro de todos os detalhes sobre a coloração de grafos httpsyoutubeq UApUu81WA 46 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 8 A AS 7 PONTES DE KÖNIGSBERG B GRAFO DE EULER a b Fonte Problema das Pontes de Königsberg 2021 PraCegoVer A figura A representa as 7 pontes de Konigsberg elas são representadas pelas letras do alfabeto a b c d e f e g As pontes a b c d e e formam um círculo e região central é simbolizada pela letra A A ponte f está próxima da ponte d e a ponte g está próxima da ponte f A figura b representa o grafo da ponte O vértice A tem duas arestas paralelas c e d que ligam ao vértice C e outras duas arestas paralelas a e b que ligam ao vértice B A aresta g liga o vértice C ao vértice D A aresta e liga o vértice A ao vértice D A aresta f liga o vértice B ao vértice D Por muitos anos moradores e visitantes se questionavam se era possível atravessar todas as pontes em uma caminhada contínua e sem passar duas vezes pela mesma ponte Ao visitar a cidade Euler propôs uma solução SZWARCFITER 2018 O grafo apresentado na figura 8 b é a representação do modelo definido por Euler Seu modelo tem as seguintes propriedades V m m é uma ilha ou uma margem A m1m2 p existe uma ponte p unindo as margens ou ilhas m1 e m2 V A B C D A ACc ACd ABa ABb ADe BDf CDg O grafo que modela o problema é conexo não direcionado e um multigrafo O objetivo do problema consiste em partindo de qualquer vértice tentar atravessar todas as arestas uma única vez e retornar ao vértice de origem Euler ao apresentar uma solução para esse problema preocupouse em descobrir em que tipos de grafos é possível percorrer esse ciclo passando por 47 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II todas as arestas uma única vez Esse tipo de percurso fechado foi chamado caminho de Euler e um grafo que consiste em um caminho de Euler foi chamado grafo de Euler SZWARCFITER 2018 Assim Euler tentou resolver o problema das pontes de Königsberg por meio do caminho de Euler Um grafo para ser definido como grafo de Euler deve ser conexo e todos os seus vértices devem ter grau par Agora vamos aplicar o grafo de Euler no problema das pontes de Königsberg para sabermos se existe solução Ficou curioso sobre o fim desse problema Então acesse o link a seguir e veja como fica a solução do problema das pontes de Königsberg SZWARCFITER 2018 Não é difícil encontrar atualmente problemas semelhantes ao das pontes de Königsberg a ideia de encontrar um caminho que passe pelas ruas de um bairro ou pelos corredores de um prédio uma vez e uma só em cada um e voltando ao ponto de partida Problemas de vendas em domicílio de coleta de lixo de entrega de correio de visitas a museus ou a algumas grandes lojas são exemplos de problemas reais desse tipo E com um detalhe muito importante teremos que lidar com situações em que o grafo tenha vértices de grau ímpar BOAVENTURA 2017 Então restanos encontrar uma solução que atenda de forma mais ampla e geral todos os casos A solução vem com o teorema Teorema 211 O número mínimo de caminhos que dividem o conjunto de arestas de um grafo G VE não direcionado e conexo com 2k vértices de grau ímpar é 0 k k N BOAVENTURA 2017 Esse teorema nos diz que para conectarmos os k percursos parciais teremos de repetir trechos do percurso Se o grafo não for euleriano não há como agir de outra forma A solução envolvendo repetições de trechos de percurso é conhecida como um caminho préeuleriano A seguir vejamos algumas aplicações Clique aqui e veja a solução das pontes de Königsberg segundo Euler https wwwfcunespbrHome DepartamentosMatematica revistacqd2228v5a06as pontesdekonigsbergpdf 48 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 O problema da otimização de turbinas Uma turbina a jato deve funcionar em rotação uniforme e sem vibrações Para tal suas aletas devem ser posicionadas de forma a otimizar o giro O problema de localizar as aletas de uma turbina de forma a obter a melhor configuração possível é um problema que de uma forma geral é equivalente a distribuir as aletas em uma circunferência de modo a harmonizar as diferenças de fabricação minimizar as diferenças entre aletas vizinhas Assim o problema pode ser modelado como um caixeiroviajante simétrico quando adotada uma medida de proximidade igual à diferença entre cada par de aletas A figura 9 exemplifica a aplicação GOLDBARG 2012 FIGURA 9 EXEMPLO DE BALANCEAMENTO DE ALETAS EM TURBINA A JATO Fonte Goldbarg 2012 PraCegoVer A figura 1 representa um grafo de correlações valorado de doze vértices O vértice 1 é conectado ao vértice 2 pela aresta de valor 2 ao vértice 5 Pela aresta de valor 1 e ao vértice 6 pela aresta de valor 1 O vértice 2 é conectado ao vértice 5 pela aresta de valor 2 ao vértice 9 pela aresta de valor 4 ao vértice 3 pela aresta de valor 10 e ao vértice 10 pela aresta de valor 2 O vértice 3 é conectado ao vértice 4 pela aresta de valor 1 O vértice 4 é conectado ao vértice 10 pela aresta de valor 1 ao vértice 11 pela aresta de valor 4 O vértice 5 é conectado ao vértice 6 pela aresta de valor 1 ao vértice 12 ela aresta de valor 4 e ao vértice 9 pela aresta de valor 2 O vértice 6 é conectado ao vértice 7 pela aresta de valor 1 O vértice 7 é conectado ao vértice 8 pela aresta de valor 4 ao vértice 12 pela aresta de valor 10 O vértice 8 é conectado ao vértice 5 pela aresta de valor 10 ao vértice 12 pela aresta de valor 12 O vértice 9 é conectado ao vértice 12 pela aresta de valor 2 ao vértice 11 pela aresta de valor 2 O vértice 10 é conectado ao vértice 11 pela aresta de valor 4 O vértice 11 é conectado ao vértice 12 pela aresta de valor 5 ao vértice 5 A Figura 2 representa uma alocação de aletas na turbina O desenho se forma da seguinte maneira O vértice 1 se liga ao vértice 5 pela aresta 49 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II de valor 1 O vértice 5 se liga ao vértice 2 pela aresta de valor 2 O vértice 2 se liga ao vértice 10 pela aresta de valor 2 O vértice 10 se liga ao vértice 3 pela aresta de valor 2 O vértice 3 se liga ao vértice 4 pela aresta de valor 1 O vértice 4 se liga ao vértice 11 pela aresta de valor 4 O vértice 11 se liga ao vértice 9 pela aresta de valor 2 O vértice 9 se liga ao vértice 12 pela aresta de valor 2 O vértice 12 se liga ao vértice 8 pela aresta de valor 1 O vértice 8 se liga ao vértice 7 pela aresta de valor 4 O vértice 7 se liga ao vértice 6 pela aresta de valor 1 O vértice 6 se liga ao vértice 1 pela aresta de valor 1 Fechando o ciclo O problema do sequenciamento de genoma Para sequenciar um genoma diversos mapas locais do genoma obtidos por radiação devem ser integrados A integração se faz com base na verossimilhança dos mapas Mapas de regiões vizinhas são mais verossimilhantes que mapas de regiões afastadas do genoma A solução do problema do caixeiroviajante providencia um caminho para integrar os mapas locais com o mapa global GOLDBARG 2012 FIGURA 10 IMAGEM ILUSTRATIVA DE UM GRAFO DE SEQUENCIAMENTO DE GENOMA Fonte Elaborada pela autora 2021 PraCegoVer A figura representa um grafo de genoma com a seguinte sequência AAC liga na ACA que se liga em CAG e CAT CAG se liga a AGG que se liga a GGT que se liga a GTG que se liga a TGC O CAT se liga a ATA que se liga TAG que se liga a AGT que também se liga GTG que se liga TGG Uma seta vertical apontada de cima para baixo mostra a versão compactada do grafo descrito acima Onde temse AACA ligado por aresta de incidência a CAGGT e CATAGT que são conectados por arestas de incidência a GTG que se conecta por aresta de incidência a TGC e a TGG 50 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Movimentação de satélites de exploração Satélites de exploração são programados para realizar tarefas de observação sobre um conjunto de corpos celestes selecionados Para tal devem direcionar seus equipamentos para o objetoalvo A cada tarefa é preciso reposicionar aparelhos ou o próprio satélite para que o próximo alvo seja observável O problema consiste em movimentar o satélite ou seus aparelhos minimizando custos A figura 11 exibe a solução para um satélite deslocar da estrela 1 para a estrela 2 FIGURA 11 ESQUEMA DO PROBLEMA DO SATÉLITE DE EXPLORAÇÃO Fonte Goldbarg 2012 PraCegoVer A figura 1 representa o problema onde temos o satélite e as estrelas alvo Na figura 2 temos as estrelas alvo numeradas de um a sete e circuladas de modo a separálas das demais Na Figura 3 as estrelas são representadas por vértices de um grafo A figura 4 é o grafo de movimentação com nove vértices O vértice 1 se liga por arestas aos vértices 2 4 3 e 7 O vértice 2 se liga por arestas aos vértices 5 6 e 4 O vértice 3 se liga por arestas aos vértices 4 e 7 O vértice 5 se liga por arestas aos vértices 6 e 9 O vértice 6 se liga por arestas aos vértices 7 8 e 9 O vértice 7 se liga por aresta ao vértice 8 O vértice 8 se liga por aresta ao vértice 9 A Figura 5 mostra a solução viável com o caminho 1425986731 51 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 222 GRAFOS PLANARES Muitos grafos podem ser redesenhados de maneira a evitar que suas arestas se cruzem em outros pontos que não nos vértices Um grafo que possa ser redesenhado dessa maneira é chamado de grafo planar SZWARCFITER 2018 O conceito de planaridade serve de aporte para muitas aplicações do mundo real Por exemplo no projeto de distribuição de energia elétrica é desejável que se tenha um mínimo de interseções possível A situação ideal é a do projeto de um circuito que seja planar e portanto não tenha interseções Grafos planares desempenham um papel importante no chamado problema de coloração que também já foi discutido nesta unidade Um grafo planar é um grafo que admite uma representação gráfica na qual as arestas só se encontrem possivelmente nos vértices aos quais são incidentes Exemplos clássicos de grafos planares são dados pelos grafos que representam os poliedros SZWARCFITER 2018 A figura 12 apresenta os 5 sólidos de Platão ou poliedros regulares e seus grafos tetraedro cubo octaedro dodecaedro e icosaedro Esses grafos são naturalmente regulares FIGURA 12 SÓLIDOS DE PLATÃO E SEUS RESPECTIVOS GRAFOS TETRAEDRO HEXAEDRO CUBO DODECAEDRO E ICOSAEDRO Fonte Boaventura Netto e Jurkiewicz 2017 PraCegoVer A figura representa os poliedros de platão e seus respectivos grafos O Tetraedro é representado pelo grafo de 4 vértices O Hexaedro é representado pelo grafo de 6 vértices O cubo é representado pelo grafo de 8 vértices Dodecaedro é representado pelo grafo de 12 vértices O icosaedro é representado pelo grafo de 20 vértices 52 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Um grafo plano é um grafo desenhado em uma superfície plana de tal forma que duas quaisquer de suas arestas se encontram apenas nos vértices extremidade considerando que elas se encontram Um grafo planar é um grafo que é isomorfo a um grafo plano isto é pode ser redesenhado como um grafo plano Por exemplo o grafo GVE mostrado na figura 13a é um grafo planar e o grafo da figura 13b é um grafo isomorfo ao grafo plano BOAVENTURA 2017 FIGURA 13 A GRAFO PLANAR DADO QUE SEU ISOMORFO B É PLANO Fonte Nicoletti e Hruschka Jr 2017 PraCegoVer A figura a representa um grafo com dez vértices Todos os vértices têm grau três A forma do grafo é dois pentágonos na horizontal ligados por uma aresta A figura b representa um grafo plano com forma de losango ligados por uma aresta Todos os vértices possuem grau três A fórmula de Euler é muito utilizada quando o tema á planaridade de grafos assista ao vídeo a seguir para aprender sobre ela httpsyoutube ZzyvIM1P8oY Vamos sintetizar os teoremas advindos da fórmula de Euler a seguir 53 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Fórmula de Euler Teorema 1 Seja G um grafo conectado plano e seja n o número de vértices de G e o número de arestas de G f o número de faces de G Então 2 n e f Se G é um grafo plano com n vértices e arestas f faces e k componentes conectadas então 1 n e f k Fórmula de Euler Corolário 1 do Teorema 1 Se G é um grafo plano com n vértices e arestas f faces e k componentes conectadas então 1 n e f k Fórmula de Euler Corolário 2 do Teorema 1 Sejam G1 e G2 dois grafos planos que são ambos diferentes desenhos do mesmo grafo planar G então fG1 fG2 ou seja G1 e G2 têm o mesmo número de faces Agora indicaremos alguns exemplos para facilitar o entendimento 54 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Exemplo 1 Considere o grafo G conectado da figura 14 a Esse grafo tem 11 vértices 14a arestas e 4 faces n e f 2 Considere agora o grafo G2 não conectado da figura 14 a que tem 9 vértices 11 arestas e cinco faces Tornando o grafo G2 conectado por meio do acréscimo de uma aresta como mostra a figura 14 b a fórmula de Euler passa a ser verificada FIGURA 14 A GRAFOS G1 G2 E G3 E SUAS FACES B GRAFO G2 CONECTADO a b Fonte Nicoletti e Hruschka Jr 2017 PraCegoVer A figura representa A figura representa em G1 um grafo com seis vértices com vértices de grau dois três vértices de grau três e um vértice de grau quarto faces f1 f2 f3 f4 f5 O grafo G2 com nove vértices com um laço três vértices de grau três três vértices de graus dois e faces f1 f2 f3 f4 f5 sendo o grafo de face f2 interno e não conectado aos demais vértices do grafo O grafo G3 com nove vértices com um laço quatro vértices de grau três dois vértices de graus dois e faces f1 f2 f3 f4 f5 f6 e f7 dois vértices de grau quatro A figura b representa o grafo com nove vértices e faces f1 f2 f3 f4 e f5 com um laço sendo quatro vértices de grau três um vértice de grau quatro quatro de vértices de grau dois 55 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Exemplo 2 Considere o grafo G da figura 15 Para esse grafo que tem 14 vértices 13 arestas 5 faces e 5 componentes conectados vale 14 13 5 5 1 FIGURA 15 GRAFO G COM 14 VÉRTICES 13 ARESTAS 5 FACES E 5 COMPONENTES CONEXOS Fonte Nicoletti e Hruschka Jr 2017 PraCegoVer A figura representa o grafo de um vértice sem aresta outro grafo de forma triangular com quatro vértices e quatro arestas outro vértice com forma triangular com três vértices e três arestas Outro grafo com quatro vértice e cinco arestas e por fim um grafo com dois vértices uma aresta Exemplo 3 O grafo G da figura 16 é isomorfo aos grafos planos G1 e G2 e portanto G é um grafo planar Como pode ser verificado na figura fG1 fG2 FIGURA 16 GRAFO PLANAR G E SEUS GRAFOS PLANOS ISOMORFOS G1 E G2 Fonte Nicoletti e Hruschka Jr 2017 PraCegoVer A figura representa O grafo G com quatro vértice e eis arestas sedo fechando o quadrado e as ouras duas as diagonais do quadrado O grafo G1 quatro vértices e seis arestas sendo quatros fechando um quadrado uma na diagonal e a outra passando por fora E o grafo G3 formando um tetraedro 56 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 DUALIDADE Seja G um grafo plano o dual de G é definido como o grafo G construído como segue 1 A cada face f de G existe um correspondente vértice f de G 2 A cada aresta e de G existe uma aresta correspondente e em G tal que se a aresta e ocorre na fronteira de duas faces f e g então a aresta e une os vértices correspondentes f e g em G 3 Se a aresta e for uma ponte é tratada como se ocorresse duas vezes na fronteira da face f à qual pertence e então a correspondente aresta e é um loop incidente com o vértice f em G 223 O PROBLEMA DO CAIXEIROVIAJANTE Uma das profissões mais antigas de vendedor ambulante na antiguidade era chamado de caixeiroviajante Tal profissão ainda muito difundida hoje recebe nomes diferentes como vendedor representante mercador Na teoria dos grafos problemas relacionados a vendas podem ser solucionados por meio do algoritmo desenvolvido a partir do problema do caixeiroviajante NICOLETTI 2017 Suponha um vendedor de produtos identificado como caixeiroviajante que atua em várias localidades no caso cidades algumas das quais são ligadas por estradas O trabalho do vendedor exige que ele visite cada uma das cidades A pergunta é é possível para ele planejar uma viagem de carro partindo e voltando a uma mesma cidade visitando cada uma das cidades exatamente uma vez Se tal viagem for possível é viável planejála de maneira a minimizar a distância total percorrida Esse problema é conhecido como o problema do caixeiroviajante NICOLETTI 2017 57 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Esse problema pode ser modelado como um grafo valorado G as cidades são representadas pelos vértices e duas cidades dois vértices estão conectadas por uma aresta estrada ponderada se e somente se as cidades correspondentes possuem uma estrada de ligação que não passa por nenhuma das outras cidades O valor peso da aresta representa a distância da estrada entre as cidades Para você entender o problema do caixeiroviajante é preciso antes que você aprenda o que é grafo hamiltoniano Agora que você já sabe o que é um grafo hamiltoniano vamos continuar estudando o problema do caixeiroviajante Suponha que um caixeiroviajante tenha de visitar quatro cidades n4 diferentes começando e terminando sua viagem na primeira cidade Suponha também que não importa a ordem com que as cidades são visitadas e que todas estão conectadas ou seja de cada uma delas podese ir diretamente a qualquer outra BOAVENTURA 2017O problema do caixeiroviajante consiste em descobrir a rota que torna mínima a viagem total Nesse caso n 4 a cidades serão rotuladas como A B C e D uma rota que o caixeiroviajante deve considerar poderia ser sair de A e ir para B depois para C em seguida para D e então de volta a A A primeira pergunta é quais são as outras possibilidades Note que essa resposta envolve combinatória e é relativamente fácil de responder Veja as possibilidades de rotas ABCDA ABDCA ACBDA ACDBA ADBCA ADCBA Sendo assim temos seis possíveis rotas O problema do caixeiro é um clássico exemplo de problema de otimização combinatória pois envolve a busca pelo menor caminho dentre todos os possíveis Ao resolver problemas desse tipo a primeira coisa a se fazer é reduzilo a um problema de enumeração Uma forma de fazermos isso é encontrando todas as rotas possíveis outra forma é calculando o comprimento de cada um dos caminhos e então vemos qual o menor GOLDBARG 2012 Assista ao vídeo e fique por dentro do que são grafos hamiltonianos httpsyoutubeYWQQ 7U0PzU 58 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Para encontrar o número Rn de rotas para o caso de n cidades é necessária uma combinatória simples e clássica definida por 1 R n n No entanto esse método não é muito eficaz pois a recursividade do fatorial tende a gerar valores altos Assim trataremos o problema do caixeiroviajante como um problema de complexidade exponencial Os algoritmos exatos têm limitações não as discutiremos aqui preferindo apresentar uma heurística Em um grafo completo de ordem n teremos n 1 soluções visto que as n permutações circulares de uma dada permutação possuem o mesmo valor e que as que nos interessam partem sempre de um dado vértice SZWARCFITER 2018 Antes de discutir a heurística porém há um ponto interessante a destacar Consideremos um grafo G de ordem n e o grafo completo Kn Vamos então ponderar as arestas de Kn por valores β v w da seguinte forma Se v w E G então β v w 1 Se v w E G então 2 β v w Vamos agora buscar um ciclo hamiltoniano de valor mínimo em Kn Se o valor dele for n ele será formado por n arestas associadas às arestas de G e este portanto será hamiltoniano Entretanto se o valor dele for maior do que n então ele conterá pelo menos uma aresta que não figura em G e portanto G não será hamiltoniano Portanto o problema do caixeiroviajante é equivalente ao problema da busca de um ciclo hamiltoniano em um grafo qualquer Isso significa que poderemos sempre usar um algoritmo seja exato ou heurístico para procurar uma solução para qualquer dos dois problemas Aqui aparece outra questão interessante os valores dados às arestas não podem ser arbitrários ou se poderá obter um percurso préhamiltoniano ou seja que repita algum vértice de custo menor que o de um percurso hamiltoniano Veja a figura 17 neste grafo o percurso fechado de menor custo tem valor 60 enquanto o ciclo hamiltoniano que usa a aresta de valor 100 tem valor 140 59 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 17 GRAFO PONDERADO Fonte Boaventura Netto e Jurkiewicz 2017 PraCegoVer A figura representa o grafo ponderado de cinco vértices rotulados com a b c d e e arestas valoradas O vértice A se liga ao vértice C pela aresta de valor 10 e ao vértice e pela aresta de valor 10 O vértice C se liga aos vértices A B E e D por arestas de valor 10 cada uma O vértice b se liga ao vértice d pela aresta de valor 10 O vértice d se liga ao vértice e pela aresta de valor 100 224 UMA HEURÍSTICA Uma estratégia é por meio da matriz de valores de um grafo achar um ciclo ou circuito hamiltoniano começar por um vértice que tenha a ligação de menor valor e ir escolhendo as seguintes pelo mesmo critério a chamada estratégia gulosa Entretanto essa estratégia é muito mais exceção do que regra no caso dos percursos hamiltonianos ela pode fracassar completamente prova disso é o seguinte exemplo 60 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Aplicar a estratégia gulosa na figura 18 nos leva a escolher em primeiro lugar a aresta de custo 10 Depois disso nada poderá impedir que o ciclo final tenha custo 10 30 100 30 170 verifique Não escolhendo inicialmente aquela aresta poderemos obter um ciclo formado pelas 4 arestas de custo 30 com custo total 120 FIGURA 18 EXEMPLO DE GRAFO PONDERADO Fonte Boaventura Netto e Jurkiewicz 2017 PraCegoVer A figura representa um grafo ponderado em forma de tetraedro com as arestas das bases com valores de 30 30 e 10 Uma face tem as arestas com valores 30 30 100 e a outra face com arestas de valores 30 10 e 30 O fracasso leva a outras tentativas e descoberta de técnicas melhores Como prova disso vejamos como exemplo o algoritmo conhecido como farthest insertion for traveling salesman problem FITSP ou inserção mais distante para o problema do caixeiroviajante Ele é uma heurística de inclusão ou seja uma estratégia baseada no desenvolvimento progressivo de um ciclo pela inclusão de vértices 61 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II O critério para seleção do vértice a ser inserido determina a heurística no caso do FITSP procura se o vértice mais distante do circuito já construído até o momento sendo essa distância medida a partir do vértice do circuito que esteja mais próximo ao novo vértice Escolhido assim um vértice r V procurase o par de vértices ij do circuito entre os quais ele será inserido por meio da minimização do custo cij vir vrj vij Isso equivale a substituir um arco ij por dois arcos ir e rj incluindo assim r no circuito O funcionamento da heurística em uma dada iteração pode ser representado pela figura 19 FIGURA 19 EXEMPLO DE HEURÍSTICA DE INSERÇÃO FITSP Fonte Boaventura Netto e Jurkiewicz 2017 PraCegoVer A figura representa dois grafos O primeiro grafo possui oito vértices Ele possui um ciclo vigente com quatro vértices e linha pontilhada com um vértice e três vértices isolados O outro grafo possui um novo ciclo vigente com cinco vértices e linha pontilhada e dois vértices isolados Você pode se apro fundar ainda mais nesse problema do caixeiroviajante Assista aos vídeos 1 e 2 e veja algumas soluções para o problema do caixeiroviajante httpsyoutubeDoy6cBjb8uw httpsyoutubeyI9bRgXbE1c 62 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 CONCLUSÃO Esta unidade teve como objetivo aprofundar o conhecimento acerca da teoria dos grafos Os conceitos e as aplicações aqui discutidos servem de aporte teórico e prático para a compreensão da importância da pesquisa operacional na formação profissional A teoria dos grafos é amplamente utilizada em diversas áreas do conhecimento suas definições e propriedades permitem modelar situações reais de forma a facilitar a solução de problemas Aprofundar os conhecimentos sobre teoria dos grafos permite a construção de uma base sólida clara e coerente com os objetivos da disciplina de pesquisa operacional O que estudamos até aqui serve de fonte inspiradora para que você busque cada vez mais conhecimento informação e transformação UNIDADE 3 OBJETIVO Ao final desta unidade esperamos que possa 63 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Introduzir a resolução de problemas de programação linear Apresentar técnicas de soluções de problemas de programação linear 64 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 INTRODUÇÃO À PROGRAMAÇÃO LINEAR INTRODUÇÃO DA UNIDADE A programação linear PL é uma das mais importantes ferramentas da PO e sua aplicação está cada vez mais disseminada Em um problema de programação linear a funçãoobjetivo e todas as restrições do modelo são representadas por funções lineares De forma complementar as variáveis de decisão devem ser contínuas ou seja devem obrigatoriamente assumir quaisquer valores em um intervalo real O objetivo de resolver um problema de PL consiste em maximizar ou minimizar determinada função linear sujeita a um conjunto de restrições Entre os algoritmos ou métodos de solução que podem ser aplicados para a determinação da solução ótima do modelo o método simplex é o mais conhecido e utilizado Em função da abrangência do tema a programação linear será aqui dividida em seis sessões em que iremos explorar de forma objetiva e clara os fundamentos e as aplicações da programação linear 11 PROGRAMAÇÃO LINEAR UMA TÉCNICA PODEROSA A programação linear tem sido utilizada para a otimização de problemas reais em múltiplos setores Como exemplos podemos citar os setores de comércio de serviços economia de transporte de produção entre outros A programação linear vem gerando economia de milhões ou até bilhões de dólares para as indústrias que a utilizam Portanto estudar e conhecer esta ferramenta poderosa é fundamental 65 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 1 ÁREAS DE APLICAÇÃO DA PL Fonte Pixabay 2022 PraCegoVer a imagem representa por meio de ícones o desenho de diversas áreas de aplicação da PL como economia ciência indústria logística finanças distribuição de energia água entre outras 111 CRIAÇÃO E EVOLUÇÃO HISTÓRICA O desenvolvimento da programação linear é considerado um dos mais importantes avanços científicos dos meados do século XX e a cada nova aplicação que surge essa afirmação se confirma Desde 1950 a programação linear tem impactado de forma extraordinária os modelos de tomada de decisões LACHTERMACHER 2021 Sua origem está na Segunda Guerra Mundial em que entre vários problemas enfrentados pelos países a limitação na alocação de recursos era um problema a ser resolvido A busca pela solução para o problema de alocação de recursos levou à criação do método simplex em 1947 por George B Dantzig que era um dos membros do SCOOP No entanto seu trabalho só foi largamente avaliado em 1951 LACHTERMACHER 2021 66 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Ainda que com equipamentos computacionais primitivos e com alto grau de limitação o método simplex foi a base para o desenvolvimento de métodos práticos de solução para o problema de PL entre os anos de 1948 e 1952 As quatro maiores barreiras veja a Figura 2 para solucionar problemas de PL foram enfrentados em 1952 e durante os dois ou três anos posteriores FIGURA 2 OBSTÁCULOS PARA SOLUÇÃO DE PROBLEMAS DE PL Fonte Elaborada pela autora 2022 PraCegoVer a imagem representa o desenho de quatro obstáculos o primeiro é encontrar uma solução básica inicial ponto de partida do algoritmo o segundo é resolver o problema de armazenar a situação de degeneração o terceiro é minimizar a área de memória e o número de operações aritméticas necessárias para provocar limitações de uso e o quarto é manter precisão numérica suficiente para a aquisição de resultados significativos Todas as barreiras foram aos poucos sendo derrubadas encontrar uma solução básica viável inicial era o mesmo problema que achar uma solução ótima partindo daquela Problemas de relacionados à degeneração foram vastamente discutidos em diversos trabalhos publicados na época e as dificuldades existentes foram sanadas LACHTERMACHER 2021 Quanto à minimização de operações aritméticas e espaço de memória em 1953 foi desenvolvido um modelo que foi bem aceito Em 1954 o uso da dupla precisão numérica veio a resolver o último dos obstáculos mencionados embora o uso da dupla precisão numérica aumentou o tempo de operação aritmética ele foi aceito por resolver o problema MORETIN 2018 67 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Nos anos de 1954 e 1955 foram incorporados coeficientes da função objetivo o que ampliou ainda mais o uso da PL de forma simultânea foram desenvolvidos os algoritmos de parametrização e em 1957 novos aperfeiçoamentos aconteceram como a melhora nas técnicas de inversão de matrizes a manobra de variáveis implicitamente limitadas e a introdução ao algoritmo dual Apesar de não terem sido muito utilizados na época e pelos anos seguintes atualmente eles são característicaspadrão em versões melhoradas de sistemas de programas computacionais para programação linear MORETIN 2018 Atualmente ela é considerada uma ferramenta padrão que economizou muitos milhares ou milhões de dólares para muitas empresas ou até mesmo negócios de médio porte em países industrializados por todo mundo e seu emprego em outros setores da sociedade se alastrou velozmente A maior parte de toda a computação científica realizada em computadores é dedicada ao uso da programação linear Diversos textos tratando da programação linear foram redigidos e artigos publicados descrevendo aplicações importantes agora estão disponíveis ao alcance de todos E fica a pergunta qual é a natureza dessa admirável ferramenta e a que tipos de problemas ela se destina Vamos responder a esta pergunta com a compreensão desse tema à medida que discutirmos alguns exemplos Entretanto um spoiler acerca de conceitos pode te ajudar a ter uma perspectiva O tipo mais comum de informação envolve o problema comum de alocar da melhor forma possível isto é de forma ótima recursos restritos para atividades que competem entre si Mais precisamente esse problema envolve selecionar o nível de certas atividades que competem por recursos escassos que são necessários para realizar essas mesmas atividades HILLIER 2013 A escolha do nível de atividades define então quanto de cada recurso será consumido a cada atividade A diversidade de situações para as quais essa descrição se aplica é grande modificando de fato da alocação de recursos de produção a produtos da alocação de recursos nacionais a necessidades domésticas do projeto agrícola a sessões de radioterapia e assim por diante Contudo o ingrediente mais comum em cada uma desses casos é a necessidade de alocar recursos compatíveis com estas atividades escolhendo se seu nível HILLIER 2013 68 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II A programação linear utiliza um modelo matemático para descrever o problema A palavra linear define que todas as funções matemáticas envolvidas nesse modelo são lineares A palavra programação nesse caso não se refere à programação de computador ela é essencialmente um sinônimo para planejamento Assim a programação linear envolve o planejamento de atividades para alcançar um excelente resultado entre todas as alternativas possíveis ANDRADE 2015 Apesar de a alocação de recursos para atividades ser o tipo de aplicação mais comum a programação linear possui outras aplicações importantes Dessa forma qualquer problema cujo modelo matemático se adeque ao formato genérico para o modelo de programação linear é considerado um problema de programação linear Por esse motivo um problema de programação linear e seu modelo normalmente são chamados de forma equivalente como apenas programa linear ou simplesmente PL Além disso um procedimento de solução incomparavelmente eficiente chamado método simplex é utilizado para solucionar até mesmo problemas de programação linear de grandes dimensões Essas são algumas das razões que fazem da programação linear um fenômeno desde a sua criação até hoje FIGURA 3 ILUSTRAÇÃO DO USO COMPUTACIONAL DO MÉTODO SIMPLEX Fonte Pixabay 2022 PraCegoVer a imagem representa um homem utilizando o computador para resolver problemas de programação linear pelo método simplex 69 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 112 FUNDAMENTOS SUPOSIÇÕES E TERMOS UTILIZADOS A Pesquisa Operacional PO compreende a utilização de procedimentos que auxiliam na tomada de decisão é importante para um pesquisador estudar as principais definições envolvidas nesse processo para que possa entender como a PO pode auxiliálo de forma coerente e estruturada LACHTERMACHER 2021 Assim podemos perceber que os objetivos da organização estão relacionados com a tomada de decisão de modo que sejam minimizadas as improbabilidades os riscos e a complicações inerentes ao processo e com o intuito de que seja selecionada a melhor decisão entre as diversas opções disponíveis tornandose assim imprescindível o valor e a qualidade da informação E é exatamente com foco na tomada eficaz de decisão levando em consideração as diversas interfaces e o caráter externo dos sistemas e dos mercados que a PO se insere como campo do conhecimento a fim de propiciar ao agente tomador de decisão maior embasamento e melhor conhecimento do problema em análise seja em finanças em economia em logística ou em marketing LACHTERMACHER 2021 Nesse contexto a programação linear é a uma das ferramentas que a PO utiliza com frequência nos processos de tomada de decisão A programação linear requer o uso e o conhecimento de elementos fundamentais que passaremos a conhecer a partir de agora Vamos iniciar falando sobre os três principais elementos que constituem um processo de tomada de decisão relacionados à PO são eles Variáveis de decisão e parâmetros as variáveis de decisão são as incógnitas ou valores desconhecidos que serão definidos por meio pela solução do modelo Por meio da escala de mensuração as variáveis classificamse variáveis contínuas discretas ou binárias Figura 4 As variáveis de decisão são sempre positivas Aqui você fica sabendo um pouco mais sobre os tipos de variáveis MORETIN 2018 70 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 4 TIPOS DE VARIÁVEIS DE DECISÃO Contínuas Discretas Variáveis de decisão Binárias Fonte Elaborada pela autora 2022 PraCegoVer a imagem representa um esquema com um balão no centro e com o texto variáveis de decisão ao redor estão dispostos três círculos com os textos contínuas binárias e discretas Variáveis contínuas Podem assumir quaisquer valores em um intervalo de números reais Como exemplo de variáveis de decisão contínuas temse a quantidade ótima a ser produzida em litros de cada tipo de cerveja em uma empresa de cervejaria artesanal Variáveis discretas Podem assumir valores dentro de um conjunto finito ou uma quantidade enumerável de valores sendo aquelas provenientes de determinada contagem Como exemplo de variáveis discretas temse o número ideal de funcionários por turno de trabalho 71 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Variáveis binárias Conhecidas por variáveis dummy estas podem assumir somente dois possíveis valores 1 quando a característica de interesse está presente na variável ou 0 caso contrário Como exemplo de variáveis de decisão binárias temse a decisão por fabricar ou não determinado produto Os parâmetros são os valores fixos já conhecidos do problema como por exemplo a demanda de cada produto para um problema b custo variável para produzir determinado tipo de perfume c lucro ou custo por unidade de produto produzido e d custo por contratação de mão de obra Funçãoobjetivo é uma função matemática que define o valoralvo que se deseja alcançar ou a qualidade da solução em função das variáveis de decisão e dos parâmetros podendo ser uma função que maximiza lucro receita riqueza entre outros atributos ou que minimiza custo risco entre outros MORETIN 2018 Restrições as restrições são um conjunto de equações e inequações que impõe condições que as variáveis de decisão do modelo matemático devem atender As restrições são adicionadas ao modelo com o objetivo de levar em conta as limitações físicas do sistema e afetam de forma direta os valores das variáveis de decisão MORETIN 2018 72 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Como exemplos de funções objetivos podemos citar a minimização do custo total de fabricação de diversos tipos de alimentos b minimização do risco de crédito de uma carteira de clientes c minimização do número de mão de obra envolvidas em certo serviço d maximização do retorno sobre aplicação de médio e longo prazo e e maximização do lucro líquido na produção de vários tipos de cosméticos E como exemplos de restrições a serem consideradas em um modelo matemático temos a limite máximo de produção b risco máximo de investimento ao qual o investidor está disposto a correr c número máximo de equipamentos disponíveis e d demanda mínima admissível de um produto A programação linear utiliza modelos determinísticos em que todas as variáveis envolvidas em sua formulação são constantes e conhecidas Em um problema de programação linear PL a função objetivo f e todas as restrições 1 2 ig i m que fazem parte do modelo descrito em Eq1 serão representadas por funções lineares das variáveis de decisão Uma função é dita linear quando os elementos presentes são constantes e os termos têm variáveis de primeiro grau Do contrário a função é não linear 1 1 2 1 n g x x x b 2 1 2 2 n g x x x b 1 2 m n m g x x x b 1 2 n 0 x x x restrição de não negatividade Eq 1 73 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Em que xj são as variáveis de decisão j 1 2 n fx1 x2xn é a função objetivo função das variáveis de decisão xj gix1 x2xn representa a restrição i i 1 2 m função das variáveis de decisão xj bi é o termo independente constante ou quantidade de recursos disponíveis da iésima restrição Por exemplo a funçãoobjetivo 2 3 1 2 3 3 8 2 f x x x x x x corresponde a uma função linear Analogamente a restrição 2 3 1 1 2 3 2 4 3 12 g x x x x x x também é linear Graficamente uma função linear será representada por uma reta LACHTERMACHER 2021 Os problemas de PL buscam encontrar valores ótimos para as variáveis de decisão 1 2 n x x x que precisam ser contínuas com alvo em maximizar ou minimizar a função linear z sujeita a um conjunto de m restrições lineares de igualdade eou de desigualdade ANDRADE 2015 As soluções que satisfazem todas as restrições inclusive as de não negatividade das variáveis de decisão são chamadas de soluções factíveis A solução factível que apresenta melhor valor da funçãoobjetivo é chamada de solução ótima ANDRADE 2015 A formulação de um modelo geral de programação linear pode ser representada matematicamente como 1 2 1 1 2 2 max min n n n ou z f x x x c x c x c x Sujeito a 11 1 12 2 1 1 21 1 22 2 2 2 n n n n a x a x a x b a x a x a x b 1 1 2 2 m m mn n m a x a x a x b 1 2 n 0 x x x restrição de não negatividade Eq 2 74 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Em que z é a função objetivo jx são as variáveis de decisão principais ou controláveis 1 2 j n ija é a constante ou coeficiente da iésima restrição da jésima variável 1 2 1 2 i m j n ib é o termo independente ou quantidade de recursos disponíveis da iésima restrição 1 2 i m jb é a constante ou coeficiente da jésima variável da função objetivo 1 2 j n Agora que já sabemos um pouco mais sobre os fundamentos da PL vamos começar nossa discussão sobre modelagem de problemas 113 MODELAGEM DE PROBLEMAS DE PROGRAMAÇÃO LINEAR Nesta seção vamos conhecer a formulação nas formas padrão e canônica além de operações elementares que podem alterar a formulação de problemas de programação linear Para a resolução de um problema de programação linear seja por qualquer método a formulação do modelo deve estar na forma padrão ou seja alguns requisitos devem ser atendidos são eles os termos independentes das restrições devem não negativos todas as restrições devem modeladas por equações lineares as variáveis de decisão devem ser positivas Matematicamente temos 1 2 1 1 2 2 max min n n n ou z f x x x c x c x c x 75 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Sujeito a 11 1 12 2 1 1 21 1 22 2 2 2 n n n n a x a x a x b a x a x a x b 1 1 2 2 m m mn n m a x a x a x b 0 1 2 jx j n Eq 3 O problema padrão de programação linear também pode ser escrito de forma matricial min f x c x Sujeito a 0 Ax b x Em que 11 1 1 1 1 2 1 0 0 0 n n m mn n n a a x b A x b c c c c a a x b Em um modelo de PL na forma canônica as restrições devem ser apresentadas por inequações podendo z ser uma funçãoobjetivo de maximização ou de minimização LACHTERMACHER 2021 Para um problema de maximização a forma canônica pode ser representada matematicamente como 1 2 1 1 2 2 max n n n z f x x x c x c x c x Sujeito a 11 1 12 2 1 1 21 1 22 2 2 2 n n n n a x a x a x b a x a x a x b 1 1 2 2 m m mn n m a x a x a x b 76 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 0 1 2 jx j n Eq 4 E para um problema de minimização a forma canônica passa a ser 1 2 1 1 2 2 min n n n z f x x x c x c x c x Sujeito a 11 1 12 2 1 1 21 1 22 2 2 2 n n n n a x a x a x b a x a x a x b 1 1 2 2 m m mn n m a x a x a x b 0 1 2 jx j n Eq 5 Para que um problema de programação linear exiba uma das formas mostradas acima algumas operações elementares podem ser realizadas da formulação geral e é o que veremos agora Problema padrão de maximização Um problema padrão de maximização pode ser transformado em um problema de minimização de programação linear 1 2 1 2 max min n n z f x x x z f x x x Eq 6 Analogamente um problema de minimização pode ser transformado em outro de maximização 1 2 1 2 min max n n z f x x x z f x x x Eq 7 Restrição de desigualdade Uma restrição de desigualdade do tipo pode ser transformada em outra do tipo por meio da multiplicação de ambos os lados por 1 1 1 2 2 i i in n a x a x a x éequivalentea 1 1 2 2 i i in n i a x a x a x b Eq 8 Analogamente uma restrição de desigualdade do tipo pode ser transformada em outra do tipo 1 1 2 2 1 1 2 2 i i in n i i i in n i a x a x a x b éequivalentea a x a x a x b Eq 9 77 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Restrição de igualdade Uma restrição de igualdade pode ser transformada em duas restrições de desigualdade 1 1 2 2 i i in n i a x a x a x b éequivalentea 1 1 2 2 1 1 2 2 i i in n i i i in n i a x a x a x b a x a x a x b Eq 10 Restrição de desigualdade do tipo Uma restrição de desigualdade do tipo pode ser reescrita por meio de uma equação de igualdade considerando a adição de uma nova variável não negativa do lado esquerdo LHS Left Hand Side 0 kx chamada de variável de folga 1 1 2 2 i i in n i a x a x a x b éequivalentea 1 1 2 2 i i in n k i a x a x a x x b Eq 11 Analogamente a restrição de desigualdade do tipo também pode ser transformada em uma equação de igualdade por meio da subtração de uma nova variável não negativa do lado esquerdo 0 kx chamada de variável de excesso 1 1 2 2 i i in n i a x a x a x b éequivalentea 1 1 2 2 i i in n k i a x a x a x x b Eq 12 Variável jx Uma variável jx que não tem restrição de sinal chamada de variável livre pode ser expressa como a diferença de duas variáveis não negativas 1 2 1 2 0 j j j j j x x x x x Eq 13 78 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Para o problema de programação linear a seguir reescrevao na forma padrão a partir de uma funçãoobjetivo de minimização 1 2 3 4 1 2 3 4 max 5 2 4 z f x x x x x x x x Sujeito a 1 2 4 2 12 x x x 1 2 3 2 3 6 x x x 1 2 3 4 x livre x x x 0 Solução para que o modelo possa ser reescrito na forma padrão as restrições de desigualdade devem ser expressas na forma de igualdade Eq 11 e 12 e a variável livre x1 pode ser expressa como a diferença de duas variáveis não negativas Considerando uma funçãoobjetivo de minimização temse que 1 2 1 2 3 4 1 1 2 3 4 max 5 5 2 4 z f x x x x x x x x x 1 2 1 1 2 4 5 2 12 x x x x x 1 2 1 1 2 3 6 2 2 3 6 x x x x x 1 2 1 1 2 3 4 5 6 0 x x x x x x x 79 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Em PL a funçãoobjetivo e as restrições devem satisfazer as seguintes hipóteses Proporcionalidade Nesta hipótese cada variável de decisão presente no modelo a sua contribuição em relação à funçãoobjetivo e às restrições do modelo são diretamente proporcionais ao valor da variável de decisão Aditividade Esta hipótese de aditividade diz que o valor total da funçãoobjetivo ou de cada função de restrição de um modelo de programação linear é expresso pela adição das contribuições individuais de cada variável de decisão Assim a contribuição de cada variável de decisão não depende da contribuição das outras variáveis isso exclui o surgimento de termos cruzados tanto na funçãoobjetivo quanto nas restrições do modelo Divisibilidade e não negatividade Cada uma das variáveis de decisão presentes no modelo pode assumir quaisquer valores positivos dentro de um intervalo real desde que as restrições do modelo sejam respeitadas Certeza Essa hipótese afirma que os coeficientes da funçãoobjetivo os coeficientes das restrições e os termos independentes de um modelo de programação linear são determinísticos constantes e conhecidos com certeza 80 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 5 HIPÓTESES DO MODELO DE PROGRAMAÇÃO LINEAR Proporcionalidade Divisibilidade Hipóteses do modelo de PL Aditividade Certeza Fonte Elaborada pela autora 2022 PraCegoVer a imagem representa um esquema com um balão no centro com o texto modelo de programação linear ao redor estão dispostos quatro círculos com os textos proporcionalidade divisibilidade aditividade e certeza 12 SOLUÇÃO GRÁFICA Nesta seção vamos introduzir a resolução de problemas de programação linear e você vai começar sua experiência pela resolução gráfica que tem a finalidade de explorar as possíveis soluções nesse tipo de problema Em seguida serão abordados os métodos analítico e tabular que servirão para mostrar como efetivamente podemos implementar em computador pelo método simplex a resolução de programação linear 81 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 121 SOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR A solução de um problema de programação linear PL pode ocorrer de várias maneiras aqui vamos discutir sobre a solução pela forma gráfica a solução analítica e pelo método Simplex HILLIER2013 Um problema de programação linear envolvendo duas variáveis de decisão é facilmente resolvido de forma gráfica Problemas com até três variáveis de decisão são solucionados de forma gráfica contudo são de maior complexidade ANDRADE 2015 Na resolução gráfica de um modelo de programação linear seguese os seguintes passos FIGURA 6 ETAPAS DA SOLUÇÃO GRÁFICA DE UM MODELO DE PROGRAMAÇÃO LINEAR 1º passo Inicialmente é determinado o espaço de soluções viáveis ou região factível em um eixo cartesiano LACHTERMACHER 2021 2º passo Constituise em encontrar a solução ótima do modelo ou seja a solução factível que tenha o melhor valor da funçãoobjetivo LACHTERMACHER 2021 Fonte Elaborada pela autora 2022 PraCegoVer a imagem representa um processo com dois passos No primeiro passo temse o texto Inicialmente é determinado o espaço de soluções viáveis ou região factível em um eixo cartesiano LACHTERMACHER 2021 E no segundo passo temse o texto Constituise em encontrar a solução ótima do modelo ou seja a solução factível que tenha o melhor valor da função objetivo LACHTERMACHER 2021 82 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II O conjunto de soluções factíveis de um problema de programação linear é representado por K Daí surge o primeiro teorema Teorema O conjunto K é convexo Um conjunto K é convexo quando todos os segmentos de reta que unem dois pontos quaisquer de K estão contidos em K Um conjunto convexo é fechado se ele compreende a sua fronteira FÁVERO 2012 n p Para PL em que m n o primeiro passo é escolher um conjunto de variáveis n m de x denominadas variáveis não básicas VNB as quais são atribuídos valores nulos As m variáveis restantes do sistema chamadas variáveis básicas VB são então determinadas Essa solução é chamada solução básica SB O conjunto de variáveis básicas é chamado base FÁVERO 2012 Se a solução básica atende às restrições de não negatividade isto é as variáveis básicas são não negativas ela é chamada solução básica factível SBF Uma VB também pode ser definida como aquela que apresenta coeficiente 1 em apenas uma equação e 0 nas demais Todas as variáveis restantes são VNB A solução ótima é obtida calculando o valor da funçãoobjetivo z e selecionar a melhor solução O número máximo de SB a serem calculadas é n m n n C m m n m Eq 13 Dessa forma o método analítico aplicado avalia todas as possíveis combinações de n variáveis escolhidas m a m escolhendo a melhor delas Utilizar o método de solução por sistemas é viável em casos em que m e n são pequenos caso contrário o cálculo tornase impraticável FÁVERO 2012 A melhor forma de compreender é por meio de um problema então assista ao vídeo e veja como fazer uma solução gráfica https youtube29q6FcbTWeU 83 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 A solução gráfica e analítica é mais viável para a resolução de problemas de programação linear com duas ou no máximo três variáveis de decisão maior complexidade O método simplex é uma opção interessante que pode ser aplicado para a resolução de qualquer problema de PL O algoritmo simplex é um método iterativo que parte de uma solução inicial considerada como básica factível e que procura a cada iteração uma nova solução básica factível SBF denominada solução básica factível adjacente que possui o melhor valor na funçãoobjetivo até que o valor ótimo seja atingido Vejamos conceito de SBF adjacente a seguir A partir de uma solução básica atual uma variável não básica entra na base no lugar de outra variável básica que passa a ser não básica gerando uma nova solução chamada solução básica adjacente Para um problema com m variáveis básicas e n m variáveis não básicas duas soluções básicas são adjacentes se elas tiverem em comum 1 m variáveis básicas podendo elas apresentar valores numéricos diferentes Isso implica também que 1 n m variáveis não básicas sejam comuns FÁVERO 2012 n p Se a solução básica adjacente atende às restrições de não negatividade ela é chamada solução básica factível adjacente SBF adjacente A descrição geral do algoritmo simplex é apresentada na Figura 7 A solução de PL é muito interessante e de extrema relevância assista ao vídeo a seguir e fique por dentro de todos os detalhes https youtube4AbjF8Lehe8 84 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 7 FLUXOGRAMA DO ALGORITMO DO MÉTODO SIMPLEX Fonte Elaborado pela autora 2022 PraCegoVer a imagem representa um fluxograma com símbolo de retângulo com as bordas arredondada indicando início do processo forma padrão seta para retângulo que indica o processo Encontrar uma solução básica factível seta para losango que é um símbolo de decisão seta para retângulo com as bordas arredondada fim do processo se a solução é ótima e seta indicando o retângulo de passo de processo alternativo determinar uma solução básica factível adjacente melhor que retorna ao retângulo que indica o processo Encontrar uma solução básica factível O processo se repete até que a solução seja determinada 122 CRIAÇÃO E SOLUÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR NO COMPUTADOR Até aqui nosso foco foi com o embasamento teórico necessário para a resolução do problema e sua análise A partir de agora mostraremos como evitar todos os cálculos Concentraremos nossa atenção no que esperamos ser a tarefa de um gerente isto é vamos nos concentrar na modelagem de problemas e na análise de suas respostas Existem muitos softwares disponíveis no mercado que podem nos ajudar na tarefa dos cálculos FÁVERO 2012 Atualmente 85 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 existem diversos softwares no mercado para solução de problemas de programação linear incluindo GAMS AMPL AIMMS softwares de planilhas eletrônicas Solver do Excel Whats Best entre outros MORETIN 2018 Agora vamos resolver um problema real por meio da ferramenta Solver e para facilitar o entendimento o processo de modelagem consiste em responder a quatro perguntas gerais na seguinte sequência a quem decide b o que decide c para que decide e d com que restrições FÁVERO 2012 Vejamos a seguir uma situação hipotética que envolver decisões do tipo fazer ou comprar Caso VEG Motores Ltda a VEG Motores Ltda uma fábrica de motores para caminhões recebeu um pedido de R 90000000 em que seus três tipos de motores são itens relacionados Cada motor precisa de certa quantidade de horas de trabalho no setor de montagem e de acabamento Uma estratégia da VEG é terceirizar parte da sua produção A Tabela 1 resume esses dados A empresa pretende determinar a quantidade de motores que ela deve produzir e a quantidade que devem ser produzidos de maneira terceirizada para atender à demanda do pedido TABELA 1 VEG MOTORES LTDA Modelo 1 2 3 Total Demanda 3000 unid 2500 unid 500 unid 6000 unid Montagem 1 hunid 2 hunid 05 hunid 6000 h Acabamento 25 hunid 1 hunid 4 hunid 10000 h Custo de Produção R 5000 R 9000 R 12000 Terceirizado R 6500 R 9200 R 14000 Fonte Adaptada de Lachtermacher 2016 n p PraCegoVer a imagem representa uma tabela com cinco colunas seis linhas Da primeira à sexta coluna os textos aparecem na seguinte ordem Modelo 1 2 3 Total Na Linha dois da primeira à quinta coluna os textos aparecem na seguinte ordem Demanda 3000 unid 2500 unid 500 unid 6000 unid Na Linha três da primeira à quinta coluna os textos aparecem na seguinte ordem Montagem 31 hunid 2 hunid 05 hunid 6000 h Na Linha quatro da primeira à quinta coluna os textos aparecem na seguinte ordem Acabamento 25 hunid 1 hunid 4 hunid 10000 h Na Linha cinco da primeira à quinta coluna os textos aparecem na seguinte ordem Custo de Produção R 5000 R9000 R12000 em branco Na Linha seis da primeira à quinta coluna os textos aparecem na seguinte ordem Terceirizado R 6500 R9200 R14000 em branco 86 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Quem decide O tomador de decisão é o administrador de produção da fábrica O que decide A quantidade de motores de cada tipo que devem ser fabricados e quantos devem ter sua produção terceirizada Logo as variáveis de decisão são F1 Número de motores do modelo 1 fabricados pela VEG F2 Número de motores do modelo 2 fabricados pela VEG F3 Número de motores do modelo 3 fabricados pela VEG T1 Número de motores do modelo 1 terceirizados T2 Número de motores do modelo 2 terceirizados T3 Número de motores do modelo 3 terceirizados Para que decide Para maximizar os lucros da VEG Motores isto é receitas despesas representados pela equação abaixo 1 2 3 1 2 3 900000 50 90 1 20 65 92 1 40 Max F F F T T T Vale ressaltar que como a receita é constante R 90000000 maximizar essa equação é rigorosamente igual a minimizar os custos entre parênteses Logo uma funçãoobjetivo mais simples seria dada por 1 2 3 1 2 3 50 90 1 20 65 92 1 40 Min F F F T T T Com que restrições As restrições estão relacionadas com os recursos da empresa Nesse caso as restrições que se impõem ao problema são Restrição de montagem 1 2 3 1 2 05 6000 F F F Restrição de acabamento 1 2 3 25 1 4 1 0000 F F F Restrições de demanda 1 1 F 3000 T motor do tipo 1 2 2 F 2500 T motor do tipo 2 3 3 F 500 T motor do tipo 3 87 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 O modelo O nosso caso pode ser resumido pelo seguinte modelo matemático 1 2 3 1 2 3 50 90 1 20 65 92 1 40 Min F F F T T T sr 1 2 3 1 2 05 6000 F F F 1 2 3 25 1 4 1 0000 F F F 1 1 2 2 3000 2500 F T F T 3 3 F 500 T 1 2 3 1 2 3 0 F F F T T T Agora vamos para a solução no Excel A Figura 8 representa a organização utilizada na modelagem do caso Agora devemos colocar as fórmulas que representam os VEG das cinco restrições A Tabela 2 a seguir apresenta as fórmulas necessárias TABELA 2 FÓRMULAS REFERENTES AO LHS DAS RESTRIÇÕES Restrição Célula Fórmulas LHS das restrições F1 T1 3000 B5 B3B4 F2 T2 2500 C5 C3C4 F3 T3 500 D5 D3D4 F1 2F2 05F3 6000 E13 SOMARPRODUTOB13D13B3D3 25F1 F2 4F3 10000 E14 SOMARPRODUTOB14D14B3D3 Fonte Adaptada de Lachtermacher 2016 n p PraCegoVer a imagem representa uma tabela com três colunas seis linhas Da primeira à terceira coluna os textos aparecem na seguinte ordem Restrição Célula Fórmulas LHS das restrições Na Linha dois da primeira à terceira coluna os textos aparecem na seguinte ordem F1 T1 3000 B5 B3B4 Na Linha três da primeira à terceira coluna os textos aparecem na seguinte ordem F2 T2 2500 C5 C3C4 Na Linha quatro da primeira à terceira coluna os textos aparecem na seguinte ordem F3 T3 500 D5 D3D4 Na Linha cinco da primeira à terceira coluna os textos aparecem na seguinte ordem F1 2F2 05F3 6000 E13 SOMARPRODUTO B13D13B3D3 Na Linha seis da primeira à terceira coluna os textos aparecem na seguinte ordem 25F1 F2 4F3 10000 E14 SOMARPRODUTO B14D14B3D3 Vale notar que nas fórmulas das células E13 e E14 aparecem nas expressões que representam F1 F2 e F3 Esses símbolos indicam que as células são fixas na simbologia utilizada pelo Excel 88 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II O último passo a ser seguido é a definição do modelo na ferramenta Solver do Excel A janela de parâmetros deve ser preenchida como apresentado na Figura 9 e o modelo deve ser otimizado clicando no botão Resolver na mesma janela FIGURA 8 INTERFACE DO SOLVER NO EXCEL Fonte Adaptada de Lachtermacher 2016 n p PraCegoVer a imagem representa a interface do solver no Excel para inserção das informações sobre o problema a ser resolvido Inicialmente devemos indicar a célula onde se encontra a função objetivo Logo abaixo tem botões de opções para escolha dispostos horizontalmente que aparecem na ordem maximização minimização valor para e um espaço para preenchimento de valores Logo abaixo tem o espaço para alteração das variáveis Em seguida vem a janela para inserção das restrições com botões de escolha à esquerda com os textos na ordem de cima para baixo adicionar alterar excluir redefinir tudo e carregar ou salvar Selecione a caixa de checklist caso queira incluir as variáveis Em seguida um menu suspenso para selecionar um método de soluções com textos na ordem GRG não linear LP não linear e Evolutionary À direita do menu suspenso tem o botão de opções E na parte inferior a esquerda a opção ajuda no meio resolver e à direita fechar Parâmetros do caso VEG Motores inseridos no Solver a planilha receberá as respostas do modelo automaticamente A Figura 9 mostra os resultados obtidos 89 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 9 RESULTADOS DO MODELO LCL MOTORES Fonte Elaborada pela autora 2022 PraCegoVer a imagem representa a planilha no Excel Na Linha 1 A1 texto VEG Motores B1 Motores Motores e Motores Na linha 2 da coluna A até D os textos na ordem Tipo 1 2 e 3 Na linha 3 da coluna A até D os textos na ordem Fabricado 3000 500 e 500 Na linha 4 da coluna A até D os textos na ordem Terceirizado 0 2000 e 0 Na linha 5 da coluna A até D os textos na ordem Total por tipo 3000 2500 e 500 Na linha 6 da coluna A até D os textos na ordem Demanda 3000 2500 e 500 Na linha 8 da coluna A até D os textos na ordem Custos Reaisunidades Reaisunidades e Reaisunidades Na linha 9da coluna A até D os textos na ordem Fabricado 50 90 e 120 Na linha 10 da coluna A até D os textos na ordem Terceirizado 65 92 e 140 Na linha 12 da coluna A até F os textos na ordem Horas Horasunidades Horasunidades Horasunidades usadas e disponíveis Na linha 13 da coluna A até F os textos na ordem Montagem 1 2 05 4250 e 6000 Na linha 14 da coluna A até F os textos na ordem Acabamento 25 1 4 10000 e 10000 Na linha 16 da coluna A até b os textos na ordem Custo Total 439000 Retângulo laranja entorno da linha 16 nas colunas a e B com seta vermelha indicando Função Objetivo e Retângulo verde entorno das linhas 3 e 4 nas colunas de A a D com seta verde indicando Variáveis de Decisão 123 ANÁLISE DE SENSIBILIDADE A análise de sensibilidade investiga os efeitos que determinadas alterações nos parâmetros do modelo causariam na solução ótima sendo portanto fundamental no estudo de problemas de programação linear Pode ser empregada em dois casos distintos análise de sensibilidade e análise pósotimização LACHTERMACHER 2021 90 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 10 ILUSTRAÇÃO DO RESULTADA DA ANÁLISE DE SENSIBILIDADE Fonte Pixabay 2022 PraCegoVer a imagem representa o desenho de um gráfico de barras com um gráfico de linhas sobre ele e no fundo há uma tabela de valores dando um efeito de plano de fundo No primeiro caso chamado simplesmente de análise de sensibilidade estuda se a variação que os coeficientes da funçãoobjetivo e as constantes presentes no membro direito de cada restrição permanecendo inalterada a solução ótima do modelo inicial ou a região de factibilidade Dessa forma fica excluída a necessidade de recalcular a nova solução ótima do modelo após alterações em seus parâmetros Esse caso pode ser analisado graficamente utilizando cálculos algébricos ou diretamente pelo Solver do Excel considerando uma alteração por vez Na análise a partir de alterações nos termos independentes das restrições o objetivo é determinar os limites inferiores e superiores que os termos independentes das restrições podem assumir sem alterar a região de factibilidade que mantém os preços sombra constantes O preçosombra shadow price pode ser definido como o acréscimo ou decréscimo no valor da função objetivo caso seja adicionada ou retirada uma unidade na quantidade atual de recursos disponíveis da iésima restrição O preço sombra pode ser interpretado como o preço justo a ser pago pela utilização de uma unidade do recurso i ou o custo de oportunidade de recursos pela perda de uma unidade do recurso i LACHTERMACHER 2021 p 124 O segundo caso conhecido como análise pósotimização é empregado quando após mudanças nos parâmetros do modelo a solução ótima 91 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 do modelo é afetada a solução passa a ser subótima ou infactível sendo necessário recalcular a nova solução ótima do modelo Essa análise é efetuada a partir da forma tabular do método simplex ou de forma gráfica para problemas com até duas variáveis podendo considerar mais de uma alteração simultaneamente Apesar da necessidade do cálculo de uma nova solução ótima partese da solução ótima do modelo preliminar que está mais próxima da ótima do modelo atual de forma que o tempo computacional empregado no cálculo da nova solução pode ser reduzido substancialmente LACHTERMACHER 2021 Veja como funciona a análise de sensibilidade na prática por meio de um exercício clicando neste link httpsyoutubeCt3BLwDyQBE CONCLUSÃO Esta unidade teve como objetivo introduzir a programação linear Os conceitos e aplicações aqui discutidos servem de aporte teórico e prático para a compreensão da importância da Pesquisa Operacional na formação profissional A programação linear é uma ferramenta poderosa e vastamente utilizada em diversas situações que envolvem a Pesquisa Operacional A programação linear pode ter inúmeras aplicações importantes De fato qualquer problema cujo modelo matemático se encaixe no formato bem genérico para o modelo de programação linear é um problema de programação linear Além disso o procedimento de solução extraordinariamente eficiente chamado método simplex serve para solucionar até mesmo problemas de programação linear de grandes dimensões Essas são algumas das razões para o grande impacto da programação linear em décadas recentes UNIDADE 4 OBJETIVO Ao final desta unidade esperamos que possa 92 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Associar problemas de fluxo de rede às situações reais Exemplificar fluxo de redes por meio de problemas que envolvem soluções reais 93 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 PROBLEMAS ESPECIAIS EM REDES INTRODUÇÃO DA UNIDADE Nesta unidade iremos abordar problemas especiais de programação linear conhecidos como problemas em rede Situações reais podem ser modeladas como problemas de rede o que torna sua compreensão e aplicação mais fácil em especial na área de gestão e produção Os problemas de programação linear na maioria das vezes utilizam os modelos de rede especiais tendo em vista que os problemas são melhores por meio da representação gráfica Problemas de otimização como por exemplo de distribuição logística e de energia produção e outros podem ser resolvidos de forma mais satisfatória e rápida quando modelados como problemas de rede Modelos de rede facilitam a visualização das relações entre os componentes do sistema proporcionando uma visão clara e uma melhor compreensão do problema e das possibilidades de resultados Diversos problemas de tomada de decisão no mundo real estão categorizados como problemas de rede Nesta unidade daremos ênfase aos problemas fluxo máximo caminho mínimo transporte transbordo e atribuição em que por meio de mídias integradas dicas de pesquisa e exemplos você irá ter conhecimento deste universo de redes 11 FLUXO DE REDES Inúmeros modelos de programação linear possuem uma estrutura especial que permite o desenvolvimento de algoritmos eficientes baseados na especificação do método simplex em sua solução De modo geral os chamados modelos em redes permitem a solução de importantes problemas reais e são de extraordinária aplicação prática 94 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 111 INTRODUÇÃO Os grafos são estruturas utilizadas para modelar os problemas de fluxo pois por meio de sua estrutura os vértices e as arestas representam os pontos de oferta e demanda em um processo de otimização de distribuição de produtos por exemplo A maiorias dos problemas de fluxo são aplicados em casos de sistemas de distribuição de pluvial elétrico telefonia transporte entre outros FÁVERO 2012 Nas relações de interdependência entre os elementos podese ter restrições que devem ser consideradas como a capacidade de tráfego e os custos variados por exemplo Muitas vezes as conexões entre os vértices de um grafo estão associadas a uma variável numérica denominada fluxo que representa uma característica mensurável dessa conexão que pode ser a distância entre os vértices o custo de transporte o tempo gasto o tamanho do fio o montante de produtos transportados entre outras De maneira análoga os vértices de um grafo podem estar associados a uma variável numérica chamada capacidade podendo representar a capacidade de carga e descarga suprimentos demanda entre outras FÁVERO 2012 Um grafo cujos arcos eou nós estão associados à variável numérica fluxo e ou capacidade é chamado de rede A Figura 1 mostra um exemplo de redes Os nós representam as cidades e os fluxos representam as distâncias km entre elas Definese uma rede R V E F como um grafo direcionado G V E atravessado por um fluxo 1 2 m F f f f que circula em suas m arestas usualmente denominadas de arcos Em uma rede normalmente existem três tipos de vértices os vértices fonte sumidouros e vértices de passagem Um vértice fonte permite que o fluxo entre na rede Um vértice sumidouro permite que o fluxo deixe a rede Um vértice de passagem permite que o fluxo circule na rede 95 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 1 EXEMPLO DE REDE NÃO DIRECIONADA Fonte Fávero 2012 p 267 PraCegoVer a imagem representa o desenho de um exemplo de uma rede não direcionada é mostrado o mapa do Brasil As cidades de Manaus Natal Salvador Brasília e Porto Alegre são consideradas vértices A aresta que liga Manaus a Natal tem comprimento de 5985km a aresta que liga Natal a Salvador mede 1126km a aresta que liga Natal a Brasília mede 2422km a aresta que liga Manaus a Brasília mede 3490km a aresta que liga Manaus a Porto Alegre mede 4563km a aresta que liga Brasília a Porto Alegre mede 2027km a aresta que liga Brasília a Salvador mede 1446km a aresta que liga Salvador a Porto Alegre mede 3090km A título de simplificação não faremos mais a distinção entre os termos grafo e rede e vamos utilizar apenas a notação rede Os nós de uma rede podem ser subdivididos em três tipos a nós de oferta ou fontes que representam entidades que produzem ou distribuem determinado produto b nós de demanda que representam entidades que consumem o produto c nós de transbordo que são os pontos intermediários entre os nós de oferta e demanda e representam os pontos de passagem desses produtos Os arcos podem ter uma seta indicando a direção do arco Quando o fluxo entre os respectivos nós ocorre em uma única direção indicada por uma seta temse um arco direcionado Quando o fluxo ocorre em ambas as direções ele é chamado arco não direcionado Em casos em que há uma única conexão entre os nós porém sem a seta indicando a direção do arco presumese que o arco é não direcionado FÁVERO 2012 p 269 96 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 A Figura 2 mostra uma rede direcionada em que os vértices representam modalidade de exercícios físicos com seus respectivos tempo de duração minutos e as arestas direcionadas representam as relações de precessão entre as atividades FIGURA 2 EXEMPLO DE REDE DIRECIONADA Fonte Fávero 2012 p 269 PraCegoVer a figura representa o desenho de uma rede direcionada com os vértices A 10 Alongamento B 35 Corrida C 40 Natação D 25 Hidroginástica E 15 Ioga Do vértice A saem duas arestas uma para o vértice B Corrida e outra para o vértice Cnatação e chega uma aresta do vértice E Ioga No vértice B Corrida de valor 35 sai uma aresta para o vértice C e uma para o vértice D Hidroginástica No vértice C sai uma aresta para o vértice D e outra para o vértice E O vértice D sai uma aresta para o vértice E e no vértice E sai uma aresta para A 112 CAMINHO MÍNIMO O problema do caminho mais curto também conhecido como problema do caminho mínimo tem como finalidade determinar o menor caminho entre dois vértices de uma rede Uma alternativa é minimizar o custo total ou o tempo total de viagem em vez de minimizar a distância total percorrida MORETIN 2013 O problema considera apenas um nó de oferta que corresponde ao ponto de origem da rede e apenas um nó de demanda que corresponde ao ponto de destino da rede A capacidade de fornecimento do nó de oferta e a demanda do nó de destino da rede correspondem a uma unidade Já todos os outros nós intermediários ou de transbordo terão oferta e demanda iguais a zero Temse novamente um modelo em que as variáveis de decisão são binárias recaindo em outro problema de programação binária FÁVERO 2012 p352 O problema do caminho mais curto pode ser eficientemente resolvido pelo algoritmo de Dijkstra 97 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Início conjunto de nós rotulados R 0 Conjunto de nós não rotulados 1 2 NR n Passo 1 atribua valor 0 ao nó fonte e aos demais nós Passo 2 enquanto o conjunto de nós não rotulados for não vazio NR Ø faça o seguinte selecione o nó ainda não rotulado com menor valor nó k passe o nó k para o conjunto de nós rotulados para todo nó j ainda não rotulado que seja sucessor de k some o valor do nó k com o custo do arco que une os nós k e j e atribua esse novo valor ao nó j em caso de melhoria Nesse caso definese o nó k como precedente de j só se houver melhoria FÁVERO 2012 Em resumo nos problemas de menor caminho haverá sempre dois tipos de nós especiais chamados de origem e destino Entre um nó de origem e um nó de destino geralmente existem nós intermediários que podem representar cidades que conectam rodovias subestações com problemas de distribuição de energia e assim por diante Vejamos uma aplicação 98 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 1 Problema Uma fábrica de artigos de decoração deve entregar grande quantidade de peças no mesmo estado A empresa quer saber qual rota seu caminhão de entregas deve fazer para minimizar a distância total percorrida A origem é Lambari e o destino Baependi Figura 3 Ambiente decorado com móveis da fábrica Fonte Pixabay 2022 PraCegoVer a figura representa a foto de um ambiente decorado mostrando objetos de decoração como cadeias acolchoadas mesa de centro folhagens telas de pinturas e vasos decorativos 99 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 2 Mapas A Figura 3a mostra o mapa rodoviário da região do estado em que se situam as duas cidades e a Figura 3b mostra o mapa esquemático e as distâncias entre as cidades na forma de rede FIGURA 3 A MAPA RODOVIÁRIO QUE LIGA AS CIDADES DE LAMBARI A BAEPENDI B REPRESENTAÇÃO EM REDE DO PROBLEMA a b Fonte Lachtermacher 2016 p 167 PraCegoVer a figura representa dois desenhos o da esquerda representa o desenho do mapa rodoviário da região onde se localizam as cidades de origem Lambari e destino Baependi As cidades próximas são Campanha Três Corações São Thomé das Letras Cruzilia Airuoca Alagoa Caxambu e São Lourenço A figura da direita representa o desenho da rede do problema com as cidades que têm estrada de ligação entre a origem e o destino Os vértices são as cidades de Lambari 1 Três Corações 2 São Thomé das Letras 4 Caxambu 5 São Lourenço 3 e Baependi 6 A distância entre Lambari e Três Corações é de 41km entre Lambari e São Lourenço é de 44km entre Lambari e Caxambu é de 50km entre Três Corações e São Thomé das Letras é de 37km entre São Thomé das Letras e Baependi é de 45 km entre Caxambu e Baependi é de 4km entre São Lourenço e Caxambu é de 27km entre Caxambu e Baependi é de 4km 100 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 3 Variáveis de decisão São os possíveis caminhos que ligam a origem ao destino x12 trecho Lambari 1 Três Corações 2 x13 trecho Lambari 1 São Lourenço 3 x15 trecho Lambari 1 Caxambu 5 x24 trecho Três Corações 2 São Thomé das Letras 4 x35 trecho São Lourenço 3 Caxambu 5 x46 trecho São Thomé das Letras 4 Baependi 6 x56 trecho Caxambu 5 Baependi 6 FIGURA 4 VARIÁVEIS DE DECISÃO REPRESENTADAS POR LIGAÇÕES DA REDE Fonte Elaborada pela autora 2022 PraCegoVer a figura representa as variáveis de decisão indicadas pelos vértices e arestas O vértice 1 ligado ao vértice 2 indica o trecho Lambari Três Corações O vértice 1 ligado ao vértice 3 indica o trecho Lambari São Lourenço O vértice 1 ligado ao vértice 5 indica o trecho Lambari Caxambu O vértice 2 ligado ao vértice 4 indica o trecho Três Corações São Thomé das Letras O vértice 3 ligado ao vértice 5 indica o trecho São Lourenço Caxambu O vértice 4 ligado ao vértice 6 indica o trecho São Thomé das Letras Baependi O vértice 5 ligado ao vértice 6 indica o trecho Caxambu Baependi 101 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 4 Funçãoobjetivo Visa a minimizar a distância percorrida pelo caminhão Logo se as variáveis de decisão assumem zero ou um a multiplicação destas pelas distâncias entre as respectivas cidades será zero caso a estrada não seja utilizada é igual à distância entre as cidades se ela for utilizada Portanto o somatório desses produtos será a distância percorrida 12 13 15 24 35 46 56 min 41 44 50 37 27 45 4 Z x x x x x x x FIGURA 5 ESQUEMA DO PROCESSO DE FLUXO MÍNIMO Fonte Elaborada pela autora 2022 PraCegoVer a figura representa um esquema ilustrativo de como a funçãoobjetivo atua no processo de busca pelo fluxo máximo A funçãoobjetivo deve minimizar a função Z que é a soma dos produtos 41x12 somado a 44x13 somado a 50x15 somado a 37x24 somado a 27x35 somado a 45x46 somado a 4x56 fechando o percurso de Lambari à Baependi 102 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 5 Resolvendo no solver Fórmulas utilizadas nas restrições do problema FIGURA 6 SOLUÇÃO ÓTIMA PARA O PROBLEMA Fonte Elaborada pela autora 2022 PraCegoVer a figura representa a planilha do Solver no Excel A coluna B corresponde à origem e da linha 4 à linha 10 os valores são 1 1 1 2 3 4 5 A coluna C corresponde ao destino e da linha 4 à linha 10 os valores são 2 3 5 4 5 6 6 A coluna D corresponde à distância em quilômetro e da linha 4 à linha 10 os valores são 41 44 50 37 27 45 4 A coluna E corresponde à rota selecionada e da linha 4 à linha 10 os valores são 0 0 1 0 0 0 1 A coluna G corresponde ao nó e da linha 4 à linha 9 os valores são 1 2 3 4 5 6 A coluna H corresponde ao Fluxo Líquido e da linha 4 à linha 9 os valores são 1 0 0 0 0 1 Na linha 12 é apresentada a distância total com valor de 54 km 103 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 6 Conclusão O caminho que resulta a menor distância entre as cidades de Lambari e Baependi é o que passa pelo município de Caxambu Logo o caminhão de entregas deve sair de Lambari seguir a estrada que leva até Caxambu x15 1 e de lá partir para Baependi x56 1 percorrendo uma distância total de 54 quilômetros 50 km de Lambari a Caxambu e mais 4 km de Caxambu a Baependi FIGURA 7 MENOR CAMINHO ENTRE FORNECEDOR E CONSUMIDOR Fonte Elaboradora pela autora 2022 PraCegoVer a figura representa o percurso a ser realizado para que haja custo mínimo O caminhão de entregas deve sair de Lambari no vértice 1 seguir a estrada que leva até Caxambu no vértice 5 e de lá partir para Baependi no vértice 6 percorrendo uma distância total de 54 quilômetros 50 km de Lambari a Caxambu e mais 4 km de Caxambu a Baependi Acesse o link a seguir e aprenda mais sobre como resolver problemas de fluxo mínimo httpsyoutu beLmGRAIpF28Q 113 FLUXO MÁXIMO O problema do fluxo máximo busca maximizar o fluxo de mercadorias materiais energia etc a partir de um nó de origem para um nódestino da rede respeitando o limite mínimo e máximo de fluxo nos arcos O fluxo pode ser medido em duas direções fluxo máximo de saída do nó de origem ou fluxo máximo de chegada no nó de destino Como exemplos de aplicações do problema do fluxo máximo têmse a maximizar o fluxo de mercadorias em uma rede de distribuição b maximizar o fluxo por meio de sistema de dutos como gasodutos ou aquedutos por exemplo e c maximizar o fluxo 104 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 de veículos em uma rede de transportes O problema do caminho mais curto pode ser resolvido de forma eficiente pelo algoritmo de FordFulkerson Início para cada arco atribuir duas variáveis numéricas o fluxo já enviado entre os nós que inicialmente é nulo e a capacidade residual do arco que inicialmente é igual à capacidade do arco Passo 1 escolhese um caminho qualquer desde o nó de origem até o nó de destino Passo 2 neste caminho verificase o arco com menor capacidade residual crmin O fluxo crmin é então atribuído ou somado ao fluxo já existente para todos os arcos deste caminho Passo 3 para cada arco deste caminho calcular também a capacidade residual Passo 4 se não existir nenhum caminho em que todos os arcos têm capacidade residual positiva pare o fluxo corrente é máximo Caso contrário volte para o passo 1 existe um caminho de aumento de fluxo na rede residual Vejamos um exemplo de problema de fluxo máximo 105 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 Problema Ache o fluxo máximo na rede representada pela figura a seguir considerando as capacidades representadas nos ramos Desejase encontrar o fluxo máximo entres os vértices s A e t F FIGURA 8 REDE DE CAPACIDADES DE FLUXOS Fonte Lachtermacher 2016 p 138 PraCegoVer a figura representa o desenho de uma rede com os vértices A B C D E F As arestas são valoradas e as ligação são A 23 B A 12 C B 8 C B 15 D B 20 E C 25 D C 28 E D 7 E D 16 F E 14 F 106 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 2 Resolução parte 1 FlMax 0 Ramos desativados serão assinalados Primeiro caminho γAFABBDDF c Min231516 15 FlMax 0 15 15 FIGURA 9 REDE DE CAPACIDADES DE FLUXOS Fonte Lachtermacher 2016 p 138 PraCegoVer a imagem representa uma tabela com três colunas e onze linhas Da primeira à terceira coluna os textos aparecem na seguinte ordem arco a ca e fia Na Linha dois da primeira à terceira coluna os textos aparecem na seguinte ordem AB 23 e 0 Na linha três da primeira à terceira coluna os textos aparecem na seguinte ordem AC 12 e 0 Na linha quatro da primeira à terceira coluna os textos aparecem na seguinte ordem CB 8 e 0 Na linha cinco da primeira à terceira coluna os textos aparecem na seguinte ordem BD 15 e 0 Na linha seis da primeira à terceira coluna os textos aparecem na seguinte ordem BE 20 e 0 Na linha sete da primeira à terceira coluna os textos aparecem na seguinte ordem CD 25 e 0 Na linha oito da primeira à terceira coluna os textos aparecem na seguinte ordem CE 28 e 0 Na linha nove da primeira à terceira coluna os textos aparecem na seguinte ordem DE 7 e 0 Na linha dez da primeira à terceira coluna os textos aparecem na seguinte ordem DF 16 e 0 Na linha onze da primeira à terceira coluna os textos aparecem na seguinte ordem EF 14 e 0 107 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 3 Resolução parte 2 Segundo caminho FIGURA 10 REDE DE CAPACIDADES DE FLUXOS Fonte Lachtermacher 2016 p 139 PraCegoVer a imagem representa uma tabela com três colunas e onze linhas Da primeira à terceira coluna os textos aparecem na seguinte ordem arco a ca e fia Na Linha dois da primeira à terceira coluna os textos aparecem na seguinte ordem AB 8 e 15 Na linha três da primeira à terceira coluna os textos aparecem na seguinte ordem AC 12 e 0 Na linha quatro da primeira à terceira coluna os textos aparecem na seguinte ordem CB 8 e 0 Na linha cinco da primeira à terceira coluna os textos aparecem na seguinte ordem xBD 0 e 15 Na linha seis da primeira à terceira coluna os textos aparecem na seguinte ordem BE 20 e 0 Na linha sete da primeira à terceira coluna os textos aparecem na seguinte ordem CD 25 e 0 Na linha oito da primeira à terceira coluna os textos aparecem na seguinte ordem CE 28 e 0 Na linha nove da primeira à terceira coluna os textos aparecem na seguinte ordem DE 7 e 0 Na linha dez da primeira à terceira coluna os textos aparecem na seguinte ordem DF 1 e 15 Na linha onze da primeira à terceira coluna os textos aparecem na seguinte ordem EF 14 e 0 Logo abaixo da tabela temos que o fluxo máximo neste caso é 23 passando por A B B E E F e valores mínimos de 82014 108 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 4 Resolução parte 3 Terceiro caminho FIGURA 11 REDE DE CAPACIDADES DE FLUXOS Fonte Lachtermacher 2016 p 139 PraCegoVer a imagem representa uma tabela com três colunas e onze linhas Da primeira à terceira coluna os textos aparecem na seguinte ordem arco a ca e fia Na Linha dois da primeira à terceira coluna os textos aparecem na seguinte ordem xAB 0 e 23 Na linha três da primeira à terceira coluna os textos aparecem na seguinte ordem AC 12 e 0 Na linha quatro da primeira à terceira coluna os textos aparecem na seguinte ordem CB 8 e 0 Na linha cinco da primeira à terceira coluna os textos aparecem na seguinte ordem xBD 0 e 15 Na linha seis da primeira à terceira coluna os textos aparecem na seguinte ordem BE 12 e 8 Na linha sete da primeira à terceira coluna os textos aparecem na seguinte ordem CD 25 e 0 Na linha oito da primeira à terceira coluna os textos aparecem na seguinte ordem CE 28 e 0 Na linha nove da primeira à terceira coluna os textos aparecem na seguinte ordem DE 7 e 0 Na linha dez da primeira à terceira coluna os textos aparecem na seguinte ordem DF 1 e 15 Na linha onze da primeira à terceira coluna os textos aparecem na seguinte ordem EF 6 e 8 Logo abaixo da tabela temos que o fluxo máximo neste caso é 29 passando por A C C E E F e valores mínimos de 122816 109 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 5 Resolução parte 4 Quarto caminho FIGURA 12 REDE DE CAPACIDADES DE FLUXOS Fonte Lachtermacher 2016 p 140 PraCegoVer a imagem representa uma tabela com três colunas e onze linhas Da primeira à terceira coluna os textos aparecem na seguinte ordem arco a ca e fia Na linha dois da primeira à terceira coluna os textos aparecem na seguinte ordem xAB 0 e 23 Na linha três da primeira à terceira coluna os textos aparecem na seguinte ordem AC 6 e 6 Na linha quatro da primeira à terceira coluna os textos aparecem na seguinte ordem CB 8 e 0 Na linha cinco da primeira à terceira coluna os textos aparecem na seguinte ordem xBD 0 e 15 Na linha seis da primeira à terceira coluna os textos aparecem na seguinte ordem BE 12 e 8 Na linha sete da primeira à terceira coluna os textos aparecem na seguinte ordem CD 25 e 0 Na linha oito da primeira à terceira coluna os textos aparecem na seguinte ordem CE 22 e 6 Na linha nove da primeira à terceira coluna os textos aparecem na seguinte ordem DE 7 e 0 Na linha dez da primeira à terceira coluna os textos aparecem na seguinte ordem DF 1 e 15 Na linha onze da primeira à terceira coluna os textos aparecem na seguinte ordem xEF 0 e 14 Logo abaixo da tabela temos que o fluxo máximo neste caso é 30 passando por A C C D D F e valores mínimos de 6251 110 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 6 Resolução parte 5 Como não há mais caminho possível o fluxo máximo é 30 FIGURA 13 CAMINHO QUE INDICA O FLUXO MÁXIMO Fonte Elaborada pela autora 2022 PraCegoVer a figura representa o caminho a ser percorrido para obter o fluxo máximo Saindo do vértice A passando pela aresta de comprimento 12 em direção ao vértice C depois percorrendo a aresta de comprimento 25 em direção ao vértice D seguindo sobre a aresta de comprimento 16 até o vértice F Saiba mais sobre fluxo máximo acessando o link a seguir httpsintegradaminhabiblioteca c o m b r r e a d e r b o o k s 9 7 8 8 5 9 5 1 5 5 7 6 3 epubcfi6345B3Bvndvstidref3DaB97885352 781495001055D42822626210245315Bti c2Ces5D 111 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 12 PROBLEMAS ESPECIAIS Os problemas chamados de especiais são caracterizados por modelos dinâmicos de fluxo em rede isso porque possuem uma estrutura periódica ao longo do tempo LOESCH 2013 Em síntese três aspectos são considerados na escolha deste modelo Em primeiro lugar problemas com estrutura de fluxo em rede permitem uma visão diagramática de um problema físico Em segundo lugar possibilitam a definição do problema por meio de estruturas gráficas o que facilita a compreensão de especialistas ou não Por fim esta classe de problemas pode ser uma ordem de grandeza mais rápida que códigos de propósito ANDRADE 2015 n p 121 TRANSPORTE O problema de transporte genérico se refere em sentido literal ou figurado a distribuir qualquer matériaprima de qualquer grupo de centros de fornecimento denominados de origens a qualquer grupo de centros de recepção chamados destinos de maneira a minimizar o custo total de distribuição Cada fornecedor fabrica um número fixo de produtos e cada consumidor tem uma demanda conhecida que será atendida FÁVERO 2012 O problema considera dois elos da cadeia de suprimentos ou seja não inclui facilidades intermediárias centros de distribuição terminal porto marítimo ou fábrica O problema clássico de transporte é modelado portanto como um problema de programação linear Porém em vez de ser resolvido diretamente pelo método simplex utilizase o algoritmo de transporte que é uma simplificação do simplex FÁVERO 2012 p 350 O problema de transporte é um problema de fluxo em grafo bipartido de modo que não existem vértices intermediários de transbordo ou transição para o fluxo Na visão clássica deste problema os arcos não possuem limite de capacidade para o fluxo De forma geral a descrição gráfica do problema pode ser resumida na Figura 11 112 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 14 CARACTERÍSTICA DO FLUXO NO PROBLEMA DE TRANSPORTE Fonte Fávero 2012 p 271 PraCegoVer a figura representa um diagrama de flechas o primeiro conjunto corresponde aos vértices de oferta seus elementos são chamados de o1 o2 o3 e o4 O segundo conjunto corresponde aos vértices de demanda seus elementos são chamados de d1 d2 d3 d4 e d5 As flechas ligam os elementos da seguinte forma o1 se liga a d1 e d2 o2 se liga a d2 d3 e d4 o3 se liga a d3e d4 o4 se liga a d4 e d5 Os nós da rede na Figura 14 foram numerados exibindo a condição de saída nós de oferta e entrada de fluxo nós de demanda O problema de transporte pode ser entendido como um problema de fluxo em que o foco é minimizar totalmente os custos dos fluxos por meio das arestas HILLIER 2013 Algoritmo de transporte Início o problema deve apresentar o fluxo total de entrada igual ao fluxo total de saída ou seja deve estar balanceado e expresso na forma tabular Passo 1 encontrar uma solução básica factível SBF inicial Existem três métodos que podem ser aplicados para determinação da SBF método do custo mínimo método de aproximação de Vogel e método do canto noroeste Passo 2 teste de otimalidade 113 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Para verificar se a solução encontrada é ótima utilizase o método dos multiplicadores que é baseado na teoria da dualidade Aplicar a condição de otimalidade do método simplex ao problema de transporte Se a condição é satisfeita o algoritmo finaliza aqui Caso contrário determinase uma SBF adjacente melhor FÁVERO 2012 Iteração determinar uma SBF adjacente melhor Para encontrar uma nova solução básica factível três passos devem ser tomados 1 Encontrar a VNB que entrará na base utilizando o método dos multi plicadores 2 Selecionar a VB que passará para o conjunto de VNB utilizando a con dição de factibilidade do método simplex 3 repetir os cálculos para encontrar a nova solução básica Veja alguns métodos de resolução utilizados em problemas de redes de transportes Simplex Tratase de um algoritmo extremamente eficiente para soluções de sistemas lineares e adaptável ao cálculo computacional Branch and Bound BB Fundamentase na ideia de ramificação e avaliação progressiva ou seja dividir para conquistar Aplicase em problemas grandes e complexos que se tornam impossíveis de resolver de forma direta assim ele é dividido em subproblemas cada vez menores até que sejam vencidos GOLDBARG 2005 Método Heurístico É um procedimento que provavelmente encontrará uma excelente solução viável mas não necessariamente uma solução ótima para o problema específico em questão 114 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 122 TRANSBORDO O problema de transbordo transshipment problem TSP pode ser visto como um caso especial ou uma extensão do clássico problema de transporte em que agora consideramse pontos intermediários de transbordo facilidades como centro de distribuição terminal porto marítimo ou fábrica que podem fazer a ligação entre os caminhos com a finalidade de minimizar os custos logísticos FÁVERO 2012 O problema de transbordo considera três elos na cadeia de suprimentos e o processo de transporte ocorre em dois estágios transporte dos pontos fornecedores para os pontos de transbordo e transporte dos pontos de transbordo para os pontos de demanda O objetivo do problema de transbordo é determinar o fluxo de mercadorias a serem transportadas a partir de um conjunto de origens para um conjunto de destinos via facilidades intermediárias a fim de minimizar o custo total de transporte envolvido no sistema O problema de transbordo também é modelado como um problema de programação linear FÁVERO 2012 p 299 Para que um problema de transbordo possa ser convertido em um problema de transporte os nós de transbordo se tornam tanto pontos de oferta como também de demanda Devese definir também a capacidade de fornecimento das novas fontes e a demanda dos novos destinos HILLIER 2013 O problema de transbordo é um problema de fluxo em um grafo G V E em que cada vértice produz ou consome o produto Esse problema quando os comprimentos das arestas ou dos arcos de um grafo são considerados custos pode ser visto como um caso do transbordo não capacitado como mostra a Figura 15 Confira um vídeo sobre problema de transporte acessando o link https youtubeE30TnWwpIo 115 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 15 CAMINHO MAIS CURTO EM MODELO DE REDES Fonte Goldbarg 2014 p 250 PraCegoVer a figura representa um modelo de rede direcionada com caminho mais curto A rede possui sete vértices sendo o vértice s a origem o vértice t o destino e os demais vértices enumerados com 1 2 3 4 e 5 as arestas são valoradas e fazem as seguintes conexões do vértice 1 sai a aresta de comprimento 2 para o vértice 2 do vértice 2 sai a aresta de comprimento 4 para o vértice t e outra de comprimento 3 para o vértice 5 do vértice 3 sai a aresta de comprimento 2 para o vértice 2 e outra de comprimento 1 para o vértice 4 do vértice 5 sai a aresta de comprimento 1 para o vértice t do vértice s sai a aresta de comprimento 1 para o vértice 2 e outra de comprimento 1 para o vértice 1 nos vértices de origem e destino temse o valor 1 associado Tratase de um problema de fluxo a custo mínimo sem restrições de capacidade nos arcos O problema de caminho mais curto é um problema de transbordo em que o vértice raiz s injeta uma unidade de fluxo e o vértice destino t consome uma unidade de fluxo e os demais vértices têm ofertas ou demandas nulas FÁVERO 2012 Confira o vídeo sobre problema de transbordo acessando o link httpsyoutubeNUbG08QNU 116 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 123 ATRIBUIÇÃO O problema de designação de tarefas também conhecido como problema de alocação ou atribuição consiste em designar um conjunto de tarefas a um conjunto de máquinas de forma a minimizar o custo total de designação O problema de designação de tarefas pode ser modelado como um problema de transportes em que os fornecedores correspondem às tarefas e as demandas correspondem às máquinas FÁVERO 2012 p 308 considerando que cada tarefa só pode ser designada a uma única máquina e cada máquina só pode executar apenas uma tarefa se o problema de atribuição for modelado como um problema de transportes a oferta de cada fornecedor e a demanda de cada cliente corresponderá a 1 Além disso as variáveis de decisão do problema de atribuição serão binárias caracterizando um modelo de programação binária LOESCH 2008 A Figura 16 apresenta a representação em redes do problema de designação de tarefas FIGURA 16 MODELAGEM EM REDES DO PROBLEMA DE DESIGNAÇÃO DE TAREFAS COMO UM PROBLEMA DE TRANSPORTE Fonte Fávero 2012 p 308 PraCegoVer a figura representa um desenho com um modelo de rede de designação de tarefas os vértices da esquerda correspondem às tarefas e são rotulados como T1 T2Tm os vértices da direita correspondem às máquinas e são rotulados como M1 M2 Mm onde todos os vértices da esquerda se conectam com os vértices da direita por meio de arestas direcionadas no sentido da esquerda para direita 117 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II O problema de designação de tarefas pode ser resolvido de forma eficiente pelo método Húngaro Início o problema deve estar representado na forma matricial de custos Passo 1 para cada linha da matriz m m encontrar o elemento com menor custo Construir uma nova matriz em que os novos valores dos elementos de uma determinada linha corresponderão à diferença entre os valores originais e o menor elemento da linha selecionado Passo 2 para a matriz resultante do passo 1 encontrar o elemento com menor custo em cada coluna Construir uma nova matriz chamada matriz de custo reduzido em que os novos valores dos elementos de uma determinada coluna corresponderão à diferença entre os valores originais e o menor elemento da coluna selecionado Passo 3 cubra com retas horizontais e verticais o menor número possível de linhas e colunas de forma que todos os elementos com valores nulos da matriz de custo reduzido sejam cobertos Se m retas são necessárias há uma solução ótima entre os elementos com valores nulos cobertos na matriz Se foram utilizadas menos de m retas vá para o passo 4 Passo 4 entre os elementos não cobertos pelo passo 3 selecione aquele com menor valor chamado k Construa uma nova matriz de custos subtraindo k de cada elemento não coberto na matriz de custo reduzido e adicionando k para cada elemento coberto tanto por linha como por coluna respectivamente Os demais elementos permanecem inalterados Retorne ao passo 3 Para saber mais sobre o conteúdo acesse o link httpsintegradaminhabibliotecacombrreader books9788521629672epubcfi6345B3Bvnd vstidref3Dchapter55D47224405226 118 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 CONCLUSÃO Esta unidade teve como objetivo apresentar aplicações reais de problemas de programação linear como problemas de redes Os problemas apresentados simbolizam a maioria dos casos reais que podem ser vivenciados na prática cotidiana de um profissional Os processos de otimização e tomada de decisão estão atrelados e a programação linear aplicada em problemas de redes traz soluções ótimas e eficientes para situações que envolvem diversas áreas do conhecimento Por meio de conceitos e exemplos foi possível compreender os algoritmos que tornam os processos eficientes suas aplicações são demostradas na teoria e por meio dos vídeos e exemplos resolvidos e agora você é capaz de associar e resolver problemas de fluxo de redes envolvendo situações reais UNIDADE 5 OBJETIVO Ao final desta unidade esperamos que possa 119 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Definir e apresentar uma visão geral sobre os objetivos e a natureza da programação não linear Instruir de forma mais prática como problemas podem ser resolvidos computacionalmente 120 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 PROGRAMAÇÃO NÃO LINEAR INTRODUÇÃO DA UNIDADE Nesta unidade iremos abordar o conceito de programação não linear Como o próprio nome sugere este tipo de programação envolve funções não lineares Assim os problemas reais resolvidos pela programação não linear PNL podem ser modelados como funções não lineares De forma geral problemas envolvendo funções lineares são mais comuns do que se possa pensar tanto na natureza quanto em empresas Como exemplos de situações em que encontramos a aplicação da programação não linear podemos citar crescimento populacional e as interrelações entre receitas custos e lucros entre outros Os problemas de programação não linear podem ser classificados como PNL irrestrita com uma única variável ou com múltiplas variáveis e PNL com restrição inclui programação côncava convexa quadrática e separável Nesta unidade discutiremos a programação não linear desde a sua origem até os tipos mais comuns de programação não linear fique atento e estude assista aos vídeos e aprofunde seu conhecimento por meio das indicações de estudo 11 CONHECENDO SOBRE PROGRAMAÇÃO NÃO LINEAR A base da programação linear é que todas as suas funções funçãoobjetivo e funções de restrição são lineares Embora essa hipótese seja válida para a maioria dos problemas reais frequentemente ela não se verifica Portanto muitas vezes é necessário lidar diretamente com problemas de programação não linear e assim voltaremos nossa atenção para essa importante área 111 CRIAÇÃO E EVOLUÇÃO HISTÓRICA Wilhelm Leibniz e Isaac Newton estão entre os homens mais inteligentes que já existiram em todos os tempos Na verdade em termos de Ciências Exatas Newton Figura 1 é certamente a maior inteligência de todos os tempos 121 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Algumas das principais contribuições de Newton além do Cálculo são nas seguintes áreas a Lei da gravitação b Teorema binomial c Estudos de ótica d Leis do movimento e Representação de funções por séries infinitas f Geometria g Geometria Analítica h Álgebra i Astronomia j Química k estudos sobre o som l sistemas de coordenadas e m solução numérica de equações etc MORETIN 2018 Newton e Leibniz criaram o Cálculo de maneira independente com aproximadamente 10 anos de diferença Ao longo de suas vidas Leibniz desafiou Newton diversas vezes com problemas difíceis que foram resolvidos em questão de horas Ao final de suas vidas ambos eram inimigos mas conscientes da genialidade do outro Essa disputa fez com que houvesse uma separação entre matemáticos da Inglaterra e do continente fazendo com que a Inglaterra se atrasasse ao longo do século XVIII em relação ao que se fazia no resto da Europa COLIN 2017 FIGURA 1 ISAAC NEWTON O MAIOR PRECURSOR DAS CIÊNCIAS EXATAS Fonte Pixabay 2022 PraCegoVer a imagem representa um desenho da foto do rosto de Isaac Newton com cabelo cacheado longo bem abaixo do ombro e com um cachecol em volta do pescoço Um dos motivos para o maior avanço da matemática do continente foi o italiano de nascimento e francês de ascendência JosephLouis Lagrange 122 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 17361813 que juntamente com o suíço Leonhard Euler 17071783 são considerados os dois maiores matemáticos do século XVIII Lagrange fez diversas contribuições como os multiplicadores de Lagrange que servem para otimizar problemas sujeitos a restrições de igualdade Adicionalmente no campo da otimização fez grandes contribuições ao Cálculo Variacional que trata da otimização de funções em vez de números Já Euler revisou praticamente tudo que havia sido escrito antes dele dando um tratamento mais uniforme e unificado a grande parte da Matemática que era conhecida na época ANDRADE 2015 FIGURA 2 A TANGÊNCIA DA SUPERFÍCIE SUPERIOR COM O ESPAÇO DE RESTRIÇÕES NO CENTRO REPRESENTA A SOLUÇÃO Fonte Wikipedia 2022 PraCegoVer a imagem representa um desenho de uma superfície plotada dentro de um cubo de aresta variando de 5 a 5 nos eixos cartesianos x y e z em níveis de cores e reticulado No centro da figura têmse uma figura abaloada que representa a solução e as restrições em forma de planos que tangenciam na superfície superior da solução Embora a Matemática tenha ganhado destaque desde a época de Lagrange e Euler o tipo de problema que estudamos em programação não linear praticamente não evoluiu até a década de 1930 A próxima grande evolução aconteceria com a introdução de restrições de desigualdades no problema de otimização com restrições William Karush 19171997 um estudante de 123 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 mestrado na Universidade de Chicago publicou sua dissertação em 1939 considerando as restrições de desigualdade Aliado ao fato de Karush não ter ideia do alcance de sua descoberta sua pressa em começar e terminar seu doutorado fez com que ele não publicasse seu trabalho HILLIER 2013 O trabalho de Karush se manteve desconhecido por um longo período Com a criação da PL por Dantzig no final dos anos 1940 o interesse pela otimização sujeita a restrições cresceu significativamente Harold W Kuhn 19252014 e Albert W Tucker 19051995 desenvolveram um trabalho muito semelhante ao trabalho de Karush no qual eles apresentaram condições para que um ponto de uma função fosse ótimo COLIN 2017 Quando Dantzig foi visitar Von Neumann em Princeton uma feliz coincidência do destino fez com que Tucker desse uma carona a ele Nessa carona Dantzig apresentou a programação linear a Tucker que notou algumas analogias com problemas de Engenharia Elétrica que ele estudara algum tempo antes Dois anos depois Tucker convidou Kuhn para desenvolverem em conjunto o que posteriormente viria a ser chamado de condições de KarushKuhnTucker KKT COLIN 2017 Apesar de as condições de KKT serem um dos desenvolvimentos teóricos mais importantes da programação não linear na prática elas não são usadas para resolver problemas Grande parte da base utilizada nos métodos de programação não linear usados atualmente foi originada na década de 1960 com trabalhos de William Davidon 19272013 Roger Fletcher 19392016 e M J D Powell 19362015 COLIN 2017 Antes do início de seus estudos sobre o tema os maiores problemas não lineares não quadráticos que eram resolvidos estavam na casa de 10 variáveis Em uma conferência de 1962 quando Powell relatou que conseguira resolver problemas de 100 variáveis a maioria dos participantes do evento não o levou a sério COLIN 2017 Devido à existência de muitos tipos e de muitos algoritmos a programação não linear é um assunto particularmente extenso contudo abordaremos de forma reduzida Desse modo é importante um estudo complementar Veja as indicações no final deste texto 124 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 112 VISÃO GERAL MODELAGEM E SOLUÇÃO COMPUTACIONAL A breve introdução sobre a criação e evolução da programação não linear é suficiente para perceber a complexidade associada aos problemas de programação não linear Mostrar que muitas das ideias usadas na programação não linear sua origem no Cálculo ou em transformações simples de ideias dele é fundamental para compreendermos seu desenvolvimento COLIN 2017 A figura 3 mostra uma aplicação do cálculo os modelos de PNL com funções contínuas também chamadas de suaves que são deriváveis e com isso a busca por solução se torna mais eficiente Para as funções que apresenta descontinuidade ou não são diferenciáveis teremos restrições que possam garantir sua aplicabilidade FIGURA 3 FUNÇÕES SUAVES E DERIVADAS Fonte Cefet MG s d PraCegoVer a imagem representa o desenho de três curvas plotadas nos eixos cartesianos x e y O primeiro gráfico referese a uma curva suave o segundo gráfico a uma curva não contínua e o terceiro gráfico a uma função não diferenciável Em termos práticos o Cálculo como geralmente se aprende em cursos superiores é pouco utilizado na solução de problemas relacionados à gestão de empresas Por exemplo embora seja difícil avaliar se um ponto não diferenciável é de máximo ou mínimo muitas técnicas de programação não linear fazem isso com relativa facilidade Nesse sentido a programação não linear se aproxima mais dos nossos interesses uma vez que muitos problemas importantes são não contínuos eou não diferenciáveis ANDRADE 2015 125 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 A definição do problema de PNL Programação Não Linear é parecida com a definição do problema de programação linear A diferença está basicamente no fato de que as funções usadas tanto funçãoobjetivo como restrições possuem pelo menos uma relação não linear entre as variáveis Por exemplo se há uma multiplicação entre duas variáveis quaisquer o problema é considerado não linear MORETIN 2018 Formalmente o problema de PNL em seu caso mais genérico pode ser definido como identificar os 1 2 3 x x x nx para os quais a seguinte formulação seja satisfeita 1 2 3 max z f x x x nx 1 1 2 1 n sujeitoa g x x x b 1 2 n n n g x x x b Em que 1 2 ib i m é um valor constante e pelo menos uma das equações 1 2 1 2 ƒ n i n x x x g x x x possui uma relação não linear O objetivo é obviamente identificar os valores de 1 2 x x n x que otimizam z Quase tudo o que foi aprendido na PL em termos de manipulação do problema padrão continua válido Por exemplo a multiplicação por 1 transforma a maximização em minimização e restrições de em e viceversa Uma segunda transformação importante permite que a adição de uma variável de folga transforme as inequações em equações HILLIER 2013 Caso o problema não possua restrições ele é chamado de problema de otimização irrestrito Para se aprofundar mais não deixe de assistir ao vídeo a seguir httpsyoutube1Mi1PbmdCG8 126 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 113 ASPECTOS TEÓRICOS DA PROGRAMAÇÃO NÃO LINEAR Considerando a complexidade dos problemas de PNL em que até mesmo a identificação de uma solução ponto de ótimo local não é uma tarefa muito simples As condições de KarushKuhnTucker KKT fazem isso ou seja identificam se uma solução é ótima ou não COLIN 2017 As condições de KKT são consideradas necessárias para que um ponto seja um ótimo local mas não garantem que ele seja um ótimo global Para problemas com certas características como convexidade as condições de KKT garantem a otimização global e nesse caso são consideradas condições necessárias e suficientes para que o ótimo seja global COLIN 2017 Assista este vídeo para saber mais sobre as condições de KarushKuhnTucker KKT https youtubeg8ah6jZSFI Nesta seção veremos alguns detalhes de métodos existentes para resolver problemas de PNL Estudos teóricos em geral são focados em duas perguntas centrais 1 o algoritmo converge para a solução ótima E caso a resposta seja afirmativa 2 com que rapidez Alguns métodos de solução não são robustos o suficiente para que em qualquer caso a solução seja sempre encontrada ou seja dependendo dos pontos iniciais da busca a solução pode ser encontrada ou não Caso a solução seja encontrada independentemente dos pontos iniciais dizse que o algoritmo é globalmente convergente e esse é o objeto de estudo da primeira pergunta A segunda pergunta simplesmente tenta avaliar entre os algoritmos que convergem quais são os mais rápidos COLIN 2017 Métodos de otimização com uma variável são importantes por duas razões 1 são utilizados para resolver problemas práticos e 2 são utilizados como base de procedimentos mais sofisticados que resolvem problemas de múltiplas variáveis A Figura 4 apresenta uma classificação dos principais algoritmos utilizados para resolver problemas de uma variável COLIN 2017 127 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Detalhes adicionais sobre otimização você encontra aqui neste link https integradaminhabibliotecacombrreader books9788597014488epubcfi6725B3Bvnd vstidref3Dchapter225D41186405195 FIGURA 4 CLASSIFICAÇÃO DE MÉTODOS DE SOLUÇÃO PARA PROBLEMAS COM UMA ÚNICA VARIÁVEL Fonte Colin 2017 p 299 PraCegoVer a imagem representa o esquema hierárquico começando com o texto Otimização com uma variável este tópico se divide em duas ramificações a ramificação superior com texto Cálculo diferencial que se divide em outras duas ramificações com os textos Derivação na ramificação superior e Multiplicadores de Lagrange na ramificação inferior A ramificação inferior do texto Otimização com uma variável se divide em outras duas ramificações com os textos Métodos de Eliminação na ramificação superior e Métodos de Interpolação na ramificação inferior A ramificação Métodos de Eliminação se ramifica em cinco galhos com os textos Busca Irrestrita Busca exaustiva Busca dicotômica Método de Fibonacci Método da seção áurea A ramificação Métodos de Interpolação se ramifica em três galhos com os textos Cúbico Raiz Direta Quadrático Os galhos com os textos Cúbico Raiz Direta têm uma chave com o texto requerem derivada O galho com o texto Quadrático tem uma chave com o texto não requerem derivada 128 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II No mundo real funções de múltiplas variáveis são mais frequentes do que funções de uma única variável Os métodos para o tratamento desse tipo de problema são diversos a Figura 5 apresenta uma classificação parcial destes métodos COLIN 2017 FIGURA 5 CLASSIFICAÇÃO DE MÉTODOS DE SOLUÇÃO PARA PROBLEMAS COM MÚLTIPLAS VARIÁVEIS Fonte Colin 2017 p 300 PraCegoVer a imagem representa o esquema hierárquico começando com o texto Otimização com Múltiplas Variáveis este tópico se divide em três ramificações a ramificação superior com texto Derivações a ramificação do meio com o texto Problemas sem Restrições que se divide em outras duas ramificações com os textos métodos de busca direta na ramificação superior e Métodos ascendentes na ramificação inferior A ramificação métodos de busca direta se ramifica em cinco galhos com os textos Busca aleatória Método univariado Métodos de busca de padrão Método das coordenadas rotativas Método simplex estes galhos são unidos por uma chave com o texto não requerem derivadas A ramificação Métodos ascendentes se ramifica em quatro galhos com os textos Maior passo ascendente Método do gradiente conjugado Métodos quase Newton Método de métrica variável Os galhos com os textos Cúbico Raiz Direta têm uma chave com o texto requerem derivada Estes galhos são unidos por uma chave com o texto requerem derivadas A terceira ramificação do texto Otimização com Múltiplas Variáveis primeiro galho se divide em três galhos O galho com o texto Quadrático tem uma chave com o texto não requere derivada A ramificação inferior do texto Otimização com Múltiplas Variáveis com o texto problemas com restrições se divide em outras três ramificações com os textos Multiplicadores de Lagrange na ramificação superior e Métodos de busca direta que se divide em dois galhos com os textos direções viáveis que se divide em quatro galhos com os textos Método de Zoutendijk Método de projeção do gradiente Método do gradiente reduzido generalizado Método simplexconvexo O galho de Métodos de busca indireta se divide em dois galhos com os textos Transformação de variáveis e Funções de penalidade respectivamente sendo que o galho Função de penalidade se divide em dois galhos com os textos Interior e Exterior respectivamente 129 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 12 TIPOS DE PROBLEMA DE PROGRAMAÇÃO NÃO LINEAR Os problemas de PNL se apresentam de muitas formas e formatos distintos Diferentemente do método simplex para PL não existe um algoritmo único capaz de resolver todos esses tipos diferentes de problemas Em vez disso foram desenvolvidos algoritmos para várias classes individuais de problemas de PNL Para compreender os problemas que envolvem a PNL veja o seguinte problema de aplicação real httpsyoutubeAt6YFZk9KKUv 121 PROGRAMAÇÃO NÃO LINEAR RESTRITA E IRRESTRITA Os problemas de programação não linear irrestrita são classificados de acordo com o número de variáveis Dessa forma temos problemas com apenas uma variável ou com várias variáveis Os problemas de PNL irrestrita como o nome sugere não possui restrições assim o modelo é expresso em termos da funçãoobjetivo que visa a maximizar ou minimizar uma função não linear com uma ou múltiplas variáveis FÁVERO 2012 Os problemas de PNL restritos ou com restrição têm como finalidade maximizar ou minimizar uma função seja ela linear ou não com múltiplas variáveis sujeito a apenas uma única restrição ou múltiplas restrições Entre os problemas de PNL restritos os mais utilizados são programação côncava convexa quadrática e separável FÁVERO 2012 As condições de KarushKuhnTucker KKT são aplicadas para verificar se uma determinada solução de um problema de PNL é ou não uma solução ótima local Entretanto o uso de tais condições de KKT assegura que o ótimo local seja também um ótimo global FÁVERO 2012 Em problemas de maximização de PNL quando a funçãoobjetivo é uma 130 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II função côncava e todas as restrições são funções convexas é possível afirmar que todo ponto que atenda às condições de KKT ótimo local é também um ótimo global FÁVERO 2012 De forma bem semelhante dado um problema de minimização de PNL se a funçãoobjetivo e todas as restrições são funções convexas podese afirmar que qualquer ponto que atenda às condições de KKT ótimo local é também um ótimo global COLIN 2017 A PNL irrestrita com uma única variável apresenta várias formas de ser obter a solução ou seja existem diversos métodos de solução Veja aqui os mais empregados Método da bisseção O método da bisseção é um método numérico muito simples para determinar a raiz x de uma função fx não linear seu foco é determinar a solução analítica da equação fx 0 O método gráfico é uma opção para encontrar as raízes da função fx correspondendo aos valores de x em que a função intercepta o eixo horizontal do gráfico FÁVERO 2012 A desvantagem deste método é que a convergência no sentido de encontrar a raiz da função fx é muito lenta FÁVERO 2012 Método de Newton O método de Newton conhecido também no cálculo numérico como método de NewtonRaphson tem o objetivo de determinar uma função chamada interativa que é responsável pela agilidade na convergência da estimação das raízes de uma função não linear fx Em comparação ao método da Bisseção o método de Newton é mais rápido FÁVERO 2012 Para que a convergência seja satisfatória o valor inicial estimado deve ser adequado isto é suficientemente próximo da raiz da função Quando falamos em PNL irrestrita com múltiplas variáveis estamos tratando de um modelo expresso em termos da funçãoobjetivo PNL sem restrições mas que visa a maximizar ou minimizar uma função não linear com n variáveis Para a solução de problemas de PNL irrestrita com múltiplas variáveis temos os métodos de busca direta e descida ou indiretos COLIN 2017 131 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Métodos de busca direta são aqueles que minimizam ou maximizam uma função com múltiplas variáveis sem a necessidade de derivar da função objetivo É importante dizer que na maioria das vezes os métodos que envolvem derivadas têm convergência mais rápida em relação aos métodos de busca direta Entre os métodos de busca direta os mais utilizados são método simplex método de busca aleatória método de Rosenbrock método de busca seccionada e método de Hooke e Jeeves com busca linear FÁVERO 2012 Método de busca aleatória Nesse método são utilizados números aleatórios para determinar a solução ótima É considerando menos eficiente comparado a outros métodos de busca direta Por trabalhar com valores aleatório não precisa de valores iniciais Método de busca seccionada Esse método utiliza várias direções de busca entretanto a cada iteração a busca é realizada em apenas uma direção utilizando métodos univariáveis FÁVERO 2012 Método de Hooke e Jeeves com busca linear É uma adaptação do método original proposto por Hooke e Jeeves utilizando buscas lineares Esse método realiza dois tipos de busca exploratória e progressiva A busca exploratória estima a direção provável do ponto extremo a partir de um ponto inicial Já a busca progressiva percorre essa direção enquanto o valor da funçãoobjetivo diminuir minimização ou aumentar maximização FÁVERO 2012 p 302 Método de Rosenbrock O método de Rosenbrock utiliza passos discretos ao longo das direções de busca É uma versão adaptada do método de Hooke e Jeeves só que percorrendo novas direções ortogonais FÁVERO 2012 132 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Método simplex Nesse método a funçãoobjetivo é verificada ponto a ponto que sejam extremos do polígono simplex Métodos de descida ou métodos indiretos esses métodos utilizam as derivadas de primeira e segunda ordem da funçãoobjetivo para determinar as direções de busca Entre eles podemos citar os mais utilizados método do gradiente método de Newton método do QuaseNewton e método do gradiente conjugado COLIN 2017 Método de Newton A segunda derivada da funçãoobjetivo define a direção de busca Quando a funçãoobjetivo é quadrática o mínimo da função é determinado com apenas uma iteração FÁVERO 2012 Método do quaseNewton É uma particularidade do método de Newton pois utiliza somente a primeira derivada da funçãoobjetivo Esta particularidade torna o método do QuaseNewton muitas vezes mais eficiente que o próprio método de Newton FÁVERO 2012 Método do gradiente Utilizando apenas a primeira derivada da funçãoobjetivo no processo de busca esse método é bem simples pois usa os gradientes para direcionar a busca A desvantagem é que frequentemente a busca para em ótimos locais FÁVERO 2012 Método do gradiente conjugado Esse método é indicado quando se trata de problemas com elevado número de variáveis isso porque ele ocupa pouco espaço de armazenamento das informações Seu desenvolvimento envolve somente a primeira derivada da funçãoobjetivo utiliza o método do 133 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 gradiente para encontrar a direção do passo atual e a nova direção de busca passa a ser determinada pela combinação linear das direções de busca dos passos anteriores associada à direção do passo atual FÁVERO 2012 122 PROGRAMAÇÃO CÔNCAVA E CONVEXA Antes de iniciarmos nossa discussão sobre programação côncava e convexa a figura 6 mostra um exemplo de funções côncava e convexa para uma variável Neste caso é correto dizer de uma forma simples que uma função é convexa se uma linha que intercepta dois pontos de seu gráfico fica acima dele E se a linha que intercepta o gráfico ficar abaixo dele temos uma função côncava FIGURA 6 EXEMPLO DE FUNÇÃO CÔNCAVA E CONVEXA Fonte Colin 2017 p 288 PraCegoVer a imagem representa gráficos no eixo cartesiano de coordenadas x e y de funções matemáticas O primeiro gráfico representa uma função com a concavidade voltada para cima e uma reta traçada interceptando a curva em dois pontos distintos de forma que reta fique acima da curvatura O segundo gráfico representa uma função com a concavidade voltada para baixo e uma reta traçada interceptando a curva em dois pontos distintos de forma que reta fique abaixo da curvatura Um problema de programação não linear é dito de programação côncava se apresenta as seguintes características se a otimização for de maximização se a funçãoobjetivo for uma função côncava se a restrição for do tipo i i g x b menor ou igual e ig x é uma função convexa 134 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II se a restrição for do tipo i i g x b maior ou igual e ig x é uma função côncava se a restrição de igualdade for linear O relevante desse tipo de modelo está no fato de que um problema de programação côncava terá o máximo global igual ao máximo local Isso significa que o modelo será eficientemente resolvido pelo algoritmo aplicado LACHTERMACHER 2021 Podemos garantir que o conjunto de soluções viáveis de um PNL com restrições apenas inequações é um conjunto convexo se todas as restrições respeitam as seguintes regras se a restrição for do tipo i i g x b menor ou igual e ig x é uma função convexa se a restrição for do tipo i i g x b maior ou igual e ig x é uma função côncava Decorre dessa consideração que se o modelo for uma maximização a funçãoobjetivo será uma função côncava e o conjunto de soluções viáveis um conjunto convexo então o PNL será dito de programação côncava e o máximo encontrado será global LACHTERMACHER 2021 Note que a única diferença entre as duas definições está no fato de uma incluir igualdade linear e a outra não O fato de o conjunto de restrições de um problema de PNL incluir igualdades não lineares tem como consequência a complexidade na determinação se o conjunto de soluções viáveis for ou não um conjunto convexo Portanto quando existirem igualdades não lineares em um problema não poderemos garantir que a solução encontrada pelo Solver seja ou não global LACHTERMACHER 2021 Vale ressaltar que se o conjunto de restrições apresentar apenas restrições lineares poderemos garantir que o conjunto de soluções viáveis será um conjunto convexo Portanto se existir uma funçãoobjetivo côncava e o problema for de maximização teremos um problema de programação côncava LACHTERMACHER 2021 135 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Um problema de programação não linear é dito de programação convexa se apresenta as seguintes características se a otimização é de minimização se a funçãoobjetivo é uma função convexa se a restrição é do tipo i i g x b menor ou igual e ig x é uma função convexa se a restrição é do tipo i i g x b maior ou igual e ig x é uma função côncava se cada restrição de igualdade é linear O relevante desse tipo de modelo está no fato de que um problema de programação convexa terá o mínimo global igual ao mínimo local Isso significa que o modelo será eficientemente resolvido pelo algoritmo aplicado LACHTERMACHER 2021 Podemos garantir que o conjunto de soluções viáveis de um PNL com restrições apenas inequações é um conjunto convexo se todas as restrições respeitam as regras a seguir se a restrição é do tipo i i g x b menor ou igual e ig x é uma função convexa se a restrição é do tipo i i g x b maior ou igual e ig x é uma função côncava Decorre dessa consideração que se o modelo é uma minimização a função objetivo é uma função convexa e o conjunto de soluções viáveis é um conjunto convexo o PNL é dito programação convexa e o mínimo encontrado pelo algoritmo é global COLIN 2017 A Figura 7 mostra um exemplo de função objetivo e uma restrição para um modelo convexo 136 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 7 EXEMPLO DE MODELO CONVEXO Fonte CefetMG s d PraCegoVer a imagem representa gráficos no eixo cartesiano de coordenadas x y e z O primeiro gráfico representa a funçãoobjetivo em forma de superfície dando o feito de uma folha de papel levemente envergada com forma de uma função logarítmica com tonalidade de cores diferentes O segundo gráfico representa uma restrição em forma de superfície dando o feito de uma folha de papel levemente envergada com forma de uma função exponencial com tonalidade de cores diferentes Note que a única diferença entre as duas definições está no fato de uma incluir igualdades lineares e a outra não LACHTERMACHER 2021 O fato de o conjunto de restrições de um problema de PNL incluir igualdades não lineares tem como consequência a complexidade para determinar se o conjunto de soluções viáveis é ou não um conjunto convexo Portanto quando existirem igualdades não lineares em nosso problema não poderemos garantir que a solução encontrada pelo Solver seja ou não global COLIN 2017 Vale ressaltar que se o conjunto de restrições apresentar apenas restrições lineares poderemos garantir que o conjunto de soluções viáveis será um conjunto convexo Portanto se existir uma funçãoobjetivo convexa e o problema for de minimização teremos um problema de programação convexa LACHTERMACHER 2021 137 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 123 PROGRAMAÇÃO NÃO LINEAR SEPARÁVEL A programação separável é caracterizada por problemas em que os termos da funçãoobjetivo separados por somas ou subtrações possuem só uma variável Cada termo pode ter qualquer formato linear quadrático logarítmico etc mas não pode haver nenhuma operação não aditiva como multiplicação e divisão entre duas variáveis COLIN 2017 Caso as funções j j f x sejam côncavas e o problema seja de maximização a programação linear pode ser usada para se resolver o problema O mesmo resultado é verdade para problemas de minimização de funções convexas Em ambos os casos as funções não lineares são aproximadas por funções lineares segmentadas Caso as funções j j f x não sejam nem côncavas nem convexas podese usar variáveis inteiras binárias para se aproximarem as funções originais por funções lineares segmentadas COLIN 2017 Algumas vezes funções não lineares não separadas podem ser transformadas em funções não lineares separadas Não existe uma metodologia genérica de conversão e cada situação depende mais da habilidade do modelador do que de um algoritmo de conversão As conversões só podem ser feitas em funções que são intrinsecamente separáveis ou seja existem funções que não são separáveis de forma alguma Como não há um algoritmo genérico para fazer as conversões acesse o link a seguir e veja alguns exemplos de como elas podem ser feitas httpsintegradaminhabibliotecacombrreader books9788597014488epubcfi6765B3Bvnd vstidref3Dchapter245D4642405293 138 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II CONCLUSÃO Esta unidade teve como objetivo discutir os aspectos da programação não linear que embora seja mais complexa é mais comum na prática do que se possa imaginar Os métodos de solução de problemas de programação não linear envolvem métodos matemáticos dos mais simples aos mais complexos o que torna sua aplicação muito diversificada e aplicável Alguns conceitos e métodos estudados para solução de problemas de programação linear podem ser utilizados com ajustes para problemas de programação não linear isso torna o processo mais simples e objetivo Por meio do que estudamos nesta unidade agora você é capaz de associar e resolver problemas de tomada de decisão que são modelados por funções não lineares que por sua vez em alguns casos podem ser transformados em funções lineares UNIDADE 6 OBJETIVO Ao final desta unidade esperamos que possa 139 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Resolver problemas reais com programação linear quadrática Apresentar casos que ilustram situações reais em que a solução é por meio da programação não linear 140 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 1 PROGRAMAÇÃO NÃO LINEAR QUADRÁTICA INTRODUÇÃO DA UNIDADE Nesta unidade iremos abordar a programação não linear quadrática Este tipo de programação envolve funções não lineares em que a funçãoobjetivo é fundamentalmente uma função quadrática Os casos apresentados ao longo desta unidade retratam problemas reais resolvidos por meio de algoritmos de Programação Não Linear PNL modelados como funções não lineares Os problemas que forem classificados como de programação quadrática independentemente de o modelo se tratar de uma maximização ou de uma minimização terão a sua solução ótima encontrada pelos algoritmos de resolução de problemas não lineares sem dificuldades Como o conjunto de restrições é formado apenas por funções lineares da mesma maneira que nos problemas de programação linear podemos garantir que o conjunto de soluções será um conjunto convexo COLIN 2017 Portanto em um caso de programação quadrática de maximização em que a funçãoobjetivo é uma função côncava o algoritmo encontrará o máximo global Naturalmente em um caso de programação quadrática de minimização em que a funçãoobjetivo é uma função convexa o algoritmo encontrará o mínimo global 11 PROGRAMAÇÃO QUADRÁTICA UM CASO ESPECIAL Essencialmente um problema de programação quadrática pode ser definido como aquele que possui uma funçãoobjetivo em que pelo menos um dos termos é quadrático multiplicação de duas variáveis os outros termos são no máximo quadráticos e as restrições são lineares A programação quadrática é responsável pela solução de problemas práticos importantes 141 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 111 OTIMIZAÇÃO DE PREÇOS E VOLUMES DE VENDAS FIGURA 1 OTIMIZAÇÃO DE VENDAS Fonte Pixabay 2022 PraCegoVer a imagem representa um homem buscando atingir seus objetivos de otimização Ele usa um gráfico de barras sobreposto por um gráfico de linhas Uma roldana liga um fio que é segurado pelo homem à extremidade do gráfico de linhas representando a ideia de elevação do processo de otimização O problema da maximização da margem ou otimização de preços e volumes de vendas pode ser usado em uma infinidade de situações Praticamente em qualquer caso em que o preço de um produto determine sua demanda e exista flexibilidade para se alterarem volumes de venda o uso bem conduzido do modelo traz vantagens É interessante notar que apesar da relativa simplicidade ele não é usado com a frequência que deveria Já nos deparamos com situações em que empresas de diversos portes em especial as grandes e muito grandes não têm uma noção clara a respeito do relacionamento entre preços de venda custos de produção e margens financeiras FÁVERO 2012 142 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II O relacionamento entre preço e demanda possui um conceito importante associado que é a elasticidade A elasticidade da demanda com relação ao preço determina quanto a demanda muda para uma dada variação no preço do produto COLIN 2017 Para produtos normais em geral existe um relacionamento inverso entre preço e demanda à medida que o preço aumenta a demanda diminui e quando o preço baixa a demanda aumenta veja Figura 2 Para esse comportamento padrão pode haver uma série de curvas que satisfazem o relacionamento inversamente proporcional Vamos considerar o caso mais simples que é o relacionamento linear entre preço e demanda FÁVERO 2012 FIGURA 2 EXEMPLO DE CURVA DE ELASTICIDADE DA DEMANDA Fonte Colin 2017 p 336 PraCegoVer a imagem representa um gráfico de curva de elasticidade o eixo horizontal corresponde a Demanda e o eixo vertical corresponde ao eixo Preço Os pontos sobre o gráfico possuem as coordenadas x e y respectivamente com os textos Ponto 1 demanda para o preço 1 e Preço 1 e Ponto 2 demanda para o preço 2 e Preço 2 e a diferença entre estes dois pontos corresponde à variação de demanda dada uma variação de preço A curva formada pelo gráfico corresponde a Curva de elasticidade da demanda 143 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Sejam conjuntos de produtos j j 1 2 n e períodos i i 1 2 m O preço do produto j no período i é representado por pji e a previsão de vendas para o mesmo produto no mesmo período é dada por qji Nesse exemplo tanto a previsão de vendas como a demanda prevista são equivalentes à produção de produtos Para o caso linear podemos dizer que ji ji ji ji q a b p Eq 1 Em que a e b são parâmetros que dependem da curva de elasticidade em questão Para cji o custo de produção do produto j no período i a margem dele mji é definida como ji ji ji ji m p c q Eq 2 Mas como a quantidade é uma função do preço podemos dizer que 2 ji ji ji ji ji ji ji ji ji ji ji ji ji ji m p c a b p b p a b c p a c Eq 3 A margem da empresa para todos os produtos ao longo do horizonte de planejamento pode ser definida como 2 1 1 m n ji ji ji ji ji ji ji ji i j M b p a b c p a c Eq 4 O modelo desenvolvido é bastante completo e em geral algumas das variáveis descritas são valores constantes COLIN 2017 Por exemplo para um produto apenas a margem poderia ser descrita como 2 1 m i i i i i i i M b p a b c p a c Eq 5 E para um período apenas como 6 Por outro lado o modelo poderia ser expandido para que as curvas de elasticidade da demanda fossem referentes a regiões de demanda ou até mesmo a pontos de venda No vídeo a seguir você vai conhecer o Método de Wolfe que é bastante utilizado para solução de problemas por meio da Programação Não Linear quadrática COLIN 2017 httpsyoutubeDaGTFv 6Ao 144 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 112 PROBLEMA DA MAXIMIZAÇÃO DE MARGEM FIGURA 3 ILUSTRAÇÃO DE MAXIMIZAÇÃO DE MARGEM Fonte Pixabay 2022 PraCegoVer a imagem representa um gráfico de linhas com o dedo de um homem apontando para o alvo que é a maximização O modelo de maximização da margem como o próprio nome diz maximiza a margem total da empresa sujeito a restrições diversas Sejam Qi a capacidade de produção total no período i e p e p os preços máximo e mínimo respectivamente COLIN 2017 O modelo de maximização da margem pode ser representado por 2 1 1 max m n ji ji ji ji ji ji ji ji i j M b p a b c p a c Sujeito a 1 n ji ji ji i j a b p Q para 1 2 i m para ji ji ji p p p 1 2 i m e 1 2 j n Eq 7 O primeiro grupo de restrições estabelece que em cada período a produção não pode exceder a capacidade de produção O segundo grupo de restrições estabelece que o preço deve estar entre dois limites um que estabelece o preço máximo e outro o preço mínimo de cada produto COLIN 2017 145 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Outras restrições poderiam ser introduzidas Por exemplo 1 capacidade de produção desdobrada em equipamentos e produtos 2 capacidade de estocagem caso as vendas fossem independentes da produção 3 matérias primas disputadas por vários produtos 4 capacidades de elementos da logística da empresa como carregamento de caminhões e de navios vagões e caminhões disponíveis 5 relacionamento entre produtos considerando canibalização e competidores 6 custos de produção dependentes dos volumes de vendas e assim por diante COLIN 2017 Vamos usar um exemplo hipotético para compreender melhor a Star Mobile grande multinacional começou a atuar há alguns anos no mercado de aparelhos celulares FIGURA 4 TECNOLOGIA DA STAR MOBILE Fonte Pixabay 2022 PraCegoVer a imagem representa um homem segundo um celular e dele saem vários ícones que representam aplicativos de nuvem redes sociais bancos entre outros mostrando que por meio da tecnologia GSM é possível se conectar a tudo o tempo todo A especialidade da empresa é a tecnologia GSM tecnologia da Tim Oi Claro que possui algumas vantagens com relação a outras tecnologias como menor custo de produção No Brasil as tecnologias GSM juntamente com a CDMA tecnologia da Vivo estão crescendo ao passo que a tecnologia TDMA ATL BCP Maxitel Telemig Celular Tess etc está sendo abandonada progressivamente COLIN 2017 A Star Mobile está interessada em avaliar dois de seus produtos que concorrem pelo mesmo mercado denominados celular 1 e celular 2 Para 146 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II tanto encomendou uma pesquisa de mercado que estabeleceu as curvas de elasticidade da demanda com relação ao preço para ambos os produtos As equações são definidas como 1 1 2 4100 8 d p p 2 2 1 3800 9 08 d p p Eq 8 Em que djj 1 2 j representa o mercado potencial para o produto j em milhares de unidades e pj representa o preço do aparelho em R Observe que a demanda dos produtos aumenta à medida que seus preços caem mas também aumenta à medida que o preço do outro produto concorrente sobe COLIN 2017 A empresa tem a capacidade de estabelecer o preço da classe de produtos no mercado e seus competidores vão seguila de perto A sua participação de mercado de 50 e 40 respectivamente é independente do preço pois os concorrentes vão precificar seus produtos de forma muito próxima Ainda não há evidências de que essa participação vá mudar ao longo do tempo COLIN 2017 Uma outra característica é que a Star Mobile importa boa parte dos componentes de produtores asiáticos e especialmente por esse motivo o custo de produção varia conforme o volume de vendas Mais especificamente 1 1 1000 190 05 c d e 2 2 1000 260 04 c d Eq 9 Em que c é o custo de produção Observe que a modelagem considera que a produção é equivalente a 50 e 40 dos mercados potenciais respectivamente A margem total m da empresa a ser capturada com sua participação de mercado em todo o mercado potencial é definida por 1 1 1 2 2 2 05 04 M p c d p c d Eq 10 A administração só vê com receio sua capacidade de montagem e de expedição Por esse motivo ambas as capacidades serão consideradas restrições As restrições de capacidade juntamente com o modelo podem ser inseridas 147 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 em uma planilha eletrônica para facilitar a solução a Tabela 1 apresenta os resultados obtidos como solução do problema Para as restrições de capacidade consideramos que o mercado total seja capturado ao longo dos próximos quatro anos COLIN 2017 TABELA 1 QUADRO DE VALORES DA SOLUÇÃO DO PROBLEMA Variável Denominação Unidade Produto Cel1 Cel2 Preço R Unidade 37866 37107 Dados Participação de mercado 50 40 Requisito de capacidade Montagem hunidade 0150 0160 Expedição hunidade 0018 0018 Cálculos Margem unitária R Unidade 18750 10779 Margem total Milhares de R 134996 32920 Mercado potencial Milhares de unidades 1440 764 Custo R Unidade 19139 26327 Demanda da empresa Milhares de unidades 720 305 Soma Capacidade disponível Restrições Montagem h 2250 1018 3268 4160 Capacidade produção EmbalagemExpedição h 270 115 385 416 Fonte Colin 2017 p 339 PraCegoVer a imagem representa uma tabela intitulada Quadro de valores da solução do problema que tem quinze linhas e quatro colunas Da primeira à quarta coluna os textos aparecem na seguinte ordem Variável Denominação Unidade e Produto Na Linha dois da primeira à quarta coluna os textos aparecem na seguinte ordem Preço R Unidade 37866 Cel 1 37107 Cel 2 Na linha três da primeira à quarta coluna os textos aparecem na seguinte ordem Dados Participação de mercado 50 40 Na linha quatro da primeira à quarta coluna os textos aparecem na seguinte ordem Dados Requisito de capacidade e Na linha cinco da primeira à quarta coluna os textos aparecem na seguinte ordem Dados Montagem hunidade 0150 0160 Na linha seis da primeira à quarta coluna os textos Dados Expedição hunidade e 0018 0018 Na linha sete da primeira à quarta coluna os textos Cálculos Margem unitária R Unidade 18750 10779 Na linha oito da primeira à quarta coluna os textos Cálculos Margem total Milhares de R 134996 32920 Na linha nove da primeira à quarta coluna os textos Cálculos Mercado potencial Milhares de unidades 1440 764 Na linha dez 148 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II da primeira à quarta coluna os textos Cálculos Custo R Unidade 19139 26327 Na linha onze da primeira à quarta coluna os textos Cálculos Demanda da empresa Milhares de unidades 720 305 Na linha doze da primeira à quinta coluna os textos Na linha treze da primeira à quarta coluna os textos Soma e Capacidade disponível Na linha quatorze da primeira à quinta coluna os textos Restrições Montagemh 2250 1018 3268 4160 Na linha quinze da primeira à quarta coluna os textos Capacidade produção EmbalagemExpedição h 270 115 385 416 Observe que embora os custos sejam significativamente diferentes entre ambos os modelos de aparelhos celulares o preço de venda sugerido é parecido o que não é intuitivo em um primeiro momento A preocupação da administração em relação à capacidade de produção também se mostrou infundada tendo em vista que há capacidade excedente COLIN 2017 É interessante notar que assim como os outros modelos apresentados esse modelo é uma ferramenta poderosa de análise de sensibilidade Por exemplo a administração pode reduzir imediatamente a capacidade alocada para esses produtos até um nível que não comprometa a margem Para mais detalhes sobre programação quadrática assista ao vídeo a seguir e aprenda sobre o método de Programação Quadrática GRG pelo Solver httpsyoutubejxSyvA6vbGw 113 PROBLEMA DA OTIMIZAÇÃO DE CARTEIRAS Analistas de bancos e investidores de uma forma geral estão sempre preocupados com relação a como sua carteira de ativos é alocada entre as diversas oportunidades de investimento No cerne do problema está a questão da ponderação entre risco e retorno Vamos considerar inicialmente o caso do investimento no mercado acionário COLIN 2017 Por características inerentes à gestão da empresa e ao mercado o investimento em algumas ações é mais arriscado do que em outras Na teoria financeira o risco está associado não só ao perigo de perda mas também à 149 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 oportunidade de ganho Quando dizemos que uma ação é mais arriscada do que outra estamos querendo dizer que a esperança do retorno associado à empresa possui maior variabilidade COLIN 2017 Por exemplo por resultados passados podemos dizer que empresas do ramo de eletricidade são menos arriscadas do que empresas do ramo de entretenimento FIGURA 5 MERCADO DE AÇÕES Fonte Pixabay 2022 PraCegoVer a imagem representa um homem segurando um celular e mostrando as movimentações financeiras do mercado de ações E como plano de fundo há outro gráfico de movimentação na bolsa de valores Como existe uma grande diversidade de ações para se investir mais de 400 só no Brasil o administrador de carteira está interessado em definir a alocação do capital da carteira de modo que o retorno seja máximo com um risco mínimo A noção de que um maior risco leva ou deve levar a um maior retorno é quase que intuitiva e se não fosse assim não faria sentido Portanto os objetivos de se aumentar retorno e diminuir risco são conflitantes e consequentemente não podemos otimizar ambos ao mesmo tempo COLIN 2017 Dessa forma convencionalmente o administrador pode formular seu problema em um dos dois seguintes formatos maximizar o retorno considerando um nível máximo de risco a ser assumido minimizar o risco considerando uma rentabilidade mínima a ser obtida Do ponto de vista teórico os dois problemas são equivalentes desde que 150 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II parâmetros compatíveis sejam usados em ambas as formulações Considere uma carteira com n ativos e que um ativo qualquer seja representado por 1 2 j j n Cada ativo j isto é cada ativo j da carteira tem um peso wj que representa a sua participação na carteira e a soma de todos os pesos dos ativos deve ser 100 ou seja 1 1 n j wj Eq 11 Para rj o retorno do ativo j o retorno da carteira r pode ser definido como a média ponderada dos retornos dos ativos Matematicamente 1 n j j j r w r Eq 12 Há várias medidas de risco que poderíamos usar mas uma das mais tradicionais é a variância A variância de uma carteira com dois ativos é dada por 2 2 1 1 2 2 1 1 1 2 2 2 1 2 1 2 2 1 2 1 var w r w r w cov r r w cov r r rr cov r r r rcov r r Em que cov representa a covariância entre os dois ativos Sabendo que j j j cov r r var r e i j j i cov r r cov r r a expressão pode ser simplificada para 1 1 2 2 1 2 2 1 2 var w r w r var r var r cov r r Para o caso mais genérico de uma carteira com n ativos a variância do retorno é dada por 1 1 n n j j i j i j j i j var w r cov r r w w Eq 13 Acesse o link a seguir e veja um exemplo que ilustra o caso de problema de otimização de carteiras de ativos httpsintegradaminhabibliotecacombrreader books88597014488epubcfi6745B3Bvndvst idref3Dchapter235D41482 151 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Problema Théo opera diariamente no home broker e quer escolher uma nova carteira de investimentos que minimize seu risco medido pela variância da carteira Para isso Théo escolheu cinco investimentos possíveis e avaliou o retorno mensal de cada um nos últimos 12 meses conforme a Tabela 2 Esperase um limite mínimo de retorno mensal da carteira no valor de 095 Formule o problema do investidor Théo FIGURA 6 RETORNO MENSAL DE CADA ATIVO NOS ÚLTIMOS 12 MESES Fonte Fávero 2012 p 458 PraCegoVer a imagem representa uma tabela Na primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Ativo 1 Ativo 2 Ativo 3 Ativo 4 e Ativo 5 Na segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Janeiro 213 219 426 356 e 129 Na terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Fevereiro 305 290 089 229 e 023 Na quarta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Março 062 489 096 016 e 189 Na quinta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Abril 001 080 027 077 e 203 Na sexta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Maio 280 092 142 129 e 014 Na sétima linha da primeira à sexta coluna os textos aparecem na seguinte ordem Junho 260 132 433 402 e 006 Na oitava linha da primeira à sexta coluna os textos aparecem na seguinte ordem Julho 160 302 079 087 e 097 Na nona linha da primeira à sexta coluna os textos aparecem na seguinte ordem Agosto 322 171 061 031 e 012 Na décima linha da primeira à sexta coluna os textos aparecem na seguinte ordem Setembro 223 123 242 202 e 198 Na décima primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Outubro 160 152 129 229 e 145 Na décima segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Novembro 622 099 294 264 e 124 Na décima terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Dezembro 008 398 008 114 e 107 152 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Solução As variáveis de decisão do modelo são 1x porcentagem do capital investido no ativo 1 2x porcentagem do capital investido no ativo 2 5x porcentagem do capital investido no ativo 5 FIGURA 7 REPRESENTAÇÃO EM EXCEL DO PROBLEMA DA EMPRESA MDC PACTUAL Fonte Fávero 2012 p 458 PraCegoVer a tabela Quadro de valores da solução do problema tem treze linhas e seis colunas Na primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Ativo 1 Ativo 2 Ativo 3 Ativo 4 e Ativo 5 Na segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Janeiro 213 219 426 356 e 129 Na terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Fevereiro 305 290 089 229 e 023 Na quarta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Março 062 489 096 016 e 189 Na quinta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Abril 001 080 027 077 e 203 Na sexta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Maio 280 092 142 129 e 014 Na sétima linha da primeira à sexta coluna os textos aparecem na seguinte ordem Junho 260 132 433 402 e 006 Na oitava linha da primeira à sexta coluna os textos aparecem na seguinte ordem Julho 160 302 079 087 e 097 Na nona linha da primeira à sexta coluna os textos aparecem na seguinte ordem Agosto 322 171 061 031 e 012 Na décima linha da primeira à sexta coluna os textos aparecem na seguinte ordem Setembro 223 123 242 202 e 198 Na décima primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Outubro 160 152 129 229 e 145 Na décima segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Novembro 622 099 294 264 e 124 Na décima terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Dezembro 008 398 008 114 e 153 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 107 Na linha 17 apresenta a média para os Ativo 1 Ativo 2 Ativo 3 Ativo 4 e Ativo 5 Com os valores 089 001 115 105 e 097 respectivamente Na linha 19 tem o Capital investido de 100 Na linha 21 retorno da carteira com valor maior ou igual a 095 Na linha 23 os textos Solução x1 x2 x3 x4 x5 e z Na linha 24 irá alocar a porcentagem investida Solver Aplicando o Solver obtemos a solução ótima A solução ótima é portanto 1 2 3 4 0 557 0 2127 5 7317 x x x x x com 0000033 z FIGURA 8 SOLUÇÃO ÓTIMA OBTIDA PELO SOLVER PARA O PROBLEMA DA CORRETORA MDC PACTUAL Fonte Fávero 2012 p 460 PraCegoVer a imagem representa uma tabela Na primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Ativo 1 Ativo 2 Ativo 3 Ativo 4 e Ativo 5 Na segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Janeiro 213 219 426 356 e 129 Na terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Fevereiro 305 290 089 229 e 023 Na quarta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Março 062 489 096 016 e 189 Na quinta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Abril 001 080 027 077 e 203 Na sexta linha da primeira à sexta coluna os textos aparecem na seguinte ordem Maio 280 092 142 129 e 014 Na sétima linha da primeira à sexta coluna os textos aparecem na seguinte ordem Junho 260 132 433 402 e 006 Na oitava linha da primeira à sexta coluna os textos aparecem na seguinte ordem Julho 160 302 079 087 e 097 Na nona linha da primeira à sexta coluna os textos aparecem na seguinte ordem Agosto 322 171 061 031 e 012 Na décima linha da primeira à sexta coluna 154 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II os textos aparecem na seguinte ordem Setembro 223 123 242 202 e 198 Na décima primeira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Outrubro 160 152 129 229 e 145 Na décima segunda linha da primeira à sexta coluna os textos aparecem na seguinte ordem Novembro 622 099 294 264 e 124 Na décima terceira linha da primeira à sexta coluna os textos aparecem na seguinte ordem Dezembro 008 398 008 114 e 107 Na linha 17 apresenta a média para os Ativo 1 Ativo 2 Ativo 3 Ativo 4 e Ativo 5 Com os valores 089 001 115 105 e 097 respectivamente Na linha 19 tem o Capital investido de 100 Na linha 21 retorno da carteira com valor maior ou igual a 095 Na linha 23 os textos Solução x1 x2 x3 x4 x5 e z Na linha 24 irá alocar a porcentagem investida 000 557 000 2127 7317 e 0000033 12 CASOS EM PROGRAMAÇÃO NÃO LINEAR Os temas abordados neste tópico são todos casos baseados em situações reais de modo que eles irão auxiliar na compreensão da aplicação da PNL em diferentes situações 121 DEFINIÇÃO DO TAMANHO E ALOCAÇÃO DE FORÇA DE VENDAS Vamos iniciar nossos estudos por meio de um estudo de caso a Scorp iniciou suas atividades em 1940 nos EUA preparando medicamentos dermatológicos Algum tempo depois começou a oferecer produtos de controle da natalidade e desde então diversificou ainda mais suas especialidades de atuação Suas vendas em 1981 foram de US710 milhões com um lucro líquido de US98 milhões O CAGR Compound Annual Growth Rate taxa composta de crescimento anual ou crescimento médio foi de 23 entre 1971 e 1981 Até a década de 1990 quando foi vendida a Scorp possuía operações relevantes em diversos países mas em especial nos EUA COLIN 2017 A Scorp tinha operações de desenvolvimento manufatura marketing e vendas de medicamentos A Scorp Laboratories subsidiária norteamericana da Scorp fabricava e comercializava produtos farmacêuticos para a saúde humana 155 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Em 1982 a linha de produtos da Scorp era composta de sete principais produtos Medicamento 1 antirreumatoide Medicamento 2 analgésico Medicamento 3 anticoncepcional oral e Medicamento 4 Medicamento 5 e Medicamento 6 usados no tratamento de inflamação de pele Medicamento 1 era o produto mais importante da Scorp e era o 3º antirreumatoide mais vendido nos EUA COLIN 2017 FIGURA 9 LINHA DE PRODUTOS DA SCORP Fonte Adaptado dePixabay 2022 PraCegoVer a imagem representa a foto de medicamentos enumerados de 1 a 6 indicando todos os medicamentos produzidos pela Scorp O marketing e as vendas de produtos Scorp eram feitos da mesma forma que nos outros laboratórios e da mesma forma que ainda são feitos hoje em dia para produtos de prescrição Os elementos de marketing são força de vendas propagandas em revistas médicas malas diretas amostras e participações em congressos médicos COLIN 2017 O trabalho da força de vendas é visitar o médico e fazer apresentações sobre produtos da empresa que ele representa Há uma segmentação dos médicos de acordo com algum critério como sua especialidade por exemplo e uma força de vendas específica é encarregada de atendêlo As apresentações 156 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II duram um pouco mais de um minuto em que o propagandista ou representante faz a apresentação de dois ou três produtos COLIN 2017 Problema no final de 1981 a alta administração da Scorp Laboratories sentiu a necessidade de uma abordagem de prazo mais longo para analisar o tamanho da força de vendas Na época a força de vendas aumentava em 30 ou 40 propagandistas a cada ano de forma intuitiva a mesma forma que grande parte das empresas farmacêuticas ainda faz Em resumo a administração da Scorp Laboratories desejava uma abordagem de prazo mais longo para a definição do tamanho ideal da força de vendas enquanto a administração corporativa desejava uma análise mais cuidadosa e completa para avaliar grandes investimentos Em termos de programação matemática considere que a empresa queira maximizar seu lucro variando a força de vendas e sua alocação COLIN 2017 Solução o departamento de pesquisa de mercado da Scorp buscou na literatura referências para ajudálos na tarefa Encontraram estudos que sugeriram uma nova abordagem baseada na criação de modelos para resolver o problema Em linhas gerais modelos dessa área tentam identificar como as vendas variam dada uma variação no esforço relacionado com elas COLIN 2017 Após chegarem a um consenso a respeito do que dispunham para resolver o problema eles resolveram utilizar a técnica Delphi para estimar a função de resposta de vendas A teoria de marketing indica que curvas de respostas dessa classe são do tipo S em que há vendas para zero de esforço e um limite máximo de vendas mesmo que o esforço aumente muito A Figura 7 mostra um exemplo de curva desse tipo No esforço equivalente a 100 as vendas são 100 e representam respectivamente o esforço atual de vendas e as vendas efetivas COLIN 2017 157 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 FIGURA 10 EXEMPLO DE UMA CURVA DE RESPOSTA ESFORÇO DE VENDAS Fonte Colin 2017 p 365 PraCegoVer a figura representa o desenho da curva com eixos x e y Os valores sobre o eixo x são dermatologia 0 50 100 150 200 e 250 Os valores sobre o eixo y são vendas 0 25 50 75 100 e 150 A curva começa de forma exponencial no ponto 025 e cresce da esquerda para a direita O ponto mínimo 025 representa a A ausência de esforço de vendas promove vendas nos curto e médio prazos O ponto máximo 250125 representa a As vendas convergem para um valor máximo mesmo que o esforço de vendas seja aumentado significativamente Agora você pode continuar resolvendo este problema Para isso acesse o link a seguir httpsintegradaminhabibliotecacombrreader books9788597014488epubcfi6785B3Bvnd vstidref3Dchapter255D4422405181 158 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II 122 MAXIMIZAÇÃO DE MARGEM EM UMA EMPRESA DE TRADING Para compreendermos este assunto vamos estudálo por meio de um estudo de caso Mercado Sucroalcooleiro Mundial o Brasil tem sido um ator importante no mercado açucareiro desde a época colonial Mais recentemente desde a criação do próetanol na década de 1970 o Brasil tem se destacado na produção sucroalcooleira mundial A Figura 8 apresenta os principais produtores importadores e exportadores de açúcar em 2000 Observe que o Brasil é responsável por quase 50 das exportações de açúcar do mundo COLIN 2017 FIGURA 11 PRINCIPAIS PRODUTORES IMPORTADORES E EXPORTADORES DE AÇÚCAR NO MUNDO EM 2000 Fonte Adaptado de Colin 2017 p 367 PraCegoVer a figura representa um gráfico de barras com as informações de Produção Importação e Exportação para cada um dos seguintes países EUA UE Cuba México Brasil Índia Rússia China Tailândia Austrália e Outros Para os EUA os valores 8 2 e 0 são correspondentes a Produção Importação e Exportação respectivamente Para UE os valores 19 4 e 7 são correspondentes a Produção Importação e Exportação respectivamente Para CUBA os valores 4 0 e 3 são correspondentes a Produção Importação e Exportação respectivamente Para México os valores 5 0 e 1 são correspondentes a Produção Importação e Exportação respectivamente Para Brasil os valores 20 0 e 12 são correspondentes a Produção Importação e Exportação respectivamente Para Índia os valores 20 0 e 0 são correspondentes a Produção Importação e Exportação respectivamente Para Rússia os valores 0 5 e 0 são correspondentes a Produção Importação e Exportação respectivamente Para 159 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 China os valores 8 1 e 0 são correspondentes a Produção Importação e Exportação respectivamente Para Tailândia os valores 6 0 e 3 são correspondentes a Produção Importação e Exportação respectivamente Para Austrália os valores 5 0 e 4 são correspondentes a Produção Importação e Exportação respectivamente Para Outros os valores 41 26 e 10 são correspondentes a Produção Importação e Exportação respectivamente A evolução do etanol como um combustível alternativo tem sido impulsionada especialmente pelas exigências do Protocolo de Kyoto que estabelece regulamentações mais severas relativas à emissão de poluentes COLIN 2017 A empresa descrita neste caso é uma grande produtora e comercializadora de açúcar e etanol Planejamento o principal critério de planejamento da empresa é a quantidade de canadeaçúcar a ser plantada A decisão de plantio é importante porque o ciclo produtivo é completado em seis anos em média Ou seja uma decisão de expansão ou retração da capacidade produtiva em um ano terá impacto por outros cinco anos À medida que sabemos a quantidade de cana plantada e consequentemente a ser colhida conseguimos ter uma noção do volume de produtos finais açúcar e etanol por meio do uso de uma estimativa do seu ART Açúcares Redutores Totais Contexto fazendo um esforço como grande parte das maiores empresas desde meados da década de 1990 a empresa estava implantando o módulo SOP do sistema de gestão SAP R3 Em uma dada fase da implantação do sistema a consultoria contratada para a realização da implantação decidiu que seria necessário um modelo de suporte que pudesse fazer a otimização de margens da empresa O interesse era otimizar margens atendendo às previsões de demanda e às chamadas macrorrestrições que se referiam às capacidades dos grandes processos da empresa COLIN 2017 160 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II FIGURA 12 MÓDULOS DO SAP R3 Fonte Elaborado pela autora 2022 PraCegoVer a figura representa o desenho dos módulos de SAP R3 que são dispostos formando um losango em que no centro tem a sigla SAP e nos lados do losango quadrados que indicam os elementos do SAP são eles PP produção MM materiais SD vendasdistribuição QM qualidade PM manutenção HR Recursos humanos PS projetos AA ativos fixos CO controladoria e FI gestão financeira Modelo o interesse da empresa é definir um plano de produção estocagem e vendas que otimize margens considerando as capacidades de processamento armazenagem carregamento etc A empresa é consciente de que seu tamanho e sua importância são mais do que suficientes para influenciar o mercado isso levando em conta que os produtos fabricados são commodities COLIN 2017 Mais especificamente a empresa deseja maximizar sua margem de contribuição que é definida como preço líquido de vendas menos custos variáveis de vendas e produção e menos os custos de armazenagem externa e de retirada do estoque Além disso dada a grande taxa de juros aproximadamente 20 ao ano a empresa deseja maximizar o valor presente da margem considerando que a taxa de descontos seja igual à taxa de juros Para a solução do problema devese considerar que os resultados do primeiro trimestre já são descontados LACHTERMACHER 2021 161 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 As restrições básicas relacionadas com a capacidade de processamento e produção são descritas a seguir Capacidade de carregamento De navios Capacidade de produção De açúcar Capacidade de produção De etanol anidro Capacidade de produção De etanol hidratado Capacidade de armazenagem De açúcar para o mercado interno Capacidade de armazenagem De açúcar para o mercado externo Capacidade de armazenagem De etanol para o mercado interno Capacidade de armazenagem De etanol para o mercado externo 162 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II Além das capacidades outras restrições precisam ser atendidas Toda canadeaçúcar programada para colheita deve ser usada na produção dos produtos Equações de equilíbrio de estoque estoques nunca podem ser negativos Preços de venda devem estar dentro da faixa estabelecida pelos preços máximo e mínimo A empresa começou o primeiro trimestre do horizonte de planejamento sem nenhum estoque Solução uma sugestão de solução do problema descrito é iniciála com o desenho de um fluxo de produtos para os diversos estágios de produção e estocagem Considere que os diferentes mercados podem ser abastecidos com produtos provenientes tanto do estoque como diretamente da produção FÁVERO 2012 Agora é a hora de você colocar a mão na massa analise e responda as questões a seguir e você será capaz de compreender este estudo de caso Análise do problema Pela descrição do caso qual parece ser a técnica mais apropriada para se fazer o planejamento agregado da empresa Modelagem Dois pontos são suficientes para estabelecer a equação de uma reta Defina matematicamente as equações que regem os comportamentos de preços e quantidades de produtos Variáveis de decisão Para o problema em consideração identifique as variáveis de decisão Desenhe o fluxo de produtos para os estágios da cadeia produtiva abastecimento de canadeaçúcar e processamento da mesma e da distribuição 163 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 Solução computacional Implante o modelo no computador e resolva Qual a margem de contribuição total na solução ótima 123 ESCOAMENTO DE GRÃOS Iniciemos nossa discussão com um estudo de caso o trigo na Australia é um produto homogêneo plantado em regiões geográficas distintas e alocado a diversas regiões de demanda classificadas de acordo como uso final requerido para esse grão Basicamente a diferença entre os preços de oferta e demanda é devida aos custos de transporte e armazenagem Para cada região funções que relacionam produção local demanda final e preços podem ser derivadas LACHTERMACHER 2021 Dadas essas funções e os respectivos custos do sistema de distribuição envolvido é possível determinar os preços de equilíbrio em todos os segmentos de mercado assim como a quantidade de trigo demandada e ofertada em cada região Podem também ser obtidos o volume e a direção das quantidades de trigo transportadas entre cada par de regiões que maximizem o lucro de cada fonte de produção permitindo assim a distribuição de trigo a um custo mínimo O modelo de equilíbrio espacial foi escolhido e apresentou as seguintes vantagens a é uma generalização do modelo de transporte no sentido de que os resultados obtidos com um modelo de transporte podem também ser reproduzidos pelo modelo de equilíbrio espacial b possibilita a inclusão das elasticidades preços de oferta e demanda já estimadas para a indústria de trigo australiana o que facilitaria uma avaliação dos efeitos das mudanças no nível de produção causados pela implementação de políticas agrícolas que viessem afetar o setor c pode ser estendido para permitir a inclusão de funções de custo de distribuição baseadas em funções de oferta não perfeitamente elásticas d sua estrutura poderia ser modificada para que imperfeições tais como monopólio espacial ou mercados oligopolisticos pudessem ser incluídas 164 MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 PESQUISA OPERACIONAL II e A estrutura básica do modo de distribuição da indústria de trigo pode ser representada pela Figura 10 FIGURA 14 ESTRUTURA DO SISTEMA DE DISTRIBUIÇÃO DE TRIGO NA AUSTRALIA Armazéns Produção Estoque Inicial Oferta Consumo Humano Ração animal Exportação Estoque Final Fonte Caixeta 2004 PraCegoVer a figura representa um esquema com oito retângulos O retângulo com texto Produção liga ao retângulo com texto Armazéns que se liga ao retângulo com texto Oferta que se liga aos retângulos Consumo humano Ração animal Exportação Estoque final e Estoque inicial Para aprofundar ainda mais na solução de problemas deste tido de caso acesse o link a seguir e veja como escrever as formulações matemáticas e concluir a solução de casos deste tipo https integradaminhabibliotecacombrreader books9788522465750pageid122 165 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 CONCLUSÃO Esta unidade teve como objetivo apresentar casos reais em que a programação não linear é colocada em prática para solução de problemas de tomada de decisão Os métodos de solução de problemas de programação não linear envolvem uma complexidade que possibilita sua aplicação desde casos de carteiras de investimentos até produção e importação de produtos agrícolas A programação quadrática é um tipo de especial de programação não linear em que a funçãoobjetivo é uma função quadrática e as restrições podem assumir características lineares o que a torna especialmente interessante e aplicável Os casos discutidos nesta unidade servem como referência e embasamento para desenvolvimento e aplicação da programação não linear e seus algoritmos para solução de problemas reais nas mais variadas vertentes do mercado Esta disciplina foi direcionada para proporcionar o entendimento de como a PO surgiu seus objetivos como ciência multidisciplinar o que são modelos como são classificados e quais são as etapas de um processo de resolução de problemas Foi importante inserir você no contexto das decisões demonstrando que decidir é uma atividade rotineira e não menos relevante foi descrever os precedentes históricos que instituíram a PO como um campo da ciência O processo de resolução de problemas na PO ocorre com a motivação de otimizar processos o uso da PL e PNL por meio de modelagem com as planilhas eletrônicas mostra a eficiência dos métodos em problemas reais que foram aqui simulados por situações hipotéticas Foi demonstrado como o recurso gerenciador de cenários do software Microsoft Excel pode ser empregado na modelagem e na resolução de um problema Enfatizouse os modelos de PL o significado do termo linearidade e a estrutura algébrica de um modelo de PL também se apresentou os esquemas de algoritmo para os tipos de problemas mais usuais de aplicação da PL Discutimos os tipos de PNL enfatizando seus aspectos importantes vimos a programação côncava e convexa programação separável e quadrática Discutimos estudos de casos que evidenciaram a aplicação real da PNL de forma prática Por fim esta disciplina servirá de aporte para o desenvolvimento profissional e pessoal durante sua trajetória acadêmica e profissional 166 PESQUISA OPERACIONAL II MULTIVIX EAD Credenciada pela portaria MEC nº 767 de 22062017 Publicada no DOU em 23062017 REFERÊNCIAS ANDRADE E L Introdução à Pesquisa Operacional método e modelos para análise de decisões 5 ed Grupo GEN 2015 BOAVENTURA NETTO P O JURKIEWICZ S Grafos introdução e prática São Paulo Blucher 2017 COLIN C E Pesquisa Operacional 170 aplicações em estratégia finanças logística produção marketing e vendas 2 ed Rio de Janeiro Atlas 2017 FÁVERO L P Pesquisa Operacional para cursos de Administração São Paulo LTC 2012 GOLDBARG M Grafos conceitos algoritmos e aplicações São Paulo LTC Grupo GEN 2012 GOLDBARG M Programação Linear e Fluxos em Redes São Paulo Elsevier 2014 GOLDBARG M GOLDBARG E Grafos São Paulo LTC 2012 HILLIER F S Introdução à pesquisa operacional 9 ed São Paulo McGRAWHILL EDUCATION 2013 LACHTERMACHER G Pesquisa Operacional na tomada de decisões 5 ed São Paulo LTC 2021 LOESCH C HEIIN N Pesquisa Operacional fundamentos e modelos São Paulo Saraiva 2008 MORETIN P A Análise de séries temporais modelos lineares univariados 3 ed v 1 São Paulo Edgard Blücher 2018 MORETIN P A Análise de séries temporais modelos lineares univariados v 1 3 ed São Paulo Edgard Blücher 2018 NICOLETTI M C HRUSCHKA JÚNIOR E R Fundamentos da Teoria dos Grafos para Computação São Paulo LTC 2017 SZWARCFITER J L Teoria Computacional de Grafos os algoritmos Rio de Janeiro Elsevier 2018 EADMULTIVIXEDUBR CONHEÇA TAMBÉM NOSSOS CURSOS DE PÓSGRADUAÇÃO A DISTÂNCIA NAS ÁREAS DE SAÚDE EDUCAÇÃO DIREITO GESTÃO E NEGÓCIOS