O número de Bacon, e o algoritmo da distância mínima

O prolífico ator Kevin Bacon fez, um dia, uma declaração de que já trabalhou com todo mundo em Hollywood. Realmente, ele está na ativa desde os anos 80, trabalhando em dúzias de filmes como JFK, Apollo 13 e até X-Men First Class.

Baseado nesta afirmação e na Teoria dos Seis Graus de Separação, cientistas de dados criaram o “Número de Bacon”: qual a distância mínima entre Bacon e cada ator que já atuou em filmes.

Este site mostra o número de Bacon: https://oracleofbacon.org/movielinks.php

Exemplos:

O grande Tarcísio Meira tem número de Bacon 3. Trabalhou com Luc Merenda em “OSS 117 takes a vacation”, que por sua vez trabalhou com Tomas Milian em “Silent Action”, que trabalhou com Bacon em “JFK”.

O habilidoso Bruce Lee tem número de Bacon 3.

Note que pode haver mais de um caminho mínimo possível, por isso o botão “Find a different link”.

A “Mulher Maravilha” Gal Gadot tem número de Bacon 2.

E o “Capitão Nascimento” Wagner Moura, número de Bacon 2.

Há vários atores brasileiros que não constam na lista, quando mexemos no site. Neste caso, eles têm número de Bacon infinito.

Mundo Pequeno

É bem difícil encontrar algum ator que tenha uma distância de Bacon grande (a maior distância que encontrei foi 3 – mas eu também não tenho lá grande conhecimento de nomes de atores). O mundo de Hollywood é muito menor que o mundo real.

Porém, mesmo no mundo real, existe a teoria do “Mundo Pequeno”. Na média, 6 conexões separam quaisquer duas pessoas no mundo. Entre eu e o presidente dos EUA, eu conheço alguém que conhece alguém que conhece alguém que conhece alguém que conhece alguém que conhece o presidente.

Esta teoria é utilizada para entender a topologia de uma rede. Exemplo. O Facebook reportou distância média de 4,57, em 2016, baseado em 1,6 bilhão de usuários.

Outra reflexão é a dos superconectores. Há pessoas que são super elos, aqueles que conhecem muita gente, e que devem ser atingidos para que uma mensagem passe adiante.

Note que é a distância mínima que vale, o que nos leva à seguinte pergunta.

Como funciona o algoritmo do caminho mínimo?

O algoritmo consiste em encontrar o menor caminho num grafo. A ideia básica é simples, vamos tentar exemplificar com um hipotético “Número de Romário”.

Digamos que eu tenha as seguintes listas (resumidas, a bem da simplicidade):

Seleção Brasileira de 1994:

  • Taffarel
  • Dunga
  • Cafu
  • Bebeto
  • Romário

Seleção Brasileira de 1998:

  • Taffarel
  • Dunga
  • Cafu
  • Rivaldo
  • Ronaldo

Seleção Brasileira de 2002:

  • Dida
  • Cafu
  • Ronaldinho Gaúcho
  • Rivaldo
  • Ronaldo

Seleção Brasileira de 2006 (quadrado mágico):

  • Ronaldinho Gaúcho
  • Ronaldo
  • Adriano
  • Kaká

Quero calcular o “Número de Romário”, para todos os envolvidos.

Começo com a seleção de 1994. Todo mundo que jogou junto com Romário tem conexão 1:

Na seleção de 1998, Romário não jogou (porque o Zagallo não gostava dele, uma injustiça, diga-se de passagem!).
Primeiro, faço uma varredura se os nomes de 1998 já foram contabilizados.

Taffarel, Dunga e Cafu já estão na lista, então não entram.

Já Rivaldo e Ronaldo, podem ser ligados via qualquer um dos três, vamos mostrar só a conexão com Cafu, por simplicidade. Eles terão distância 2.

Em 2002, dois novos nomes: Dida e Ronaldinho Gaúcho.

Eles podem ser ligados via Rivaldo ou Ronaldo – mas aí a distância vai ser 3.

Ou eles podem ser ligados via Cafu (um superconector), e a distância vai ser 2. Como queremos a menor distância, vale esta conexão.

Em 2006, dois novos nomes: Adriano e Kaká.
Eles podem ser ligados por Ronaldo, e aí vão ter distância 3.

Este não é o único algoritmo possível, existem diversas outras alternativas, com seus prós e contras. Encontrar distâncias em grafos pode ser utilizada em roteirização (como o Waze).

Note também que Romário e Ronaldo já jogaram juntos, na vida real. Aqui, é só ilustrativo.

Exercício

