Programação Linear: entenda o que é e como utilizá-la!

A Programação Linear é uma técnica matemática utilizada para resolver problemas de otimização em que se busca maximizar ou minimizar uma função linear sujeita a um conjunto de restrições lineares.

A maneira de realizar cálculos mudou muito com o surgimento dos computadores e com o avanço da Engenharia da Computação. E sem dúvidas a Programação Linear tem um grande peso para essa evolução!

A parte teórica sempre se manteve igual, a diferença é que com o avanço dos algoritmos de computadores, foi possível realizar muito mais cálculos em um período de tempo muito menor.

Se deseja aprender um pouco mais sobre programação linear e onde ela pode ser aplicada, fique aqui conosco. Separamos alguns tópicos para auxiliar você nesta jornada:

O que é Programação Linear?
História da Programação Linear;
Qual o objetivo da Programação Linear?
Onde se aplica a Programação Linear?
Exemplo de exercício resolvido com Programação Linear.

Vamos à leitura?

O que é Programação Linear?

A Programação Linear é um tipo de programação que busca sempre obter o melhor resultado matematicamente possível de um modelo. Esse modelo deve ser composto apenas por relações lineares.

Em outras palavras, a Programação Linear é um método para otimizar processos lineares que estão sujeitos a restrições por meio de variáveis reais.

A Programação Linear nada mais é do que uma técnica para a Pesquisa Operacional, termo que será apresentado abaixo e ajudará você a conectar os pontos.

O que é Pesquisa Operacional?

A Pesquisa Operacional é um campo do conhecimento no qual se busca estudar, desenvolver e aplicar métodos analíticos para conseguir auxiliar na hora da tomada de decisão. Pode ser tanto aplicada para problemas simples quanto para problemas mais complexos.

Vale ressaltar, que apesar do computador realizar os cálculos, cada usuário dependerá da capacidade analítica de cada um para gerar os inputs e analisar os dados.

Este termo surgiu com o interesse em gerenciar de forma eficiente operações de logística militar. Mas com o avanço da tecnologia como um todo, a pesquisa operacional passou a ser usada em diversas outras áreas de atuação.

Aplicações da Pesquisa Operacional

Continental Airlines: A empresa conseguiu otimizar o processo de realocação da tripulação quando ocorria desajustes do horário dos voos. Com isso, foi possível uma economia anual de 40 milhões de dólares;
Samsung: Conseguiu reduzir o lead time e os níveis de estoque da fábrica tendo uma economia anual de 200 milhões de dólares;
General Motors: Otimizou e aumentou a eficiência das suas linhas de produção. Economizando anualmente 90 milhões de dólares;
Sears: Aplicou a Pesquisa Operacional na programação de rotas de veículos para realizar entregas e também atendimento. Gerando uma economia anual de 42 milhões de dólares;
Hewlett-Packard: Reformulou o tamanho do estoque de segurança e o local onde ele era mantido na fábrica para atender às metas de produção de impressoras. Como consequência, a empresa aumentou seu faturamento de 1998 em 280 milhões de dólares.

Quer dar os primeiros passos no mundo da programação com Python?

Então baixe agora mesmo nosso ebook gratuito "Primeiros Passos com Python" e mergulhe nessa poderosa linguagem.

Aprenda os conceitos básicos, descubra como escrever seus primeiros programas e desvende os segredos por trás dessa linguagem tão popular.

Não perca tempo, clique no banner abaixo e faça o download gratuito do ebook "Primeiros Passos com Python".

História da Programação Linear

Tudo começou por volta de 1827, quando o matemático francês Fourier publicou um método para a resolução de problemas com desigualdades lineares que foi chamado de método de eliminação Fourier-Motzkin.

Em meados de 1939, o matemático e economista Leonid Kantorovich desenvolveu uma formulação de programação linear. Isso pode ser aplicado durante a segunda guerra mundial, com o objetivo de planejar gastos e retornos, sendo possível reduzir os custos do exército.

Durante essa mesma época, o economista holandês TC Koopmans foi responsável por fazer a formulação de problemas clássicos relacionados à economia em algoritmos de Programação Linear.

Pouco mais tarde, em 1975, Kantorovich e Koopmans dividiram o prêmio Nobel de economia.

Em 1941, Frank Lauren propôs fórmulas sobre transporte através dos algoritmos lineares. Alguns anos depois, Frank acabou falecendo e não recebendo o prêmio Nobel.

Por volta de 1947, George B. Dantzig criou de maneira independente uma formulação de algoritmos lineares para utilizar na resolução de problemas e otimização de processos do planejamento da Força Aérea dos Estados Unidos.

Dantzig também foi a pessoa responsável por criar o método chamado de simples, esse método aborda diversos problemas de programação linear.

Em 1951, Dantzig teve um de seus trabalhos disponibilizados para o público, intitulado de “A Theorem on Linear Inequalities”. Este trabalho foi muito importante, pois diversas indústrias passaram a aplicá-lo em seu dia a dia.

A Theorem on Linear Inequalities

