Olá, Mundo!

da programação matemática

Introdução

Olá, Mundo!

Para qualquer pessoa que já tenha feito um curso ou tutorial em uma linguagem de programação, esta última frase é bem conhecida. Sua tradição começou com uma das primeiras linguagens de grande escala de sucesso: C. No livro The C Programming Language (1978), os autores Brian Kernighan e Dennis Ritchie selecionaram a frase para exemplificar a sintaxe de impressão do programa, que o usuário do programa faria ser capaz de ver em um terminal ou tela. Com a evolução das linguagens de programação, a necessidade de exemplos simples para a sintaxe do software persistiu, então o Olá, Mundo! tornou-se o caso introdutório à programação.

Ainda que o modelo matemático não tenha um problema universal para apresentar seus conceitos para iniciantes, existe um um enfoque clássico que é usado frequentemente. Se trata de uma pequena representação de uma decisão empresarial, normalmente com algumas restrições e alavancas, que podem ser facilmente resolvidas desenhando-os em um gráfico.

Inspirado nestes exemplos, o objetivo deste e-book é servir de introdução para a combinação deles no uso de linguagens de programação matemática. Mostar como traduzir um modelo de um problema matemático para as seguintes ferramentas: Python, Java, C++, AMPL e Excel.

O Modelo Matemático

Um fabricante produz dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido a 27 dólares e utiliza 10 dólares em matérias-primas. Cada soldado que é fabricado aumenta os custos de mão de obra e despesas gerais em 14 dólares. Um trem é vendido a 21 dólares e utiliza 9 dólares em matérias primas. Cada trem construído aumenta os custos variáveis e despesas gerais em 10 dólares. A fabricação de soldados e trens de madeira requer dois tipos de mão de obra especializada: carpintaria e acabamento. Um soldado requer 2 horas de trabalho de acabamento e 1 hora de trabalho de carpintaria. Um trem requer 1 hora de trabalho de acabamento e 1 hora de trabalho de carpintaria.

A cada semana, a empresa consegue obter toda a matéria-prima necessária, mas apenas 100 horas de acabamento e 80 horas de carpintaria. A demanda por trens é ilimitada, mas apenas 40 soldados são comprados, no máximo, por semana. A empresa deseja maximizar o lucro semanal. Esta descrição pode ser traduzida no seguinte sistema de equações.

Maximizar Lucro = (27-10-14)×Soldados+ (21-9-10)×Trens

Sujeito à

2×Soldados+Trens ≤100 (Restrição de acabamento)

Soldados+Trens ≤80 (Restrição de carpintaria)

Soldados ≤40 (Demanda de soldados)

Soldados ≥0 (Quantidade mínima de soldados)

Trens ≥0 (Quantidade mínima de trens)

Ferramentas de Implementação

Excel

Python

JAVA

C++

AMPL

Implementação Excel

Embora o Excel não seja propriamente uma linguagem de programação, é uma das ferramentas mais conhecidas do mundo e possui opções de otimização que podem ser usadas para resolver nosso caso base. A primeira coisa a fazer é certificar-se de que o Excel possui o Solver Add-in selecionado para uso. Em seguida, a implementação do problema começa com a construção de tabelas para as entradas do problema, conforme mostrado na Figura 2.

A próxima etapa consiste em definir as saídas do modelo, que são, neste caso, dependentes da quantidade de soldados e trens construídos (Figura 3). Observe que o arquivo está usando o recurso de nomear células, para facilitar a compreensão das fórmulas.

Com a entrada e a saída definidas, é possível criar o modelo de otimização usando o assistente do Excel para esse pop-up (Figura 4) após a ferramenta Solver (Ferramentas> Solver…) ser ativada. A primeira coisa é definir o campo Set Objective (definir objetivo), que seria o H4, denominado Lucro. Então, a seleção To (para) deve ser definida como Max (maximizar), uma vez que o modelo busca o lucro máximo possível. O terceiro campo By Changing Variable Cells (ao se alterar os valores das células) deseja conhecer as variáveis do modelo, que são as células H9 e H10, intervalo denominado Producao_brinquedos. Depois disso, o campo Subject to the Constraints (sujeito às restrições) precisa conhecer cada um dos limites do problema. Cada restrição é adicionada individualmente, como a célula H7 (nomeada Operacao_acabamento) (é menor ou igual a) C15 (nomeada Acabamento), e assim por diante. A última é definir o campo Select a Solving Method (selecione método de resolução), que para este problema linear é Simplex LP.

Com o modelo totalmente formulado, chamando por Solve (resolve), se encontra o resultado ótimo (Figura 5).

Implementação Python

Além de seu ótimo desempenho no tratamento de dados, Python também possui diversas bibliotecas dedicadas a algoritmos de otimização. Esta implementação usa o pacote OR-Tools do Google, importando-o.

from ortools.linear_solver import pywraplp

Depois, é necessário definir a função do modelo que terá todas as declarações do modelo.

def olaMundo():

O primeiro comando da função é definir o objeto que encapsula o modelo, incluindo o solver (GLOP).

# Crie o resolvedor linear com o backend GLOP

resolvedor = pywraplp.Solver.CreateSolver('GLOP')

O próximo passo envolve a declaração das variáveis, usando a função NumVar. Para definir cada variável esta função usa três argumentos, nesta ordem: valor mínimo possível, valor máximo possível e rótulo. Portanto, a declaração está implícita na definição das restrições.

# Crie as variáveis soldados e trens

soldados = resolvedor.NumVar(0, 40, 'Soldados')

trens = resolvedor.NumVar(0, 10000, 'Trens')

Seguido da declaração de restrições, use as funções Constraint e SetCoefficient. O primeiro usa três argumentos, nesta ordem: valor mínimo possível, valor máximo possível e rótulo; enquanto o último usa dois argumentos: a variável e seu coeficiente na restrição.

# Criar restrições de acabamento, 0 <= 2*soldados + trens <= 100

acabamento = resolvedor.Constraint(0, 100, 'acabamento')

acabamento.SetCoefficient(soldados, 2)

acabamento.SetCoefficient(trens, 1)

// Criar restrições de carpintaria, 0 <= soldados + trens <= 80

carpintaria = resolvedor.Constraint(0, 80, 'carpintaria')

carpintaria.SetCoefficient(soldados, 1)

carpintaria.SetCoefficient(trens, 1)

Falta apenas a declaração do objetivo para completar o modelo, cujo formato é similar ao das restrições.

# Criar a função objetivo, 3 * soldados + 2 * trens

lucro = resolvedor.Objective()

lucro.SetCoefficient(soldados, 3)

lucro.SetCoefficient(trens, 2)

lucro.SetMaximization()

Para executar o modelo, tem que chamar a função Solve() do objeto solucionador.

# Solucionar o modelo

resolvedor.Solve()

Finalmente, os resultados podem ser exibidos na interface usando o comando print, como:

print('Lucro = ', lucro.Value())

