Otimização: implementando a programação linear

Problema e primeira solução - Apresentação

Olá, boas-vindas a este curso de Otimização com Programação Linear, ministrado pelo Allan Spadini.

Autodescrição: Allan se considera um homem branco, com cabelos e olhos castanhos e veste uma camiseta azul-escura. Ao fundo, há algumas espumas hexagonais e luzes verdes e azuis incidindo na parede.

Neste curso, vamos estudar o projeto desenvolvido por Judecir Cavalcante. Nele, nosso objetivo será maximizar o lucro de uma fazenda. Para isso, teremos que lidar com os recursos limitados dessa fazenda e também com as restrições atreladas a esse problema.

Ao finalizar o curso, você será capaz de lidar com problemas de minimização ou maximização de funções lineares. Para acompanhar o curso, é necessário ter um conhecimento básico de programação em Python (Python).

Então, esperamos você nos próximos vídeos. Até lá!

Problema e primeira solução - Problema da produção de alimentos

Neste curso, queremos resolver o problema da Fazenda Verde Vida, que deseja maximizar o lucro em suas operações, mas cultiva apenas tomates e alfaces. Como podemos entender esse problema?

Vamos começar escrevendo as características do problema para entender como vamos resolvê-lo. Podemos pensar que estamos lidando com o quilo de alimentos. Portanto, vamos escrever um comentário indicando que estamos trabalhando com lucro por quilo de cada tipo de alimento.

Vamos criar um dicionário chamado lucro_por_tipo, que será igual a {}, e passar o primeiro tipo de alimento, que é o tomate. Temos um lucro de R$2,00 por quilo de tomate plantado. Portanto, temos aqui o lucro por cada tipo de alimento, R$2,00 por 1 quilo de tomate plantado. Para a alface, temos "Alface": 1.50. Portanto, temos um lucro de R$2,00 para 1 quilo de tomate plantado e um lucro de R$1,50 para o quilo de alface plantado.

# Lucro por quilo de cada tipo de alimento
lucro_por_tipo = {
    "Tomate": 2.00,
    "Alface": 1.50
}

Parece que se começarmos a plantar tomate, vamos maximizar o lucro da fazenda, certo? Mas não é só isso. Temos algumas características do problema que precisam ser alcançadas na resolução dele.

Primeiro de tudo, temos recursos limitados, não podemos simplesmente começar a plantar infinitamente, temos um limite de terra, da área da fazenda, também temos um limite de água que podemos usar, por exemplo, para resolver esse problema.

Vamos escrever a demanda por tipo de alimento plantado. Vamos colocar dentro de um novo dicionário, chamado demanda_por_tipo, e vamos dar igual a {}, e agora vamos colocar novamente o tomate, "Tomate": {}, e agora o primeiro recurso que mencionamos, a água. Então, "agua": 3.

Precisamos de 3 litros de água para plantar os tomates. Mas também precisamos de espaço em terra para plantar os tomates. Então, vamos colocar aqui "espaco": 2, e agora vamos colocar os recursos relacionados à alface.

Então, "Alface": {}, e agora vamos implementar a água, "agua": 2. Ou seja, precisamos de 2 litros de água para plantar a alface, e precisamos de mais espaço para plantar a alface. Precisamos de "espaco": 3.

Agora o problema ficou um pouco mais complexo. Talvez não consigamos resolvê-lo exatamente de cabeça. Temos um lucro maior de tomate, mas ao mesmo tempo precisamos de mais água para plantá-lo. Então, dependendo dos nossos recursos, pode ser mais favorável dividir, plantar parte de tomate, parte de alface.

# Demanda de recursos por quilo de cada tipo de alimento
# Agora, removemos o 'tempo_cuidado' e ajustamos as quantidades de água e espaço
demanda_por_tipo = {
    "Tomate": {"agua": 3, "espaco": 2},
    "Alface": {"agua": 2, "espaco": 3}
}

Vamos entender agora qual é a nossa disponibilidade total desses recursos. Pressionaremos o atalho Shift + Enter e vamos colocar a disponibilidade de recursos, mais um dicionário, que vai receber a água e o espaço. Então, disponibilidade_recursos, que será igual a {}, e agora vamos passar "agua": 5900, e "espaco": 5400.

# Disponibilidade total de recursos na fazenda
disponibilidade_recursos = {
    "agua": 5900,
    "espaco": 5400
}

