View
7
Download
0
Category
Preview:
DESCRIPTION
Relatório de Otimização Combinatoria
Citation preview
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
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: secretaria@decea.ufop.br
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
5 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: secretaria@decea.ufop.br
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
6 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
7 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
8 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
9 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: secretaria@decea.ufop.br
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;
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
10 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
11 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
12 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: secretaria@decea.ufop.br
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
N° de Professores: 10
N° de disciplinas: 28
Instância Tempo de Resolução (s) Iterações Solução Ótima
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
13 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: secretaria@decea.ufop.br
Tabela 2 - Resultados da dimensão 3 para o método exato.
DIMENSÃO 3
N° de Professores: 20
N° de disciplinas: 60
Instância Tempo de Resolução (s) Iterações Solução Ótima
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
Fonte: Elaborado pelos Autores.
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.
Fonte: Elaborado pelos Autores.
DIMENSÃO 1
N° de Professores: 10
N° de disciplinas: 28
Instância Tempo de Resolução (s) Iterações Solução Ótima
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
14 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: secretaria@decea.ufop.br
Tabela 4 - Resultados da dimensão 2 para o método de Relaxação Linear.
Fonte: Elaborado pelos Autores.
Tabela 5 - Resultados da dimensão 3 para o método de Relaxação Linear.
Fonte: Elaborado pelos Autores.
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,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
N° de Professores: 20
N° de disciplinas: 60
Instância Tempo de Resolução (s) Iterações Solução Ótima
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
15 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: secretaria@decea.ufop.br
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.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
16 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: secretaria@decea.ufop.br
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
17 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: secretaria@decea.ufop.br
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
Tabela 2- Custo de alocação para cada professor em um total de 15 professores.
Professores 1 2 3 4 5 6 7 8
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
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Aplicadas
Campus João Monlevade
18 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: secretaria@decea.ufop.br
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
Tabela 3- Custo de alocação para cada professor em um total de 10 professores.
Professores 1 2 3 4 5 6 7 8
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
Recommended