A Introdução à Otimização Inteira

Quiz 1 - Introdução à otimização inteira

Data limite de entrega: 13 de abril de 2022

 

Entrega: Ao final desta prática, você deverá enviar no SIGAA da disciplina um arquivo .zip.

O quiz poderá ser feito em trio e submetido por apenas um (a) aluno(a), informando os três

nomes no SIGAA.

Cópias, de qualquer natureza, serão penalizadas com nota zero.

Atividade 1

[3 pontos] - Leia completamente o artigo “Minimizando os custos energéticos de alocação de aulas a salas: o caso de uma instituição federal de ensino” do SBPO 2019 (ver Materiais de

Aula) e responda, de forma direta, as seguintes questões:

(a) Qual problema foi tratado no artigo?

No artigo é demonstrado algumas formulações de modelos de otimização em que o objetivo é tentar mitigar o problema de alocação de turmas em salas de aulas dentro de uma instituição federal de ensino de forma que os custos associados à utilização destas salas e laboratórios de informática sejam os menores possíveis

No artigo o problema tratado é referente a alocação de aulas a salas no contexto de uma

(b) Explique os modelos de otimização apresentados (variáveis, função, objetivo e restrições).

Para explicar os modelos apresentados primeiro devemos entender os conjuntos e as variáveis neles presentes:

Conjuntos:

Conjunto A- turmas de 1 a n

Conjunto L- de locais de aula

Conjunto H - horários de aula

B ⊆ A é o conjunto que necessitam apenas de salas normais ou seja, uma parte das turmas ou todas elas necessitam apenas de salas normais

C ⊆ A é o conjunto que necessitam de laboratório de informática ou seja, uma parte das turmas ou todas elas têm aulas de laboratório de informática

Bk ⊆  B é o conjunto de turmas que requerem apenas salas de aula que possuem o mesmo horário k ∈  H

Ck ⊆ C é o conjunto de turmas que necessitam de laboratórios de informática que possuem mesmo horário k ∈  H

S ⊆ L é o conjunto das salas de aula

I ⊆ C é o conjunto dos laboratórios de informática

Si ⊆ S é o conjunto das salas de aulas que suportam a quantidade de alunos presentes na turma i ∈ B

Ii ⊆ I é o conjunto dos laboratórios de informática que suportam a quantidade de alunos presentes na turma i ∈  C

Hi ⊆ H é o horário das aulas de uma turma i ∈  A.

As turmas que requerem apenas salas de aula são elementos do conjunto B

As salas de aula são elementos do conjunto S

As turmas que necessitam de laboratórios de informática são elementos do conjunto C

Os laboratórios de informática são elementos do conjunto I

Variáveis:

Yij  é uma variável binária que assumirá o valor de 1 quando uma turma i ∈ B for alocada em um local de aula j ∈ Si

Xikj  é uma variável binária que assumirá o valor de 1 quando o horário da aula k ∈ H da turma i ∈ B (apenas turmas que requerem salas de aulas simples) for alocada em um local de aula j ∈ Si

Tikj  é uma variável binária que assumirá o valor de 1 quando uma turma i ∈ C(Turmas que necessitam de laboratório de informática) for alocada em um local de aula j ∈ Si

Uij  é uma variável binária que assumirá o valor de 1 quando uma turma i ∈ C for alocada em um local de aula j ∈ Ii

Zj  é uma variável binária que assume o valor 1 quando um local de aula é utilizado por pelo menos uma aula.

Cj é o custo de qualquer aula j pertence a L

mj é o custo da utilização de um computador por aluno

qi é a quantidade de alunos presentes na turma

A seguir explicamos os modelos de programação linear inteira implementados buscando minimizar o número de aulas de uma mesma turma alocadas em salas distintas:

Formulação F1

Função objetivo:

[pic 1]

Primeiro membro: O somatório de todos componentes do conjuntos i ∈ B ( turmas que necessitam apenas de salas de aula simples) *  somatório de todos os componentes do conjunto k ∈ Hi (Horários de aulas) * somatório de todos os componentes do conjunto j ∈ Si ( locais de aula que suportam a quantidade de alunos presentes na turma i ∈ B) * pelo custo da aula * pela variável que assume o valor de 1 quando o horário da aula k ∈ H da turma i ∈ B for alocada em um local de aula j ∈ Si

Segundo membro:  O somatório de todos os componentes do conjunto i ∈ C ( turmas que necessitam de laboratórios de informática) * somatório de todos os componentes do conjunto k ∈ Hi (Horários de aulas) * somatório do conjunto j ∈ Ii ( locais de aula que suportam a quantidade de alunos presentes na turma i ∈ C) * ( custo da aula + quantidade de alunos na turma * custo da utilização do computador por aluno) * variável que assume o valor de 1 quando o horário da aula k ∈ H da turma i ∈ C for alocada em um local de aula j ∈ Ii

A soma do primeiro membro com o segundo compõe a função objetivo da Formulação F1 e tem como objetivo minimizar o custo energético da utilização de locais de aula pelas aulas das turmas.

Restrições:

[pic 2]

Restrições:

(2) O somatório de todos os componentes do conjunto  j  ∈ Si (locais de aulas que suportam a quantidade de alunos presentes na turma i ∈ B) * variável Xikj que assumirá o valor de 1 quando o horário da aula k ∈ H da turma i ∈ B for alocada em um local de aula j ∈ Si deve ser igual a 1 - Essa restrição faz com que duas turmas que necessitam apenas de salas de aulas normais não possam ser alocadas no mesmo local em um mesmo horário)