|
MARGARIDA
VAZ PATO, Departamento de Matemática, ISEG
A OPTIMIZAÇÃO NO PROCESSO
DE DECISÃO. ALGUNS CASOS DE APLICAÇÃO
RESUMO
Nos mais diversos sectores da actividade económica, os agentes
decisores são chamados a fazer opções tendo
que considerar uma ampla e complexa gama de condicionalismos. Em
tais circunstâncias, depois de identificar um problema, a
sua abordagem por intermédio de simples modelizações
matemáticas poderá, para além de ajudar a clarificar
a situação, apoiar a tomada de decisão e fornecer
argumentos sólidos de justificação junto dos
vários intervenientes ou utentes do processo. Acresce o facto
de actualmente a internet e as folhas de cálculo disponibilizarem
software standard de fácil utilização para
resolução de problemas de pequena dimensão.
Nesta comunicação
serão apresentados alguns problemas reais surgidos na área
financeira, na gestão empresarial e na administração
pública, seguindo-se as respectivas modelizações
no contexto da optimização combinatória. Referir-se-á
o software aplicado em cada caso e comentar-se-ão brevemente
os resultados obtidos.
VOLTAR
JOÃO PAULO COSTA,
Faculdade de Economia da Universidade de Coimbra
DETERMINAÇÃO DE LIMITES
SUPERIORES PARA OS CRITÉRIOS NUM MODELO ESTOCÁSTICO
BICRITÉRIO
RESUMO
Nesta comunicação estabelecem-se duas propriedades
de um modelo estocástico bicritério, baseado em árvores
de decisão. O modelo assume que diferentes processos podem
ser utilizados para empreender uma tarefa homogénea. Cada
utilização de um processo tem um custo e demora um
certo tempo, fazendo avançar a tarefa de acordo com um processo
binomial. Pretende-se conhecer as estratégias de utilização
dos processos por forma a minimizar o custo e o tempo necessários
à realização da tarefa. Sendo um modelo que
pode ser muito útil em análise de projectos e planeamento
de produção, conduz, na maior parte dos casos práticos,
a árvores de decisão muito grandes e, consequentemente,
o tempo gasto na determinação directa das estratégias
não dominadas torna-se proibitivo.
As propriedades
que se apresentam nesta comunicação estabelecem limites
superiores para o custo e o tempo gastos na realização
de uma porção da tarefa, auxiliando assim a concepção
de algoritmos que ponham de lado partes significativas da árvore
de decisão sem que tenham de ser analisadas ou mesmo construídas.
Estes limites podem ser especialmente úteis na concepção
de algoritmos interactivos onde se pretenda determinar uma estratégia
não dominada que represente um compromisso, entre o custo
e o tempo, que esteja de acordo com as preferências de um
gestor.
Trabalho conjunto com:
Pedro Godinho (Faculdade de Economia da Universidade de Coimbra).
VOLTAR
EDITE M. G. P. FERNANDES, Departamento de Produção
e Sistemas, Universidade do Minho
UMA TÉCNICA QUASI-NEWTON
FACTORIZADA PARA PROBLEMAS DE MÍNIMOS QUADRADOS
RESUMO
Nesta comunicação é apresentada uma técnica
Quasi-Newton factorizada para resolver problemas de mínimos
quadrados não lineares. São deduzidas duas fórmulas
de actualização na forma factorizada, com o objectivo
de gerar direcções de procura descendentes para a
função objectivo. Sob certas condições,
prova-se que o algoritmo tem uma convergência local q-superlinear.
As experiências computacionais realizadas mostram que o algoritmo
é robusto e eficiente em termos práticos.
Trabalho conjunto com:
M. Fernanda P. Costa (Departamento de Matemática, Universidade do Minho).
VOLTAR
SUELY
OLIVEIRA, Department of Computer Science, University
of Iowa
MÉTODOS
DE SUBESPAÇO EM PROGRAMAÇÃO SEMI-DEFINIDA
RESUMO
Os problemas de programação semi-definida (PSD) são
problemas de optimização da forma min_X C.X sujeito
a A_i . X = a_i, i = 1,2,...,m, em que X é uma matriz simétrica
semi-definida positiva. Note-se que A.B = traço(A^T B) =
soma_{i,j} a_ij b_ij. Os problemas de PSD têm sido utilizados
recentemente para aproximar problemas difíceis em optimização
combinatória. Os problemas de PSD, embora mais fáceis
que os problemas combinatórios que aproximam, não
podem ser utilizados directamente em problemas de grandes dimensões:
se X for n×n, então, na prática, n está
limitado a aproximadamente 3×103. O nosso trabalho incide
sobre a utilização de técnicas de subspaço
para resolver problemas de PSD de grandes dimensões. Os resultados
numéricos considerados resultam da aplicação
destas técnicas a problemas de PSD provenientes do problema
da partição de grafos.
VOLTAR
CARLOS
J. LUZ, Escola Superior de Tecnologia de Setúbal,
Instituto Politécnico de Setúbal
SOBRE
O NÚMERO DE INDEPENDÊNCIA DE UM GRAFO
RESUMO
A optimização em grafos têm, actualmente, um
papel insubstituível no estudo de numerosos sistema s oriundos
de áreas tão distintas como as Telecomunicações,
a Electrónica, a Gestão, a Psicologia e a Química,
entre outras.
Um dos problemas
de optimização em grafos mais investigados consiste
na determinação de um conjunto de vértices
de um grafo, não adjacentes dois a dois, cuja cardinalidade
seja a maior possível. Esta cardinalidade diz-se o número
de independência (ou de estabilidade) do grafo. Um subconjunto
de vértices do grafo com um número de vértices
igual ao número de independência, diz-se um conjunto
independente máximo do grafo.
Recorrendo a
uma situação concreta, esta comunicação
iniciar-se-á com uma possível motivação
para o estudo do número de independência de um grafo.
Relacionaremos este número com outros números que
caracterizam o grafo e citaremos alguns desenvolvimentos da teoria
dos grafos com origem no estudo destes números.
A determinação
dum conjunto independente máximo de um grafo (bem como do
número de independência) é, em geral, um problema
de grande dificuldade, sendo esta tanto maior quanto maior for a
dimensão do grafo. Trata-se, efectivamente, de um problema
NP-hard, tal é a designação dada a uma classe
de problemas que, tal como o problema mencionado, são de
muito difícil resolução.
Dadas as dificuldades
encontradas em encontrar um
algoritmo polinomial para obter o número de estabilidade
num grafo qualquer, têm sido propostos na literatura diversos
majorantes e minorantes para aproximar aquele número.
Apresentar-se-á
nesta comunicação uma revisão dos mais significativos
majorantes do número de independência bem como de algumas
das suas propriedades. Na parte final, proceder-se-á à
comparação dos majorantes apresentados à luz
do binómio qualidade da aproximação/tempo de
cálculo.
VOLTAR
DOMINGOS
M. CARDOSO, Departamento de Matemática, Universidade
de Aveiro
PROBLEMAS
COMBINATÓRIOS EM CONJUNTOS PARCIALMENTE ORDENADOS
RESUMO
Existem muitos problemas práticos que se podem modelar como
problemas de ordenação, para cuja resolução
se torna especialmente vantajosa a utilização de resultados
decorrentes da Teoria dos Conjuntos Parcialmente Ordenados.
Entre estes contam-se o disciplinamento de tarefas (que é
um modelo de optimização combinatória de aplicação
frequente), a identificação de subsequências
em sequências de informação experimental que
indiciam uma certa localização relativa no ADN (que
é um problema típico da moderna Biologia Molecular),
a detecção de sequências de mensagens com significado
relevante (que tem especial importância no processamento de
informações), etc.. Por exemplo, suponha-se que de
um grande número de experiências laboratoriais decorre
a conclusão que uma certa doença tem de ser combatida
com a administração de um determinado conjunto de
medicamentos. Suponha-se ainda que alguns destes medicamentos, quer
por razões de compatibilidade, quer por razões de
dosagem, não podem ser administrados antes que outros o sejam
e, por outro lado, que entre duas administrações consecutivas
de medicamentos com relações de precedência
deste tipo, deverão decorrer pelo menos 24 horas. Neste contexto
podem colocar-se as seguintes questões:
- Admitindo
que a um determinado conjunto de pacientes, devido ao
estado adiantado da sua doença, tem de ser imediatamente
aplicado o maior número possível de medicamentos compatíveis
(i.e., entre os quais não existe qualquer relação
de precedência),
como se determinam esses medicamentos?
- Tendo em
vista a cura completa dos restantes pacientes, qual ordem
segundo a qual todos os medicamentos devem ser administrados?
As relações
de ordem parcial e as suas representações algébricas
e combinatórias, proporcionam estruturas matemáticas
poderosas para a modelação e resolução
de muitos problemas de natureza combinatória, entre os quais
se incluem os anteriormente referidos. Nesta apresentação,
analisam-se os principais parâmetros associados a um conjunto
parcialmente ordenado (como sejam, o comprimento, a largura
e a dimensão), bem como as suas principais subrelações
e extensões, com particular destaque para as relações
de ordem intervalar, as semitransitivas, as semiordens,
as relações de ordem fracae as lineares.
Estudam-se as respectivas representações combinatórias
(por intermédio de grafos) e algébricas (com recurso
aos espaços vectoriais associados) e abordam-se algumas técnicas
para a determinação de extensões fracas e lineares,
exemplificando-se as suas aplicações. Finalmente referem-se
alguns problemas de investigação corrente relacionados
com conjuntos parcialmente ordenados.
VOLTAR
LUÍS
GOUVEIA, Departamento de Estatística e Investigação
Operacional, FCUL
ÁRVORES
COM RESTRIÇÕES DE DIÂMETRO: PROPRIEDADES E MODELOS
DE FLUXO EM REDES
RESUMO
Dado um grafo não orientado, pretende-se determinar uma árvore
de suporte de custo mínimo com a restrição
adicional de que o seu diâmetro não é superior
a um determinado natural D. Uma maneira intuitiva de garantir a
restrição adicional consiste em utilizar diretamente
a definição de diâmetro e impôr as seguintes
restrições: para qualquer par de nodos, o número
máximo de arestas no único caminho na árvore
que liga esses dois nodos é não superior a D. Tais
restrições levam a modelos em programação
linear inteira com um número exagerado de variáveis.
Com o objectivo de reduzir a dimensão de tais modelos, discutem-se
propriedades de árvores que representam soluções
admissíveis para o problema em estudo. Enquanto que é
relativamente fácil sugerir uma boa caracterização
de uma árvores com diâmetro D par, o mesmo já
não se passa relativamente ao caso em que D é impar.
Assim, grande parte desta comunicação dedica-se a
discutir diversas caracterizações de árvores
de suporte com diâmetro ímpar bem como diferentes de
maneira de escrever modelos de fluxo em redes sugeridos pelas diversas
caracterizações.
Trabalho conjunto com:
Thomas L. Magnanti (Sloan School of Management, MIT) e
Cristina Requejo (Departamento de Matemática,
Universidade de Aveiro).
VOLTAR
|