Agora sabemos a disponibilidade de recursos, e um primeiro caminho que poderíamos pensar em resolver esse problema seria por tentativa e erro. Tentar alocar, por exemplo, uma quantidade X de tomates, depois uma quantidade X de alface, e verificar como essas restrições se dão no decorrer desse problema.

No próximo vídeo, agora que já entendemos algumas das características do problema, que temos uma demanda por recursos, que temos a disponibilidade de recursos, vamos fazer uma primeira tentativa de resolver esse problema. Até o próximo vídeo.

Problema e primeira solução - Primeira ideia de resolução

No vídeo anterior, implementamos as características do problema. Observamos que temos um lucro por determinado tipo de alimento plantado e também uma demanda de recursos por determinado tipo de alimento. Precisamos utilizar 3 litros de água ou 2 metros quadrados de espaço para plantar o tomate, por exemplo. Mas como isso impacta a nossa produção?

A primeira questão que vamos tentar determinar é o máximo de tomates que conseguimos produzir no total. Para isso, temos uma fórmula pré-implementada. Essa fórmula calcula a água disponível pela água necessária por quilo de tomate. Isso vai retornar a quantidade em quilos de tomate que conseguimos plantar relacionada à água disponível, ao total de água disponível. Portanto, é o máximo de tomates que conseguimos plantar em relação à água disponível.

O mesmo se aplica ao espaço. Teremos o máximo de tomates que conseguimos plantar relacionado ao espaço. Se o fator espaço limita a quantidade total de tomates que conseguimos plantar mais do que a água, por exemplo, se conseguimos plantar 2.000 quilos de tomate em relação à água disponível, mas só 1.500 quilos de tomate relacionado à quantidade de espaço disponível, teremos que pegar o valor mínimo que conseguimos plantar, porque, na verdade, esse valor é o máximo que conseguimos plantar.

Não adianta ter 3 litros de água para plantar tomate se só temos um espaço que nos limita a plantar 1.500 quilos de tomate. Portanto, vamos pegar o valor mínimo do resultado dessa conta. Isso vai retornar o máximo possível de tomate que conseguimos plantar.

Determinando a produção máxima

Para implementar isso, vamos fazer o cálculo do max_tomate, que será igual ao mínimo (min) da disponibilidade de recursos (disponibilidade_recursos) de água, dividido pela demanda por tipo de tomate (demanda_por_tipo['tomate']['agua']). Faremos o mesmo para o uso da terra, para o nosso espaço disponível. Copiaremos essa linha e colaremos na linha debaixo, substituindo agua por espaco.

# Cálculo do máximo que pode ser produzido para cada tipo de vegetal
max_tomate = min(
    disponibilidade_recursos["agua"] / demanda_por_tipo["Tomate"]["agua"],
    disponibilidade_recursos["espaco"] / demanda_por_tipo["Tomate"]["espaco"]
)

A mesma coisa acontece para a alface. Basta implementar um max_alface, que vai receber o valor alface, e assim resgatamos os valores dos nossos alfaces disponíveis.

max_alface = min(
    disponibilidade_recursos["agua"] / demanda_por_tipo["Alface"]["agua"],
    disponibilidade_recursos["espaco"] / demanda_por_tipo["Alface"]["espaco"]
)

Vamos verificar quanto de tomate conseguimos produzir. max_tomate será igual a 1.966 quilos, aproximadamente, e max_alface será aproximadamente 1.800 quilos.

Testando diferentes quantidades de alface e tomate

Isso está relacionado ao máximo de alface e ao máximo de tomate que conseguimos produzir. Mas, qual a combinação de tomate e de alface que conseguimos produzir?

Antes de mais nada, temos uma restrição. Não podemos produzir só tomate ou só alface. Temos que produzir pelo menos 10% de tomate em relação à quantidade de alface produzida.

Agora queremos implementar uma função que permita testar, para diferentes combinações de alface e tomate, qual o lucro que estamos obtendo e se essa quantidade de tomate e de alface está infringindo ou não essa restrição de quantidade de espaço e de água que vamos usar para produzir.

Vamos implementar essa função e o nome dela será calcular_lucro_e_viabilidade.

A primeira coisa que vamos calcular é a quantidade de água que estamos usando. Qual é o nosso uso da água? uso_agua será a quantidade de alface, vezes a demanda por tipo de alface (demanda_por_tipo['alface']['agua']), mais a quantidade de tomate, vezes a demanda por tipo de tomate (demanda_por_tipo['tomate']['agua']).