print('Soldados' = ', soldados.solution_value.Value())

print('Trens' = ', trens.solution_value.Value())

Que retorna o seguinte:

Lucro = 180

Soldados = 20

Trens = 60

Implementação JAVA

Java é bem conhecido por ser uma linguagem orientada a objetos que pode ser executada facilmente em todos os tipos de máquinas e atinge um bom equilíbrio entre velocidade e curva de aprendizado. Essa implementação também usa o pacote OR-Tools do Google, importando as seguintes classes:

import com.google.ortools.Loader;

import com.google.ortools.linearsolver.MPConstraint;

import com.google.ortools.linearsolver.MPObjective;

import com.google.ortools.linearsolver.MPSolver;

import com.google.ortools.linearsolver.MPVariable;

Bibliotecas nativas precisam ser carregadas com o seguinte comando

// Carregar bibliotecas

Loader.loadNativeLibraries();

No típico estilo java, começaremos criando uma classe Model com um campo para o resolvedor, variáveis e função objetivo. Incluiremos um construtor e um método solve na classe:

class Modelo {

private MPSolver resolvedor; // resolvedor linear

private MPVariable soldados; // Variável de soldados

private MPVariable trens; // Variável de trens

private MPObjective lucro; // função objetivo

public Modelo() {..}

public void resolve() {...}

}

No construtor, primeiro definimos o objeto que encapsula o modelo, incluindo o solver (GLOP).

// Iniciar o resolvedor linear com o backend GLOP

resolvedor = MPSolver.createSolver("GLOP");

Também instanciamos as variáveis e declaramos as restrições, que seguem estruturas semelhantes às descritas na seção Python

// Crie as variáveis soldados e trens

soldados = resolvedor.makeNumVar(0, 40, "soldados");

trens = resolvedor.makeNumVar(0, 1000, "trens");

// Criar restrição de acabamento, 0 <= 2*soldados + trens <= 100

MPConstraint acabamento = resolvedor.makeConstraint(0, 100, "acabamento");

acabamento.setCoefficient(soldados, 2);

acabamento.setCoefficient(trens, 1);

// Criar restrição de carpintaria, 0 <= soldados + trens <= 80

MPConstraint carpintaria = resolvedor.makeConstraint(0, 80, "carpintaria");

carpintaria.setCoefficient(soldados, 1);

carpintaria.setCoefficient(trens, 1);

Para completar o modelo, instanciamos o objetivo, que segue estruturas semelhantes às descritas na seção Python

// Criar a função objetiva, 3 * soldados + 2* trens

lucro = resolvedor.objective();

lucro.setCoefficient(soldados, 3);

lucro.setCoefficient(trens, 2);

lucro.setMaximization();

Finalmente, criamos um método solve que chama as ferramentas OR solve e imprime o resultado

public void resolve() {

// Solucionar o modelo

resolvedor.solve();

// Imprimir função objetivo e solução

System.out.println("Soluções: ");

System.out.println("Valor objetivo = " + lucro.value());

System.out.println("soldados = " + soldados.solutionValue());

System.out.println("trens = " + trens.solutionValue());

}

Que retorna o seguinte:

Soluções:

Valor objetivo = 180

soldados = 20

trens = 60

Implementação C++

As linguagens C e C++ são provavelmente as usadas na maioria dos solvers porque são linguagens de alto desempenho. Da mesma forma que as outras implementações, começamos importando as bibliotecas significativas e também usamos o namespace operations_research

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {...}

Dentro do namespace criado, definimos nossa função ola mundo e declaramos o modelo GLOP

void olaMundo() {

// Crie um resolvedor linear com backend GLOP

std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

// …

}

Em seguida, declaramos nossas variáveis e restrições, que seguem estruturas semelhantes às seções anteriores.

// Crie as variáveis soldados e trens

MPVariable* const soldados = solver->MakeNumVar(0, 40, "Soldados");

MPVariable* const trens = solver->MakeNumVar(0, 1000, "Trens");

// Crie a restrição de acabamento, 0 <= 2*soldados + trens <= 100

MPConstraint* const acabamento = solver->MakeRowConstraint(0,100,"acabamento");

acabamento->SetCoefficient(soldados, 2);

acabamento->SetCoefficient(trens, 1);

// Crie a restrição de carpintaria, 0 <= soldados + trens <= 80

MPConstraint* const carpintaria = solver->MakeRowConstraint(0, 80, "carpintaria ");

carpintaria->SetCoefficient(soldados, 1);

carpintaria->SetCoefficient(trens, 1);

Para completar o modelo, declaramos a função objetivo, que segue estruturas semelhantes às seções anteriores.

// Crie a função objetiva, 3 * soldados + 2* trens

MPObjective* const objetivo = solver->MutableObjective();

objetivo->SetCoefficient(soldados, 3);

objetivo->SetCoefficient(trens, 2);

objetivo->SetMaximization();

Para executar o modelo, tem que chamar a função Solve() do objeto solucionador.

// Solucione o modelo

solver->Solve();

std::cout << "Soluções:" << std::endl;

std::cout << "Valor objetivo = " << objetivo->Value() << std::endl;

std::cout << "soldado = " << soldados->solution_value() << std::endl;

std::cout << "trens = " << trens->solution_value() << std::endl;

Finalmente, criamos uma função principal do programa, e chamamos para a função olaMundo().

int main() {

operations_research::olaMundo();

return 0;

}

Que retorna o seguinte:

Soluções:

Valor objetivo = 180

soldados = 20

trens = 60

Implementação AMPL

A A Mathematical Programming Language (AMPL) é dedicada à representação algébrica de modelos e é muito similar à formulação do problema. Uma vez que este software esteja instalado na máquina, abra seu Terminal e abra AMPL usando o comando ampl. A partir daí, a declaração do modelo é direta. A primeira coisa a fazer é definir os conjuntos do modelo:

set Brinquedos;

set Custos;

set Operacoes;

Então, os parâmetros:

param custos_de_producao {b in Brinquedos, c in Custos};

param preco {b in Brinquedos};

param demanda {b in Brinquedos};

param tempo_de_operacao {b in Brinquedos, o in Operacoes};

param horas_de_trabalho {o in Operacoes};

Seguido por variáveis:

var Producao {b in Brinquedos} >= 0;

Em seguida, as restrições do modelo:

subject to restricoes_operacionais {o in Operacoes}:

sum{b in Brinquedos} (Producao[b] * tempo_de_operacao[b,o]) <= horas_de_trabalho[o];

subject to restricoes_demandas {b in Brinquedos}: Producao[b] <= demanda[b];

E finalmente, a função objetivo:

maximize lucro: sum{b in Brinquedos} (Producao[b] * (preco[b] - sum{c in Custos} custos_de_producao[b,c]));

Com todas as estruturas no lugar, resta definir os elementos dos conjuntos e o valor dos parâmetros, usando o comando data:

data;

set Brinquedos := 'Soldados' 'Trens';

set Custos := 'Materias primas' 'Trabalho e despesas gerais';

set Operacoes := 'Acabamento' 'Carpintaria';

param custos_de_producao :

'Materias primas' 'Trabalho e despesas gerais' :=

'Soldados' 10 14

'Trens' 9 10;

param: preco demanda :=

'Soldados' 27 40

'Trens' 21 10000;

param tempo_de_operacao :

'Acabamento' 'Carpintaria' :=

'Soldados' 2 1

'Trens' 1 1;

param horas_de_trabalho :=

'Acabamento' 100

'Carpintaria' 80;

Finalmente, o programador seleciona um solver, usando o comando option, e encontra uma solução, chamando o comando solve. Por exemplo, usamos o Xpress como mecanismo de resolução.

option solver xpress;

solve;

Que imprime a solução no Terminal:

XPRESS 8.5(33.01.05): Optimal solution found

Objective 180

2 simplex iterations

Comparação de tecnologias

Embora todas as abordagens tenham fornecido os mesmos resultados para o caso simples, pode não ser o caso para outros modelos. A escolha tecnológica para o desenvolvimento deve levar em consideração vários outros fatores, tais como: complexidade do modelo, capacidade de processamento, habilidades de programação, orçamento reservado, interface gráfica com o usuário (GUI), sistema de versões, etc.

Por exemplo, o Excel é uma ótima opção para problemas de otimização simples, sendo capaz de gerar facilmente visualizações da solução e alterar os valores dos parâmetros. No entanto, ele tem um baixo número de variáveis que pode considerar e baixa capacidade de processamento; portanto, problemas maiores geralmente estão fora do escopo. Além disso, ele não possui nenhum sistema de controle de versão, o que pode ser confuso se muitos colegas de trabalho usarem o mesmo modelo.

As três principais linguagens de programação listadas, Python, Java e C / C++, são muito semelhantes em suas capacidades de resolver problemas de alta complexidade e possuem poderoso poder de processamento. Ainda tem a vantagem de poderem ser usados gratuitamente e são compatíveis com tecnologias de versionamento, como git. No entanto, criar um aplicativo para mostrar resultados e interagir com os usuários exige excelentes habilidades de programação.

O principal benefício do software AMPL é a divisão clara do modelo e dos dados, mas é a única opção que requer licença, que é gratuita para estudantes e paga para pesquisadores e empresas. AMPL permite que não-programadores modelem facilmente problemas complexos e ainda sejam capazes de alcançar os mesmos níveis de desempenho e sistemas de controle de versionamento de outras linguagens de programação. Além disso, pode contar com uma interface flexível com gráficos e tabelas, chamada Quandec, que possui uma estrutura de dados embutida para gerenciamento de cenários, acesso online, colaboração paralela, ferramentas de comparação e muito mais.

Conclusão

O mundo está repleto de oportunidades de otimização que apenas precisam da ferramenta certa para o trabalho. Esperamos que este e-book tenha adicionado outro em sua caixa de ferramentas. No entanto, se o desafio parece exigir mais experiência em programação matemática, entre em contato com o Cassotis em nossos canais e podemos iniciar uma colaboração.