Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional Email:universo.po.2.2014@gmail.com Contatos 21-987641703 21-23323101 Programa Introdução a programação linear As Origens da Pesquisa Operacional A Natureza da Pesquisa Operacional O Impacto da Pesquisa Operacional Visão Geral da Abordagem de Modelagem da Pesquisa Operacional Definição do Problema e Coleta de Dados Formulando um Modelo Matemático Derivando Soluções a Partir do Modelo Testando o Modelo Preparando-se para Aplicar o Modelo Implementação Introdução à Programação Linear Exemplo de Protótipo O Modelo de Programação Linear Hipóteses da Programação Linear Exemplos Adicionais Alguns Estudos de Caso Clássicos Formulando e Solucionando Modelos de Programação Linear em uma Planilha Formulando Modelos de Programação Linear de Grandes Dimensões Pesquisa Operacional Introdução à Programação Linear Introdução a Programação Linear O desenvolvimento da programação linear tem sido classificado entre os mais importantes avanços científicos dos meados do século XX. Seu impacto desde 1950 tem sido extraordinário. Hoje em dia é uma ferramenta-padrão que poupou muitos milhares ou milhões de dólares para muitas empresas ou até mesmo negócios de tamanho moderado em diversos países industrializados ao redor do mundo; Qual é a natureza dessa admirável ferramenta e a que tipos de problemas ela se destina? Introdução a Programação Linear Envolve o problema genérico de alocar da melhor forma possível (isto é, ótima) recursos limitados para atividades que competem entre si. Mais precisamente, esse problema envolve selecionar o nível de certas atividades que competem por recursos escassos que são necessários para realizar essas atividades. A escolha do nível de atividades determina, então, quanto de cada recurso será consumido por atividade. Introdução a Programação Linear A programação linear usa um modelo matemático para descrever o problema em questão. O adjetivo linear significa que todas as funções matemáticas nesse modelo são necessariamente funções lineares. A palavra programação, nesse caso, não se refere à programação de computador; ela é, essencialmente, um sinônimo para planejamento. Portanto, a programação linear envolve o planejamento de atividades para obter um resultado ótimo, isto é, um resultado que atinja o melhor objetivo especificado (de acordo com o modelo matemático) entre todas as alternativas viáveis. Introdução a Programação Linear Exemplo A WYNDOR GLASS CO. fabrica produtos de vidro de alta qualidade, entre os quais janelas e portas de vidro. A empresa possui três fábricas industriais. As esquadrias de alumínio e ferragens são feitas na Fábrica 1, as esquadrias de madeira são produzidas na Fábrica 2 e, finalmente, a Fábrica 3 produz o vidro e monta os produtos. Em consequência da queda nos ganhos, a direção decidiu modernizar a linha de produtos da empresa. Produtos não rentáveis estão sendo descontinuados, liberando capacidade produtiva para o lançamento de dois novos produtos com grande potencial de vendas Introdução a Programação Linear Produto 1: Uma porta de vidro de 2,5 m com esquadria de alumínio Produto 2: Uma janela duplamente adornada com esquadrias de madeira de 1,20 X 1,80 m • O produto 1 requer parte da capacidade produtiva das Fábricas 1 e 3, mas nenhuma da Fábrica 2. • O produto 2 precisa apenas das Fábricas 2 e 3. A divisão de marketing concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas fábricas. Entretanto, pelo fato de ambos os produtos poderem estar competindo pela mesma capacidade produtiva na Fábrica 3, não está claro qual mix dos dois produtos seria o mais lucrativo. Portanto, foi constituída uma equipe de PO para estudar essa questão. Introdução a Programação Linear A equipe de PO começou promovendo discussões com a alta direção para identificar os objetivos da diretoria para tal estudo. Essas discussões levaram à seguinte definição do problema: Determinar quais devem ser as taxas de produção para ambos os produtos de modo a maximizar o lucro total, sujeito às restrições impostas pelas capacidades produtivas limitadas disponíveis nas três fábricas. (cada produto será fabricado em lotes de 20, de forma que a taxa de produção é definida como o número de lotes produzidos por semana.) É permitida qualquer combinação de taxas de produção que satisfaça essas restrições, inclusive não produzir nada de um produto e o máximo possível do outro. Introdução a Programação Linear A equipe de PO também identificou os dados que precisavam ser coletados: 1. - Número de horas de tempo de produção disponível por semana em cada fábrica para esses novos produtos. (A maior parte do tempo nessas fábricas já está comprometida com os produtos atuais, de modo que a capacidade disponível para os novos produtos é bastante limitada.) 2. - Número de horas de tempo de produção usado em cada fábrica para cada lote produzido de cada novo produto. 3. Lucro por lote produzido de cada novo produto. Foi escolhido o lucro por lote produzido como uma medida apropriada após a equipe de PO ter concluído que o incremento de lucro de cada lote adicional produzido ser aproximadamente constante independentemente do número total de lotes produzidos. Pelo fato de nenhum custo adicional incorrer para o início da produção e a comercialização de tais produtos, o lucro total de cada um deles é aproximadamente esse lucro por lote vezes o número de lotes produzidos. Introdução a Programação Linear A equipe de PO reconheceu imediatamente que se tratava de um problema de programação linear do clássico tipo mix de produtos e então a equipe empreendeu a formulação do modelo matemático correspondente. Introdução a Programação Linear Formulação como Problema de Programação Linear Para formular o modelo matemático (programação linear) para esse problema, temos: x 1 =número de lotes do produto 1 produzido semanalmente x2 = número de lotes do produto 2 produzido semanalmente Z = lucro total por semana (em milhares de dólares) obtido pela produção desses dois produtos Portanto, x1 e x2 são as variáveis de decisão para o modelo. Usando-se a linha inferior da Tabela acima, se obtém: Z = 3x1 + 5x2 Função Objetivo O objetivo é escolher os valores de x1 e x2 de forma a maximizar Z = 3x1 + 5x2, sujeito às restrições impostas em seus valores por limitações de capacidade de produção disponível nas três fábricas. Introdução a Programação Linear A Tabela 1 indica que cada lote de produto 1 fabricado por semana usa uma hora de tempo de produção por semana na Fábrica 1, ao passo que estão disponíveis somente quatro horas semanais. Essa restrição é expressa matematicamente pela desigualdade x1 ≤ 4. Similarmente, a Fábrica 2 impõe a restrição 2x2 ≤ 2. O número de horas de produção usado semanalmente na Fábrica 3 escolhendo-se x1 e x2 como as taxas de produção dos novos produtos seria 3x1 + 2x2. Portanto, a declaração matemática da restrição da Fábrica 3 é 3x1 + 2x2 ≤ 18. Finalmente, já que as taxas de produção não podem ser negativas, é necessário restringir as variáveis de decisão para serem não negativas, por tanto temos: x1 ≥ O e x2 ≥ O. Introdução a Programação Linear Em suma, na linguagem matemática da programação linear, o problema é escolher os valores de x1 e x2 de forma a: Maximizar Z = 3x1 + 5x2 Sujeito às restrições x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 Introdução a Programação Linear Esse pequeno problema possui apenas duas variáveisde decisão e, portanto, somente duas dimensões, de forma que um procedimento gráfico pode ser usado para resolvê-lo. Este procedimento envolve construir um gráfico bidimensional tendo x1 e x2 como eixos. O Primeiro passo é identificar os valores de (x1. x2) que são permitidos pelas restrições. Isso é feito desenhando-se cada reta que limita o intervalo de valores permissíveis para uma restrição. Para começar, observe que as restrições de não negatividade x1 ≥ 0 e x2 ≥ 0: requerem que (x1. x2) estejam no lado positivo dos eixos (inclusive, na realidade, sobre ambos os eixos), isto é, no primeiro quadrante. A seguir, observe que a restrição x1≤ 4 significa que (x1. x2) não pode estar à direita da reta x1 = 4. Esses resultados são mostrados na Figura 1 em que a área sombreada contém os únicos valores de (x1. x2) que ainda são permitidos. Introdução a Programação Linear Figura 1 Introdução a Programação Linear De modo semelhante, a restrição 2x2 ≤ 12(ou, equivalentemente, x2 ≤ 6 implica que a reta 2x2 ≤ 12 deve ser adicionada ao contorno da região de soluções viáveis. A restrição final, 3x1 + 2x2 ≤18, requer traçar os pontos (x1. x2) de maneira que 3x1 + 2x2 = 18 (outra reta) complete o contorno. (Observe que pontos como 3x1 +2x2 ≤18 são aqueles que estão abaixo ou sobre a reta 3x1 + 2x2 = 18, de forma que essa é a reta limitante acima da qual os pontos não satisfazem a desigualdade.) Introdução a Programação Linear A região resultante de valores viáveis de (x1.x2 ), chamada região de soluções viáveis, é mostrada na Figura 2 seguinte: O passo final é escolher o ponto nessa região de soluções viáveis que maximiza o valor de Z = 3x1 + 5x2 Introdução a Programação Linear O passo final é escolher o ponto nessa região de soluções viáveis que maximiza o valor de Z = 3x1 + 5x2 Para descobrir como realizar esse passo de forma eficiente, comece por tentativa e erro. Tente, por exemplo, Z = 10 = 3x1 + 5x2 para ver se há na região de soluções viáveis quaisquer valores de (x1, x2) que levem uma função Z a um valor 10. Desenhando-se a reta 3x1 + 5x2 = 10 (ver a Figura 3), podemos observar que há muitos pontos sobre essa reta que se encontram dentro da região. Tendo ganhado alguma visão tentando esse valor escolhido arbitrariamente de Z = 10, você deve tentar seguir um valor arbitrário de Z maior, digamos, Z = 20 = 3x1 + 5x2 . Novamente, a Figura 3 revela que um segmento da reta 3x1 + 5x2 = 20 se encontra dentro da região, de forma que o valor máximo permissível de Z tem de ser pelo menos 20. Introdução a Programação Linear O passo final é escolher o ponto nessa região de soluções viáveis que maximiza o valor de Z = 3x1 + 5x2 Agora, observe na Figura 3 que as duas retas que acabaram de ser construídas são paralelas. Não se trata de uma coincidência, visto que qualquer reta construída desse modo tem a forma Z = 3x1 + 5x2 para o valor escolhido de Z, implicando 5x2 = - 3x1 + Z ou, equivalentemente, a: X2=- 3 5 x1 + 1 5 Z Figura 3 Introdução a Programação Linear Esta última equação, chamada forma de interseção da inclinação da função objetivo, demonstra que a inclinação da reta é − 3 5 uma vez que a cada incremento unitário em x1 corresponde a um incremento de − 3 5 em x2, ao passo que a interseção da reta com o eixo x2 é 1 5 Z, O fato de a inclinação ser fixada em − 3 5 significa que todas as retas construídas dessa maneira serão paralelas. Repetindo, comparando-se as retas 10 = 3x1 + 5x2 e 20 = 3x1 + 5x2 da Figura 3, notamos que a reta que dá um valor maior de Z (Z = 20) se encontra bem acima e distante da origem quando comparada com a outra reta (Z = 10). Esse fato também está implícito pela forma de interseção da inclinação da função objetivo que indica que a interseção com o eixo x1 ( 1 5 𝑍) aumenta quando o valor escolhido para Z se eleva. Introdução a Programação Linear Essas observações fazem que nosso procedimento de tentativa e erro para construção de retas na Figura 3 envolva mais do que desenhar uma família de retas paralelas contendo pelo menos um ponto na região de soluções viáveis e selecionar a reta que corresponde ao maior valor de Z. A Figura 3 mostra que essa reta passa pelo ponto (2, 6) indicando que a solução ótima é x1 = 2 e x2 = 6. A equação dessa reta é 3x1 + 5x2 = 3(2) + 5(6) = 36 = Z, indicando que o valor ótimo de Zé Z = 36. O ponto (2, 6) se encontra na interseção das retas 2x2 = 12 e 3x1 + 2x2 = 18, conforme mostrado na Figura 3, de forma que esse ponto pode ser calculado algebricamente como a solução simultânea dessas duas equações. Introdução a Programação Linear Após termos visto o procedimento de tentativa e erro para descobrir o ponto ótimo (2,6), podemos agora aperfeiçoar esse método para outros problemas. Em vez de desenhar várias retas paralelas, é suficiente formar uma única reta com uma régua para estabelecer a inclinação. Depois, desloque a régua com inclinação fixa através da região de soluções viáveis na direção em que Z cresce. (Quando o objetivo for o de minimizar Z movimente a régua na direção em que Z decresce.) Pare de deslocar a Introdução a Programação Linear Após termos visto o procedimento de tentativa e erro para descobrir o ponto ótimo (2,6), podemos agora aperfeiçoar esse método para outros problemas. Em vez de desenhar várias retas paralelas, é suficiente formar uma única reta com uma régua para estabelecer a inclinação. Depois, desloque a régua com inclinação fixa através da região de soluções viáveis na direção em que Z cresce. (Quando o objetivo for o de minimizar Z movimente a régua na direção em que Z decresce.) Pare de deslocar a régua até o último instante em que ela ainda passa por um ponto dentro dessa região. Esse ponto é a desejada solução ótima. Este procedimento é normalmente conhecido como método gráfico para programação linear. Pode ser usado para solucionar qualquer problema de programação linear com duas variáveis de decisão. Com considerável dificuldade, é possível estender o método para três variáveis de decisão, mas não mais que três. (O próximo capítulo se concentrará no método simplex para solucionar problemas maiores) Modelos de Programação Linear A programação linear é bastante versátil para ser completamente caracterizada em um único exemplo. Serão discutidas as características gerais dos problemas de programação linear, inclusive as diversas formas legítimas do modelo matemático para programação linear. Certos símbolos são comumente usados para representar os diversos componentes de um modelo de programação linear. Esses símbolos são apresentados, a seguir, juntamente com suas interpretações para o problema geral de alocar recursos a atividades. Z = valor da medida de desempenho global xj = nível de atividade j (para j = 1, 2, ... , n) cj = incremento em Z que resultaria de cada incremento unitário no nível de atividade j bi = quantidade do recurso i que se encontra disponível para alocação em atividades (para i= 1, 2, ... , m) aiJ = quantidade do recurso i consumido por unidade de atividade j Introdução a Programação Linear O modelo formula o problema em termos de tomar decisões em relação aos níveis de atividade, de forma que x1. X2. ... , Xn são denominadas variáveis de decisão. Conforme sintetizado na Tabela A, os valores de cj, bi e aiJ (parai= 1, 2, ... , m e j = 1, 2, ... , n) são as constantes de entrada para o modelo. cj, bi e aiJ também são conhecidos como parâmetros do modelo. Introdução a Programação Linear Uma Forma-padrão de Modelo Continuando no problema da WyndorGlass Co., agora temos condições de formular o modelo matemático para esse problema genérico de alocação de recursos para atividades. Em particular, esse modelo visa selecionar os valores para x1. x2, ... , xm de forma a: Maximizar Z = x1c1 +x2c2 ........xncn Sujeito as restrições a11x1 +a12x2 +.......+a1nxn ≤b1 a21x1 +a22x2 +.......+a2nxn ≤b2 am1x1 +am2x2 +.......+amnxn ≤bm E x1 ≥0 ; x2 ≥0....... xn ≥0 Introdução a Programação Linear Chama-se a isto forma-padrão, 1 para o problema de programação linear. Qualquer situação cuja formulação matemática se encaixe nesse modelo é um problema de programação linear. Observe que o modelo para a Wyndor Glass Co. atende à nossa forma- padrão com m = 3 e n = 2. . A terminologia comum para o modelo de programação linear pode agora ser sintetizada da seguinte forma. Introdução a Programação Linear A função que está sendo maximizada, c1x1 + c2x2 + ... + cmxm é chamada função objetivo. As limitações são normalmente denominadas restrições. As primeiras m restrições (aquelas com uma função de todas as variáveis a11x1 +a12x2 +.......+a1nxn do lado esquerdo) são algumas vezes ditas restrições funcionais (ou restrições estruturais). De forma similar x1 ≥0 ; x2 ≥0....... xn ≥0 , as restrições são conhecidas como restrições de não-negatividade (ou condições não-negativas). Introdução a Programação Linear Outras Formas Agora, temos de nos apressar para acrescentar que, na verdade, o modelo precedente não se encaixa na forma natural de alguns problemas de programação linear. As demais formas legítimas são as seguintes: Minimizar em vez de maximizar a função objetivo; Minimizar : Z = x1c1 +x2c2 ........xncn Algumas restrições funcionais com uma desigualdade do tipo maior do que ou igual a: para alguns valores de i. a11x1 +a12x2 +.......+a1nxn ≥b1 a21x1 +a22x2 +.......+a2nxn =b2 Eliminar as restrições não-negativas para algumas das variáveis de decisão: Introdução a Programação Linear Terminologia para Soluções de Modelos Você deve estar acostumado a ver o termo solução com o significado de resposta final para um problema, porém, a convenção em programação linear (e suas extensões) é bem diferente. Aqui, qualquer especificação de valores para as variáveis de decisão (x1, x2, ... , xn) é chamada solução, independentemente de ela ser desejável ou até mesmo ser uma opção admissível. Diferentes tipos de soluções são então identificados usando-se um adjetivo apropriado. Uma solução viável é aquela para a qual todas as restrições são satisfeitas. Uma solução inviável é aquela para a qual pelo menos uma das restrições é violada. No exemplo, os pontos (2, 3) e (4, 1) na Figura 4 são soluções viáveis ao passo que os pontos (-1, 3) e (4, 4) são soluções inviáveis. Introdução a Programação Linear Figura 4 A região de soluções viáveis é o conjunto de todas as soluções viáveis. A região de soluções viáveis no exemplo é toda a área preenchida na Figura 4. É possível que não haja nenhuma solução viável. Isso poderia ter acontecido no exemplo caso os novos produtos tivessem exigido um lucro líquido de pelo menos US$ 50.000 por semana para justificar a descontinuação de parte da linha de produtos atual. Introdução a Programação Linear A restrição correspondente, 3x1 + 5x2 ≥ 50, iria eliminar toda a região de soluções viáveis, de forma que nenhum mix de novos produtos seria superior ao status quo. Esse caso é ilustrado na Figura 5. Figura 5 Introdução a Programação Linear Dado que existem soluções viáveis, o objetivo da programação linear é encontrar a melhor solução viável conforme medida pelo valor da função objetivo no modelo. Uma solução ótima é uma solução viável que tem o valor mais favorável da função objetivo. Introdução a Programação Linear O valor mais favorável é o maior valor se a função objetivo tiver de ser maximizada, ao passo que será o menor valor caso ela deva ser minimizada. A maior parte dos problemas terá apenas uma solução ótima. Entretanto, é possível ter mais de uma. Isso ocorreria no exemplo caso o lucro por lote fabricado do produto 2 fosse alterado para US$ 2.000. Isso altera a função objetivo para Z = 3x1 + 2x2 de forma que todos os pontos no segmento de reta conectando os pontos (2, 6) e ( 4, 3) seriam ótimos. Esse caso é ilustrado na Figura 3.5. Como acontece nesse caso, qualquer problema tendo soluções ótimas múltiplas terá um número infinito delas, cada uma com o mesmo valor ótimo da função objetivo. Introdução a Programação Linear Introdução a Programação Linear Outra possibilidade é que um problema não tenha nenhuma solução ótima. Isso acontece apenas se (l) ela não tiver nenhuma solução viável ou (2) as restrições não impedirem que se aumente indefinidamente o valor da função objetivo (Z) na direção favorável (positiva ou negativa). O último caso é conhecido como tendo um Z ilimitado ou uma função objetivo ilimitada. Para fins ilustrativos, esse caso aconteceria se as duas últimas restrições funcionais fossem eliminadas por engano no exemplo, conforme ilustrado na Figura. Introduzimos, a seguir, um tipo especial de solução viável que desempenha papel fundamental quando o método simplex procura uma solução ótima. Introdução a Programação Linear Introdução a Programação Linear Uma solução FPE (viável em ponto extremo) é a aquela que está em um vértice da região de soluções viáveis. Hipóteses da Programação Linear Todas as hipóteses de programação linear estão, na realidade, implícitas na formulação do modelo já apresentada. Em particular, do ponto de vista matemático, as hipóteses simplesmente são que o modelo deve ter uma função objetivo linear sujeita a restrições lineares. Entretanto, do ponto de vista de modelagem, essas propriedades matemáticas de um modelo de programação linear implicam que certas hipóteses têm de ser satisfeitas em relação às atividades e aos dados do problema que está sendo modelado, incluindo hipóteses sobre o efeito de se variar os níveis de atividades. É bom destacá-las para que você possa avaliar mais facilmente quão bem a programação linear se aplica a qualquer problema dado. Além disso, ainda precisamos ver por que a equipe de PO da Wyndor Glass Co. concluiu que uma formulação de programação linear forneceria uma representação satisfatória do problema. Hipóteses da Programação Linear Proporcionalidade A contribuição de cada atividade ao valor da função objetivo Zé proporcional ao nível de atividade xj, conforme representado pelo termo cjxj na função objetivo. De modo semelhante, a contribuição de cada atividade do lado esquerdo de cada restrição funcional é proporcional ao nível de atividade xj, como representado pelo termo aijxj na restrição. Conseqüentemente, essa hipótese descarta qualquer expoente que não seja 1 para qualquer variável em qualquer termo de qualquer função (seja a função objetivo ou a função que se encontra do lado esquerdo na declaração de uma restrição funcional) em um modelo de programação linear Hipóteses da Programação Linear Proporcionalidade Hipóteses da Programação Linear Aditividade Toda função em um modelo de programação linear (seja a função objetivo, seja a função que se encontra do lado esquerdo da declaração de uma restrição funcional) é a soma das contribuições individuais das respectivas atividades. Hipóteses da Programação Linear Divisibilidade As variáveis de decisão em um modelo de programação linear podem assumir quaisquer valores, inclusivevalores não- inteiros, que satisfaçam as restrições funcionais e de não- negatividade. Logo, essas variáveis não são restritas apenas a valores inteiros. Já que cada variável de decisão representa o nível de alguma atividade, supõe-se que as atividades possam ser desenvolvidas em níveis fracionários. Certeza O valor atribuído a cada parâmetro de um modelo de programação linear é assumido como uma constante conhecida. Exercícios Resolva os modelos abaixo pelo método gráfico, encontre as coordenadas dos pontos correspondentes as soluções ótimas por médio dos sistemas de equações das restrições 1.- Achar X1 e X2 de forma a Maximizar Z = 3X1 + 6X2 Restrições 9X1 + 8X2 ≤72 X2 ≤6 -5X1 +4X2 ≤20 X1 e X2 ≥0 2.- Achar X1 e X2 de forma a Maximizar Z = 4X1 + 8X2 Restrições 2X1 + 0,5X2 ≤ 10 4X1 - 2X2 ≥ 0 -X1 + 5X2 ≥ 0 X1 + 2X2 ≤ 10 X1 e X2 ≥0 Trabalhos Trabalho 1 A Universo Pinturas produz tintas para interiores e exteriores com base em 2 matérias primas M1 e M2 , a tabela a continuação apresenta os dados básicos do problema Toneladas de Matéria prima por tonelada de : Tinta para exteriores Tinta para interiores Disponibilidade Máxima Diária (Ton) Matéria Prima M1 6 4 24 Matéria Prima M2 1 2 6 Lucro por Tonelada 5 4 Uma pesquisa de mercado indica que a demanda diária de tintas para interiores não pode ultrapassar a de tintas para exteriores por mais de 1 tonelada . Além disso, a demanda diária de tinta para interiores é de 2 t. A universo tintas quer determinar o mix ótimo de produtos de tintas para interiores e exteriores que maximize o lucro total diário. • Identifique as variáveis de decisão do modelo • Função objetivo • Restrições • Apresente a solução gráfica do problema , identificando soluções viáveis e solução ótima Trabalhos Trabalho 2 A Universo rural usa no mínimo 800 quilos de ração especial por dia para alimentação de gado, esta ração especial é uma mistura de milho e soja com as composições apresentadas na tabela a seguir : Os requisitos nutricionais de ração especial são de no mínimo 30% de proteína e de no máximo 5% de fibra. A universo rural quer determinar a mistura que gera a ração de mínimo custo diário. • Identifique as variáveis de decisão do modelo • Função objetivo • Restrições • Apresente a solução gráfica do problema , identificando soluções viáveis e solução ótima Composição de ração da Universo Rural kilos por kilo de Ração Ração Proteína Fibra Custo por kilo Milho 0,09 0,02 0,3 Soja 0,6 0,06 0,9
Compartilhar