Pesquisa operacional, Manuais, Projetos, Pesquisas de Engenharia Elétrica

Baixe Pesquisa operacional e outras Manuais, Projetos, Pesquisas em PDF para Engenharia Elétrica, somente na Docsity! Universidade Federal de Viçosa Departamento de Informática Prof. Mauro Nacif Rocha Prof. Luiz Aurélio Raggi Prof. Heleno do Nascimento Santos Fevereiro de 2005 INF-280 Pesquisa Operacional I Conteúdo: Programação Linear Programação em Redes ii 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 3 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 fidedig- na da realidade. Os dados coletados durante a observação do problema podem ser usados para a va- lidaçã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 esco- lher 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 dinamicamen- te, fazendo-se mudanças quando necessárias. 4. Áreas de aplicação Segundo trabalhos apresentados em reuniões da Sociedade Brasileira de Pesquisa Operacio- nal (SOBRAPO), citam-se abaixo algumas áreas onde a P.O. foi aplicada com algum sucesso e on- de 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 4 5. Técnicas aplicadas Os trabalhos de PO desenvolvidos e submetidos para apresentação em congressos e para pu- blicaçã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 for- mação em Engenharia, Matemática e/ou Estatística, entusiasmados com as novas técnicas relacio- nadas a P.O. que aqui chegavam pela difusão natural do conhecimento humano, começaram a for- mar 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. 5 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 faci- lidades (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 po- de 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. 8 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 de- vem ser repartidos entre deman- das competitivas ⇔ Decisões são interligadas na tomada de decisão ⇔ Demandas competem entre si na procura dos recursos escassos 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. 9 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 COMPARAÇÃO COM A REALIDADE IMPLEMENTAÇÃO DA SOLUÇÃO 10 4. Modelagem de problemas MODELOS SÃO REPRESENTAÇÕES DA REALIDADE GRANDE NÚME- RO DE VARIÁ- VEIS SELEÇÃO DAS VA- RIÁVEIS PRINCIPAIS SIMPLIFICAÇÃO DA REALIDADE SISTEMA INTER- RELACIONAMENTO 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 n VARIÁVEIS DE DECISÃO (x1, x2, … , xn) REPRESENTA A MEDIDA DE EFICIÊNCIA DO SISTEMA FUNÇÃO OBJETIVO Z = f(x1, x2, … , xn) SÃO RESTRIÇÕES AOS VALORES DAS VARIÁVEIS DE DECISÃO REPRESENTADAS POR EQUA- ÇÕES OU INEQUAÇÕES MA- TEMÁTICAS É A REALIDADE É UMA APROXIMAÇÃO VALIDADE ASSOCIADA AO GRAU DE COR- RELAÇÃO 13 Exemplos de Modelos para Alguns Problemas Clássicos de Pro- gramação Linear Escolha da Mistura para Rações Grão 1 Grão 2 Grão 3 Necessidades mínimas Nutriente A 2 3 7 1250 Nutriente B 1 1 0 250 Nutriente C 5 3 0 900 Nutriente D 0,6 0,25 1 232,5 $/kg 41 35 96 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 + 3x2 + 7x3 ≥ 1250,0 (Nutriente A) x1 + x2 ≥ 250,0 (Nutriente B) 5x1 + 3x2 ≥ 900,0 (Nutriente C) 0,6x1 + 0,25x2 + x3 ≥ 232,5 (Nutriente D) Queremos obter uma ração que tenha um custo mínimo. Portanto, o modelo completo fica assim: Minimizar 41x1 + 35x2 + 96x3 (Função Objetivo ou F.O.) Sujeito a: (Restrições) 2x1 + 3x2 + 7x3 ≥ 1250,0 (Nutriente A) x1 + x2 ≥ 250,0 (Nutriente B) 5x1 + 3x2 ≥ 900,0 (Nutriente C) 0,6x1 + 0,25x2 + x3 ≥ 232,5 (Nutriente D) e: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 14 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 5 2 2 0 Produto 2 1833 3 0 1 Produto 1 Lucro unitário (em R$) 122 41 Capacidade disponível Seção Nº Modelo completo: Maximizar Z = 3x1 + 5x2, sujeito a x 1 ≤ 4 2x 2 ≤ 12 3x1 + 2x 2 ≤ 18 x1 ≥ 0, x2 ≥ 0 15 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 po- de 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. ∑ = N j jj xR 1 s.a.: 0 1 ≥ ≤∑ = j N j jj x Wxw 18 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 transpor- tar. Cada pessoa poderá levar até 10 quilos de bagagem pessoal, Toda a região foi isolada e só cir- culam 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 Veículo de ¼ ton. do Exército Helicóptero Ônibus Microônibus Veículo de Passeio Quantidade de Unidades Disponíveis 10 20 15 10 5 60 Capacidade de Transporte 20 pessoas 5 pessoas 10 pessoas 30 pessoas 15 pessoas 5 pessoas Capacidade para bagagem 1 ton. 20 kg 50 kg 1 ton. 500 kg 100 kg Custo por Viagem 10 u.m. 4 u.m. 75 u.m. 5 u.m. 3 u.m. 2 u.m. Tempo de Viagem 1 h 45 min. 10 min. 45 min. 30 min. 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ó po- derã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. 19 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) maximizar 12x1 + 15x2 sujeito a: (2) 4x1 + 3x2 ≤ 12 (3) 2x1 + 5x2 ≤ 10 (4) x1 ≥ 0 e x2 ≥ 0 Solução Ótima: ponto b, onde x1 = 15/7, x2 = 8/7 e 12x1 + 15x2 = 300/7 20 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, con- siderando o limite dos recursos que tem? Modele o problema como um problema de programação linear (PPL). x1
Horas-aula de natação; x2
Horas-aula de pólo aquático máx. x1 + x2 (1) s.a.: x1 + x2 ≤ 18 (2) 8x1 + 5x2 ≤ 100 (3) 1600x1 + 3300x2 ≤ 40000 (4) (1) (2) (3) (4) 23 Casos Encontrados na Resolução Gráfica Continuaremos usando aqui modelos de duas variáveis, mantendo um espaço bidimensional (pla- no), 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 (1) 16x1 + 33x2 ≤ 400 (2) 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F.O. (1) (2) x1 x2 24 Exemplo 2: min 2x1 + 1,2x2 s.a. 2x1 + 50x2 ≥ 11 (1) 50x1 + 10x2 ≥ 70 (2) 2. Infinitas soluções ótimas. máx. 16x1 + 10x2 s.a.: 8x1 + 5x2 ≤ 100 (1) 16x1 + 33x2 ≤ 400 (2) 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 x1 x2 (1) (2) (1) (2) 25 3. Solução ótima ilimitada. Exemplo 1: max 2x1 + 1,2x2 s.a. 2x1 + 50x2 ≥ 11 (1) 50x1 + 10x2 ≥ 70 (2) Exemplo 2: max x1 – x2 s.a. 2x1 – x2 ≥ 0 (1) x2 ≤ 4 (2) x1 x2 (1) (2) (1) (2) 28 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 = ∑ = n j jj xc 1 Sujeito a: ∑ = n j jij xa 1 = bi, i = 1, … , m; xj ≥ 0, j = 1, … , n; bi ≥ 0, i = 1, … , m. É 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 tor- nam-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: [ ] ∑∑∑ −−=−−= jjjjjj xcMáximoxcMáximoxcMínimo )( Então, se o problema é minimizar e deseja-se trabalhar como maximizar, multiplica-se os coeficien- tes 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 "≤": k n j jkj bxa ≤∑ =1 Utiliza-se uma variável xk, chamada variável de folga, em que xk = bk – ∑j akj xj, de forma que kk n j jkj bxxa =+∑ =1 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. 29 3) Variáveis de Excesso Considere a inequação linear do tipo "≥": s n j jsj bxa ≥∑ =1 Utiliza-se uma variável xs, chamada variável de excesso, em que xs = ∑j asj xj, – bs, de forma que ss n j jsj bxxa =−∑ =1 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 pro- blema original, então, para construir a forma padrão do modelo de PL, substitui-se essa variável, fa- zendo-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. 2x1 + 1,2x2 s.a. 2x1 + 50x2 ≥ 11 50x1 + 10x2 ≥ 70 Forma padrão: max. – 2x1 – 1,2x2 s.a. 2x1 + 50x2 – x3 = 11 50x1 + 10x2 – x4 = 70 30 Definições básicas Considere o problema de programação linear na forma matricial e padrão: Maximizar Z = cx (1) Sujeito a: Ax = b (2) x ≥ 0 (3) 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 colu- nas 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: bBxB 1−= 0Nx = 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 sim- plesmente 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 = x1 + 3 x2 (1) sujeito a: x1 + x2 ≤ 6 (2) x2 ≤ 3 (3) xj ≥ 0 A representação gráfica é a seguinte: 33       = 3 31x ,       = 0 62x ,       = 3 03x ,       = 0 04x 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). 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 exis- tência de uma solução degenerada afeta o comportamento do algoritmo Simplex, e daí a importân- cia 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 + x2 ≤ 6 x2 ≤ 3 x1 + 2 x2 ≤ 9 Sua representação gráfica é a seguinte: x1 x2 x3 x4 34 Usando variáveis de folga o sistema é transformado em igualdades, na forma: x1 + x2 + x3 = 6 x2 + x4 = 3 x1 + 2 x2 + x5 = 9 A matriz de coeficientes do sistema expandido é: [ ]           == 1 0 0 0 1 0 0 0 1 2 1 1 1 0 1 4321 aaaaA Considere a matriz básica formada pelas três primeiras colunas de A, ou seja, B = [a1 a2 a3]. A so- lução correspondente é dada por: Variáveis básicas:           =                     − =                     ==           = − − 0 3 3 9 3 6 111 010 120 9 3 6 021 010 111 1 1 3 2 1 bB x x x xB Variáveis não básicas:       =      = 0 0 5 4 x x xN Tendo em vista que a variável básica x3 = 0, então a solução é degenerada. Veremos as implicações disso mais tarde. 35 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 line- armente 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. O sistema pode então ser reescrito assim: BxB + RxR = b 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 bBxB 1−= 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. xB B R m x: n – m m A: 38 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 corres- pondente é 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. Vere- mos como isso pode ser feito mais adiante. Caso de problema em que não é necessário usar a Fase 1: Maximizar 5 x1 + 2 x2 sujeito a: 1 x1 ≤ 3 1 x2 ≤ 4 1 x1 + 2 x2 ≤ 9 Solução gráfica Colocando o problema na forma padrão tem-se: Maximizar 5 x1 + 2 x2 sujeito a: 1 x1 + x3 = 3 1 x2 + x4 = 4 1 x2 + 2 x2 + x5 = 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. 39 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 pas- so 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 mo- mento 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 al- guma 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: Y Modelo de PL original Y Forma Padrão - Quadro Simplex | Obter Solução Básica Viável (SBV) inicial s Y Escolher Pivoteamento em torno de As er=max c,jeN N Escolher F* |min (b,/a;.), a;-> 0 Modelo inconsistente Solução ótima Com?) Solução ilimitada 40  43 V.B. xE xM xA xP x1 x2 x3 b L0 – Z 100 80 120 20 0 0 0 0 L1 x1 1 1 1 4 1 0 0 250 L2 x2 0 1 1 2 0 1 0 600 L3 x3 3 2 4 0 0 0 1 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 3L′ ← L3 ÷ 4: V.B. xE xM xA xP x1 x2 x3 b L0 – Z 100 80 120 20 0 0 0 0 L1 x1 1 1 1 4 1 0 0 250 L2 x2 0 1 1 2 0 1 0 600 3L′ xA ¾ ½ 1 0 0 0 ¼ 125 Depois, fazemos: 0L′ ← -120 × 3L′ + L0 1L′ ← -1 × 3L′ + L1 2L′ ← -1 × 3L′ + L2 e obtemos o segundo quadro simplex: V.B. xE xM xA xP x1 x2 x3 b 0L′ – Z 10 20 0 20 0 0 -30 -15.000 1L′ x1 ¼ ½ 0 4 1 0 -¼ 125 2L′ x2 -¾ ½ 0 2 0 1 -¼ 475 3L′ xA ¾ ½ 1 0 0 0 ¼ 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 ar- mários. Observe que ainda existem variáveis que podem contribuir para o crescimento da F.O. Co- mo 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). 44 Executamos então o 2º pivoteamento: 1L ′′ ← 1L′ ÷ ½ 0L ′′ ← -20 × 1L ′′ + 0L′ 2L ′′ ← -½ × 1L ′′ + 2L′ 3L ′′ ← -½ × 1L ′′ + 3L′ e obtemos o terceiro quadro simplex: V.B. xE xM xA xP x1 x2 x3 b 0L ′′ – Z 0 0 0 -140 -40 0 -20 -20.000 1L ′′ xM ½ 1 0 8 2 0 -½ 250 2L ′′ x2 -1 0 0 -1 1 1 0 350 3L ′′ xA ½ 0 1 -4 -1 0 ½ 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 so- luçã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 repre- sentada 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 ca- sos, 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. 45 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 sorve- te em copinho produzido (em toneladas), temos: max. Xp + Xc s.a. Xp ≤ 300 Xc ≤ 150 Xp + 1,5Xc ≤ 400 2. Resolva-o graficamente. Xp0 Xc 100 100 200 200 300 300 400 Solução ótima: (Xp=300; Xc=66,67; Z=366,67) 400 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 coorde- nadas: Xp* = 300; Xc* = (400 – Xp) / 1,5 = 100 / 1,5 = 66,67; Z* = 366,67. 48 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 ajx para cada restrição do problema, ou somente para as restrições que tiverem variável de folga com coeficiente negativo. 2. Resolvemos o problema para a seguinte F.O. modificada: Min. q = ∑ ajx 3. Se q* = 0, então existe uma solução básica viável para o problema original. Neste caso, elimi- namos as variáveis artificiais, substituímos a F.O. modificada pela original e prosseguimos com o simplex. Introduzindo uma variável artificial ax6 , e mudando a função objetivo de forma a conter somente as variáveis artificiais, temos: Minimizar q = ax6 s.a.: x1 + x3 = 4 x2 + x4 = 6 3x1 + 2x2 - x5 + ax6 = 18 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, ax6 ≥ 0 V.B. x1 x2 x3 x4 x5 ax6 q 0 0 0 0 0 -1 x3 1 0 1 0 0 0 4 x4 0 1 0 1 0 0 6 ax6 3 2 0 0 -1 1 18 Reduzindo a coluna 6 à forma canônica, temos: V.B. x1 x2 x3 x4 x5 ax6 q 3 2 0 0 -1 0 18 x3 1 0 1 0 0 0 4 x4 0 1 0 1 0 0 6 ax6 3 2 0 0 -1 1 18 Iteração 1: V.B. x1 x2 x3 x4 x5 ax6 q 3 2 0 0 -1 0 18 x3 1 0 1 0 0 0 4 x4 0 1 0 1 0 0 6 ax6 3 2 0 0 -1 1 18 49 Iteração 2: V.B. x1 x2 x3 x4 x5 ax6 q 0 2 -3 0 -1 0 6 x1 1 0 1 0 0 0 4 x4 0 1 0 1 0 0 6 ax6 0 2 -3 0 -1 1 6 V.B. x1 x2 x3 x4 x5 ax6 q 0 0 0 0 0 -1 0 x1 1 0 1 0 0 0 4 x4 0 0 3/2 1 1/2 -1/2 3 x2 0 1 -3/2 0 -1/2 1/2 3 Fim da Fase 1. Retirando as partes sombreadas acima, e re-introduzindo a função objetivo original, temos: FASE 2 V.B. x1 x2 x3 x4 x5 -Z’ 3 5 0 0 0 0 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 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 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 4: V.B. x1 x2 x3 x4 x5 -Z’ 0 0 0 -3 1 -36 x1 1 0 0 -2/3 -1/3 2 x3 0 0 1 2/3 1/3 2 x2 0 1 0 1 0 6 50 Quadro final (ótimo): V.B. x1 x2 x3 x4 x5 -Z’ 0 0 -3 -5 0 -42 x1 1 0 1 0 0 4 x5 0 0 3 2 1 6 x2 0 1 0 1 0 6 x10 x2 6 4 3 2 A B C q = 18 q = 6 q = 0 Z = -27 Z = -36 Z = -42 Segundo Exemplo: Escolha da Mistura para Rações Grão 1 Grão 2 Necessidades mínimas Nutriente A 2 3 650 Nutriente C 5 3 1050 $/kg 32 35 Seja: x1 = qtde. (kg) do Grão 1 usada na ração x2 = qtde. (kg) do Grão 2 usada na ração Minimizar 32x1 + 35x2 Sujeito a: 2x1 + 3x2 ≥ 650 5x1 + 3x2 ≥ 1050 x1 ≥ 0, x2 ≥ 0 53 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. Mudança no vetor c 2. Mudança no vetor b 3. Mudança na matriz A 4. Adição de nova atividade 5. 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 = B B R Rc x c x+ s.a. B RBx Rx b+ = , 0, 0B Rx x≥ ≥ 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 0Rx = , é de- nominada 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: Bx Rx -Z 0 cj – zj 1Bc B b − xB I 1B R− 1B b− onde zj = 1B jc B a − 54 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, respec- tivamente): max. x1 + x2 s.a. x1 + x3 = 300 x2 + x4 = 150 x1 + 1,5x2 + x5 = 400 xj ≥ 0 sendo [ ] 1 2 3 4 5 1 0 1 0 0 300 0 1 0 1 0 150 1 1 0 0 0 1 1,5 0 0 1 400 x x A b c x x x x                = = = =                  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. Expres- sando isso em termos das equações matriciais vistas anteriormente, temos... 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0,67 0 0,67 1 1,5 0 0 1 0,67 1 0,67 B R B−            = = = −           −      [ ] [ ] 1 3 2 5 4 1 1 0 0 0 B R B R x x c c x x x x x     = = = =        [ ]1 0,333 0,667R Bc c B R−− = − − [ ]1 300 66,67 83,33Bx B b−= = 366,67B Bc x = ...que é precisamente o resultado que obtivemos na resolução do PPL através do Simplex: 55 ==================================================== -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, exi- gindo-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: [ ] 1 3 3 3 3( ) 0 ( ) 0 1 0 0 1 (0 ) 1 1 0 0,67 0 0,67 0 0 0,67 1 0,67 0 0,333 0 0,333 Bc z c c B aλ λ λ λ λ −+ − ≤ ⇒ + − ≤        ⇒ + − − ≤       −    ⇒ − ≤ ⇒ ≤ 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: [ ] [ ] 1 0 1 0 0 1 0 0 0 (1 ) 1 0 0,67 0 0,67 0 0 0 0,67 1 0,67 0 1 0,333 R Bc c B R λ λ −− ≤        ⇒ − + − ≤       −    ⇒ ≥ − 58 Primal (P) Dual (D) Max. cx Min. ub s.a. Ax ≤ b s.a. uA ≥ c x ≥ 0 x: (1× n) u ≥ 0 u: (m × 1) Exemplo: Primal (P) Dual (D) Max. 3x1 + 1x2 + 2x3 s.a. 2x1 + 4x2 + 3x3 ≤ 6 3x1 + 3x2 + 1x3 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 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 buxc ≤ Teorema 2: Se x e u são soluções viáveis dos problemas (P) e (D), respectivamente, e buxc = , então essas so- luções são ótimas, ou seja, bucx ** = Teorema da Existência Para um par de problemas duais, uma e somente uma das alternativas abaixo é verdadeira: • 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. Ex: (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: 59    ≥−∴≥−∴≤ ≥−∴≥−∴≥ 0)(0 0)(0 xAucAuccAu bxAubxAbxA Fazendo    −= −= xAuc bxAu )( )( β α Teremos: 0)()( ≥−=−+−=+ buxcxAucbxAuβα Se x e u forem soluções ótimas, teremos: buxc = 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 Problema de Minimização ≥ 0 ←–→ ≥ ≤ 0 ←–→ ≤ V ar iá ve is Irrestrito ←–→ = R es tr iç õe s ≤ ←–→ ≥ 0 ≥ ←–→ ≤ 0 = ←–→ Irrestrito R es tr iç õe s V ar iá ve is Feita essa primeira transformação, podemos então aplicar as regras usuais para passar o modelo du- al para a forma padrão, caso, seja necessário. 60 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 dispo- nibilidade destes recursos, a contribuição unitária de cada produto para o lucro da empresa, e a de- manda mínima do mercado. Consumo de Recursos (horas / unid.) Recursos da Fábrica (Setores de Produção) Televisor DVD Cãmera Disponibilidade (horas / mês) Produção de Circuitos Produção de Mecanismos Produção de Gabinetes Montagem de Produtos Expedição 0,151 0,000 0,078 0,340 0,057 0,210 0,345 0,056 0,450 0,030 0,120 0,450 0,045 0,370 0,045 22,500 17,200 10,500 35,000 6,800 Lucro (R$ / unid.) 45,00 115,00 216,00 Demanda mínima (unid. / mês) 55,800 15,500 23,200 Para o problema acima foi obtida a seguinte solução ótima através do Lindo: OBJECTIVE FUNCTION VALUE 1) 9578.494 VARIABLE VALUE REDUCED COST X1 55.800000 0.000000 X2 15.500000 0.000000 X3 24.467567 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 7.883092 0.000000 3) 0.842095 0.000000 4) 4.178559 0.000000 5) 0.000000 583.783813 6) 2.053360 0.000000 7) 0.000000 -153.486481 8) 0.000000 -147.702698 9) 1.267568 0.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 45.000000 153.486481 INFINITY X2 115.000000 147.702698 INFINITY X3 216.000000 INFINITY 121.444443 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 22.500000 INFINITY 7.883092 3 17.200000 INFINITY 0.842095 4 10.500000 INFINITY 4.178559 5 35.000000 0.692389 0.469000 6 6.800000 INFINITY 2.053360 7 55.800000 1.379412 2.036438 8 15.500000 1.042222 4.162659 9 23.200000 1.267568 INFINITY 63 PARTE II – Programação em Redes Introdução No contexto da Pesquisa Operacional, chamamos de Programação em Redes o estudo dos proble- mas que utilizam a Teoria dos Grafos como um dos principais recursos de modelagem. Neste con- texto, 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 mode- lagem por meio de grafos, como veremos mais adiante. 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 à ci- dade 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 “Pro- blema do Caixeiro Viajante (PCV)”. Podemos exemplificar o problema considerando somente 5 ci- dades e a rede de interligações (estradas) ilustrada na figura a seguir, onde os valores nas linhas re- presentam as distâncias entre as cidades. Redes / Grafos ESTRUTURA TOPOLÓGICA INFORMAÇÕES QUANTITATIVAS SOBRE OS ELEMENTOS 64 2 3 4 5 1 300 300 200 200 200 150 350 200 250 350 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: 17 9 10 4 10× = 2,5 × 107 segundos = 9,5 meses! 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 en- contrar 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 mode- lagem matemática em forma de PL, ou usando um outro algoritmo qualquer. Diferente dos proble- mas de PL que estudamos anteriormente, que dispõem do eficiente método Simplex, todos os méto- dos disponíveis para a obtenção de uma solução ótima para o PCV possuem dificuldade exponenci- al 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 en- contrar 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 pro- blemas, 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 “aproxima- das”. 65 Introdução à Teoria de Grafos Teoria dos grafos é uma ferramenta para formular problemas, tornando-os precisos, e definindo in- ter-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 po- dem 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 pro- blemas 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 gra- fos pode nos ajudar a compreender em “poucas palavras” o significado de grandes problemas liga- dos à 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ên- cia 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 ca- minho fechado, já a questão de determiná-lo só foi resolvida em 1873 (ou seja, 137 anos mais tarde) por Heierholzer. 68 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) é da- do por: V = { Maria, Pedro, Joana, Luiz } A = { (Maria, Pedro) , (Joana, Maria) , (Pedro, Luiz) , (Joana, Pedro) } G1: Neste exemplo estamos considerando que a relação <v é amigo de w> é uma rela- ção simétrica, ou seja, se <v é amigo de w> então <w é amigo de v>. Como conse- qüê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)} G2: A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é o caso de <w é pai/mãe de v>. O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos. 69 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 vizi- nhos) 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 exem- plo 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 ar- cos 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 Rena- ta e Emerson em G2. 70 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. G4: 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 particio- nado 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: • V = H U M • A = {(v,w) | (v ∈ H e w ∈ M) ou (v ∈ M e w ∈ H) e <v foi namorado de w>} G5: O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém duas par- tições de 3 vértices cada. Ele é completo pois todos os vértices de uma partição es- tão ligados a todos os vértices da outra par- tição. G6: K3,3 73 ÁRVORE Uma árvore é um grafo conexo sem ciclos. Seja G(V,A) um grafo com ordem n > 2; as proprie- dades seguintes são equivalentes para caracterizar G como uma árvore: 1. G é conexo e sem ciclos; 2. G é sem ciclos e tem n-1 arestas; 3. G é conexo e tem n-1 arestas; 4. 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. G20: ARBORESCÊNCIA Uma arborescência é uma árvore que possui uma ra- iz. Aplica-se, portanto, somente a grafos orientados. G21: FLORESTA Uma floresta é um grafo cujas componentes conexas são árvores. G22: 74 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 de- terminada demanda do produto; Nós de transbordo, que representam somente “pontos de passagem” para os produtos. São cruza- mentos, 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 ge- ral, 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 de- manda. 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 exem- plo, um caso típico onde temos diversas fábricas ou atacadistas que desejam distribuir um ou mais produtos para determinadas cidades ou lojas. 75 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: 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: 1 1 Custo Total , ( , ) n n ij ij i j c x i j A = = = ∀ ∈∑∑ ou: ( , ) Custo Total ij ij i j A c x ∈ = ∑ 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 re- presentarmos os limites mínimos e máximos dos fluxos nos arcos, como na figura abaixo. Chama- mos essas restrições de capacidade nos arcos. onde devemos ter, obrigatoriamente, ( , )ij ij ijl x u 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 ca- pacidades 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 qual- quer para onde chegam e de onde saem determinados arcos (fluxos): i i j (cij, lij, uij) i j xij 78 Sistemas Equilibrados Em sistemas ditos equilibrados, temos que: ,i js d i S j D= ∀ ∈ ∈∑ ∑ Nesses casos, podemos escrever o modelo da seguinte forma: Minimizar ( , ) ij ij i j A c x ∈ ∑ s.a. ( , ) ( , ) 0 i ij ki i i j A k i A s i S x x d i D i T ∈ ∈ ∀ ∈ − = − ∀ ∈  ∀ ∈ ∑ ∑ Uma outra forma de escrever as restrições de conservação de fluxo é a seguinte: Podemos considerar o fluxo produzido em um nó como sendo a sua capacidade máxima de ofer- ta, caso o nó seja de oferta. Caso contrário, o fluxo produzido no nó é igual a zero. Da mesma for- ma, 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 resolvi- do 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. Fluxo que chega ao nó i Fluxo produzido no nó i Fluxo que sai do nó i Fluxo consumido pelo nó i + + = 79 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 en- globa uma enorme quantidade de aplicações e pode ser resolvido de maneira extremamente eficien- te. O Problema de Transporte, de Designação, de Caminho Mais Curto e de Fluxo Máximo, que ve- remos 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éto- do Simplex de Redes, pode ser utilizada de maneira ainda mais eficiente do que o próprio Simplex. Algumas Considerações 1. A rede é representada por um Dígrafo (orientada) e conectada. 2. No mínimo um dos nós é um nó de oferta (origem). 3. No mínimo um dos nós é um nó de demanda (destino). 4. Todos os nós restantes são nós de transbordo (entreposto, intermediário, transshipment). 5. 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). Exemplos de Aplicações A mais importante aplicação está em planejar a operação de uma rede de distribuição de uma com- panhia. 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 cli- entes (demanda). Tipo de Aplicação Nós de Fornecimento Nós de Transbordo Nós de Demanda Operação de uma rede de distribuição Fontes de bens Locais de armazena- gem intermediárias Clientes Gerenciamento de detri- tos sólidos Fontes de resíduos Instalações de pro- cessamento Locais de depósitos de resíduos sólidos Operações de uma rede de fornecimento Vendedores Estoques intermediá- rios Instalações de proces- samento Gerenciamento de fluxo de dinheiro Fontes de dinheiro em um tempo específico Opções de investi- mento Necessidades de dinhei- ro em um tempo especí- fico Coordenação de mistura de produtos em plantas Plantas Produção de um pro- duto específico Mercado para um pro- duto específico 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). 80 Temos também os custos de transporte cij e as capacidades máximas de fluxo dos arcos AB e CE. Podemos também representar a mesma rede da seguinte forma: 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 Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED s.a. Nó A) xAB + xAC + xAD ≤ 60 Nó B) xBC – xAB ≤ 50 Nó C) xCE – xAC – xBC = 0 Nó D) xDE – xAD – xED = –30 Nó E) xED – xCE – xDE = –60 xAB ≤ 10 xCE ≤ 80 xij ≥ 0 A solução dada pelo Lindo© segue abaixo: A D B E C bA = 60 bB = 50 bD = –30 bE = –60 (2, 0, 10) (1, 0, 80) (3, 0, ∞) (9, 0, ∞) (4, 0, ∞) (3, 0, ∞) (2, 0, ∞) A D cAD = 9 B E C sA = 60 sB = 50 dD = 30 dE = 60 cAB = 2 uAB = 10 cAC = 4 cBC = 3 cDE = 3 cED = 2 cCE = 1 uCE = 80 83 Transformando Sistemas Não Equilibrados em Sistemas Equilibrados Caso o sistema não seja equilibrado, é fácil transformá-lo em um sistema equilibrado. Basta acres- centarmos 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 ar- cos com custo igual a zero. Fazendo isso, a função-objetivo original não será afetada, e a oferta ex- cedente será naturalmente “escoada” dos nós de oferta para esse nó artificial. Podemos ver isso u- sando o Exemplo 1 visto anteriormente: 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 Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED s.a. Nó A) xAB + xAC + xAD + xAr = 60 Nó B) xBC + xBr – xAB = 50 Nó C) xCE – xAC – xBC = 0 Nó D) xDE – xAD – xED = –30 Nó E) xED – xCE – xDE = –60 Nó r) – xAr – xBr = –20 xAB ≤ 10; xCE ≤ 80; xij ≥ 0 A D cAD = 9 B E C bA = 60 bB = 50 bD = –30 bE = –60 cAB = 2 uAB = 10 cAC = 4 cBC = 3 cDE = 3 cED = 2 cCE = 1 uCE = 80 r cAr = 0 cBr = 0 br = –20 A D B E C bA = 50 bB = 40 bD = –30 bE = –60 90 50 40 30 84 Resolvendo o modelo através do Lindo, vemos que a folga que existia para o “Nó A” agora é trans- formada no fluxo xAr: OBJECTIVE FUNCTION VALUE 1) 480.0000 VARIABLE VALUE REDUCED COST XAB 0.000000 1.000000 XAC 30.000000 0.000000 XAD 10.000000 0.000000 XBC 50.000000 0.000000 XCE 80.000000 0.000000 XDE 0.000000 5.000000 XED 20.000000 0.000000 XAR 20.000000 0.000000 XBR 0.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES Nó A) 0.000000 0.000000 Nó B) 0.000000 1.000000 Nó C) 0.000000 4.000000 Nó D) 0.000000 9.000000 Nó E) 0.000000 7.000000 Nó R) 0.000000 0.000000 8) 10.000000 0.000000 9) 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: 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: Soma dos fluxos que chegam ao nó i Soma dos fluxos que saem do nó i = 85 Podemos então escrever o modelo da seguinte maneira: Minimizar Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED s.a. Nó A) xAB + xAC + xAD – xf A = 0 Nó B) xBC – xAB – xf B = 0 Nó C) xCE – xAC – xBC = 0 Nó D) xDE + xDs – xAD – xED = 0 Nó E) xED + xEs – xCE – xDE = 0 Nó f) xf A + xf B – xsf = 0 Nó s) 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: A D B E C bA = 50 bB = 40 bD = –30 bE = –60 2 1 3 9 4 3 2 A D B E C bA = 50 bB = 40 bD = –30 bE = –60 2 1 3 9 4 3 2 f bf = 90 0 0 s 0 0 bs = –90 0 88 Minimizar ( , ) Custo Total ij ij i j A c x ∈ = ∑ s.a. ( , ) ij i i j A x s ∈ ≤∑ i S∀ ∈ ( , ) ij j i j A x d ∈ − = −∑ j D∀ ∈ ij ij ijl x u≤ ≤ ( , )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; 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: 0ijx ≥ ( , )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ão- capacitados): Min. ( , ) ij ij i j A c x ∈ ∑ s.a. ( , ) ij i i j A x s ∈ ≤∑ 1,2,3,...,i m= ( , ) ij j i j A x d ∈ =∑ 1, 2,3,...,j n= 0ijx ≥ ( , )i j A∀ ∈ Para sistemas equilibrados, podemos ainda escrever: Min. ( , ) ij ij i j A c x ∈ ∑ s.a. ( , ) ij i i j A x s ∈ =∑ 1,2,3,...,i m= ( , ) ij j i j A x d ∈ =∑ 1, 2,3,...,j n= 0ijx ≥ ( , )i j A∀ ∈ 89 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. Usando a forma clássica, o modelo de PL que resolve esse problema pode ser escrito assim: Min. Z = 4x11 + 3x12 + 4x21 + 5x22 + 7x23 + 6x24 + 2x33 + 4x34 s.a. s1) x11 + x12 ≤ 50 s2) x21 + x22 + x23 + x24 ≤ 50 s3) x33 + x34 ≤ 50 d1) x11 + x21 = 20 d2) x12 + x22 = 15 d3) x23 + x33 = 18 d4) x24 + x34 = 25 xij ≥ 0 A solução dada pelo Lindo© segue abaixo: OBJECTIVE FUNCTION VALUE 1) 261.0000 VARIABLE VALUE REDUCED COST X11 20.000000 0.000000 X12 15.000000 0.000000 X21 0.000000 0.000000 X22 0.000000 2.000000 X23 0.000000 5.000000 X24 0.000000 2.000000 X33 18.000000 0.000000 X34 25.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES S1) 15.000000 0.000000 S2) 50.000000 0.000000 S3) 7.000000 0.000000 D1) 0.000000 -4.000000 D2) 0.000000 -3.000000 D3) 0.000000 -2.000000 D4) 0.000000 -4.000000 1 1 3 2 2 4 3 4 3 5 7 6 2 4 50 50 50 20 15 18 25 4 90 O grafo que representa essa solução é dado abaixo: 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. 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. Z = 4x11 + 3x12 + 4x21 + 5x22 + 7x23 + 6x24 + 2x33 + 4x34 s.a. s1) x11 + x12 + x15 = 50 s2) x21 + x22 + x23 + x24 + x25 = 50 s3) x33 + x34 + x35 = 50 1 1 3 2 2 4 3 4 5 3 5 7 6 2 4 0 0 0 50 50 50 20 15 18 25 72 4 1 1 3 2 2 4 3 20 15 18 25 50 50 50 20 15 18 25 93 O grafo que representa essa solução é dado abaixo: 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 re- solver 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 W2 W3 W4 Disponibilidade C1 75 75 C2 5 65 55 125 120 55 C3 15 85 100 85 Demanda 80 5 65 70 15 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 W1 W3 C2 W2 W4 C3 75 15 85 55 5 65 C1 W1 W3 C2 W2 W4 C3 20 70 30 55 80 45 94 O Problema de Designação (PD) Este problema, também chamado de Problema de Atribuição, de Alocação ou de Casamento (1- Matching), é 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, tam- bé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, obser- vadas 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. 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 de- mandas 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. 1 1 n n ij ij i j c x = = ∑∑ s.a. 1 1 n ij j x = =∑ 1, 2,3,...,i n= 1 1 n ij i x = =∑ 1, 2,3,...,j n= {0,1}ijx ∈ ,i j∀ Veja que a nossa variável de decisão é binária, ou seja, teremos: 1 1 3 2 2 4 3 4 Máquinas (ofertas) Tarefas (demanda) 95 1 se a máquina estiver designada à tarefa ; 0 caso contrário.ij i j x  =   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 uni- modularidade 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 1 2 3 4 1 1 3 4 5 2 4 2 4 7 3 6 7 8 3 M áq ui na s 4 5 4 2 1 Aplicação do Algoritmo: 1. Determinar o menor valor para cada linha da matriz: Valor Mínimo na Linha (ui) 1 3 4 5 1 4 2 4 7 2 6 7 8 3 3 5 4 2 1 1 2. Subtrair do valor em cada linha, o mínimo ui daquela linha: 0 2 3 4 2 0 2 5 3 4 5 0 4 3 1 0 3. Determinar o menor valor para cada coluna dessa matriz resultante: