24 Agosto 2021

Optimização Linear – Parte I

Atualmente, muitos problemas do quotidiano têm como objetivo encontrar a melhor maneira de executar uma dada tarefa. Muitas vezes, esses problemas podem ser modelados através de uma função para a qual se queira encontrar um valor mínimo ou máximo, tais como o tempo mínimo para fazer uma dada viagem ou o máximo lucro que se pode obter com a venda de uma gama de produtos. Quando tal acontece, estamos perante um problema de optimização [2].

O que é um problema de optimização?

Um problema de optimização tem como objetivo determinar quais os valores atribuir às variáveis de uma função, de modo a minimizar ou maximizar o seu resultado, respeitando as restrições impostas pelo problema [6]. Por outras palavras, um problema de optimização é aquele para o qual se pretende encontrar a melhor solução de entre um conjunto de possíveis soluções. Por vezes, mediante o tipo de problema, encontrar apenas uma solução viável pode ser suficiente.

Este tipo de problemas é comum em áreas como a engenharia e a indústria, tornando-se desafiante quando há um elevado número de variáveis de decisão envolvido. Calcular todas as combinações possíveis e determinar a melhor torna-se numa tarefa inviável, exigindo elevados recursos computacionais [7]. Algumas bibliotecas, como o Google OR-Tools, usam algoritmos que restrigem o conjunto de pesquisa, a fim de encontrar uma solução óptima (ou próxima da óptima) [5].

Um problema típico de optimização e que é bastante conhecido é o Problema de Transporte.

Problema de Transporte

O problema de transporte consiste em minimizar o custo de transporte de uma dada mercadoria desde a origem (ex.: fábricas) até ao destino (ex.: armazéns, clientes finais), respeitando as restrições impostas tanto pela origem (ex.: capacidade máxima de envio de mercadorias), como pelo destino (ex.: número de produtos recebidos pelo armazém, número de produtos encomendados por cada cliente). Para além dessas restrições, é preciso também ter em conta o custo relativo ao envio da mercadoria desde a origem até ao destino (custo de transporte – cij) [1].

Figura 1 – Problema de Transporte

 

A Figura 1 ilustra um cenário típico de um problema de transporte. No cenário representado pela figura, uma empresa possui três fábricas (A, B e C) com diferentes capacidades de produção. As fábricas A, B e C têm capacidade para produzir, diariamente, 500, 400, 200 produtos, respectivamente. Todos os dias, a empresa usa a sua frota de camiões para distribuir os seus produtos por quatro armazéns (1,2,3 e 4). Cada armazém tem capacidade para receber um número mínimo de produtos, por dia. Assim sendo, os armazéns 1, 2, 3 e 4 esperam receber, no mínimo, 80, 270, 160 e 150 produtos, por dia, respectivamente. Há também um custo de transporte fixo relativo à entrega de uma unidade de um produto da fábrica i para o armazém j, tal como representado na Tabela 1.

 

Tabela 1 –  Custos de Transporte da Fábrica i ao Armazém j.

Tendo em conta este cenário, a nossa tarefa consiste em determinar qual a quantidade de produtos que é necessário enviar desde a fábrica i até ao armazém j, de modo a minimizar o custo de transporte e, simultaneamente, satisfazer as necessidades mínimas de recepção dos armazéns, bem como a capacidade máxima de produção de cada uma das fábricas.

Como resolver um problema de optimização?

O primeiro passo para resolver um problema de optimização consiste em construir um modelo de optimização apropriado ao problema em análise. Esse processo consiste em identificar quais as variáveis de decisão do problema para as quais procuramos solução, quais as restrições que é preciso ter em conta e qual a função objetivo que se quer optimizar [3].

  • Variáveis de Decisão: As variáveis de decisão são os components do sistema para os quais queremos encontrar valores. Para o cenário descrito anteriormente as variáveis são a quantidade de produtos que é necessário enviar da fábrica i para o armazém j , podendo ser representada por:

