RELATÓRIO

MINISTÉRIO DA EDUCAÇÃO

Universidade Federal de Ouro Preto – UFOP

Instituto de Ciências Exatas e Aplicadas

Campus João Monlevade

RELATÓRIO

Trabalho Final de Otimização Combinatória

JOÃO MONLEVADE

Julho de 2015





FLÁVIA CHAVES DE AMORIM

MARIANA GABRIELA ROSA BATISTA

MATHEUS LUCAS DE MELO SANTOS

RELATÓRIO

Trabalho Final de Otimização Combinatória

Relatório apresentado para avaliação na

disciplina de Otimização Combinatória, do

curso de Engenharia de Produção, turno

vespertino, da Universidade Federal de Ouro

Preto, orientado pelo Professor Dr. Thiago

Silva.

JOÃO MONLEVADE

Junho 2015





Sumário 1. INTRODUÇÃO .................................................................................................................... 4

2. OBJETIVO ............................................................................................................................ 4

2.1. Objetivo Geral ............................................................................................................... 4

2.2. Objetivos Específicos .................................................................................................... 5

3. REFERENCIAL TEÓRICO ................................................................................................. 5

3.1. Programação Linear Inteira ........................................................................................... 5

3.2. Relaxação Linear ........................................................................................................... 6

3.3. Linguagem AMPL......................................................................................................... 7

4. DESCRIÇÃO DO PROBLEMA ........................................................................................... 8

5. DESCRIÇÃO DO MODELO DE OTIMIZAÇÃO ............................................................... 9

5.1. Definição das Instâncias .............................................................................................. 11

6. RESULTADOS COMPUTACIONAIS .............................................................................. 11

6.1. Resultados por meio do Método Exato ....................................................................... 11

6.2. Resultados por meio da Relaxação Linear .................................................................. 13

7. CONCLUSÃO .................................................................................................................... 15

8. REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................ 16





4 Departamento de Ciências Exatas e Aplicadas – DECEA Rua 37, nº 115 - Bairro Loanda – Caixa Postal 24 – CEP: 35.930-970 - João Monlevade /MG – Brasil - Telefax: (0xx31) 3852-8709 Homepage ; www.ufop.br - email: [email protected]

1. INTRODUÇÃO

A Programação Linear é tida como uma área essencial da otimização, principalmente

pelo de fato de vários problemas práticos em pesquisa operacional poderem ser expressos

como problemas de Programação Linear. Verifica-se então, um vasto cenário de

aplicação da Programação Linear atualmente como: “decisões de investimentos, políticas

de estoques, orçamentos de capital, fluxos de caixa, mix de produção, organização de

transportes, localização industrial e fluxo de redes, dentre outros” (MIRANDA et al, 200,

p. 46).

O presente relatório vem desta forma, compreender e implementar um real problema

de otimização combinatória, o qual foi extraído de um artigo apresentado no Simpósio

Brasileiro de Pesquisa Operacional em 2009. O modelo em questão foi formulado como

um problema de programação linear inteira, que é considerada uma subclasse da

Programação Linear pelo fato de conter todas as suas variáveis pertencentes ao conjunto

dos números inteiros. O modelo implementado e apresentado pelos autores do artigo

objetiva a programação de horários de professores pertencentes a um departamento de

uma Instituição Pública de Ensino Superior do Brasil.

O relatório está estruturado conforme 3 seções: Descrição do modelo de otimização,

Implementação do modelo de otimização: instanciamento e métodos de resolução, e

Resultados computacionais. A primeira seção refere-se a um detalhamento e explicação

de todas as componentes descritas no modelo formulado (Conjuntos, parâmetros,

variáveis e etc.). A segunda seção aborda a implementação do modelo de otimização

proposto destacando o processo de instanciamento e a sua resolução através do método

exato e sua relaxação linear. E a última seção aborda os resultados obtidos com os

critérios de instanciamento e métodos de resolução utilizados.

2. OBJETIVO

2.1. Objetivo Geral






Compreender, analisar, implementar e resolver o problema de programação de

horários de professores de uma Instituição Pública de Ensino Superior do Brasil, o qual é

