Olá, pessoal? Boas-vindas ao curso de IA Aumentada: Otimização na prática da Alura!
Eu sou Guilherme Silveira, instrutor deste curso, no qual vamos aprofundar nosso conhecimento em ferramentas de otimização. Tentaremos resolver um problema do mundo real onde buscamos minimizar algo. Por exemplo, minimizar o custo do uso de aviões em um aeroporto.
Audiodescrição: Guilherme Silveira é uma pessoa de pele clara, olhos castanhos, cabelos castanhos e curtos. Está vestindo uma camiseta "gola V" verde e usando headset preto. O ambiente no qual está sentado tem iluminação entre os tons de verde e azul. Ao fundo, uma prateleira com um vaso de plantas e uma placa neon onde está escrito "Alura".
Precisamos que os aviões pousem e estacionem, mas também precisamos minimizar o custo envolvido para que nossos passageiros saiam de uma posição e voem até outra, onde precisam passar pelo controle de passaporte ou pegar suas bagagens.
Temos que minimizar o custo dos ônibus que transportam passageiros quando o estacionamento é um ponto remoto, assim como o custo de colocar aviões com controle de passaporte ou sem controle.
São várias questões a serem trabalhadas, ou seja, restrições que queremos adicionar a um modelo. Vamos modelar este problema, assim como fizemos em um curso anterior, abordando vários tipos de problemas de otimização: minimizar, maximizar ou encontrar uma solução possível.
Modelaremos qualquer um desses tipos de problemas e pediremos para encontrar uma solução, seja minimizando, maximizando ou encontrando uma solução qualquer.
Esse modelo é matemático e isso envolve pensar de forma cada vez mais matemática. Até agora, para resolver esse problema, pensamos de forma computacional, algo com o qual estamos acostumados, que é com variáveis, números inteiros, etc.
Agora vamos pensar mais em matrizes e booleanos, verdadeiros e falsos, restrições que são mais naturais desse tipo de problema e solução.
O objetivo desse curso é aprender a utilizar uma das ferramentas mais famosas, o RTools com o SCP (Simplex Constraint Programming), para resolver esses problemas.
Ao mesmo tempo em que atacamos os problemas dos aviões nos aeroportos para tentar minimizar custos, dando continuidade ao curso anterior, também queremos treinar nossa capacidade de modelar essas situações. Esse é o desafio: ter uma restrição e modelá-la de forma adequada nesse modelo matemático no computador.
É nisso que focaremos aula após aula neste curso.
Até a próxima!
Tudo bem, pessoal? Vamos começar esse novo curso em que continuamos trabalhando com operações, utilizando o R-Tools para encontrar uma solução ótima para o nosso problema.
Podemos pensar que o problema é de um aeroporto, de encaixar coisas, de calcular muitas opções, mas se trata de um problema matemático, em que o computador calcula as opções e encontra uma solução ótima para o nosso problema. É isso que nós queremos!
Então, retomando o nosso projeto, Aeroporto2 - 1.2, temos um código em que instalávamos as ferramentas, o R-Tools e o Pandas, numa versão específica, que já era boa o suficiente. Criamos uma função para resolver o problema, e ela resolveu o problema.
Também criamos uma função para afirmar que os aviões têm que ser distintos nos estacionamentos. Ou seja, se um avião está parado em um estacionamento, ele não pode estacionar em outro também, ele só estaciona em um estacionamento por vez.
Além disso, colocamos uma restrição de que todo avião tem que estacionar em algum lugar, não pode ficar voando. Se for necessário, por exemplo, que ele voe um pouco mais, temos que modelar essa possibilidade. No nosso caso, o pedido do nosso cliente foi que o plano de estacionamento permitisse que todos estacionem.
Geramos duas classes: Estacionamento
e Aviao
. Lembrando que o avião pode ser grande ou não, isto é, pode ser pequeno, e o estacionamento também pode ser grande ou não e ter vizinhos. Sendo assim, adicionamos uma restrição extra, que vamos encontrar mais abaixo, que é: os vizinhos estão limitados. Significa que se existe um avião grande, outro avião grande não pode ficar do lado.
Foi com isso que nós acabamos criando os últimos exemplos de modelos para testar e conferir se tudo estava funcionando e encontramos soluções ótimas quando essas soluções existiam.
Nosso trabalho agora é tornar o modelo cada vez mais interessante, com mais tipos de restrições, com mais dimensões e muitas outras coisas legais, que vamos fazer agora. Para isso, a primeira restrição que vamos trabalhar é a questão de controle de passaporte em aeroportos internacionais.
Algumas das portas de entrada do aeroporto têm controle de passaporte, outras não. Por exemplo, se estamos em São Paulo e está chegando um voo de Salvador, não precisamos controlar o passaporte, então, criamos uma área do aeroporto sem controle de passaporte, em que as pessoas consigam passar direto.
Mas uma pessoa vinda da Alemanha ou de algum país da Europa, por exemplo, precisa passar pelo controle de passaporte. Por isso, criamos uma área do aeroporto com controle de passaporte. Lembrando que esta questão não se limita em separar voos internacionais e nacionais, pois existem acordos entre países, como no Mercosul, em que você só precisa de um certo tipo de documento, não necessariamente o passaporte.
Vamos trabalhar com a ideia de requer passaporte ou não requer passaporte.
Então, se o tipo de acordo é um ou outro, a questão é: precisa de passaporte ou não precisa para esse avião? Um avião vindo de Salvador não precisa de controle de passaporte, então podemos direcionar para onde não precisa. Se precisa de controle de passaporte, tem que ir para onde precisa de controle de passaporte. Não pode ir para onde não tem controle de passaporte. Então, vamos trabalhar com isso.
O primeiro ponto, é: os aviões precisam dizer se requerem controle de passaporte. Então, vamos localizar no código a parte onde definimos a classe Aviao
.
class Aviao:
def __init__(self, k, grande):
self.k = k
self.grande = grande
Além de saber se ele é grande ou não, queremos saber se ele requer controle de passaporte.
class Aviao:
def __init__(self, k, grande, requer_controle_de_passaporte):
self.k = k
self.grande = grande
self.requer_controle_de_passaporte = requer_controle_de_passaporte
A variável requer_controle_de_passaporte
é do avião, não é do modelo matemático, é do avião. O avião requer ou não requer: True
ou False
.
Já no caso do estacionamento, precisamos saber se ele tem controle de passaporte ou não.
class Estacionamento:
def __init__(self, k, total_de_avioes, grande, modelo, tem_controle_de_passaporte):
self.grande = grande
self.tem_controle_de_passaporte = tem_controle_de_passaporte
self.variavel = modelo.NewIntVar(0, total_de_avioes, f'estacionamento_{k}')
self.k = k
self.vizinhos = []
self.recebe_aviao_grande = modelo.NewBoolVar(f'recebe_aviao_grande_{k}')
if not self.grande:
modelo.Add(self.recebe_aviao_grande == 0)
Então, nos dois inicializadores, nos dois construtores dessas classes, colocamos se o estacionamento tem controle de passaporte, sim ou não, e se o avião requer controle de passaporte, sim ou não. Qual é o próximo passo?
Vamos localizar um exemplo mais abaixo no código. Quando vamos criar o nosso exemplo, definimos aviões distintos, que todo avião tem que estacionar, limitamos vizinhos, limitamos aviões grandes, mas precisamos de mais que isso.
Temos que limitar os aviões que precisam de controle de passaporte, pois eles não podem ir onde não tem controle de passaporte. Portanto, chamaremos a função limitar_avioes_que_requerem_passaporte
e passaremos:
O código ficará assim:
avioes = [Aviao(1, False, True),
Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
Agora, criaremos um nova célula de código, def limitar_avioes_que_requerem_passaporte( )
que recebe modelo, estacionamentos, avioes
, que são os objetos, listas de objetos em Python.
def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
Precisamos saber quais são os aviões que requerem controle de passaporte. Então, queremos saber quais aviões precisam de controle.
def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
avioes_com_controle =
Para trabalhar com os avioes_com_controle
, usaremos um for
que devolve uma lista. Então, se o avião requer passaporte, vamos devolver o próprio avião.
def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
Assom, faremos uma lista com todos os aviões que requerem controle de passaporte. Agora, precisamos saber quais são os estacionamentos que não têm controle de passaporte, ou seja, os estacionamentos_sem_controle
.
def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
estacionamentos_sem_controle = [estacionamento for estacionamento in estacionamentos if not estacionamento.tem_controle_de_passaporte]
Com isto, temos a lista dos estacionamentos sem controle e a lista dos aviões que precisam de controle. Tenho que falar que esse estacionamento não pode ter esse avião. Já fizemos esse trabalho. Ele se resume nestes passos:
Para cada estacionamento sem controle: for estacionamento in estacionamentos_sem_controle
;
Em aviões com controle: for aviao in avioes_com_controle
;
Adicionamos uma restrição dizendo que a variável do modelo matemático do estacionamento não pode ser esse avião, portanto, tem que ser diferente de aviao
: modelo.AddConstraint(estacionamento.variavel != aviao.k)
.
Em outras palavras, estamos dizendo ao estacionamento que a variável do modelo matemático do estacionamento 1 não pode ter o avião 3, pois ele requer passaporte e o estacionamento não.
def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
estacionamentos_sem_controle = [estacionamento for estacionamento in estacionamentos if not estacionamento.tem_controle_de_passaporte]
for estacionamento in estacionamentos_sem_controle:
for aviao in avioes_com_controle:
modelo.Add(estacionamento.variavel != aviao.k)
Desta forma, vamos adicionar uma centena de restrições dizendo onde o avião não pode estacionar, dependendo do tamanho do modelo, de quantos estacionamentos, quantos aviões. Então, é uma forma razoavelmente simples e direta de falar.
Vamos rodar essa célula e seguir com a criação do modelo. Nosso modelo terá dois aviões e criaremos um exemplo com apenas dois estacionamentos, bem simples, direto ao ponto. Dois estacionamentos e dois aviões.
Além disso, precisamos dizer se algum desses aviões tem necessidade de passaporte, True
, e se algum não tem, False
. O primeiro tem necessidade e o segundo não. O mesmo vale para o estacionamento, o primeiro avião suporta controle de passaporte, tem controle de passaporte, o segundo não.
avioes = [Aviao(1, False, True),
Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
Quer dizer que se executarmos tudo ("Tempo de execução > Executar tudo"), o primeiro avião tem que ir no primeiro estacionamento, ele não pode ir no segundo estacionamento, o primeiro avião no primeiro estacionamento.
avioes = [Aviao(1, False, True),
Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
OPTIMAL
estacionamento_1 tem aviao 1 grande=False
estacionamento_2 tem aviao 2 grande=False
Vamos trocar a ordem para nos certificarmos que o código está correto. Agora, o primeiro avião é False
e o segundo é True
. Feito isso, o segundo avião tem que ir no primeiro estacionamento.
avioes = [Aviao(1, False, False),
Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
OPTIMAL
estacionamento_1 tem aviao 2 grande=False
estacionamento_2 tem aviao 1 grande=False
Agora vamos criar o caso de dar errado: dois aviões que requerem controle de passaporte. Já que ambos requerem controle de passaporte, não deveria achar solução.
avioes = [Aviao(1, False, True),
Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
INFEASIBLE
Sem solucao
Não achou solução. E se tivermos um com controle de passaporte, dois sem controle de passaporte, então False
e False
, e três estacionamentos, sendo que só o primeiro requer passaporte e tem suporte a passaporte.
avioes = [Aviao(1, False, True),
Aviao(2, False, False)],
Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
Estacionamento(3, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
OPTIMAL
estacionamento_1 tem aviao 1 grande=False
estacionamento_2 tem aviao 3 grande=False
estacionamento_3 tem aviao 2 grande=False
Vamos simular mais uma situação? Então, temos três aviões, de novo, o primeiro deles requer controle de passaporte, tem que ir no estacionamento 1. O segundo deles é grande e vamos colocar uma vaga grande no estacionamento 3. Então, ele tem que ir no estacionamento 3. Vamos conferir?
avioes = [Aviao(1, False, True),
Aviao(2, True, False)],
Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
Estacionamento(3, total_de_avioes, Trug, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
OPTIMAL
estacionamento_1 tem aviao 1 grande=False
estacionamento_2 tem aviao 3 grande=False
estacionamento_3 tem aviao 2 grande=False
Ele foi no estacionamento 3. Para nos certificarmos que o modelo está funcionando, vamos criar mais um exemplo, adicionando outro avião grande, 4, que tem controle de passaporte. Esse avião pode ir no estacionamento 1? Não, porque o estacionamento 1 não é grande. Ele pode ir no estacionamento 2? Não, porque não é grande. Ele pode ir no estacionamento 3? Não pode, porque não tem controle de passaporte.
Sendo assim, precisamos de mais um estacionamento: estacionamento 4, que tem total de aviões, suporta avião grande e controle de passaporte. O avião 1, que tem controle de passaporte, não pode ir no último estacionamento. Não é uma solução viável, porque o avião 4 não teria onde pousar. O único lugar que o avião 4 pode pousar é no estacionamento 4.
avioes = [Aviao(1, False, True),
Aviao(2, True, False),
Aviao(3, False, False),
Aviao(4, True, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False),
Estacionamento(3, total_de_avioes, True, modelo, False),
Estacionamento(4, total_de_avioes, True, modelo, True)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)
OPTIMAL
estacionamento_1 tem aviao 1 grande=False
estacionamento_2 tem aviao 3 grande=False
estacionamento_3 tem aviao 2 grande=False
estacionamento_4 tem aviao 4 grande=True
Começa com o avião mais restrito, o 4. Ele só pode ir no estacionamento 4. Então, sobra outro avião restrito, que é o avião 1, como ele requer controle de passaporte, tem que ir no 1. Então, sobrou outro que é grande, o 2. Ele tem que ir no 3. E aí o outro que sobrou ficou no 2.
Resolvemos, mas ainda temos outros desafios pela frente. Até mais!
Vamos continuar. Queremos agora dar um exemplo de um aeroporto em que nós temos uma situação um pouco mais complexa, que é muito importante para nós colocarmos tudo o que já conhecemos em prática.
Imaginem um aeroporto com quatro estacionamentos: dois com controle de passaporte e dois sem controle de passaporte. Chegaram dois aviões que não precisam de controle de passaporte. Para onde vocês vão direcionar esses aviões? Eles vão aparecer no estacionamento sem controle de passaporte. Nós pensamos que faz sentido. Pessoas sem controle de passaporte vão para o local sem controle de passaporte.
Mas chega um terceiro avião com o combustível no final, precisando pousar. Você vai fazer o quê? Vai dizer para ele não pousar, se não for no estacionamento correspondente? Não vamos falar isso, vamos deixar pousar, e infelizmente, no controle de passaporte.
Não é o ideal, não é uma restrição forte, ou seja, uma restrição hard, mas sim uma restrição soft. Queremos colocar essa restrição, mas se não colocar, tudo bem.
Então, as ferramentas de otimização permitem que implementemos esse tipo de recurso. Algumas de forma explícita, através de uma chamada do tipo soft, de uma restrição soft. E outras, como já vimos no passado, no curso anterior, adicionamos uma penalidade.
Um avião sem controle de passaporte, vindo de Salvador, por exemplo, até pode ser inserido na área de controle de passaporte, mas não é bacana. Então, podemos colocar uma penalidade, podendo diminui-la.
Por exemplo, cada avião que não precisa de controle de passaporte, mas para onde precisa controle de passaporte, vou dar uma penalidade de mil. Quer dizer, queremos minimizar essa penalidade. Então, quanto mais aviões nessa situação, pior para nós. E o modelo vai tentar encontrar o ponto mínimo, a solução que minimiza esse custo.
Com o Google Sheets aberto, criaremos uma aba nova e digitaremos na célula A1: cada avião que não precisa de controle de passaporte e está no controle de passaporte tem custo de 1000. Assim, teremos uma somatória. Somaremos todos os custos de todos os aviões. Esse será o custo total e é isso que queremos minimizar.
Desejamos minimizar o custo total.
Percebam que o custo total está em função dos aviões. É uma função dos aviões, porque se o avião está aqui ou lá, estamos em função dele. Então, literalmente, é uma função matemática. Por quê? Porque é uma somatória, é a soma de todos os custos.
Soma todas essas penalidades, que podem ser zero ou mil. Zero para um avião que está onde deveria e mil para um avião que não está onde deveria. Soma todas elas e isso vai dar um custo, isso é uma função. Nós chamamos essa função de função objetivo. Essa função objetivo deve ser minimizada.
Você pode falar "ah, tenho um problema de maximização". Tudo bem, faz um de maximizar. No nosso caso, queremos minimizar. Não queremos que os aviões parem nesses lugares. Então, colocamos uma penalidade e falamos que não queremos isso. Então, essa sacada da função objetivo é super importante, já vimos no curso passado essa história da penalidade e da função objetivo para minimizar. Vamos ver agora de novo, só que com vários aviões.
Como vamos fazer isso? Vamos subir no nosso código, nos nossos exemplos. Depois de limitar aviões que requerem passaporte, vamos indicar que preferimos aviões em determinada situação. Trata-se de uma preferência, não é uma requisição. Preferimos aviões que tem controle de passaporte. Se vier sem, adiciona uma penalidade.
Essa função vai receber um modelo
, estacionamentos
e avioes
, como de costume. Vamos precisar dos aviões e vamos precisar dos estacionamentos adequados. Quais são os estacionamentos? Os estacionamentos que requerem controle de passaporte. Então, são os estacionamentos que têm controle.
Vamos copiar do bloco de código acima. Já temos os estacionamentos sem controle, copiaremos e colaremos. Só retirando a palavra not
. Esses são os estacionamentos com controle.
Lembrem-se que esses estacionamentos com controle vão precisar de um avião que seja com ou sem controle de passaporte. Disso dependerá a penalidade. Então, vamos precisar provavelmente dos dois tipos de aviões. Vamos colocar os dois tipos de aviões, copiando de lá de cima, aviões com controle e aviões sem controle, inserindo a palavra not
após o if
.
def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)
estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
Então, agora já temos os estacionamentos com controle de passaporte. E sabemos que para cada um desses estacionamentos, então for estacionamento in estacionamentos_com_controle
, temos que verificar se o avião que está lá requer ou não passaporte.
Se ele exigir passaporte, a penalidade é igual a zero. Se ele não exigir passaporte, teremos uma penalidade de mil. Então, vamos fazer para cada avião. Quais são os aviões que queremos passar? Os aviões que não requerem. Porque se não requer, vamos colocar a penalidade. Depois vemos se vamos precisar dos que requerem.
Escreveremos for aviao in avioes_sem_controle
, indicando cada avião que não precisa de passaporte. Preciso saber se esse avião está nesse estacionamento. Como fazemos isso?
Para saber se esse avião está nesse estacionamento e poder calcular uma penalidade, precisaremos da penalidade. Então, vamos calcular essa penalidade. Penalidade é igual a modelo.NewIntValue(0, 1000, f 'penalidade_{estacionamento.k}_{aviao.k}')
.
def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
for estacionamento in estacionamentos_com_controle:
for aviao in avioes_sem_controle:
penalidade = modelo.NewIntValue(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')
Então, essa vai ser a variável que representa ou zero ou mil, que é a penalidade se esse avião estiver aqui. Agora, temos que tomar cuidado. Já trabalhamos com penalidade. Queremos que a penalidade seja mil. Assim, escreveremos modelo.Add(penalidade == 1000)
.
Acontece que a penalidade só vai ser mil se, ou seja, OnlyEnforceIf
. Então, a penalidade vai ser mil somente se um avião sem controle estiver nesse estacionamento. Então, OnlyEnforceIf
se esse avião está nesse estacionamento.
Assim, queremos que a penalidade seja mil se, em tempo de execução, o modelo matemático perceber que um avião sem controle precisa pousar em um estacionamento com controle de passaporte.
E no caso contrário? Queremos que seja zero. Então, vamos escrever o caso contrário. modelo.Add(penalidade == 0)
. Então, a penalidade agora é zero. Mas quando a penalidade é zero? OnlyEnforceIf
, somente se, o avião não está nesse estacionamento. Então, a variável aviao_esta_nesse_estacionamento.Not()
. Então, se ele não está nesse estacionamento.
Parece aquele trabalho que já fizemos de criar uma penalidade, que é uma variável com if
. Só que lembrem, não é uma variável do Python. É uma variável do modelo matemático. O modelo matemático vai ter que decidir se coloca o avião lá ou não, podendo ter uma penalidade de zero ou de mil.
def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
for estacionamento in estacionamentos_com_controle:
for aviao in avioes_sem_controle:
penalidade = modelo.NewIntValue(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')
modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
Mas atenção: Estamos criando uma penalidade para cada parzinho de estacionamento com controle e avião sem controle. Então, temos muitas penalidades. Imaginem que, se tivermos dez estacionamentos com controle e dez aviões sem controle, são criadas cem variáveis penalidade
.
E um monte dessas penalidades será igual a zero, porque o avião não está lá. Só, no máximo, tem um avião ali dentro. Então, a maior parte disso vai ser zero. Mas se algum desses aviões estiver nesse estacionamento, vai ser mil, porque definimos assim.
Faltou criar a variável aviao_esta_nesse_estacionamento
. Mas essa variável tem que ser booleana, porque ela é uma variável true
ou false
. Já trabalhamos com essas variáveis booleanas. Então, criamos um modelo.NewBoolVar()
, uma variável booleana, que terá um nome também. Dentro dela, escreveremos f
. Queremos dizer que, no estacionamento tal, temos tal avião. Então,f 'estacionamento_(estacionamento.k)_tem_aviao_(aviao.k)
. Nesse estacionamento, temos esse avião. É a variável booleana que diz isso: no estacionamento 1, tem o avião 1. Se tiver, é true
, se não tiver, é false
.
Mas como falamos "se tiver, é true
, se não tiver, é false
"? Fazemos um pouco o contrário: vamos adicionar para o modelo uma restrição nova. Diremos que se a variável aviao_esta_nesse_estacionamento
for true
, então o estacionamento.variavel
tem que ser igual aviao.k
.
O modelo matemático vai ter o raciocínio dele, mas podemos pensar assim: o que ele tenta fazer é colocar um true
ou false
. Ele tenta colocar um true
, digamos que o avião 5 esteja no estacionamento 3. Já que ele colocou um true
na variável em modelo.NewBoolVar()
, então, a variável estacionamento 3 tem que ter o valor 5.
E se por acaso esse avião é um avião sem controle e um estacionamento com controle, o que vai acontecer? Vai ser acrescentada a penalidade de 1000
. Lembre-se de que precisamos da restrição contrária. modelo.Add().OnlyEnforceIf
. Se aviao_nesse_estacionamento.not
, ou seja, ele não está nesse estacionamento, o modelo tentou colocar um false
para ver se resolve o nosso problema.
Já que ele tentou colocar, o que ele vai fazer? estacionamento.variavel
tem que ser diferente desse avião. Obrigamos a ser diferente. Não quer dizer que ele vai tentar, ele vai olhar essas regras, vai otimizar e vai fazer buscas para tornar esse processo o melhor possível. Essa é a ideia.
Com isso, temos as variáveis que queremos. O que faltou é somar todos essas penalidades. Então, na parte de cima do código, criaremos penalidades
, uma lista. E aí, para cada um deles, fazemos penalidades.append(penalidade)
. E no final, retornamos penalidades. Então, a função prefere_avioes_com_controle_de_passaporte
vai devolver as penalidades.
def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
for estacionamento in estacionamentos_com_controle:
for aviao in avioes_sem_controle:
penalidade = modelo.NewIntVar(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')
aviao_esta_nesse_estacionamento = modelo.NewBoolVar(f'estacionamento_{estacionamento.k}_tem_aviao_{aviao.k}')
modelo.Add(estacionamento.variavel == aviao.k).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
modelo.Add(estacionamento.variavel != aviao.k).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
penalidades.append(penalidade)
return penalidades
Chamaremos essa função no fim do modelo, com prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)
. Ela devolve para nós as penalidades
, pois vamos precisar delas. E agora, o que queremos fazer? Quando formos resolver o problema, quero passar essas penalidades para o solucionador: resolve(solucionador, modelo, estacionamentos, avioes, penalidades)
.
Subiremos de novo até o resolve
para incluir as penalidades
dentre os parâmetros. Antes de resolver, escreveremos modelo.Minimize(sum(penalidades))
. Estamos pedindo para minimizar a soma dessas penalidades. Aí, você fala "mas pode fazer sum
em penalidades
?". Pode, porque são variáveis inteiras.
Então, a função objetivo é a soma das penalidades. E é ela que queremos minimizar. Se for infeasible, não teve solução. Agora, já que tem solução, queremos imprimir qual foi o valor total das penalidades. No nosso caso, vamos colocar a função objetivo ou "Valor objetivo"
. O valor mínimo que ela encontrou será o solucionador.ObjectiveValue()
.
// trecho de código suprimido
print(f"Valor objetivo = solucionador.ObjectiveValue()")
Vamos salvar, executar e esperar não ter cometido nenhum erro. Se tudo estiver correto, veremos o resultado esperado. O valor objetivo, nesse caso, é zero. Não se esqueça de passar penalidades
como parâmetro para resolve
em todos os casos. De qualquer forma, encontramos uma solução para todos os casos anteriores, então a solução foi zero. Se não tem solução, não há o que fazer.
No terceiro caso, ele retornou INFEASIBLE
porque são dois aviões que requerem passaporte. Nesse caso, não podemos deixar passar. Quando há um avião exigindo passaporte e dois que não exigem, enquanto temos um portão com passaporte e dois sem. Nesse caso, o custo é zero. No próximo, um avião com controle de passaporte e dois sem também funciona com custo zero. Em seguida, outro caso que funcionava a custo zero.
Agora, o caso mais simples de todos é aquele com dois aviões: um que requer e outro que não requer passaporte. Vamos mudar para dois aviões que não requerem passaporte, com apenas um estacionamento que não requer. Nesse caso, será necessário pegar qualquer um dos dois aviões e pousá-lo no estacionamento com controle de passaporte. Neste caso, o custo tem que ser mil.
avioes = [Aviao(1, False, False),
Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
penalidades= prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes, penalidades)
Após rodar o código, receberemos o valor de 1000
como penalidade. Podemos copiar o código e colá-lo logo em seguida para torná-lo mais complexo: inseriremos mais um avião, que não requer passaporte. Além disso, incluiremos mais um estacionamento que requer o controle de passaporte. Nesse caso, a penalidade precisa ser de 2 mil.
avioes = [Aviao(1, False, False),
Aviao(2, False, False),
Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)
estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
Estacionamento(2, total_de_avioes, False, modelo, False),
Estacionamento(3, total_de_avioes, False, modelo, True)]
avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
penalidades= prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)
solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes, penalidades)
Ao executar o código, obtemos exatamente a penalidade de 2000
. Isso acontece porque dois aviões estão indo onde não gostaríamos que eles fossem. Se inserirmos um quarto avião que precisa do controle de passaporte, ficando assim com três aviões sem controle e um com controle. Além disso, se editarmos os estacionamentos para ficarem com três sem controle e um com controle, o custo deve ser zero.
No próximo vídeo, vamos dar uma olhada nas variáveis de penalidade na planilha. Até mais!
O curso IA aumentada: aprimorando técnicas de otimização em um problema prático possui 103 minutos de vídeos, em um total de 34 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:
Formações com mais de 1500 cursos atualizados e novos lançamentos semanais, em Programação, Inteligência Artificial, Front-end, UX & Design, Data Science, Mobile, DevOps e Inovação & Gestão.
A cada curso ou formação concluído, um novo certificado para turbinar seu currículo e LinkedIn.
No Discord, você tem acesso a eventos exclusivos, grupos de estudos e mentorias com especialistas de diferentes áreas.
Faça parte da maior comunidade Dev do país e crie conexões com mais de 120 mil pessoas no Discord.
Acesso ilimitado ao catálogo de Imersões da Alura para praticar conhecimentos em diferentes áreas.
Explore um universo de possibilidades na palma da sua mão. Baixe as aulas para assistir offline, onde e quando quiser.
Formações com mais de 1500 cursos atualizados e novos lançamentos semanais, em Programação, Inteligência Artificial, Front-end, UX & Design, Data Science, Mobile, DevOps e Inovação & Gestão.
A cada curso ou formação concluído, um novo certificado para turbinar seu currículo e LinkedIn.
No Discord, você tem acesso a eventos exclusivos, grupos de estudos e mentorias com especialistas de diferentes áreas.
Faça parte da maior comunidade Dev do país e crie conexões com mais de 120 mil pessoas no Discord.
Acesso ilimitado ao catálogo de Imersões da Alura para praticar conhecimentos em diferentes áreas.
Explore um universo de possibilidades na palma da sua mão. Baixe as aulas para assistir offline, onde e quando quiser.
Luri é nossa inteligência artificial que tira dúvidas, dá exemplos práticos, corrige exercícios e ajuda a mergulhar ainda mais durante as aulas. Você pode conversar com a Luri até 100 mensagens por semana.
Aprenda um novo idioma e expanda seus horizontes profissionais. Cursos de Inglês, Espanhol e Inglês para Devs, 100% focado em tecnologia.
Formações com mais de 1500 cursos atualizados e novos lançamentos semanais, em Programação, Inteligência Artificial, Front-end, UX & Design, Data Science, Mobile, DevOps e Inovação & Gestão.
A cada curso ou formação concluído, um novo certificado para turbinar seu currículo e LinkedIn.
No Discord, você tem acesso a eventos exclusivos, grupos de estudos e mentorias com especialistas de diferentes áreas.
Faça parte da maior comunidade Dev do país e crie conexões com mais de 120 mil pessoas no Discord.
Acesso ilimitado ao catálogo de Imersões da Alura para praticar conhecimentos em diferentes áreas.
Explore um universo de possibilidades na palma da sua mão. Baixe as aulas para assistir offline, onde e quando quiser.
Mensagens ilimitadas para estudar com a Luri, a IA da Alura, disponível 24hs para tirar suas dúvidas, dar exemplos práticos, corrigir exercícios e impulsionar seus estudos.
Envie imagens para a Luri e ela te ajuda a solucionar problemas, identificar erros, esclarecer gráficos, analisar design e muito mais.
Aprenda um novo idioma e expanda seus horizontes profissionais. Cursos de Inglês, Espanhol e Inglês para Devs, 100% focado em tecnologia.
Escolha os ebooks da Casa do Código, a editora da Alura, que apoiarão a sua jornada de aprendizado para sempre.
Acesso completo
durante 1 ano
Estude 24h/dia
onde e quando quiser
Novos cursos
todas as semanas