A seleção de 2010 era muito ruim, nem vale muita consideração, mas suponha que foi essa a convocação simplificada:

  • Daniel Alves
  • Robinho
  • Kaká
  • Luis Fabiano

Qual o “Número de Romário” do Robinho e do Luis Fabiano?

Veja também:

Guten Tag, Hannover!

I’m attending the #hannovermesse2022, in Germany. It is the most important industrial fair of the world, with more than 5.000 expositors and 200.000 visitants from all around the world, including we, from Brazil.

Some technological trends and curiosities:

– Every year there is a partner country. This year is Portugal

#iot is not only sensors anymore. Current solutions integrate sensors, transmission, data storage in cloud, also training algorithms, in order to have an almost plug and play solution

– Energy and #sustainability continue to be very hot topics, and Germany takes if very seriously. In the route between Frankfurt and Hannover, I saw at least a dozen wind turbines, for example

– A closed loop of information is a trend: seamless integration of several internal and external sources of information, to facilitate data mining and insights. Also, integration of information along the supply chain

– The noble area of #operationsresearch is also present: Google showed a case of optimization of data centers. Modern data centers are estimated to consume around 1,8% of the energy of the world. There are huge fluctuations in the demand and also in weather conditions, affecting costs and sustainability. Using OR techniques, they’re able to double the energy efficiency of their data centers.

– Hannover is a wonderful city, with a mix of green areas, modern city and historical architecture. With less than 1 million inhabitants, it has a fairly good structure of trains, easy even for tourists like us.

Danke, Hannover!

See also:

Os efeitos gênesis e apocalipse dos modelos de otimização

 
Quando falamos que encontramos a “solução ótima”, esta é com aspas mesmo: todo modelo é necessariamente uma simplificação do mundo real, extremamente complexo e cheio de efeitos de segunda e terceira ordem.
 
O “efeito gênese” ocorre no início, quando as variáveis ainda não estão “a todo vapor”. É a fase de aquecimento, transitória, e o modelo ainda é jovem demais para aproveitar.
 
Já o “efeito apocalipse” ocorre no final. Como o mundo do modelo acaba com o fim da simulação, ele tende a otimizar tudo: para de produzir, consome todo o estoque, curte a vida adoidado.
 
Nem todos trabalhos sofrem com esses efeitos, obviamente depende do caso. São mais frequentes principalmente nos que envolvem o tempo.


 
Para contrabalancear. No caso da gênese, começar com variáveis iniciais próximas ao estável – ou deixar rodar por alguns períodos e desprezar esse começo. No caso do apocalipse, a mesma coisa: ter restrições contrabalanceando o mínimo de variáveis, e/ou deixar ele rodando por um tempo e desprezar os períodos finais.
 
Quando a gente constrói um modelo e manda otimizar, ele otimiza mesmo, e encontra furos que não fazem sentido na vida real. Boa parte do trabalho é ficar fechando esses furos lógicos.
 
Fica a dica.

Veja artigos semelhantes e me siga no LinkedIn:

https://ideiasesquecidas.com/2021/12/19/o-bilionario-que-fazia-graficos-com-lapis-coloridos/

https://www.linkedin.com/in/arnaldogunzi/

Uma bobina a mais e o MP Load

Descrevendo uma situação que me deixou bastante feliz. Durante visita à unidade de Sacos, em Lages, o meu amigo Marcelo Oliveira contou que a utilização do MP-Load, descrito abaixo, possibilitou o envio de um pallet a mais no contêiner. “Não cabe”, dizia o pessoal; “Cabe, olha só o estudo”, disse o Marcelo.

O MP Load é uma ferramenta extremamente simples, feita em Excel – VBA.

Basta preencher as dimensões (Altura – Largura – Comprimento) e carga máxima do contêiner; e dimensões da bobina a ser transportada – diâmetro externo, largura e peso individual.

As unidades das dimensões estão em milímetros.

Como hipótese, as bobinas sempre vão de pé, e todas as bobinas são iguais. O limite é o volume geométrico ou o peso máximo, o mais restritivo.

Há ferramentas de formação de carga extremamente mais complexas, que conjugam bobinas de vários tipos, deitadas, de pé, etc. Porém, a situação simples de bobina única e de pé deve atender uns 90% das situações, e a beleza é ela ser puramente geométrica, simples de resolver.

O MP Load surgiu com a inspiração acima, pelo amigo Didiel Peça. A ideia era utilizar na hora de tirar pedidos dos clientes de mercado externo, de modo que o valor solicitado fechasse exatamente a carga de um contêiner.

Para o caso de Pallets, basta escolher “P” no campo. As dimensões agora são comprimento – largura – altura (pelo pallet ser retangular) e o peso por pallet.

Há também uma folga adicional de 10 mm no comprimento e na largura, por hipótese.

E que diferença faz uma bobina a mais por carregamento, ou um pallet a mais? Otimização de frete.

Uma bobina faz pouca diferença, individualmente. Mas uma bobina, multiplicada por todas as áreas que otimizam o carregamento, multiplicada por todos os dias em que o estudo é feito, faz toda a diferença.

Segue link.

https://1drv.ms/x/s!Aumr1P3FaK7jn2hfs8JKd7qiZX30

Hipóteses utilizadas:

  • As bobinas são todas idênticas (idem para pallets)
  • As bobinas sempre vão de pé
  • No caso de pallets, há uma folga considerada de 10 mm
  • O comprimento do contêiner é maior do que a largura do mesmo

Como o cálculo é realizado?

Tanto para bobinas quanto para pallets, são analisados dois padrões: retangular e zig-zag

O padrão retangular é um do lado do outro.

Para o cálculo, arrendondar para baixo as dimensões do contêiner dividido pelo diâmetro da bobina.

Já o padrão zig-zag (por falta de um nome melhor), considera um encaixe tipo laranjas empilhadas:

Sejam c e d catetos de um triângulo retângulo, com a hipotenusa sendo o diâmetro externo.

d = sqrt ( Dext^2 – c^2)

Se encontrarmos o valor de c, o valor de d estará definido pela fórmula acima.

No zig-zag, o contorno externo terá um Dext de dimensão, e as camadas internas serão X vezes a dimensão c.

O limite máximo para X é dado pela (Largura do contêiner – Dext) dividido pelo Dext, arredondando para cima.

Com isso, calculamos o número de linhas X, o c e o d, todos os parâmetros para a distribuição.

Por fim, analisamos o carregamento pelo padrão retangular x padrão zig-zag, e pegamos o que ficou melhor.

Um mundo melhor através do Analytics.

https://ideiasesquecidas.com

Veja também:

As Linguagens de Analytics

No último fórum da Informs (a mais importante associação americana de Operations Research), em Chicago, citaram Pythons umas 6 vezes, Excel também umas 6 vezes, Java uma vez (de um fornecedor que disse que estava mudando para Python), R nenhuma mênção.

Isto mostra a força do Python como a língua franca do Analytics da atualidade.

O pessoal que citou Excel o fez metade das vezes para falar mal, outra metade para dizer que o usuário final utiliza. Isto mostra a resiliência do Excel, que apesar de todas as críticas, continua firme e forte nas grandes corporações – por seu poder e facilidade de uso. Há até uma piada que diz: “Todo o sistema financeiro mundial é baseado em Excel”.

Um último comentário: no final das contas, não interessa muito a linguagem, e sim ter uma base teórica forte e capacidade de execução. Linguagens e ferramentas vêm e vão. Até hoje tem gente utilizando Fortran muito bem, por exemplo.

Otimização (?) Matemática

Há um fascínio enorme dos executivos em geral, sobre métodos mágicos matemáticos que pegam um monte de variáveis e chegam numa solução ótima, coisa que chamaremos aqui de “Otimização Matemática”.
 

Mas na verdade, isto é uma “pseudo-otimização”, ou uma otimização sob certas circunstâncias artificiais. Vejamos o por quê.

 


Há diversos métodos de otimização matemática, para diversos tipos de problema. Há problemas de otimização para funções contínuas, utilizando métodos de cálculo diferencial, que tem muita aplicação em engenharia, química. Para problemas do mundo corporativo, como definir a localização e fluxos de centros de distribuição, minimizar as perdas numa máquina de corte ao escolher uma combinação correta de pedidos, utiliza-se métodos de Programação Linear e Inteira.

 
Acontece mais ou menos assim: o processo do mundo real tem que ser mapeado para um problema, que será uma simplificação do mundo real. Fazer esta simplificação, que atenda os pontos principais do problema e deixe de fora detalhes que não importam, é a grande arte da modelagem. Este modelo terá uma formulação matemática, que será resolvido por um solver de Programação Linear e Inteira.
 

Mas, por melhor que seja a modelagem, há objetivos conflitantes na vida real que devem ser equilibrados.


Vejamos o planejamento da produção de uma fábrica.

 
Temos uma demanda de clientes, cada um com um produto, um volume diferente, um deadline diferente. Para o cliente, o ideal são as máquinas produzirem o que ele quer quando ele quer.

Clientes

Para a fábrica, temos uma programação de corridas de produtos. Para a fábrica, quanto mais tempo ela conseguir produzir o mesmo produto, melhor, porque evita perdas no setup de máquina – note que conflita com o desejo da demanda de clientes, que é ter o que quer na hora que quer.

