Prévia do material em texto
Método simplex Você vai estudar a programação linear (PL), uma técnica de otimização que aponta as relações entre variáveis como relações lineares, o que simplifica sua modelagem e permite o uso de métodos computacionais eficazes para encontrar a solução ótima, como é o caso do método simplex. Prof. Mauro Rezende Filho 1. Itens iniciais Propósito O estudo do método simplex permite capacitar estudantes e profissionais para resolver problemas complexos de otimização linear de forma eficiente. Estudar o simplex contribui para o desenvolvimento de habilidades analíticas e de resolução de problemas essenciais para diversas áreas, como engenharia, economia, logística e gestão. Objetivos Reconhecer o método simplex para a resolução de problemas de PL. Reconhecer como o método simplex atua na resolução de problemas de PL. Aplicar o método simplex na resolução de problemas de PL. Introdução A modelagem matemática nos permite representar, de forma simplificada, um problema complexo por meio de linguagem matemática. Com isso, conseguimos analisar diferentes cenários de forma mais rápida e barata do que se a situação fosse avaliada na realidade, auxiliando-nos, assim, no processo de tomada de decisão. No contexto da programação linear (PL), que se aplica, por exemplo, no planejamento de redes logísticas, há métodos, como o método gráfico, que se restringem à solução de problemas com apenas duas ou no máximo três variáveis de decisão. Como solucionar, então, problemas mais complexos, com maior número de variáveis de decisão? Esse é o assunto a ser tratado neste conteúdo. A seguir, abordaremos o método simplex para a solução de problemas de PL e aprenderemos a utilizar o solver do Excel para a solução desse tipo de problema. Acompanhe! Conteúdo interativo Acesse a versão digital para assistir ao vídeo. • • • 1. O método simplex para a solução de problemas de PL Conceito e história do método simplex Antes da década de 1940, a otimização linear era um território inexplorado. Resolver problemas que envolviam a alocação ideal de recursos, como a produção de bens ou o planejamento de transporte, era um processo lento e ineficiente. Então, em 1947, concebido por George Dantzig, surgiu o método simplex como um algoritmo revolucionário para desbravar esse universo. Visualizando o método simplex Imagine um poliedro tridimensional, como um cubo ou uma pirâmide. Cada face desse poliedro representa uma solução possível para um problema de programação linear (PL). O método simplex funciona como um alpinista experiente explorando esse terreno. Seu objetivo é encontrar o vértice (um ponto em que as faces encontram-se) que represente a melhor solução, aquela que otimiza determinado critério, como o lucro máximo ou o menor custo. Para percorrer esse terreno de forma estratégica, o método simplex adota um processo iterativo. Em cada iteração, ele avalia a altitude de cada vértice visitado, ou seja, o valor do objetivo (lucro, custo etc.) associado àquela solução. Ele então se move para o vértice adjacente com um valor objetivo melhor, até alcançar o pico mais alto — a solução ótima. Desconstruindo o processo: as etapas do método simplex Para solucionar problemas de PL com o método simplex, seguimos cinco etapas fundamentais. Acompanhe! Formulação do problema Etapa em que se traduz o problema do mundo real para a linguagem matemática da programação linear. Definimos as variáveis que representam as quantidades a serem otimizadas (por exemplo, a produção de diferentes produtos), a função objetivo que queremos maximizar ou minimizar (por exemplo, o lucro total), e as restrições que limitam as variáveis (por exemplo, a disponibilidade de matéria-prima, a mão de obra ou o tempo). Conversão para a forma padrão Etapa em que são realizadas transformações algébricas para garantir que o problema esteja na forma padrão, facilitando a aplicação do algoritmo. Aqui, percebemos que nem todo problema de PL está formulado da maneira ideal para o método simplex. Encontrando uma solução viável Etapa em que o primeiro passo para a escalada rumo à solução ótima é encontrar um ponto de apoio na região viável, ou seja, um conjunto de valores para as variáveis que respeitam todas as restrições do problema. O método simplex dispõe de técnicas específicas para encontrar essa solução inicial viável. Otimização da solução Etapa em que, a partir da solução viável inicial, o método simplex inicia sua jornada iterativa. A cada iteração, ele avalia as variáveis básicas (aquelas que estão no valor limite imposto por alguma restrição) e não básicas (aquelas que ainda possuem folga). Ele identifica oportunidades de substituir variáveis não básicas por básicas, desde que isso melhore o valor da função objetivo. Esse processo continua até que nenhuma melhoria seja possível, indicando que a solução ótima foi alcançada. Análise da solução Chegamos ao pico da montanha! Etapa em que se analisa a solução encontrada para garantir que ela seja realmente ótima. O método simplex fornece indicadores para verificar se a solução é ótima local (a melhor em um entorno específico) ou global (a melhor considerando todas as possibilidades). Em alguns casos, pode ser necessário realizar análises complementares para garantir a otimização global. O método simplex não é apenas uma ferramenta teórica, ele tem um vasto leque de aplicações práticas em diversos setores. Vamos conhecê-los! Economia O método é utilizado pelas empresas para otimizar a alocação de recursos em processos produtivos, definir estratégias de investimento e planejar o mix de produtos a serem fabricados. Engenharia O método auxilia a otimização de projetos de estruturas, como pontes e edifícios, para minimizar o uso de materiais e garantir a resistência necessária. Também é utilizado para dimensionar peças industriais e planejar processos de manufatura de forma eficiente. Logística O método é utilizado pelas empresas de transporte para definir rotas de entrega otimizadas, minimizando as distâncias percorridas e os custos com combustível. Também é aplicado no planejamento de frotas de veículos, garantindo que se tenha a quantidade ideal de caminhões, vans etc. Pesquisa operacional O método é uma ferramenta basilar na pesquisa operacional, área que busca soluções otimizadas para problemas complexos em diversos ramos, como: saúde, finanças, manufatura e gestão de projetos. O simplex na indústria Agora, vamos conferir alguns exemplos de simplex na indústria. Empresas A gigante Amazon utiliza o método simplex para otimizar sua complexa rede de logística, garantindo entregas rápidas e eficientes a seus clientes. Governos Diversos países, com o aval de seus governantes, utilizam o método simplex para otimizar a alocação de recursos públicos em diferentes áreas, como: saúde, educação e infraestrutura. Organizações sem fins lucrativos O método simplex auxilia ONGs na otimização de seus recursos, para que possam maximizar o impacto de seus programas e serviços na sociedade. Impacto transformador do método simplex O método simplex impactou significativamente diversos setores, impulsionando avanços consideráveis, como: Melhoria na tomada de decisão As informações precisas fornecidas pelo método simplex embasam as decisões estratégicas, permitindo que empresas e organizações escolham as melhores alternativas com maior segurança. Redução de custos A otimização proporcionada pelo método simplex leva à redução de custos em diversos processos, aumentando a lucratividade e a competitividade das empresas. Aumento da produtividade A otimização dos processos proporcionada pelo método simplex aumenta a produtividade, gerando mais resultados com os mesmos recursos. Aumento da competitividade A utilização do método simplex pelas empresas pode propiciar uma vantagem competitiva no mercado, pois são capazes de operar de forma mais eficiente e eficaz. Método simplex: considerações importantes Como toda ferramenta, o método simplex também possui limitações, como sere espaço de armazenamento. Dados: Lucro por medicamento: Medicamento A: R$ 10 Medicamento B: R$ 15 Medicamento C: R$ 20 Custo por medicamento: Medicamento A: R$ 5 Medicamento B: R$ 7 Medicamento C: R$ 10 Orçamento disponível: R$ 1000 Espaço de armazenamento disponível: 100 m² Espaço ocupado por medicamento: Medicamento A: 0,5 m² Medicamento B: 1 m² Medicamento C: 2 m² Faça uma modelagem matemática para solucionar o problema. Chave de resposta Variáveis de decisão: • • • • • x1: Quantidade de medicamentos A a serem comprados. x2: Quantidade de medicamentos B a serem comprados. x3: Quantidade de medicamentos C a serem comprados. Modelo matemático: função objetivo (maximizar lucro): Restrições: Orçamento: Espaço de armazenamento: Não negatividade: Questão 4 Uma empresa precisa determinar a quantidade ideal de cada ingrediente a ser utilizado na produção de um novo tipo de biscoito, de modo a minimizar o custo total da mistura e atender às restrições nutricionais e de sabor. Dados: • • • • Ingredientes: Farinha de trigo Açúcar Cacau em pó Manteiga Custo por kg de ingrediente: Farinha de trigo: R$ 2,00 Açúcar: R$ 3,00 Cacau em pó: R$ 5,00 Manteiga: R$ 8,00 Restrições nutricionais: Teor de gordura máximo: 20% Teor de açúcar máximo: 30% Teor de cacau em pó mínimo: 10% Restrição de sabor: A proporção de farinha de trigo e açúcar deve ser entre 2:1 e 3:1. Chave de resposta • • • • • • • • • • • Variáveis de decisão: x1: Quantidade de farinha de trigo a ser utilizada (kg) x2: Quantidade de açúcar a ser utilizada (kg) x3: Quantidade de cacau em pó a ser utilizada (kg) x4: Quantidade de manteiga a ser utilizada (kg) Modelo matemático: função objetivo (minimizar custo total): Restrições: Teor de gordura: Teor de açúcar: Teor de cacau em pó: Proporção farinha/açúcar: Não negatividade: • • • • Questão 5 Uma empresa precisa determinar a alocação ideal de seu orçamento de marketing entre diferentes canais (como TV, rádio, internet e mídia impressa) para maximizar o retorno sobre o investimento (ROI). Dados: Orçamento total de marketing: R$ 100.000 Custo por clique (CPC) em cada canal: TV: R$ 10 Rádio: R$ 5 Internet: R$ 2 Mídia impressa: R$ 3 Taxa de conversão (CR) em cada canal: TV: 2% Rádio: 1% Internet: 5% Mídia impressa: 3% Valor médio de uma venda: R$ 100 Qual modelagem matemática maximiza o ROI? Chave de resposta Variáveis de decisão: x1: Quantidade de cliques a serem comprados na TV. x2: Quantidade de cliques a serem comprados no rádio. x3: Quantidade de cliques a serem comprados na internet. • • • • • • • x4: Quantidade de cliques a serem comprados na mídia impressa. Modelo matemático: Função objetivo (maximizar ROI): Restrições: Orçamento: Não negatividade: Questão 6 Uma empresa de sucos precisa determinar a quantidade ideal de laranjas para polpa e suco concentrado para minimizar o custo total de produção de um litro de suco de laranja. Dados: Custo por kg de laranja para polpa: R$ 0,50 Custo por litro de suco concentrado: R$ 2,00 Rendimento: • • • 1 kg de laranja para polpa rende 0,8 litro de suco. 1 litro de suco concentrado misturado com água rende 5 litros de suco final. Quantidade de suco final a ser produzida: 100 litros. Qual modelagem matemática determinaria a melhor solução para o problema? Chave de resposta Variáveis de decisão: x1: Quantidade de kg de laranja para polpa a ser usada (kg). x2: Quantidade de litros de suco concentrado a ser usada (litros). Modelo matemático: Função objetivo (minimizar custo total): Restrições: Quantidade de suco da polpa: Como são necessários 100 litros de suco final, e o suco concentrado representa 4/5 do volume final (pois é diluído em água), precisamos de: 0.8x1 \geq (4/5) * 100 litros = 80 litros Quantidade de suco do concentrado: x2 * 5 = suco do concentrado diluído • • • • • • • • x2 * 5 = (1/5) * 100 litros = 20 litros (já que o suco concentrado representa 1/5 do volume final) Não negatividade: Neste vídeo, veja a resolução da questão! https://play.yduqs.videolib.live/player?token=991660c7a7a34b80abbe3d8601f40b8c Teoria na prática Uma lanchonete oferece três tipos de lanches: sanduíche de frango, hambúrguer simples e hambúrguer completo. O proprietário quer maximizar o lucro diário, considerando que o estoque de ingredientes é limitado. Aqui estão os dados: Lucro por lanche: · Sanduíche de frango: R$ 8,00 · Hambúrguer simples: R$ 10,00 · Hambúrguer completo: R$ 15,00 Estoque de ingredientes disponíveis para o dia: · Pão: 100 unidades · Peito de frango desfiado: 20 kg · Carne de hambúrguer: 30 kg · Queijo: 15 kg · Alface: 5 kg · Tomate: 8 kg Ingredientes necessários por lanche: · Sanduíche de frango: 1 pão, 0,2 kg de peito de frango, 0,1 kg de queijo e 0,05 kg de alface. · Hambúrguer simples: 1 pão, 0,3 kg de carne, 0,1 kg de queijo, 0,05 kg de alface e 0,05 kg de tomate. · Hambúrguer completo: 1 pão, 0,4 kg de carne, 0,2 kg de queijo, 0,1 kg de alface e 0,1 kg de tomate. • • • Como maximizar o lucro? Chave de resposta Neste vídeo, confira a resolução a seguir! Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Verificando o aprendizado Questão 1 Suponha que uma empresa fabrica dois tipos de produtos: camisetas e calças. O objetivo é determinar a quantidade de cada produto a ser produzida para maximizar o lucro total da empresa, sujeito a certas restrições. Aqui estão os dados: O lucro por unidade de camiseta é $5 e por unidade de calça é $8. Para produzir uma camiseta, são necessários 2 metros de tecido e 1 hora de trabalho. Para produzir uma calça, são necessários 3 metros de tecido e 2 horas de trabalho. A empresa tem 100 metros de tecido e 80 horas de trabalho disponíveis por semana. O lucro da fábrica será igual a: A 266, 67 B 266,00 C 305,48 D 305,00 E 180,00 A alternativa B está correta. Vamos ao modelo matemático do problema, que envolve programação linear. Considere: x = quantidade de camisetas a serem produzidas. y = quantidade de calças a serem produzidas. Nossa função objetivo é maximizar o lucro total, dado por: Sujeito às seguintes restrições: Restrição de tecido: (não podemos usar mais de 100 metros de tecido). Restrição de trabalho: (não podemos exceder 80 horas de trabalho). Além disso, as variáveis devem ser não negativas e inteiras: e y . Agora, você pode usar o LINDO para encontrar os valores ótimos de x e y que maximizam o lucro total Z. Resolvendo, obtemos: • • • • • Questão 2 Suponha que uma empresa fabrique três tipos de produtos: X, Y e Z. O objetivo é determinar a quantidade de cada produto a ser produzida para maximizar o lucro total da empresa, sujeito a certas restrições. Aqui estão os dados: O lucro por unidade de produto X é $10, por unidade de produto Y é $12, e por unidade de produto Z é $15. Para produzir uma unidade de produto X, são necessárias 2 unidades do recurso A e 1 unidade do recurso B. Para produzir uma unidade de produto Y, são necessários 1 unidade do recurso A e 2 unidades do recurso B. Para produzir uma unidade de produto Z, são necessárias 3 unidades do recurso A e 2 unidades do recurso B. A empresa tem 200 unidades do recurso A e 150 unidades do recurso B disponíveis. Assinale a alternativa correta: A x = 83.333336, y =33.333332 e z = 2.333333 B x = 83.333336, y =33.333332 e z = 0,000000 C x = 82.333336, y =33.333332 e z = 1,000000 • • • • • D x = 82.000000, y =33.000000 e z = 1,000000 E x = 75.000000, y =28.000000 e z = 12,000000 A alternativa D está correta. Então, vamos formular o problema como um problema de programação linear. Considere: x = quantidade de unidades do produto X a serem produzidas y = quantidade de unidades do produtoY a serem produzidas z = quantidade de unidades do produto Z a serem produzidas Nossa função objetivo é maximizar o lucro total, dado por: Sujeito às seguintes restrições: Restrição do recurso A: (não podemos usar mais de 200 unidades do recurso A). Restrição do recurso B: (não podemos usar mais de 150 unidades do recurso B). Além disso, as variáveis e devem ser não negativas e inteiras: x , y e z . Agora, podemos usar o LINGO para encontrar os valores ótimos de x, y e z que maximizam o lucro total Z. Temos, portanto, a seguinte solução: • • • 4. Conclusão Considerações finais O método simplex é amplamente reconhecido como um dos algoritmos fundamentais da pesquisa operacional para resolver problemas de programação linear. A popularidade desse método decorre de sua capacidade de otimizar uma variedade de problemas em diferentes setores, como transporte, logística, finanças e manufatura, oferecendo uma abordagem sistemática para maximizar lucros ou minimizar custos. No entanto, apesar de suas vantagens, o simplex enfrenta alguns desafios significativos que precisam ser superados para garantir sua eficácia em cenários complexos. Um desses desafios é a escalabilidade limitada do simplex, o que significa que ele pode enfrentar dificuldades na resolução de problemas de grande porte com muitas variáveis e restrições. Nesses casos, podem ser necessárias soluções alternativas ou até mesmo o uso de métodos mais avançados de otimização. Além disso, o simplex está sujeito a armadilhas subótimas, cenário em que pode encontrar soluções que não são as melhores possíveis no contexto do problema. Isso requer cautela na interpretação dos resultados e pode exigir ajustes no modelo ou nos parâmetros do algoritmo. Outro desafio crítico é a precisão computacional. Como o simplex realiza cálculos iterativos, ele é sensível a erros de arredondamento e precisão numérica, o que pode impactar a qualidade da solução final. Portanto, é preciso que analistas e pesquisadores estejam atentos aos detalhes durante a implementação do algoritmo para evitar distorções nos resultados. Por fim, a modelagem prévia adequada do problema como um modelo de programação linear é uma etapa fundamental para o sucesso do método simplex. Isso envolve definir corretamente a função objetivo, as variáveis de decisão e as restrições, garantindo que o modelo captura com precisão as complexidades do problema real e orienta o simplex na direção da solução ótima. Explore + Não pare por aqui! Para você continuar explorando os assuntos abordados, recomendamos a leitura dos seguintes artigos: Maximization of a linear function of variables subject to linear inequalities, de Dantzig, G. B. (1947), publicado no American Journal of Operations Research. O artigo introduz o conceito de programação linear como técnica fundamental para otimizar problemas com restrições lineares. Vale a pena conferir! The many facets of linear programming, de Todd (1976), publicado no jornal acadêmico Management Science. O artigo discute as diferentes formulações da programação linear, apresenta o conceito de dualidade e aborda a importância desse tipo de programação na tomada de decisão em diversas áreas, como finanças, logística e engenharia. Referências BAZARAA, M. S.; JARVIS, J. J.; SHERALI, H. D. Linear programming and network flows. 4th ed. Hoboken, NJ: Wiley, 2009. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to algorithms. 3rd ed. Cambridge, MA: The MIT Press, 2009. HILLIER, F. S.; LIEBERMAN, G. J. Introduction to operations research. 8th ed. New York, NY: McGraw-Hill Higher Education, 2005. • • KAGAN, N. et al. Métodos de otimização aplicados a sistemas elétricos de potência. São Paulo: Blucher, 2009. TAHA, H. A. Operations research: an introduction. 10th ed. Upper Saddle River, NJ: Pearson, 2016. Método simplex 1. Itens iniciais Propósito Objetivos Introdução Conteúdo interativo 1. O método simplex para a solução de problemas de PL Conceito e história do método simplex Visualizando o método simplex Desconstruindo o processo: as etapas do método simplex Formulação do problema Conversão para a forma padrão Encontrando uma solução viável Otimização da solução Análise da solução Economia Engenharia Logística Pesquisa operacional O simplex na indústria Empresas Governos Organizações sem fins lucrativos Impacto transformador do método simplex Melhoria na tomada de decisão Redução de custos Aumento da produtividade Aumento da competitividade Método simplex: considerações importantes Conceito e história do método simplex Conteúdo interativo Vantagens e desvantagens do método simplex Conteúdo interativo Vantagens Eficiência Simplicidade Versatilidade Aplicações práticas Desvantagens Dificuldade com problemas grandes Soluções ótimas locais Sensibilidade a erros Limitações teóricas Complexidade de implementação Relação do método simplex com outros métodos de otimização Similaridades com outros métodos A reta Plano α Plano α Diferenças do método simplex Método do lagrange Programação linear mista Programação linear semidefinida Programação convexa Relação com a programação linear Método do gradiente Método das bissecções Algoritmos genéticos Relação do método simplex com outros métodos de otimização Conteúdo interativo Verificando o aprendizado 2. Problemas de PL com o método simplex Teorema da fundamentalidade da PL Mergulhando na essência do teorema Existência de solução ótima Dualidade Exemplo 1: Maximização da produção Exemplo 2: Minimização de custos Exemplo 3: Modelagem matemática Teorema da fundamentalidade da PL Conteúdo interativo Condições de otimalidade Essência das condições Condições de primalidade Condições de dualidade Exemplos de maximização e minimização Maximização da produção Minimização de custos Aplicações práticas e relevância Exemplo detalhado Condições de otimalidade Conteúdo interativo Dualidade na PL O surgimento da dualidade Conceitos fundamentais Explorando as aplicações práticas Maximização da produção Minimização de custos Alocação de recursos em um hospital Interpretação das variáveis duais Relaxamento de restrições Dualidade e sensibilidade Problema de transporte com capacidades Problema de mistura de ração animal Desafios e considerações acerca do simplex Exemplo detalhado da dualidade na PL Limite inferior para o custo total de transporte Preços sombra das restrições Análise da solução dual Dualidade na PL Conteúdo interativo O software LINDO Regras do software LINDO para PL Definir o modelo Executar a solução Analisar a solução Geração de relatórios Análise de sensibilidade Programação O software LINDO Conteúdo interativo Resolução de problemas de PL com o método simplex Formulação do problema Conversão para a forma padrão Construção da tabela simplex Seleção da variável entrante Seleção da variável saliente Cálculo da razão pivô Atualização da tabela simplex Teste de otimalidade Resolução de problemas de PL com o método simplex Conteúdo interativo Verificando o aprendizado 3. Aplicações do método simplex Conceitos básicos da programação linear (PL) Conceitos, formulação de problemas, métodos de resolução Conteúdo interativo Maximizar Minimizar Tipos de restrições Igualdade Desigualdade Não negatividade Exemplo 1 Conteúdo interativo Formulação de problemas de PL Exemplo 2 Conteúdo interativo Métodos de resolução de problemas de PL Método gráfico Método simplex Branch-and-bound Programação linear inteira mista (MILP) Considerações importantes para a escolha do método adequado Interpretação de resultados Solução ótima Valor da função objetivo Sensibilidade Interpretação de sombras Relatórios e outputs Mão na massa Teoria na prática Conteúdo interativo Verificando o aprendizado 4. Conclusão Considerações finais Explore + Referênciasineficiente para resolver problemas de PL com grande número de variáveis e restrições, exigindo recursos computacionais robustos, e poder encontrar soluções ótimas que não são necessariamente ótimas em um contexto global, necessitando de técnicas adicionais para garantir a solução ideal. O método simplex é um marco na história da otimização linear, uma ferramenta promissora que contribuiu consideravelmente para a eficiência e o progresso em diversas áreas. Apesar de suas limitações, o método continua sendo um algoritmo fundamental para a resolução de problemas de PL, abrindo portas para um futuro de decisões mais inteligentes e resultados otimizados. Confira, a seguir, um esquema que usa o método simplex! Esquema de um problema de transporte. Na sequência, vamos dar continuidade ao nosso estudo entendendo melhor as vantagens e as desvantagens do método. Conceito e história do método simplex Confira, neste vídeo, como o método simplex pode ser uma técnica poderosa no auxílio à tomada de decisões complexas. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Vantagens e desvantagens do método simplex Confira neste vídeo as características básicas do método simplex! Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Como você já sabe, o método simplex revolucionou a otimização linear. Sua capacidade de resolver problemas de programação linear (PL) com notável rapidez impulsionou o desenvolvimento de técnicas de otimização em diversas áreas e suas vantagens são inúmeras. Acompanhe! Vantagens Chegou a hora de detalhar algumas das muitas vantagens do método simplex. Vamos lá! 1 Eficiência O método simplex é um dos métodos mais eficientes para resolver problemas de PL, especialmente quando comparado a métodos preexistentes. A capacidade que o método tem de encontrar soluções ótimas rapidamente o torna ideal para problemas que exigem respostas em tempo hábil. A simplicidade do algoritmo facilita a implementação em softwares e ferramentas computacionais. • • • 2 Simplicidade O método simplex é baseado em conceitos matemáticos relativamente simples, o que o torna fácil de entender e aprender. A estrutura lógica e intuitiva do método facilita a implementação e o acompanhamento do processo de resolução. A simplicidade da ferramenta também o torna acessível a um público mais amplo, não apenas a especialistas em matemática ou otimização. 3 Versatilidade O método simplex pode ser aplicado a inúmeros problemas de PL em diferentes áreas. A flexibilidade do método permite adaptá-lo a diferentes tipos de problemas e restrições. A versatilidade do método o torna uma ferramenta basilar para diversos setores da economia e da sociedade. 4 Aplicações práticas O método simplex é utilizado em diversas áreas, como economia, engenharia, logística e pesquisa operacional. A aplicação prática contribui para a otimização de recursos, o aumento da produtividade e a redução de custos. O método simplex tem impacto significativo na tomada de decisões estratégicas em diversas organizações. E então, o que achou do método? Bastante positivo, não é mesmo? Mas tenha atenção às suas desvantagens, afinal, nada é perfeito. Desvantagens Agora, confira algumas das desvantagens que merecem nossa atenção ao escolher o método. • • • • • • • • • 1 Dificuldade com problemas grandes O método simplex pode ser ineficiente para resolver problemas de PL com grande número de variáveis e restrições. Nesses casos, o tempo de processamento pode ser excessivo, tornando a solução inviável na prática. A necessidade de recursos computacionais robustos pode limitar a aplicação do método em problemas de grande escala. 2 Soluções ótimas locais O método simplex pode encontrar soluções ótimas que não são necessariamente ótimas em um contexto global. Em alguns casos, o método pode parar em um ponto que é ótimo localmente, mas não é o melhor possível globalmente. Técnicas adicionais, como o método das big-M ou o método das barreiras, podem ser necessárias para garantir a solução ótima global. 3 Sensibilidade a erros O método simplex pode ser sensível a erros de arredondamento e imprecisões nos dados. Pequenas alterações nos dados podem levar a grandes mudanças na solução final. É importante ter cuidado ao inserir dados e interpretar os resultados do método simplex. 4 Limitações teóricas O método simplex não é capaz de resolver todos os problemas de PL. Existem alguns tipos de problemas de PL para os quais o método simplex não é aplicável. Nesses casos, outros métodos de otimização podem ser necessários. • • • • • • • • • 5Complexidade de implementação A implementação eficiente do método simplex pode ser complexa, especialmente para problemas de grande escala. É importante ter conhecimento de matemática e programação para implementar o método simplex de forma eficaz, e a necessidade de expertise pode limitar a aplicação do método por usuários menos experientes. O método simplex é uma ferramenta que apresenta muitas vantagens, mas algumas desvantagens, portanto, sua escolha depende da natureza do problema a ser solucionado, dos recursos computacionais disponíveis e da expertise do usuário. Antes de decidir, analise! Relação do método simplex com outros métodos de otimização Embora muito vantajoso, o método simplex não é o único método de otimização disponível. Na sequência, vamos explorar a relação do simplex com outros métodos de otimização, destacando suas similaridades, diferenças e aplicações específicas. Vamos lá! Similaridades com outros métodos A maioria dos métodos de otimização, incluindo o simplex, baseia-se em princípios matemáticos como a teoria dos conjuntos convexos e a programação linear, e o objetivo central de todos eles é encontrar a solução ótima para um problema, seja maximizando uma função objetivo ou minimizando um custo. Além disso, muitos desses métodos, incluindo o simplex, utiliza um processo iterativo para encontrar a solução ótima, ajustando as variáveis a cada iteração até alcançar o ponto ideal. A reta É um conjunto de pontos convexo. Plano α É uma região convexa. • • Plano α É uma região côncava. Diferenças do método simplex O método simplex utiliza um algoritmo específico para navegar pelo politopo convexo (região viável — é um objeto geométrico delimitado por um número finito de segmentos de linha reta ou plano) do problema de PL, buscando o vértice com o melhor valor objetivo. O simplex é considerado um dos métodos mais eficientes para resolver problemas de PL, especialmente quando comparado a métodos preexistentes. É preciso destacar ainda que o simplex, por ser baseado em conceitos matemáticos relativamente simples, é mais fácil de entender e implementar. Veja, a seguir, uma comparação do simplex com outros métodos. Método Similaridades Diferenças Vantagens Desvantagens Aplicações Método do gradiente Base matemática, objetivo comum, iteração. Abordagem, eficiência, simplicidade. Eficiente para funções não lineares. Sensível a erros, pode convergir para soluções ótimas locais. Otimização de carteiras de investimento, planejamento de produção e logística. Método das bissecções Base matemática, objetivo comum, iteração. Abordagem, eficiência, simplicidade. Simples de implementar. Pode ser lento para problemas com grande número de variáveis. Encontrar raízes de equações, determinar o ponto de máximo de uma função unimodal. Algoritmos genéticos Base matemática, objetivo comum. Abordagem, eficiência, simplicidade. Eficaz para problemas complexos. Pode ser computacionalmente caro. Otimização de design de produtos, planejamento de rotas complexas, seleção de características em problemas de machine learning. Método do ponto interior Base matemática, objetivo comum, iteração. Abordagem, eficiência. Mais eficiente que o simplex para alguns problemas. Mais complexo de implementar. Problemasde PL com grande número de variáveis. Método da ramificação e corte Base matemática, objetivo comum. Abordagem, eficiência. Eficaz para problemas de PL com estrutura especial. Pode ser lento para alguns problemas. Otimização de problemas de transporte, planejamento de produção. Quadro: Comparação do método simplex com outros métodos de solução de problemas de otimização. Mauro Rezende Filho Ainda temos outras opções relevantes, como: Método do lagrange Encontra soluções para problemas com restrições de igualdade. Programação linear mista Resolve problemas com variáveis contínuas e discretas. Programação linear semidefinida Otimiza problemas com variáveis definidas por matrizes. Programação convexa Abrange uma gama de problemas com funções objetivas e restrições convexas. Relação com a programação linear O simplex é um dos principais métodos para resolver problemas de programação linear. Sua relação com a PL é tão intrínseca que é frequentemente utilizado como sinônimo de resolução de problemas de PL. O método é especialmente eficiente para resolver problemas de PL com um número limitado de variáveis e restrições. Vejamos algumas aplicações específicas de outros métodos! Método do gradiente Otimização de carteiras de investimento, planejamento de produção e logística. Método das bissecções Encontro de raízes de equações, determinar o ponto de máximo de uma função unimodal. Algoritmos genéticos Otimização de design de produtos, planejamento de rotas complexas, seleção de características em problemas de machine learning. A compreensão das similaridades, diferenças e aplicações específicas do simplex e de outros métodos de otimização é fundamental para a escolha da ferramenta mais adequada para cada caso. Lembre-se disso! Relação do método simplex com outros métodos de otimização Confira, neste vídeo, os métodos aplicados em otimização linear. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Verificando o aprendizado Questão 1 Um empresário precisa otimizar a produção de sua fábrica para maximizar o lucro, considerando diversas restrições de capacidade, demanda e matéria-prima. Ele tem à disposição diversos métodos de otimização, mas qual deles é mais adequado para essa situação, considerando que o problema pode ser modelado como um problema de programação linear de grande escala? A Método simplex B Busca local C Programação dinâmica D Algoritmo genético E Ponto interior A alternativa E está correta. Como o simplex pode ser lento para resolver problemas de grande escala, o método ponto interior pode ser uma alternativa mais eficiente para esse tipo de problema, pois converge à solução ótima mais rapidamente. Questão 2 Um cientista precisa determinar a estrutura molecular de um composto químico por meio de métodos computacionais. Ele tem à disposição o método simplex e outros métodos de otimização. Qual método é mais adequado para essa situação, considerando que o problema pode ser modelado como um problema de otimização não linear com muitas variáveis? A Método simplex B Busca local C Programação dinâmica D Algoritmo genético E Gradiente descendente A alternativa D está correta. O método simplex e o gradiente descendente não são adequados para problemas de otimização não linear com muitas variáveis. O algoritmo genético é uma técnica robusta que pode lidar com esse tipo de problema, buscando a solução ótima global por meio de uma simulação inspirada na evolução natural. 2. Problemas de PL com o método simplex Teorema da fundamentalidade da PL O teorema fundamental da programação linear (TFLP) é um pilar na área de otimização, fornecendo uma base sólida para a resolução de problemas de maximização ou minimização de funções lineares sob restrições lineares. Esse teorema garante que, se um problema de programação linear (PL) for viável e limitado, então ele possui uma solução ótima, e essa solução pode ser encontrada por meio de um método finito de busca. Mergulhando na essência do teorema O TFLP pode ser dividido em duas partes principais, confira! 1 Existência de solução ótima Todo problema de PL viável e limitado possui pelo menos uma solução ótima. Isso significa que existe um conjunto de valores para as variáveis que maximiza ou minimiza a função objetivo nas restrições impostas. 2 Dualidade Para cada problema de PL, existe outro problema, chamado de problema dual, que fornece informações sobre a solução ótima do problema original. A solução ótima do problema dual fornece um limite inferior ou superior para o valor da função objetivo do problema original. Agora, vejamos alguns exemplos para esclarecer o conceito. Exemplo 1: Maximização da produção 1. Formulação do problema: Variáveis de decisão: x₁: quantidade de A produzida x₂: quantidade de B produzida Função objetivo: Lucro = 2x₁ + 3x₂ Restrições: Disponibilidade de recursos: Matéria-prima: 2x₁ + x₂ ≤ 6 Mão de obra: x₁ + 2x₂ ≤ 8 • • • • • Demanda do mercado: A: x₁ ≥ 1 B: x₂ ≥ 2 2. Resolução: Utilizando o método do simplex, obtemos a solução ótima: x₁ = 1 x₂ = 3 3. Verificação da solução: Função objetivo: Lucro = 1(2) + 3(3) = 11 Restrições: Matéria-prima: 2(1) + 3 = 5 ≤ 6 (verdadeiro) Mão de obra: 1 + 2(3) = 7 ≤ 8 (verdadeiro) Demanda do mercado: A: 1 ≥ 1 (verdadeiro) B: 2 ≥ 2 (verdadeiro) Exemplo 2: Minimização de custos 1. Formulação do problema: Variáveis de decisão: xᵢⱼ: quantidade de produtos transportada do armazém i para a loja j Colocando a matriz, temos: Armazém 1 Armazém 2 Armazém 3 Loja 1 x11 x12 x13 Loja 2 x21 x22 x23 Loja 3 x31 x32 x33 • • • • • • • • • • Loja 4 x41 x42 x43 Tabela: Dados do problema para minimização de custos. Mauro Rezende Filho. Função objetivo: • Custo = 4x₁₁ + 6x₁₂ + 5x₁₃ + 7x₁₄ + 2x₂₁ + 3x₂₂ + 2x₂₃ + x₂₄ + 3x₃₁ + x₃₂ + 2x₃₃ + 3x₃₄ Restrições: Demanda das lojas: Loja 1: 2x₁₁ + x₁₂ + x₁₃ ≥ 4 Loja 2: x₂₁ + 3x₂₂ + x₂₃ ≥ 6 Loja 3: x₃₁ + x₃₂ + 2x₃₃ ≥ 5 Loja 4: x4₁ + 2x4₂ + 3x4₃ ≥ 7 Disponibilidade dos armazéns: Armazém 1: x₁₁ + x₂₁ + x₃₁ + x4₁ ≤ 8 Armazém 2: x₁₂ + 3x₂₂ + x₃₂ + x4₂ ≤ 12 Armazém 3: 2x₁₃ + x₂₃ + x₃₃+ 2x4₃≤ 10 Colocando de forma matricial, temos: 2. Resolução: Utilizando o método simplex, obtemos a solução ótima: x₁₂ = 4 x₂₃ = 5 x₃₂ = 1 x₃₃ = 4 • • • • • • • • • • • x42 = 7 3. Verificação da solução: Função objetivo: Custo = 4X2 + 5X1 + 1X2 + 4X2 +7X1 = 30 Restrições: Apresentando as restrições de forma matricial, temos que todas as restrições foram atendidas. Observe! Armazém 1 Armazém 2 Armazém 3 Total Loja 1 0 4 0 4 Loja 2 0 0 5 5 Loja 3 0 1 4 5 Loja 4 0 7 0 7 Total 0 12 9 21 Tabela: Restrições de forma matricial. Mauro Rezende Filho. Exemplo 3: Modelagem matemática Formulação do problema: Variáveis de decisão: x₁: quantidade de milho (kg) x₂: quantidade de soja (kg) x₃: quantidade de farelo de algodão (kg) Função objetivo: Custo = 2x₁ + 3x₂ + 4x₃ Restrições: Nutrição: Proteína: 0.2x₁ + 0.4x₂ + 0.5x₃ ≥ 12 • • • • • • • Energia: 3x₁ + 4x₂ + 5x₃ ≥ 20 Disponibilidade: Milho: x₁ ≤ 8 Soja: x₂ ≤ 6 Farelo de algodão: x₃ ≤ 5 2. Resolução: Utilizando o método simplex ou o solver, obtemos a solução ótima: x₁ = 4 x₂ = 2 x₃ = 3 3. Verificação da solução: Função objetivo: Custo = 2(4) + 3(2) + 4(3) = 26 Restrições: Nutrição: Proteína: 0.2(4) + 0.4(2) + 0.5(3) = 1.6 + 0.8 + 1.5 = 3.9 ≥ 12 (verdadeiro) Energia: 3(4) + 4(2) + 5(3) = 12 + 8 + 15 = 35 ≥ 20 (verdadeiro) Disponibilidade: Milho: 4 ≤ 8 (verdadeiro) Soja: 2 ≤ 6 (verdadeiro) Farelo de algodão: 3 ≤ 5 (verdadeiro) Interpretação da solução: • • • • • • • • • • • • • A dieta ótima para as vacas leiteiras consiste em 4 kg de milho, 2 kg de soja e 3 kg de farelo de algodão. Essa dieta fornece os nutrientes necessários para as vacas e tem um custo mínimo de R$ 26. O TFLP éutilizado em diversas áreas, como: Logística: otimização de rotas de transporte, alocação de recursos em armazéns. Finanças: otimização de carteiras de investimento, gestão de riscos. Indústria: otimização da produção, planejamento de recursos. Engenharia: projeto de estruturas, planejamento de obras. Teorema da fundamentalidade da PL Confira, neste vídeo, um exemplo de aplicação do teorema fundamental da programação linear (TFLP). Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Condições de otimalidade Em problemas de otimização, encontrar a solução ótima é fundamental para alcançar o melhor resultado possível. As condições de otimalidade fornecem um conjunto de critérios que garantem que uma solução seja realmente ótima. Essência das condições As condições de otimalidade podem ser divididas em dois tipos: primalidade e dualidade. Conheça-as! 1 Condições de primalidade Envolvem: Condição de viabilidade: a solução deve satisfazer todas as restrições do problema. Condição de complementaridade: para cada restrição, o produto entre a folga (diferença entre o limite da restrição e o valor da variável) e o multiplicador de Lagrange deve ser igual a zero. Condição de estacionariedade: a derivada da função objetivo em relação a cada variável, considerando as restrições, deve ser igual a zero. • • • • • • • 2 Condições de dualidade Envolvem: Dualidade fraca: o valor da função objetivo no problema primal é sempre maior ou igual ao valor da função objetivo no problema dual. Dualidade forte: se os problemas primal e dual forem viáveis e limitados, então os valores das funções objetivo no primal e no dual serão iguais. Condições de complementaridade dual: similar à primalidade, mas para as variáveis duais e folgas das restrições duais. Exemplos de maximização e minimização Vamos exemplificar ambos os casos. Observe! Maximização da produção Considere o problema de maximizar a produção de uma fábrica com duas máquinas, A e B, sujeito a restrições de tempo e recursos. As condições de primalidade garantem que a solução escolhida seja a que maximize a produção, respeitando as restrições de tempo e recursos. As condições de dualidade fornecem informações sobre o valor máximo da produção e sobre os preços sombra dos recursos. Minimização de custos Considere o problema de minimizar o custo de transporte de produtos entre armazéns e lojas. As condições de primalidade garantem que a solução escolhida seja a que minimize o custo de transporte, respeitando as restrições de demanda e disponibilidade. As condições de dualidade fornecem informações sobre o custo mínimo de transporte e sobre os preços sombra das restrições de demanda e disponibilidade. Aplicações práticas e relevância As condições de otimalidade são utilizadas em diversas áreas, como: Logística: otimização de rotas de transporte e alocação de recursos em armazéns. Finanças: otimização de carteiras de investimento e gestão de riscos. Indústria: otimização da produção e planejamento de recursos. Engenharia: projeto de estruturas e planejamento de obras. Agora, vamos a algumas considerações importantes para ajudar você a sintetizar. As condições de otimalidade são um conjunto de critérios matemáticos que garantem a otimalidade de uma solução. • • • • • • • • A verificação das condições de otimalidade pode ser complexa, especialmente para problemas de grande porte. Existem diversos métodos para verificar as condições de otimalidade. Exemplo detalhado Considere o problema de maximizar a função objetivo: 1. Formulação do problema: Função objetivo: Restrição: 2. Condições de primalidade: Viabilidade: Complementaridade: Estacionariedade: • • 3. Solução: Resolvendo o sistema de equações, encontramos a solução ótima: 4. Verificação das condições: Viabilidade: Complementaridade: Estacionariedade: 5. Condições de dualidade: Dualidade fraca: Dualidade forte: Complementaridade dual: 6. Interpretação da solução: A solução ótima para o problema de maximização é x = y = 1/2, com um valor máximo da função objetivo de f(x, y) = 1/2. O multiplicador de Lagrange λ = 1 representa o preço sombra da restrição. Observações: Esse é um exemplo simples de um problema de otimização com restrições. Problemas de otimização mais complexos podem ter grande número de variáveis e restrições. Existem diversos softwares disponíveis para resolver problemas de otimização. Resumindo, as condições de otimalidade são responsáveis por garantir que uma solução seja realmente ótima. Por meio da verificação das condições de primalidade e dualidade, podemos ter certeza de que a solução escolhida é a que melhor atende aos objetivos do problema. Condições de otimalidade Aprenda, neste vídeo, como assegurar a otimalidade em um problema de PL. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Dualidade na PL A programação linear (PL) é uma técnica matemática importantíssima para otimizar a alocação de recursos em diversos cenários, mas isso você já sabe, não é mesmo? É preciso que se lembre que ela tem como base formular um problema como uma função objetiva a ser maximizada ou minimizada, sob um conjunto de restrições lineares. Ao longo da história, a PL se tornou um instrumento inegociável em determinadas áreas, especialmente logística, finanças, indústria e engenharia. O surgimento da dualidade Em 1947, o matemático John von Neumann introduziu o conceito de dualidade na PL, abrindo um novo capítulo na compreensão e resolução de problemas de otimização. A dualidade estabelece uma relação profunda entre um problema de PL (chamado problema primal) e outro problema de PL derivado (chamado problema dual). Essa relação permite explorar o problema original sob diferentes perspectivas, revelando informações relevantes e facilitando a sua resolução. Imagine um problema de PL que busca minimizar o custo de transporte de produtos entre armazéns e lojas. A dualidade cria um problema dual associado, que analisa o mesmo cenário sob a ótica de maximizar o lucro obtido pelas lojas ao vender os produtos, considerando os custos de recebimento de cada armazém. • • • • • Conceitos fundamentais Nesse cenário, dois conceitos são basilares: Explorando as aplicações práticas O problema dual em programação linear oferece diversas vantagens estratégicas. Primeiramente, ele estabelece limites basilares para a função objetivo: o valor dual fornece um limite inferior para problemas de minimização e superior para maximização, sendo essencial na avaliação de soluções aproximadas quando resolver o problema primal for complexo ou computacionalmente custoso. Além disso, as variáveis duais identificam os preços sombra das restrições do problema primal, indicando o valor marginal pelo qual a função objetivo se altera ao relaxar essas restrições. Essa informação é imprescindível para decisões estratégicas, permitindo avaliar a importância de cada restrição e seu impacto potencial em mudanças. Em certos cenários, resolver o problema dual pode ser mais simples do que o primal, especialmente quando o número de restrições é substancialmente menor que o de variáveis, o que possibilita encontrar soluções de forma mais rápida ou lidar eficientemente com problemas de grande escala. Além das vantagens mencionadas, o problema dual também facilita a análise de sensibilidade. Isso significa que ele permite entender como a solução ótima do problema primal é afetada por mudanças nos coeficientes dos objetivos ou nas constantes das restrições. Essa capacidade de análise é importante para ajustar estratégias de produção, planejamento financeiro ou alocação de recursos de forma dinâmica, considerando as flutuações e mudanças no ambiente operacional. Portanto, o uso eficaz do problema dual não apenas simplifica a resolução de problemas complexos, mas fortalece a capacidade das organizações de tomar decisões informadas e adaptativasem resposta às condições do mercado e às necessidades operacionais. Vamos ver alguns exemplos para esclarecer os conceitos citados! Dualidade fraca O valor mínimo da função objetivo no problema primal é sempre maior ou igual ao valor máximo da função objetivo no problema dual. Essa propriedade garante que a busca pela solução ótima no primal nunca resultará em um valor inferior ao que poderia ser obtido no dual. Dualidade forte Se o problema primal for viável e limitado (possui soluções e restrições finitas), e o problema dual também for viável e limitado, então os valores das funções objetivo no primal e no dual serão iguais. Essa propriedade garante que, se ambos os problemas forem solucionados com sucesso, os resultados serão consistentes e fornecerão a solução ótima para o problema original. Maximização da produção Primal: maximizar a produção de uma fábrica, respeitando restrições de tempo e recursos. Dual: minimizar o custo associado a essas restrições (custo do tempo e recursos utilizados). Minimização de custos Primal: minimizar o custo de transporte de produtos. Dual: maximizar o lucro obtido pelas lojas ao vender os produtos, considerando os custos de recebimento de cada armazém. Alocação de recursos em um hospital Primal: minimizar o custo total de atendimento a pacientes em um hospital, considerando a disponibilidade de recursos (médicos, enfermeiros, leitos etc.). Dual: maximizar a qualidade do atendimento aos pacientes, considerando os custos de cada tipo de recurso. Vamos aprofundar alguns conceitos! 1 Interpretação das variáveis duais As variáveis duais no problema dual representam os preços sombra das restrições do problema primal. Imagine que uma empresa enfrenta uma restrição de disponibilidade de um determinado material. A variável dual associada a essa restrição indicaria o valor máximo que a empresa estaria disposta a pagar por uma unidade adicional do material, caso esta estivesse disponível. 2 Relaxamento de restrições A dualidade permite analisar o impacto de relaxar (aumentar) as restrições do problema primal. Ao resolver o problema dual com as restrições modificadas, é possível determinar o valor máximo que a função objetivo pode atingir sem violar a viabilidade do problema. • • • • • • 3Dualidade e sensibilidade A dualidade está intimamente ligada à análise de sensibilidade em PL. Ao analisar as variáveis duais, é possível determinar quais restrições são mais críticas para a solução ótima e como a função objetivo é alterada em resposta a mudanças nos parâmetros do problema. Confira mais exemplos avançados de uso do simplex! Problema de transporte com capacidades Considere um problema de transporte com restrições de capacidade nos armazéns e nas lojas. A dualidade pode ser utilizada para determinar os preços sombra das capacidades, fornecendo insights sobre a importância de cada armazém e loja na solução ótima. Problema de mistura de ração animal Considere um problema de mistura de ração para animais com restrições nutricionais. A dualidade pode ser utilizada para determinar os preços sombra dos nutrientes, indicando a importância de cada nutriente para a saúde dos animais. Desafios e considerações acerca do simplex A interpretação das variáveis e restrições do problema dual pode ser complexa, especialmente em problemas com grande número de variáveis e restrições. Em alguns casos, a resolução do problema dual pode ser tão complexa quanto a do problema primal. A dualidade é aplicada principalmente a problemas de PL com funções objetivo e restrições lineares. Para modelos não lineares, existem técnicas alternativas de análise e otimização. Ao compreender e utilizar a dualidade, é possível: Obter limites para a função objetivo. Identificar preços sombra das restrições. Simplificar a resolução em alguns casos. Avaliar o impacto de relaxar restrições. Realizar análises de sensibilidade. A dualidade contribui para uma compreensão mais profunda dos problemas de PL e fornece informações importantíssimas para a tomada de decisão. A aplicação da dualidade em diversas áreas demonstra sua importância como ferramenta para otimizar recursos e alcançar resultados mais eficientes. Exemplo detalhado da dualidade na PL Vamos considerar o seguinte cenário: uma empresa de logística precisa transportar produtos entre três armazéns (A, B e C) e cinco lojas (1, 2, 3, 4 e 5). A empresa possui informações sobre a demanda de cada loja, a capacidade de cada armazém e o custo de transporte entre cada armazém e loja. • • • • • Seu objetivo é: minimizar o custo total de transporte, considerando as restrições de demanda e capacidade. Problema primal Função objetivo: Variáveis: xij: quantidade de produtos transportados do armazém i para a loja j Restrições: Demanda: Capacidade: Não negatividade: Problema dual Função objetivo: Variáveis: Restrições: Resolução: Utilizando um software de PL, podemos resolver o problema primal e o problema dual, e obter as seguintes soluções ótimas: Solução primal: yi: preço sombra da demanda da loja i zi: preço sombra da capacidade do armazém i Solução dual: Análise da solução: Custo total de transporte: Dualidade fraca: Observe que o valor da função objetivo no problema dual (G) é igual ao valor da função objetivo no problema primal (F), confirmando a dualidade forte. Interpretação dos preços sombra: yi: preço sombra da demanda da loja i. Indica o valor máximo que a empresa estaria disposta a pagar por uma unidade adicional de demanda na loja i. zi: preço sombra da capacidade do armazém i. Indica o valor marginal que a empresa perde ao reduzir a capacidade do armazém i em uma unidade. Exemplo: O preço sombra da demanda da loja 1 (y1) é 1. Isso significa que a empresa estaria disposta a pagar até R$ 1 por uma unidade adicional de demanda na loja 1, pois isso resultaria em uma redução de R$ 1 no custo total de transporte. • • • O preço sombra da capacidade do armazém 1 (z1) é 2. Isso significa que a empresa perde R$ 2 em valor marginal ao reduzir a capacidade do armazém 1 em uma unidade. A dualidade na PL fornece informações relevantes sobre o problema original, como: Limite inferior para o custo total de transporte O valor da função objetivo no problema dual (G) fornece um limite inferior para o custo total de transporte (F). Preços sombra das restrições As variáveis duais no problema dual fornecem os preços sombra das restrições do problema primal. Análise da solução dual Permite identificar as restrições mais críticas para o problema e avaliar o impacto de relaxar (aumentar) as restrições. A dualidade é uma ferramenta para otimizar a solução de problemas de PL e para a tomada de decisões estratégicas. Observações adicionais: A interpretação dos preços sombra pode ser complexa em problemas com grande número de variáveis e restrições. Existem técnicas para relaxar as restrições do problema primal e analisar o impacto na solução ótima. A dualidade também pode ser aplicada a problemas de PL com funções objetivo e restrições não lineares. Dualidade na PL Confira, neste vídeo, como assegurar a dualidade em um problema de PL. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. O software LINDO A LINDO Systems é conhecida pelos seus softwares de otimização, em especial o LINDO API e o LINDO Solver. Essas ferramentas são amplamente utilizadas para a programação linear, a programação inteira, a programação não linear e outras tarefas de otimização. A LINDO Systems fornece soluções de software para empresas, pesquisadores e analistas que precisam resolver problemas complexos de otimização. • • • • Para baixar o aplicativo, visite o site da LINDO e baixe a versão mais recente. Um modelo LINDO deverá conter os seguintes itens: Função objetivo (fo), que deverá iniciar com os comandos MAX para maximizar e MIN para minimizar, e à frente, deverá ser colocada a função objetivo.A declaração SUBJECT TO (sujeito a), que pode ser substituída por st ou s.t., e logo após, serão declaradas as restrições do problema. Para finalizar, devemos declarar o comando END. Observe o modelo a seguir. Executando o aplicativo, teclando no ícone de dardo e flecha, obtemos o seguinte resultado: Regras do software LINDO para PL O LINDO é um software importante para a resolução de problemas de PL. Ele oferece uma interface amigável e recursos avançados para otimizar modelos de programação linear. • • • Acompanhe algumas regras básicas! Definir o modelo Criar variáveis e definir seus tipos (reais, inteiras, binárias). Especificar a função objetivo (maximizar ou minimizar). Incluir as restrições do problema (igualdades e desigualdades). Executar a solução Carregar o modelo no LINDO. Resolver o problema usando o comando Solve. Visualizar a solução ótima, incluindo valores das variáveis, função objetivo e valores duais. Analisar a solução Avaliar a viabilidade e otimalidade da solução. Interpretar os valores das variáveis e dos preços sombra. Identificar restrições críticas e realizar análises de sensibilidade. Os recursos adicionais são: Geração de relatórios O LINDO permite gerar relatórios detalhados com a solução do problema, incluindo valores das variáveis, função objetivo, valores duais e outros indicadores. Análise de sensibilidade O LINDO oferece ferramentas para analisar o impacto de mudanças nos parâmetros do problema, como coeficientes da função objetivo e restrições sobre a solução ótima. • • • • • • • • • Programação O LINDO permite escrever scripts para automatizar tarefas e resolver problemas de PL de forma mais complexa. Confira alguns exemplos de regra! GIN y: define a variável y como inteira. Especificar função objetivo: MAX: maximiza a função objetivo (MIN minimiza). 2x + 3y = 0: define a restrição como x >= 0. O software LINDO Confira, neste vídeo, o software LINDO, da LINDO Systems, muito utilizado em programação linear. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Resolução de problemas de PL com o método simplex O método simplex é um algoritmo poderoso para resolver problemas de PL. Sua simplicidade e eficiência o tornaram a ferramenta mais utilizada para otimizar problemas em diversas áreas, desde logística e finanças até engenharia e pesquisa operacional. O método simplex funciona iterativamente, explorando vértices do poliedro viável (região definida pelas restrições do problema) até encontrar a solução ótima. Em cada iteração, o método avalia a solução corrente e determina uma direção de movimento que melhora a função objetivo. Esse processo é repetido até que a solução ótima seja alcançada. Acompanhe as etapas do método simplex! Formulação do problema Definir a função objetivo e as restrições do problema em forma de equações lineares. • • • • • Conversão para a forma padrão Transformar o problema para a forma padrão da PL, com variáveis de folga e artificiais, se necessário. Construção da tabela simplex Organizar as informações do problema em uma tabela que facilita a visualização e o acompanhamento das iterações. Seleção da variável entrante Identificar a variável que, ao entrar na base, resultará no maior aumento da função objetivo. Seleção da variável saliente Determinar a variável que deve sair da base para manter a viabilidade do problema. Cálculo da razão pivô Encontrar o valor que determina a quantidade a ser adicionada à variável entrante e a quantidade a ser retirada da variável saliente. Atualização da tabela simplex Atualizar a tabela com os novos valores das variáveis após a iteração. Teste de otimalidade Verificar se a solução atual é ótima. Se não, retornar à etapa 4. Vamos a um exemplo detalhado. Um produtor independente dispõe de 2 unidades de geração de energia elétrica, que podem ser conectadas ao sistema elétrico em pontos distintos, para a venda do excedente de energia elétrica que são capazes de produzir. Tanto os custos de produção quanto as tarifas negociadas para a venda de energia são distintos para os 2 geradores. O produtor deseja vender o máximo possível de energia seguindo, entretanto, seu plano de negócios, que não permite gastar acima de um valor preestabelecido para a produção de energia (Kagan et al., 2009). Gerador 1 Gerador 2 Capacidade de produção (MWh) 5.000 7.000 Custo de produção (R$/MWh) 50 100 Tarifa de venda (R$/MWh) 90 120 Máximo custo de produção total (R$) 800.000 Tabela: Valores associados à geração de energia. Mauro Resende. Escrevendo o problema em forma de inequações, temos o seguinte problema de geração: Função objetivo: Sujeito a: Confira a solução pelo método simplex no LINDO! Observe que existem poucas diferenças entre o modelo escrito e o colocado no software. Executando, obtemos o seguinte: Veja a tela a seguir, em que rodamos a análise de sensibilidade. Preste atenção nas seguintes dicas! No software LINDO para PL, o termo Reduced Cost (custo reduzido) refere-se à quantidade pela qual o coeficiente de uma variável não básica na função objetivo precisaria melhorar para que essa variável se tornasse uma candidata a entrar na base. Em outras palavras, o custo reduzido indica o potencial benefício de incluir uma variável não básica na solução. Dual Price (preço dual) refere-se ao valor marginal de cada restrição no problema. Em outras palavras, o preço dual indica o quanto a função objetivo (lucro) pode aumentar se a RHS (lado direito) de uma restrição for relaxada em uma unidade. Coefficient Ranges (intervalos de coeficientes) refere-se a uma saída opcional que fornece informações sobre a sensibilidade da solução ótima em relação às variações nos coeficientes da função objetivo e das restrições. Especificamente, o Coefficient Ranges indica o intervalo no qual um coeficiente pode ser alterado sem afetar a variável básica atual na solução e a otimalidade do problema. Right-hand Side Ranges (intervalos do lado direito) é uma subseção específica dentro da saída opcional Coefficient Ranges (intervalos de coeficientes). Como vimos, o Coefficient Ranges analisa a sensibilidade da solução ótima em relação a variações nos coeficientes da função objetivo e das restrições. O Right-hand Side Ranges foca especificamente as mudanças no lado direito (RHS) das restrições do problema. Considere o seguinte problema de programação linear: Sujeito às seguintes restrições: • • • • Colocando no LINDO, temos: Executando com o relatório de análise de sensibilidade, temos: Observe que as variáveis x1 e x3 não participam do problema, e a resposta será x3 = 5 e . Uma empresa está tentando otimizar a produção de três produtos diferentes, denotados como Produto A, Produto B e Produto C. O objetivo é maximizar o lucro total obtido com a venda desses produtos, sujeito a várias restrições operacionais e de mercado. As quantidades produzidas dos três produtos são representadas pelas variáveis de decisão x1 (Produto A), x2 (Produto B) e x3 (Produto C). O lucro obtido com a venda de cada produto é diferente devido às suas características e à demanda no mercado. A empresa definiu as seguintes restrições: A disponibilidade de matéria-prima e mão de obra limita a produção total, representada pela primeira restrição: 3x1−x2+2x3≤10. • Devido à demanda do mercado, a produção total dos produtos deve atender a um mínimo de lucro, representado pela segunda restrição: 2x1+2x2+3x3≥12. Há uma relação específica entre os produtos A, B e C, indicando que a produção deles deve satisfazer a uma relação fixa, representada pela terceira restrição: x1+2x2−x3=5. As quantidades produzidas de cada produto devem ser não negativas: x1,x2,x3≥0. O objetivo da empresa é determinar as quantidades ideais de cada produto a serem produzidas para maximizar o lucro total, seguindo as restrições mencionadas anteriormente. Temoso seguinte modelo matemático para colocar no LINDO: Transferindo para o LINDO, temos: Executando, obtemos: • • • Maximizar Sujeito a: Mas atenção, essa solução está errada! Isso porque, se estamos falando de produtos, temos que pensar que eles não podem ser fracionários. Veja a solução correta: E a solução: Resolução de problemas de PL com o método simplex Confira, neste vídeo, um exemplo de aplicação do método simplex. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Verificando o aprendizado Questão 1 Uma empresa de manufatura está tentando otimizar a produção de dois produtos para maximizar seu lucro. A função objetivo foi definida e as restrições foram estabelecidas. O problema foi convertido para a forma padrão da programação linear (PL) e uma tabela simplex foi construída. Durante o processo, a empresa identificou a variável que entrará na base para maximizar a função objetivo e determinou a variável que deve sair da base para manter a viabilidade. Em seguida, calculou a razão pivô e atualizou a tabela simplex. No entanto, após várias iterações, ainda não estava certa se havia alcançado a solução ótima. Considerando o texto, analise as alternativas a seguir e assinale a correta. A A próxima etapa é construir a tabela simplex novamente com novas variáveis. B A próxima etapa é reavaliar a função objetivo original. C A próxima etapa é identificar novamente as variáveis de folga e artificiais. D A próxima etapa é verificar a otimalidade da solução atual e, se necessário, retornar à seleção da variável entrante. E A próxima etapa é converter o problema de volta à sua forma original. A alternativa D está correta. Após atualizar a tabela simplex com os novos valores das variáveis, a próxima etapa é verificar se a solução atual é ótima. Se não for, o processo deve retornar à seleção da variável entrante para continuar com as iterações até que a solução ótima seja encontrada. As demais alternativas estão incorretas, pois não seguem a sequência correta do método Simplex. Questão 2 Em uma empresa de engenharia, foi realizado um estudo profundo sobre a aplicação da dualidade na programação linear (PL) para otimizar processos de produção. Durante a análise, identificou-se que a dualidade oferece benefícios como a obtenção de limites para a função objetivo e a identificação de preços sombra das restrições. No entanto, os engenheiros enfrentaram desafios na interpretação das variáveis e restrições do problema dual, especialmente devido à complexidade de modelos com muitas variáveis. Apesar das vantagens, a resolução do problema dual também se mostrou complicada em alguns casos, comparável à do problema primal. Considerando o texto, analise as alternativas a seguir e assinale a correta. A A dualidade na programação linear não oferece benefícios práticos na interpretação de variáveis e restrições. B A dualidade na programação linear simplifica automaticamente a resolução de problemas com muitas variáveis. C A resolução do problema dual sempre é mais simples do que a do problema primal. D A dualidade na programação linear é aplicável apenas a problemas com funções objetivo e restrições não lineares. E A dualidade na programação linear contribui para uma compreensão mais profunda dos problemas e oferece informações valiosas para a tomada de decisão. A alternativa E está correta. A dualidade na programação linear contribui positivamente e oferece informações valiosas para a tomada de decisão. As alternativas A, B e C estão incorretas porque não refletem corretamente os benefícios e as características da dualidade na PL mencionados no estudo de caso. A alternativa D também está incorreta, pois a dualidade na PL aplica-se a problemas com funções objetivo e restrições lineares, não necessariamente não lineares. 3. Aplicações do método simplex Conceitos básicos da programação linear (PL) Conceitos, formulação de problemas, métodos de resolução Confira, neste vídeo, um bate-papo sobre os conceitos básicos e a formulação, assim como os métodos de resolução e a interpretação de resultados de problemas de PL. Conteúdo interativo Acesse a versão digital para assistir ao vídeo. A programação linear pode trazer benefícios significativos para as empresas, como a redução de custos, o aumento da produtividade e a melhoria da tomada de decisão. A PL é uma técnica matemática utilizada para resolver problemas de otimização, em que se busca: Maximizar Lucro, produção e quantidade de recursos. Minimizar Custos, tempo e desperdícios. A PL funciona como uma receita para resolver problemas de otimização. Cada componente é um ingrediente essencial para formular e solucionar o problema. Vamos detalhar cada um deles! No centro de um problema de PL está a função objetivo, que define o objetivo a ser maximizado ou minimizado, como lucro, produção, custo ou tempo. Essa função representa a meta final que se busca alcançar com a otimização das variáveis de decisão — os parâmetros controláveis, como quantidades de produtos a fabricar ou horas de trabalho. As restrições, por sua vez, estabelecem as limitações ou as condições que as variáveis de decisão devem respeitar, como disponibilidade de recursos ou capacidade de produção máxima. A interseção das restrições forma a região viável, que representa o conjunto de todas as combinações possíveis das variáveis de decisão que satisfazem todas as restrições. A solução ótima de um problema de PL é o ponto dentro da região viável que maximiza ou minimiza a função objetivo, conforme desejado. Essa solução é a combinação ideal de valores para as variáveis de decisão que proporciona o melhor resultado possível, seja maximizando lucro, minimizando custo ou atingindo qualquer outro objetivo estipulado. Para encontrar essa solução ótima, utilizamos métodos como o método simplex, que explora sistematicamente os vértices da região viável até encontrar o ponto que otimiza a função objetivo. A PL é uma técnica matemática fundamental para a tomada de decisões eficientes e estratégicas, permitindo às empresas e organizações resolverem problemas complexos de modo estruturado e objetivo. Tipos de restrições Conheça, a seguir, alguns tipos de restrições! Igualdade Representa equilíbrios (ex.: x + y = 2, em que x e y são ingredientes que precisam somar 2 unidades). Desigualdade Define limites (ex.: x + y ≤ 2, em que a soma de x e y não pode ultrapassar 2 unidades). Não negatividade Algumas variáveis não podem ser negativas (ex.: x ≥ 0, você não pode ter uma quantidade negativa de ingredientes). Veja agora alguns exemplos! Exemplo 1: uma empresa fabrica dois produtos, A e B. O lucro por unidade de A é R$ 2,00 e o lucro por unidade de B é R$ 3,00. A empresa tem 10 horas de mão de obra disponíveis por dia e 12 horas de máquina disponíveis por dia. O produto A exige 1 hora de mão de obra e 2 horas de máquina por unidade, enquanto o produto B exige 2 horas de mão de obra e 1 hora de máquina por unidade. A empresa deseja determinar a quantidade de cada produto a ser fabricada para maximizar o lucro total. Exemplo 1 Confira, neste vídeo, a resolução da questão! Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Exemplo 1.1: uma atleta precisa definir sua dieta diária para otimizar a ingestão de proteína e carboidrato, respeitando suas necessidades nutricionais e seus limites calóricos. Variáveis de decisão: x = gramas de frango (fonte de proteína) y = gramas de arroz (fonte de carboidrato) Função objetivo (FO): maximizar a proteína total (PT) (em que 2 é a proteína por grama de frango e 0,5 é a proteína por grama de arroz). Restrições: Necessidade mínima de proteína: a atleta precisa de pelo menos 100 gramas de proteína por dia. Necessidade mínima de carboidrato: a atleta precisa de pelo menos 200 gramas de carboidrato por dia. • • • • • Limite calórico: a ingestão diária não pode ultrapassar 2000 calorias. Atenção: 10 é o valor calórico por grama de frango e 4 é o valorcalórico por grama de arroz. Não negatividade: a atleta não pode comer quantidades negativas de frango ou arroz. Resolução: O problema pode ser resolvido graficamente (para 2 variáveis) ou pelo método simplex (para mais variáveis) ou pelo solver. A solução ótima determina a quantidade ideal de frango (x) e arroz (y) que a atleta deve consumir para maximizar a proteína total, respeitando todas as restrições alimentares. Exemplo 2: um fazendeiro precisa criar uma mistura de ração para alimentar seu gado, utilizando três tipos de grãos: milho, soja e aveia. Cada tipo de grão possui diferentes teores de proteína, gordura e fibra, além de diferentes custos. O fazendeiro deseja formular a mistura de ração que atenda às necessidades nutricionais do gado, minimizando o custo total da mistura. Variáveis de decisão: porcentagem de milho na mistura porcentagem de soja na mistura porcentagem de aveia na mistura Função objetivo (FO): minimizar o custo total (CT) Atenção: 0,5 é o custo por kg de milho, 0,8 é o custo por kg de soja e 0,4 é o custo por kg de aveia. Restrições: Teor de proteína: a mistura precisa ter no mínimo 20% de proteína. • 10x + 4y ≤ 2000 • • • • Teor de gordura: a mistura precisa ter no máximo 10% de gordura. Teor de fibra: a mistura precisa ter entre 15% e 25% de fibra. Totalização: a soma das porcentagens deve ser igual a 100%. Não negatividade: as porcentagens não podem ser negativas. Resolução: O problema pode ser resolvido pelo método simplex ou pelo solver. A solução ótima determinará a porcentagem ideal de cada grão (milho, soja e aveia) na mistura de ração para minimizar o custo total, respeitando as necessidades nutricionais do gado. Formulação de problemas de PL É a etapa inicial para utilizar a ferramenta de otimização. É nessa fase que você transforma um problema complexo do mundo real em um modelo matemático que a PL pode resolver. Vamos apresentar alguns exemplos de formulação de modelo matemático. Exemplo 1: uma padaria produz dois tipos de pães: francês e integral. O lucro por unidade de pão francês é R$ 1,50, e o lucro por pão integral é R$ 2,00. A padaria tem 6 horas de forno disponíveis por dia e 4 horas de mão de obra disponíveis por dia. O pão francês leva 0,5 horas de forno e 0,3 horas de mão de obra por unidade, enquanto o pão integral leva 1 hora de forno e 0,4 horas de mão de obra por unidade. A padaria deseja determinar a quantidade de cada tipo de pão a ser produzida para maximizar o lucro total. Variáveis de decisão: = quantidade de pães franceses a serem produzidos. quantidade de pães integrais a serem produzidos. Função objetivo: Restrições: (horas de forno) (horas de mão de obra) (não negatividade) Dicas para formulação efetiva: Identifique claramente o objetivo e as limitações do problema. Defina variáveis de decisão que representem quantidades controláveis. Traduza as restrições em inequações ou equações matemáticas. Certifique-se de que todas as variáveis são não negativas. Verifique se o modelo é consistente e bem definido. Exemplo 2: uma fábrica produz três tipos de brinquedos: carrinhos, bonecas e bicicletas. Cada brinquedo necessita de diferentes quantidades de matéria-prima e horas de mão de obra para ser produzido. A fábrica possui limitações diárias de ambas as quantidades, e deseja determinar a produção ideal de cada brinquedo para maximizar o lucro total, respeitando essas restrições. Variáveis de decisão: = número de carrinhos a serem produzidos. número de bonecas a serem produzidas. • • • • • • • • • • • • número de bicicletas a serem produzidas. Função objetivo: maximizar o lucro total (LT) Atenção: 5 é o lucro por carrinho, 3 é o lucro por boneca e 8 é o lucro por bicicleta. Restrições: Mão de obra: a produção diária não pode ultrapassar 100 horas de mão de obra. Matéria-prima (plástico): a produção diária não pode exceder 80 kg de plástico. Matéria-prima (metal): a produção diária não pode exceder 50 kg de metal. Não negatividade: a produção de cada brinquedo não pode ser negativa. Estoque mínimo de bicicletas: a fábrica precisa produzir pelo menos 10 bicicletas por dia. Explicação das restrições: A primeira restrição limita a produção total de brinquedos conforme a disponibilidade de mão de obra. • • A segunda e a terceira restrições limitam a produção conforme a disponibilidade de plástico e metal, respectivamente. A quarta restrição garante que a produção de brinquedos seja representada por valores reais e não negativos. A quinta restrição estabelece uma demanda mínima de bicicletas que deve ser atendida. Solução: O problema pode ser resolvido utilizando o método simplex ou outros métodos de otimização. A solução ótima indicará a quantidade ideal de cada brinquedo (carrinhos, bonecas e bicicletas) a ser produzida para maximizar o lucro total da fábrica, respeitando as limitações de mão de obra, material e a demanda mínima de bicicletas. Considerações adicionais: Este exemplo demonstra como incorporar restrições de diferentes naturezas (quantidade, mínimo) na formulação do problema. A escolha dos coeficientes na função objetivo e restrições reflete os custos de produção e valores de lucro de cada brinquedo. Exemplo 2 Confira a resolução a seguir! Conteúdo interativo Acesse a versão digital para assistir ao vídeo. Conclusão: A formulação precisa de problemas de PL com três variáveis e cinco restrições permite modelar situações complexas de produção e otimizar a tomada de decisão. Com essa técnica, empresas podem maximizar lucros ao alocar recursos de modo eficiente, respeitando restrições e demandas. Exemplo 3: uma pizzaria oferece três tipos de pizza: muçarela (M), calabresa (C) e frango com catupiry (FC). Cada pizza necessita de diferentes quantidades de ingredientes, e a pizzaria possui um estoque limitado desses ingredientes para o dia. O objetivo é determinar a quantidade ideal de cada tipo de pizza a ser produzida para maximizar o lucro total, respeitando as restrições de ingredientes. Estoque disponível de ingredientes: queijo: 10 kg, tomate: 8 kg, calabresa: 5 kg, frango: 7 kg e catupiry: 3 kg. Lucro por pizza: M = R$ 10, C = R$ 12, FC = R$ 15. • • • • • Ingredientes por pizza: Pizza Queijo (kg) Tomate (kg) Calabresa (kg) Frango (kg) Catupiry (kg) Muçarela (M) 0,2 0,1 Calabresa (C) 0,15 0,1 0,2 Frango com catupiry (FC) 0,18 0,12 3 0,1 Mauro Resende Filho Variáveis de decisão: número de pizzas muçarela a serem produzidas. número de pizzas calabresa a serem produzidas. = número de pizzas frango com catupiry a serem produzidas. Função objetivo: maximizar o lucro total (LT) Restrições: Queijo: a quantidade total de queijo utilizada não pode exceder o estoque disponível. Tomate: a quantidade total de tomate utilizada não pode exceder o estoque disponível. Calabresa: a quantidade total de calabresa utilizada não pode exceder o estoque disponível. • • • Frango: a quantidade total de frango utilizada não pode exceder o estoque disponível. Catupiry: a quantidade total de catupiry utilizada não pode exceder o estoque disponível. Não negatividade: a produção de cada tipo de pizza não pode ser negativa. Solução: O problema pode ser resolvido utilizando o método simplex ou outros métodos de otimização. A solução ótima indicará a quantidade ideal de cada tipo de pizza a ser produzida (muçarela, calabresa e frango com catupiry) para maximizar o lucro total da pizzaria, respeitando as limitações de ingredientes. Exemplo de resultado: Por meio da resolução do problema de PL, a pizzaria pode descobrir que a produção ideal é de: pizzas muçarela pizzas calabresa pizzas frango com catupiry Com essa produção, a pizzaria maximiza o lucro total e utiliza todo o estoque disponível de ingredientes de forma eficiente. Métodos de resolução de problemas de PL Como você sabe,a PL é uma técnica matemática poderosa para otimizar decisões em diversas áreas. Ela permite modelar problemas de otimização com variáveis lineares, restrições e uma função objetivo a ser maximizada ou minimizada. Diversos métodos eficientes foram desenvolvidos para resolver problemas de PL, cada um com suas vantagens e desvantagens. • • • Método gráfico Ideal para problemas com duas variáveis e fácil visualização da solução gráfica. Útil para entender conceitos básicos de PL e para problemas simples. Limitado a problemas com duas variáveis; pode ser difícil encontrar a solução ótima em problemas mais complexos. Método simplex Algoritmo iterativo que busca a solução ótima passo a passo. Amplamente utilizado e eficiente para resolver problemas de PL com diversas variáveis. Pode ser lento para problemas com grande número de variáveis e restrições. Implementado em diversos softwares de otimização. Branch-and-bound Utilizado para resolver problemas de PL com variáveis inteiras. Divide o problema em subproblemas e explora as soluções candidatas de forma eficiente. Pode ser lento para problemas com grande número de variáveis inteiras. • • • • • • • • • • Programação linear inteira mista (MILP) Combinação de PL e programação linear inteira para problemas com variáveis contínuas e inteiras. Abrange uma gama mais ampla de problemas de otimização. Pode ser mais difícil de resolver do que PL pura. Pode ser utilizado o solver do Microsoft Excel. Agora vamos a um resumo importante sobre o que estudamos neste conteúdo! Os fatores na escolha do método são: Tamanho do problema (número de variáveis e restrições). Natureza das variáveis (contínuas, inteiras ou mistas). Complexidade do problema. Disponibilidade de software. Tempo e recursos disponíveis. Conheça os softwares de otimização! GAMS LINDO LINGO CPLEX Solver • • • • • • • • • • • • • • AMPL Python com bibliotecas PuLP, Pyomo Considerações importantes para a escolha do método adequado A escolha do método depende das características do problema e dos recursos disponíveis. É importante ter conhecimento dos diferentes métodos para escolher o mais adequado. Além disso, softwares de otimização facilitam a resolução de problemas de PL e podem ser muito úteis. Escolher o método de resolução de problemas de PL é imprescindível para alcançar a solução ótima de modo eficiente. O conhecimento dos diferentes métodos, suas vantagens e desvantagens, além da utilização de softwares de otimização, permite que você maximize os resultados de sua análise e otimize seus processos de tomada de decisão. Interpretação de resultados Ao resolver um problema de PL, você obtém resultados que fornecem informações valiosíssimas sobre a solução ideal e o cenário otimizado. Vamos entender melhor! Solução ótima A solução de um problema de PL fornece os valores das variáveis de decisão que otimizam a função objetivo, seja maximizando o lucro ou minimizando o custo. Essa solução indica a quantidade ideal de cada recurso a ser alocada para alcançar o objetivo desejado. Valor da função objetivo O valor da FO na solução ótima indica o lucro máximo ou o custo mínimo que pode ser atingido sob as restrições do problema. Esse valor é uma medida da performance da solução e permite comparar diferentes cenários e decisões. Sensibilidade A análise de sensibilidade avalia como a solução ótima muda em resposta a alterações nos parâmetros do problema, como coeficientes da função objetivo, valores de demanda e restrições. Essa análise fornece informações significativas acerca da robustez da solução e ajuda a identificar os parâmetros mais críticos para o problema. Interpretação de sombras As sombras, também conhecidas como preços duais, indicam o valor marginal de cada restrição na solução ótima. Elas revelam o impacto de relaxar cada restrição em uma unidade e podem ser utilizadas para identificar gargalos e oportunidades de otimização. • • Relatórios e outputs Softwares de PL geralmente fornecem relatórios detalhados com a solução, valores da função objetivo, sensibilidade, sombras e coeficientes. É importante analisar esses outputs cuidadosamente para interpretar os resultados e extrair insights relevantes. Confira alguns exemplos de interpretação! Em um problema de otimização de produção, a solução pode indicar a quantidade ideal de cada produto a ser produzida para maximizar o lucro. A análise de sensibilidade pode mostrar como o lucro muda em resposta a alterações no preço de venda de cada produto. As sombras podem indicar quais produtos são mais lucrativos e quais restrições limitam a produção. A interpretação de resultados em PL é fundamental para extrair insights da solução e tomar decisões estratégicas mais informadas. Por meio da análise cuidadosa da solução, da sensibilidade das sombras, você pode compreender o impacto de diferentes variáveis e identificar oportunidades de otimização em seus problemas. Mão na massa Questão 1 Uma empresa de produtos alimentícios precisa determinar a quantidade ideal de biscoitos de chocolate e biscoitos de aveia a serem produzidos para maximizar o lucro. Dados: Lucro por biscoito: Chocolate: R$ 0,50 Aveia: R$ 0,60 Tempo de produção por biscoito: Chocolate: 2 minutos Aveia: 3 minutos • • • • • • • Tempo total disponível de produção: 600 minutos Matéria-prima disponível: Farinha: 120 kg Açúcar: 80 kg Qual modelo matemático soluciona esse problema? Chave de resposta Variáveis de decisão: x: Quantidade de biscoitos de chocolate a serem produzidos. y: Quantidade de biscoitos de aveia a serem produzidos. Modelo matemático: Função objetivo (maximizar lucro): Restrições: Tempo de produção: Matéria-prima: Farinha: • • • • • Açúcar: Não negatividade: Solução: O modelo matemático apresentado pode ser resolvido usando softwares específicos de programação linear, como simplex, LINGO ou solver. A solução ótima para esse problema é a seguinte: x = 200 (biscoitos de chocolate) y = 100 (biscoitos de aveia) Lucro máximo: Interpretação da solução: A empresa deve produzir 200 biscoitos de chocolate e 100 biscoitos de aveia para maximizar o lucro, que será de R$ 160. Análise de sensibilidade: É importante realizar uma análise de sensibilidade para avaliar como a solução ótima muda em resposta a alterações nos parâmetros do problema. Por exemplo, podemos analisar como o lucro máximo muda se o tempo de produção de um biscoito de chocolate aumentar para 3 minutos. • • • • Questão 2 Uma empresa de produção de móveis precisa determinar a quantidade ideal de mesas e cadeiras a serem produzidas para maximizar o lucro. A empresa possui agora 4 tipos de móveis: mesas de madeira, mesas de vidro, cadeiras de madeira e cadeiras de plástico. Dados: Lucro por móvel: Mesa de madeira: R$ 100 Mesa de vidro: R$ 120 Cadeira de madeira: R$ 80 Cadeira de plástico: R$ 70 Tempo de produção por móvel: Mesa de madeira: 2 horas Mesa de vidro: 3 horas Cadeira de madeira: 1 hora Cadeira de plástico: 0,5 horas Tempo total disponível de produção: 80 horas Matéria-prima disponível: Madeira: 120 m² Vidro: 80 m² • • • • • • • • • • • Plástico: 50 m² Qual meio matemático otimiza a produção? Chave de resposta Variáveis de decisão: x1: quantidade de mesas de madeira a serem produzidas. x2: quantidade de mesas de vidro a serem produzidas. x3: quantidade de cadeiras de madeira a serem produzidas. x4: quantidade de cadeiras de plástico a serem produzidas. Modelo matemático: função objetivo (maximizar lucro): Restrições: Tempo de produção: Matéria-prima: Não negatividade: • • • • • • Questão 3 Uma farmácia precisa determinar a quantidade ideal de medicamentos a serem comprados para maximizar o lucro, considerando as restrições de orçamento