Embed Size (px)
Citation preview
PAVF
c
1999 13
Introdu�c~ao �a PMO
� Conceitos b�asicos e exemplos
� Caracter��sticas e aplica�c~oes
PAVF
c
1999 14
Conceitos b�asicos e exemplos
Programa�c~ao multiobjetivo - PMO
Ramo da programa�c~ao matem�atica que se ocupa da ca-
racteriza�c~ao de solu�c~oes e do desenvolvimento de m�etodos
de otimiza�c~ao para problemas que envolvam mais de uma
fun�c~ao objetivo
Matematicamente ...
minimizar
x2
(f
1
(x); f
2
(x); : : : ; f
m
(x))
onde
f
1
; f
2
; : : : ; f
m
: fun�c~oes a minimizar (m � 2)
: conjunto das alternativas fact��veis
x = (x
1
; x
2
; : : : ; x
n
) : vari�aveis de decis~ao
Relevancia
� A solu�c~ao de qualquer problema de otimiza�c~ao mono-
objetivo depende da escolha do objetivo a minimizar
� Muitos problemas de otimiza�c~ao admitem diferentes
fun�c~oes objetivos, em geral con itantes
� Modelos multiobjetivos permitem considerar simulta-
neamente todos os poss��veis objetivos do problema
PAVF
c
1999 15
Conceitos b�asicos e exemplos
Exemplo - Dieta multiobjetivo
Dada um conjunto de n alimentos, determinar suas quan-
tidades x
i
; i = 1; 2; : : : ;m de forma a atender necessidades
di�arias de p nutrientes b
j
; j = 1; 2; : : : ; p que implique em
1) Custo m��nimo
2) Colesterol m��nimo
3) Carboidrato m��nimo
Modelo multiobjetivo:
minimizar
x
(c
1
x; c
2
x; c
3
x)
s.a a
11
x
1
+ a
12
x
2
+ � � �+ a
1n
x
n
� b
1
a
21
x
1
+ a
22
x
2
+ � � �+ a
2n
x
n
� b
2
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
x
1
+ a
m2
x
2
+ � � �+ a
mn
x
n
� b
p
x
i
� x
i
� x
i
; i = 1; 2; : : : ; n
onde
a
ij
: concentra�c~ao do nutriente i no alimento j
c
i
:=
h
c
i
1
c
i
2
� � � c
i
n
i
; i = 1; 2; 3
c
i
j
: custo unit�ario (i = 1), concentra�c~ao de colesterol
(i = 2) ou de carboidrato (i = 3) do alimento j
x
i
; x
i
: quantidade m��nima e m�axima do alimento i
PAVF
c
1999 16
Conceitos b�asicos e exemplos
Exemplo - Opera�c~ao de reservat�orios
Acima de uma s�erie de consumidores de �agua existe um
reservat�orio que pode ser utilizado para abastecimento e
dilui�c~ao de res��duos aumentando-se a vaz~ao liberada
PSfrag replacements
x
n+1
x
1
x
2
x
3
x
n
Ponto de controle
Reservat�orio
Pode-se �xar n��veis de tratamento para os consumidores
e regular a vaz~ao liberada pelo reservat�orio:
x
i
: n��vel de tratamento do consumidor i = 1; 2; : : : ; n
x
n+1
: quantidade de �agua liberada para diluir res��duos
Problema:
1) Minimizar o custo de tratamento da �agua
2) Maximizar a quantidade de �agua no reservat�orio
3) Minimizar a polui�c~ao no ponto de controle
PAVF
c
1999 17
Conceitos b�asicos e exemplos
Caracter��sticas essenciais
� Em geral, n~ao existem solu�c~oes �otimas, no sentido de
minimizarem individualmente todos os objetivos
� Exemplo: m��nimo custo n~ao implica m��nimo colesterol
PSfrag replacements
0
A
B
colesterol
custo
solu�c~ao 'ut�opica'
(c
1
x; c
2
x); x fact��vel
� Uma alternativa �e Pareto-�otima se o decr�escimo de um
objetivo implica no acr�escimo de algum outro
� A alternativa 'B' �e Pareto-�otima; 'A' �e dominada por
outras alternativas fact��veis
� Solu�c~ao do problema: alternativa Pareto-�otima - exis-
tem in�nitas - que satisfa�ca crit�erios adicionais (sub-
jetivos) de um decisor ('decision-maker' )
PAVF
c
1999 18
Caracter��sticas e aplica�c~oes
Quest~oes principais em PMO
� Desenvolver condi�c~oes necess�arias e/ou su�cientes que
caracterizem solu�c~oes Pareto-�otimas (e�cientes)
� Desenvolver m�etodos para resolu�c~ao de problemas que
modelem e viabilizem a interven�c~ao do decisor
Vantagens da PMO
� Aplic�avel a qualquer �area na qual decis~oes sejam to-
madas a partir de modelos de otimiza�c~ao
� M�etodos multiobjetivos s~ao implementados a partir de
m�etodos mono-objetivos existentes
Aplica�c~oes da PMO
� Gest~ao da atividade economica
� Planejamento da produ�c~ao
� Administra�c~ao p�ublica
� Planejamento de transportes e tr�afego
� Gest~ao de recursos h��dricos
� Projeto de sistemas (controladores)