Ex.: = quantidade de produtos enviados da fábrica A para o armazém 1

  • Restrições: As restrições são funções (equações e/ou inequações) que descrevem as relações entre as variáveis de decisão e definem os valores mínimo e máximo que essas variáveis podem ter. No cenário da Figura 1, temos 3 restrições:

1. Capacidade máxima de produção de cada fábrica: as fábricas A, B e C apenas conseguem produzir, no máximo, 500, 400, 200 produtos, respectivamente. Matematicamente, essas restrições podem ser descritas da seguinte forma:

Sendo equivalente a:

 

2. Requisitos mínimos de recepção de cada armazém: Os armazéns 1,2,3 e 4 apenas esperam receber, no mínimo, 80, 270, 160 e 150 produtos, por dia, respectivamente. Matematicamente, essas restrições podem ser descritas como:

O que equivale à seguinte fórmula:

 

3. Quantidade mínima de produtos: A quantidade de produtos enviada da fábrica i para o armazém j terá de ser um número inteiro positivo, maior ou igual a 0. Matematicamente, essas restrições podem ser descritas como:

 

O que equivale a:

 

  • Função Objetivo: A função objetivo representa a quantidade que queremos minimizar ou maximizar. Para o cenário usado como exemplo, a nossa função objetivo terá de ser uma função que calcula o custo de transporte para qualquer quantidade de produtos enviada desde a fábrica i até ao armazém Essa função será usada para identificar quais os valores das variáveis de decisão que garantem o menor custo de transporte total. Matematicamente, a nossa função será definida como:

Equivalente a:

Tendo definido o modelo a optimizar, o segundo passo consiste em identificar o tipo de problema que se quer resolver. Há diferentes tipos de problemas de optimização. Para cada tipo de problema existem diferentes abordagens e algoritmos que permitem encontrar a solução óptima. Como tal, é necessário identificar qual o nosso tipo de problema para que possamos escolher o solver (um algoritmo de procura para encontrar a solução óptima) mais adequado, antes mesmo de qualquer implementação do modelo. O nosso problema de transporte pode ser classificado como um problema de Programação Linear Inteira (Integer Linear Programming), uma vez que as variáveis apenas podem tomar valores inteiros e tanto a função objetivo como as restrições do modelo são representadas como expressões lineares.

Como implementar o modelo que descreve o problema de optimização?

Atualmente, existem várias bibliotecas que podem ser usadas para implementar um modelo de optimização. Essas bibliotecas permitem-nos, modelar, programaticamente, o nosso problema de optimização e invocar um solver para encontrar a sua solução. Os solvers são algoritmos que implementam métodos usados na resolução de problemas de programação linear, tais como o simplex e o branch-and-bound. Uma dessas bibliotecas é o Google OR-Tools.

O que é o Google OR-Tools?

O Google OR-Tools é uma biblioteca open source da Google que disponibiliza um conjunto de API’s de alto nível que permitem modelar diferentes problemas de optimização combinatória. O Google OR-Tools pode ser usado para encontrar a melhor solução para um problema de optimização a partir de um vasto conjunto de soluções possíveis. Eis alguns tipos de problemas onde o OR-Tools pode ser usado [5]:

  • Problemas de Programação Linear (Linear Programming) ou Programação Inteira Mista (Mixed-Integer Programming – algumas variáveis de decisão do modelo podem assumir valores reais ou inteiros). O OR-Tools procura encontrar o melhor valor que a função objetivo pode ter, tendo em conta as restrições do modelo expressas como inequações.
  • Problemas de Restrição (problemas em que o objetivo é encontrar soluções viáveis, tendo em conta um conjunto de restrições impostas pelo modelo. Ex.: uma sala não pode ser usada para 2 eventos simultaneamente).
  • Rotas de veículos (encontrar a melhor rota para um veículo de entre todas as rotas possíveis tendo em conta um conjunto de restrições).
  • Problemas de Grafos (encontrar os caminhos mais curtos num grafo, fluxos de custo mínimo ou máximo)

 