Setup

 

Em termos de estoque, quanto menor o estoque, melhor. Então, se a fábrica adiantar muito a produção de um cliente, vai pagar a conta de manter o material em estoque.

 

Então, olhando só para este exemplo simples, temos três forças conflitantes: demanda dos clientes, setup de máquina e estoques.

ForçasOtimizacao

 

Como se resolve tal conflito? Pode-se colocar um dos itens, como a demanda de clientes, como uma restrição a ser atendida, que é o que é feito na maioria dos livros de Pesquisa Operacional. Mas, na prática, há demandas de clientes que não precisam ser atendidas, e há clientes que precisam ser atendidos. Além disto, na prática uma restrição tão pesada pode dar “infeasible”, ou seja, não dar solução porque a fábrica não consegue atender.
 

Um outro método de resolver o conflito é ponderando todas as forças. Cada cliente gera uma receita (em $ por tonelada) se atendido, sendo que o cliente mais importante vai remunerar a empresa melhor. O setup tem um custo, ou seja, quanto mais setups, pior. Cada item em estoque tem custo proporcional ao tempo que ficar nos estoques.
 

E a ponderação disto seria a fórmula a ser maximizada.

 

Lucro = receita – custoSetup – custoEstoque

 

Ponderar os fatores conflitantes pelo seu custo é uma forma poderosa de se resolver este tipo de problema, e isto ajuda muito.

 


Problema resolvido? Não.
 

Muitas vezes, acontece de o analista rodar o modelo, e aí descobrir que alguma coisa ruim aconteceu.

  • Exemplo 1: Cliente tal é importante, mas não foi atendido. E não foi atendido porque, apesar de importante, o preço que ele paga pelo produto não é tão mais alto que o do cliente ruim. E assim, o analista aumenta artificialmente a receita do produto para ele.
  • Exemplo 2: Tenho o custo de estoques, mas pela ponderação dos custos, o custo de estoques pode ser muito menor que os demais. Aí o modelo, que é matemático, vai lotar os estoques. Aí o analista dá um peso maior para os estoques e coloca uma regra adicional: coloca uma restrição de estoque máximo.

 

O modelo matemático é burro, ele faz exatamente a conta que lhe é informada. Não tem discernimento para entender se está coerente ou não.

E assim, a gente vai martelando os pontos problemáticos do modelo, para tapar os furos que ele vier a ter, e se chegar numa solução compatível com a do mundo real. É sim um método de otimização, mas não é algo que pode funcionar sozinho: tem que ter um analista bom, capaz de analisar, criticar os resultados e mexer alguns pauzinhos para se chegar numa solução.


 

Este é um ponto de vista eminentemente prático, de alguém que trabalha de verdade com estes métodos. Dificilmente algo assim vai estar escrito em algum livro-texto do mundo acadêmico.

 

Arnaldo Gunzi

Set 2015

A solução ótima para o problema errado

De que adianta obter a solução ótima para o problema errado?

solucaoOtima.JPG

Primeiro, uma definição. A solução ótima é a melhor solução possível, analisada do ponto de vista global, para um determinado problema. Nas ciências exatas, as áreas de Pesquisa Operacional, métodos analíticos, têm como objetivo resolver problemas difíceis para encontrar soluções ótimas.

A grande complexidade dos problemas do mundo real não está em resolver com perfeição um problema difícil. Está em formular tal problema. A realidade é, e sempre será, muito mais complexa do que qualquer modelo matemático concebível pelo ser humano. E, para colocar em moldes matemáticos “resolvíveis”, é necessário simplificar a realidade. É aí o calcanhar de Aquiles.

 

Além disso, a solução ótima é ótima para um cenário estacionário. Onde nenhuma hipótese vai mudar, e se tudo continuar da forma que sempre foi. Ora, não foi dada ao ser humano a capacidade de prever o futuro. E quando o mundo mudar? Não seria mais interessante ter respostas rápidas para acompanhar o mundo mutante?

Na natureza, não se encontra um único caso em que dada espécie tente otimizar algum recurso pensando de forma global. Isto porque:

  1. A demanda de energia de processamento para encontrar o ótimo é desproporcionalmente grande
  2. O mundo muda constantemente. Não é possível chegar num ótimo global quando as perguntas mudam. O que pode ser bom hoje não necessariamente será amanhã.
  • Portanto, vejo um extremo desequilíbrio entre os trabalhos acadêmicos desta área e o mundo real. É um caso de “Mura”, do sistema Toyota. Tenta-se resolver com precisão indescritível e métodos cada vez mais mirabolantes os problemas errados. E o por que disto? Talvez em algum post futuro eu tente descrever o que penso.