Problemas, soluções e aplicações de programação linear [com exemplo]

A ciência de dados tem muitas aplicações, uma das mais proeminentes entre elas é a otimização. Todos nós tendemos a nos concentrar em otimizar as coisas. A otimização se concentra em obter os resultados mais desejados com os recursos limitados que você tem.

Existem todos os tipos de problemas de otimização disponíveis, alguns são pequenos, alguns são altamente complicados. Ao passar por eles, você encontrará uma categoria específica chamada problemas de programação linear. Neste artigo, discutimos o que são e como você pode trabalhar com eles.

Suponha que você seja um vendedor de frutas que pode comprar laranjas ou maçãs ou uma certa combinação de ambas. No entanto, você só tem um orçamento de INR 5.000 e só pode armazenar 30 sacos deles. Agora, você tem que comprá-los da maneira que lhe dá o maior lucro.

Agora, um saco de laranjas custa INR 500, enquanto um saco de maçãs custa INR 750. Você pode ganhar INR 100 com a venda de um saco de laranjas e INR 200 com a venda de um saco de maçãs.

Este problema tem várias possibilidades. Você pode optar por comprar apenas laranjas, mas teria apenas 10 sacos em seu armazenamento e seu lucro seria de INR 1.000. Da mesma forma, você pode optar por comprar apenas maçãs e obter INR 1.500 como lucro. Você também pode comprar uma combinação dos dois.

Tais problemas são chamados de problemas de programação linear e vamos discuti-los em detalhes. Vamos começar:

O que é programação linear?

A programação linear é um método de representar relacionamentos complexos usando funções lineares. Nosso objetivo com a programação linear é encontrar as soluções mais adequadas para essas funções. A relação real entre dois pontos pode ser altamente complexa, mas podemos usar programação linear para descrevê-los com simplicidade. A programação linear encontra aplicações em muitas indústrias.

Noções básicas de programação linear

Aqui estão alguns termos fundamentais da programação linear:

Limitação

As limitações (ou restrições) de suas variáveis ​​de decisão são chamadas de restrições. A maioria das restrições de tempo são as limitações que você tem em seus recursos para resolver um problema.

Variável de Decisão

Essas variáveis ​​definem sua saída. Seu resultado depende dessas variáveis, por isso as chamamos de 'variáveis ​​de decisão'.

Restrição de não negatividade

As variáveis ​​de decisão de um problema de programação linear só podem ter valor não negativo. Isso significa que os valores para suas variáveis ​​de decisão podem ser iguais ou maiores que zero apenas.

Função objetiva

A função objetivo é o objetivo de tomar sua decisão. Em termos simples, é o resultado final do seu problema de programação linear. Por exemplo, quando você encontra o lucro máximo que pode obter com um determinado conjunto de recursos, o lucro máximo é a função objetivo.

Formulando Problemas de Programação Linear

Você deve saber como formular uma programação linear para aplicá-la na vida real. Suponha que você seja um fabricante de brinquedos e produza apenas dois brinquedos: A e B. Grosso modo, seus brinquedos requerem dois recursos X e Y para serem fabricados. Aqui estão os requisitos de seus brinquedos:

• Uma unidade de brinquedo A requer uma unidade de recurso X e três unidades de recurso Y

• Uma unidade do brinquedo B requer uma unidade do recurso X e duas unidades do recurso Y

Você tem cinco unidades do recurso X e 12 unidades do recurso Y. Suas margens de lucro na venda desses brinquedos são:

• INR 6 em cada unidade vendida do brinquedo A
• INR 5 em cada unidade vendida do brinquedo B

Quantas unidades de cada brinquedo você produziria para obter o máximo lucro?

A solução

Vamos representar nosso problema de programação linear em uma equação:

Z = 6a + 5b

Aqui, z representa o lucro total, a representa o número total de unidades do brinquedo A e b representa o número total de unidades B. Nosso objetivo é maximizar o valor de Z (o lucro).

Agora, sua empresa gostaria de produzir o maior número possível de unidades desses brinquedos, mas você tem recursos limitados. As limitações dos nossos recursos são as limitações deste problema. Temos apenas um total de