proposto por um artigo publicado no Simpósio Brasileiro de Pesquisa Operacional em

2009.

2.2. Objetivos Específicos

Implementar o problema de otimização descrito no artigo na linguagem de

modelagem matemática AMPL.

Utilizar o método de solução exata e sua relaxação linear para resolver o

problema.

Utilizar o Solver CPLEX para a obtenção da solução ótima através dos dois

métodos de resolução.

Compreender e analisar as soluções geradas pelo solver CPLEX.

3. REFERENCIAL TEÓRICO

3.1. Programação Linear Inteira

Vimos que a Programação Linear Inteira são casos da Programação Linear em que

as variáveis de decisão devem ser inteiras. Ao utilizar esse modelo é importante ter em

mente o grau de dificuldade associado à sua solução. Porém, isto não implica que

problemas que exijam computadores com alta capacidade computacional não possam ser

resolvidos em um tempo aceitável. É possível encontrar boas soluções viáveis e mostrar

quão próximo da solução ótima pode estar, mesmo que a solução ótima não seja

encontrada.

Segundo Alvez (1997), um problema de Programação Linear Inteira (PLI) é um

problema de Programação Linear (PL) em que todas ou alguma (s) das suas variáveis são

discretas (têm de assumir valores inteiros). Quando todas as variáveis estão sujeitas à

condição de integralidade estamos perante um problema de Programação Linear Inteira






Pura (PLIP); e se apenas algumas o estão, trata-se de um problema de Programação Linear

Inteira Mista (PLIM). Embora a Programação Inteira (PI) inclua também a Programação

Não-Linear Inteira, em praticamente todos os modelos da vida real se preserva a estrutura

linear das funções, pelo que quase não existe diferença entre a PI e a PLI. Os modelos de

PLI serão então do tipo dos modelos de PL, sujeitos a restrições adicionais indicando que

algumas ou todas as variáveis são discretas.

Existe um caso especial de variáveis inteiras: as variáveis binárias que apenas

podem tomar os valores 0 (zero) ou 1 (um). Quando todas as variáveis de um modelo são

binárias, o modelo diz-se de Programação Inteira Binária. As variáveis binárias são muito

úteis para exprimirem situações dicotómicas

3.2. Relaxação Linear

O termo Relaxação Linear, em uma Programação Linear Inteira é utilizado para

indicar que algumas das restrições do problema original foram relaxadas. Esta relaxação

é uma maximização para o problema e é obtida movendo a integralidade das variáveis.

De uma maneira mais teórica, se tivermos uma formulação F representada por:

𝑍 = min {𝑐(𝑥): 𝑋 ∈ 𝑃}

sendo P o conjunto de pontos que satisfazem as restrições dessa formulação, 𝑐(𝑥) a

função objetivo e 𝑍 o valor da solução ótima. Dizemos que uma formulação 𝐹𝑅 dada por

𝑍𝑅 = min {𝑓(𝑥): 𝑋 ∈ 𝑅}

é uma relaxação se todo ponto de 𝑃 está em 𝑅 , ou seja 𝑃 ⊆ 𝑅 e se 𝑓(𝑥) ≤ 𝑐(𝑥) para

𝑥 𝜖 𝑃.

É possível notar que devido a essas propriedades, a solução ótima da relaxação é

um limitante dual (ou seja, no nosso caso é um limite inferior e superior no de

maximização) para a formulação original ou seja, 𝑍𝑅 ≤ 𝑍. Os Limitantes duais podem ser

utilizados, por exemplo, para melhorar o desempenho do algoritmo de Branch and Bound.






Ao se utilizar relaxações tem se a vantagem que em certos casos elas são mais

fáceis de serem resolvidas. Por exemplo, as relaxações lineares podem ser resolvidas em

tempo polinomial, enquanto a versão restrita a inteiros, em geral, é N P ‑difícil.

A relaxação de uma formulação também pode ser obtida removendo algumas de

suas restrições. Porém quanto mais relaxamos a formulação pior tende a ser a qualidade

