XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: UM ESTUDO DE MÉTODOS DE CORTES E DE TÉCNICAS DE FIXAÇÃO DE VARIÁVEIS APLICADOS À RESOLUÇÃO DE PROBLEMAS DE PARTICIONAMENTO Autor: MARCELO PRAIS
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
CELSO DA CRUZ CARNEIRO RIBEIRO - ORIENTADOR
Nº do Conteudo: 10249
Catalogação: 06/08/2007 Idioma(s): PORTUGUÊS - BRASIL
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10249@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10249@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.10249
Resumo:
Título: UM ESTUDO DE MÉTODOS DE CORTES E DE TÉCNICAS DE FIXAÇÃO DE VARIÁVEIS APLICADOS À RESOLUÇÃO DE PROBLEMAS DE PARTICIONAMENTO Autor: MARCELO PRAIS
Nº do Conteudo: 10249
Catalogação: 06/08/2007 Idioma(s): PORTUGUÊS - BRASIL
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10249@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10249@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.10249
Resumo:
Este trabalho consiste da aplicação de métodos de planos
de corte (euclideano acelerado e cortes disjuntivos) na
solução de problemas de programação inteira pura do tipo 0-
1 e suas especializações para o problemas de
particionamento, quando combinados com técnicas de
penalidades para fixação de variáveis.
Desenvolve-se um estudo de técnicas de penalidades, que
permitem fixar variáveis a valores inteiros a partir da
solução ótima da relaxação linear do problema inteiro. As
variáveis fixadas são eliminadas do problema e este é
reescrito, tendo suas dimensões originais reduzidas.
Sugerem-se melhorias no cálculo destas penalidades,
levando-se em conta a estrutura particular do problema de
particionamento.
Finalmente, propõe-se um novo enfoque para a solução de
problemas de particionamento: um algoritmo de planos de
corte que utiliza técnicas de penalidades, com a
finalidade de acelerar a convergência dos métodos puros de
planos de corte e de reduzir os problemas por estes
apresentados.
Resultados computacionais são apresentados, comparando-se
o desempenho (i) do algoritmo euclideano acelerado, (ii)
do algoritmo de cortes disjuntivos e (iii) do algoritmo de
cortes disjuntivos utilizando-se técnicas de penalidades.
Para este último algoritmo, são comparados os resultados
obtidos utilizando-se técnicas de penalidades genéricas
para problemas inteiros do tipo 0-1 e as melhorias destas
penalidades, especificas para problemas de particionamento.
Considerando-se o problemas de particionamento e as
melhorias propostas no cálculo de penalidades, mostra-se
que é, freqüentemente, possível fixar um maior número de
variáveis ou até mesmo resolver-se diretamente o problema
0-1 original. Em alguns casos, ao aplicar-se o algoritmo
de planos de corte com técnicas de penalidades não só pode-
se acelerar a convergência, como também superar os
problemas de degenerescência dual e erros por
arredondamento apresentados pelos algoritmos puros de
plano de corte.
Descrição | Arquivo |
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS | |
CAPÍTULO 1 | |
CAPÍTULO 2 | |
CAPÍTULO 3 | |
CAPÍTULO 4 | |
CAPÍTULO 5 | |
REFERÊNCIAS BIBLIOGRÁFICAS |