a + b 5

Agora cada unidade do brinquedo A e B requer 3 e 2 unidades do recurso Y respectivamente. E temos apenas um total de 12 unidades de recurso Y, então matematicamente, ficaria assim:

3a + 2b 12

Lembre-se de que os valores das unidades do brinquedo A podem ser apenas em números inteiros. Isso significa que também temos as restrições de a->0 e b<-0.

Então, agora você tem um problema de programação linear adequado. Você pode formular outros problemas de programação linear seguindo este exemplo. Embora este exemplo tenha sido bastante simples, os problemas de PL podem se tornar altamente complicados.

Leia: Ideias e tópicos de projetos de programação linear

Etapas de Formulação de Problemas de Programação Linear

Para formular um problema de programação linear, siga estes passos:

• Encontre as variáveis ​​de decisão
• Encontre a função objetivo
• Identifique as restrições
• Lembre-se da restrição de não negatividade

Se um problema atende aos critérios acima, é um problema de programação linear. É uma prática recomendada manter esse critério em mente ao trabalhar na identificação do tipo de problema.

Resolvendo problemas de programação linear com R

Se você estiver usando R, resolver problemas de programação linear se tornará muito mais simples. Isso porque o R possui o pacote lpsolve que vem com várias funções projetadas especificamente para resolver esses problemas. É altamente provável que você use o R com muita frequência para resolver problemas de LP como cientista de dados. É por isso que compartilhamos dois exemplos distintos para ajudar você a entender melhor sua implementação:

Exemplo

Vamos começar com um problema básico. Uma organização tem dois produtos com preços de venda de INR 25 e INR 20 e são chamados de produto A e B, respectivamente. Todos os dias, eles têm 1800 unidades de recursos para produzir esses produtos. O produto A requer 20 unidades de recursos e B requer 12 unidades de recursos. O tempo de produção para ambos os produtos é de quatro minutos e a organização recebe um total de oito horas de trabalho todos os dias. O problema é: qual deve ser a quantidade de produção de cada um desses produtos para maximizar os lucros da empresa?

Solução:

Vamos começar a resolver este problema definindo sua função objetivo:

max(Vendas) = ​​max( 25 anos 1 + 20 anos 2 )

Aqui, 25 e 20 são os preços do produto A e B respectivamente, y1 é o total de unidades do produto A produzido e y2 é o total de unidades do produto B produzido. Nossas variáveis ​​de decisão são y1 e y2.

Vamos agora definir as restrições para o nosso problema:

Restrição de recursos:

20 anos 1 + 12 anos 2 1800

Restrição de tempo:

4 anos 1 + 4 anos 2 8*60

Nosso objetivo é encontrar o número correto de produtos que temos que fabricar para obter o máximo lucro.

Usando R para resolver o problema:

Usaremos lpsolve para resolver este problema de LP e começaremos com a definição da função objetivo:

> exigir(lpSolve)

Carregando o pacote necessário: lpSolve

> objetivo.in <- c(25, 20)

> objetivo.in

[1] 25 20

Então vamos construir uma matriz para as restrições:

> const <- matriz(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> const

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> resource_constraints <- 1800

> restrições de tempo

[1] 480

> resource_constraints

[1] 1800

Vamos agora criar as equações já definidas:

> rhs <- c(resource_constraints, time_constraints)

> rh

[1] 1800 480

> direção <- c(“<=”, “<=”)

> direção

[1] “<=” “<=”

Assim que todas as informações necessárias forem adicionadas, podemos começar a encontrar a resposta ideal. A sintaxe do nosso pacote é:

lp( direção, objetivo, const.mat, const.dir, const.rhs )

> ótimo <- lp(direction=”max”, object.in, const, direction, rhs)

> ótimo

Sucesso: a função objetivo é 2625

> resumo (ótimo)

Modo de Classe de Comprimento

direção 1 -nenhum- numérico

x.count 1 -none- numérico

objetivo 2 -nenhum- numérico

const.count 1 -none- numérico

restrições 8 -nenhum- numérico

int.count 1 -none- numérico

int.vec 1 -nenhum- numérico

bin.count 1 -none- numérico

binário.vec 1 -nenhum- numérico

num.bin.solns 1 -none- numérico

objval 1 -nenhum- numérico

solução 2 -nenhuma- numérica

pré-resolver 1 -nenhum- numérico

compute.sens 1 -none- numérico

sens.coef.from 1 -none- numeric

sens.coef.to 1 -none- numérico

duais 1 -nenhum- numérico

duals.from 1 -none- numérico

duals.to 1 -none- numérico

escala 1 -nenhum- numérico

use.dense 1 -none- numérico

denso.col 1 -nenhum- numérico

denso.val 1 -nenhum- numérico

denso.const.nrow 1 -none- numérico

denso.ctr 1 -none- numérico

use.rw 1 -none- numérico

tmp 1 -nenhum- caractere

status 1 -nenhum- numérico

Após executar o código acima, você pode obter as soluções desejadas para o nosso problema.

Os valores ótimos para y1 e y2:

Lembre-se que y1 e y2 eram as unidades do produto A e do produto B que tínhamos que produzir:

> ótima$solução

[1] 45 75

O valor ideal de vendas:

O lucro máximo que podemos gerar com os valores obtidos de y1 e y2 é:

> ótimo$objval

[1] 2625

Leia também: Álgebra Linear para Aprendizado de Máquina

Usos da programação linear

Como mencionamos anteriormente, a programação linear encontra aplicações em muitos setores. Aqui estão algumas áreas onde nós o usamos:

• Com a crescente popularidade dos serviços de entrega, a programação linear tornou-se um dos métodos mais favorecidos para encontrar as rotas ideais. Quando você pega um Ola ou Uber, o software usa programação linear para encontrar a melhor rota. Empresas de entrega como Amazon e FedEx também o usam para determinar as melhores rotas para seus entregadores. Eles se concentram na redução do tempo e custo de entrega.
• O aprendizado supervisionado do aprendizado de máquina trabalha os conceitos fundamentais da programação linear. No aprendizado supervisionado, você precisa encontrar o modelo matemático ideal para prever a saída de acordo com os dados de entrada fornecidos.
• O setor de varejo utiliza programação linear para otimizar o espaço nas prateleiras. Com tantas marcas e produtos disponíveis, determinar onde colocá-los na loja é uma tarefa muito rigorosa. A colocação de um produto na loja pode afetar muito suas vendas. Grandes cadeias de varejo, como Big Bazaar, Reliance, Walmart, etc. usam programação linear para determinar a colocação de produtos. Eles têm que manter o interesse dos consumidores em mente, garantindo a melhor colocação do produto para gerar o máximo de lucro.
• As empresas usam programação linear para melhorar suas cadeias de suprimentos. A eficiência de uma cadeia de suprimentos depende de muitos fatores, como rotas escolhidas, horários, etc. Usando programação linear, eles podem encontrar as melhores rotas, horários e outras alocações de recursos para otimizar sua eficiência.

Saiba mais sobre programação linear e ciência de dados

A programação linear é um dos conceitos mais vitais da ciência de dados. Também é um tópico fundamental que você deve conhecer para se tornar um cientista de dados proficiente. Como discutimos, existem muitas aplicações para esse conceito e você pode encontrar seus casos de uso no seu dia a dia.

Você pode aprender mais sobre ciência de dados e seus conceitos relacionados, acessando nosso blog. Temos muitos recursos valiosos para ajudá-lo a aprender mais. Aqui estão alguns para sua leitura adicional:

• Principais motivos para se tornar um Cientista de Dados
• Os algoritmos que todo cientista de dados deve conhecer
• Como se tornar um cientista de dados

Por outro lado, você pode obter um curso de ciência de dados para aprender com especialistas do setor. Você aprenderá interativamente por meio de vídeos, questionários e projetos. Fazer um curso ajudará você a aprender as habilidades necessárias para se tornar um cientista de dados profissional. Confira o PG Diploma in Data Science do IIIT-B & upGrad, criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1-on-1 com mentores do setor, mais de 400 horas de aprendizagem e assistência ao emprego com as principais empresas.