Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional I 1 Pesquisa Operacional I Alexander Cascardo Carneiro Edison Alves Portela Junior 1ª e di çã o Pesquisa Operacional I 2 DIREÇÃO SUPERIOR Chanceler Joaquim de Oliveira Reitora Marlene Salgado de Oliveira Presidente da Mantenedora Wellington Salgado de Oliveira Pró-Reitor de Planejamento e Finanças Wellington Salgado de Oliveira Pró-Reitor de Organização e Desenvolvimento Jefferson Salgado de Oliveira Pró-Reitor Administrativo Wallace Salgado de Oliveira Pró-Reitora Acadêmica Jaina dos Santos Mello Ferreira Pró-Reitor de Extensão Manuel de Souza Esteves DEPARTAMENTO DE ENSINO A DISTÂNCIA Gerência Nacional do EAD Bruno Mello Ferreira Gestor Acadêmico Diogo Pereira da Silva FICHA TÉCNICA Texto: Alexander Cascardo Carneiro e Edison Alves Portela Junior Revisão Ortográfica: Rafael Dias de Carvalho Moraes Projeto Gráfico e Editoração: Antonia Machado, Eduardo Bordoni, Fabrício Ramos e Victor Narciso Supervisão de Materiais Instrucionais: Antonia Machado Ilustração: Eduardo Bordoni e Fabrício Ramos Capa: Eduardo Bordoni e Fabrício Ramos COORDENAÇÃO GERAL: Departamento de Ensino a Distância Rua Marechal Deodoro 217, Centro, Niterói, RJ, CEP 24020-420 www.universo.edu.br Ficha catalográfica elaborada pela Biblioteca Universo – Campus Niterói C289p Carneiro, Alexander Cascardo. Pesquisa operacional I / Alexander Cascardo Carneiro e Edison Alves Portela Junior ; revisão de Rafael Dias de Carvalho Moraes. – 1. ed. – Niterói, RJ: UNIVERSO: Departamento de Ensino à Distância, 2018. 233 p. : il. 1. Pesquisa operacional. 2. Programação linear. 3. Método Simplex. 4. Dualidade (Matemática). 5. Análise de sensibilidade. 6. Problema de localização - alocação. 7. Transporte de mercadorias - Programação linear. 8. Administração de pessoal - Programação linear. 9. Ensino à distância. I. Portela Junior, Edison Alves. II. Moraes, Rafael Dias de Carvalho. III. Título. CDD 658.4034 Bibliotecária responsável: Elizabeth Franco Martins CRB 7/4990 Informamos que é de única e exclusiva responsabilidade do autor a originalidade desta obra, não se r esponsabilizando a ASOEC pelo conteúdo do texto formulado. © Departamento de Ensi no a Dist ância - Universidade Salgado de Oliveira Todos os direitos reservados. Nenhuma parte desta publicação pode ser reproduzida, arquivada ou transmitida de nenhuma forma ou por nenhum meio sem permissão expressa e por escrito da Associação Salgado de Oliveira de Educação e Cultura, mantenedora da Univer sidade Salgado de Oliveira (UNIVERSO). Pesquisa Operacional I 3 Palavra da Reitora Acompanhando as necessidades de um mundo cada vez mais complexo, exigente e necessitado de aprendizagem contínua, a Universidade Salgado de Oliveira (UNIVERSO) apresenta a UNIVERSOEAD, que reúne os diferentes segmentos do ensino a distância na universidade. Nosso programa foi desenvolvido segundo as diretrizes do MEC e baseado em experiências do gênero bem-sucedidas mundialmente. São inúmeras as vantagens de se estudar a distância e somente por meio dessa modalidade de ensino são sanadas as dificuldades de tempo e espaço presentes nos dias de hoje. O aluno tem a possibilidade de administrar seu próprio tempo e gerenciar seu estudo de acordo com sua disponibilidade, tornando-se responsável pela própria aprendizagem. O ensino a distância complementa os estudos presenciais à medida que permite que alunos e professores, fisicamente distanciados, possam estar a todo o momento, ligados por ferramentas de interação presentes na Internet através de nossa plataforma. Além disso, nosso material didático foi desenvolvido por professores especializados nessa modalidade de ensino, em que a clareza e objetividade são fundamentais para a perfeita compreensão dos conteúdos. A UNIVERSO tem uma história de sucesso no que diz respeito à educação a distância. Nossa experiência nos remete ao final da década de 80, com o bem- sucedido projeto Novo Saber. Hoje, oferece uma estrutura em constante processo de atualização, ampliando as possibilidades de acesso a cursos de atualização, graduação ou pós-graduação. Reafirmando seu compromisso com a excelência no ensino e compartilhando as novas tendências em educação, a UNIVERSO convida seu alunado a conhecer o programa e usufruir das vantagens que o estudar a distância proporciona. Seja bem-vindo à UNIVERSOEAD! Professora Marlene Salgado de Oliveira Reitora. Pesquisa Operacional I 4 Pesquisa Operacional I 5 Sumário Apresentação da disciplina ............................................................................................. 07 Plano da disciplina ............................................................................................................ 09 Unidade 1 – Programação Matemática ........................................................................ 11 Unidade 2 – Programação Linear .................................................................................. 31 Unidade 3 – O Método Simplex ..................................................................................... 45 Unidade 4 – Dualidade..................................................................................................... 73 Unidade 5 – Análise de Sensibilidade........................................................................... 93 Unidade 6 – O Problema de Transporte....................................................................... 107 Unidade 7 – O Problema de Designação ..................................................................... 131 Considerações finais ......................................................................................................... 151 Conhecendo o autor ......................................................................................................... 152 Referências .......................................................................................................................... 153 Anexos.................................................................................................................................. 155 Pesquisa Operacional I 6 Pesquisa Operacional I 7 Apresentação da Disciplina Sejam bem-vindos a disciplina: Pesquisa Operacional I! Ao início de cada unidade de estudo, você encontrará uma apresentação dos temas que serão desenvolvidos, os aspectos mais relevantes, além dos objetivos a serem alcançados. Além disso, há também uma série de referências bibliográficas sobre os assuntos abordados. As unidades foram redigidas de forma a facilitar o entendimento do seu conteúdo, que compreende uma parte conceitual, sempre com aplicações dos conceitos, seguida de exercícios práticos. Estamos certos de que a leitura dos conteúdos será uma atividade prazerosa. Porque a profissão de engenheiro requer muito estudo e aprimoramento que dependem diretamente dela. A disciplina em questão é uma ferramenta poderosa para os engenheiros, preferencialmente os de produção, na sua aplicação em otimização dos processos de manufatura ou de serviço. Utilize o seu tempo e imprima o seu próprio ritmo de aprendizagem. Lembre- se, você tem total autonomia na condução do seu processo de estudo, mas sempre que possível procure seguir o cronograma da disciplina. É importante que você faça todas as atividades e reflita sobre os respectivos padrões de respostas. Além disso, você poderá complementar o conteúdo de cada unidade através da leitura complementar e, por sua própria iniciativa, buscar nos jornais e revistas casos práticos que envolvam empresas, objeto da aplicação das teorias e modelos analisados nas aulas. Pesquisa Operacional I 8 Pesquisa Operacional I 9 Plano da Disciplina A disciplina tem como objetivo principal desenvolver, no estudante de engenharia,a capacidade de analisar qualquer problema de uma maneira simples e lógica e de aplicar, à sua solução, uns poucos e bem compreendidos princípios básicos. E ainda, compreender e entender fenômenos e funções da Pesquisa Operacional como uma ferramenta no auxilio das tomadas de decisões, suas ênfases, campo de atuação e responsabilidades, bem como sua interação com as outras ferramentas das engenharias e outros segmentos de trabalho. Para isso, a disciplina foi dividida em sete unidades para maior compreensão dos assuntos abordados. Com a finalidade de facilitar a compreensão segue uma síntese de cada unidade, ressaltando seus objetivos específicos para que você possa ter uma visão ampla do conteúdo que irá estudar. Unidade 1 – Programação Matemática Nesta unidade, faremos uma análise do contexto sócio histórico que propiciou o seu surgimento: O que é pesquisa operacional? A partir daí poderemos entender melhor o seu conceito e o seu objeto de estudo. Objetivos da unidade: Analisar a condição da pesquisa operacional como ferramenta na tomada de decisão e o uso da programação linear como solução. Unidade 2 – Programação Linear Nesta unidade, será apresentada uma forma de solução ou possíveis soluções de um P.P.L. usando o método gráfico e o método analítico. Objetivos da unidade: Mostrar ao leitor formas matemáticas para solucionar um P.P.L., usando métodos matemáticos simples. Como e quando aplicar essas soluções. Unidade 3 - O Método Simplex Nesta unidade, será apresentada a forma de solução ou possíveis soluções de um P.P.L. usando o método tabular Simplex. Pesquisa Operacional I 10 Objetivos da unidade: Mostrar ao leitor formas matemáticas para solucionar um P.P.L. usando métodos matemáticos tabulares simples. Como e quando aplicar essas soluções. Unidade 4 - Dualidade Nesta unidade, será apresentada forma de solução ou possíveis soluções de um P.P.L. usando a dualidade. Objetivos da unidade: Mostrar ao leitor que a quantidade de cálculo necessária para resolver um modelo linear pelo Simplex pode ser reduzida, substituindo o modelo chamado primal pelo modelo dual. Unidade 5 - Análise de Sensibilidade Nesta unidade, serão discutidos alterações no P.P.L., na função objetivo, nas restrições e nas variáveis de decisão e o impacto nas suas soluções. Objetivos da unidade: Mostrar ao leitor que os dados podem sofrer variações com o decorrer do tempo ou com a inclusão de novas informações que surgem com o progresso das tecnologias. Unidade 6 – O Problema de Transporte Nesta Unidade, aprenderemos de forma mais ampla algumas das aplicabilidades de um P.P.L. em problemas de transporte. Objetivos da unidade: Mostrar ao leitor o método tabular simplex na solução de problemas de transporte. Determinar a solução otimizada para o transporte de mercadorias entre as origens e os destinos. Apresentar a solução para problemas não balanceados. Unidade 7 – O Problema de Designação Nesta unidade, aprenderemos algumas das aplicabilidades de um P.P.L. em problemas de designação. Objetivos da unidade: Mostrar ao leitor o método tabular simplex na solução de problemas de designação. Determinar a solução otimizada para a designação a partir do método húngaro. Pesquisa Operacional I 11 Programação Matemática 1 Pesquisa Operacional I 12 Nesta unidade, faremos uma análise do contexto sócio histórico que propiciou o seu surgimento: O que é pesquisa operacional? A partir daí poderemos entender melhor o seu conceito e o seu objeto de estudo. Objetivos da unidade: Analisar a condição da pesquisa operacional como ferramenta na tomada de decisão e o uso da programação linear como solução. Plano da unidade: O que é a Pesquisa Operacional? Problemas de otimização. Exemplos. Programação Linear. Formulação do problema Convenção da solução Bons estudos! Pesquisa Operacional I 13 O que é a Pesquisa Operacional? A origem histórica da Pesquisa Operacional (PO) foi realizada por indivíduos como Charle Baggage. Sua pesquisa foi sobre o custo de transporte e triagem do correio para a "Penny Post" da Inglaterra universal em 1840, e estudos sobre o comportamento dinâmico de veículos ferroviários em defesa de bitola larga do GWR. Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre problemas em física na década de 1920 e, mais tarde, tentar estender estes para as ciências sociais. A Pesquisa Operacional moderna teve origem na Estação de Pesquisa Bawdsey no Reino Unido em 1937 e foi o resultado de uma iniciativa do superintendente da estação, AP Rowe. Rowe concebeu a ideia como um meio para analisar e melhorar o funcionamento do sistema de radar de alerta, nos seus primórdios, no Reino Unido, Chain Home (CH). Inicialmente, ele analisou o funcionamento do equipamento de radar e de suas redes de comunicação, expandindo posteriormente para incluir o comportamento do pessoal de operação. Isto revelou limitações não reconhecidas da rede CH e permitiu medidas corretivas a tomar. O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares na Segunda Guerra Mundial. Por conta do esforço requerido pela guerra na alocação de recursos escassos às várias operações militares e às atividades dentro de cada operação de uma maneira efetiva, várias seções de pesquisa operacional foram estabelecidas nas forças armadas britânicas. Logo depois, esses esforços similares foram empreendidos nos Estados Unidos. Muitos cientistas foram reunidos para aplicar uma abordagem científica a problemas estratégicos e táticos. Esses cientistas foram chamados a realizar “pesquisas operacionais militares”, daí vem o nome. Um passo natural tomado foi estender o sucesso da Pesquisa Operacional nos esforços de guerra para as organizações civis. A indústria pós-guerra havia crescido muito e se deparava com os problemas causados pela crescente complexidade das organizações. Vale lembrar que após a guerra houve inúmeros movimentos para a reconstrução dos países arrasados. Os problemas que apareceram durante a guerra e a complexidade das organizações na reconstrução dos países eram muito Pesquisa Operacional I 14 semelhantes, porém em um contexto diferente. Em 1948, o Massachusetts Institute of Tecnology (MIT) instituiu o primeiro programa formal de estudos em Pesquisa Operacional para campos não militares. A “idade de ouro” da PO vai de 1945 até meados da década de 1970, devida à rápida expansão. Dois fatores foram cruciais para o crescimento da PO naquele período: O primeiro foi o avanço na melhoria nas técnicas de PO e na formulação dos problemas - Ex. o método simplex para resolver problemas de programação linear. O segundo foi a popularização dos computadores. Problemas de otimização A construção de modelos. O desafio da PO é transformar um problema real de produção ou de processo em um modelo matemático que reproduza fielmente essa realidade; destacar as variáveis que se queira controlar - variáveis essas que estão sujeitas a restrições de ordem técnica; validar o modelo matemático e implementá-lo. Para facilitar nosso estudo vamos dividir esse problema em etapas: Definição da situação-problema; Formulação de um modelo quantitativo; Resolução do modelo e encontro da melhor solução; Consideração de fatores imponderáveis; Implementação da solução. Agora vamos ver cada uma destas etapas. Definição da situação-problema Nessa fase os gerentes do projeto deverão discutir o problema de forma mais clara e coerente, definir o escopo do projeto, definir os objetivos a serem alcançados e quais são os possíveis caminhos a seguir. Pesquisa Operacional I 15 As limitações técnicas devem ser levantadas e as relações deste sistema com os demais da empresa ou do ambiente externo. Sejam micro clientes ou micro fornecedores internos da corporaçãoe stakeholders de outras organizações, com a finalidade de validar esse modelo. Formulação de um modelo quantitativo Em PO os modelos quantitativos são modelos matemáticos formados por um conjunto de equações e inequações. A eficiência do modelo é medida pela função objetivo, que pode ser de maximização ou de minimização. Por exemplo, maximizar o lucro ou minimizar o custo. Quanto melhor o valor obtido na função objetivo para cada solução proposta, melhor a eficiência do modelo: A solução ótima. Resolução do modelo e encontro da melhor solução Variáveis controladas ou de decisão: são aquelas cujo valor está sob o controle do administrador. Cabe a ele decidir um particular valor a cada uma dessas variáveis. Numa programação de produção uma possível variável a ser controlada pode ser a quantidade a ser produzida em um período de tempo, o que é competência do administrador. Variáveis não controladas: são aquelas cujos valores são arbitrados por sistemas fora do controle do administrador. Custos de produtos ou insumos, demanda de produtos, preços de mercado, são alguns exemplos desse tipo de variável. Podemos afirmar que um bom modelo é aquele que tem desempenho que mais chega próximo da realidade. O modelo deve ser rodado sempre, comparado com a realidade e revisado a fim de chegar o mais próximo possível dessa realidade. O modelo se torna mais fiel à realidade, incorporando características, com a adição de variáveis. Pesquisa Operacional I 16 Consideração de fatores imponderáveis Por outro lado, existem fatores que podem ser importantes, mas são difíceis de quantificar. O comportamento humano é um deles. A interação homem-máquina também. Faz-se necessário estimar o impacto desses fatores na solução que foi gerada pelo modelo matemático. Providências preliminares devem ser tomadas visando esses fatores. Implementação da solução Essa é a fase final. Deve ser apresentado ao administrador. A implantação deve ser acompanhada observando o comportamento do sistema com a solução adotada. Novos ajustes serão requeridos. É desejável que nessa fase do processo as pessoas que serão atingidas pelas mudanças estejam envolvidas. Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. Fonte: Adaptado de Moreira (2004 apud Moreira, 2010). Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. Pesquisa Operacional I 17 Programação Linear A programação linear é um dos mais populares modelos matemáticos estruturados utilizados para resolver problemas que apresentam variáveis que podem ser medidas e cujos relacionamentos podem ser expressos por meio de equações e/ou inequações lineares. As aplicações podem ser em vários campos das áreas científicas ou sociais, tais como administração da produção, análise de investimento, controle de estoque, economia, logística e etc. O modelo matemático de programações linear, que de agora em diante denominaremos de Problema de Programação Linear (PPL) é constituído de uma função objetivo linear; de restrições técnicas representadas por um grupo de equações e/ou inequações também lineares; e da restrição matemática de não negatividade (não pode ser negativa). Otimizar: ),,,()( 21 nxxxfXf – Função objetivo Sujeito a: mnm n n b b b xxxg xxxg xxxg 2 1 21 212 211 ),,,( ),,,( ),,,( Onde: nnn xcxcxcxxxfXf 221121 ),,,()( ),,1( ),,,( 33221121 mi xaxaxaxaxxxg niniiini Pesquisa Operacional I 18 n é o número de variáveis do problema m é o número de restrições do problema i é o índice de determinada restrição ),,1( mi j é o índice de determinada variável ),,1( nj jc é o coeficiente (constante) da variável jx , da função objetivo ija é o coeficiente (constante) na i-ésima restrição e da variável jx ib é constante da i-ésima restrição Um problema de programação linear está na sua forma padrão, quando o problema de otimização linear tiver as seguintes características: A função objetivo deve ser minimizada ou maximizada; As restrições do problema são definidas por um sistema de equações e/ou inequações lineares; As condições de não negatividade de todas as variáveis de decisão complementam as restrições do problema. Matematicamente, podemos representar um problema na forma-padrão por: nnxcxcxcMaxZ 2211 S.R. (Segundo as Restrições) 11212111 bxaxaxa nn 0,,, 21 2211 22222121 xx bmxaxaxa bxaxaxa nmnmm nn Pesquisa Operacional I 19 Ou na forma reduzida: j n j j xcMaxZ 1 S.R. ij n j ij bxa 1 ),,1( mipara 0,,, 21 nxxx Agora iremos introduzir alguns termos: Solução: qualquer valor obtido dentro do domínio da função objetivo, )(Xf , para as variáveis de decisão; Solução viável: são soluções que satisfaçam todas as restrições; Solução ótima: uma solução viável que tenha o melhor valor da função objetivo, )(Xf , isto é, que maximiza ou minimiza a função objetivo, podendo ser única ou múltipla; Proporcionalidade: o valor da função objetivo é diretamente proporcional ao valor de cada variável de decisão. Formulação do Problema Não há uma regra fixa para a construção do modelo matemático. Mas a maioria dos problemas de programação linear (PPL) segue um roteiro que norteia o raciocínio. Veremos a seguir um roteiro básico em quatro etapas: 1.Definir as variáveis de decisão ),,1( njxj . Se estivermos estudando uma programação da produção, as variáveis de decisão podem representar as quantidades produzidas de produtos; se for uma programação de investimento, as variáveis representarão o tipo de portfólio escolhido. Pesquisa Operacional I 20 2.Definir a função objetivo da tomada de decisão. Que pode ser maximizar lucro, minimizar custos e etc. Ela é uma expressão formada por uma combinação linear das variáveis de decisão. 3.Definir as restrições técnicas as quais estará sujeito. Como por exemplo, quantidade em estoque; homem-hora disponível na produção; 4.A não negatividade. Sempre. 0,,, 21 nxxx Exemplo 1.1: Na fábrica de Brinquedos Eletrônicos X-Playhouse, são produzidos dois tipos de brinquedos: B1 e B2. O setor de contabilidade e custos informa que o lucro unitário do brinquedo B1 é de R$ 20,00 e do brinquedo B2 é de R$ 35,00. Na linha de produção o brinquedo B1 consome 2 horas e o brinquedo B2 consome 4 horas de trabalho. Essa linha de montagem tem 24 horas de trabalho disponíveis por dia. Sabe-se ainda que a demanda esperada pelo brinquedo B1 é de 8 unidades e de B2 é de 4 unidades por dia. Como o engenheiro de produção da fábrica Brinquedos Eletrônicos X-Playhouse, monte o plano de produção de forma que o lucro seja maximizado. Solução: 1. Comece definindo as variáveis de decisão, ou seja, as quantidades a serem produzidas de cada brinquedo. 1x = quantidade de B1 a produzir; 2x = quantidade de B2 a produzir; 2. Formule a função objetivo que irá maximizar o lucro da empresa. O objetivo é maximizar o lucro, que pode ser calculado da seguinte forma: Lucro auferido com a venda de B1: 20 x 1x (lucro por unidade de B1 vezes quantidade produzida de B1). Pesquisa Operacional I 21 Lucro auferido com a venda de B2: 35 x 2x (lucro por unidade de B2 x quantidade produzida de B2). Então o lucro total obtido será: 2121 3520);( xxxxL Objetivo: 2121 3520);( xxxxLMax 3. Sujeito às restrições técnicas: 4 8 2442 2 1 21 x x xx 4. A não negatividade. 0, 21 xx Convenção da solução A solução de um problema de programação linear, P.P.L., pode ter uma única solução ótima ou pode ter infinitas soluções ótimas, como veremos nos próximos capítulos. A função objetivo pode ser de maximização, por exemplo,maximizar o lucro de uma empresa; como pode ser de minimização, minimizar custos. As restrições técnicas podem ser =, ou : se um insumo será utilizado em sua totalidade, a restrição será de igualdade (=); se um insumo que está estocado, então, esta restrição será ( ), porque ele vai até a quantidade que está disponível no estoque; se há a necessidade desse insumo ser pelo menos, então, esta restrição será ( ). Pesquisa Operacional I 22 Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em contato com seu tutor virtual através do ambiente virtual de aprendizagem e consulte sempre a biblioteca do seu polo. É hora de se avaliar Lembre-se de realizar as atividades desta unidade de estudo. Elas irão ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de ensino-aprendizagem. Pesquisa Operacional I 23 Exercícios – Unidade 1 1) Sobre a origem da Pesquisa Operacional, é correto afirmar que: a) Sua origem histórica foi realizada por indivíduos como Charle Baggage. b) Baggage pesquisou o custo de transporte e triagem do correio. c) Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre problemas em física na década de 1920. d) TODAS as alternativas acima estão CORRETAS. e) TODAS as alternativas acima estão INCORRETAS. 2) Considere as seguintes afirmações sobre a Pesquisa Operacional na era moderna: I- O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares na Segunda Guerra Mundial. II- Até hoje a Pesquisa Operacional é utilizada apenas nas pesquisas militares. III- Dois fatores foram fundamentais para o crescimento da Pesquisa Operacional: o primeiro foi o avanço na melhoria nas técnicas de PO e na formulação dos, e o segundo foi a popularização dos computadores. São corretas as afirmações: a) I, apenas. b) I e II, apenas. c) I e III, apenas. d) TODAS as afirmações estão CORRETAS. e) TODAS as afirmações estão INCORRETAS. Pesquisa Operacional I 24 3) São etapas para a resolução de problemas de Pesquisa Operacional, EXCETO: a) Definição da situação-problema. b) Formulação de um modelo qualitativo. c) Formulação de um modelo quantitativo. d) Implementação da solução. e) Consideração de fatores imponderáveis. 4) Sobre as etapas para a resolução de problemas de Pesquisa Operacional (PO), é INCORRETO afirmar que: a) Em PO os modelos quantitativos são modelos matemáticos formados por um conjunto composto tanto por equações, quanto por inequações. b) A eficiência do modelo é medida pela função objetivo, que pode ser de maximização ou de minimização. c) As variáveis controladas ou de decisão são aquelas cujo valor está sob o controle do administrador. d) Numa programação de produção uma possível variável a ser controlada pode ser a quantidade a ser produzida em um período de tempo. e) Custos de produtos ou insumos, demanda de produtos, preços de mercado, são alguns exemplos de variáveis controladas. 5) Sobre a Programação Linear, é correto afirmar que: a) A função objetivo deve ser minimizada ou maximizada. b) A solução viável é aquela que maximiza ou minimiza a função objetivo. c) Uma solução ótima não precisa ser uma solução viável. d) TODAS as alternativas acima estão CORRETAS. e) TODAS as alternativas acima estão INCORRETAS. Pesquisa Operacional I 25 6) Certa fabrica produz dois produtos P1 e P2. O lucro unitário do produto P1 é de R$ 100,00, enquanto o lucro do produto P2 é de R$ 180,00. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo de produção disponível para isso é de 1.200 horas. A demanda esperada para cada produto é de 40 unidades para P1 e 30 unidades para P2. Qual é o plano de produção para que a empresa maximize o seu lucro nesses itens? Considere: 1x = quantidade de P1 a produzir; 2x = quantidade de P2 a produzir; a) 2121 180100);( xxxxLMax Restrições técnicas 30 40 200.13020 2 1 21 x x xx Restrições de não negatividade 0, 21 xx b) 2121 180100);( xxxxLMax Restrições técnicas 60 50 200.13020 2 1 21 x x xx Restrições de não negatividade 0, 21 xx c) 2121 3020);( xxxxLMax Restrições técnicas 30 40 200.1180100 2 1 21 x x xx Restrições de não negatividade 0, 21 xx d) 2121 180100);( xxxxLMax Pesquisa Operacional I 26 Restrições técnicas 30 40 200.13020 2 1 21 x x xx e) 2121 180100);( xxxxLMax Restrições de não negatividade 0, 21 xx 7) Um vendedor de legumes pode transportar 800 caixas de legumes para sua região de vendas. Ele necessita transportar 200 caixas de cenouras a R$ 20,00 de lucro por caixa, pelo menos 100 caixas de batata a R$ 10,00 de lucro por caixa, e no máximo 200 caixas de mandioca a R$ 30,00 por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Considere: 1x = quantidade de caixas de batata; 2x = quantidade de caixas de mandioca; a) 40003010);( 2121 xxxxLMax Restrições técnicas 200 100 600 2 1 21 x x xx Restrições de não negatividade 0, 21 xx b) 40003010);( 2121 xxxxLMax Restrições técnicas 200 100 600 2 1 21 x x xx Restrições de não negatividade 0, 21 xx c) 4000200100);( 2121 xxxxLMax Pesquisa Operacional I 27 Restrições técnicas 30 10 600 2 1 21 x x xx Restrições de não negatividade 0, 21 xx d) 2121 3010);( xxxxLMax Restrições técnicas 200 100 800 2 1 21 x x xx Restrições de não negatividade 0, 21 xx e) 40003010);( 2121 xxxxLMax Restrições técnicas 200 100 800 2 1 21 x x xx Restrições de não negatividade 0, 21 xx 8) Na fabricação de dois de seus produtos, uma empresa utiliza dois equipamentos que limitam a produção. Em um dado período de tempo, estão disponíveis 30 horas do equipamento 1 e 60 horas do equipamento 2. Para a fabricação de uma unidade do produto A, usa-se 1 hora do equipamento 1 e 2 horas do equipamento 2. Já para uma unidade do produto B, são gastas 2 horas do equipamento 2. O equipamento 1 não toma parte na produção do produto B. Por outro lado, uma unidade do produto A leva a um lucro de R$120,00, enquanto cada unidade do produto B gera um lucro de R$ 52,00. Formule o modelo de programação linear para maximizar o lucro da empresa. Considere: 1x = quantidade do produto A; 2x = quantidade do produto B; Pesquisa Operacional I 28 a) 2121 3060);( xxxxLMax Restrições técnicas 30 12022 1 21 x xx Restrições de não negatividade 0, 21 xx b) 2121 52120);( xxxxLMax Restrições técnica s 60 60 2 21 x xx Restrições de não negatividade 0, 21 xx c) 2121 3060);( xxxxLMax Restrições técnicas 30 60 1 21 x xx Restrições de não negatividade 0, 21 xx d) 2121 52120);( xxxxLMax Restrições técnicas 30 6022 1 21 x xx Restrições de não negatividade 0, 21 xx e) 2121 52120);( xxxxLMax Restrições técnicas 30 12022 1 21 x xx Restrições de não negatividade 0, 21 xx Pesquisa Operacional I 29 9) Uma alfaiataria está considerando quanto deve produzir de seus dois modelos de terno, denominados de Executivo e Despojado, de forma a maximizar o lucro. Será impossível fabricar quanto se queira de cada um dos modelos, porque existem limitações nas horas disponíveis para a operação de costura e a operação de acabamento, as duas operações são básicas na fabricação. No caso da costura, existem 160 horas-máquinas disponíveis, enquanto para o acabamento, que é feito manualmente, haverá, no máximo, 220 homens-horas. Em termos de lucro unitário e produção, osdois modelos apresentam as seguintes características: a. Executivo: I. Lucro unitário: R$ 105,00 II. Horas-máquina de costura por unidade: 2 III. Homens-hora de acabamento por unidade: 1 b. Despojado: I. Lucro unitário: R$ 70,00 II. Horas-máquina de costura por unidade: 1 III. Homens-hora de acabamento por unidade: 4 Formule o modelo de programação linear para maximizar o lucro da alfaiataria. Considere: 1x = quantidade do terno Executivo; 2x = quantidade do terno Despojado; Pesquisa Operacional I 30 10) Uma rádio FM local tem o seguinte problema: foi descoberto que o programa de sertanejo com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 ouvintes, enquanto o programa de MPB, com 10 minutos de musica e 1 minuto de propaganda chama a atenção de 10.000 ouvintes. No decorrer de uma semana, o patrocinador insiste no uso mínimo, 5 minutos pra sua propaganda e que não há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de telespectadores: Construa o modelo do PPL. Pesquisa Operacional I 31 2Programação Linear Pesquisa Operacional I 32 Nesta unidade, será apresentada uma forma de solução ou possíveis soluções de um P.P.L. usando o método gráfico e o método analítico. Objetivos da unidade: Mostrar ao leitor formas matemáticas para solucionar um P.P.L., usando métodos matemáticos simples. Como e quando aplicar essas soluções. Plano da unidade: Introdução. Formas padrão e normal Exemplos de aplicação Definição geral de programação linear. Conjunto convexo Solução gráfica de um PPL Bons estudos! Pesquisa Operacional I 33 Introdução. Formas padrão e normal Como já foi introduzido na unidade 1, dizemos que um P.P.L. está em sua forma padrão se for proposto nela uma maximização da função objetiva e se todas as restrições forem do tipo menor ou igual, bem como se os termos constantes ( ib ) e as variáveis de decisão assumirem valores não negativos. Matematicamente, podemos representar um P.P.L. na forma padrão assim: nnxcxcxcMaxZ 2211 S.R. 11212111 bxaxaxa nn 0,,, 21 2211 22222121 xx bmxaxaxa bxaxaxa nmnmm nn Ou na forma reduzida: j n j j xcMaxZ 1 S.R. ij n j ij bxa 1 ),,1( mipara 0,,, 21 nxxx Pesquisa Operacional I 34 Quando resolvemos o modelo matemático na forma padrão, chegamos à solução. Que pode ser definhada assim: Solução: quaisquer valores dentro do domínio da função objetivo, )(Xf , para as variáveis de decisão, independentemente de se tratar de uma escolha desejável ou permissível. Solução viável: uma solução é dita viável quando todas as restrições são satisfeitas. Solução ótima: é a solução viável que tem o valor mais favorável da função objetivo, )(Xf , isto é, maximiza ou minimiza a função objetivo, podendo ser única ou múltipla, como veremos adiante. Exemplos de aplicação A programação linear pode ser empregada de várias formas em vários setores e campos da ciência, por exemplo: Administração da produção; Análise de investimento; Alocação de recursos limitados; Planejamento regional e urbano; Logística; Custo de transporte; Localização da rede de distribuição; Alocação de recursos energéticos. Pesquisa Operacional I 35 Definição geral de programação linear. Conjunto convexo A definição geral já foi ministrada na unidade um, que repito agora para relembrar. Otimizar: ),,,()( 21 nxxxfXf – Função objetivo Sujeito a: mnm n n b b b xxxg xxxg xxxg 2 1 21 212 211 ),,,( ),,,( ),,,( Onde: nnn xcxcxcxxxfXf 221121 ),,,()( ),,1( ),,,( 33221121 mi xaxaxaxaxxxg niniiini n é o número de variáveis do problema m é o número de restrições do problema i é o índice de determinada restrição ),,1( mi j é o índice de determinada variável ),,1( nj jc é o coeficiente (constante) da variável jx , da função objetivo ija é o coeficiente (constante) na i-ésima restrição e da variável jx ib é constante da i-ésima restrição Pesquisa Operacional I 36 Agora vamos apresentar alguns teoremas a respeito das soluções de um P.P.L. Porém, antes vamos definir o que representa um conjunto convexo. Vamos fazê-lo de forma intuitiva. Um conjunto convexo é um conjunto de pontos em que todos os segmentos de reta que unem dois de seus pontos que são internos ao conjunto, isto é, todos os pontos de cada segmento também pertencem ao conjunto original. Graficamente, um exemplo de conjunto convexo e não convexo é representado na figura abaixo. Solução gráfica de um PPL Em problemas de programação linear que envolvam 02 (duas) variáveis de decisão, a solução que pode ser viável e/ou ótima, pode ser encontrada graficamente. Vamos considerar o P.P.L. abaixo: 2121 95);( xxxxLMax Sujeito a )(3 )(4 )(1642 2 1 21 IIIx IIx Ixx 0, 21 xx Pesquisa Operacional I 37 A solução óbvia para );( 21 xxL se dá em 01 x e 02 x , então substituindo na função objetivo, )0;0(L = 0 – Solução óbvia. Usaremos o par de eixos cartesianos para representar as quantidades 1x e 2x . Agora vamos traçar as retas que representam as restrições técnicas de função constantes (II) e (III), figura abaixo: A restrição (I) é dada pela inequação 1642 21 xx que iremos representar no gráfico por uma reta. Como vamos trabalhar em R2, convém representar a inequação acima na sua forma canônica, que mostraremos a seguir: 2 4 4 216 2164 1642 1 2 1 2 12 21 x x x x xx xx Pesquisa Operacional I 38 Graficamente, podemos representar o conjunto ou região de soluções viáveis por meio da figura abaixo. Todas as possíveis soluções de 1x e 2x estão presentes na região destacada do gráfico. Para encontrarmos o valor que melhor atende nosso P.P.L. proposto, vamos usar o processo de tentativa e erro. Podendo chegar ao valor ótimo verificando a existência de pontos da reta que fazem parte do conjunto de soluções viáveis. Traçamos a reta da função objetivo no ponto da solução óbvia (ponto A(0;0)) e a partir dela traçamos as paralelas a essa, passando pelos pontos críticos da região de solução viável até o ponto extremo (é o ponto ótimo, que maximiza ou minimiza a função objetivo, que nesse caso é o ponto C(4;2)), pois estamos maximizando a função objetivo (devemos observar todas as “quinas” da região que contém as soluções viáveis, que chamamos de “pontos críticos” até encontrar o ponto que maximiza a função objetivo, que chamamos de ponto extremo). No ponto extremo, será dado o valor máximo da função objetivo L. Que no exemplo usado L = 38. Esse processo está mostrado na figura abaixo: Pesquisa Operacional I 39 Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em contato com seu tutor virtual através do ambiente virtual de aprendizagem e consulte sempre a biblioteca do seu polo. É hora de se avaliar Lembre-se de realizar as atividades desta unidade de estudo. Elas irão ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de ensino-aprendizagem. Pesquisa Operacional I 40 Exercícios – Unidade 2 1) São campos de aplicações da programação linear, EXCETO: a) Análise de investimento. b) Logística. c) Custo de transporte. d) Redes envolvendo arcos. e) Alocação de recursos energéticos. Considere o seguinte enunciado para as questões 2, 3 e 4: 2121 32);( xxxxLimizarMax Sujeito a 62 42 21 21 xx xx 0, 21 xx 2) Marque a alternativa que representa corretamente cada uma das restrições (inequações)na forma canônica (isto é, isolando 2x ): a) 2 2 12 x x e 2 4 12 x x b) 2 4 12 x x e 2 2 12 x x c) 2 2 12 x x e 2 3 12 x x d) 2 4 12 x x e 2 4 12 x x e) 42 x e 32 x Pesquisa Operacional I 41 3) Assinale a alternativa que apresente a solução óbvia e os pontos críticos. Dica: Esboce os gráficos das inequações na forma canônica da questão 2. a) (0;0), (6;0), (1;5/2) e (0;2). b) (0;0), (3;0) e (0;3). c) (0;0), (6;0) e (0;2) d) (3;0) e (0;2) e) (6;0) e (0;3) 4) Marque a alternativa que maximiza a função objetivo L, e os respectivos valores de 1x e 2x , que compõe o ponto extremo. a) 01 x ; 02 x e Lucro = 12 b) 11 x ; 52 x e Lucro = 17 c) 01 x ; 22 x e Lucro = 10 d) 11 x ; 2/52 x e Lucro = 13 e) 61 x ; 02 x e Lucro = 12 Considere o seguinte enunciado para as questões 5, 6 e 7: 2121 5,03,0);( xxxxLimizarMax Sujeito a 33 22 21 21 xx xx 0, 21 xx Pesquisa Operacional I 42 5) Marque a alternativa que representa corretamente cada uma das restrições (inequações) na forma canônica (isto é, isolando 2x ): a) 12 1 xx e 2 2 12 x x b) 12 22 xx e 3 1 12 x x c) 12 22 xx e 3 2 12 x x d) 2 1 12 x x e 3 1 12 x x e) 3 3 12 x x e 2 2 12 x x 6) Assinale a alternativa que apresente a solução óbvia e os pontos críticos. Dica: Esboce os gráficos das inequações na forma canônica da questão 5. a) (0;0), (1;0) e (0;1). b) (0;0), (1;0), (0,7;0,7) e (0,5;1). c) (0;0), (1;0), (0,6;0,8) e (0;1). d) (1;0) e (0;1). e) (0,7;0) e (0,7;0). 7) Marque a alternativa que maximiza a função objetivo L, e os respectivos valores de 1x e 2x , que compõe o ponto extremo. a) 01 x ; 12 x e Lucro = 0,5 b) 11 x ; 02 x e Lucro = 0,3 c) 01 x ; 02 x e Lucro = 2 Pesquisa Operacional I 43 d) 6,01 x ; 8,02 x e Lucro = 0,58 e) 7,01 x ; 7,02 x e Lucro = 0,65 8) Considere o seguinte enunciado: 2121 32);( xxxxLimizarMax Sujeito a 6 42 93 21 21 21 xx xx xx 0, 21 xx Marque a alternativa que maximiza a função objetivo L, e os respectivos valores de 1x e 2x , que compõe o ponto extremo. a) 01 x ; 12 x e Lucro = 3 b) 01 x ; 62 x e Lucro = 18 c) 61 x ; 02 x e Lucro = 12 d) 5,41 x ; 5,12 x e Lucro = 13,5 e) 51 x ; 22 x e Lucro = 16 Pesquisa Operacional I 44 9) Considere o seguinte enunciado: 2121 1210);( xxxxCMinimizar Sujeito a 10 202 21 21 xx xx 0, 21 xx Encontre os pontos críticos. 10) Considere a questão anterior: encontre o valor que minimiza a função objetivo de custos C, e os respectivos valores de 1x e 2x , que compõe o ponto extremo. Pesquisa Operacional I 45 3O Método Simplex Pesquisa Operacional I 46 Nesta unidade, será apresentada forma de solução ou possíveis soluções de um P.P.L. usando o método tabular Simplex. Objetivos da unidade: Mostrar ao leitor formas matemáticas para solucionar um P.P.L. usando métodos matemáticos tabulares simples. Como e quando aplicar essas soluções. Plano da unidade: Desenvolvimento do Método Simplex Resumo de procedimentos de solução do Método Simplex Técnica de variáveis artificiais Variação das aplicações do Método Simplex Bons estudos! Pesquisa Operacional I 47 Desenvolvimento do Método Simplex O método gráfico para a solução de um P.P.L., que aprendemos na Unidade anterior, só pode ser empregado quando existir duas ou, no máximo, três variáveis (neste caso de difícil visualização). Quando tiver três ou mais variáveis é aconselhável usar a solução tabular chamada de método Simplex. Utilizando esse método é possível incrementar as variáveis básicas trocando pelas varáveis não básicas até chegar à solução teste de otimalidade. Ou seja, as soluções básicas por não básicas, gerando novas soluções. Os critérios de escolha de vetores e consequentemente das variáveis que entram e saem para a formação da nova base constituem o centro do Simplex. Vamos tomar o modelo que apresenta uma solução básica inicial. Suponhamos que a função objetivo seja de maximização, que os modelos possuam restrições (menor ou igual) e os termos da direita sejam não negativos (positivos ou iguais a zero), então existe uma solução básica formada pelas variáveis de folga. Exemplo: 2121 53);( xxxxLimizarMax Sujeito a 30 206 1042 21 21 21 xx xx xx 0, 21 xx Primeiro vamos transformar o sistema de inequações em um sistema de equações com variáveis não negativas. Para isso, introduziremos em cada uma das inequações as variáveis F1, F2 e F3, que representam as folgas das inequações 1, 2 e 3, isto é, a diferença entre o segundo e o primeiro membro dessas inequações. Isso tem como resultado o sistema de equações com variáveis não negativas: Pesquisa Operacional I 48 30 206 1042 321 221 121 Fxx Fxx Fxx 0,,,, 32121 FFFxx 1º Passo: Teste de otimalidade para a solução. Este teste consiste em avaliar o efeito da permuta da uma variável básica por outra não básica, com a consequente formação de uma nova solução. Se a entrada de uma variável não básica puder melhorar o desempenho do sistema, a solução testada não é ótima. Essa avaliação é possível quando a função objetivo está escrita somente em termos das variáveis não básicas. Voltemos ao exemplo, a função objetivo está escrita na forma: 2121 53);( xxxxLMax Fazendo 0,0 21 xx , uma solução básica inicial formada pelas variáveis de folga F1=10, F2=20 e F3=30. Neste caso, as variáveis básicas são F1, F2 e F3 e as variáveis não básicas 1x e 2x Portanto, a função objetivo está escrita com as variáveis não básicas. Examinando a função objetivo e a solução inicial 0,0 21 xx e L = 0, com 2121 53);( xxxxL , temos: Se 1x entra na base com valor 1, o valor de L passa de L=0 para L=3, aumentando 3 unidades, exatamente o valor do coeficiente de 1x . Se 2x entra na base com valor 1, o valor de L passa de L=0 para L=5, aumentando 5 unidades, exatamente o valor do coeficiente de 2x . Por outro lado, se o coeficiente 1x ou 2x fosse negativo, a entrada dessa variável diminuiria o valor de L, de acordo com seu coeficiente. Podemos concluir Pesquisa Operacional I 49 que enquanto a função objetivo apresentar variáveis não básicas com coeficientes positivos, ela poderá ser aumentada, não sendo, portanto a solução ótima. Vamos reescrever agora, a função objetivo com todas as variáveis à esquerda: 2121 53);( xxxxL 053 21 xxL Os coeficientes positivos à direita se tornam negativos quando passamos para a esquerda, portanto, coeficientes à esquerda indicam que o valor de L pode ser aumentado com a entrada da variável na base, e na proporção de seu coeficiente. Escrito dessa forma, a solução testada só será ótima quando as variáveis não básicas apresentam somente coeficientes positivos. 2º Passo: Cálculo da nova solução básica. a) Variável que entra na base: entra na base a variável com coeficiente negativo de maior valor absoluto. A ideia é incrementar o valor de L. Examinando a função objetivo do exemplo: 053 21 xxL ou 2121 53);( xxxxL Entra a variável 2x , pois cada unidade a mais de 2x aumenta L em 5 unidades. b) Variável que sai: sai a variável que primeiro se anula com a entrada da variável escolhida no item anterior, no caso 2x , que entra com maior valor possível. Ela pode ser descoberta dividindo-se os termos da direita das restrições pelos coeficientes positivos da variável que entra. O menor valor indica que a variável básica dessa linha é a que primeiro se anula e sairá da base. No nosso exemplo: 30 206 1042 321 221 121 Fxx FxxFxx Entra 10/4=2,5 → Sai a variável dessa linha (F1) 20/1=20 30/(-1) = - 30 Pesquisa Operacional I 50 A última divisão (30/(-1)) não pode ser considerada, pois daria valor negativo para a variável na próxima base, o que não é possível. Portanto, sai a variável da primeira linha, no caso F1. c) Elemento pivô: A coluna da variável que entra e a linha da variável que sai identificam um elemento comum chamado pivô. A linha variável que sai é também linha pivô. No caso, a primeira linha é a pivô e o coeficiente 4 de 2x é o elemento pivô. d) Calculando a nova solução: Vamos organizar a função objetivo e restrições em uma tabela com colunas formadas pelos coeficientes de cada variável e outra dos termos independentes. L X1 X2 F1 F2 F3 b Tabela 1 1 -3 -5 0 0 0 0 L1 F1 0 2 4 1 0 0 10 L2 F2 0 6 1 0 1 0 20 L3 F3 0 1 -1 0 0 1 30 L X1 X2 F1 F2 F3 b Tabela 1 1 -3 -5 0 0 0 0 L1 F1 0 2 4 1 0 0 10 Sai (Linha pivô) L2 F2 0 6 1 0 1 0 20 L3 F3 0 1 -1 0 0 1 30 Entra na base Dividimos a linha pivô pelo valor do elemento pivô, que em nosso exemplo tem valor 4,obtendo uma nova linha com o pivô unitário. Linha pivô 0 2 4 1 0 0 10 Dividido por 4 0 0,5 1 0,25 0 0 2,5 Nova linha pivô Vamos reescrever cada uma das outras linhas da seguinte maneira: 1º Multiplicar os elementos da nova linha pivô pelo coeficiente da variável que entra da outra linha, com sinal trocado. Pesquisa Operacional I 51 2º Somar termo a termo com os elementos da outra linha. Voltando ao exemplo: Coeficiente da variável que entra (X2) na primeira linha é -5. Então: Nova linha pivô 0 0,5 1 0,25 0 0 2,5 Multiplicar por 5 0 2,5 5 1,25 0 0 12,5 (+) linha da função objetivo 1 -3 -5 0 0 0 0 Nova linha da função objetivo 1 -0,5 0 1,25 0 0 12,5 Coeficiente da variável que entra (X2) na linha 2 é 1. Então: Nova linha pivô 0 0,5 1 0,25 0 0 2,5 Multiplicar por (-1) 0 -0,5 -1 -0,25 0 0 -2,5 (+) linha 2 0 6 1 0 1 0 20 Nova linha 2 0 5,5 0 -0,25 1 0 17,5 Coeficiente da variável que entra (X2) na linha 3 é -1. Nova linha pivô 0 0,5 1 0,25 0 0 2,5 Multiplicar por (1) 0 0,5 1 0,25 0 0 2,5 (+) linha 3 0 1 -1 0 0 1 30 Nova linha 3 0 1,5 0 0,25 0 1 32,5 Reescrevendo a nova tabela com os resultados obtidos teremos: L X1 X2 F1 F2 F3 b Tabela 2 1 -0,5 0 1,25 0 0 12,5 L1 X2 0 0,5 1 0,25 0 0 2,5 L2 F2 0 5,5 0 -0,25 1 0 17,5 L3 F3 0 1,5 0 0,25 0 1 32,5 De onde concluímos a nova solução: Variáveis Não básicas: X1 = 0 e F1 = 0 (termos presentes na primeira linha); Variáveis básicas: X2 = 2,5, F2 = 17,5 e F3 = 32,5 (obtido das demais linhas, fazendo X1 = 0 e F1 = 0) e Valor de L: L = 12,5 (obtido da primeira linha fazendo X1 = 0 e F1 = 0) A função objetivo na nova solução está escrita em termos das variáveis não básicas X1 e F1. As variáveis básicas têm coeficientes nulos. A solução obtida tem L = 12,5, contra um L = 0 da solução inicial. É melhor, mas não é ótima, pois o coeficiente de X1 na nova função objetivo é negativo. Pesquisa Operacional I 52 Cálculo da nova solução: L X1 X2 F1 F2 F3 b b/X1 Tabela 2 1 -0,5 0 1,25 0 0 12,5 L1 X2 0 0,5 1 0,25 0 0 2,5 5,0 L2 F2 0 5,5 0 -0,25 1 0 17,5 3,18 Sai L3 F3 0 1,5 0 0,25 0 1 32,5 21,67 Entra Variável que entra na base: X1 (coeficiente negativo de maior valor absoluto na nova função – tabela 2). Variável que sai: vamos dividir os termos independentes (constantes, isto é, b) pelos coeficientes positivos de X1 (o resultado já aparece na última coluna da tabela anterior): 2,5/0,5 = 5 17,5/5,5 = 3,18 menor valor: sai a variável dessa linha, no caso F2 Nova linha pivô – L Elemento pivô: 5,5 Nona linha pivô = linha pivô dividido por 5,5. Nova linha pivô 0 5,5 0 -0,25 1 0 17,5 Dividido por 5,5 0 1 0 -0,045 0,18 0 3,18 O coeficiente da variável que entra (X1) na nova linha é -0,5. Então: Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 Multiplicar por 0,5 0 0,5 0 -0,02 0,091 0 1,59 (+) linha da função objetivo 1 -0,5 0 1,25 0 0 12,5 Nova linha da função objetivo 1 0 0 1,227 0,09 0 14,09 O coeficiente da variável que entra (X1) na nova linha L1 é 0,5. Então: Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 Multiplicar por -0,5 0 -0,5 0 0,0227 -0,09 0 -1,59 (+) Linha 1 0 0,5 1 0,25 0 0 2,5 Nova linha 1 0 0 1 0,273 -0,09 0 0,91 Pesquisa Operacional I 53 O coeficiente da variável que entra (X1) na nova linha L3 é 1,5. Então: Nova linha pivô 0 1 0 -0,045 0,18 0 3,18 Multiplicar por -1,5 0 -1,5 0 0,068 -0,27 0 -4,77 (+) linha 3 0 1,5 0 0,25 0 1 32,5 Nova linha 3 0 0 0 0,318 -0,27 1 27,73 Reescrevendo a nova tabela com os resultados obtidos teremos: L X1 X2 F1 F2 F3 b Tabela 3 1 0 0 1,227 0,09 0 14,09 L1 X2 0 0 1 0,273 -0,09 0 0,91 L2 X1 0 1 0 -0,045 0,18 0 3,18 L3 F3 0 0 0 0,318 -0,27 1 27,73 A nova solução será, portanto: Variáveis Não básicas: F1 = 0 e F2 = 0; Variáveis básicas: X1 =3,18; X2 = 0,91 e F3 = 27,73 e Valor de L: L = 14,09 A função objetivo está escrita em termos das variáveis não básicas F1 e F2, pois os coeficientes das variáveis básicas são nulos. O valor de L passou de L = 12,5 para L = 14,09. Essa solução é ótima, pois os coeficientes das variáveis não básicas na função objetivo são positivos. Se F1 ou F2 entrar na base, o valor de L diminui, contrariando o objetivo. Além disso, temos os valores de X1 =3,18 e X2 = 0,91. Pesquisa Operacional I 54 Resumo de procedimentos de solução do Método Simplex Este tópico será apresentado através de um exemplo, como segue abaixo: 321321 32);;( xxxxxxZimizarMax Sujeito a 3023 202 40 321 321 321 xxx xxx xxx 0,, 321 xxx Note que agora nosso sistema tem três variáveis. a. Vamos agora colocar as variáveis de folga e as variáveis de função objetivo à esquerda e transformar as inequações em equações, introduzindo as variáveis de folga. 032 321 xxxZimizarMax Sujeito a 3023 202 40 3321 2321 1321 Fxxx Fxxx Fxxx 0,,,,, 321321 FFFxxx Montamos o quadro agora: Z X1 X2 X3 F1 F2 F3 b b/X2 Tabela 1 1 -2 -3 -1 0 0 0 0 L1 F1 0 1 1 1 1 0 0 40 40 L2 F2 0 2 1 -1 0 1 0 20 20 L3 F3 0 3 2 -1 0 0 1 30 15 Sai Entra Pesquisa Operacional I 55 b. Solução básica inicial: Variáveis Não básicas: X1 = 0; X2 = 0 e X3 = 0 Variáveis básicas: F1 =40; F2 = 20 e F3 = 30 Valor de Z: Z = 0 c. Teste da solução: A solução não é ótima, pois tem coeficientes negativos na função objetivo. d. Cálculo da nova solução: Variável que entra: X2 (coeficiente negativo da função objetivo de maior valor absoluto) Variável que sai (termos independentes b divididos pelos coeficientes de X2 – variável que entra na base): Da coluna b/X2, 40/1 = 40; 20/1 = 20 e 30/2 = 15 Sai o de menor valor: 15 Sai a variável da linha 3 (F3) Linha pivô: linha 3 Elemento pivô: 2 Dividindo a linha pivô por 2, temos: Nova linha pivô: Linha pivô 0 3 2 -1 0 0 1 30 Dividido por 2 0 1,5 1 -0,5 0 0 0,5 15 Cálculo da nova linha de Z (coeficiente da variável que entra = -3) Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 X (3) 0 4,5 3 -1,5 0 0 1,5 45 (+) linha Z 1 -2 -3 -1 0 0 0 0 Nova linha Z 1 2,5 0 -2,5 0 0 1,5 45 Pesquisa Operacional I 56 Cálculo da nova linha L1 (coeficiente da variável que entra = 1) Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 X (-1) 0 -1,5 -1 0,5 0 0 -0,5 -15 (+) linha 1 0 1 1 1 1 0 0 40 Nova linha 1 0 -0,5 0 1,5 1 0 -0,5 25 Cálculo da nova linha L2 (coeficiente da variável que entra = 1) Nova linha pivô 0 1,5 1 -0,5 0 0 0,5 15 X (-1) 0 -1,5 -1 0,5 0 0 -0,5 -15 (+) linha 2 0 2 1 -1 0 1 0 20 Nova linha 2 0 -0,5 0 -0,5 0 1 -0,5 5 Reescrevendo a nova tabela teremos: Z X1 X2 X3 F1 F2 F3 b b/X1 Tabela 2 1 2,5 0 -2,5 0 0 1,5 45 L1 F1 0 -0,5 0 1,5 1 0 -0,5 25 16,67 Sai L2 F2 0 0,5 0 -0,5 0 1 -0,5 5 -10L3 X2 0 1,5 1 -0,5 0 0 0,5 15 -30 Entra Nova solução: Variáveis Não básicas: X1 = 0; X3 = 0 e F3 = 0 Variáveis básicas: X2 = 15; F1 = 25 e F2 = 5 Valor de Z: Z = 45 Essa solução não é ótima, pois o coeficiente de X3 na nova função objetivo tem valor negativo (-2,5). Vamos calcular uma nova iteração: Variável que entra: X3 (coeficiente negativo da função objetivo de maior valor absoluto) Variável que sai (termos independentes b divididos pelos coeficientes de X3 – variável que entra na base): Da coluna b/X3 25/1,5 = 16,67; 5/(-0,5) = -10 e 1,5/(-0,5) = -30 Pesquisa Operacional I 57 Sai o de menor valor: desconsidere os valores negativos, pois dariam valores negativos para as variáveis na próxima solução. Sai, portanto, a variável da linha L1: F1 Linha pivô: linha 1 Elemento pivô: 1,5 Dividindo a linha pivô por 1,5, temos: Nova linha pivô: Linha pivô 0 -0,5 0 1,5 1 0 -0,5 25 Dividido por 1,5 0 -0,33 0 1 0,67 0 -0,33 16,67 Cálculo da nova linha de Z (coeficiente da variável que entra = -2,5) Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 X (2,5) 0 -0,83 0 2,5 1,68 0 -0,83 41,68 (+) linha Z 1 2,5 0 -2,5 0 0 1,5 45 Nova linha Z 1 1,68 0 0 1,68 0 0,68 86,68 Cálculo da nova linha L2 (coeficiente da variável que entra = -0,5) Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 X (0,5) 0 -0,17 0 0,5 0,34 0 -0,17 8,34 (+) linha 2 0 0,5 0 -0,5 0 1 -0,5 5 Nova linha 2 0 0,34 0 0 0,34 1 -0,67 13,34 Cálculo da nova linha L3 (coeficiente da variável que entra = -0,5) Nova linha pivô 0 -0,33 0 1 0,67 0 -0,33 16,67 X (0,5) 0 -0,17 0 0,5 0,34 0 -0,17 8,34 (+) linha 3 0 1,5 1 -0,5 0 0 0,5 15 Nova linha 3 0 1,34 1 0 0,34 0 0,34 23,34 Pesquisa Operacional I 58 Reescrevendo a nova tabela teremos: Z X1 X2 X3 F1 F2 F3 b Tabela 3 1 1,68 0 0 1,68 0 0,68 86,68 L1 X3 0 -0,33 0 1 0,67 0 -0,33 16,67 L2 F2 0 0,34 0 0 0,34 1 -0,67 13,34 L3 X2 0 1,34 1 0 0,34 0 0,34 23,34 Nova solução: Variáveis Não básicas: X1 = 0; F1 = 0 e F3 = 0 Variáveis básicas: X2 = 23,34; X3 = 16,67e F2 = 13,34 Valor de Z: Z = 86,68 Essa nova solução é ótima, pois todos os coeficientes das variáveis na função objetivo são positivos. Temos o valor máximo de Z = 86,68, obtido com X1 = 0, X2 = 23,34 e X3 = 16,67. Técnica de variáveis artificiais Nos exemplos que foram resolvidos até agora pelo método tabular Simplex, as restrições eram todas do tipo com os termos da direita positivos. O acréscimo das variáveis de folga fornece nesse caso uma solução básica inicial. Veremos agora os demais tipos: 1º a restrição é do tipo : a variável de folga é subtraída e seu valor é negativo, quando se anulam as variáveis de decisão. 2º a restrição é do tipo =:não receba a variável de folga. Quando estes tipos de estrições acima ocorrem, acrescentamos variáveis auxiliares ai com formação de um novo modelo. A solução básica inicial do novo modelo é formada pelas variáveis de folga das restrições do tipo e pelas variáveis auxiliares ai. Pesquisa Operacional I 59 Exemplo: 321321 );;( xxxxxxZimizarMax Sujeito a 6032 202 102 321 321 321 xxx xxx xxx 0,, 321 xxx a) Acrescentar as variáveis de folga: 2X1 + X2 - X3 + F1 = 10 X1 + X2 + 2X3 - F2 = 20 2X1 + X2 + 3X3 = 60 Nestes termos, não há uma solução básica inicial devido a segunda e a terceira restrições. Pois F2 = -20 é inviável segundo a não negatividade e 0 = 60 é matematicamente falso. b) Acrescentar nas segunda e terceira restrições as variáveis auxiliares ou artificiais a2 e a3: 2X1 + X2 - X3 + F1 = 10 X1 + X2 + 2X3 - F2 + a2 = 10 2X1 + X2 + 3X3 + a3 = 60 Agora temos uma solução básica inicial: F1 = 10; a2 = 20 e a3 = 60 com todas as outras variáveis nulas. Pesquisa Operacional I 60 Variação das aplicações do Método Simplex O problema da minimização. No caso da função objetivo ser de minimização, então, devemos multiplicá-la por (-1). Obtendo uma função equivalente para a maximização. Exemplo: 321321 43);;( xxxxxxZrMinimimiza Sujeito a 202 10 321 321 xxx xxx 0,, 321 xxx O modelo equivalente será então: 321 43)( xxxZimizarMax Sujeito a 202 10 321 321 xxx xxx 0,, 321 xxx Resolvido o modelo equivalente, teremos a solução do modelo original com a troca do sinal de Z. O método de a função objetivo auxiliar Esse método foi desenvolvido para atender as equações e inequações dos tipos = e , acrescentando as variáveis auxiliares, para compor com as folga das inequações do tipo , a solução básica necessária à aplicação do Simplex. Começaremos a estudar esse método, construindo uma função objetivo auxiliar W, formada pela soma das variáveis auxiliares. W = a1 + a2 + , ..., + an Pesquisa Operacional I 61 A função W deve ser escrita em termos das variáveis originais e comporá o novo objetivo a ser minimizado. Minimizar W porque o objetivo desse método é fazer as variáveis auxiliares iguais à zero. Quando as variáveis auxiliares forem não básicas, teremos: a1 = a2 = ... = an = 0 e W = 0 As variáveis e funções auxiliares podem ser abandonadas, como diz o próprio nome: auxiliares. O novo objetivo será dado pela função objetivo original. Então teremos o modelo original com a solução básica inicial procurada. Exemplo: 321321 );;( xxxxxxZimizarMax Sujeito a 6032 202 102 321 321 321 xxx xxx xxx 0,, 321 xxx 1.Começamos acrescentando as variáveis de folga e as variáveis auxiliares, conforme já fizemos anteriormente, teremos então: 6032 202 102 3321 22321 1321 axxx aFxxx Fxxx 2.Fazemos a função auxiliar W = a2+a3 Da segunda restrição: a2 = -X1-X2-2X3+F2+20 Da terceira restrição: a3 = -2X1-X2-3X3+60 W = a2+a3 = -3X1-2X2-5X3+F2+80 Mini W = Max (-W) = 3X1+2X2+5X3-F2-80 Logo, -W -3X1-2X2-5X3+F2 = -80 Pesquisa Operacional I 62 O quadro com a função auxiliar fica: Z W X1 X2 X3 F1 F2 a2 a3 b b/X3 Tabela 1 1 -1 -1 -1 0 0 0 0 0 L1 F1 0 2 1 -1 1 0 0 0 10 -10 L2 a2 0 1 1 2 0 -1 1 0 20 10 Sai L3 a3 0 2 1 3 0 0 0 1 60 20 -w -1 -3 -2 -5 0 1 0 0 -80 Entra Solução da tabela 1 Variáveis Não básicas: X1 = 0; X2 = 0; X3 = 0 e F2 = 0 Variáveis básicas: F1 = 10; a2 = 20 e a3 = 60 Valor de W: W = 80 A função objetivo a ser minimizada é W. Observando seus coeficientes, verificamos que a resolução do quadro não é ótima. Cálculo da nova solução: Variável que entra: X3 (coeficiente negativo da função objetivo de maior valor absoluto: -5) Variável que sai (termos independentes b divididos pelos coeficientes de X3 – variável que entra na base): Da coluna b/X3 10/(-1) = -10; 20/2 = 10 e 60/3 = 20 Sai o de menor valor, não negativo: 10. Sai a variável da linha 2 (a2) Linha pivô: linha 2 Elemento pivô: 2 Dividindo a linha pivô por 2, temos: Pesquisa Operacional I 63 Nova linha pivô: Cálculo da nova linha de Z (coeficiente = -1) Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 X (1) 0 0,5 0,5 1 0 -0,5 0,5 0 10 (+) linha Z 1 -1 -1 -1 0 0 0 0 0 Nova linha Z 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 Cálculo da nova linha L1 (coeficiente = -1) Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 X (1) 0 0,5 0,5 1 0 -0,5 0,5 0 10 (+) linha 1 0 2 1 -1 1 0 0 0 10 Nova linha 1 0 2,5 1,5 0 1 -0,5 0,5 0 20 Cálculo da nova linha L3 (coeficiente = 3) Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 X (-3) 0 -1,5 -1,5 -3 0 1,5 -1,5 0 -30 (+) linha 3 0 2 1 3 0 0 0 1 60 Nova linha 3 0 0,5 -0,5 0 0 1,5 -1,5 1 30 Cálculo da nova linha W (coeficiente = -5) Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10 X (5) 0 2,5 2,5 5 0 -2,5 2,5 0 50 (+) linha w -1 -3 -2 -5 0 1 0 0 -80 Nova linha w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 Pesquisa Operacional I 64Reescrevendo a nova tabela teremos: Z W X1 X2 X3 F1 F2 a2 a3 b b/X1 Tabela 2 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 L1 F1 0 2,5 1,5 0 1 -0,5 0,5 0 20 -40 L2 X3 0 0,5 0,5 1 0 -0,5 0,5 0 10 -20 L3 a3 0 0,5 -0,5 0 0 1,5 -1,5 1 30 20 Sai -w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 Entra Nova solução: Variáveis Não básicas: X1 = 0; X2 = 0, F2 = 0 e a2 = 0 Variáveis básicas: X3 = 10; F1 = 20 e a3 = 30 Valor de W: W = 30 Cálculo da nova solução: Variável que entra: F2 (coeficiente -1,5) Variável que sai (termos independentes b divididos pelos coeficientes de F2 – variável que entra na base): Da coluna b/F2, 20/(-0,5) = -40; 10/(-0,5) = -20 e 30/1,5 = 20 Sai o de menor valor, não negativo: 20 Sai a variável da linha 3 (a3) Linha pivô: linha 3 Elemento pivô: 1,5 Dividindo a linha pivô por 1,5, temos: Pesquisa Operacional I 65 Nova linha pivô: Linha pivô 0 0,5 -0,5 0 0 1,5 -1,5 1 30 Dividido por 1,5 0 0,33 -0,33 0 0 1 -1 0,67 20 Cálculo da nova linha de Z (coeficiente = -0,5) Nova linha pivô 0 0,33 -0,33 0 0 1 -1 0,67 20 X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 (+) linha Z 1 -0,5 -0,5 0 0 -0,5 0,5 0 10 Nova linha Z 1 -0,333 -0,667 0 0 0 0 0,333 20 Cálculo da nova linha L1 (coeficiente = -0,5) Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 (+) linha 1 0 2,5 1,5 0 1 -0,5 0,5 0 20 Nova linha 1 0 2,667 1,333 0 1 0 0 0,333 30 Cálculo da nova linha L2 (coeficiente = -0,5) Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 X (0,5) 0 0,167 -0,17 0 0 0,5 -0,5 0,33 10 (+) linha 2 0 0,5 0,5 1 0 -0,5 0,5 0 10 Nova linha 2 0 0,667 0,333 1 0 0 0 0,333 20 Cálculo da nova linha W (coeficiente = -1,5) Nova linha pivô 0 0,333 -0,33 0 0 1 -1 0,67 20 X (1,5) 0 0,5 -0,5 0 0 1,5 -1,5 1 30 (+) linha w -1 -0,5 0,5 0 0 -1,5 2,5 0 -30 Nova linha w -1 0 0 0 0 0 1 1 0 Pesquisa Operacional I 66 Nova tabela: Z X1 X2 X3 F1 F2 a2 a3 b Tabela 3 1 -0,333 -0,667 0 0 0 0 0,333 20 L1 F1 0 2,667 1,333 0 1 0 0 0,333 30 L2 X3 0 0,667 0,333 1 0 0 0 0,333 20 L3 F2 0 0,333 -0,333 0 0 1 -1 0,667 20 -w -1 0 0 0 0 0 1 1 0 Nova solução: Variáveis Não básicas: X1 = 0; X2 = 0; a2 = 0 e a3 = 0 Variáveis básicas: X3 = 20; F1 = 30 e F3 = 20 Valor de W: W = 0 O problema apresenta agora uma solução básica formada pelas variáveis originais. As variáveis auxiliares e a função objetivo auxiliar são nulas. Devemos abandoná-las e continuar a solução do problema com a função objetivo original em Z. A tabela será, portanto: Z X1 X2 X3 F1 F2 b 1 -0,333 -0,667 0 0 0 20 L1 F1 0 2,667 1,333 0 1 0 30 L2 X3 0 0,667 0,333 1 0 0 20 L3 F2 0 0,333 -0,333 0 0 1 20 Nesse quadro original em Z será aplicado o método Simplex para a solução ótima de Z. Após aplicar o método Simplex chegaremos a seguinte solução: Solução: Variáveis Não básicas: X1 = 0 e F1 = 0 Variáveis básicas: X2 = 22,5; X3 = 12,5 e F2 = 27,5 Valor de Z: Z = 35 Pesquisa Operacional I 67 Caso a função auxiliar W represente solução ótima e valor não nulo, as variáveis auxiliares não serão todas nulas e o modelo original não representará então uma solução básica. Nesse caso, o problema não tem solução. Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em contato com seu tutor virtual através do ambiente virtual de aprendizagem e consulte sempre a biblioteca do seu polo. É hora de se avaliar Lembre-se de realizar as atividades desta unidade de estudo. Elas irão ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de ensino-aprendizagem. Pesquisa Operacional I 68 Exercícios – Unidade 3 1. Considere o seguinte enunciado: 2121 1210);( xxxxRimizarMax Sujeito a 27032 100 21 21 xx xx 0, 21 xx Assinale a alternativa que apresente o elemento pivô da primeira tabela do método Simplex. a) 1 b) 2 c) 3 d) 5 e) 10 2. Considere o seguinte enunciado: 321321 432);;( xxxxxxLimizarMax Sujeito a 80 2102 100 1 21 321 x xx xxx 0,, 321 xxx Pesquisa Operacional I 69 Assinale a alternativa que apresente o elemento pivô da primeira tabela do método Simplex. a) 1 b) 2 c) 3 d) 5 e) 10 Considere o seguinte enunciado para as questões 3, 4 e 5: 321321 422,0);;( xxxxxxZimizarMax Sujeito a 15 503 202 321 31 21 xxx xx xx 0,, 321 xxx 3. Assinale a alternativa que apresente o elemento pivô da primeira tabela do método Simplex. a) 1 b) 2 c) 3 d) 5 e) 10 4. Assinale a alternativa que apresente as variáveis básicas e não básicas da segunda tabela do método Simplex. a) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =20; F2 = 50 e F3 = 15 Pesquisa Operacional I 70 b) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =20; X3 = 50 e F3 = 15 c) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =20; F2 = -15 e F3 = 50 d) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =20; X3 = 50 e F3 = 65 e) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =0; F2 = 50 e F3 = -15 5. O valor ótimo de Z é igual a: a) 200 b) 220 c) 240 d) 260 e) 280 Considere o seguinte enunciado para as questões 6, 7 e 8: 321321 435);;( xxxxxxZimizarMax Sujeito a 1505 2802 600 32 31 321 xx xx xxx 0,, 321 xxx 6. Assinale a alternativa que apresente o elemento pivô da primeira tabela do método Simplex. a) 1 b) 2 c) 3 d) 5 e) 10 Pesquisa Operacional I 71 7. Assinale a alternativa que apresente as variáveis básicas e não básicas da segunda tabela do método Simplex. a) Básicas: X1 = 0 e X3 = 0; não básicas: F1 = 500, F2 = 50 e X2 = 280 b) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =280; X3 = 50 c) Básicas: X1 = 0; X2 = 0 e X3 = 0; não básicas: F1 =500; F2 = -30 d) Básicas: X1 = 0; X2 = 0 e F2 = 0; não básicas: F1 =500 e X3 = 50 e) Básicas: X1 = 0 e X3 = 0; não básicas: F1 = 570, F2 = 280 e X2 = 30 8. O valor ótimo de Z é igual a: a) 90 b) 610 c) 862 d) 915 e) 1120 Considere o seguinte enunciado para as questões 9 e 10: 321321 23);;( xxxxxxZMinimizar Sujeito a 1 623 633 21 21 321 xx xx xxx 0,, 321 xxx Pesquisa Operacional I 72 9) Encontre as variáveis básicas e não básicas quando o valor da função objetivo auxiliar é igual a zero (W = 0). 10) Encontre o valor de Z que minimiza a função objetivo e os respectivos valores de X1, X2 e X3. Pesquisa Operacional I 73 4 Dualidade Pesquisa Operacional I 74 Nesta unidade, será apresentada forma de solução ou possíveis soluções de um P.P.L. usando a dualidade. Objetivos da unidade: Mostrar ao leitor que a quantidade de cálculo as necessária para resolver um modelo linear pelo Simplex pode ser reduzida, substituindo o modelo chamado primal pelo modelo dual. Plano da unidade: Introdução. Como obter? Interpretação. Tabela de conversão Dual-Primal. Exemplos. Propriedades importantes Primal-Dual. Bons estudos! Pesquisa Operacional I 75 Introdução. Como obter? Interpretação. O modelo inicial de um problema de programação linear, chamado de primal, pode ser substituído por um outro modelo que chamamos de Dual. Isso será possível em determinadas situações onde a quantidade de cálculos necessária para solucionar um modelo linear pelo método Simplex pode ser reduzida. Considere o modelo de programações linear que tem a função objetivo de maximização, as restrições são do tipo e as variáveis são não negativas. Chamamos esse modelo de primal ao qual podemos associar outro modelo que chamamos de dual, que será construído da seguinte maneira: 1. Variáveis de decisão do dual: a cada restrição do primal, faremoscorresponder uma variável yi; 2. Objetivo: a função objetivo será de minimização. Cada uma das parcelas será o produto da variável yi pelo termo da direita da restrição correspondente; 3. Restrições: Cada variável de decisão primal gera uma restrição no dual. Termos da esquerda: Cada termo é o produto da variável dual yi pelo coeficiente respectivo da variável de decisão primal. Sinal: Sinal do tipo . Termo da direita: é o coeficiente da variável primal na função objetivo. Exemplo: Primal: 321321 32);;( xxxxxxZimizarMax Variáveis duais Sujeito a 30 2062 10243 321 321 321 xxx xxx xxx 0,, 321 xxx y1 y2 y3 Pesquisa Operacional I 76 Dual: 321321 302010);;( yyyyyyDMinimizar Sujeito a 12 364 223 321 321 321 yyy yyy yyy 0,, 321 yyy Tabela de conversão Dual-Primal. Exemplos. Consideremos agora o seguinte modelo primal: a) Função objetivo de minimização; b) Restrições do tipo ; c) Variáveis todas não negativas. Seu dual será então: a) Função objetivo de maximização; b) Restrições do tipo ; c) Variáveis todas não negativas. Exemplo: Votemos ao exemplo anterior e tomemos o seu dual como o primal de agora. Coeficientes de x1 Coeficientes de x2 Coeficientes de x3 (Termos da direita) Pesquisa Operacional I 77 Primal: 321321 302010);;( xxxxxxZMinimizar Sujeito a 12 364 223 321 321 321 xxx xxx xxx 0,, 321 xxx Dual: 321321 32);;( yyyyyyDimizarMax Sujeito a 30 2062 10243 321 321 321 yyy yyy yyy 0,, 321 yyy Deste exemplo, podemos concluir: a) Que o dual de um dual é o modelo primal; b) Se uma restrição primal é do tipo =, a variável dual correspondente será sem restrição de sinal; c) Se uma variável primal for sem restrição de sinal, as restrições do dual correspondente será do tipo =. Exemplo: Primal: 321321 32);;( xxxxxxZimizarMax Sujeito a 2042 10 321 21 xxx xx 0,, 321 xxx Variáveis duais y1 y2 y3 (Termos da direita) Coeficientes de x1 Coeficientes de x2 Coeficientes de x3 y1 y2 Pesquisa Operacional I 78 Dual: 2121 2010);( yyyyDMinimizar Sujeito a 1 34 22 2 21 21 y yy yy 21 ,0 yy Livre Podemos resumir essas regras na seguinte tabela: Problema de Maximização Problema de Minimização Restrições Variáveis ≥ ⇔ ≤ 0 ≤ ⇔ ≥ 0 = ⇔ Irrestrita Variáveis Restrições ≥ 0 ⇔ ≥ ≤ 0 ⇔ ≤ Irrestrita ⇔ = Observe que a tabela não utiliza a notação primal e dual. O que importa aqui é o sentido da otimização (se o primal for de maximização, então o dual será de minimização e vice-versa). É importante observar que ser irrestrita é sinônimo de ser livre. (Termos da direita) Pesquisa Operacional I 79 Propriedades importantes Primal-Dual. A. A cada solução viável básica primal não ótima corresponde uma solução básica inviável dual; B. A solução ótima primal corresponde à solução ótima dual com Z=D; C. O coeficiente da variável de decisão na função objetivo primal é o valor da variável de folga correspondente na solução dual – (coeficiente de xi = valor de yFi); D. O coeficiente da variável de folga da função objetivo primal é o valor da variável de decisão correspondente na solução dual – (coeficiente de xFi= yi); Como o primal é dual do próprio dual, vale o raciocínio no sentido dual primal. – (coeficiente yi = valor de xFi) e (coeficiente yFi = valor de xi). Exemplo: Primal: 321321 32);;( xxxxxxZimizarMax Sujeito a 93 1242 10 321 321 321 xxx xxx xxx 0,, 321 xxx Dual: 321321 91210);;( yyyyyyDMinimizar Sujeito a 34 23 12 321 321 321 yyy yyy yyy Pesquisa Operacional I 80 0,, 321 yyy Colocando as variáveis de folga no primal e no dual, temos: Primal: 321321 32);;( xxxxxxZimizarMax Sujeito a 93 1242 10 3321 2321 1321 Fxxx Fxxx Fxxx Transpondo para o quadro do simplex: Primal Z X1 X2 X3 F1 F2 F3 b Tabela 1 1 -1 -2 -3 0 0 0 0 L1 F1 0 1 1 1 1 0 0 10 L2 F2 0 2 1 4 0 1 0 12 L3 F3 0 1 3 -1 0 0 1 9 Solução: Variáveis Não básicas: F1 = 10; F2 = 10 e F3 = 9 Variáveis básicas: X1 = 0; X2 = 0 e X3 = 0 Valor de Z: Z = 0 Dual: 321321 91210);;( yyyyyyDMinimizar Como já vimos minimizar D é igual a maximizar –D, então: 091210 91210);;)(( 321 321321 yyyD yyyyyyDMaximizar Pesquisa Operacional I 81 Sujeito a 34 23 12 3321 2321 1321 Fyyy Fyyy Fyyy Transpondo para o quadro do simplex: Dual D Y1 Y2 Y3 F1 F2 F3 c Tabela 1 -1 10 12 9 0 0 0 0 L1 F1 0 1 2 1 -1 0 0 1 L2 F2 0 1 1 3 0 -1 0 2 L3 F3 0 1 4 -1 0 0 -1 3 Solução: Variáveis Não básicas: F1 = -1; F2 = -2 e F3 = -3 Variáveis básicas: Y1 = 0; Y2 = 0 e Y3 = 0 Valor de D: D = 0 Observe a correspondência entre o primal e o dual: Coeficiente de x1 = -1 => Valor de F1 (de y) = -1 Coeficiente de x2 = -2 => Valor de F2 (de y) = -2 Coeficiente de x3 = -3 => Valor de F3 (de y) = -3 Coeficiente de F1 (de x) = 0 => Valor de y1 = 0 Coeficiente de F2 (de x) = 0 => Valor de y2 = 0 Coeficiente de F3 (de x) = 0 => Valor de y3 = 0 Valor de x1 = 0 => coeficiente de F1 (de y) = 0 Valor de x2 = 0 => coeficiente de F2 (de y) = 0 Valor de x3 = 0 => coeficiente de F3 (de y) = 0 Valor de F1 = 10 (de x) => coeficiente de y1 = 10 Pesquisa Operacional I 82 Valor de F2 = 12 (de x) => coeficiente de y2 = 12 Valor de F3 = 9 (de x) => coeficiente de y3 = 9 Valor de Z = 0 => Valor de D = 0 Continuando a solução do primal, com a entrada da variável x3 (pois seu coeficiente -3) e a saída da variável F2 (12/4=3), após o pivotamento, será: Primal Z X1 X2 X3 F1 F2 F3 b Tabela 2 1 0,5 -1,25 0 0 0,75 0 9 L1 F1 0 0,5 0,75 0 1 -0,25 0 7 L2 X3 0 0,5 0,25 1 0 0,25 0 3 L3 F3 0 1,5 3,25 0 0 0,25 1 12 Solução: Variáveis Não básicas: F1 = 7; F3 = 12 e X3 = 3 Variáveis básicas: X1 = 0; X2 = 0 e F2 = 0 Valor de Z: Z = 9 Usando a correspondência descrita acima, vamos montar o quadro dual correspondente (considerando a Tabela 2 do Primal e sua solução): Coeficientes xi (linha de Z) => valores de yfi (coluna de c) Coeficientes xfi (linha de Z) => valores de yi (coluna de c) Valores de xi (solução acima) => coeficientes yfi (linha de D) Valores de xfi (solução acima) => coeficientes yi (linha de D) Temos então o quadro abaixo: Dual D Y1 Y2 Y3 F1 F2 F3 c Tabela 2 -1 7 0 12 0 0 3 -9 L1 F1 0 1 0 0,5 L2 F2 0 0 1 -1,25 L3 Y2 1 0 0 0,75 Solução: Pesquisa Operacional I 83 Variáveis Não básicas: F1 = 0,5; F2 = -1,25 e Y2 = 0,75 Variáveis básicas: Y1 = 0; Y3 = 0 e F3 = 0 Valor de D: D = 9 Vamos ao terceiro quadro primal: Primal Z X1 X2 X3 F1 F2 F3 b Tabela 3 1 1,077 0 0 0 0,846 0,385 13,615 L1 F1 0 0,154 0 0 1 -0,308 -0,231 4,231 L2 X3 0 0,385 0 1 0 0,231 -0,077 2,077 L3 X2 0 0,461 1 0 0 0,077 0,308 3,692 Solução: Variáveis Não básicas: X2 = 3,692; X3 = 2,077 e F1 = 4,231 Variáveis básicas: X1 = 0; F2 = 0 e F3 = 0 Valor de Z: Z = 13,615 Usando a correspondência descrita, podemos montar o terceiro quadro dual: Dual D Y1 Y2 Y3 F1 F2 F3 c Tabela 3 -1 4,321 0 0 0 3,962 2,077 -13,615 L1 F1 0 0 0 1 0 1,077 L2 Y2 0 1 0 0 -1 0,846 L3 Y3 0 0 1 0 0 0,385 Solução: Variáveis Não básicas: Y2 = 0,846; Y3 = 0,385 e F1 = 1,077 Variáveis básicas: Y1 = 0; F2 = 0 e F3 = 0 Valor de D: D = 13,615 Pesquisa Operacional I 84 Conclusão: as soluções matemáticas do primal e do dual são pontos ótimos de mesmo valor (ou seja, Z=D). A escolha entre um e outro se dará levando em conta o menor esforço computacional, que depende do número de restrições, das variáveis artificiais
Compartilhar