Em seu relatório, Dantzig utilizou de exemplo encontrar a melhor combinação de 70 pessoas para 70 empregos.

Para resolver este tipo de problema, seria necessário um poder de computação impossível para a época, pois seria necessário verificar um número muito grande de permutações e selecionar a melhor.

No entanto, Dantzig, observou que por meio do software Simplex, levaria menos tempo para encontrar a solução ideal, isto porque, o algoritmo era capaz de diminuir consideravelmente o número de soluções possíveis que precisavam ser verificadas.

Qual o objetivo da Programação Linear?

A Programação Linear é uma área da Pesquisa Operacional muito utilizada, com o objetivo de resolver problemas na prática que possam ser expressos através de equações lineares.

Alguns casos especiais de Programação Linear, como o problema de fluxo de network, foi responsável por gerar muitas pesquisas sobre os algoritmos de PL especializados para a sua solução.

Ao passar dos anos, as ideias relacionadas a programação linear tiveram inspiração em conceitos da teoria de otimização, como por exemplo, a dualidade e a decomposição.

A PL também foi muito utilizada no início da microeconomia, tendo papel fundamental para seu surgimento. Atualmente, a PL é usada na gestão de diversas empresas com o objetivo de melhoramento de processos, como o de planejamento da produção, transporte, entre outros.

Apesar da gestão das empresas estar em constante mudança, todas elas têm o objetivo de maximizar os lucros e minimizar os gastos de recursos. E para situações similares a esta, a Programação Linear consegue cumprir seu papel com excelência.

Onde se aplica a Programação Linear?

Além de diversas áreas da pesquisa, a Programação Linear pode ser aplicada também dentro da indústria.

É muito utilizada na matemática, economia, negócios e engenharia. Dentro da indústria, a Programação Linear costuma otimizar e resolver problemas de transporte, energia, telecomunicações, manufatura etc.

Sua aplicação consiste na tomada de decisão que será necessária para atingir um objetivo. Otimizando o processo e alocando os recursos da melhor maneira possível.

E além disso, a PL tem se mostrado muito eficaz para modelagem de problemas de planejamento, programação e design.

Exemplo de exercício resolvido com Programação Linear

Um exemplo de exercício de programação linear é o seguinte:

O Problema

Suponha que uma empresa produza dois produtos: A e B. O produto A requer 2 horas de trabalho para ser fabricado e o produto B requer 3 horas de trabalho.

A empresa possui disponível um total de 80 horas de trabalho por semana.

O lucro por unidade vendida do produto A é de R$10 e do produto B é de R$15.

Além disso, há uma restrição de demanda, sendo que o máximo de unidades do produto A que podem ser vendidas é 50 e o máximo de unidades do produto B é 40.

O objetivo é determinar a quantidade de cada produto que a empresa deve produzir para maximizar o lucro total, respeitando as restrições de disponibilidade de horas de trabalho e de demanda.

Resolução

Para resolver esse problema, pode-se utilizar métodos como o método gráfico, o método Simplex ou softwares específicos de programação linear.

Vamos atribuir as seguintes variáveis de decisão:

x = quantidade de unidades do produto A a ser produzida;
y = quantidade de unidades do produto B a ser produzida.

A função objetivo será maximizar o lucro total, que é dado por:

Lucro Total = 10x + 15y

Sujeito às seguintes restrições:

2x + 3y ≤ 80 (restrição de disponibilidade de horas de trabalho);
x ≤ 50 (restrição de demanda para o produto A);
y ≤ 40 (restrição de demanda para o produto B);

Podemos resolver esse problema utilizando o método Simplex, que é um método computacional para resolver problemas de programação linear. Após a resolução, obtemos os seguintes resultados:

x = 40 (quantidade de unidades do produto A a ser produzida);
y = 13.33 (quantidade de unidades do produto B a ser produzida).

O lucro total máximo alcançado é de R$766,67.

Lembrando que a quantidade de unidades deve ser um valor inteiro, então podemos arredondar a quantidade de unidades do produto B para o valor mais próximo, ficando:

x = 40 (quantidade de unidades do produto A a ser produzida);
y = 13 (quantidade de unidades do produto B a ser produzida).

Nesse caso, o lucro total máximo alcançado seria de R$760.

Portanto, para maximizar o lucro total, a empresa deve produzir 40 unidades do produto A e 13 unidades do produto B.

Por fim, esperamos que esse artigo tenha sido proveitoso para você e agregado ao seu conhecimento. Não deixe de acompanhar o Blog Voitto para mais conteúdos parecidos como esse, e não deixe de conferir nossa dica para você!

Aprenda a programar em Python de forma prática e eficiente!

Conheça nosso curso de Fundamentos em Python e dê o primeiro passo rumo ao domínio dessa linguagem poderosa.

Com aulas interativas, exemplos e exercícios práticos, você vai dominar os fundamentos essenciais e se tornar um programador versátil.

Não perca tempo, aproveite essa oportunidade de expandir seus conhecimentos e impulsionar sua carreira! Garanta sua vaga gratuitamente com o cupom BLOG100!