ApostilaINF280

Universidade Federal de Viçosa Departamento de Informática Prof. Mauro Nacif Rocha Prof. Luiz Aurélio Raggi Prof. Heleno do Nascimento Santos INF-280 Pesquisa Operacional I Conteúdo: Programação Linear Programação em Redes Fevereiro de 2005 ASPECTOS GERAIS DA PESQUISA OPERACIONAL ........................................................................................ 1 EXEMPLOS DE ALGUNS PROBLEMAS COMUNS DA P.O............................................................................................... 5 PARTE I – PROGRAMAÇÃO LINEAR ................................................................................................................. 8 EXEMPLOS DE MODELOS PARA ALGUNS PROBLEMAS CLÁSSICOS DE PROGRAMAÇÃO LINEAR .................................. 13 PROBLEMAS PARA MODELAGEM ............................................................................................................................ 17 SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR – INTERPRETAÇÃO GEOMÉTRICA ...................................... 19 CASOS ENCONTRADOS NA RESOLUÇÃO GRÁFICA ................................................................................................... 23 O MÉTODO SIMPLEX.......................................................................................................................................... 27 MODELO MATEMÁTICO E FORMA PADRÃO DE UM PPL............................................................................................. 27 DEFINIÇÕES BÁSICAS ............................................................................................................................................. 30 TEOREMAS FUNDAMENTAIS ................................................................................................................................... 35 O ALGORITMO SIMPLEX ........................................................................................................................................ 37 ALGORITMO SIMPLEX – MÉTODO DAS DUAS FASES ................................................................................................ 47 ELEMENTOS DE PÓS-OTIMIZAÇÃO................................................................................................................ 53 MUDANÇA NO VETOR C .......................................................................................................................................... 55 MUDANÇA NO VETOR B .......................................................................................................................................... 56 DUALIDADE .......................................................................................................................................................... 57 PARTE II – PROGRAMAÇÃO EM REDES......................................................................................................... 63 INTRODUÇÃO ........................................................................................................................................................ 63 INTRODUÇÃO À TEORIA DE GRAFOS ............................................................................................................ 65 UMA BREVE HISTÓRIA DA TEORIA DOS GRAFOS ..................................................................................................... 65 CONCEITOS BÁSICOS DA TEORIA DE GRAFOS .......................................................................................................... 68 FLUXOS EM REDE ............................................................................................................................................... 74 FORMULAÇÃO GERAL (CLÁSSICA) PARA PROBLEMAS DE FLUXOS EM REDE ............................................................. 75 O PROBLEMA DE FLUXO DE CUSTO MÍNIMO (PFCM).............................................................................................. 79 O PROBLEMA DE TRANSPORTE (PT) ....................................................................................................................... 87 O PROBLEMA DE DESIGNAÇÃO (PD) ...................................................................................................................... 94 O PROBLEMA DO CAMINHO MAIS CURTO (PCMC) ............................................................................................... 100 O PROBLEMA DE FLUXO MÁXIMO (PFM) ............................................................................................................. 104 O PROBLEMA DA ÁRVORE GERADORA MÍNIMA (AGM) ........................................................................................ 111 O PROBLEMA DE STEINER EM GRAFOS NÃO DIRECIONADOS .................................................................................. 115 REDES PERT / CPM ............................................................................................................................................ 117 REDES PERT....................................................................................................................................................... 117 REDES PERT/CPM.............................................................................................................................................. 121 BIBLIOGRAFIA................................................................................................................................................... 125 ii Aspectos Gerais da Pesquisa Operacional 1. Introdução e Histórico Durante a II Guerra Mundial, líderes militares da Inglaterra e dos Estados Unidos requisitaram um grupo de cientistas de diversas áreas de conhecimento para analisarem alguns problemas militares. Entre esses problemas citam-se: desenvolvimento, operação e localização de radares, gerenciamento e controle de navios de apoio, planejamento de ataques aéreos, lançamento de bombas contra submarinos, defesa das comunidades européias contra ataques aéreos inimigos, abastecimento de tropas com munições e alimentos, operações de mineração, etc. A aplicação de métodos matemáticos e científicos para ajudar as operações militares foi chamada “Operational Research” ou “Operations Research”. 1759 (Quesney), 1874 (Walras) 1873 (Jordan), 1896 (Minkowsky), 1903 (Farkas) 1920 (Markov) 192* (periódicos de negócios e engenharia industrial) 1920 (Erlang) 1937 (Von Neumann), 1939 (Kantorovich) 1938 (RAF – viabilidade dos sistemas de radar) 1940 (tomada da França pelos alemães) 1947 (Dantzig) a partir de 1947 Modelos primitivos de programação matemática. Bases matemáticas para os modelos lineares. Modelos dinãmicos. Sugestões inovadoras para controle econômico de estoques. Estudos pioneiros dos fenômenos das filas de espera. Modelos econômicos mais sofisticados. Operational Research – RESEARCH into (military) OPERATIONS Maior conquista da OR na II Guerra. Primeira formulação abstrata de um problema de programação linear. Aplicações na engenharia, economia, controle de estoque, análise de tráfego aéreo, agricultura, comunicação, planejamento rural e urbano, distribuição de energia e outros Operational Research Operations Research Obs.: U.K. / Europa: E.U.A.: 1 2. Definição “Pesquisa Operacional é o uso do método científico com o objetivo de prover departamentos executivos de elementos quantitativos para a tomada de decisões, com relação a operações sob seu controle” (Kittel, 1947). “A Pesquisa Operacional é a aplicação do método científico, por equipes multidisciplinares, a problemas envolvendo o controle de sistemas organizados de forma a fornecer soluções que melhor interessam a determinada organização” (Ackoff,1968). “Pesquisa Operacional é uma metodologia de estruturar processos aparentemente não estruturados por meio da construção de modelos. Utiliza um conjunto de técnicas quantitativas com o intuito de resolver os aspectos matemáticos dos modelos” (Ehrlich, 1991). Hoje, o termo operations research, ou pesquisa operacional, significa “um método científico para tomada de decisão, que busca determinar como melhor planejar e operar um sistema, usualmente sob condições que requerem alocação de recursos escassos”. 3. A Metodologia da Pesquisa Operacional Geralmente a atividade de uma equipe de P.O. envolve as seguintes fases: • • • • • identificação do problema; construção de um modelo; obtenção da solução; teste do modelo e avaliação da solução; implantação e acompanhamento da solução. Deve-se salientar que tais fases não são distintas, superpondo-se e interagindo entre si, na tentativa de se obter uma melhor identificação entre o modelo e o real. Quando a pesquisa operacional é usada para resolver um problema de uma organização, o seguinte procedimento, poderá ser seguido: Passo 1 - Identificação e formulação do problema Em primeiro lugar deve ser definido claramente o problema da organização, incluindo a especificação dos objetivos e as partes da organização que devem ser estudadas antes que o problema possa ser resolvido. Passo 2 - Observação do sistema Dados devem ser coletados para estimar valores de parãmetros que afetam o problema da organização. Estes valores são usados para desenvolver e avaliar o modelo matemático para o problema. Passo 3 - Formulação do modelo matemático para o problema Consiste no desenvolvimento do modelo matemático para o problema. Geralmente, existem várias técnicas que podem ser aplicadas na solução dos modelos matemáticos. A técnica adequada é selecionada em função das características do modelo representativo do problema. Algumas situações, no entanto, são tão complexas que não existem modelos analíticos tratáveis que possam repre2 sentá-las. Quando isso acontece é possível desenvolver modelos de simulação e usar a capacidade dos computadores para aproximar o comportamento desses sistemas. Passo 4 - Verificação do modelo e uso do modelo para predição Verifica-se se o modelo matemático proposto para o problema é uma representação fidedigna da realidade. Os dados coletados durante a observação do problema podem ser usados para a validação do modelo na situação corrente. Passo 5 - Selecionar uma alternativa aceitável Dado o modelo do problema e um conjunto de alternativas (soluções viáveis) deve-se escolher aquela (se existir) que melhor atende aos objetivos da organização. Em alguns casos, a seleção da melhor alternativa possível é um problema de difícil solução e, nesses casos, aceita-se uma “boa” alternativa. Passo 6 - Apresentação dos resultados e conclusões A partir da definição do modelo e das alternativas determinadas para o problema são feitas as recomendações para os gerentes das organizações para que eles possam tomar as decisões que melhor atendem os objetivos buscados. Passo 7 - Implementação e avaliação das recomendações Se a organização aceita o estudo realizado e as recomendações feitas, parte-se para a fase de implementação da solução, a qual deve ser constantemente monitorada, e atualizada dinamicamente, fazendo-se mudanças quando necessárias. 4. Áreas de aplicação Segundo trabalhos apresentados em reuniões da Sociedade Brasileira de Pesquisa Operacional (SOBRAPO), citam-se abaixo algumas áreas onde a P.O. foi aplicada com algum sucesso e onde se observa a grande variedade dessas aplicações: • • • • • • • • • • • • • • • administração agropecuária economia e planejamento econômico educação e saúde energia engenharia forças armadas investimentos e finanças localização-armazenamento-distribuição planejamento e controle da produção planejamento urbano e regional recursos hídricos siderurgia telecomunicações transporte 3 5. Técnicas aplicadas Os trabalhos de PO desenvolvidos e submetidos para apresentação em congressos e para publicação revistas científicas envolvem a utilização das seguintes técnicas: • • • • • • • • • Análise e previsão de séries temporais Controle e qualidade Estatística Teoria dos grafos Otimização Programação matemática Processos estocásticos e teorias das filas Simulação Teoria da decisão e teoria dos jogos Estas técnicas permitem que se resolva uma variedade enorme de problemas, dentre os quais são típicos: • • • • • • • • • • • Alocação de recursos Localização e distribuição da produção Estoque Substituição e reposição de equipamentos Seqüenciamento e coordenação de tarefas Determinação de caminhos em rede Situações de competição (teoria dos jogos) Busca de informação Roteamento de veículos Fluxos em rede Problemas de características híbridas 6. Surgimento e desenvolvimento da PO no Brasil O início da P.O. no Brasil se deu aproximadamente uma década após sua implantação na Grã-Bretanha e nos Estados Unidos. Assim, já nos meados da década de 50, professores com formação em Engenharia, Matemática e/ou Estatística, entusiasmados com as novas técnicas relacionadas a P.O. que aqui chegavam pela difusão natural do conhecimento humano, começaram a formar equipes de P.O. nas universidades e instituições de ensino (ITA, PUC, COPPE-UFRJ, UFPB, UNICAMP, UFSC, UFMG, UFV, etc.), reproduzindo-se e induzindo a formação de equipes em conjunto com as empresas (PETROBRÁS, ELETROBRÁS, USIMINAS, CSN, EMBRAPA, SOUZA CRUZ, TELEBRÁS, etc.), bem como a formação de consultorias nas grandes cidades. Atualmente, vê-se com certo otimismo as perspectivas da P.O. no Brasil e, em particular, na Agricultura, Sistemas de Produção e Engenharia de Alimentos, baseando-se nos seguintes fatores: • A crise como elemento propulsor (escassez de recursos); • A explosão da informática; • Massa crítica existente de analistas de P.O.; • Integração universidade × empresa; • Seminários de P.O. aplicada à agropecuária; • Existência de cursos de P.O. nas universidades brasileiras; • Cursos e pesquisas em andamento na COPPE, UNICAMP, UFPb, UFSc, EMBRAPA, etc. 4 Exemplos de Alguns Problemas Comuns da P.O. Problema do Caminho Mínimo (PCM) Objetivos: determinar a rota de menor caminho (distância, tempo ou custo) existente entre um ponto de origem (cidade, endereço, computador, objeto etc.) e um ponto de destino. Problemas de Localização de Facilidades Objetivos: determinar a localização e capacidade das facilidades (restaurantes, depósitos, antenas de rádio etc.) de forma a suprir a demanda da região toda com um custo mínimo e/ou lucro máximo (considerando um determinado período). Cada facilidade possui normalmente um custo fixo de instalação e custos variáveis de operação. Problema da Mochila Rolando Caio da Rocha, um exuberante alpinista, está se preparando para uma longa escalada nos Alpes. Ele consegue levar até W quilos em sua mochila. Ele tem N diferentes tipos de itens que pode incluir em seu fardo, e cada unidade de item j pesa wj quilos. Para cada item j, ele calculou um valor numérico Rj representando o valor de sobrevivência de cada unidade do item. Como exemplo, se ele levar cinco unidades do item 3 e sete unidades do item 9, o “valor” para ele desta seleção na mochila é 5R3 + 7R9. O problema do Rolando é escolher o número de cada tipo para incluir em sua mochila. 5 Escolha da Mistura para Rações Grão 1 Grão 2 Grão 3 Necessidades mínimas 2 3 7 1250 Nutriente A 1 1 0 250 Nutriente B 5 3 0 900 Nutriente C 0,6 0,25 1 232,5 Nutriente D 41 35 96 $/peso Objetivos: formular uma ração formada a partir da mistura dos grãos que atenda às necessidades mínimas e máximas de nutrientes e tenha um custo mínimo. Bin-packing / Cutting Stock Barra (bin) = 4100mm Demanda (mm) 3100 1930 1850 850 850 795 639 Objetivos: determinar a quantidade mínima possível de barras para que sejam cortados todos os pedaços necessários para suprir a demanda. Fornecimento de Produtos através de uma Rede de Transportes Usinas S1 Fornecimentos disponíveis S2 S3 Sm Depósitos D1 D2 Necessidades D3 de demanda Dn Objetivos: determinar a quantidade do produto que cada fornecedor deve enviar para cada depósito, de forma que o custo total do transporte seja mínimo, que cada depósito tenha sua demanda atendida, e que nenhum depósito estoure sua capacidade de fornecimento. 6 Problemas de Produção Recursos Especificações Atividades INSUMOS PRODUTOS Máquinas Produto 1 Ferramentas Produto 2 Capital Decisões . ⇔ ⇔ Matéria prima . Mão-de-obra Produto n CUSTOS RECEITA Objetivos: determinar as atividades que devem ser realizadas ou produzidas de forma a maximizar o lucro ou minimizar o custo de produção, levando-se em conta a quantidade máxima disponível para cada insumo. O Problema de Designação (caso particular do problema de transporte) Indivíduos ou máquinas (n) 1 2 3 Custos cij Tarefas a serem executadas (n) 1 2 3 Objetivos: minimizar o custo total para executar um conjunto de tarefas, onde cada tarefa deve ser executada por uma única máquina, e cada máquina executa uma única tarefa. 7 Parte I – Programação Linear 1. O significado da expressão “PROGRAMAÇÃO” ⇒ alocação de itens ou entidades “LINEAR” ⇒ relativo a funções, equações ou inequações lineares 2. O problema geral Recursos escassos devem ser repartidos entre demandas competitivas Objetivos: • Otimizar a distribuição dos recursos limitados no atendimento às demandas competitivas; • Maximizar lucros ou o uso dos recursos; • Minimizar custos, sobras, tempos ou distâncias. Decisões são interligadas na tomada de decisão Demandas competem entre si na procura dos recursos escassos ⇔ ⇔ 8 3. Fases na solução de um problema de pesquisa operacional FLUXOGRAMA FORMULAÇÃO DO PROBLEMA OBTENÇÃO DO MODELO DEFINIÇÃO DO MÉTODO DE SOLUÇÃO OBTENÇÃO E PREPARO DOS DADOS EXPERIÊNCIA RESOLUÇÃO DO PROBLEMA INTERPRETAÇÃO DOS RESULTADOS IMPLEMENTAÇÃO DA SOLUÇÃO COMPARAÇÃO COM A REALIDADE 9 4. Modelagem de problemas MODELOS SÃO REPRESENTAÇÕES DA REALIDADE GRANDE NÚMERO DE VARIÁVEIS SISTEMA SELEÇÃO DAS VARIÁVEIS PRINCIPAIS INTERRELACIONAMENTO SIMPLIFICAÇÃO DA REALIDADE MODELO 5. Modelos matemáticos Os modelos matemáticos são modelos simbólicos - o sistema real é representado por EQUAÇÕES E EXPRESSÕES MATEMÁTICAS que descrevem suas propriedades relevantes. n DECISÕES QUE SÃO QUANTIFICÁVEIS E INTERRELACIONADAS REPRESENTA A MEDIDA DE EFICIÊNCIA DO SISTEMA SÃO RESTRIÇÕES AOS VALORES DAS VARIÁVEIS DE DECISÃO n VARIÁVEIS DE DECISÃO (x1, x2, … , xn) FUNÇÃO OBJETIVO Z = f(x1, x2, … , xn) REPRESENTADAS POR EQUAÇÕES OU INEQUAÇÕES MATEMÁTICAS É A REALIDADE VALIDADE ASSOCIADA AO GRAU DE CORRELAÇÃO É UMA APROXIMAÇÃO 10 6. Expressão matemática de um modelo de programação linear OBJETIVO Determinar os valores das variáveis x1, x2, … , xn que otimizam (maximizam ou minimizam) a função linear Z = c1 x1 + c2 x2 + … + cn xn, obedecendo às seguintes RESTRIÇÕES: + a1nxn ≤, =, ≥ + a2nxn ≤, =, ≥ + amnxn ≤, =, ≥ a11x1 a21x1 am1x1 + + a12x2 a22x2 + + + + am2x2 … … … … b1 b2 bm e de forma que as variáveis sejam NÃO NEGATIVAS, ou seja: xn ≥ 0, xn ≥ 0, … xn ≥ 0. Temos que cj, aij e bi são constantes conhecidas, para todo i e todo j. Os parãmetros e variáveis do modelo são: Z xj cj bi aij n m Medida de eficiência do sistema (chamada de Função Objetivo ou F.O.); Nível da atividade j (variável de decisão); Taxa de contribuição unitária da atividade j; Disponibilidade do recurso i; Coeficiente tecnológico (quantidade i / consumido por j) Número de atividades no modelo; Número de restrições no modelo. 7. Construção de um modelo de programação linear ETAPAS A SEGUIR PARA CONSTRUIR UM MODELO DE PL 1. Definição das atividades Definir as atividades (xj) e escolher uma unidade de medida para o seu nível. 2. Definição dos recursos Determinar os recursos consumidos e escolher a unidade de medida conveniente. 3. Determinação das condições externas Determinar a quantidade de recurso disponível (bi). 4. Cálculo dos coeficientes insumo/produção Determinar a relação entre atividades e recursos (aij). 11 5. Construção do modelo Associar x1, x2, … , xn às n atividades; Escrever as equações de balanceamento por recurso; Indicar o uso dos recursos; Estabelecer a função objetivo como medida de eficiência. 12 Exemplos de Modelos para Alguns Problemas Clássicos de Programação Linear Escolha da Mistura para Rações Grão 1 2 1 5 0,6 41 Grão 2 3 1 3 0,25 35 Grão 3 7 0 0 1 96 Necessidades mínimas 1250 250 900 232,5 Nutriente A Nutriente B Nutriente C Nutriente D $/kg Seja: x1 = qtde. (kg) do Grão 1 usada na ração x2 = qtde. (kg) do Grão 2 usada na ração x3 = qtde. (kg) do Grão 3 usada na ração Custo total da ração: 41x1 + 35x2 + 96x3 Para atender às necessidades mínimas para cada nutriente, devemos ter: 2x1 x1 5x1 0,6x1 + 3x2 + x2 + 3x2 + 0,25x2 + 7x3 ≥ ≥ ≥ ≥ 1250,0 250,0 900,0 232,5 (Nutriente A) (Nutriente B) (Nutriente C) (Nutriente D) + x3 Queremos obter uma ração que tenha um custo mínimo. Portanto, o modelo completo fica assim: Minimizar Sujeito a: 2x1 x1 5x1 0,6x1 e: + 3x2 + x2 + 3x2 + 0,25x2 + 7x3 ≥ ≥ ≥ ≥ 41x1 + 35x2 + 96x3 (Função Objetivo ou F.O.) (Restrições) 1250,0 250,0 900,0 232,5 (Nutriente A) (Nutriente B) (Nutriente C) (Nutriente D) + x3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 13 Problema de Produção A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três seções de produção: Seção de Serralharia: para produzir as estruturas de alumínio Seção de Carpintaria: para produzir as estruturas de madeira Seção de Vidro e Montagem: para produzir vidro e montar as portas e janelas Devido à diminuição dos lucros, o gerente geral decidiu reorganizar a produção, e propõe produzir só 2 produtos que têm uma melhor aceitação entre os clientes. Estes produtos são: Produto 1: uma porta de vidro com estrutura de alumínio Produto 2: uma janela grande com estrutura de madeira O Departamento de Marketing concluiu que a empresa pode vender tanto de qualquer dos dois produtos, tendo em conta a capacidade de produção disponível. Como ambos os produtos partilham a capacidade de produção da seção 3, o dono solicitou ao gerente de produção da empresa a resolução deste problema. O gerente então levantou os seguintes dados: a capacidade de produção por minuto de cada seção, a ser utilizada para produzir uma unidade de cada produto os lucros unitários para cada produto Capacidade por unidade de produção Seção Nº 1 2 3 Lucro unitário (em R$) Produto 1 1 0 3 3 Produto 2 0 2 2 5 Capacidade disponível 4 12 18 Modelo completo: Maximizar Z = 3x1 + 5x2, sujeito a x1 2x 2 3x1 + 2x 2 ≤ 4 ≤ 12 ≤ 18 x1 ≥ 0, x2 ≥ 0 14 Problema da Mochila Rolando Caio da Rocha, um exuberante alpinista, está se preparando para uma longa escalada nos Alpes. Ele consegue levar até W quilos em sua mochila. Ele tem N diferentes tipos de itens que pode incluir em seu fardo, e cada unidade de item j pesa wj quilos. Para cada item j, ele calculou um valor numérico Rj representando o valor de sobrevivência de cada unidade do item. O problema do Rolando é escolher o número de cada tipo para incluir em sua mochila. Modelo: F.O.: Max. R1x1 + R2x2 + ... + Rjxj + ... + RNxN s.a.: w1x1 + w2x2 + ... + wjxj + ... + wNxN ≤ W xj ≥ 0 ou: Max. ∑R x j=1 j N N j s.a.: ∑w x j j =1 j ≤W xj ≥ 0 15 Cutting Stock Tamanho (mm) Quantidade 3100 26 1530 71 850 47 Tamanho da Barra: 6000 mm Temos então as seguintes possibilidades de corte: x1 x2 x3 x4 x5 x6 Demanda 1 1 0 0 0 0 26 1 0 3 2 1 0 71 1 3 1 3 5 7 47 520 350 560 390 220 50 3100 1530 850 Sobra: Sendo NB = No total de barras de 6000 mm que serão cortadas, xj = No de barras de 6000 mm que serão cortadas segundo o padrão de corte j, F.O.: Min. NB = x1 + x2 + x3 + x4 + x5 + x6 s.a.: x1 + x2 x1 + 3x3 + 2x4 + x5 x1 + 3x2 + x3 + 3x4 + 5x5 + 7x6 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0 Se: ≥ ≥ ≥ 26 71 47 aij = No de pedaços de tamanho i que serão cortados no padrão j, bi = demanda de pedaços i, m = No de tamanhos diferentes (linhas), n = No de padrões de corte diferentes (colunas). Min. NB = s.a. ∑x j =1 n j =1 n j ∑a x ij j ≥ bi , i = 1, 2, ..., m xj ≥ 0 e inteiro, j = 1, 2, ..., n 16 Problemas para Modelagem Problema de Produção e Alocação de Recursos Um fazendeiro deseja determinar que área de sua propriedade deve plantar milho e feijão para maximizar o seu lucro, e informa o seguinte: a) o fazendeiro dispõe de uma área máxima de 8 alqueires para o plantio das 2 culturas, 100 m3 de água para irrigação por semana, e a semente de feijão lhe permite um plantio de 4 alqueires no máximo; b) o lucro por alqueire plantado com milho é de R$200,00 e plantado com feijão é de R$150,00; c) cada alqueire plantado com milho requer 10m3 de água por semana, e com feijão 20m3 ; d) por questões pessoais, ele deseja plantar no máximo 2/3 da área total com milho. Formule o problema como um PPL. Problema de Alocação de Recursos Em uma determinada repartição, existem m máquinas disponíveis para realizar determinadas tarefas ou fabricar determinados produtos. Cada máquina, devido à idade e ao fabricante, pode ser mais ou menos adequada que as outras para fabricar um determinado produto, bem como ter um custo de operação próprio (consumo de energia, manutenção etc.). Seja: n o número de produtos que precisam ser fabricados nessas máquinas, dij o tempo necessário para fabricar o produto j na máquina i, xij o número de unidades de j produzido na máquina i, ai o tempo disponível para a máquina i, bj o número de unidades de j que precisam ser produzidos, e cij o custo para fabricar uma unidade do produto j na máquina i. Modele este PPL de forma a obter uma produção de custo mínimo. Problema de Alocação de Transportes O expedidor de vôos, Eli Cóptero, da companhia Frete Aéreo Cauda Alta Ltda., que opera de um terminal central, tem 8 aviões do Tipo 1, 15 aviões do Tipo 2 e 11 aviões do Tipo 3 disponíveis para os vôos de hoje. A capacidade de cada avião é de 45t, 7t e 5t, respectivamente. O Sr. Cóptero deve expedir aviões para as cidades A, B e C. A quantidade mínima de cada produto que deve ser enviada para cada cidade é de 20t, 28t e 30t, respectivamente. Cada avião pode voar somente uma vez por dia. O custo de enviar um avião do terminal a cada cidade é dado pelo seguinte quadro: Tipo 1 23 58 64 Tipo 2 15 20 24 Tipo 3 1,4 3,8 4,2 Cidade A Cidade B Cidade C Denote por xij o número de aviões do tipo i enviado para a Cidade j (x1A, x1B, x1C, x2A etc.). Formule um modelo de PL para esse problema. 17 Problema de Planejamento de Tarefas Uma determinada região está sendo ameaçada pela ruptura de uma barragem e deve ser evacuada em, no máximo, 10 horas. São no total 8.000 homens, 7.900 mulheres e 1.850 crianças a transportar. Cada pessoa poderá levar até 10 quilos de bagagem pessoal, Toda a região foi isolada e só circulam veículos autorizados para que se evitem acidentes e engarrafamentos. Para efetuar a evacuação estão disponíveis os seguintes meios: Veículo de 6 ton. do Exército Quantidade de Unidades Disponíveis Capacidade de Transporte Capacidade para bagagem Custo por Viagem Tempo de Viagem 10 20 pessoas 1 ton. 10 u.m. 1h Veículo de ¼ ton. do Exército 20 5 pessoas 20 kg 4 u.m. 45 min. Veículo de Passeio 60 5 pessoas 100 kg 2 u.m. 30 min. Helicóptero Ônibus Microônibus 15 10 pessoas 50 kg 75 u.m. 10 min. 10 30 pessoas 1 ton. 5 u.m. 45 min. 5 15 pessoas 500 kg 3 u.m. 30 min. Para minimizar o pânico, as crianças deverão viajar acompanhadas por suas mães. Existem 10 famílias com 5 filhos, 25 com 4 filhos, 150 com 3, 450 com 2 e 350 com 1. Os carros de passeio só poderão fazer uma viagem de evacuação, ficando, por segurança, retidos fora da área de perigo. Formular o programa de evacuação que minimize os custos finais da operação. 18 Solução de um Problema de Programação Linear – Interpretação Geométrica Representação no espaço de soluções – duas dimensões (variáveis). Exemplo 1 (1) sujeito a: (2) (3) (4) maximizar 12x1 + 15x2 4x1 + 3x2 ≤ 12 2x1 + 5x2 ≤ 10 x1 ≥ 0 e x2 ≥ 0 Solução Ótima: ponto b, onde x1 = 15/7, x2 = 8/7 e 12x1 + 15x2 = 300/7 19 Exemplo 2 Por determinação médica, um jovem precisa fazer algum tipo de atividade física em uma academia. Por questões pessoais, ele escolheu fazer natação e/ou pólo aquático. Ele sabe que: • Uma hora de aula de natação custa R$8,00; • Uma hora de aula de pólo custa R$5,00; • Seu orçamento lhe permite dispor de 100 reais mensais para as atividades de academia; • Seus afazeres escolares lhe dão liberdade de gastar mensalmente, no máximo, 18 horas e 40.000 calorias de sua energia para essas atividades; • Cada hora de aula de pólo consome 3.300 calorias, e de natação consome 1.600 calorias; • Ele não tem preferência por nenhuma dessas duas atividades. Como ele deve planejar as suas atividades físicas para obter o número máximo de horas-aula, considerando o limite dos recursos que tem? Modele o problema como um problema de programação linear (PPL). x1 Horas-aula de natação; máx. x1 + x2 s.a.: x1 + x2 ≤ 18 8x1 + 5x2 ≤ 100 1600x1 + 3300x2 ≤ 40000 x2 (1) (2) (3) (4) Horas-aula de pólo aquático (3) (1) (2) (4) 20 Exemplo 3 Um fazendeiro deseja determinar que área de sua propriedade deve plantar milho e feijão para maximizar o seu lucro, e informa o seguinte: a) o fazendeiro dispõe de uma área máxima de 8 alqueires para o plantio das 2 culturas, 100 m3 de água para irrigação por semana, e a semente de feijão lhe permite um plantio de 4 alqueires no máximo; b) o lucro por alqueire plantado com milho é de R$200,00 e plantado com feijão é de R$150,00; c) cada alqueire plantado com milho requer 10m3 de água por semana, e com feijão 20m3 ; d) por questões pessoais, ele deseja plantar no máximo 2/3 da área total com milho. x1 x2 Qtde. de alqueires plantados com milho Qtde. de alqueires plantados com feijão máx. 200x1 + 150x2 s.a.: x1 + x2 = 8 x2 ≤ 4 x1 ≤ 16/3 10x1 + 20x2 ≤ 100 (1) (2) (3) (4) 21 Exemplo 4 Suponha que, por motivos justificáveis, uma certa dieta alimentar esteja restrita a leite desnatado e uma salada de composição bem conhecida. Sabendo-se ainda que os requisitos nutricionais serão expressos em termos de vitamina A e cálcio e controlados por suas quantidades mínimas (em miligramas). A tabela abaixo resume a quantidade de cada nutriente em disponibilidade nos alimentos e a sua necessidade diária para a boa saúde de uma pessoa. Nutriente Leite (copo) Salada (500g) Requisito Nutricional Mínimo Vit. A 2 mg 50 mg 11 mg Cálcio 50 mg 10 mg 70 mg Custo/unid. R$ 2,00 R$ 1,20 sendo x1 = qtd. de leite (em copos) x2 = qtd. de salada (em porções de 500g) min s.a. 2x1 + 1,2x2 2x1 + 50x2 ≥ 11 50x1 + 10x2 ≥ 70 -----–––– –––– 22 Casos Encontrados na Resolução Gráfica Continuaremos usando aqui modelos de duas variáveis, mantendo um espaço bidimensional (plano), facilitando assim a visualização, para ilustrar todas as situações possíveis de ocorrer para um modelo de PL qualquer. 1. Uma única solução ótima. Exemplo 1: máx. x1 + x2 s.a.: 8x1 + 5x2 ≤ 100 16x1 + 33x2 ≤ 400 x2 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 F.O. (1) (2) 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 x1 (1) (2) 23 Exemplo 2: min s.a. 2x1 + 1,2x2 2x1 + 50x2 ≥ 11 50x1 + 10x2 ≥ 70 (1) (2) (2) (1) 2. Infinitas soluções ótimas. máx. 16x1 + 10x2 s.a.: 8x1 + 5x2 ≤ 100 16x1 + 33x2 ≤ 400 x2 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 x1 (1) (2) (1) (2) 24 3. Solução ótima ilimitada. Exemplo 1: max s.a. 2x1 + 1,2x2 2x1 + 50x2 ≥ 11 50x1 + 10x2 ≥ 70 (1) (2) (2) (1) Exemplo 2: max s.a. x1 – x2 2x1 – x2 ≥ 0 x2 ≤ 4 x2 (1) (2) (1) (2) x1 25 Exemplo 3: min s.a. x1 – 2x2 2x1 – x2 ≥ 0 – x1 + 2x2 ≤ 4 (1) (2) x2 (1) (2) x1 Neste caso, embora existam soluções ótimas finitas (qualquer ponto sobre a reta 2, incluindo e à direita do ponto de intercessão dessa reta com a reta 1), limitando o valor ótimo da F.O., o conjunto desses pontos não é limitado ou “fechado”. 4. Problema inviável (nenhuma solução existente). min s.a. Z = f(x1, x2) x1 + x2 ≤ 1 x1 + x2 ≥ 2 (uma função-objetivo qualquer) (1) (2) x2 (2) (1) x1 Veja que, neste caso, não existe nenhum ponto (x1, x2) no plano euclidiano que satisfaça simultaneamente as expressões (1) e (2). 26 O Método Simplex O método Simplex, desenvolvido por DANTZIG em 1956, procura, a partir de uma determinada partição da matriz A, resolver o sistema de equações Ax = b. Veremos a seguir como podemos “preparar” um modelo de PL qualquer para que seja resolvido pelo Simplex, quais os fundamentos teóricos do algoritmo, e como ele podemos usá-lo para resolver os modelos estudados. Modelo matemático e forma padrão de um PPL Considere o seguinte problema de programação linear: Maximizar Z = Sujeito a: c1x1 a11x1 a21x1 am1x1 xn≥0, + + + + c2x2 a12x2 a22x2 am2x2 xn≥0, + + + + … … … … … … + cnxn + a1nxn ≤, =, ≥ + a2nxn ≤, =, ≥ + amnxn ≤, =, ≥ xn≥0 b1 b2 bm A forma apresentada acima é a expandida. Outras formas de representar um problema de programação linear são as mostradas a seguir: a) Forma de Somatório: Maximizar Z = Sujeito a: ∑c j =1 n n j xj x j ≤, =, ≥ bi, ∑a j =1 ij i = 1, … , m; j = 1, … , n. xj ≥ 0, b) Forma Matricial Maximizar Z = Sujeito a: cx Ax ≤, =, ≥ x≥ 0 b onde A é uma matriz retangular de dimensões m × n; c é um vetor 1 × n, b é um vetor m × 1 e x é um vetor n × 1. O uso de uma ou outra forma depende da conveniência da aplicação. As formas matricial e somatório são mais usadas para provas e demonstrações diversas. A forma expandida é necessária quando se torna necessário explicitar os coeficientes aij, bi e cj. 27 Forma Padrão de um Modelo de PL Antes de estabelecermos um algoritmo único para resolver os modelos matemáticos apresentados anteriormente, é necessário padronizar o formato desses modelos. Usaremos o formato padrão de maximização, que é adotado pela maioria dos livros de P.L.: Um modelo de PL na forma padrão é constituído apenas por equações lineares, e suas variáveis e termos independentes (bi) devem ser não negativas, como o modelo abaixo: Maximizar Z = Sujeito a: ∑c j =1 n n j xj x j = bi, ∑a j =1 ij i = 1, … , m; j = 1, … , n; i = 1, … , m. xj ≥ 0, bi ≥ 0, É importante salientar que em um problema de programação linear qualquer podem aparecer varáveis que devem ser deixadas livres em sua formulação, ou seja, variáveis irrestritas em sinal. Além disso, outras varáveis podem representar grandezas que na prática não podem ser positivas. Para que um problema com variáveis dos tipos mencionados acima seja colocado na forma padrão tornam-se necessários alguns recursos matemáticos, os quais serão discutidos a seguir. Recursos para se obter a forma padrão de um modelo de PL 1) Função Objetivo Os problemas de programação linear consistem em maximizar ou minimizar uma função objetivo. Um problema de minimizar pode ser transformado em maximizar fazendo-se: Mínimo ∑ c j x j = − Máximo − ∑ c j x j = − Máximo ∑ (−c j ) x j [ ] Então, se o problema é minimizar e deseja-se trabalhar como maximizar, multiplica-se os coeficientes da função objetivo por (-1), resolve-se o problema de maximizar e toma-se o negativo do valor encontrado. Esse valor é o mínimo do problema original. 2) Variáveis de Folga Considere a inequação linear do tipo "≤": ∑a j =1 n kj x j ≤ bk Utiliza-se uma variável xk, chamada variável de folga, em que xk = bk – ∑j akj xj, de forma que ∑a j =1 n kj x j + x k = bk Para cada restrição do tipo "≤" deve-se utilizar uma variável de folga diferente que representa a “folga” do recurso disponível que não foi utilizado. 28 3) Variáveis de Excesso Considere a inequação linear do tipo "≥": ∑a j =1 n sj x j ≥ bs Utiliza-se uma variável xs, chamada variável de excesso, em que xs = ∑j asj xj, – bs, de forma que ∑a j =1 n sj x j − x s = bs Para cada restrição do tipo "≥" deve-se utilizar uma variável de excesso diferente que representa o “excesso” do recurso utilizado. 4) Variáveis livres ou irrestritas em sinal Quando uma variável representa uma grandeza que pode assumir na prática valores positivos, nulos ou negativos, ou seja, a variável deve ser irrestrita em sinal, então na forma padrão essa variável é substituída pela diferença de duas outras não negativas, e, posteriormente, quando o problema for resolvido, seu valor real é resgatado. Assim, se xl é irrestrita em sinal, faz-se: xl = xl' - xl'', onde xl' ≥ 0 e xl'' ≥ 0. Resolve-se o problema com xl' e xl'', e após a solução obtém-se xl. 5) Variáveis com valores não positivos Quando uma variável xq representa uma grandeza que não deve assumir valores positivos no problema original, então, para construir a forma padrão do modelo de PL, substitui-se essa variável, fazendo-se xq = - xq', onde xq' ≥ 0. Resolve-se o PPL com xq' e, posteriormente, recupera-se xq. 6) Termos independentes com valores negativos Se algum bi tiver sinal negativo, basta multiplicar a linha toda por –1: 4x1 – 3x2 ≤ –2 ⇔ – 4x1 + 3x2 ≥ 2 Exemplo: min. s.a. 2x1 + 1,2x2 2x1 + 50x2 ≥ 11 50x1 + 10x2 ≥ 70 Forma padrão: max. – 2x1 – 1,2x2 s.a. 2x1 + 50x2 – x3 = 11 50x1 + 10x2 – x4 = 70 29 Definições básicas Considere o problema de programação linear na forma matricial e padrão: Maximizar Z = Sujeito a: cx Ax = x ≥ (1) (2) (3) b 0 Define-se como solução de um PPL, um vetor x que satisfaz as restrições (2); solução viável de um PPL é um vetor x que satisfaz as restrições (2) e (3); e região viável ou conjunto de soluções viáveis de um PPL é o conjunto de vetores x que satisfazem (2) e (3). Considere o sistema Ax = b no problema acima e suponha que posto [A | b] = posto [A] = m, o que significa que o sistema Ax = b é compatível, ou seja, tem solução. Uma permutação das colunas de A pode ser feita de forma a obter A = [B,N], onde B é uma matriz quadrada de dimensões m × m, e N é de dimensões m × (n-m). Se o posto (B) = m, então B é uma matriz inversível, e uma solução do sistema pode ser dado por: x B = B −1b xN = 0 O vetor x = (xB | xN) é chamado uma solução básica do sistema de equações Ax = b. Se x ≥ 0, então x é chamado uma solução básica viável do sistema. A matriz B é chamada matriz básica, ou simplesmente base do sistema e a matriz N é chamada matriz não básica. No vetor x = (xB | xN), as componentes de xB são chamadas variáveis básicas e as componentes de xN são chamadas variáveis não básicas. Se todas as componentes de xB forem maiores que zero, então x é chamado solução básica viável não degenerada, e se pelo menos uma de suas componentes for nula, então x é chamado solução básica degenerada. Exemplo para ilustrar as definições básicas Seja o problema de programação linear com duas variáveis e duas restrições: Maximizar z = sujeito a: x1 x1 xj + + ≥ 0 3 x2 x2 x2 ≤ ≤ (1) (2) (3) 6 3 A representação gráfica é a seguinte: 30 Obtendo-se a forma padrão do PPL pela introdução das variáveis de folga x3 e x4 nas restrições (2) e (3), respectivamente, tem-se o seguinte sistema de equações lineares: x1 + xj ≥ 0 x2 + x2 x3 + = x4 = 6 3 A matriz de coeficientes tecnológicos A e os vetores colunas correspondentes são os seguintes: 1 1 1 0 A=  = [a1 0 1 0 1  a2 a3 a4 ] Para se obter uma matriz básica B (2 × 2) a partir da matriz A, deve-se selecionar 2 vetores, ai e aj, linearmente independentes. Para uma matriz A (m × n), o número máximo possível de matrizes quadradas de dimensões m × m é dado por: n! m!(n − m)! No caso, n = 4 e m = 2, assim esse número máximo é 6. No entanto, como os vetores a1 e a3 são iguais, ou seja, não são linearmente independentes, o número de matrizes básicas fica reduzido a 5. A seguir são mostradas todas as matrizes básicas obtidas a partir do sistema dado, com as respectivas soluções básicas xB e as não básicas xN. 1) B = [a1 1 1 a2 ] =   0 1 x  1 − 1 6 3 x B =  1  = B −1b =    =   0 1  3 3  x2   x  0 xN =  3  =    x 4  0 31 2) B = [a1 1 0 a4 ] =   0 1 1 0 6 6 x  x B =  1  = B −1b =    =   0 1 3 3  x4   x  0 xN =  2  =    x3  0 3) B = [a 2 1 1 a3 ] =   1 0 x  0 1  6 3 x B =  2  = B −1b =    =   1 − 1 3 3  x3   x  0 xN =  1  =    x 4  0 4) B = [a 2 1 0 a4 ] =   1 1  x   1 0 6  6  x B =  2  = B −1b =    =    − 1 1  3  − 3  x4   x  0 xN =  1  =    x3  0 5) B = [a 3 1 0 a4 ] =   0 1 x  1 0 6 6 x B =  3  = B −1b =    =   0 1 3 3  x4   x  0 xN =  1  =    x 2  0 Das soluções básica obtidas, apenas a solução número 4 não é viável, visto que o componente x4 é negativo. Então são 4 soluções básicas viáveis para o PPL, a saber: 3 3 1 x = , 0   0 6 0 2 x =  , 0   3 0 3  3 x =  , 3    0 0 0 4 x =  6   3 Estes pontos pertencem a R4 . Uma projeção em R2, ou seja, no plano gerado por x1 e x2, tem como resultante os seguintes pontos: 32 3 x1 =   , 3 6 x2 =   , 0 0 x3 =   , 3  0 x4 =   0 Estes pontos são identificados na solução gráfica do problema, mostrando que eles correspondem aos pontos extremos do polígono de restrições (figura seguinte). x3 x1 x4 x2 Solução básica degenerada Uma solução básica viável é dita degenerada se existir uma ou mais variáveis básicas nulas. A existência de uma solução degenerada afeta o comportamento do algoritmo Simplex, e daí a importância sobre desse tipo de solução. Um exemplo mostrando a ocorrência de uma solução degenerada é dado a seguir. Seja o seguinte conjunto de restrições de um PPL com duas variáveis e três restrições (assumiremos sempre todos os xj ≥ 0, a menos que se diga o contrário): x1 x1 + + x2 x2 2 x2 ≤ ≤ ≤ 6 3 9 Sua representação gráfica é a seguinte: 33 Usando variáveis de folga o sistema é transformado em igualdades, na forma: x1 x1 + + x2 x2 2 x2 + x3 + x4 + x5 = = = 6 3 9 A matriz de coeficientes do sistema expandido é: A = [a1 1 1 1 0 0 a 4 ] = 0 1 0 1 0   1 2 0 0 1    a2 a3 Considere a matriz básica formada pelas três primeiras colunas de A, ou seja, B = [a1 a2 a3]. A solução correspondente é dada por: Variáveis básicas:  x1  1 1 1 x B =  x 2  = B −1b = 0 1 0      x3  1 2 0     Variáveis não básicas:  x 4  0 xN =   =    x5  0 −1 6 0 2 1  6 3 3 = 0 1 0  3 = 3        9 1 1 − 1 9 0        Tendo em vista que a variável básica x3 = 0, então a solução é degenerada. Veremos as implicações disso mais tarde. 34 Teoremas fundamentais Considere o problema de programação linear na forma padrão: Maximizar Z = cx Sujeito a: Ax = b x ≥ 0 Relembraremos agora algumas definições básicas, ilustrando-as de forma um pouco diferente: Definição 1: Uma base de uma matriz A (m × n) é uma matriz quadrada de m vetores coluna linearmente independentes em —m. As variáveis associadas a essas colunas são chamadas variáveis básicas. Ax = b x = (xB, xR), onde: xB representa o vetor das variáveis básicas de m componentes, e xR representa o vetor das restantes n – m variáveis não básicas. xB x: B A: m R m O sistema pode então ser reescrito assim: BxB + RxR = b n–m Como podemos solucionar o conjunto de equações somente em função das variáveis básicas, temos: xR = 0 e BxB = b Definição 2: Seja B uma base associada a uma matriz A. O vetor composto de x B = B −1b e xR = 0 é chamado de solução básica. Definição 3: Uma solução básica sem componentes negativas é denominada solução básica viável. Definição 4: O conjunto C = {x | Ax = b, x ≥ 0} denomina-se conjunto de soluções viáveis. 35 Teorema 1 O conjunto C das soluções viáveis de um modelo de programação linear é um conjunto convexo. Demonstração:  x = α x1 + (1 − α ) x 2 ∈ C {x1 , x 2 } ∈ C ⇒  0 ≤ α ≤ 1 Ax = A[α x1 + (1 − α ) x 2 ] = α Ax1 + (1 − α ) Ax 2 = α b + (1 − α )b = b Teorema 2 Toda solução básica viável do sistema Ax = b é um ponto extremo do conjunto de soluções viáveis, ou seja, um ponto extremo do conjunto C Teorema 3 Todo ponto extremo x de um conjunto de soluções viáveis de um sistema Ax = b é uma solução básica viável. Corolário 1: O conjunto de pontos extremos de um conjunto de soluções viáveis é finito e limitado m em C n . Corolário 2: Se existe uma solução viável, então existe uma solução básica viável. Teorema 4 1. Se o PPL tem solução ótima (máximo ou mínimo de Z) finita, então pelo menos uma solução ótima ocorre em um ponto extremo (vértice) do conjunto C; 2. Se a solução ótima ocorre simultaneamente em mais de um ponto extremo, então qualquer combinação convexa desses pontos extremos também é solução ótima. 36 O Algoritmo Simplex O algoritmo Simplex é um procedimento computacional desenvolvido para resolver problemas de programação linear. Podemos dividi-lo em duas fases distintas: Fase 1 - consiste em determinar uma solução básica viável do PPL ou, então, mostrar que tal solução não existe. Neste último caso, não havendo solução básica viável, não existe solução para o problema, ou seja, o conjunto de restrições é inconsistente. Quando uma solução básica viável puder ser identificada facilmente, a Fase 1 não precisa ser usada; Fase 2 - consiste em determinar a solução ótima para o PPL ou, então, mostrar que a solução é ilimitada, ou seja, que o valor de Z pode crescer ou decrescer infinitamente. A Fase 2 inicia a partir de uma solução básica viável do PPL, que pode ser obtida usando-se a Fase 1. Ilustração Caso típico de problema em que é necessário o uso da Fase 1: Maximizar sujeito a: 1 x1 -1 x1 1 x1 2 x1 2 x1 + + + + 2 x2 3 x2 2 x2 1 x2 1 x2 ≤ ≤ ≤ ≥ 9 0 10 5 Solução gráfica Colocando o problema na forma padrão tem-se: Maximizar sujeito a: 1 x1 -1 x1 1 x1 2 x2 2 x1 + + + + 2 x2 3 x2 2 x2 1 x2 1 x2 + x3 + x4 + x5 - x6 = = = = 9 0 10 5 37 Tomando-se x1 e x2 como variáveis não básicas, tem-se x1 = 0 e x2 = 0. Os valores das variáveis básicas são obtidas de forma trivial, ou seja: x3 = 9, x4 = 0, x5 = 10 e x6 = -5. A solução básica correspondente é x = (0, 0, 9, 0, 10, -5), que não é viável, pois existe uma componente negativa (x6 = -5). Neste caso, para se obter uma solução básica inicial é necessário usar a Fase 1 do Simplex. Veremos como isso pode ser feito mais adiante. Caso de problema em que não é necessário usar a Fase 1: Maximizar sujeito a: 5 x1 1 x1 1 x1 Solução gráfica + 2 x2 1 x2 2 x2 ≤ ≤ ≤ + 3 4 9 Colocando o problema na forma padrão tem-se: Maximizar sujeito a: 5 x1 1 x1 1 x2 + 2 x2 + x3 + 1 x2 2 x2 + x4 + x5 = = = 3 4 9 Tomando-se x1 e x2 como variáveis não básicas, tem-se x1 = 0 e x2 = 0. Os valores das variáveis básicas são obtidas de forma trivial, ou seja: x3 = 3, x4 = 4 e x5 = 9. A solução básica correspondente é x = (0, 0, 3, 4, 9), que é viável, pois todas componentes são não negativas. Neste caso, para se obter uma solução básica inicial não é necessário usar a Fase 1 do Simplex. 38 O Algoritmo Simplex – Detalhamento Passo 1 Determine uma solução básica viável (SBV) inicial. Se necessário usar a Fase 1; Passo 2 Testar se a SBV corrente é ótima. Se sim, pare, o problema está resolvido; se não, vá ao passo seguinte; Passo 3 Fazer a mudança de base, ou seja: (i) Determinar a variável não básica que deve entrar na base – a variável não básica a entrar na base deve ser aquela que mais aumenta o valor da função objetivo no momento corrente, ou seja, aquela que tem o maior coeficiente; (ii) Determinar a variável básica que deve sair da base – a variável a sair da base deve ser aquela que primeiro assumirá valores negativos como conseqüência do aumento do valor da variável escolhida para entrar na base. O propósito é não permitir que alguma variável assuma valores negativos, tornando o problema inviável; (iii) Processar a mudança de base fazendo-se a operação de pivoteamento e retornar ao Passo 2. Podemos também descrever o algoritmo em forma de fluxograma, como mostra a figura seguinte: 39 40 Exemplo 1 Uma grande fábrica de móveis dispõe em estoque de 250m de tábuas, 600m de pranchas e 500m de painéis de conglomerado. A fábrica normalmente oferece uma linha de móveis composta por um modelo de escrivaninha, uma mesa de reunião, um armário e uma prateleira. Cada tipo de móvel consome uma certa quantidade de matéria prima, conforme a tabela abaixo. A escrivaninha é vendida por R$100, a mesa por R$80, o armário por R$120 e a prateleira por R$20. Modele e resolva o problema pelo simplex, de forma a maximizar a receita com a venda dos móveis. Quantidade de material em metros consumidos por unidade de produto Mesa Armário Prateleira Escrivaninha 1 1 1 4 0 1 1 2 3 2 4 0 100 80 120 20 Disponibilidade do Recurso (m) 250 600 500 Tábua Prancha Painéis Valor de Revenda (R$) Considerando as seguintes variáveis de decisão: xE = Nº de escrivaninhas a ser produzido; xM = Nº de mesas a ser produzido; xA = Nº de armários a ser produzido; xP = Nº de prateleiras a ser produzido. Podemos então escrever o modelo de PL: Max. Z = 100xE + 80xM + 120xA + 20xP s.a. + xM + xA + 4xP xE xM + xA + 4xP 3xE + 2xM + 4xA Passando para a forma padrão, temos: Max. Z = 100xE + 80xM + 120xA + 20xP s.a. xE + xM + xA + 4xP xM + xA + 4xP 3xE + 2xM + 4xA ≤ ≤ ≤ 250 600 500 + x1 + x2 + x3 = = = 250 600 500 A nossa solução básica viável inicial pode ser obtida, neste caso, de forma trivial: x1 = 250; x2 = 600; x3 = 500; xE = xM = xA = xP = 0. Podemos agora montar o quadro simplex. Para isso, trataremos a equação da F.O. como se fosse apenas mais uma equação do nosso sistema linear: –Z + 100xE xE 3xE + 80xM + xM xM + 2xM + 120xA + xA + xA + 4xA + 20xP + 4xP + 4xP = = = = 0 250 600 500 41 + x1 + x2 + x3 Essa linha será destacada no quadro, e sua importância será vista no decorrer do algoritmo. Além disso, usaremos a 1ª coluna para fazer a numeração das linhas, somente para facilitar as explicações a seguir. A 2ª coluna serve para relacionarmos as variáveis básicas (V.B.): V.B. –Z x1 x2 x3 xE 100 1 0 3 xM 80 1 1 2 xA 120 1 1 4 xP 20 4 2 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 b 0 250 600 500 L0 L1 L2 L3 Para entrar na base, devemos escolher a variável que possui o maior coeficiente na linha L0. Esses coeficientes indicam a contribuição que cada variável dá à Função Objetivo. para cada unidade de aumento de seus respectivos valores. No quadro acima, vemos que cada unidade de aumento da variável xA resulta em um aumento de 120 unidade no valor da F.O. Essa é a variável que mais contribui localmente para o processo de maximização da F.O., e é portanto a escolhida para entrar na base. Esse processo de escolha é representado no fluxograma da seguinte maneira: cj* = max(cj) onde j* representa a coluna correspondente à variável que deve entrar na base. Para que a variável xA entre na base, é preciso que uma variável básica saia da base (por que?). Para determinar isso, é só fazer com que o valor de xA cresça o máximo possível. Podemos ver pelos valores do quadro acima que, se xA for maior que 125 (ou 4xA > 500), então teremos para a ultima restrição o seguinte: 4xA + x3 = 500 x3 = 500 – 4xA e o valor de x3 seria negativo, o que seria inviável. Com isso, o maior valor que xA pode assumir sem violar nenhuma das restrições é xA = 125. Nesse caso, o valor de x3 seria igual a zero, e ele então sai da base. Todo esse processo de escolha é representado no fluxograma da seguinte maneira: Escolher i* | min(bi / aij*), aij* > 0 onde i* representa a linha correspondente à variável que deve sair da base. O significado desse “procedimento” é bem simples: divida todos os bi pelos valores de aij* que forem maiores que zero, e pegue o menor valor dessa divisão, que corresponderá à linha i*. No caso acima, teríamos: L1: 250 / 1 = 250 L2: 600 / 1 = 600 L3: 500 / 4 = 125 → i* Agora podemos representar a mudança de base usando setas no quadro: 42 L0 L1 L2 L3 V.B. –Z x1 x2 x3 xE 100 1 0 3 xM 80 1 1 2 xA 120 1 1 4 xP 20 4 2 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 b 0 250 600 500 O elemento destacado representa o nosso pivot. Observe que os vetores-coluna das variáveis básicas na matriz A formam uma matriz identidade, e seus coeficientes da linha L0 são nulos. Esse padrão será mantido durante todo o decorrer do algoritmo. Dessa forma, os valores das V.B. são obtidos diretamente na última coluna (b), e o valor de – Z é obtido na posição b0. O pivoteamento consiste então em transformar a coluna correspondente à variável que está entrando na base em um vetor canônico, substituindo o vetor canônico da variável que está saindo da base. Fazemos isso por meio das operações básicas de linha. Primeiro, fazemos L′ ← L3 ÷ 4: 3 V.B. –Z x1 x2 xA xE 100 1 0 ¾ xM 80 1 1 ½ xA 120 1 1 1 xP 20 4 2 0 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 ¼ b 0 250 600 125 L0 L1 L2 L′ 3 Depois, fazemos: L′ ← -120 × L′ + L0 3 0 L′ ← -1 × L′ + L1 1 3 L′2 ← -1 × L′ + L2 3 e obtemos o segundo quadro simplex: L′ 0 L′ 1 L′2 L′ 3 V.B. –Z x1 x2 xA xE 10 xM 20 xA 0 xP 20 x1 0 x2 0 x3 -30 b -15.000 ¼ -¾ ¾ ½ ½ ½ 0 0 1 4 2 0 1 0 0 0 1 0 -¼ -¼ ¼ 125 475 125 Temos agora a solução básica x1 = 125; x2 = 475; xA = 125; xE = xM = x3 = xP = 0. Passamos de um lucro igual a zero para um lucro de R$15.000, correspondente à produção de 125 armários. Observe que ainda existem variáveis que podem contribuir para o crescimento da F.O. Como existe um empate no maior valor, entre xM e xP, escolheremos xM para entrar na base. Nesse caso, haverá também um empate entre x1 e xA para sair da base. Escolheremos xA para sair da base (depois discutiremos as implicações desses empates). 43 Executamos então o 2º pivoteamento: ′ L1′ ← L′ ÷ ½ 1 ′ L′′ ← -20 × L1′ + L′ 0 0 ′ ′ L′2 ← -½ × L1′ + L′2 ′ L′′ ← -½ × L1′ + L′ 3 3 e obtemos o terceiro quadro simplex: L′′ 0 ′′ L1 ′ L′2 L′′ 3 V.B. –Z xM x2 xA xE 0 ½ -1 ½ xM 0 1 0 0 xA 0 0 0 1 xP -140 8 -1 -4 x1 -40 2 1 -1 x2 0 0 1 0 x3 -20 -½ 0 ½ b -20.000 250 350 0 Temos agora a solução básica xM = 250; x2 = 350; xA = 0 (VB); xE = xP = x1 = x3 = 0 (VNB). O lucro agora aumentou para R$20.000, correspondente à produção de 250 mesas. Essa solução é ótima, já que não existe VNB que possa contribuir para o crescimento da F.O. Todas elas possuem coeficiente nulo ou negativo na linha da F.O. A solução ótima pode ser representada assim: x* = (0; 250; 0; 0; 0; 350; 0) Z* = 20.000 A variável de folga x2 representa a folga do recurso “Pranchas”. A solução ótima para esse problema, consiste em fabricar somente 250 mesas, tendo uma sobra de 350m de pranchas, e obtendo um lucro máximo de R$20.000,00. Veja que, apesar da variável xA estar na base, seu valor é nulo, indicando que essa solução é degenerada. Degeneração (ou degenerescência) e Ciclagem Em casos esporádicos (alguns autores dizem que esses casos são raros ou muito difíceis de ocorrer na prática), o algoritmo simplex pode entrar “em loop”, ou em processo de “ciclagem”. Nesses casos, ocorrem mudanças de base, mas a cada pivoteamento, o algoritmo retorna ao mesmo ponto do espaço de soluções, representado por vetores diferentes, mas linearmente dependentes. Isso ocorre quando há empate nos critérios de entrada e de saída da base, normalmente devido a alguma VB possuir valor nulo. Para evitar o processo de ciclagem, normalmente recorre-se a uma das duas regras mais conhecidas: – Regra Lexicográfica. Veja detalhes em (Bazaraa, 1990). – Regra de Bland • • Entre todas as candidatas a entrar na base, selecione a variável xk que possui o menor índice. Entre todas as candidatas a sair na base, selecione a variável xr que possui o menor índice. 44 Exemplo 2 Uma sorveteria produz dois tipos de sorvete: no palito e no copinho. Na sorveteria, o único ponto crítico é a mão-de-obra disponível. O sorvete no copinho consome 50% a mais de mão-de-obra do que no palito. Sabe-se que se todo sorvete produzido fosse no palito a companhia poderia produzir 400 toneladas por dia. No entanto, o mercado tem condições de absorver, diariamente, apenas 300 toneladas de sorvete no palito e 150 toneladas de sorvete no copinho. 1. Modele o problema de modo a maximizar a produção de sorvete. Considerando Xp igual à quantidade de sorvete em palito, e Xc igual à quantidade de sorvete em copinho produzido (em toneladas), temos: max. s.a. Xp + Xc Xp ≤ 300 Xc ≤ 150 Xp + 1,5Xc ≤ 400 2. Resolva-o graficamente. Xc 400 300 200 100 Solução ótima: (Xp=300; Xc=66,67; Z=366,67) 0 100 200 300 400 Xp Pela inclinação e sentido de crescimento da F.O. (linha pontilhada), vemos que a solução ótima é a interseção das retas Xp = 300 e Xp + 1,5Xc = 400. Isso nos dá as seguintes coordenadas: Xp* = 300; Xc* = (400 – Xp) / 1,5 = 100 / 1,5 = 66,67; Z* = 366,67. 45 3. Resolva-o pelo método simplex. Marcando os pivôs em negrito, temos os seguintes quadros do simplex (alguns valores aparecem arredondados no quadro): ==================================================== | Xp Xc X3 X4 X5| b ----------------------------------------------------Z| 1.0 1.0 0.0 0.0 0.0| 0.0 ---------------------------------------------------X3| 1.0 0.0 1.0 0.0 0.0| 300.0 X4| 0.0 1.0 0.0 1.0 0.0| 150.0 X5| 1.0 1.5 0.0 0.0 1.0| 400.0 ==================================================== -Z| 0.0 1.0 -1.0 0.0 0.0| -300.0 ---------------------------------------------------Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 X4| 0.0 1.0 0.0 1.0 0.0| 150.0 1.5 -1.0 0.0 1.0| 100.0 X5| 0.0 ==================================================== -Z| 0.0 0.0 -0.3 0.0 -0.7| -366.7 ---------------------------------------------------Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 X4| 0.0 0.0 0.7 1.0 -0.7| 83.3 Xc| 0.0 1.0 -0.7 0.0 0.7| 66.7 ==================================================== Solucao otima: Z* = 366.67 x* = (300; 66,67; 0; 83.33; 0; 0) Observe que a variável X4 representa a folga em termos de mercado para o sorvete em copinho (ou seja, é o tanto que estamos produzindo abaixo do valor máximo permitido). 4. Agora observe de novo a solução gráfica e observe o que acontece, graficamente, a cada iteração do Simplex. 46 Algoritmo Simplex – Método das Duas Fases Primeiro Exemplo (extraído de Goldbarg&Luna,2000): Considere o seguinte modelo de P.L.: Minimizar Z = -3x1 - 5x2 sujeito a: x1 ≤ 4 x2 ≤ 6 3x1 + 2x2 ≥ 18 x1 ≥ 0 e x2 ≥ 0 Passando para a forma padrão, temos: Maximizar Z’ = 3x1 + 5x2 s.a.: + x3 = 4 x2 + x4 = 6 3x1 + 2x2 - x5 = 18 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0 x2 x1 6 A B 3 C 0 2 4 x1 Observe que, neste caso, não podemos considerar a solução inicial contendo somente as variáveis de folga, o que resultaria em uma solução inviável. Isso pode ser visto na representação gráfica do problema, mostrado acima. A solução trivial x1 = 0 e x2 = 0 não pertence ao espaço de soluções. Nessas situações, normalmente opta-se por usar um dos seguintes métodos para solucionar o modelo de P.L.: • • Método do grande M Método das duas fases Veremos aqui o método das duas fases (o outro será discutido em sala de aula). 47 Na FASE 1, utilizamos o simplex sobre o problema modificado, e tentamos encontrar uma solução básica viável inicial do problema original. Na FASE 2, de posse da base encontrada na 1a Fase, aplicamos o método simplex tradicional em busca da solução ótima do problema. FASE 1 1. Introduzimos uma variável artificial x a para cada restrição do problema, ou somente para as j restrições que tiverem variável de folga com coeficiente negativo. 2. Resolvemos o problema para a seguinte F.O. modificada: Min. q = ∑ x a j * 3. Se q = 0, então existe uma solução básica viável para o problema original. Neste caso, eliminamos as variáveis artificiais, substituímos a F.O. modificada pela original e prosseguimos com o simplex. a Introduzindo uma variável artificial x 6 , e mudando a função objetivo de forma a conter somente as variáveis artificiais, temos: a Minimizar q = x 6 s.a.: x1 3x1 + x3 x2 + 2x2 + x4 - x5 a + x6 = = = 4 6 18 a x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x 6 ≥ 0 V.B. q x3 x4 a x6 x1 0 1 0 3 x2 0 0 1 2 x3 0 1 0 0 x4 0 0 1 0 x5 0 0 0 -1 a x6 -1 0 0 1 4 6 18 Reduzindo a coluna 6 à forma canônica, temos: a x6 V.B. x1 x2 x3 x4 x5 q 3 2 0 0 -1 0 x3 1 0 1 0 0 0 x4 0 1 0 1 0 0 a x6 3 2 0 0 -1 1 Iteração 1: V.B. x1 q 3 x3 1 x4 0 a x6 3 18 4 6 18 x2 2 0 1 2 x3 0 1 0 0 x4 0 0 1 0 x5 -1 0 0 -1 a x6 0 0 0 1 18 4 6 18 48 Iteração 2: V.B. x1 q 0 x1 1 x4 0 a x6 0 V.B. q x1 x4 x2 x1 0 1 0 0 x2 2 0 1 2 x2 0 0 0 1 x3 -3 1 0 -3 x3 0 1 3/2 -3/2 x4 0 0 1 0 x4 0 0 1 0 x5 -1 0 0 -1 x5 0 0 1/2 -1/2 a x6 0 0 0 6 4 6 6 1 a x6 -1 0 -1/2 1/2 0 4 3 3 Fim da Fase 1. Retirando as partes sombreadas acima, e re-introduzindo a função objetivo original, temos: FASE 2 V.B. -Z’ x1 x4 x2 x1 3 1 0 0 x2 5 0 0 1 x3 0 1 3/2 -3/2 x4 0 0 1 0 x5 0 0 1/2 -1/2 0 4 3 3 Reduzindo as colunas 1 e 2 à forma canônica, temos: V.B. x1 x2 x3 x4 x5 -Z’ 0 0 9/2 0 5/2 -27 x1 1 0 1 0 0 4 x4 0 0 3/2 1 1/2 3 x2 0 1 -3/2 0 -1/2 3 Iteração 3: V.B. x1 -Z’ 0 x1 1 x4 0 x2 0 Iteração 4: x1 V.B. -Z’ 0 x1 1 x3 0 x2 0 x2 0 0 0 1 x3 9/2 1 3/2 -3/2 x4 0 0 1 0 x5 5/2 0 1/2 -1/2 -27 4 3 3 x2 0 0 0 1 x3 0 0 1 0 x4 -3 -2/3 2/3 1 x5 1 -1/3 1/3 0 -36 2 2 6 49 Quadro final (ótimo): V.B. x1 x2 -Z’ 0 0 x1 1 0 x5 0 0 x2 0 1 x2 x3 -3 1 3 0 x4 -5 0 2 1 x5 0 0 1 0 -42 4 6 6 6 Z = -36 A B Z = -42 3 C q=0 Z = -27 q = 18 0 q=6 2 4 x1 Segundo Exemplo: Escolha da Mistura para Rações Grão 1 2 5 32 Grão 2 3 3 35 Necessidades mínimas 650 1050 Nutriente A Nutriente C $/kg Seja: x1 = qtde. (kg) do Grão 1 usada na ração x2 = qtde. (kg) do Grão 2 usada na ração Minimizar Sujeito a: 2x1 5x1 + 3x2 ≥ 650 + 3x2 ≥ 1050 x1 ≥ 0, x2 ≥ 0 32x1 + 35x2 50 FASE 1 Introduzindo as variáveis de folga e as variáveis artificiais, temos o seguinte modelo artificial, já na forma padrão: a a Maximizar q = − x5 − x6 s.a.: 2x1 5x1 + 3x2 + 3x2 – x3 – x4 a + x5 a + x6 = = 650 1050 V.B. q a x5 a x6 x1 0 2 5 x2 0 3 3 x3 0 -1 0 x4 0 0 -1 a x5 -1 1 a x6 -1 0 650 1050 0 1 Reduzindo as colunas 5 e 6 à forma canônica, temos: a a x5 x6 V.B. x1 x2 x3 x4 q 7 6 -1 -1 0 0 a x5 2 3 -1 0 1 0 a x6 1700 650 1050 5 3 0 -1 0 1 Iteração 1: V.B. x1 q 7 a x5 2 a x6 x2 6 3 3 x3 -1 -1 0 x4 -1 0 -1 a x5 0 1 a x6 0 0 1700 650 1050 5 0 1 Iteração 2: V.B. x1 q 0 a x5 0 x1 V.B. q x2 x1 1 x1 0 0 1 x2 1,8 1,8 0,6 x2 0 1 0 x3 -1 -1 0 x3 0 -0,56 0,33 x4 0,4 0,4 -0,2 x4 0 0,22 0,13 a x5 0 a x6 -1,4 230 230 210 1 0 a x5 -1 0,56 -0,33 -0,4 0,2 a x6 -1 -0,22 -0,13 0 127,78 133,33 Fim da Fase 1. Retirando as partes sombreadas acima, e re-introduzindo a função objetivo original, temos: 51 FASE 2 V.B. -Z’ x2 x1 x1 32 0 1 x2 35 1 0 x3 0 -0,56 0,33 x4 0 0,22 0,13 0 127,78 133,33 Reduzindo as colunas 1 e 2 à forma canônica, temos: V.B. x1 x2 x3 x4 -Z’ 0 0 -8,78 -12,04 -8.738.89 x2 0 1 -0,56 0,22 127,78 x1 1 0 0,33 0,13 133,33 O quadro acima já contém a solução ótima: x1 = 133,33 kg x2 = 127,78 kg Custo mínimo = $ 8.738.89 As iterações do algoritmo são representadas na figura abaixo: Mistura de Ração x2 400 360 320 280 240 200 160 120 80 40 0 0 40 80 F.O. Nutr.A Nutr.C 120 160 200 240 280 320 360 400 x1 52 Elementos de Pós-Otimização Seja o PPL dado pela Forma Padrão: Max. Z = cx s.a. Ax = b, x≥0 e suponha que a aplicação do método Simplex encontrou uma solução ótima associada a uma matriz básica B. Podemos ter então as seguintes situações: 1. 2. 3. 4. 5. Mudança no vetor c Mudança no vetor b Mudança na matriz A Adição de nova atividade Adição de uma nova restrição. Se a análise não permite mudança na base B, tem-se uma Análise de Sensibilidade. Caso contrário, uma Análise Paramétrica. Neste módulo, será feita uma abordagem da primeira situação. Em que faixa podem variar os custos e os meus recursos de modo que a minha solução não mude? Max. Z = cx s.a. Ax = b, x≥0 é equivalente a: Max. Z = cB xB + cR xR s.a. BxB + RxR = b , xB ≥ 0, xR ≥ 0 Como já foi visto anteriormente, o método Simplex procura, a partir de uma determinada partição da matriz A, resolver o sistema de equações Ax = b, sendo que a solução, para xR = 0 , é denominada solução básica. Se esta solução atende a restrição x ≥ 0, ela é denominada de solução básica viável. Se ela minimiza a F.O. Z, ela é chamada de solução ótima do PPL. O Quadro Simplex na Forma Canônica: xB -Z 0 xR cj – zj B −1 R cB B −1b B −1b xB onde I zj = c B B −1 a j 53 Condição de Otimalidade (maximização): (cj – zj) ≤ 0 para toda variável não básica. Um exemplo: Considere o modelo do PPL visto na página 45 (com Xp e Xc sendo substituídos por x1 e x2, respectivamente): max. s.a. x1 + x2 x1 x2 x1 + 1,5x2 xj ≥ 0 sendo 1 0 1 0 0    A = 0 1 0 1 0  1 1,5 0 0 1     300    b = 150   400    x1  x   2 x =  x3     x4   x5    + x3 + x4 = 300 = 150 + x5 = 400 c = [1 1 0 0 0] Vimos que a solução ótima para este PPL é: Z* = 366.67 x* = (300; 66,67; 0; 83.33; 0; 0) Temos, portanto, que x1, x2 e x4 são atividades básicas, e x3, x5 são atividades não básicas. Expressando isso em termos das equações matriciais vistas anteriormente, temos... 1 0 0  B = 0 1 1   1 1, 5 0    1 0  R = 0 0    0 1    0 0   1  −0, 67 0 0, 67  B =   0,67 1 −0, 67    −1 cB = [1 1 0] cR = [ 0 0]  x1  x  xB =  2   x4     x3  xR =    x5  cR − cB B −1R = [ −0,333 −0,667 ] xB = B −1b = [300 66, 67 83,33] cB xB = 366, 67 ...que é precisamente o resultado que obtivemos na resolução do PPL através do Simplex: 54 ==================================================== -Z| 0.0 0.0 -0.3 0.0 -0.7| -366.7 ---------------------------------------------------Xp| 1.0 0.0 1.0 0.0 0.0| 300.0 X4| 0.0 0.0 0.7 1.0 -0.7| 83.3 Xc| 0.0 1.0 -0.7 0.0 0.7| 66.7 ==================================================== Mudança no vetor c A análise é feita considerando-se a variação no coeficiente de cada variável na função objetivo, exigindo-se que as condições de otimalidade: (cj – zj) ≤ 0 sejam atendidas para toda VNB. Neste caso, se a variável em questão for não básica resolve-se uma desigualdade linear, enquanto que se ela for variável básica resolve-se um sistema de desigualdades lineares. Exemplo: Considere a VNB x3 no quadro SIMPLEX ótimo visto anteriormente. O coeficiente de x3 na F.O. é c3 = 0. Deve-se ter: (c3 + λ ) − z3 ≤ 0 ⇒ (c3 + λ ) − cB B −1a3 ≤ 0 0 0  1   1  −0, 67 0 0, 67  0  ≤ 0 ⇒ (0 + λ ) − [1 1 0]     0, 67 1 −0, 67  0     ⇒ λ − 0,333 ≤ 0 ⇒ λ ≤ 0,333 Isso permite uma variação para c3 de –∞ até 0,333. Neste intervalo, x3 continuará sendo VNB. Mais ainda, os conjuntos de VB e de VNB não mudam. Para fazer a mesma análise considerando uma VB (e.g. x1), poderíamos fazer assim: cR − cB B −1 R ≤ 0 0 0  1 0   1  −0, 67 0 0,67  0 0 ≤ 0 ⇒ [ 0 0] − [ (1 + λ ) 1 0]     0, 67 1 −0, 67  0 1     ⇒ λ ≥ −0,333 55 Mudança no vetor b Qualquer mudança no vetor b deve ser feita de modo que as VB continuem não negativas, ou seja: B-1b ≥ 0 Exemplo: Considere o elemento b1=300. Temos então que: 0 0  300 + λ  b1 + λ   1  b  ≥ 0 ⇒  −0, 67 0 0, 67   150  ≥ 0 B  2      b3   0, 67 1 −0, 67   400        300 + λ ≥ 0  ⇒ 66, 67 − 0.67λ ≥ 0 83,33 + 0.67λ ≥ 0  −1 ⇒ −125 ≤ λ ≤ 100 o que permite uma variação para o elemento b1 de 175 a 400. 56 Dualidade L i e(t) R Circuito 1 Relacionamentos entre a corrente i e a tensão e: Circuito 1: Circuito 2: onde G = 1 R di 1 + Ri + ∫ idt = e(t ) dt C 1 de C + Gi + ∫ edt = i (t ) dt L L C i(t) e R L C Circuito 2 Forma geral: a dx + bx + c ∫ xdt = y (t ) dt Dizemos que os Circuitos 1 e 2 são duais. Circuito 1: primal Circuito 2: dual (ou vice-versa) Seja o modelo de PL: Max. s.a. ∑c x j j =1 n n j (1) (2) (3) ∑a j =1 ij x j ≤ bi , para i = 1, 2, ..., m xj ≥ 0 para j = 1, 2, ..., n Chamamos esse modelo de primal. O modelo dual relacionado a ele é: Min. ∑b u i =1 m ij i =1 m i i (4) i s.a. ∑a u ≥ c j , para j = 1, 2, ..., n (5) (6) ui ≥ 0 para i = 1, 2, ..., m Usando a notação matricial, temos: 57 Primal (P) Max. cx s.a. Ax ≤ b x≥0 x: (1× n) Exemplo: Primal (P) Max. 3x1 + 1x2 + 2x3 s.a. 2x1 + 4x2 + 3x3 ≤ 6 3x1 + 3x2 + 1x3 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Min. ub s.a. uA ≥ c u≥0 u: (m × 1) Dual (D) Dual (D) Min. 6u1 + 8u2 s.a. 2u1 + 3u2 ≥ 3 4u1 + 3u2 ≥ 1 3u1 + 1u2 ≥ 2 u1 ≥ 0, u2 ≥ 0 Teorema 1: Se x e u são soluções viáveis dos problemas (P) e (D), respectivamente, então cx ≤ u b Teorema 2: Se x e u são soluções viáveis dos problemas (P) e (D), respectivamente, e cx = u b , então essas soluções são ótimas, ou seja, cx * = u *b Teorema da Existência Para um par de problemas duais, uma e somente uma das alternativas abaixo é verdadeira: • • • Ex: Nenhum dos problemas tem solução. Um deles não tem solução viável e o outro tem solução ótima ilimitada. Ambos possuem solução ótima finita. (P) Max. –3x1 + 2x2 s.a. x1 ≤3 x1 – x2 ≤ 0 x1 ≥ 0, x2 ≥ 0 (D) Min. –3u1 + 0u2 s.a. u1 + u2 ≥ –3 3u2 ≤ –2 u1 ≥ 0, u2 ≥ 0 Teorema das Folgas Complementares Dado um par de problemas duais, uma condição necessária e suficiente para que as soluções x e u sejam ótimas é que se verifiquem as seguintes relações de complementaridade de folga: u(Ax – b) = 0 (c – uA)x = 0 Prova: 58  Ax ≥ b ∴ Ax − b ≥ 0 ∴ u ( Ax − b) ≥ 0   u A ≤ c ∴ c − u A ≥ 0 ∴ ( c − u A) x ≥ 0 Fazendo α = u ( Ax − b)   β = (c − u A) x Teremos: α + β = u ( Ax − b) + (c − u A) x = cx − u b ≥ 0 Se x e u forem soluções ótimas, teremos: cx = u b Logo, α =β =0 Relacionamentos entre o Problema Primal e seu Dual Na prática, muitos modelos de PL contêm restrições do tipo “≤”, bem como outras restrições do tipo “≥” e outras ainda do tipo “=”. Podemos ainda ter variáveis irrestritas ou até mesmo negativas no modelo original (não padrão), como vimos anteriormente. A tabela abaixo mostra como podemos converter imediatamente esses modelos “mistos” em seus respectivos duais, sem que seja necessário passar fazer o modelo passar por transformações intermediárias. Problema de Maximização ≥0 ≤0 Irrestrito Problema de Minimização ≥ ≤ = ←–→ ←–→ ←–→ ←–→ ←–→ ←–→ Restrições ≤ ≥ = ≥0 ≤0 Irrestrito Feita essa primeira transformação, podemos então aplicar as regras usuais para passar o modelo dual para a forma padrão, caso, seja necessário. Variáveis 59 Restrições Variáveis Exemplo Uma fábrica pode produzir três produtos: televisores, DVDs e cãmeras de vídeo. Na tabela abaixo estão apresentados os consumos dos principais recursos da fábrica por produto, bem como a disponibilidade destes recursos, a contribuição unitária de cada produto para o lucro da empresa, e a demanda mínima do mercado. Recursos da Fábrica (Setores de Produção) Produção de Circuitos Produção de Mecanismos Produção de Gabinetes Montagem de Produtos Expedição Lucro (R$ / unid.) Demanda mínima (unid. / mês) Consumo de Recursos (horas / unid.) Televisor 0,151 0,000 0,078 0,340 0,057 45,00 55,800 DVD 0,210 0,345 0,056 0,450 0,030 115,00 15,500 Cãmera 0,120 0,450 0,045 0,370 0,045 216,00 23,200 Disponibilidade (horas / mês) 22,500 17,200 10,500 35,000 6,800 Para o problema acima foi obtida a seguinte solução ótima através do Lindo®: OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 X3 ROW 2) 3) 4) 5) 6) 7) 8) 9) 9578.494 VALUE 55.800000 15.500000 24.467567 SLACK OR SURPLUS 7.883092 0.842095 4.178559 0.000000 2.053360 0.000000 0.000000 1.267568 REDUCED COST 0.000000 0.000000 0.000000 DUAL PRICES 0.000000 0.000000 0.000000 583.783813 0.000000 -153.486481 -147.702698 0.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE 153.486481 INFINITY 147.702698 INFINITY INFINITY 121.444443 RIGHTHAND SIDE RANGES ALLOWABLE INCREASE INFINITY INFINITY INFINITY 0.692389 INFINITY 1.379412 1.042222 1.267568 VARIABLE X1 X2 X3 CURRENT COEF 45.000000 115.000000 216.000000 ROW 2 3 4 5 6 7 8 9 CURRENT RHS 22.500000 17.200000 10.500000 35.000000 6.800000 55.800000 15.500000 23.200000 ALLOWABLE DECREASE 7.883092 0.842095 4.178559 0.469000 2.053360 2.036438 4.162659 INFINITY 60 1. Construa um modelo matemático para este problema de produção. Observando a tabela com os parãmetros, e mais a seqüência na qual estão dispostas as constantes do lado direito (RHS) na solução dada, podemos construir o modelo exato que foi usado para obter a solução pelo Lindo: maximizar 45x1 + 115x2 + 216x3 sujeito a: 0,151x1 0,210x2 + 0,120x3 0,345x2 0,450x3 0,078x1 + 0,056x2 0,045x3 0,340x1 0,450x2 0,370x3 0,057x1 0,030x2 0,045x3 x1 x2 x3 (1) ≤ ≤ ≤ ≤ ≤ ≥ ≥ ≥ 22,5 17,2 10,5 35,0 6,8 55,8 15,5 23,2 (2) (3) (4) (5) (6) (7) (8) (9) 2. Descreva a solução obtida (variáveis de decisão, variáveis de folga e função objetivo). – O lucro máximo obtido foi de R$ 9578,494 / mês; – Para obter esse lucro, é preciso fabricar uma média de 55,8 televisores, 15,5 DVDs e 24,47 Cãmeras por mês; – Pelo resultado das variáveis de folga, vemos que: – O setor de Montagem de Produtos trabalhará sem qualquer folga; – O setor de Produção de Circuitos é o que está com uma folga maior (7,88 h/mês), seguido pelo setor de Produção de Gabinetes (4,18 h/mês); – Serão fabricadas exatamente as quantidades mínimas possíveis de televisores e DVDs, e uma média de 1,27 cãmeras / mês a mais que o mínimo de 23,2. 3. O que aconteceria com o lucro da empresa se a demanda de televisores passasse para: i) 57 unid. / mês? Pela análise de sensibilidade, vemos que, para que a mesma base seja mantida, a demanda de televisores precisa estar entre (55,8 – 2,036438) e (55,8 + 1.379412), ou seja, entre 53,76 e 57,18. Portanto, com uma demanda de 57 unid./mês, podemos considerar o preço dual para a restrição de demanda de televisores, que é de cerca de –153,48. Isso significa que o lucro da empresa piora de R$ 153,48 para cada unidade de aumento da demanda de televisores. Para uma demanda de 57, teríamos um aumento na demanda de 1,2, e portanto o lucro sofreria um decréscimo de 1,2 × 153,48 = R$ 184,17 / mês. ii) 60 unid. / mês? Neste caso, a demanda ultrapassaria o limite estabelecido pela análise de sensibilidade, e teríamos uma mudança de base. Não podemos, neste caso, fazer qualquer análise quantitativa com base somente nas informações fornecidas na solução do problema. 4. Faça sugestões para o superintendente da empresa, de modo que se possa aumentar ainda mais o lucro total. Para o superintendente da empresa, provavelmente seria difícil alterar as demandas mínimas dos produtos, pois esses são estabelecidos pelo mercado. Aumentar o lucro para cada produ61 to seria uma sugestão óbvia, mas isso provavelmente já teria sido feito se fosse possível. Analisando as variáveis de folga e os preços duais, vemos que, para cada unidade que aumentarmos a capacidade do Setor de Montagem de Produtos, o lucro aumenta em R$ 583,78 / mês. Podemos tentar obter essa capacidade adicional usando um pouco de mão de obra ociosa dos setores de Produção de Circuitos e de Produção de Gabinetes. Se não for possível deslocar essa mão de obra, teríamos ainda grande chance de contratar mão de obra adicional a um custo menor do que R$ 583,78 / hora. Deve ser notado, no entanto, que esse aumento no lucro só é válido para uma capacidade desse setor 0,62 horas / mês acima da capacidade atual. Portanto, seria interessante fazer algumas simulações para ter uma idéia melhor das conseqüências da contratação de um novo funcionário para esse setor. 62 PARTE II – Programação em Redes Introdução No contexto da Pesquisa Operacional, chamamos de Programação em Redes o estudo dos problemas que utilizam a Teoria dos Grafos como um dos principais recursos de modelagem. Neste contexto, o termo “rede” pode se referir não somente a uma “rede de computadores”, mas também a uma rede de transportes, de distribuição etc. Exemplos: • • • • • • • • Redes de computadores Redes ferroviárias Redes de telecomunicações Redes de estradas Redes Elétricas Redes de esgotos Redes de transportes Redes de atividades “scheduling” de atividades em grandes projetos → Neste escopo, portanto, uma rede pode se referir a qualquer conjunto de entidades (computadores, lojas, fábricas, máquinas, pessoas etc.) interligadas por meio de cabos, estradas, caminhos etc., ou que possuem algum inter-relacionamento. Esse tipo de problema se encaixa perfeitamente na modelagem por meio de grafos, como veremos mais adiante. Redes / Grafos ESTRUTURA TOPOLÓGICA INFORMAÇÕES QUANTITATIVAS SOBRE OS ELEMENTOS Antes de estudarmos formalmente o que são grafos, considere o seguinte exemplo: Um vendedor ambulante deve sair de uma cidade de origem, visitar várias outras cidades, e depois retornar à cidade de origem, passando por cada uma dessas cidades uma única vez. Sabendo que existem muitas formas diferentes de realizar essas visitas, ele deseja descobrir o itinerário que proporciona a menor distância (ou tempo ou custo) total percorrida. Esse problema clássico da P.O. é chamado de “Problema do Caixeiro Viajante (PCV)”. Podemos exemplificar o problema considerando somente 5 cidades e a rede de interligações (estradas) ilustrada na figura a seguir, onde os valores nas linhas representam as distâncias entre as cidades. 63 2 250 1 200 350 300 300 200 350 200 3 200 4 150 5 Como podemos resolver esse problema? A forma mais simples seria enumerar todas as rotas possíveis e calcular a distância de cada uma. Como a posição da cidade-origem no itinerário é fixo, esse método envolveria analisar todas as permutações possíveis dentre as n–1 cidades restantes, ou seja, analisar (n–1)! possíveis rotas. Com 5 cidades, teríamos 4! = 24 rotas, o que seria trivial de analisar (podendo até mesmo ser feito à mão). Com 10 cidades, teríamos cerca de 362 mil rotas, o que seria perfeitamente possível com a ajuda de um micro-computador. Aumentando esse número para 20 cidades, teríamos cerca de 1017 rotas. Se pudéssemos implementar um programa que pudesse analisar uma solução (permutação) a cada ciclo de relógio de um computador, então usando um computador de 4 GHz gastaríamos: 1017 = 2,5 × 107 segundos = 9,5 meses! 9 4 ×10 Com 50 cidades, teríamos cerca de 1062 rotas, requerendo cerca de 1045 anos de processamento! Embora o uso de uma técnica dessas de “força bruta” não fosse a maneira mais inteligente de encontrar uma solução ótima para esse problema (a não talvez para um pequeno número de cidades), nesse caso não existe realmente uma técnica apropriada para fazer isso, seja ela por meio de modelagem matemática em forma de PL, ou usando um outro algoritmo qualquer. Diferente dos problemas de PL que estudamos anteriormente, que dispõem do eficiente método Simplex, todos os métodos disponíveis para a obtenção de uma solução ótima para o PCV possuem dificuldade exponencial com o tamanho do problema (número de cidades). Assim como o PCV, diversos outros problemas de programação em redes são extremamente difíceis de resolver. Nesses casos, o mais indicado é o uso de heurísticas, ou seja, algoritmos buscam encontrar uma solução boa para o problema, mas não necessariamente a solução ótima, dentro de um intervalo de tempo viável. No entanto, outros problemas de programação em redes, embora possam ser modelados como PLs e resolvidos pelo Simplex, possuem métodos de solução bem mais eficientes e que permitem resolver problemas bem maiores do que seria possível se usássemos a modelagem matemática. Isso é possível graças aos desenvolvimentos obtidos na Teoria dos Grafos. Além de vermos alguns desses problemas, a nossa preocupação será também identificar aqueles problemas que, assim como o PCV, são mais difíceis de resolver e, portanto, requerem a busca de soluções não-ótimas ou “aproximadas”. 64 Introdução à Teoria de Grafos Teoria dos grafos é uma ferramenta para formular problemas, tornando-os precisos, e definindo inter-relações fundamentais. Algumas vezes, uma formulação simples e precisa de um problema nos ajuda a compreendê-lo melhor. O maior trunfo de uma ferramenta de formulação é a possibilidade de compreender o modelo matemático de modo simplificado. Deste modo, na Teoria dos Grafos, a maior unidade de aprendizado que se usa é a assistência a colocações e possíveis encaminhamentos futuros a um problema. Uma vez que um problema seja formulado em linguagem teórica de grafos, os conceitos de Teoria dos Grafos podem ser usados para definir o que é necessário para analisar o problema. Também, a Teoria dos Grafos pode nos levar a novos conceitos teóricos os quais podem ser usados para construir teorias sobre problemas da sociedade. No entanto, alguns problemas podem ser modelados somente em parte por grafos - problemas de telecomunicações, dentre outros, nos levando a crer que esta teoria é algo que complementa com elegância a análise de vários problemas de nosso dia a dia. Problemas de Grafos surgem geralmente em: • • • • • • • • • • Caminhos; Redes de comunicação; Localização de facilidades (Depósitos, Hospitais, Escolas, etc.); Desenhos de circuitos impressos; Desenho e/ou layout de revistas, jornais, etc; Distribuição de produtos; Telecomunicações; Limpeza urbana; Controle de tráfego; Atribuição de rádio freqüência móvel, etc. Teoria dos grafos, sem abusar muito do princípio, é uma ferramenta que às vezes resolve problemas e algumas vezes nos dá idéias sobre como resolvê-los. Ela, em geral, tem que ser usada em conjunto com muitas outras ferramentas, matemáticas ou estatísticas, etc. Felizmente, o uso da teoria dos grafos pode nos ajudar a compreender em “poucas palavras” o significado de grandes problemas ligados à nossa vida social, e algumas de suas possíveis soluções. Uma Breve História da Teoria dos Grafos Os problemas de Percurso em Arcos são os mais antigos relacionados a grafos. A primeira referência que se conhece sobre eles vem do famoso problema das sete pontes de Königsberg (Figura 1). Buscava-se saber se havia um caminho fechado que atravessasse exatamente uma vez sete pontes sobre o rio Pregel em Königsberg, hoje Kaliningrad (Figura 2). O problema foi solucionado em 1736 pelo matemático suíço Leonhard Euler, que encontrou as condições para a existência de um percurso fechado (grafo euleriano), e mostrou que não havia solução que satisfizesse aquele caso particular (Figura 3). A preocupação de Euler, na demonstração da solução, foi exclusivamente sobre a existência do caminho fechado, já a questão de determiná-lo só foi resolvida em 1873 (ou seja, 137 anos mais tarde) por Heierholzer. 65 Figura 1: Visualização de Königsberg, e indicação das sete pontes sobre o rio Pregel. Figura 2: A cidade de Kaliningrad hoje – reconstruída após a 2a Guerra Mundial. Figura 3: Representação de Euler do problema. 66 Muitos anos mais tarde, em 1962, um matemático da Universidade Normal de Shangtun, Kwan Mei-Ko, quando de sua passagem como funcionário dos correios durante a revolução cultural chinesa, preocupou-se com uma situação semelhante à de Euler e Heierholzer, porém adequada ao percurso dos carteiros que atenderiam ruas de sua cidade. Neste caso, Kwan mostrou-se interessado em definir além da travessia, a forma mais fácil de fazê-la, percorrendo a menor distância possível. Kwan, definiu assim o problema: Um carteiro tem que cobrir seu local de trabalho, antes de retornar ao posto. O problema é encontrar a menor distância de percurso para o carteiro. Esse problema é conhecido como o “Problema do Carteiro Chinês”. Dentre as muitas e famosas histórias da Teoria dos Grafos, sem dúvida uma das mais curiosas é a do matemático William Rowan Hamilton. Hamilton já fazia parte da Royal Astronomia Irlandesa aos 22 anos, foi condecorado Cavalheiro aos 30 anos, e foi reconhecido como um dos líderes matemáticos de sua época. Uma de suas descobertas mais significativas foi a existência da álgebra não comutativa, ou seja, a álgebra onde a multiplicação xy não necessariamente é igual a yx. Há muitos sistemas de álgebra não comutativa, e um deles, descoberto por Hamilton foi chamado por ele de O Cálculo Icosiano, o qual pode ser interpretado em termos de caminhos sobre um grafo descrito por um dodecaedro regular. Hamilton comunicou sua descoberta em uma carta datada de 7 de outubro de 1856, e posteriormente publicou dois artigos sobre o assunto. Ele usou uma representação gráfica como base de um quebra-cabeças, que ele chamou de O Jogo Icosiano. Hamilton expôs orgulhosamente o seu jogo na Associação Britânica em Dublin, 1857. A idéia foi vendida por 16 pounds para um comerciante de jogos e quebra-cabeças. O jogo foi comercializado em 1857, acompanhado por um guia de instruções, escrito pelo próprio Hamilton. O leitor logo veria que o objetivo do jogo era encontrar caminhos e circuitos sobre o grafo formado pelo dodecaedro, satisfazendo certas condições específicas. Particularmente, o primeiro problema era o de encontrar um circuito passando somente uma vez por cada vértice do dodecaedro, que é exatamente o PCV descrito anteriormente (Figura 4). Figura 4: (a) Dodecaedro para o Jogo Icosiano. (b) Uma solução ou “ciclo hamiltoniano”. 67 Conceitos Básicos da Teoria de Grafos GRAFO Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde: V - conjunto não vazio: os vértices ou nodos do grafo; A - conjunto de pares ordenados a=(v,w), v e w ∈ V: as arestas do grafo. Seja, por exemplo, o grafo G(V,A) dado por: V = { p | p é uma pessoa } A = { (v,w) | < v é amigo de w > } Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G1) é dado por: G1: V = { Maria, Pedro, Joana, Luiz } A = { (Maria, Pedro) , (Joana, Maria) , (Pedro, Luiz) , (Joana, Pedro) } Neste exemplo estamos considerando que a relação é uma relação simétrica, ou seja, se então . Como conseqüência, as arestas que ligam os vértices não possuem qualquer orientação DIGRAFO (Grafo Orientado) Considere, agora, o grafo definido por: V = { p | p é uma pessoa da família Castro } A = { (v,w) | < v é pai/mãe de w > } Um exemplo de deste grafo (ver G2) é: V = { Emerson, Isadora, Renata, Antonio, Rosane, Cecília, Alfredo } A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio)} A relação definida por A não é simétrica pois se , não é o caso de . O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos. G2: 68 ORDEM A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G. Nos exemplos ao lado: • • ordem(G1) = 4 ordem(G2) = 6 ADJACÊNCIA Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e Pedro em G1. No caso do grafo ser dirigido (a exemplo de G2), a adjacência (vizinhança) é especializada em: Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Emerson e Antonio são sucessores de Alfredo. Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Alfredo e Cecília são antecessores de Antonio. GRAU O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G1, por exemplo: • • grau(Pedro) = 3 grau(Maria) = 2 No caso do grafo ser dirigido (a exemplo de G2), a noção de grau é especializada em: Grau de emissão: o grau de emissão de um vértice v corresponde ao número de arcos que partem de v. Em G2, por exemplo: • grauDeEmissao(Alfredo) = 2 Grau de recepção: o grau de recepção de um vértice v corresponde ao número de arcos que chegam a v. Em G2, por exemplo: • grauDeRecepção(Alfredo) = 0 FONTE Um vértice v é uma fonte se grauDeRecepção(v) = 0. É o caso dos vértices Isadora, Alfredo e Cecília em G2. SUMIDOURO Um vértice v é um sumidouro se grauDeEmissão(v) = 0. É o caso dos vértices Renata e Emerson em G2. 69 GRAFO REGULAR Um grafo é dito ser regular quando todos os seus vértices têm o mesmo grau. O grafo G4, por exemplo, é dito ser um grafo regular-3, pois todos os seus vértices tem grau 3. GRAFO COMPLETO Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo. Um grafo Kn possui o número máximo possível de arestas para um dado número de nós n. Ele é, também regular-(n-1), pois todos os seus vértices tem grau n-1. GRAFO BIPARTIDO Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro de V2. Para exemplificar, sejam os conjuntos H={h | h é um homem} e M={m | h é um mulher} e o grafo G(V,A) (ver o exemplo G5) onde: • • G4: V=HUM A = {(v,w) | (v ∈ H e w ∈ M) ou (v ∈ M e w ∈ H) e } G5: O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém duas partições de 3 vértices cada. Ele é completo pois todos os vértices de uma partição estão ligados a todos os vértices da outra partição. G6: K3,3 70 GRAFO VALORADO Um grafo G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números. Para exemplificar (ver o grafo G7), seja G(V,A) onde: • • G7: V = {v | v é uma cidade com aeroporto} A = {(v,w,t) | } MULTIGRAFO Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas arestas entre pares de vértices de G. No grafo G8, por exemplo, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo. SUBGRAFO Um grafo Gs(Vs, As) é dito ser subgrafo de um grafo G(V,A) quando Vs ⊂ V e As ⊂ A. O grafo G9, por exemplo, é subgrafo de G8. G9: G8: CADEIA Uma cadeia é uma seqüência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para grafos orientados, bastando que se ignore o sentido da orientação dos arcos. A seqüência de vértices (x6, x5, x4, x1) é um exemplo de cadeia em G11. Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice. É dita ser simples se não passa duas vezes pela mesma aresta (arco). O comprimento de uma cadeia é o número de arestas (arcos) que a compõe. G11: 71 CAMINHO Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados. A seqüência de vértices (x1, x2, x5, x6, x3) é um exemplo de caminho em G11. CICLO Um ciclo é uma cadeia simples e fechada (o vértice inicial é o mesmo que o vértice final). A seqüência de vértices (x1, x2, x3, x6, x5, x4, x1) é um exemplo de ciclo elementar em G11. CIRCUITO Um circuito é um caminho simples e fechado. A seqüência de vértices (x1, x2, x5, x4, x1) é um exemplo de circuito elementar em G11. FECHO TRANSITIVO O fecho transitivo direto (ftd) de um vértice v é o conjunto de todos os vértices que podem ser atingidos por algum caminho iniciando em v. O ftd do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x3, x4, x5, x6}. Note que o próprio vértice faz parte do ftd já que ele é alcançável partindo-se dele mesmo. O fecho transitivo inverso (fti) de um vértice v é o conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho. O fti do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x4, x5, x7}. Note que o próprio vértice faz parte do fti já que dele se pode alcançar ele mesmo. GRAFO CONEXO Um grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia ligando cada par de vértices deste grafo G. G12: G13: GRAFO DESCONEXO Um grafo G(V,A) é dito ser desconexo se há pelo menos um par de vértices que não está ligado por nenhuma cadeia. PONTE G14: Uma aresta é dita ser um a ponte se sua remoção provoca um redução na conexidade do grafo. As arestas (x1, x2) em G13 e G14 são exemplos de pontes. 72 ÁRVORE Uma árvore é um grafo conexo sem ciclos. Seja G(V,A) um grafo com ordem n > 2; as propriedades seguintes são equivalentes para caracterizar G como uma árvore: 1. 2. 3. 4. G é conexo e sem ciclos; G é sem ciclos e tem n-1 arestas; G é conexo e tem n-1 arestas; G é sem ciclos e por adição de uma aresta se cria um ciclo e somente um; 5. G é conexo, mas deixa de sê-lo se uma aresta é suprimida (todas as arestas são pontes); 6. todo par de vértices de G é unido por uma e somente uma cadeia simples. ARBORESCÊNCIA Uma arborescência é uma árvore que possui uma raiz. Aplica-se, portanto, somente a grafos orientados. G21: G20: FLORESTA Uma floresta é um grafo cujas componentes conexas são árvores. G22: 73 Fluxos em Rede Uma rede é definida como um grafo orientado G(V,A) atravessado por um fluxo F = {f1, f2, ..., fm} que circula em seus m arcos. Em uma rede, normalmente temos três tipos de nós: Nós de oferta ou fontes, que representam entidades que produzem ou distribuem um determinado produto; Nós de demanda ou sumidouros, que representam entidades que consomem ou requerem uma determinada demanda do produto; Nós de transbordo, que representam somente “pontos de passagem” para os produtos. São cruzamentos, cidades, computadores ou quaisquer outras entidades que não produzem e nem consomem nada, mas são somente pontos intermediários entre as ofertas e as demandas. Temos abaixo alguns exemplos de redes, onde os nós s representam as ofertas, os nós t representam as demandas, e os demais nós são nós de transbordo. Os valores em cada arco representam, em geral, custos de transporte, distâncias ou tempos de viagem entre cada par de nós. Figura 1 Figura 2 Figura 3 Repare que na Figura 1 temos o caso mais simples, onde há somente um nó de oferta e um de demanda. Essa topologia é usada, por exemplo, na determinação de um caminho mais curto entre dois nós, em problemas de fluxo máximo, e em redes PERT. Na Figura 2, temos diversos nós de oferta e de demanda. Esse grafo poderia representar, por exemplo, um caso típico onde temos diversas fábricas ou atacadistas que desejam distribuir um ou mais produtos para determinadas cidades ou lojas. 74 Na Figura 3, o nó de oferta (e.g. uma fábrica) possui diversos centros de distribuição (s1, s2 e s3), que por sua vez distribuem o produto pela rede até outros centros intermediários (e.g. atacadistas ou armazéns), que por sua vez abastassem o consumidor (que poderia ser mais de um, no caso). Em todos esses tipos de problema, no entanto, o que normalmente se busca determinar é o fluxo da rede tal que o custo, o tempo ou a distância total de transporte seja minimizado, ou que o fluxo total seja maximizado. Para isso, devemos determinar o fluxo em cada arco que liga cada par de nós i e j: i xij j Conhecendo o custo cij em cada arco para se transportar cada unidade desse fluxo, podemos calcular o custo total do transporte no grafo todo como sendo: Custo Total = ∑∑ cij xij , i =1 j =1 n n ∀(i, j ) ∈ A ou: Custo Total = ( i , j )∈A ∑ cij xij onde A é o conjunto de arcos do grafo. Além do custo ou distância em cada arco, como mostra as figuras anteriores, é comum também representarmos os limites mínimos e máximos dos fluxos nos arcos, como na figura abaixo. Chamamos essas restrições de capacidade nos arcos. i (cij, lij, uij) j onde devemos ter, obrigatoriamente, lij ≤ xij ≤ uij ∀(i, j ) ∈ A Da mesma forma, podemos ter restrições de capacidade nos nós. Um exemplo seria o da Figura 3 mostrado anteriormente, onde os centros de distribuição s1, s2 e s3 e os armazéns t1 e t2 teriam capacidades mínimas e/ou máximas associadas a elas (como poderíamos modelar isso?). Formulação Geral (Clássica) para Problemas de Fluxos em Rede Para modelarmos um problema de fluxo em rede, podemos usar o mesmo princípio de conservação de fluxo que é usado, por exemplo, para circuitos elétricos. Para isso, consideremos um nó i qualquer para onde chegam e de onde saem determinados arcos (fluxos): i 75 Podemos calcular a soma total dos fluxos que saem do nó i como sendo: Fluxo total que sai do nó i = ( i , j )∈ A ∑ xij Da mesma forma, podemos calcular a soma total dos fluxos que chegam ao nó i como sendo: Fluxo total que chega ao nó i = ( k ,i )∈ A ∑ xki Para os nós de oferta, temos que o fluxo total que sai do nó não poderá exceder a sua capacidade máxima de oferta si. Além disso, podemos enxergar o fluxo que chega ao nó de oferta como sendo um aumento de sua capacidade de produção ou oferta. Portanto, para cada nó de oferta deverá existir uma restrição com o seguinte formato: (fluxo total que sai do nó i) ≤ si + (fluxo total que chega ao nó i) ou... ( i , j )∈ A ∑ ∑ xij ≤ si + xij − ( k ,i )∈ A ∑ xki (1) ou... ( i , j )∈ A ( k ,i )∈ A ∑ xki ≤ si Para os nós de demanda, temos que o fluxo total que chega ao nó deverá ser exatamente igual à sua demanda di. Além disso, podemos enxergar o fluxo que sai do nó de demanda como sendo um aumento de sua demanda. Em outras palavras, devemos fazer com que o fluxo resultante ou que efetivamente permanece no nó de demanda seja igual a di. Portanto, para cada nó de demanda deverá existir uma restrição com o seguinte formato: (fluxo total que chega ao nó i) = di + (fluxo total que sai do nó i) ou... ( k ,i )∈A ∑ ∑ xki = d i + xki − ( i , j )∈A ∑ xij ou... ( k ,i )∈A ( i , j )∈ A ∑ xij = di Podemos ainda fazer com que o lado esquerdo da equação acima fique igual à Eq.1, bastando multiplicá-la por (-1): ( i , j )∈ A ∑ xij − ( k ,i )∈ A ∑ xki = −di (2) Para os nós de transbordo, temos que o fluxo total que sai do nó deverá ser exatamente igual ao fluxo que chega ao nó, já que não há produção nem consumo no nó. Portanto, para cada nó de transbordo deverá existir uma restrição com o seguinte formato: (fluxo total que sai do nó i) = (fluxo total que chega ao nó i) ou... 76 ( i , j )∈ A ∑ ∑ xij = xij − ( k ,i )∈ A ∑ xki xki = 0 (3) ou... ( i , j )∈ A ( k ,i )∈A ∑ Com isso, o modelo completo pode ser escrito da seguinte forma: Minimizar Custo Total = s.a. ( i , j )∈A ∑ cij xij ∀i ∈ S ∀i ∈ D ∀i ∈ T ( i , j )∈ A ∑ ∑ ∑ xij − xij − xij − ( k ,i )∈ A ∑ ∑ ∑ xki ≤ si xki = −di xki = 0 ( i , j )∈ A ( k ,i )∈ A ( i , j )∈ A ( k ,i )∈A lij ≤ xij ≤ uij ∀(i, j ) ∈ A onde: A = conjunto dos arcos do grafo G = (V, A); S = conjunto dos nós de oferta; D = conjunto dos nós de demanda; T = conjunto dos nós de transbordo; xij = fluxo no arco (i, j); cij = custo por unidade do fluxo no arco (i, j); si = capacidade máxima de oferta dos nós i ∈ S; di = demanda dos nós i ∈ D; lij = limite mínimo para o fluxo no arco (i, j); uij = limite máximo para o fluxo no arco (i, j). A última restrição, que limita o fluxo nos arcos, poderá existir ou não. Quando existir, dizemos que o problema é capacitado. Caso contrário, o problema é não-capacitado, e essa restrição poderá ser substituída por: xij ≥ 0 ∀(i, j ) ∈ A Veja que, para que o modelo seja viável, devemos ter, obrigatoriamente: ∑s ≥ ∑d i j ∀i ∈ S , j ∈ D 77 Sistemas Equilibrados Em sistemas ditos equilibrados, temos que: ∑s = ∑d i j ∀i ∈ S , j ∈ D Nesses casos, podemos escrever o modelo da seguinte forma: Minimizar s.a. si  ∑ A xij − ( k∑ A xki = −di ( i , j )∈ ,i )∈ 0  ∀i ∈ S ∀i ∈ D ∀i ∈ T ( i , j )∈ A ∑ cij xij Uma outra forma de escrever as restrições de conservação de fluxo é a seguinte: Fluxo que chega ao nó i Fluxo produzido no nó i Fluxo que sai do nó i Fluxo consumido pelo nó i + = + Podemos considerar o fluxo produzido em um nó como sendo a sua capacidade máxima de oferta, caso o nó seja de oferta. Caso contrário, o fluxo produzido no nó é igual a zero. Da mesma forma, podemos considerar o fluxo consumido por um nó como sendo a sua demanda, caso o nó seja de demanda. Caso contrário, o fluxo consumido pelo nó é igual a zero. Alguns nós podem inclusive ter, ao mesmo tempo, uma capacidade de oferta e uma demanda interna, o que é facilmente resolvido na expressão acima. Veja que, seja ou não o sistema equilibrado, teremos sempre uma variável xij para cada arco do grafo, e também uma restrição para cada nó do grafo. 78 O Problema de Fluxo de Custo Mínimo (PFCM) Este problema possui papel principal entre os modelos de otimização em redes, uma vez que ele engloba uma enorme quantidade de aplicações e pode ser resolvido de maneira extremamente eficiente. O Problema de Transporte, de Designação, de Caminho Mais Curto e de Fluxo Máximo, que veremos mais adiante, são casos especiais do PFCM. Todos esses problemas citados acima são Problemas de Programação Linear, logo o Simplex pode ser utilizado para sua resolução. No entanto, uma versão específica do Simplex, denominada Método Simplex de Redes, pode ser utilizada de maneira ainda mais eficiente do que o próprio Simplex. Algumas Considerações A rede é representada por um Dígrafo (orientada) e conectada. No mínimo um dos nós é um nó de oferta (origem). No mínimo um dos nós é um nó de demanda (destino). Todos os nós restantes são nós de transbordo (entreposto, intermediário, transshipment). A rede possui arcos, tanto quanto forem necessários, com capacidade suficiente para habilitar todos os fluxos gerados nos nós de fornecimento para alcançar os nós de demanda. 6. O custo do fluxo através de cada arco é proporcional à quantidade daquele fluxo, onde o custo por unidade de fluxo é conhecido (cij). 7. O objetivo é minimizar o custo total de enviar o fornecimento disponível através da rede para satisfazer a demanda dada (um objetivo alternativo é maximizar o lucro total para fazer isto). 1. 2. 3. 4. 5. Exemplos de Aplicações A mais importante aplicação está em planejar a operação de uma rede de distribuição de uma companhia. Este tipo de aplicação envolve determinar um plano para transportar bens a partir das fontes (fábricas, etc.) para locais de armazenagem intermediárias (quando necessário) e então para os clientes (demanda). Tipo de Aplicação Operação de uma rede de distribuição Gerenciamento de detritos sólidos Operações de uma rede de fornecimento Gerenciamento de fluxo de dinheiro Coordenação de mistura de produtos em plantas Exemplo 1: Considere a rede representada pelo grafo a seguir, onde temos: • Dois nós de oferta (A e B), com capacidade de 60 e 50 unidades, respectivamente; • Dois nós de demanda (D e E), com capacidade de 30 e 60 unidades, respectivamente; • Um nó de transbordo (C). 79 Nós de Fornecimento Fontes de bens Fontes de resíduos Vendedores Fontes de dinheiro em um tempo específico Plantas Nós de Transbordo Locais de armazenagem intermediárias Instalações de processamento Estoques intermediários Nós de Demanda Clientes Locais de depósitos de resíduos sólidos Instalações de processamento Necessidades de dinheiOpções de investiro em um tempo especímento fico Produção de um pro- Mercado para um produto específico duto específico Temos também os custos de transporte cij e as capacidades máximas de fluxo dos arcos AB e CE. sA = 60 A cAD = 9 cAC = 4 cED = 2 cAB = 2 uAB = 10 cBC = 3 B sB = 50 C cCE = 1 uCE = 80 E dE = 60 cDE = 3 dD = 30 D Podemos também representar a mesma rede da seguinte forma: bA = 60 A bD = –30 D (2, 0, ∞) (2, 0, 10) C (1, 0, 80) (3, 0, ∞) B bB = 50 E bE = –60 (3, 0, ∞) (9, 0, ∞) (4, 0, ∞) onde os bi representam as ofertas nos nós, sendo que ofertas negativas são, na realidade, demandas. Podemos então escrever o modelo usando a formulação geral vista anteriormente: Minimizar s.a. Nó A) Nó B) Nó C) Nó D) Nó E) Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED xAB + xAC + xAD ≤ 60 xBC – xAB ≤ 50 xCE – xAC – xBC = 0 xDE – xAD – xED = –30 xED – xCE – xDE = –60 xAB ≤ 10 xCE ≤ 80 xij ≥ 0 A solução dada pelo Lindo© segue abaixo: 80 OBJECTIVE FUNCTION VALUE 1) VARIABLE XAB XAC XAD XBC XCE XDE XED 480.0000 VALUE 0.000000 30.000000 10.000000 50.000000 80.000000 0.000000 20.000000 REDUCED COST 1.000000 0.000000 0.000000 0.000000 0.000000 5.000000 0.000000 ROW Nó A) Nó B) Nó C) Nó D) Nó E) 7) 8) SLACK OR SURPLUS 20.000000 0.000000 0.000000 0.000000 0.000000 10.000000 0.000000 DUAL PRICES 0.000000 1.000000 4.000000 9.000000 7.000000 0.000000 2.000000 Esta solução pode ser vista com mais clareza se usarmos o próprio grafo para ilustrá-lo, como visto na figura abaixo. As linhas tracejadas representam arcos (variáveis) não usados na solução. bA = 60 A 30 20 C 80 50 B bB = 50 Exemplo 2: Considere agora a rede representada pelo grafo a seguir, diferindo do anterior somente por ser um sistema equilibrado e totalmente não-capacitado. Nesse caso, os arcos são rotulados somente com seus custos cij: E bE = –60 10 bD = –30 D 81 bA = 50 A 4 2 C 1 3 B bB = 40 9 bD = –30 D 2 3 E bE = –60 Podemos então escrever o modelo usando a formulação geral vista anteriormente: Minimizar s.a. Nó A) Nó B) Nó C) Nó D) Nó E) Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED xAB + xAC + xAD = 50 xBC – xAB = 40 xCE – xAC – xBC = 0 xDE – xAD – xED = –30 xED – xCE – xDE = –60 xij ≥ 0 A solução segue abaixo: OBJECTIVE FUNCTION VALUE 1) VARIABLE XAB XAC XAD XBC XCE XDE XED 470.0000 VALUE 0.000000 50.000000 0.000000 40.000000 90.000000 0.000000 30.000000 REDUCED COST 1.000000 0.000000 2.000000 0.000000 0.000000 5.000000 0.000000 ROW Nó A) Nó B) Nó C) Nó D) Nó E) SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 DUAL PRICES 0.000000 1.000000 4.000000 7.000000 5.000000 82 bA = 50 A 50 bD = –30 D 30 C 90 40 B bB = 40 E bE = –60 Transformando Sistemas Não Equilibrados em Sistemas Equilibrados Caso o sistema não seja equilibrado, é fácil transformá-lo em um sistema equilibrado. Basta acrescentarmos um nó de demanda artificial, cuja demanda será igual à diferença entre a oferta total e a demanda total do sistema. Depois, ligamos todos os nós de oferta a esse nó artificial por meio de arcos com custo igual a zero. Fazendo isso, a função-objetivo original não será afetada, e a oferta excedente será naturalmente “escoada” dos nós de oferta para esse nó artificial. Podemos ver isso usando o Exemplo 1 visto anteriormente: bA = 60 A cAr = 0 br = –20 r cAB = 2 uAB = 10 cBr = 0 B bB = 50 cBC = 3 C cCE = 1 uCE = 80 E bE = –60 cDE = 3 cAD = 9 cAC = 4 cED = 2 bD = –30 D Essa nova rede terá, em seu modelo de PL, uma restrição adicional, correspondendo ao nó artificial r, e duas novas variáveis, devido à ligação desse nó com os dois nós de oferta: Minimizar s.a. Nó A) Nó B) Nó C) Nó D) Nó E) Nó r) Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED xAB + xAC + xAD + xAr = 60 xBC + xBr – xAB = 50 xCE – xAC – xBC = 0 xDE – xAD – xED = –30 xED – xCE – xDE = –60 – xAr – xBr = –20 xAB ≤ 10; xCE ≤ 80; xij ≥ 0 83 Resolvendo o modelo através do Lindo, vemos que a folga que existia para o “Nó A” agora é transformada no fluxo xAr: OBJECTIVE FUNCTION VALUE 1) VARIABLE XAB XAC XAD XBC XCE XDE XED XAR XBR 480.0000 VALUE 0.000000 30.000000 10.000000 50.000000 80.000000 0.000000 20.000000 20.000000 0.000000 REDUCED COST 1.000000 0.000000 0.000000 0.000000 0.000000 5.000000 0.000000 0.000000 1.000000 ROW Nó A) Nó B) Nó C) Nó D) Nó E) Nó R) 8) 9) SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 10.000000 0.000000 DUAL PRICES 0.000000 1.000000 4.000000 9.000000 7.000000 0.000000 0.000000 2.000000 PFCM – Formulação Restrita Uma outra maneira de modelar esse tipo de problema é “fechando” ou “curto-circuitando” a rede, como se fosse um circuito elétrico contínuo. Para fazermos isso, basta acrescentar dois novos nós: um nó fonte f que servirá como “super-oferta”, ou seja, abastecerá todos os nós de oferta i ∈ S (com fluxos xfi fixos ou constantes), e um nó sumidouro s que servirá como “super-demanda”, ou seja, escoará a demanda de todos os nós de demanda j ∈ D (também com fluxos xjs fixos ou constantes). Já que nessa rede não haverá aumento nem diminuição do fluxo total (assim como num circuito elétrico fechado a corrente total é constante), devemos ter, a princípio, um sistema equilibrado. Caso o sistema não seja equilibrado, devemos adicionar ainda um terceiro nó de demanda “artificial”, como descrito anteriormente. Com esses procedimentos, teremos uma rede dita “conservativa”, e podemos utilizar um conceito de conservação de fluxo (ou “corrente”) perfeita em cada nó (conhecida como a primeira Lei de Kirschoff), e a restrição de fluxo de cada nó seguirá o seguinte formato: Soma dos fluxos que chegam ao nó i Soma dos fluxos que saem do nó i = Para exemplificar o uso da formulação restrita, usaremos a rede do Exemplo 2, que já é equilibrada, e acrescentaremos somente os nós f e s, juntamente com os arcos correspondentes: 84 bA = 50 A 0 bf = 90 f 2 C 0 B bB = 40 0 1 3 4 9 bD = –30 D 0 2 3 bs = –90 s 0 E bE = –60 Podemos então escrever o modelo da seguinte maneira: Minimizar s.a. Nó A) Nó B) Nó C) Nó D) Nó E) Nó f) Nó s) Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED xAB + xAC + xAD – xf A = 0 xBC – xAB – xf B = 0 xCE – xAC – xBC = 0 xDE + xDs – xAD – xED = 0 xED + xEs – xCE – xDE = 0 xf A + xf B – xsf = 0 xsf – xDs – xDs = 0 xf A = 50 xf B = 40 xDs = 30 xEs = 60 xij ≥ 0 Propriedades da Matriz “A” de Coeficientes Tecnológicos Considere novamente a rede vista anteriormente no Exemplo 2: bA = 50 A 4 2 C 1 3 B bB = 40 E bE = –60 85 9 bD = –30 D 2 3 Iremos agora escrever o modelo de PL, colocando cada variável em uma coluna distinta, já em um formato que se assemelha ao “quadro simplex”: Minimizar Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED s.a. Nó A) xAB + xAC + xAD Nó B) – xAB + xBC Nó C) – xAC – xBC + xCE Nó D) – xAD xDE Nó E) – xCE – xDE – xED + xED = = = = = 50 40 0 –30 –60 Escrevendo a matriz A separadamente, em forma de tabela, somente com os coeficientes das variáveis, temos: Nós A B C D E Arcos xBC +1 –1 –1 –1 xAB +1 –1 xAC +1 –1 xAD +1 xCE xDE xED +1 +1 –1 –1 +1 Repare que, como temos exatamente uma variável xij para cada arco do grafo, e como cada arco (i, j) “sai” do nó i e “entra” no nó j, temos então que cada vetor-coluna da matriz A associado à variável xij terá a forma: ei – ej onde ei e ej são vetores unitários. A principal propriedade da matriz A é a total unimodularidade. Dizemos que uma matriz é totalmente unimodular quando qualquer sub-matriz quadrada de A possui determinante igual a 0, 1 ou – 1. Por causa dessa propriedade, as soluções ótimas obtidas pelo algoritmo Simplex levando-se em conta o sistema linear Ax = b, serão sempre inteiras, desde que os valores de bi sejam também inteiros. Como já vimos também, a solução juntamente com a respectiva Base segue abaixo: bA = 50 A 50 30 C 90 40 B bB = 40 E bE = –60 86 bD = –30 D Nós A B C D E xAC +1 –1 Arcos xBC xCE +1 –1 xED +1 –1 –1 +1 O Problema de Transporte (PT) O problema de transporte é um caso especial do PFCM, onde a rede pode ser representada por um grafo bipartido. Isso significa que não existem nós de transbordo (intermediários ou de transição) para o fluxo. Além disso, não existem arcos ligando entre si os nós de oferta ou os nós de demanda. O objetivo nesse caso é descobrir somente as quantidades do produto que cada nó de oferta enviará para cada nó de demanda. A maneira como esses fluxos serão enviados (os trajetos) já é conhecida de antemão. cij o1 d1 d2 o2 d3 o3 d4 o4 d5 nós de oferta (m) nós de demanda (n) Na visão clássica desse problema, os arcos não possuem limite de capacidade para o fluxo (mas é possível que esses limites existam em alguns casos práticos). O PT consiste então em determinar o fluxo entre cada par de nós (i, j), onde i = 1, 2, ..., m, e j = 1, 2, ..., n, de tal forma a obter o menor custo (ou o maior lucro) total de transporte. Para que o fluxo global seja viável, devemos observar também as mesmas restrições já vistas para o PFCM, ou seja: • • As capacidades dos nós de oferta não devem ser ultrapassadas; As demandas devem ser atendidas. Formulação Geral (Clássica) para o PT Para o PT, podemos usar o mesmo modelo geral usado para o PFCM. No entanto, podemos fazer algumas simplificações, já que, para esse problema, • • • Não existem nós de transbordo; Só existem arcos saindo dos nós de oferta; Só existem arcos chegando aos nós de demanda. Com isso, o modelo pode ser escrito assim: 87 Minimizar Custo Total = ( i , j )∈A ∑ cij xij s.a. ( i , j )∈ A ∑ xij ≤ si xij = −d j ∀i ∈ S − ( i , j )∈ A ∑ ∀j ∈ D ∀(i, j ) ∈ A lij ≤ xij ≤ uij onde: A = conjunto dos arcos do grafo G = (V, A); S = conjunto dos nós de oferta; D = conjunto dos nós de demanda; xij = fluxo no arco (i, j); cij = custo por unidade do fluxo no arco (i, j); si = capacidade máxima de oferta dos nós i ∈ S; dj = demanda dos nós j ∈ D; lij = limite mínimo para o fluxo no arco (i, j); uij = limite máximo para o fluxo no arco (i, j). Para os problemas não-capacitados, a última restrição poderá ser substituída por: xij ≥ 0 ∀(i, j ) ∈ A Apesar do modelo acima ser válido e seguir o padrão dos problemas de fluxo em rede, uma outra forma, talvez mais natural ou intuitiva de escrevê-lo é mostrado abaixo (para problemas nãocapacitados): Min. s.a. ( i , j )∈ A ∑ ∑ ∑ cij xij xij ≤ si xij = d j i = 1, 2,3,..., m j = 1, 2, 3,..., n ∀(i, j ) ∈ A ( i , j )∈ A ( i , j )∈ A xij ≥ 0 Para sistemas equilibrados, podemos ainda escrever: Min. s.a. ( i , j )∈ A ∑ ∑ ∑ cij xij xij = si xij = d j i = 1, 2,3,..., m j = 1, 2, 3,..., n ∀(i, j ) ∈ A ( i , j )∈ A ( i , j )∈ A xij ≥ 0 88 Exemplo 1: Considere o Problema de Transporte representado pelo grafo abaixo. Note que os valores ao lado dos nós são as ofertas (si) e as demandas (dj), e os valores nos arcos são os custos cij. 4 50 1 4 5 50 2 6 50 3 2 4 7 3 1 20 2 15 3 18 4 25 Usando a forma clássica, o modelo de PL que resolve esse problema pode ser escrito assim: Min. s.a. Z = 4x11 + 3x12 + 4x21 + 5x22 + 7x23 + 6x24 + 2x33 + 4x34 s1) s2) s3) d1) d2) d3) d4) x11 + x12 ≤ 50 x21 + x22 + x23 + x24 ≤ 50 x33 + x34 ≤ 50 x11 + x21 = 20 x12 + x22 = 15 x23 + x33 = 18 x24 + x34 = 25 xij ≥ 0 A solução dada pelo Lindo© segue abaixo: OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X21 X22 X23 X24 X33 X34 261.0000 VALUE 20.000000 15.000000 0.000000 0.000000 0.000000 0.000000 18.000000 25.000000 REDUCED COST 0.000000 0.000000 0.000000 2.000000 5.000000 2.000000 0.000000 0.000000 ROW S1) S2) S3) D1) D2) D3) D4) SLACK OR SURPLUS 15.000000 50.000000 7.000000 0.000000 0.000000 0.000000 0.000000 DUAL PRICES 0.000000 0.000000 0.000000 -4.000000 -3.000000 -2.000000 -4.000000 89 O grafo que representa essa solução é dado abaixo: 20 50 1 15 1 20 2 50 2 3 18 50 3 25 4 15 18 25 Exemplo 2: Nesse caso, podemos lançar mão do mesmo artifício apresentado no PFCM para equilibrar sistemas cuja oferta é maior que a demanda, simplesmente introduzindo um nó artificial de demanda, como mostra o grafo abaixo. 4 50 1 0 50 2 0 50 3 2 4 6 4 5 7 3 1 20 2 15 3 18 4 0 5 25 72 No exemplo acima, o nó 5 representa um nó de demanda artificial, cuja demanda (72) é a diferença entre a soma das ofertas e a soma das demandas dos nós “reais”. Usando o modelo equilibrado, podemos formular o problema assim: Min. s.a. Z = 4x11 + 3x12 + 4x21 + 5x22 + 7x23 + 6x24 + 2x33 + 4x34 s1) s2) s3) x11 + x12 + x15 = 50 x21 + x22 + x23 + x24 + x25 = 50 x33 + x34 + x35 = 50 90 d1) d2) d3) d4) d5) x11 + x21 = 20 x12 + x22 = 15 x23 + x33 = 18 x24 + x34 = 25 x15 + x25 + x35 = 72 xij ≥ 0 A solução dada pelo Lindo© segue abaixo: OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X21 X22 X23 X24 X33 X34 X15 X25 X35 261.0000 VALUE 20.000000 15.000000 0.000000 0.000000 0.000000 0.000000 18.000000 25.000000 15.000000 50.000000 7.000000 REDUCED COST 0.000000 0.000000 0.000000 2.000000 5.000000 2.000000 0.000000 0.000000 0.000000 0.000000 0.000000 O grafo que representa essa solução é dado abaixo: 20 50 1 15 15 50 2 50 18 50 3 7 5 72 25 3 18 2 15 1 20 4 25 Vale lembrar que é possível também usar o modelo restrito para o PT, assim como foi feito para o PFCM, e a propriedade de total unimodularidade também é válida, o que significa que, mesmo que as variáveis xij tenham restrições de integralidade, podemos resolver o modelo usando qualquer software que implementa o simplex (PROLIN, LINDO, LINGO, CPLEX etc.), ignorando essas restrições, e com isso aproveitando outros recursos importantes, como os valores dos custos reduzidos, preços duais e a análise de sensibilidade. 91 Exemplo 3: Uma companhia enlata ervilhas nas suas unidades C1, C2 e C3, e transporta as latas por caminhão para as suas unidades de estocagem W1, W2, W3 e W4. A tabela abaixo mostra os custos de transporte, a disponibilidade das unidades Ci e as necessidades dos estoques Wj. Deseja-se determinar a distribuição das unidades Ci para os estoques Wj, de modo a minimizar o custo do transporte. Custo do Transporte ($ / caminhão) W2 W3 513 654 416 690 682 388 65 70 Origem C1 C2 C3 Demanda W1 464 352 995 80 W4 867 791 685 85 Disponibilidade 75 125 100 Nesse caso temos um grafo bipartido completo K3,4, pois cada unidade Ci pode enviar caminhões para qualquer um dos estoques Wj. Com isso, teremos 3 × 4 = 12 variáveis, e 3 + 4 = 7 restrições. Já que o modelo é também equilibrado, podemos escrevê-lo assim: Min. Z= 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22 + 690x23 + 791x24 + 995x31 + 682x32 + 388x33 + 685x34 x11 + x12 + x13 + x14 = 75 x21 + x22 + x23 + x24 = 125 x31 + x32 + x33 + x34 = 100 x11 + x21 + x31 = 80 x12 + x22 + x32 = 65 x13 + x23 + x33 = 70 x14 + x24 + x34 = 85 xij ≥ 0 s.a. C1) C2) C3) W1) W2) W3) W4) A solução dada pelo Lindo© segue abaixo: OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 ROW C1) C2) C3) W1) W2) W3) W4) 152535.0 VALUE 0.000000 20.000000 0.000000 55.000000 80.000000 45.000000 0.000000 0.000000 0.000000 0.000000 70.000000 30.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 REDUCED COST 15.000000 0.000000 84.000000 0.000000 0.000000 0.000000 217.000000 21.000000 728.000000 351.000000 0.000000 0.000000 DUAL PRICES 0.000000 97.000000 182.000000 -449.000000 -513.000000 -570.000000 -867.000000 92 O grafo que representa essa solução é dado abaixo: C1 80 20 45 W1 W2 C2 55 W3 70 C3 30 W4 Apesar de ser possível o uso do Simplex Primal tradicional para a resolução do PT, existem variações do Simplex que normalmente são usados de maneira muito mais eficiente, o que possibilita resolver problemas bem maiores sem a necessidade da modelagem explícita. Uma das simplificações pode ser observada no início do algoritmo. Ao invés de usar o método das duas fases ou do grande M para obter uma SBV inicial, podemos usar o método do canto noroeste. Esta é, na verdade, uma heurística gulosa, que busca uma solução simples por meio da própria tabela de ofertas × demandas: W1 75 5 80 5 W2 65 65 W3 55 15 70 15 W4 Disponibilidade 75 125 120 55 100 85 C1 C2 C3 Demanda 85 85 Essa solução inicial, não ótima, teria um custo de transporte de $165.595,00 (contra um ótimo de $152.535,00). Com isso, os “pivoteamentos” começariam dessa solução inicial. C1 75 5 W1 65 C2 W2 55 W3 15 C3 85 W4 93 O Problema de Designação (PD) Este problema, também chamado de Problema de Atribuição, de Alocação ou de Casamento (1Matching), é um caso especial do Problema de Transporte. O enunciado clássico desse problema segue abaixo: Dado um conjunto de n máquinas, numeradas como 1, 2, ..., n, e um conjunto de n tarefas, também numeradas como 1, 2, ..., n, e o custo da designação de cada tarefa para cada máquina (cij), deseja-se determinar uma designação que minimize o custo total de alocação das tarefas, observadas ainda as seguintes restrições: • Cada máquina só poderá realizar uma única tarefa; • Cada tarefa só poderá ser realizada por uma única máquina. Máquinas (ofertas) 1 Tarefas (demanda) 1 2 2 3 3 4 4 Esse problema tem uma ampla gama de aplicações, como designação de tarefas, alocação de vagas, alocação de professores em turmas e salas de aula, agências de casamento, distribuição de médicos entre hospitais, alocação dinãmica de táxis entre clientes, entre outros. Este problema também pode ser visto com caso especial do Problema de Emparelhamento (PE), os as mesmas alocações são feitas entre pares de nós, mas não necessariamente em um grafo bipartido. Podemos enxergar esse problema como se fosse um PT equilibrado, onde todas as ofertas e demandas são unitárias, ou seja, si = di = 1, ∀ i = 1, 2, ..., n. Com isso, podemos escrever o modelo de PL da seguinte forma: Min. s.a. ∑∑ c x i =1 j =1 n n ij ij ∑x j =1 n ij =1 i = 1, 2, 3,..., n j = 1, 2, 3,..., n ∀i, j ∑x i =1 n ij =1 xij ∈{0,1} Veja que a nossa variável de decisão é binária, ou seja, teremos: 94 1 se a máquina i estiver designada à tarefa j; xij =  0 caso contrário. Isso significa que a variável de decisão xij irá simplesmente determinar a existência ou não de um arco no grafo que representa a solução. Novamente aqui temos também a propriedade de total unimodularidade da matriz A, e portanto essa restrição de integralidade pode ser relaxada se quisermos resolver o problema usando o modelo matemático. Algoritmo Húngaro ou Algoritmo de Rotulação Um algoritmo comumente encontrado na literatura para a resolução do PD é na verdade uma variação bastante simples do simplex primal-dual. Usaremos um exemplo para mostrar o funcionamento desse algoritmo. Exemplo 1: Encontre uma solução ótima para o PD contendo 4 máquinas e 4 tarefas, onde a matriz de custos é mostrada abaixo. Tarefas cij Máquinas 1 2 3 4 Aplicação do Algoritmo: 1. Determinar o menor valor para cada linha da matriz: Valor Mínimo na Linha (ui) 1 2 3 1 1 1 4 6 5 2 3 2 7 4 3 4 4 8 2 4 5 7 3 1 1 4 6 5 3 2 7 4 4 4 8 2 5 7 3 1 2. Subtrair do valor em cada linha, o mínimo ui daquela linha: 0 2 3 4 2 0 4 3 3 2 5 1 4 5 0 0 3. Determinar o menor valor para cada coluna dessa matriz resultante: 95 0 2 3 4 0 2 0 4 3 0 3 2 5 1 1 4 5 0 0 0 Valor Mínimo na Coluna (vj) 4. Subtrair do valor em cada coluna, o mínimo vj daquela coluna: 0 2 3 4 2 0 4 3 2 1 4 0 4 5 0 0 Essa matriz obtida é chamada de matriz reduzida. As designações que minimizam o custo total são aquelas cujo “custo reduzido” cij é igual a zero. Como nesse caso n = 4, devemos escolher um fluxo contendo 4 designações que minimizam o custo. Temos então as seguintes opções: 0 2 3 2 0 4 2 1 4 4 5 0 0 2 3 2 0 4 2 1 4 4 5 0 0 2 3 2 0 4 2 1 4 4 5 0 4 3 0 0 Configuração 1 (inviável) 4 3 0 0 Configuração 2 (ótima) 4 3 0 0 Configuração 3 (inviável) O número máximo de células com custo reduzido zero tal que não mais de duas ocupem a mesma linha é igual ao número mínimo de linhas horizontais e/ou verticais necessárias para cobrir todas as células nulas da matriz. Essas células são chamadas independentes. Temos então o seguinte teorema: O número máximo de células independentes em um quadro reduzido do problema de designação é igual ao número mínimo de linhas necessárias para cobrir todos os zeros da matriz. No exemplo acima, veja que é necessário no mínimo 4 linhas para cobrir todas as células nulas da matriz. Exemplos dessa cobertura são dados abaixo: 0 2 3 4 2 0 4 3 2 1 4 0 4 5 0 0 0 2 3 4 2 0 4 3 2 1 4 0 4 5 0 0 0 2 3 4 2 0 4 3 2 1 4 0 4 5 0 0 Neste exemplo temos então uma única solução ótima, mostrada acima na “Configuração 2”, que fornece um custo total igual a 12. O grafo que representa essa solução é mostrado seguir (nos arcos foram colocados os custos das designações, obtidos da matriz original do problema): 96 Máquinas 1 1 Tarefas 1 2 2 2 3 8 1 3 4 4 Exemplo 2: Considere agora o seguinte PD, também contendo 4 máquinas e 4 tarefas: Tarefas cij Máquinas 1 2 3 4 Aplicação do Algoritmo: Subtraindo o menor valor de cada linha, temos: 93 64 54 0 0 0 80 63 53 78 0 70 67 72 68 10 1 94 74 62 11 2 1 10 88 74 3 54 88 8 81 4 68 82 76 21 Agora subtraímos o menor valor de cada coluna, obtendo a seguinte matriz reduzida: 93 64 54 0 0 0 80 63 53 78 0 70 57 62 58 0 Observando os valores nulos da matriz, vemos que há duas violações de ortogonalidade da solução: 97 93 64 54 0 0 0 80 63 53 78 0 70 57 62 58 0 1. As máquinas 1 e 2 só podem realizar a tarefa 2 (sem desempate); 2. As tarefas 1 e 4 só podem ser realizadas pela máquina 4 (sem desempate). Com isso não é possível obter uma solução viável. Essa mesma conclusão pode ser obtida também com a cobertura (ou rotulação) dos zeros da matriz. Vemos que é possível cobrir todos os zeros com apenas três linhas. Uma das formas de se fazer isso é assim: 93 64 54 0 0 0 80 63 53 78 0 70 57 62 58 0 Não importa como os zeros são cobertos ou rotulados, contanto que usemos somente linhas horizontais e/ou verticais, e o número dessas linhas seja mínimo. Com a rotulação feita acima e usando o teorema visto anteriormente, chegamos à conclusão que nessa matriz reduzida encontramos no máximo três células (ou variáveis) independentes, o que não é suficiente, pois precisamos de quatro variáveis para solucionar o problema. Passamos então à etapa de rotulação propriamente dito. Para cada fluxo inviável (como o visto acima), teremos uma iteração do algoritmo. Essa iteração é feita da seguinte maneira: 5. Fazer a cobertura dos zeros usando o menor número de linhas possível (já feito acima): 93 64 54 0 0 0 80 63 53 78 0 70 57 62 58 0 Como o menor número de linhas é menor que n, não temos portanto uma solução ótima viável, e prosseguimos ao passo seguinte: 6. Determinar o menor valor descoberto. No exemplo acima, esse valor é igual a 53. 7. Subtrair esse valor de todos os valores descobertos, e somá-lo a todas as células que têm interseção entre uma linha horizontal e uma vertical: 40 11 54 0 0 0 133 116 0 25 0 70 4 9 58 0 98 Retornamos agora ao passo 5, onde encontramos o segundo fluxo inviável: 40 11 54 0 0 0 133 116 0 25 0 70 4 9 58 0 Prosseguindo novamente com os passos 6 e 7, obtemos a seguinte matriz reduzida: 36 7 50 0 0 0 133 120 0 25 0 74 0 5 54 0 Dessa matriz podemos extrair o fluxo viável indicado pelas células sombreadas acima. Seguindo esse algoritmo, todo fluxo viável produzido será ótimo. Portanto, a solução acima é ótima, com soma total mínima igual a 97. O grafo que representa essa solução é dado abaixo: 1 1 68 10 2 2 3 8 11 3 4 4 Obs.: Nos exemplos acima, obtivemos uma única solução ótima, mas é comum obtermos matrizes reduzidas contendo vários fluxos viáveis. Nesses casos, todos os fluxos viáveis obtidos serão ótimos, obviamente com valores idênticos para as funções-objetivo. Podemos resumir o algoritmo completo da seguinte maneira: Algoritmo Húngaro ou de Rotulação 1. Reduzir a matriz de custos, subtraindo das linhas o menor valor de cada linha, e depois subtraindo das colunas o menor valor de cada coluna. 2. Fazer a cobertura dos zeros usando o menor número de linhas possível. Se o menor número de linhas for igual a n, então pare, pois a matriz contém pelo menos uma solução ótima, senão prossiga ao passo 3. 3. Determinar o menor valor descoberto. Subtrair esse valor de todos os valores descobertos, e somá-lo a todas as células que têm interseção entre uma linha horizontal e uma vertical. Retornar ao passo 2. 99 O Problema do Caminho Mais Curto (PCMC) Este problema, também chamado de Problema do Caminho Mínimo, é um caso especial do Problema de Fluxo de Custo Mínimo. Como o próprio nome indica, o problema consiste em identificar o caminho mais curto entre dois nós de uma rede. 2 20 4 10 s 1 35 15 30 t 40 6 25 3 35 5 20 Aplicações: • Encontrar um caminho de distância mínima. • Encontrar um caminho de tempo de viagem mínimo. • Encontrar um caminho de custo mínimo. • Encontrar um caminho de confiabilidade máxima. Podemos enxergar esse problema como se fosse um PFCM equilibrado, com as seguintes particularidades: • Só existe um nó de oferta, correspondente ao local ou ponto de origem; • Só existe um nó de demanda, correspondente ao local ou ponto de destino; • A oferta e a demanda são unitárias, ou seja, ss = dt = 1, onde s e t são os nós de origem e destino, respectivamente. Com isso, podemos escrever o modelo de PL da seguinte forma: Minimizar s.a. 1  ∑ A xij − ( k∑ A xki = −1 ( i , j )∈ ,i )∈ 0  xij ∈{0,1} ∀i, j se i = s se i = t caso contrário ( i , j )∈ A ∑ cij xij Veja que, assim como no PD, a nossa variável de decisão é binária, ou seja, teremos: 1 se o caminho mais curto contiver o arco (i, j ); xij =  0 caso contrário. 100 Isso significa que a variável de decisão xij irá simplesmente determinar quais os arcos por onde se deve passar para que a distância, tempo ou custo total do percurso seja mínimo. Novamente aqui temos também a propriedade de total unimodularidade da matriz A e, portanto, essa restrição de integralidade pode ser relaxada se quisermos resolver o problema usando o modelo matemático. Algoritmos de Solução Exata Apesar de ser possível utilizar a modelagem matemática, variações do simplex e algoritmos de fluxo em redes para resolver esse problema, os algoritmos mais eficientes hoje usam abordagens simples em grafos. Os mais conhecidos são listados no quadro abaixo: Autores Dijkstra Ford-Moore-Bellman Ford-Fulkerson Floyd-Warshall Ano 1959 1956 1962 1962 Descrição Complexidade Seleciona o nó de menor potencial O(n²) Técnica de rotulação FIFO O(mn) Técnica de rotulação FIFO O(mn) Técnica da “operação tríplice” O(n³) O problema da determinação do menor caminho entre os vértices de um grafo pode ser definido como um dos seguintes casos: a) Determinar o menor caminho entre dois vértices dados; b) Determinar o menor caminho entre um vértice dado e os demais vértices do grafo; c) Determinar o menor caminho entre todos os pares de vértices do grafo. Entre os algoritmos citados acima, destacam-se o algoritmo de Dijkstra e o algoritmo de Floyd. O algoritmo de Dijkstra foi projetado para determinar o menor caminho entre um vértice dado e os demais vértices do grafo, e o algoritmo de Floyd se aplica na determinação do menor caminho entre todos os pares de vértices do grafo. O algoritmo de Dijkstra pode ainda ser aplicado na determinação do menor caminho entre dois vértices dados, entre todos os vértices e um vértice-destino e, também, entre todos os pares de vértices do grafo. Para isso é necessário apenas um pequeno ajuste. É um algoritmo muito eficiente e de fácil implementação, sendo um dos mais empregado na determinação de caminhos mais curtos em grafos. Algoritmo de Dijkstra Esse algoritmo é bastante simples de implementar e entender e, apesar de não ser o mais eficiente em termos de tempo de execução, nem por isso deixa de ser muito rápido. Veremos aqui a sua forma clássica, que calcula o caminho mais curto entre um nó origem e todos os demais nós da rede. No entanto, uma desvantagem desse algoritmo é que ele não funciona na presença de arestas ou arcos de custo negativo, o que não é problema em aplicações de logística, por exemplo, mas pode não ser adequado para outras aplicações. Algoritmo: Seja G(V,A) um grafo orientado e s um vértice de G: 1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais estimativas; 2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice que precede t no caminho de custo mínimo de s para t); 3. Enquanto houver vértice aberto: • Seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos; 101 • • Feche o vértice k Para todo vértice j ainda aberto que seja sucessor de k faça: o Some a estimativa do vértice k com o custo do arco que une k a j; o Caso esta soma seja melhor que a estimativa anterior para o vértice j, substituaa e anote k como precedente de j. A seqüência de diagramas a seguir ilustra o funcionamento do Algoritmo de Dijkstra: • Inicialmente todos os nodos tem um custo infinito, exceto s (a raiz da busca) que tem valor 0: vértices s u v x y estimativas 0 ∞ ∞ ∞ ∞ precedentes - - - - - • • • selecione s (vértice aberto de estimativa mínima) feche s recalcule as estimativas de u e x vértices s u v x y estimativas 0 10 ∞ 5 ∞ precedentes s s - s - • • • selecione x (vértice aberto de estimativa mínima) feche x recalcule as estimativas de u,v e y vértices s u v x y estimativas 0 8 14 5 7 precedentes s x x s x 102 • • • selecione y (vértice aberto de estimativa mínima) feche y recalcule a estimativa de v vértices s u v x y estimativas 0 8 13 5 7 precedentes s x y s x • • • selecione u (vértice aberto de estimativa mínima) feche u recalcule a estimativa de v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x • • selecione v (vértice aberto de estimativa mínima) feche v vértices s u v x y estimativas 0 8 9 5 7 precedentes s x u s x Quando todos os vértices tiverem sido fechados, os valores obtidos serão os custos mínimos dos caminhos que partem do vértice tomado como raiz da busca até os demais vértices do grafo. O caminho propriamente dito é obtido a partir dos vértices chamados acima de precedentes. Para exemplificar, considere o caminho de custo mínimo que vai de s até v, cujo custo mínimo é 9. O vértice precedente de v na última das tabelas acima é u. Sendo assim, o caminho é: s → ... → u → v Por sua vez, o precedente de u é x. Portanto, o caminho é: s → ... → x → u → v Por último, o precedente de x é o próprio vértice s. Logo, o caminho de custo mínimo é: s→x→u→v 103 O Problema de Fluxo Máximo (PFM) Considere uma rede direcionada (dígrafo) conexa, com dois nós especiais denominados Origem (nó fonte do grafo) e Destino (nó sumidouro do grafo) e ainda, associada a cada arco, capacidades mínima e máxima para o seu fluxo. O objetivo é maximizar o fluxo entre a Origem e o Destino. Exemplos de Aplicações: • Maximizar o fluxo de uma rede de distribuição de produtos de uma companhia a partir de suas fábricas para os seus clientes. • Maximizar o fluxo de óleo (ou água, gás etc.) através de um sistema de dutos. • Maximizar o fluxo de veículos através de uma rede de transporte. Exemplo 1: Considere a rede abaixo, onde os nós O e T representam tanques de armazenamento de água de origem e destino, respectivamente, e os valores dos arcos representam o fluxo máximo de cada arco (em m³/s). Determine o fluxo total máximo nessa rede. A 5 1 7 4 3 O B 2 C 4 5 4 D 1 9 T 6 E Uma solução viável é enviar um total de 7 m³/s, sendo: 5 m³/s usando a rota O → B → E → T, 1 m³/s usando a rota O → B → C → E → T, e 1 m³/s usando a rota O → B → C → E → D → T Essa solução, apesar de viável, não é a ótima. Nesse caso, duas soluções ótimas são dadas abaixo: A 4 1 7 3 3 3 O B 4 C 4 D 1 8 T 6 E 104 A 3 3 O 7 4 B 4 3 D 8 T 1 E 6 C 4 O modelo de PL para problemas de fluxo máximo difere um pouco do modelo geral visto para os outros problemas de fluxo que estudamos anteriormente. Para este tipo de problema, podemos escrever o modelo assim: Maximizar s.a. ( O , j )∈ A ∑ xOj (ou Maximizar ( i ,T )∈ A ∑ xiT ) ( O , j )∈ A ∑ xOj − ( i ,T )∈ A ∑ xiT = 0 ( i , j )∈ A ∑ xij − ( k ,i )∈A ∑ xki = 0 ∀i ≠ O, T ∀(i, j ) ∈ A lij ≤ xij ≤ uij onde: A = conjunto dos arcos do grafo G = (V, A); O = nó de Origem; T = nó de Destino; xij = fluxo no arco (i, j); lij = limite mínimo para o fluxo no arco (i, j); uij = limite máximo para o fluxo no arco (i, j). A primeira restrição faz com que o fluxo total que sai do nó de Origem seja igual ao fluxo total que chega ao nó de Destino. O segundo conjunto de restrições deve existir para cada um dos demais nós (de transbordo), mantendo a conservação do fluxo. Observe que esse problema é inerentemente capacitado, onde pelo menos as capacidades máximas dos arcos devem existir (como no exemplo visto acima). Construindo o modelo para o Exemplo 1, usando a sintaxe do Lindo©, temos: 105 max xOA + xOB + xOC st T) xOA + xOB + xOC A) xAB + xAD - xOA = B) xBC + xBD + xBE C) xCE - xOC - xBC = D) xDT - xAD - xBD E) xED + xET - xBE end sub xOA 5 sub xOB 7 sub xOC 4 sub xAB 1 sub xAD 3 sub xBC 2 sub xBD 4 sub xBE 5 sub xCE 4 sub xDT 9 sub xED 1 sub xET 6 xDT 0 xOB 0 xED xCE - xET = 0 - xAB = 0 = 0 = 0 Veja que as restrições de capacidade dos arcos foram dadas separadamente, não sendo contadas como restrições normais. Esse recurso normalmente existe para os softwares de PL, e permite que o modelo seja resolvido de forma muito mais eficiente. No caso do Lindo, podemos usar os comandos SLB (Simple Lower Bound) para designar os valores de lij, e SUB (Simple Upper Bound) para designar os valores de uij. Como podemos ver, o Problema de Fluxo Máximo em uma Rede pode ser formulado como um Problema de Programação Linear e, portanto, o algoritmo Simplex pode ser utilizado para obtenção da solução ótima. Assim como no PFCM e no PT, existem também versões simplificadas do Simplex para lidar com este problema, que aproveitam as características específicas da matriz A e conceitos aproveitados da Teoria dos Grafos. Entretanto, existem algoritmos mais eficientes para a solução do PFM. Um deles, bastante conhecido, é chamado de Algoritmo do Caminho de Aumento (Augmenting Path Algorithm). O algoritmo do Caminho de Aumento é baseado em dois conceitos intuitivos: uma Rede Residual e um Caminho de Aumento (propriamente dito). Rede Residual Considere os dois grafos mostrados na figura a seguir, representando uma solução viável, mas não ótima, para o Exemplo 1 visto anteriormente. Os valores dos arcos da rede da esquerda representam as capacidades máximas e seus respectivos fluxos (capacidade, fluxo). Os valores dos arcos da rede da direita representam os resíduos, ou seja, a diferença entre a capacidade e o fluxo do arco. A 5,4 O 4,2 C 7,7 B 2,0 4,2 1,1 4,4 5,4 1,0 E 6,6 T C 2 E 0 D 9,7 O 2 A 1 0 B 2 0 0 1 1 T D 2 0 3,3 106 Caminho de Aumento Um Caminho de Aumento é um caminho a partir da origem para o destino na Rede Residual tal que todo arco sobre este caminho possui resíduo estritamente positivo. O valor mínimo destes resíduos é chamado de “Capacidade Residual do Caminho de Aumento”, uma vez que este representa a quantidade viável de fluxo que pode ser adicionado ao caminho todo. A 1 O 2 C 0 B 2 2 0 0 1 1 E 0 T D 2 0 O caminho: O→C→E→D→T é um Caminho de Aumento com Capacidade Residual 1 (menor resíduo neste caminho). Existem diversas “versões” do Algoritmo do Caminho de Aumento. A mais conhecida é o Algoritmo de Ford-Fulkerson (1962), modificado depois por Dinic (1970) e Edmonds & Karp (1972) para evitar casos patológicos que tornam o algoritmo original muito ineficiente. Outro algoritmo interessante, de desenvolvimento posterior, é o de Malhotra, Pramodh-Kamar e Maheshwari (MPM) (1978), baseado no conceito de potencial de fluxo. A idéia deste algoritmo é esgotar a capacidade dos nós da rede, ao invés da capacidade de suas arestas. Os melhores limites (de desempenho) da atualidade são, no entanto, os algoritmos de Ahuja & Orlin (1986) e Goldberg & Tarjan (1988). O fluxograma a seguir resume os passos do algoritmo MPM: Calcular o Potencial dos vértices vj Escolher o vértice de referência vk = mín{ vj} Fluir vj de O para T por saturação Eliminar os arcos saturados Eliminar vértices sem sucessores e seus arcos adjacentes Atualizar as capacidades na rede residual N Nó O eliminado? S FIM 107 Aplicaremos a seguir o algoritmo MPM à rede mostrada no Exemplo 1: A 5 1 7 4 3 O B 2 C 4 5 4 D 1 9 T 6 E Iteração 1: Calculando o potencial dos vértices, temos: j: vj: O 16 A 4 B 8 C 4 D 8 E 7 T 15 O vértice de referência será então o vértice A. Forçando um fluxo de 4 unidades através desse vértice, temos o primeiro fluxo parcial e a rede residual obtida subtraindo as capacidades originais desse fluxo: f1: 4 O A 1 B 1 C 1 E T 4 C 2 4 D 3 O 3 R1 : 1 7 A B 4 4 1 D 6 T 5 E Nesse momento, podemos eliminar o vértice A e seus arcos adjacentes, já que não existe mais caminho de O até T passando por A. Iteração 2: Recalculando o potencial dos vértices, temos: j: vj: O 12 B 7 C 4 D 5 E 6 T 11 O vértice de referência será agora o vértice C. Forçando um fluxo de 4 unidades através desse vértice, temos o segundo fluxo parcial e a rede residual obtida subtraindo as capacidades de R1 desse fluxo: 108 f2: A R2 : 1 7 A O 4 C B D O B 2 4 4 1 D 6 T 4 4 E T C E 1 Da mesma forma, podemos eliminar o vértice C e seus arcos adjacentes, já que não existe mais caminho de O até T passando por C. Iteração 3: Recalculando o potencial dos vértices, temos: j: vj: O 7 B 7 D 5 E 2 T 7 O vértice de referência será agora o vértice E. Forçando um fluxo de duas unidades através desse vértice, temos o terceiro fluxo parcial e a rede residual obtida subtraindo as capacidades de R2 desse fluxo: f3: 2 B 2 1 1 C E T C E D 1 2 A R3 : 1 O 5 A O B 4 2 D 5 T Dessa vez, o vértice que ficou isolado, juntamente com seus arcos adjacentes, foi o vértice E. Iteração 4: Observando o grafo R3 acima, fica claro que o único fluxo agora possível é o seguinte: f4: 4 B A R4 : 1 4 O 4 1 A O D B 2 2 D 1 T T C E C E Nesse ponto, o algoritmo termina, já que não há mais caminho de O até T. Somando os quatro fluxos parciais, temos então a seguinte solução ótima: 109 A 4 1 6 4 4 3 O B 3 C 4 D 1 8 T 6 E Veja que essa solução é diferente das outras duas soluções ótimas mostradas anteriormente para o Exemplo 1. 110 O Problema da Árvore Geradora Mínima (AGM) Considere uma rede não-direcionada, representada por um grafo G = (V,A) não-orientado, conexo, onde associado a cada aresta temos uma distância (custo, tempo, etc.) não negativa. Deseja-se encontrar um subgrafo de G que também seja conexo, e cuja soma total das arestas (distâncias, custos, tempos) seja o menor possível. O objetivo é manter uma ligação ou caminho entre cada par de vértices, gastando a menor quantidade de conexões possível. Esse problema, embora não seja modelado como um problema de fluxo em redes, encontra diversas aplicações que envolvem fluxos ou transferências de produtos, informações etc. Exemplos de Aplicações: • Projeto de redes de telecomunicação (redes de computadores, redes de fibra-ótica, redes de telefonia, redes de televisão a cabo, etc). • Projeto de rodovias, ferrovias, etc. • Projeto de redes de transmissão de energia. • Roteamento de veículos. Já vimos que uma árvore é um grafo conexo e sem ciclos. Uma árvore geradora (AG) de uma grafo G qualquer é um subgrafo de G, conexo e sem ciclos, e que contém todos os vértices de G (e obviamente só um subconjunto das arestas de G). Um grafo pode conter muitas árvores geradoras, como mostra a figura abaixo (repare que não são mostradas todas as AGs). G AG1 AG2 AG3 Este problema, portanto, consiste em encontrar pelo menos uma das árvores geradoras cuja soma das arestas seja mínima. Um modelo matemático para esse problema é dado a seguir: Min. s.a. ( i , j )∈ A ∑ ∑ cij xij xij = n − 1 xij ≤ S − 1 ∀S ⊂ G ( i , j )∈ A ( i , j )∈S ∑ xij ∈{0,1} ∀(i, j ) ∈ A A primeira restrição faz com que a AGM tenha exatamente n–1 arestas. O outro conjunto de restrições significa que, para cada subgrafo S do grafo, o número de arestas escolhidas deve ser igual ao número de nós em S menos 1. Isso implica na não existência de ciclos na AGM. Apesar desse modelo de PL ser teoricamente possível para obter a AGM, diferentemente dos problemas de fluxo vistos anteriormente, ele é impraticável, porque o número de restrições cresce exponencialmente com o tamanho do grafo. No entanto, existem também algoritmos muito eficientes 111 que resolvem o problema usando somente a Teoria de Grafos. Os mais comuns são o algoritmo de Kruskal (1956), o de Prim (1957), e o de Borüvka. Veremos dois deles a seguir: Algoritmo de Kruskal: Seja G = (V, A) um grafo conexo de n vértices e arestas valoradas. Ordenar as arestas pelos valores de peso. T = ∅ (lista de arestas contidas na AGM) Enquanto existir aresta na lista de arestas ordenadas, faça: a = próxima aresta de menor peso de A. Se a adição de a em T não formar um ciclo, então acrescente a em T. Exemplo 1: Determinar uma AGM do grafo abaixo usando o algoritmo de Kruskal. A 5 1 7 4 3 O B 2 C 4 5 4 D 1 3 T 6 E Solução: A 5 O 4 C 7 B 2 4 1 4 5 1 E 6 T 4 C 2 4 D 3 O 3 A 5 7 B 1 4 5 1 E 6 T D 3 3 A 5 O 4 C 7 B 2 4 1 3 4 5 1 E 6 T A 5 D O 4 C 7 B 2 4 1 3 4 5 1 E 6 T 3 D 3 112 A 5 O 4 C 7 B 2 4 1 3 4 5 1 E 6 T A 5 D O 4 C 7 B 2 4 1 3 4 5 1 E 6 T 3 D 3 A 1 O 4 C 2 B 3 D 1 E 3 T Solução ótima. Comprimento total = 14. O algoritmo de Prim usa uma abordagem diferente. Ao invés de adições sucessivas de arestas até que pequenas árvores formadas isoladamente se juntem numa única árvore geradora, o algoritmo de Prim inicia a partir de um vértice qualquer do grafo, e vai sucessivamente unindo os outros vértices através das arestas de menor peso. Assim, temos uma única árvore que vai crescendo até conter todos os vértices de G. Algoritmo de Prim: Seja G = (V, A) um grafo conexo de n vértices e arestas valoradas. B = Um vértice inicial qualquer de G. T = ∅ (lista de arestas contidas na AGM) Enquanto B não contém todos os vértices Escolher (u,v) = aresta de menor peso tal que u ∈ (V – B) e v ∈ B T = T ∪ {(u,v)} B = B ∪ {u} Em outras palavras, temos: • Selecionar qualquer nó e conectá-lo (isto é, adicionar um arco) para o nó mais próximo. • Identificar o nó desconectado mais próximo para um nó conectado e então conectar estes dois nós. Repetir este passo até que todos os nós tenham sido conectados. Observação: no caso de empate de dois ou mais nós não conectados mais próximos de um nó conectado, escolher arbitrariamente um dos nós não conectados. Ainda assim, a solução ótima é garantida, porém este fato pode ser um sinal da existência de múltiplas soluções ótimas. Todas as soluções ótimas podem ser obtidas executando novamente o algoritmo com decisões diferentes nos casos de empate. Isso é válido também para o algoritmo de Kruskal. Exemplo 2: O grafo abaixo representa diversos computadores posicionados em um laboratório, juntamente com as ligações (e suas respectivas distâncias em metros) possíveis de serem feitas entre eles. Deseja-se ligar todos os computadores em rede, usando a menor quantidade em cabos coaxiais possível, de forma que os usuários possam compartilhar dados e recursos, além de brincar com jogos interativos. 113 2 5 1 7 4 3 1 3 2 4 4 5 4 6 1 3 7 6 5 Solução: usando o algoritmo de Prim, e iniciando do vértice 1, temos: 2 5 1 4 4 7 3 2 4 1 4 5 1 5 6 7 4 4 2 4 6 3 1 3 2 5 7 3 1 4 5 1 5 6 7 6 3 3 2 5 1 4 4 7 3 2 4 1 3 4 5 1 5 6 7 2 5 6 1 4 4 7 3 2 4 1 3 4 5 1 5 6 7 3 6 3 2 5 1 4 4 7 3 2 4 1 3 4 5 1 5 6 7 2 5 6 1 4 4 7 3 2 4 1 3 4 5 1 5 6 7 3 6 3 2 1 1 4 4 2 3 3 6 1 5 3 7 Solução ótima. Comprimento total = 14. 114 O Problema de Steiner em Grafos não Direcionados O problema de Steiner em grafos não direcionados é o problema de conectar, a custo mínimo, um conjunto específico de nós do grafo. Considere, por exemplo, uma região de plantio de lavouras onde existem diversos pontos de irrigação posicionados segundo determinados critérios técnicos e econômicos (inclinação do terreno, tipo de lavoura, características do terreno etc.). O grafo abaixo representa essa rede: 3 10 13 1 4 8 11 14 2 7 12 15 6 9 Suponha agora que os pontos de irrigação, representados pelos vértices 8, 12, 13 e 14, precisam ser interligados e “abertos”. Essa interligação poderia ser feita de várias formas diferentes. A figura abaixo mostra duas formas de se fazer isso: 3 1 4 2 7 12 15 6 9 6 9 8 11 14 2 7 12 15 10 13 1 4 10 13 11 14 3 8 Veja que, na primeira solução, o subgrafo formado foi uma árvore contendo somente os pontos que precisavam ser interligados. Já na segunda solução, a árvore formada contém, além dos pontos obrigatórios, um outro ponto (vértice 11) que, nesse caso, serve apenas de “ponto de interligação” entre os demais. Esse ponto, que pode ser usado na interligação, mas não precisa obrigatoriamente fazer parte da árvore-solução, é chamado de Ponto de Steiner. A solução da esquerda, portanto, não contém pontos de Steiner, enquanto que a da direita contém um ponto de Steiner. Embora não tenham sido dados os pesos (custos, distâncias) das arestas, o objetivo do problema acima seria interligar os quatro pontos acima usando a menor soma total das arestas (para, por exemplo, minimizar a perda de pressão por atrito). É fácil demonstrar que a solução será sempre uma árvore contendo um subconjunto de vértices e arestas do grafo original. Por isso, esse problema é também chamado de Problema da Árvore de Steiner. 115 Dentre as várias aplicações para esse problema, destacamos as seguintes: • • • • • • • Projeto de circuitos eletrônicos e VLSI. Redes de comunicação. Redes de tráfego. Tubulações de gás e óleo. Distribuição de água para irrigação e redes de drenagem. Projetos de instalações elétricas e mecânicas. Projetos de edificações Iremos agora caracterizar o problema formalmente, no contexto da Teoria de Grafos: Seja o grafo G = (V,A), e ∆ e Χ conjuntos resultantes de uma partição do conjunto V, ou seja, ∆ ⊆ V e Χ ⊆ V, sendo que ∆ ∪ Χ = V e ∆ ∩ Χ = ∅, Χ= r e ∆= s. Determinar um subconjunto de arestas B ⊆ A que ligue todos os vértices xi ∈ Χ em um grafo conexo, onde i = 1, 2, ..., r, de modo a minimizar ∑ c j , onde cj é o custo ou o comprimento das arestas de B. Os vértices pertencentes ao j∈B conjunto ∆ (pontos de Steiner) podem ser usados ou não pela estrutura de ligação. Observe que esse problema possui três situações distintas: 1) Χ= 2, ou seja, deseja-se interligar dois pontos do grafo a um custo mínimo. Nesse caso, o problema torna-se um PCMC e pode ser facilmente resolvido (e.g. usando o algoritmo de Dijkstra visto anteriormente). 2) Χ = N ou ∆ = ∅, ou seja, deseja-se interligar todos pontos do grafo a um custo mínimo. Nesse caso, o problema se resume em achar uma AGM do grafo, que também pode ser facilmente resolvido (e.g. usando os algoritmos de Kruskal ou Prim vistos anteriormente). 3) Χ> 2 e ∆ ≠ ∅. Nesse caso, o problema cai numa classe de problemas chamada de NP-Difícil, o que na prática significa que não existe algoritmo que possa resolver qualquer instância do problema de maneira eficiente. Nesse caso, especialmente para problemas maiores, é recomendado o uso de heurísticas, ou seja, algoritmos de solução aproximada (que não garantem a obtenção da solução ótima), porém mais eficientes em termos de tempo de execução. Entre as soluções adotadas, podemos destacar as seguintes: Algoritmos de Solução Exata • • • • Enumeração baseada em árvores geradoras; Enumeração topológica (para o Steiner euclidiano); Programação Dinãmica (ou o desenvolvimento de sub-árvores de Steiner); Outros. Heurísticas • Baseadas no PCMC; • Baseadas na AGM; • Outras. 116 Redes PERT / CPM As técnicas denominadas PERT (Program Evaluation and Review Technique) e CPM (Critical Path Method) foram desenvolvidas independentemente para o Planejamento e Controle de Projetos em torno de 1950, porém a grande semelhança entre estas fez com que o termo PERT/CPM seja utilizado corriqueiramente como uma única técnica. Exemplos de Projetos que podem utilizar PERT/CPM: • Construção Civil • Projetos de Engenharia • Pesquisa e desenvolvimento de um produto • Produção de filmes • Construção de navios, aviões etc. • Instalação de um sistema de informações • Condução de campanhas publicitárias, entre outras. PERT e CPM utilizam principalmente os conceitos de Redes (grafos) para planejar e visualizar a coordenação das atividades ou tarefas do projeto. Um exemplo clássico de aplicação de PERT/CPM é o planejamento e gerenciamento da construção civil. Veremos a seguir dois exemplos dessa aplicação: a primeira usando uma Rede PERT tradicional e a segunda usando uma Rede PERT/CPM orientada a eventos. Redes PERT Exemplo 1 (Hiller/Lieberman, pg 468): Suponha que uma empreiteira ganhou uma concorrência de $5,4 milhões para construir uma planta industrial. O contrato inclui: • Uma penalidade de $300.000,00 se a empreiteira não completar a construção em 47 semanas. • Um bônus de $150.000,00 se a empreiteira completar a construção em 40 semanas. De acordo com a experiência da empreiteira, a seguinte lista foi elaborada para este projeto: Tabela 1 - Tarefas, Tarefas Precedentes e Duração Estimada Tarefas Duração Estimada Tarefa Descrição Precedentes (semanas) A Escavação e Terraplanagem 2 B Fundação A 4 C Paredes B 10 D Telhado C 6 E Encanamento Exterior C 4 F Encanamento Interior E 5 G Muros D 7 H Pintura Exterior E, G 9 I Instalação Elétrica C 7 J Divisórias F, I 8 K Piso J 4 L Pintura Interior J 5 M Acabamento Exterior H 2 N Acabamento Interior K, L 6 117 A duração para a execução da obra é 79 semanas se cada tarefa for realizada uma por vez. No entanto, existem tarefas que podem ser realizadas simultaneamente com outras tarefas, podendo com isso, reduzir a duração da execução da obra. 2. Construção da Rede A rede pode ser construída utilizando os arcos para representar as tarefas e os nos para separar as tarefas de suas tarefas precedentes, porém utilizar os nos para representar as tarefas e os arcos para representar as relações de precedência parece ser mais intuitivo. A figura abaixo ilustra a rede para o exemplo dado: Início 0 A 2 B 4 C 10 D 6 E 4 I 7 G 7 F 5 H 9 J 8 K M 2 4 L 5 N 6 Fim 0 Figura 1 – Rede PERT para o exemplo dado. A partir da lista de tarefas e das relações de precedência, a rede pode ser facilmente construída. Para isto, dada uma tarefa (nó), basta procurar na lista quais tarefas são suas tarefas precedentes. Por exemplo, na rede da Figura 1, a tarefa J possui as tarefas F e I como precedentes, as quais devem ser conectadas através de arcos orientados, indicando assim, a precedência. Através da análise da rede, varias informações podem ser obtidas, entre elas, as respostas para duas perguntas cruciais para 0 planejamento do projeto: 1. Qual o tempo total requerido para completar o projeto se nenhum atraso ocorrer? 2. Quais as tarefas que não podem sofrer atrasos para que o projeto seja executado sem atraso (“Atividades Gargalos”)? 2.1 Caminho Crítico Um caminho através de uma rede é uma rota seguindo os arcos a partir do no INICIO até o FIM. O comprimento de um caminho é a soma das durações das tarefas sobre o caminho. Na rede da Figura 118 1 existem 6 caminhos, que são dados na tabela abaixo, juntamente com seus respectivos comprimentos: Tabela 2 - Caminhos e seus respectivos Comprimentos Caminho Comprimento (semanas) Inicio-A-B-C-D-G-H-M-Fim 2+4+10+6+7+9+2 = 40 Inicio-A-B-C-E-H-M-Fim 2+4+10+4+9+2 = 31 Inicio-A-B-C-E-F-J-K-N-Fim 2+4+10+4+5+8+4+6 = 43 Inicio-A-B-C-E-F-J-L-N-Fim 2+4+10+4+5+8+5+6 = 44 Inicio-A-B-C-l-J-K-N-Fim 2+4+10+7+8+4+6 = 41 Inicio-A-B-C-1-J-L-N-Fim 2+4+10+7+8+5+6 = 42 O caminho com maior comprimento é o Caminho Critico, uma vez que todos os demais caminhos deverão alcançar o FIM antes do Caminho Critico. Isto responde a questão 1 dada acima, ou seja, o tempo total requerido é 44 semanas para completar o projeto. As tarefas sobre este caminho são as Atividades Criticas (Atividades Gargalos), ou seja, qualquer atraso em uma dessas tarefas irá atrasar a duração de todo o projeto. Já as demais tarefas, se sofrerem algum atraso, poderão ou não atrasar a duração de todo o projeto. A Figura 2 mostra o Caminho Critico: Início 0 A 2 B 4 C 10 D 6 E 4 I 7 G 7 F 5 H 9 J 8 K M 2 4 L 5 N 6 Fim 0 Figura 2 – Caminho Crítico. 2.2 Programação de Tarefas (Scheduling) A Programação das Tarefas na técnica PERT consiste em determinar em que tempo (por exemplo, em que dia, em qual semana) uma tarefa deve começar e terminar. A principio, o tempo inicial de uma tarefa deveria ser igual ao tempo final da tarefa precedente. No entanto, tarefas que possuem duas ou mais tarefas precedentes necessitam que todas as tarefas precedentes estejam completadas para só então dar início à tarefa em questão. Já para Atividades Não Criticas, o tempo inicial não 119 precisa ser necessariamente igual ao tempo final da sua tarefa precedente, uma vez que esta tarefa possui folga (não pertence ao Caminho Critico da Rede). A fim de formalizar este raciocínio, a técnica PERT utiliza quatro variáveis, a saber: TIC = Tempo Inicial Mais Cedo TFC = Tempo Final Mais Cedo TIT = Tempo Inicial Mais Tarde TFT = Tempo Final Mais Tarde De posse dessas variáveis, as seguintes regras podem ser definidas: Regra do Tempo Inicial Mais Cedo: O Tempo Inicial Mais Cedo TICi de uma tarefa i é igual ao maior Tempo Final Mais Cedo TFCj das tarefas precedentes j. TICi = max (TFCj), ∀ j ∈ πi (1) onde πi é o conjunto de todas as tarefas precedentes à tarefa i. Regra do Tempo Final Mais Cedo: TFCi = TICi + Di, onde Di é a duração da tarefa i. Regra do Tempo Inicial Mais Tarde: TITi = TFTi – Di, onde TFTi é definido abaixo. Regra do Tempo Final Mais Tarde: O Tempo Final Mais Tarde TFTi de uma tarefa i é igual ao menor Tempo Inicial Mais Tarde TITk das tarefas sucessoras k. TFTi = min (TITk), ∀ k ∈ ψi (4) (3) (2) onde ψi é o conjunto de todas as tarefas sucessoras à tarefa i. Exemplo: Cálculo de TIC, TFC, TIT e TFT para a tarefa J (divisórias) da rede do exemplo anterior: TICJ = max( TFCF, TFCI ) = max( 25, 23 ) = 25 TFCJ = TICJ + DJ = 25 + 8 = 33 TFTJ = min( TITK, TITL ) = min( 34, 33 ) = 33 TITJ = TFTJ – DJ = 33 – 8 = 25 Podemos ver que o cálculo do Tempo Inicial Mais Cedo (TIC) é função dos Tempos Finais Mais Cedos (TFCs) precedentes. Portanto, a sua obtenção é realizada calculando os TICs e TFCs no sen120 tido do nó Início até o nó Fim. Já o cálculo do Tempo Final Mais Tarde (TFT) é função dos Tempos Iniciais Mais Tardes (TITs) sucessores, e devem ser obtidos calculando os TITs e TFTs no sentido do nó Fim para o nó Início. Além disso, podemos observar também que o TICJ é igual ao TITJ, o que mostra que não há folga para iniciar essa tarefa. O mesmo acontece com o par TFCJ e TFTJ, o que é coerente, já que essa tarefa faz parte do Caminho Crítico da rede. Com uma análise mais detalhada, poderíamos mostrar que: Si = TFTi – TFCi = TITi – TICi onde Si corresponde à folga da tarefa i, ou seja, o atraso que essa tarefa pode sofrer sem comprometer o tempo total do projeto – ou o tempo do(s) caminho(s) crítico(s). Na tabela a seguir mostramos os cálculos já prontos para todos os nós da rede. Repare que o caminho crítico, já mostrado na Figura 2, corresponde ao caminho formado pelas tarefas (nós) com folga Si = 0. Dependendo da topologia da rede e dos tempos Di, podemos ter mais de um caminho crítico. Tabela 3 – Valores calculados para as variáveis de todos os nós da rede do Exemplo 1. Tarefa (i) Di TICi TITi TFCi TFTi Si Início 0 0 0 0 0 0 A 2 0 0 2 2 0 B 4 2 2 6 6 0 C 10 6 6 16 16 0 D 6 16 20 22 26 4 E 4 16 16 20 20 0 F 5 20 20 25 25 0 G 7 22 26 29 33 4 H 9 29 33 38 42 4 I 7 16 18 23 25 2 J 8 25 25 33 33 0 K 4 33 34 37 38 1 L 5 33 33 38 38 0 M 2 38 42 40 44 4 N 6 38 38 44 44 0 Fim 0 44 44 44 44 0 Redes PERT/CPM Vimos que, nas redes PERT tradicionais, as tarefas são representados por nós no grafo, e com isso temos uma rede orientada por tarefa. Na rede PERT/CPM, as tarefas são representadas por arcos no grafo, sendo que os nós nesse caso representam os inícios e os términos de uma ou mais tarefa. Dizemos então que a rede PERT/CPM é orientada por evento, já que os nós representam um determinado evento do processo, que pode ser o início ou o término de uma ou mais tarefas. Podemos tratar a rede PERT/CPM como sendo a versão dual da rede PERT (mas não iremos entrar nos aspectos de dualidade aqui, apenas mostrar como obtemos o(s) caminho(s) crítico(s), como fizemos para rede PERT). Vamos considerar o mesmo exemplo usado anteriormente. A tabela correspondente aos tempos e precedências das tarefas é replicada abaixo: 121 Tabela 1 - Tarefas, Tarefas Precedentes e Duração Estimada Tarefas Duração Estimada Tarefa Descrição Precedentes (semanas) A Escavação e Terraplanagem 2 B Fundação A 4 C Paredes B 10 D Telhado C 6 E Encanamento Exterior C 4 F Encanamento Interior E 5 G Muros D 7 H Pintura Exterior E, G 9 I Instalação Elétrica C 7 J Divisórias F, I 8 K Piso J 4 L Pintura Interior J 5 M Acabamento Exterior H 2 N Acabamento Interior K, L 6 Construindo a rede, temos o grafo mostrado na Figura 3. Desta vez, são os arcos que recebem os valores dos tempos de execução de cada tarefa, e não os nós. Note também que foram inseridos arcos adicionais, representados por linhas pontilhadas. Esses arcos são chamados de arcos-fantasma. Todos possuem valores de tempo iguais a zero, e servem para separar os eventos de início e término de determinadas tarefas. Dessa forma, não teremos nenhum nó representando o início ou o término de mais de uma tarefa distinta. G 7 7 D 6 4 A 2 B 4 C 10 E 3 5 4 8 10 12 H 9 15 M 2 19 Fim Início 1 2 23 11 F 5 9 14 J 8 16 18 L 5 21 17 13 K 4 20 6 7 I N 6 22 Figura 3 – Rede PERT/CPM para o Exemplo 1. Já que, para a rede PERT/CPM, os eventos de início e término representados pelos nós não possuem tempo ou duração envolvida, podemos obter o caminho crítico usando somente duas variáveis para cada nó da rede, a saber: TC = Tempo Mais Cedo TT = Tempo Mais Tarde As regras que definem essas variáveis podem ser dadas da seguinte forma: 122 Regra do Tempo Mais Cedo: TCInício = 0 TCj = max (TCi + Dij), ∀ i ∈ πj (5) (6) onde πj é o conjunto de todos os eventos precedentes ao evento i, e Dij é igual ao tempo da tarefa representada pelo arco (i, j). Para os arcos-fantasma, Dij = 0. Regra do Tempo Mais Tarde: TTFim = TCFim TTi = min (TTk – Dik), ∀ k ∈ ψi (7) (8) onde ψi é o conjunto de todos os eventos precedentes ao evento i. Podemos expressar essas mesmas regras de outra forma um pouco mais simples: Regra do Tempo Mais Cedo: Para calcular o Tempo Mais Cedo de cada nó, basta percorrer todos os caminhos da origem (Início) ao destino (Fim), somando os tempos e guardando sempre o maior valor. Regra do Tempo Mais Tarde: Para calcular o Tempo Mais Tarde de cada nó, basta percorrer todos os caminhos do destino (Fim) à origem (Início), subtraindo os tempos e guardando sempre o menor valor. Terminado o cálculo dessas duas variáveis, podemos obter a folga em cada nó subtraindo os dois tempos obtidos: Si = TTi – TCi Para a rede representada pela Figura 3, temos então o seguinte resultado: 123 Tabela 4 – Valores calculados para as variáveis de todos os nós da rede do Exemplo 1. Evento (i) TCi TTi Si Início 0 0 0 1 2 2 0 2 6 6 0 3 16 16 0 4 16 20 4 5 16 16 0 6 16 18 2 7 22 26 4 8 20 20 0 9 23 25 2 10 29 33 4 11 20 20 0 12 29 33 4 13 25 25 0 14 25 25 0 15 38 42 4 16 33 33 0 17 33 34 1 18 33 33 0 19 40 44 4 20 37 38 1 21 38 38 0 22 38 38 0 23 44 44 0 Fim 44 44 0 Podemos ver que o resultado obtido com a rede PERT/CPM orientada por eventos é o mesmo que o obtido pela rede PERT orientada por tarefas, com apenas um caminho crítico passando pelas atividades A, B, C, E, F, J, L e N, e tempo total do projeto igual a 44 semanas. 124 Bibliografia AHUJA, R.K., MAGNANTI, T.L., ORLIN, J.B., Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. BAZARAA, M.S., JARVIS, J.J., SHERALI, H.D., Linear Programming and Network Flows, 2nd Edition. John Wiley & Sons, 1990. BREGALDA, P.F., OLIVEIRA, A.F., BORNSTEIN, C.T., Introdução à Programação Linear. Editora Campus, 1988. CAIXETA-FILHO, J.V., Pesquisa Operacional: Técnicas de Otimização Aplicadas a Sistemas Agroindustriais, 2ª Edição. Editora Atlas, 2004. HILLIER, F.S., LIEBERMAN, G.J., Introdução à Pesquisa Operacional, Editora Campus, Rio de Janeiro. Editora USP, 1988. LAW, A.M., KELTON, W.D., Simulation Modeling & Analysis, McGraw-Hill, 1991. LUNA, H.P.L., GOLDBARG, C.M., Otimização Combinatória e Programação Linear. Editora Campus, 2000. MEDEIROS da SILVA, E., et. al., Pesquisa Operacional: Para os Cursos de Economia, Administração e Ciências Contábeis, 3ª Edição. Editora Atlas, 1998. PRADO, D., Teoria das Filas e da Simulação. EDG, 1999. RARDIN, R.L. Optimization in Operations Research, Prentice Hall, 1994. ROSS, S.M., Simulation – Second Edition. Academic Press, 1997. RUBINSTEIN, R.Y., Monte Carlo Optimization, Simulation and Sensitivity of Queuing Networks. Krieger Publishing Company, 1992. SAIGAL, R., Linear Programming: A Modern Integrated Analysis. Kluwer Academic Pub., 1995. SHIMIZU, T., Pesquisa Operacional em Engenharia, Economia e Administração: Modelos Básicos e Métodos Computacionais. Editora Guanabara Dois, 1984. WAGNER, H.M., Pesquisa Operacional, Prentice Hall, 1985. WINSTON, W.L. Operations Research: Applications and Algorithms, 3rd Edition. Wadsworth, 1997. 125