do limitante dual (considera-se o caso extremo onde se removem todas as desigualdades

do modelo: não deixa de ser uma relaxação, mas o limitante dual obtido não tem

utilidade). O ideal é que se encontre uma relaxação fácil de resolver e que dê limitantes

duais de qualidade, ou seja, bem próximos do valor ótimo da formulação original.

3.3. Linguagem AMPL

AMPL (Algebraic Modeling Programming Language”) compõe uma linguagem

de modelagem de programação matemática. Quando comparado com linguagens já

existentes, ela se destaca pela generalidade de sua sintaxe e principalmente pela

semelhança de suas expressões a notação algébrica habitualmente utilizada na

modelagem de programas matemáticos. Vaz et al (1999, p. 8) acrescenta que essa

proximidade da linguagem AMPL da linguagem matemática, “permite que problemas de

pequenas dimensões e complexidade sejam escritos num tempo razoável sem exigir um

grande esforço de aprendizagem da linguagem. ”

Segundo Fourer (1983 apud FOURER et al, 1990) a linguagem AMPL possui uma

considerável inspiração vinda da linguagem XML, no entanto ela incorpora várias

mudanças e ampliações. Fourer et al (1990) ressalta que a linguagem AMPL por si só,

pode ser somente utilizada para especificar classes de modelos de programação

matemática, sendo incorporada em um sistema que gera dados, modelos e soluções.






A linguagem ainda, faz distinção entre um determinado modelo e seus dados

(ficheiros .mod e .dat), uma vez que permite a definição de um modelo genérico e do

conjunto de dados que instanciam os parâmetros declarados. Um exemplo básico de um

modelo e de um conjunto de dados escritos em AMPL, podem ser vistos na figura 1

abaixo.

Figura 1. Exemplo de Problema em AMPL

Fonte: [Vaz et al, 1999]

4. DESCRIÇÃO DO PROBLEMA

O problema abordado neste relatório foi extraído do artigo “Programação do quadro

de horários de disciplinas de uma universidade via programação inteira” cuja a autoria

pertence a Erito Marques de Souza Filho e Carla Regina Gomes. O artigo foi publicado

no XLI Simpósio Brasileiro de Pesquisa Operacional (SBPO) em 2009 e permeia a

elaboração de um horário das disciplinas de cada curso, distribuindo os docentes

responsáveis pelas mesmas. A esse aspecto tem-se diversas particularidades envolvidas

que devem ser levadas em consideração, sendo analisadas com cautela. O objetivo maior

é a elaboração de um quadro de horários que satisfaça tanto o corpo docente, quanto o

discente. Segundo Filho e Gomes (2009, p. 360), “a realização desta tarefa é classificada

como um problema trabalhoso, sendo comparada ao ato de se montar um quebra-cabeça”,

uma vez que em muitos casos ela é feita manualmente.






Assim, a finalidade do artigo a qual se baseia este relatório é elaborar um quadro de

horários que distribua de forma adequada um conjunto de disciplinas a serem ministradas

semestralmente, considerando os professores disponíveis, e respeitando a preferência por

disciplina, preferência pelo dia da semana, um número mínimo e máximo de disciplinas

ministradas para cada professor, número máximo de disciplinas a serem oferecidas

diariamente e a quantidade máxima de salas disponíveis por dia.

5. DESCRIÇÃO DO MODELO DE OTIMIZAÇÃO

Como mencionado anteriormente, o modelo de otimização do artigo estudado,

abrange a programação linear inteira, sendo utilizado para a programação de horários dos

professores de uma Instituição Pública de Ensino Superior Brasileira. Abaixo verifica-se

a sua nomenclatura e formulação.

Índices

o Professores: p {1, 2, 3, ... , P};

o Disciplinas: d {1, 2, 3, ... , D};

o Dias da semana: t {segunda-feira, terça-feira, quarta-feira, quinta-feira,

sexta-feira}.

Conjuntos

o Mp: conjunto das disciplinas que podem ser ministradas pelo p-ésimo

professor.

o Sp: conjunto dos dias da semana na qual o professor p gostaria de ser

alocado.

Parâmetros

o Cp,d,t : Custo de alocação do professor p, na disciplina d, no dia t;

o Qt: Quantidade de salas disponíveis por dia;

o Minp: Quantidade mínima de aulas a serem ministradas por professor;

o Maxp: Quantidade máxima de aulas a serem ministradas por professor.

Variável

o xp,d,t = 1, se o professor p é alocado na disciplina d no dia t;






o xp,d,t = 0, caso contrário.

Modelo de Otimização

𝑀𝑖𝑛 ∑ ∑ ∑ 𝐶𝑝,𝑑,𝑡

𝑡𝑑𝑝

𝑥𝑝,𝑑,𝑡 (1)

Sujeito a:

𝑀𝑖𝑛𝑝 ≤ ∑ ∑ 𝑥𝑝,𝑑,𝑡

𝑡∈𝑆𝑝𝑑∈𝑀𝑝

≤ 𝑀𝑎𝑥𝑝, ∀𝑝 (2)

∑ ∑ 𝑥𝑝,𝑑,𝑡

𝑑𝑝

≤ 𝑄𝑡, ∀𝑡 (3)

∑ ∑ 𝑥𝑝,𝑑,𝑡

𝑡𝑝:𝑑∈𝑀𝑝

= 1, ∀𝑑 ∈ 𝐷 (4)

∑ 𝑥𝑝,𝑑,𝑡

𝑑

≤ 1, ∀𝑝, 𝑡 (5)

𝑥𝒑,𝒅,𝒕 ∈ {0,1}, ∀𝑝, 𝑑, 𝑡 (6)

A equação (1) representa a função objetivo que minimiza o custo total de

alocação dos professores.

A equação (2) indica que para cada professor, existe um número mínimo

e máximo de aulas a serem ministradas.

A equação (3) indica que o número total de alocações feitas por dia é

limitado a capacidade de salas disponíveis naquele dia.

A equação (4) estabelece que todas as disciplinas devem ser lecionadas.

A equação (5) estabelece que cada professor não pode dar duas disciplinas

no mesmo dia

A equação (6) indica que as variáveis são binarias.






5.1. Definição das Instâncias

As instâncias foram definidas por meio de uma análise das particularidades presente

no modelo de otimização de forma a viabilizar a implementação do mesmo. Além disso,

o instanciamento respeitou a proposta descrita para a execução deste relatório, a qual seria

a criação de 24 instâncias com três diferentes dimensões para o problema abordado.

Os arquivos de dados abordam as instâncias propostas considerando: a relação de

professores e suas respectivas disciplinas de afinidade referente a cada dimensão do

problema; o número mínimo e máximo de aulas a serem ministradas, os quais foram

definidos igualmente a todos os professores; e os respectivos custos de alocação dos

mesmos, os quais estão dispostos no anexo A deste relatório. Ressalta-se que cada

professor possui um custo de alocação distinto um do outro em cada dimensão

implementada.

6. RESULTADOS COMPUTACIONAIS

O modelo descrito acima, foi implementado na linguagem AMPL. O solver utilizado

para a resolução do problema foi o CPLEX, sendo os testes computacionais realizados

em um computador Intel Core i5 1.80GHz com 4 GB de memória RAM.

Para as 24 instâncias definidas, utilizou-se na resolução dos problemas dois métodos:

o método exato, e sua relaxação linear. Ambos os métodos proporcionaram resultados

significativos que podem ser observados na seção seguinte.

6.1. Resultados por meio do Método Exato

As Tabelas 1, 2 e 3 exibem os resultados – tempos computacionais, iterações e

soluções ótimas – para o método exato de cada instância e dimensão criada.






Tabela 1- Resultados da dimensão 1 para o método exato.

Fonte: Elaborado pelos Autores.

Tabela 2 - Resultados da dimensão 2 para o método exato.

DIMENSÃO 2

N° de Professores: 15

N° de disciplinas: 48

Instância Tempo de Resolução (s) Iterações Solução Ótima

1 0,09375 308 3183

2 0,09375 298 2974

3 0,09375 291 3056

4 0,125 311 2988

5 0,125 304 2970

6 0,03125 321 2850

7 0,015625 290 2929

8 0,03125 309 2641

Fonte: Elaborado pelos Autores

DIMENSÃO 1




1 0,09375 111 905

2 0,078125 110 1070

3 0,0625 111 825

4 0,078125 86 789

5 0,0625 85 909

6 0,0625 101 1305

7 0,0625 102 1605

8 0,078125 118 1735






Tabela 2 - Resultados da dimensão 3 para o método exato.

DIMENSÃO 3




1 0,046875 464 1557

2 0,046875 486 1959

3 0,046875 483 1975

4 0,03125 469 2101

5 0,03125 517 2257

6 0,03125 456 2286

7 0,046875 342 2272

8 0,046875 448 2627


6.2. Resultados por meio da Relaxação Linear

As Tabelas 3, 4 e 5 exibem os resultados – tempos computacionais, iterações e

soluções ótimas – para a relaxação linear referente a cada instância e dimensão criada.

Tabela 3 - Resultados da dimensão 1 para o método de Relaxação Linear.


DIMENSÃO 1




1 0,078125 91 905

2 0,046875 100 1070

3 0,0625 109 825

4 0,0625 101 789

5 0,0625 116 909

6 0,0625 98 1305

7 0,0625 113 1605

8 0,0625 105 1735










DIMENSÃO 2




1 0,078125 263 3183

2 0,09375 249 2974

3 0,046875 233 3056

4 0,09375 265 2988

5 0,09375 281 2970

6 0,015625 300 2850

7 0,015625 297 2929

8 0,015625 263 2641

DIMENSÃO 3




1 0,015625 337 1557

2 0,015625 345 1959

3 0,03125 357 1975

4 0,03125 352 2101

5 0,03125 352 2257

6 0,03125 359 2286

7 0,03125 314 2272

8 0,015625 315 2627






7. CONCLUSÃO

O presente relatório propôs uma abordagem em termos práticos do problema descrito

no artigo, afim de compreender, implementar e resolver tal problema a luz da disciplina

de Otimização Combinatória. Dessa forma, em análise do problema abordado e dos

resultados obtidos a partir da implementação do modelo de otimização, torna-se evidente

a eficácia da utilização deste modelo na alocação de professores, pelo simples fato de

gerar uma solução ótima com uma rapidez surpreendente.

O modelo em questão, exigiu um processo de definição de instâncias de forma bem

analítica. Foi necessário compreender bem as restrições existentes, de forma a criar

instâncias que proporcionassem soluções viáveis. Em contrapartida, o processo de

transcrição do modelo formulado para uma linguagem de modelagem de programação

matemática, foi tido como um processo mais simplificado e flexível, sendo assim mais

transparente a execução desta etapa.

Um outro aspecto a ser considerado, é a utilização de dois métodos distintos na

resolução do problema. Verificou-se que ambos os métodos obtiveram a solução ótima,

no entanto essa solução era gerada por um método com um tempo computacional menor

quando comparado ao outro método. Observou-se que, praticamente em totalidade, o

método de relaxação linear gerava soluções ótimas em um tempo bem mais reduzido do

que o método exato. A relaxação de um problema, vem então com a finalidade de tornar

este problema mais fácil de se resolver. Portanto, concluiu-se que em geral Problemas de

Programação Inteira são mais difíceis de se resolver quando comparado com Problemas

de Programação Linear.






8. REFERÊNCIAS BIBLIOGRÁFICAS

ALVES, R; DELGADO, C; Programação Linear Inteira. Setembro de 1997.

FILHO, E. M. S; GOMES, C. R. Programação do Quadro de Horários de Disciplinas

de uma Universidade via Programação Inteira. XLI Simpósio Brasileiro de Pesquisa

Operacional, 2009. Disponível em: <

http://www.din.uem.br/sbpo/sbpo2009/artigos/55634.pdf>. Acesso em: 15 jun. 2015.

FOURER R.; GAY D.; KERNIGHAN B.A Modeling Language for Mathematical

Programming. Management Science 36 (1990) 519{554. Disponível em: <

http://www.ampl.com/REFS/amplmod.pdf>. Acesso em: 28 jun. 2015.

MIRANDA, G. T; MARTINS, V. F; FARIA, A.F. O uso da Programação Linear num

contexto de Laticínios com várias Restricoes na Capacidade Produtiva. Custos e

@gronegócio online – v. 3 – Edicao Especial, maio 2007. Disponível em:<

http://www.custoseagronegocioonline.com.br/especialv3/programacao%20linear.pdf>.

Acesso em: 28 jun. 2015.

SUCENA, M. PROGRAMAÇÃO LINEAR INTEIRA, 2012. Disponível em: <

http://www.sucena.eng.br/eng_producao/UNESA_PESQUISA_OPERACIONAL_II_20

12_2.pdf >. Acesso em: 25 de junho

VAZ, I; MONTEIRO, T; FERNANDES, E. Ambientes de Programação e Interface

para Problemas de Optimização. Departamento de Produção e Sistemas - Escola de

Engenharia, Universidade do Minho, 1999. Disponível em:<

http://repositorium.sdum.uminho.pt/bitstream/1822/5323/1/Final_CUTE_AMPL.pdf>.

Acesso em: 28 jun. 2015

http://www.din.uem.br/sbpo/sbpo2009/artigos/55634.pdf

http://www.ampl.com/REFS/amplmod.pdf

http://www.custoseagronegocioonline.com.br/especialv3/programacao%20linear.pdf

http://repositorium.sdum.uminho.pt/bitstream/1822/5323/1/Final_CUTE_AMPL.pdf






ANEXO

Neste anexo estão dispostas as tabelas que fazem referência ao custo de alocação de cada

professor.

Tabela 1- Custo de alocação para cada professor em um total de 20 professores.

Professores 1 2 3 4 5 6 7 8

Augusto 21 21 28 48 43 41 41 47

Brenda 40 46 41 51 51 54 64 62

Carlos 30 30 23 16 26 36 36 39

Flávio 33 63 70 60 60 64 74 74

João 18 42 57 103 108 68 63 73

Jorge 44 13 19 39 36 36 26 22

José 20 26 29 29 19 16 36 36

Kaio 23 23 30 30 38 38 48 48

Laura 12 10 10 19 29 29 26 36

Luan 100 85 81 84 74 72 32 35

Lucas 35 38 42 16 12 32 34 54

Lucia 13 53 53 60 70 71 71 79

Mara 34 37 44 14 14 12 42 42

Maria 27 30 40 14 14 24 29 49

Marta 11 33 36 36 46 48 18 18

Mônica 22 57 17 17 35 38 48 88

Pâmela 45 41 41 47 57 51 55 45

Pedro 21 21 14 36 36 26 24 24

Silva 23 29 25 31 37 47 42 48

Viviane 12 25 25 35 33 32 32 38



Brenda 40 45 55 55 58 58 68 68

Carlos 30 32 42 42 48 68 68 61

João 100 105 100 90 95 75 71 71

José 35 32 39 39 31 41 42 42

Kaio 78 78 71 72 72 62 68 68






Laura 12 12 22 29 29 24 21 21

Luan 130 130 138 102 102 92 95 93

Lucas 70 75 85 81 71 71 74 14

Lucia 67 87 82 82 89 81 81 72

Maria 60 70 75 65 63 83 83 73

Marta 111 100 100 105 95 95 91 92

Mônica 22 28 25 27 37 31 36 33

Pâmela 85 35 35 45 42 32 33 43

Pedro 88 78 76 76 66 62 62 52

Silva 120 98 78 73 83 53 55 55



Carlos 50 25 25 55 88 80 38 14

João 50 50 40 44 44 70 77 92

José 15 40 30 33 15 73 45 33

Laura 30 40 40 23 76 46 65 65

Lucas 35 35 30 30 35 28 68 120

Maria 20 30 20 22 38 45 50 90

Marta 40 50 25 25 37 17 26 34

Mônica 25 20 25 43 17 30 61 36

Pedro 50 50 50 10 13 77 70 99

Silva 20 50 20 11 34 19 91 66

Documents

RELATÓRIO