Como implementar um modelo de optimização com o Google OR-Tools?

O Google OR-Tools foi escrito em C++, no entanto pode ser usado em Python, Java ou C#. Independentemente da linguagem escolhida, para implementar um modelo de optimização é necessário executar uma sequência de passos. Esta secção descreve os principais passos na implementação do modelo de optimização linear, aplicado ao cenário do problema de transporte apresentado na Figura 1.

1. Importar as bibliotecas necessárias

Figura 2 – importe das bibliotecas do Google OR-Tools.

 

2. Criar e instanciar o modelo de dados

A criação do modelo de dados é um passo opcional. Para problemas com um maior número de variáveis e restrições pode ser conveniente defini-las num modelo de dados, permitindo assim que o mesmo possa ser iterado sempre que necessário.

Figura 3 – Função de criação do modelo de dados.

 

3. Declarar o solver

O próximo passo consiste em importar e declarar um MIP solver (Mixed Integer Programming solver). Estes solvers são os mais adequados para problemas de programação linear, quando é necessário que algumas ou todas as variáveis assumam valores inteiros. Para este exemplo, optou-se por utilizar o SCIP solver.

Figura 4 – Importe e declaração do SCIP solver

4. Criar as variáveis de decisão

solver.IntVar() é usado para definir o valor mínimo e máximo que uma variável pode ter. No nosso problema de transporte, uma das restrições era a de ter variáveis com valores iguais ou superiores a 0, não havendo um limite máximo estabelecido.

Figura 5 – Variáveis de Decisão.

 

5. Definir as restrições

solver.Add() é utilizado para adicionar cada uma das inequações que representam as restrições do modelo. No cenário em estudo, essas restrições correspondem, não só à capacidade máxima de produção de cada fábrica, como também às necessidades mínimas de recepção de cada armazém.

Figura 6 – Restrições.

 

6. Definir a função objetivo

Na definição da função objetivo, cada um dos termos matemáticos da função que calcula o custo total de transporte é criado e adicionado a um array. No final, é chamada a função solver.Sum() que representa o somatório de todos os termos da função objetivo, bem como a função solver.Minimize(), uma vez que o nosso foco consiste em minimizar o custo total de transporte e descobrir qual a quantidade de produtos que deve ser enviada das 3 fábricas para os 4 armazéns, de modo a que esse custo seja o mais baixo possível.

 

Figura 7 – Função Objetivo.

 

7. Chamar o solver e imprimir os resultados

O último passo, nada mais é que chamar o solver.Solve() e imprimir os resultados, isto é, o valor que cada variável de decisão deve ter, de modo a minimizar o custo de transporte.

Figura 8 – Chamada do solver e impressão dos resultados.

Na Figura 8,  apenas imprimimos as variáveis, cuja variável de decisão é diferente de 0. Através dessa imagem, ficamos a saber que o menor custo de transporte de produtos das fábricas para os armazéns, respeitando as restrições impostas, é de 1680 e pode ser conseguido se enviarmos:

  • 80 produtos da Fábrica A para o Armazém 1 e 160 produtos para o Armazém 3;
  • 270 produtos da Fábrica B para o Armazém 2 e
  • 150 produtos da fábrica C para o Armazém 4.

Em suma, neste artigo vimos o que era um problema de optimização e explorámos um exemplo típico desse tipo de problemas: o problema de transporte. Usando um cenário fictício, vimos como resolver um problema de optimização e como implementá-lo, usando uma biblioteca open source: Google OR-Tools.

No próximo artigo (parte II), veremos como um problema de optimização pode ser aplicado a um caso de uso real.

   
   
    Sabrina Masson                       
     AI Consultant                  

 

Blog