Boletim
Ano 9 Número 18
Outubro de 2011
Informativo do Grupo de Pesquisa
Matemática Computacional
-------------------------------------------------------------------------------------------------------------PONTIFÍCIA UNIVERSIDADE CATÓLICA DE GOIÁS (PUC-Goiás)
DEPARTAMENTO DE COMPUTAÇÃO
-------------------------------------------------------------------------------------------------------------EDITORIAL
Temos a satisfação de publicar mais um número do Boletim para os interessados em
Computação. Em particular, em Matemática Computacional.
Na seção Perguntas e Respostas apresentamos valores para bolsas de pósgraduação. Na seção Artigo, publicamos uma errata do artigo do boletim passado, em
virtude de problemas técnicos da configuração original para o boletim (que ainda persiste
alguns!) e, naturalmente, pelos próprios erros.
Os integrantes do grupo no momento são: como pesquisadores, Clarimar José
Coelho, Marco Antonio Figueiredo Menezes (PUC Goiás), Leizer de Lima Pinto (UFG) e
Nelson Maculan Filho (PESC/COPPE/UFRJ); como estudantes, Bruno Diniz Faria, Dalilla
da Mota Morais, Douglas Machado de Freitas, Francisco de Assis Rodrigues dos Anjos,
Hailton David Lemos, Heber Valdo Nogueira, Lino Lopes de Barros Filho, Lorena Alves
dos Santos, Robson Iwamoto Ribeiro da Costa, Roneidson José da Silva Sousa (PUC
GOIÁS), Kelligton Fabrício de Souza Neves (PESC/COPPE/UFRJ); e Elivelton Ferreira
Bueno (Universidade de Montreal/Canadá); e como técnicos, Ivon Rodrigues Canedo (PUC
Goiás), Anderson da Silva Soares, Arlindo Rodrigues Galvão Filho, Synara Rosa Gomes
dos Santos, Tiago da Silva Curtinhas (ITA), Gustavo Teodoro Laureano (USP/São Carlos),
Gustavo Siqueira Vinhal (UFG).
Marco Antonio Figueiredo Menezes
Líder do Grupo
-------------------------------------------------------------------------------------------------------------PERGUNTAS E RESPOSTAS
Aqui, a nossa ideia é a de levantar algumas perguntas para os alunos da Computação
que venham a esclarecer, viabilizar e integrar a sua formação. Em seguida, forneceremos as
devidas respostas através de entrevistas com responsáveis pela área.
VALORES DE BOLSAS DE PÓS-GRADUAÇÃO DA CAPES E CNPq NO PAÍS
Valor das bolsas da Capes no país
1
Mestrado: R$ 1.200,00
Doutorado: R$ 1.800,00
Pós-Doutorado: R$ 3.300,00
Professor Visitante Nacional Sênior: R$ 8.905,42
Valor das bolsas do CNPq no país
Doutorado: R$ 1.800,00
Doutorado Sanduíche: R$ 2.000,00
Doutorado Sanduíche Empresarial: R$ 2.000,00
Mestrado: R$ 1.200,00
Pós-doutorado Sênior: R$ 4.000,00
Pós-doutorado Júnior: R$ 3.200,00
Pós-doutorado Empresarial: R$ 3.200,00
Maiores informações a respeito destes valores podem ser obtidas pelo site
http://www.capes.gov.br/bolsas/valores-das-bolsas
e
http://www.cnpq.br/normas/rn_10_005.htm#pais.
-------------------------------------------------------------------------------------------------------------ACONTECEU
Aconteceu informa Congressos, Simpósios, Jornadas e Encontros Científicos com a
nossa participação, de março/2011 a setembro/2011.
Congressos, Simpósios e Workshops:
1. XXI Congresso da Sociedade Brasileira de Computação – De 19 a 22 de Julho
de 2011 – Natal-RN. (http://www.dimap.ufrn.br/csbc2011/csbc2011.php)
2. XLII Simpósio Brasileiro de Pesquisa Operacional - De 15 a 18 de agosto de
2011 - Ubatuba-SP (http://www.feg.unesp.br/dpd/xliiisbpo/)
3. XXXIV Congresso Nacional de Matemática Aplicada e Computacional - De 20
a 23 de Setembro de 2011 – Águas de Lindóia – SP.
(http://www.sbmac.org.br/noticias.php?nid=490)
-------------------------------------------------------------------------------------------------------------ACONTECENDO
Acontecendo relata as atividades do Grupo Matemática Computacional. Sugerimos
uma visita ao nosso MURAL, em frente ao Departamento de Computação e próximo às
salas 411 e 412, bloco F, área 3.
Seminário de Otimização: Toda sexta-feira, das 17h às 18h, na Área 3, Bloco F, Sala 411.
Coordenador: Dr. Marco Antonio Figueiredo Menezes.
2
Seminário de Análise Multivariada: Toda quinta-feira, das 17h às 18h, na Área 3, Bloco
F, Sala 412. Coordenador: Dr. Clarimar José Coelho.
Projetos em andamento:
1. Desenvolvimento
do
LabPL
(primeiro
ano
–
–
)
Coordenador: Marco Antonio; PROPE/UCG.
2. Combustíveis Importados – Calibração por FTIR e transferência para 35
laboratórios
da
PF
(segundo
ano
–
http://www.pucgoias.edu.br/prope/projeto/admin/ficha_cadastro.asp?inscricao=3835
)
–
Coordenador: Clarimar José Coelho; PROPE/UCG.
3. Estudo de autenticidade de documentos por meio da análise de tintas de canetas
empregando a Micro-espectrometria no Infravermelho e Raman (segundo ano http://www.pucgoias.edu.br/prope/projeto/admin/ficha_cadastro.asp?inscricao=383
4) - Coordenador: Clarimar José Coelho; PROPE/UCG.
http://www.pucgoias.edu.br/prope/projeto/admin/ficha_cadastro.asp?inscricao=4013
Orientações em andamento: apenas iniciação científica.
1. Implementação de um algoritmo fortemente polinomial para programação linear. Aluno: Lino Lopes de Barros Filho; Orientador: Marco Antonio; Iniciação
Científica.
2. Implementação do métodos MLR, PCR, e PLSR utilizando programação paralela e
comparação estatística do ganho de desempenho com relação às implementações
sequenciais pertencentes ao LAMV. – Aluno: Francisco de Assis Rodrigues dos
Anjos; Orientador: Clarimar José Coelho; Iniciação Científica.
3. Estudo de autenticidade de documentos por meio da análise de tintas de canetas e
imagens hiperespectrais utilizando redes neurais artificiais. – Aluno: Heber Valdo
Nogueira; Orientador: Clarimar José Coelho; Iniciação Científica.
4. Implementação de software para calibração FT-IR com mínimos quadrados parciais.
– Aluno: Lorena Alves dos Santos; Orientador: Clarimar José Coelho; Iniciação
Científica.
5. Implementação de software para o modelo de regressão linear múltipla. – Aluno:
Roneidson José da Silva Sousa; Orientador: Clarimar José Coelho; Iniciação
Científica.
-------------------------------------------------------------------------------------------------------------ACONTECERÁ
Acontecerá informa eventos nos próximos meses no que concerne às atividades de
pesquisa.
-------------------------------------------------------------------------------------------------------------PRODUÇÃO CIENTÍFICA
3
Divulgação da produção científica. Este Boletim divulga o período março/2011setembro/2011.
Orientações concluídas: apenas iniciação científica.
1. Implementação de um algoritmo randômico para programação linear. – Aluno: Lino
Lopes de Barros Filho; Orientador: Marco Antonio; Iniciação Científica.
2. Um estudo sobre o problema de designação turmas-salas. – Aluna: Arinéia Nogueira de
Assis; Orientador: Marco Antonio; Iniciação Científica.
3. Implementação de software para o modelo de regressão em mínimos quadrados
parciais. – Aluno: Douglas Machado de Freitas; Orientador: Clarimar José Coelho;
Iniciação Científica.
4. Implementação de software para o modelo de regressão em mínimos quadrados
parciais. – Aluno: Francisco de Assis Rodrigues dos Anjos; Orientador: Clarimar José
Coelho; Iniciação Científica.
5. Implementação de software para calibração FT-IR com componentes principais. –
Aluno: Dalilla da Mota Morais; Orientador: Clarimar José Coelho; Iniciação Científica.
--------------------------------------------------------------------------------------------------------------
4
ARTIGO – ERRATA
Uma Breve Introdução à Programação Linear
Inteira
Marco Antonio Figueiredo Menezes
Departamento de Computação da
Pontifícia Universidade Católica de Goiás (PUC Goiás)
Mestrado em Engenharia de Produção e Sistemas da PUC Goiás
Endereço Eletrônico: [email protected]
Abril/2011
Resumo
Nosso objetivo aqui é definir o problema de programação linear inteira (PLI) e o problema
de programação linear inteira 0-1 e discorrer sobre eles. Gostaria de agradecer aos colegas
E. F. Bueno e M. S. N. Rangel pelas discussões sobre terminologias da área e pela correção
minuciosa da primeira versão, e ao colega N. Maculan pelas notas de aula.
1. Problemas de programação linear inteira
O problema de otimização consiste em encontrar, se possível, os minimizadores ou os
maximizadores de uma função definida em uma determinada região.
Denotamos
o conjunto dos números naturais, o conjunto dos números
inteiros,
o conjunto dos números inteiros não negativos,
o conjunto cartesiano de
conjuntos dos números inteiros, o conjunto dos números reais,
o conjunto cartesiano
de conjuntos dos números reais,
o conjunto de zeros e uns, e
o conjunto
cartesiano de conjuntos de zeros e uns.
Definição 1.1 Sejam dados um conjunto
e uma função
(a) Dizemos que um ponto
é um minimizador global de
para todo x D,
.
em
quando,
(b) Dizemos que um ponto
é um minimizador local de
‖
‖
existe um
tal que, para todo
em
quando,
5
Consideremos os números inteiros
e tais que
. Dados uma matriz
numérica com coeficientes reais ,
, e vetores
e
, uma formulação
para o problema de programação linear inteira (PLI) é o seguinte problema de otimização:
minimizar
sujeito a:
.
Por outro lado, uma formulação para o problema de programação linear inteira 0-1
(binário) é o seguinte problema de otimização:
minimizar
sujeito a:
.
Em ambos os problemas
e
, a função objetivo é definida pela função linear
; o valor da função objetivo definido pelo número
; o conjunto viável definido
pelo conjunto
,
ou
;
um ponto viável definido como um elemento do conjunto viável; o conjunto de soluções
ótimas definido pelo conjunto
,
ou
;
uma solução ótima definida como um elemento do conjunto de soluções ótimas; o
problema
é inviável quando é vazio, e o problema
é inviável quando é vazio;
e o problema
é ilimitado quando existe uma sequência
tal que
e, quando
,
.
A proposição a seguir mostra que trabalhar com minimização ou maximização é
equivalente. A demonstração pode ser encontrada nas páginas 67 e 68 em [1].
Proposição 1.2 Sejam
linear. Então,
um conjunto viável para
ou
e
uma função
6
.
Demonstração: Seja
um maximizador global do problema
.
Para todo
equivalente a,
temos: pela definição de
,
. Portanto, para todo
, que é
,
, finalizando a demonstração.
Em programação linear (contínua) o minimizador global (maximizador global) é o
minimizador local (maximizador local). Isso não é verdade para PLI. Por exemplo, para o
problema
minimizar
sujeito a:
o ponto
é o minimizador global (e local), enquanto que o ponto
é
um minimizador local (mas não minimizador global) com valor da função objetivo igual a
. Já o ponto
não é um minimizador local, apesar de seu valor objetivo ser igual a
, também. Aliás, isto ilustra minimizador local, o qual depende de uma vizinhança no
conjunto viável (neste exemplo, uma vizinhança com raio um na norma infinito) além do
valor da função objetivo.
A proposição a seguir mostra que o problema de PLI
pode ser reduzido ao
problema
. A demonstração pode ser encontrada na página 2 em [6]. Denotamos o
número
como o maior inteiro menor do que ou igual ao número real .
1
Proposição 1.3 Suponha que no problema de PLI (P) cada
, com
,
. Então, este novo problema de PLI pode ser reduzido ao problema de PLI 0.
Demonstração: Considere
desigualdades
. Para cada
∑
retirando cada restrição
desigualdades
,
⌊
⌋
. Seja o problema
, substitua-os por
⌊ ⌋
com o acréscimo de
,
. Então, reduzimos o problema (P), com o acréscimo das
, para o problema
. Isto finaliza a demonstração.
Para exemplificar o uso desta proposição, consideremos o problema de PLI com suas
variáveis inteiras limitadas, a saber (veja páginas 249 e 250 em [3]):
7
minimizar
sujeito a:
.
O conjunto viável para este problema são os pontos
,
e
, cuja solução
ótima é o ponto
, com valor ótimo igual a
. Usando a proposição anterior, vamos
substituir
∑
,
e
∑
,
e vamos retirar as restrições
de PLI 0-1
e
. Dessa forma, obtemos o problema
minimizar
sujeito a:
.
Aqui, uma solução ótima é o ponto
,
cujo valor ótimo é igual a
.
A proposição a seguir mostra que pensar em uma relaxação
para o problema de
PLI
pode ser mais interessante do que reescrevê-lo como um problema de PLI
.A
demonstração pode ser encontrada na página 457 em [4]. Denotamos o vetor de uns de
dimensão apropriada por .
Proposição 1.4 Toda solução viável para o problema de PLI 0-1
extremo do conjunto
é um ponto
.
Demonstração: Fixe arbitrariamente
um ponto extremo de . Segue-se que existem
̅
. Suponha, por contradição, que
,
tal que
não é
.
De fato,
8
e, para todo
,
,
| |
|
|
|
|
|
|
.
Considere
. Temos
, para algum , pois caso contrário, deveríamos ter
para todo , isto é,
; o que não pode ocorrer. Ainda, temos
,
para algum , pois caso contrário, deveríamos ter
para todo , isto é,
;
o que não pode ocorrer, também. Portanto, existe ,
, tal que
, isto
é,
; contradição. Pela arbitrariedade de finalizamos a demonstração.
A recíproca desta proposição é falsa. Por exemplo, para o problema
minimizar
sujeito a:
,
temos os pontos extremos
e
, enquanto que para o problema
minimizar
sujeito a:
,
temos a única solução viável
.
A definição a seguir nos auxilia a olhar para a resolução de um problema de PLI
através de métodos de programação linear (contínua).
Definição 1.5 Uma matriz quadrada com coeficientes inteiros é chamada matriz
unimodular, quando seu determinante é igual a
ou igual a . Uma matriz com
coeficientes inteiros
é chamada matriz totalmente unimodular, quando qualquer
submatriz quadrada não singular de é unimodular.
O teorema a seguir mostra que em um problema de PLI pode ser melhor resolvê-lo
como um problema de programação linear, dependendo da matriz satisfazer a condição
de unimodularidade total, cuja demonstração pode ser encontrada na página 316 em [5].
Teorema 1.6 Se
extremos de
é uma matriz totalmente unimodular, então todos os pontos
são vetores com coordenadas inteiras para qualquer vetor de inteiros .
9
Demonstração: Suponha
uma matriz totalmente unimodular. Por definição,
qualquer submatriz quadrada não singular de é unimodular. Fixe arbitrariamente uma
submatriz unimodular, obtida pelas colunas de A, tal que
,
em que
é uma submatriz formada pelas colunas restantes de . Como todo ponto
extremo é uma solução básica viável e vice-versa, segue-se que uma solução básica viável
de , associada a , pode ser escrita como
e
.
Por definição de matriz inversa,
. Uma vez que
é uma matriz
unimodular,
. Segue-se que se é um vetor de inteiros, então é um vetor de
inteiros em . Pela arbitrariedade de , todos os pontos extremos de são vetores com
coordenadas inteiras para qualquer vetor de inteiros . Isto finaliza a demonstração.
A recíproca deste teorema é falsa. Por exemplo, defina
com
[
]e
[ ].
Com efeito, os pontos extremos
,
,
,
[ ] [ ] [ ] [ ]
são todos vetores com coordenadas inteiras, todavia a submatriz quadrada não singular
[
possui
; que é diferente tanto de
]
quanto de .
Na capa do livro em Foulds [2] tem uma figura cujo enunciado é o seguinte,
conforme página 83 de seu livro:
10
minimizar
sujeito a:
.
Relaxando esse problema para obtermos um problema de programação linear, isto é,
substituímos as variáveis de valores inteiros por valores reais, obtemos a solução ótima para
o problema de programação linear
(
),
com valor da função objetivo igual a
. Observe que se conseguíssemos uma solução
inteira teríamos resolvido o problema de programação linear inteira. Uma pergunta natural,
mas não intuitiva: por que não arredondar? Porque se assim o fizermos obteremos as
possíveis soluções, baseadas em
e
,
que são
,
,
ou
,
mas as soluções ótimas são
e
,
com valor ótimo da função objetivo igual a 6. Quer dizer, arredondamento nem sempre
funciona. A propósito, para esse problema simples, mas bastante ilustrativo, temos oito
soluções viáveis para duas variáveis.
Referências
[1] P. F. Bregalda, A. A. F. de Oliveira e C. T. Bornstein. Introdução à Programação
Linear. 3a edição. Rio de Janeiro: Campus, p. 329, 1988.
[2] L. R. Foulds. Combinatorial Optimization for Undergraduates. New York: SpringerVerlag, p. 222, 1984.
[3] M. Minoux. Mathematical Programming: theory and algorithms. John Wiley &
Sons, 1986.
11
[4] G. L. Nemhauser e L. A. Wolsey. Integer and Combinatorial Optimization. New
York: John Wiley & Sons, p. 777, 1988.
[5] C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: algorithms and
complexity. Mineola: Dover, p. 512, 1998.
[6] H. M. Salkin. Integer Programming. Massachusetts: Addison Wesley, p. 557, 1975.
-------------------------------------------------------------------------------------------------------------INFORMAÇÕES E CONTATO
Página Principal: http://www.pucgoias.edu.br/NPI/index.asp
Página do boletim: http://www.pucgoias.edu.br/NPI/matematicacomp_boletim.htm
[email protected]
12