A mesma coisa para o espaço, queremos saber a quantidade de espaço que estamos utilizando. Nesse caso, basta copiar essa fórmula e o uso_espaco será exatamente a mesma fórmula do uso_agua, basta substituir a água por espaço, que ele vai resgatar os recursos que já adicionamos ao nosso dicionário.

def calcular_lucro_e_viabilidade(qtd_tomate, qtd_alface):
    # Calcula o uso total de água e espaço para as quantidades escolhidas de tomate e alface
    uso_agua = qtd_tomate * demanda_por_tipo["Tomate"]["agua"] + qtd_alface * demanda_por_tipo["Alface"]["agua"]
    uso_espaco = qtd_tomate * demanda_por_tipo["Tomate"]["espaco"] + qtd_alface * demanda_por_tipo["Alface"]["espaco"]

Temos o uso total da água e o uso do espaço. E agora queremos verificar isso em relação às nossas restrições.

Vamos escrever as restrições dentro de um dicionário. restricoes será igual a um dicionário com a água e a quantidade de água que conseguimos usar está atrelada ao nosso uso_agua. Esse dicionário de restrições vai servir para verificar o nosso uso da água.

Agora vamos ter também o espaço, que vai receber o uso_espaco, e a condição que mencionamos da diversificação. Essa condição, por enquanto, vai receber a quantidade de alface e a quantidade de tomate que estamos plantando no momento.

restricoes = {"agua": uso_agua, "espaco": uso_espaco, "diversificacao": (qtd_alface, qtd_tomate)}

Tendo esse dicionário de restrições, verificamos se viola ou não as restrições.

Vamos escrever uma regra, viola_restricoes, que será igual a uma condição que verifica se uso_agua é maior do que a disponibilidade de recursos de água (disponibilidade_recursos['agua']), ou se uso_espaco é maior do que a disponibilidade de recursos de espaço (disponibilidade_recursos['espaco']), ou se a quantidade de tomate é menor que 10% da quantidade de alface.

    # Verifica se a combinação de produção viola as restrições de recursos e diversificação
    viola_restricoes = (
        uso_agua > disponibilidade_recursos["agua"] or
        uso_espaco > disponibilidade_recursos["espaco"] or
        qtd_tomate < 10/100*qtd_alface

Por fim, vamos calcular o nosso lucro total, que será igual a quantidade de tomate vezes o lucro por tipo de tomate (lucro_por_tipo['tomate']), mais a quantidade de alface, vezes o lucro por tipo de alface (lucro_por_tipo['alface']).

Agora temos os elementos relacionados ao lucro e às restrições implementadas, e queremos retornar o lucro, viola_restricoes, e as nossas restrições, para avaliar.

    # Calcula o lucro total
    lucro = qtd_tomate * lucro_por_tipo["Tomate"] + qtd_alface * lucro_por_tipo["Alface"]

    return lucro, viola_restricoes, restricoes

Vamos testar, por exemplo, a quantidade de 16 quilos de tomate e 0 quilos de alface. Chamaremos a função calcular_lucro_e_viabilidade com 16 quilos de tomate e 0 quilos de alface. Após executar a linha de código, o retorno será:

(32.0, False, {'agua': 48, 'espaco': 32, 'diversificacao': (0, 16)})

A função calcular_lucro_e_viabilidade retorna primeiro o lucro, que foi de 32 reais, e retorna o parâmetro falso, porque de acordo com o nosso viola_restricoes, aparentemente ele não viola as restrições.

Temos as características do nosso dicionário de restrições, que temos 48 litros de água utilizados, 32 metros quadrados de espaço utilizados, e dentro da nossa diversificação, estamos usando 0 quilos de alface e 16 quilos de tomate.

O detalhe aqui é que ele retornou falso, porque a quantidade de tomates é menor do que a quantidade de alface, do que 10% da quantidade de alface, porque não plantamos nenhum tomate, então, a quantidade de tomates não tem como ser menor do que esses 10% de alface. Nesse caso ele não violou essa restrição, temos que ter tomate, mas podemos não ter alface de acordo com essa restrição.

No próximo vídeo, vamos testar diversas vezes essas restrições para entender melhor o funcionamento dessas funções. Até o próximo vídeo.

Sobre o curso Otimização: implementando a programação linear

O curso Otimização: implementando a programação linear possui 117 minutos de vídeos, em um total de 47 atividades. Gostou? Conheça nossos outros cursos de Machine Learning em Data Science, ou leia nossos artigos de Data Science.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Problema e primeira solução
• Solução gráfica
• Tipos de saída do modelo
• Resolvendo o modelo com solver
• Análise de sensibilidade