Date post: | 09-Jan-2016 |
Category: |
Documents |
Upload: | amanda-ortega |
View: | 221 times |
Download: | 0 times |
of 31
PAVF
c
1999 105
Metodos com indicac~ao a-priori
Classicac~ao dos metodos a-priori
Metodos com informac~oes cardinais
{ Metodos baseados em func~oes utilidades
{ Metodos baseados em limitantes
Metodos com informac~oes cardinais/ordinais
{ Metodos lexicogracos
{ Programac~ao por metas
PAVF
c
1999 106
Classicac~ao dos metodos a-priori
Caractersticas
Informac~oes sobre prefere^ncias s~ao passadas ao analis-
ta antes (a-priori) da soluc~ao de problema
O decisor fornece as informac~oes durante ou apos a
modelagem matematica do problema
O decisor aceita a soluc~ao encontrada pelo analista
Tipos de informac~oes
Cardinal :
As prefere^ncias do decisor s~ao baseadas em informac~oes
numericas:
Trade-o implcito :
O decisor indica nveis (valores) desejaveis para os
objetivos
Trade-o explcito :
O decisor indica relac~oes (trade-os) desejaveis
entre os objetivos
Ordinal e/ou cardinal :
As prefere^ncias do decisor s~ao baseadas em informac~oes
de ordem (prioridade), podendo estarem combinadas
com informac~oes cardinais
PAVF
c
1999 107
Metodos baseados em func~oes utilidades
Estruturac~ao de prefere^ncias
Sejam y
1
; y
2
2 R
m
. Ent~ao y
1
e y
2
s~ao comparaveis
pelo decisor se e somente se apenas uma das sentencas e
verdadeira:
a) y
1
y
2
: o decisor e indiferente entre y
1
e y
2
b) y
1
y
2
: o decisor e prefere y
1
a y
2
c) y
1
y
2
: o decisor e prefere y
2
a y
1
pode-se estruturar prefere^ncias do decisor atraves de
curvas de indifere^nca ou isoprefere^ncia
a soluc~ao do problema pode ser caracterizada como:
determinar y
2 Y tal que
y
y; 8 y 2 Y
PSfrag replacements
Y
0 y
1
y
2
y
1
y
2
y
3
y
y
1
y
2
y
3
y
curvas de indifere^nca
PAVF
c
1999 108
Metodos baseados em func~oes utilidades
Denic~ao - Func~ao utilidade
Uma func~ao u, que associa um real u(y) a cada y 2 R
m
,
e chamada de func~ao utilidade se
a) y
1
y
2
, u(y
1
) = u(y
2
)
b) y
1
y
2
, u(y
1
) u(y
2
)
as curvas de indifere^nca do decisor podem ser vistas
como curvas de nvel da sua func~ao utilidade
existem tecnicas apropriadas para levantar u a partir
de informac~oes numericas (cardinais)
hipotese simplicadoras facilitam a obtenc~ao de u's
Denic~ao - Independe^ncia prefere^ncial
u e preferencialmente independente se o grau de utilida-
de de um objetivo independe dos valores assumidos pelos
demais
Viabiliza formas especiais para u
{ Aditiva: u(y) =
m
X
i=1
u
i
(y
i
)
{ Linear: u(y) =
m
X
i=1
w
i
y
i
, w
i
0; i = 1; 2; : : : ;m
PAVF
c
1999 109
Metodos baseados em func~oes utilidades
Crtica a u's lineares
PSfrag replacements
Y
2
Y
1
0 y
1
y
2
y
1
1
y
2
1
y
1
2
y
2
2
Suponha que iguais ponderac~oes (w
1
= w
2
) tenham sido
atribudas aos objetivos
Se o espaco dos objetivos assume a forma Y
1
, o ponto
y
1
= (y
1
1
; y
1
2
) reete o julgamento a-priori do decisor
Se o espaco dos objetivos assume a forma Y
2
, o ponto
y
2
= (y
2
1
; y
2
2
) n~ao reete o julgamento a-priori
Ponderac~oes n~ao reetem importa^ncia no sentido pro-
porcional
PAVF
c
1999 110
Metodos baseados em func~oes utilidades
Vantagens
Quando e possvel obter u, o problema se reduz a re-
solver
minimizar
x2
u(f(x))
Mesmo quando n~ao e possvel obter u explicitamente,
mas o problema e convexo, obter
x
= arg min
x2
u(f(x))
e equivalente a determinar w
2W tal que
x
= arg min
x2
< w
; f(x) >
Muitos metodos exploram esta propriedade, adaptan-
do interativamente os valores dos w
i
's; no caso da
situac~ao 'Y
2
', um procedimento seria
'aumentar w
2
; diminuir w
1
'
PAVF
c
1999 111
Metodos baseados em func~oes utilidades
Propriedades globais de u
Algumas propriedades globais s~ao uteis na determinac~ao
de u:
N~ao-decrescimento: para quaiquer y
1
; y
2
tais que y
1
y
2
, obtem-se u(y
1
) u(y
2
);
Diferenciabilidade: u e diferenciavel; se u e n~ao-decrescente
e diferenciavel, ent~ao du=dy 0
Convexidade: u e convexa
Se u e diferenciavel sobre , ent~ao existe
r
x
u(f(x)) =
"
df
dx
#
T
du
df
e a unica quantidade desconhecida e du=df
Se x
0
2 n~ao e a soluc~ao do problema (r
x
u(f(x
0
)) 6=
0) e u e n~ao-decrescente e diferenciavel, ent~ao para pelo
menos um k
@u
@f
0
k
> 0
PAVF
c
1999 112
Metodos baseados em func~oes utilidades
Plano tangente
O plano tangente a uma curva de indifere^nca num ponto
y = y
0
e
M(y
0
) := fz :
"
du
dy
0
#
T
z = 0g
PSfrag replacements
0 y
1
y
2
y
1
y
2
y
0
1
y
0
2
y
0
y
du
dy
0
u cte
M(y
0
)
Da equac~ao do plano tangente,
"
du
dy
0
#
T
z =
"
du
dy
0
#
T
(y y
0
) =
m
X
i=1
@u
@y
0
i
(y
i
y
0
i
) = 0
Dividindo pela quantidade de refere^ncia @u=@y
0
1
> 0,
0
1
+
0
2
0
2
+ +
0
m
0
m
= 0
0
i
:= y
i
y
0
i
;
0
i
:=
@u=@y
0
i
@u=@y
0
1
PAVF
c
1999 113
Metodos baseados em func~oes utilidades
Se o decisor e indiferente as variac~oes
0
1
e
0
i
nos ob-
jetivos i e 1, mantidos os demais constantes
0
i
=
0
1
0
i
; i = 2; 3; : : : ;m
0
i
; i = 2; 3; : : : ;m s~ao as taxas marginais de substituic~ao
do decisor no ponto y = y
0
A partir de
0
i
; i = 2; 3; : : : ;m, a direc~ao do gradiente
de u em y = y
0
e aproximada por
du
dy
0
=
@u
@y
0
1
=
2
6
6
6
6
6
6
4
1
0
2
.
.
.
0
m
3
7
7
7
7
7
7
5
Obtenc~ao dos
0
i
's: num ponto y = y
0
, xa-se
0
1
> 0
como refere^ncia; para cada i, o decisor informa
0
i
> 0 tal
que
(y
0
1
; : : : ; y
0
i
; : : : ; y
0
m
) (y
0
1
0
1
; : : : ; y
0
i
+
0
i
; : : : ; y
0
m
)
mantidos os demais objetivos constantes. Calcula-se ent~ao
0
i
=
0
1
=
0
i
; i = 2; 3; : : : ;m
PAVF
c
1999 114
Metodos baseados em func~oes utilidades
Teoricamente e possvel obter x
e
0 satisfazendo
as KTC do problema de minimizac~ao de u sobre :
"
df
dx
#
T
du
df
+
p
X
i=1
j
g
j
(x
) = 0
g
j
(x
) 0;
j
g
j
(x
) = 0; j = 1; 2; : : : ; p
Alguns metodos (interativos, Cap. 5) seguem esta linha
Teorema
Sejam f
1
; f
2
; : : : ; f
m
func~oes convexas sobre convexo
e u uma func~ao convexa n~ao-decrescente sobre um conjun-
to convexo C Y . Ent~ao u e convexa sobre
Prova: Para quaisquer x
1
; x
2
2 e qualquer 2 [0; 1],
u[f(x
1
+ (1 )x
2
)] u[f(x
1
) + (1 )f(x
2
)]
u[f(x
1
)] + (1 )u[f(x
2
)]
A primeira desigualdade deriva da convexidade das f 's e
do n~ao-decrescimento de u. A segunda, da convexidade de
u sobre C 2
PAVF
c
1999 115
Metodos baseados em func~oes utilidades
Exemplo: Seja u(f(x)) := max
1im
ff
i
(x)g
PSfrag replacements
x
f
1
f
2
e ()
u
Teorema
Seja u uma func~ao n~ao-decrescente sobre Y . Ent~ao pelo
menos uma soluc~ao de
P
u
: minimizar
x2
u(f(x))
e eciente.
Prova: Suponha x
uma soluc~ao otima do P
u
e x
0
uma
soluc~ao otima do problema auxiliar
minimizar
x2
m
X
i=1
f
i
(x)
s.a f
j
(x) f
j
(x
); j = 1; 2; : : : ;m
PAVF
c
1999 116
Metodos baseados em limitantes
Prova (cont): Ent~ao x
0
2 e () pois, caso contrario, a
otimalidade de x
0
seria falseada. Como f(x
0
) f(x
), a
soluc~ao factvel x
0
tambem resolve P
u
pois
u(f(x
0
)) u(f(x
))
dado que u e n~ao-decrescente 2
Metodos baseados em limitantes
requerem que o decisor, 1) selecione um objetivo de
refere^ncia i, e 2) forneca nveis f
j
's e f
j
's aceitaveis
para os objetivos restantes. Em seguida resolve-se
minimizar
x2
f
i
(x)
s.a f
j
f
j
(x) f
j
; 8 j 6= i
desvantagens: especicar a-priori f
j
's e f
j
's que, 1)
tornem o problema factvel, e 2) tornem uma soluc~ao
do problema satisfatoria para o decisor
normalmente usados em conjunto com outros metodos
multiobjetivos
PAVF
c
1999 117
Metodos lexicogracos
Fomulac~ao classica
Assumem que o decisor possui uma hierarquia para
os objetivos: os objetivos podem ser priorizados numa
lista ordenada, por exemplo, P := ff
1
; f
2
; : : : ; f
m
g
Minimiza-se a primeira func~ao da lista P sujeito a
1
:= :
minimizar
x2
1
f
1
(x)
Seja
2
:= fx : f
1
(x) = min
x2
f
1
(x)g. Para i =
2; 3; : : : ;m resolve-se sequencialmente
minimizar
x2
i
f
i
(x)
Este tipo de minimizac~ao e representada como
minlex
x2
P
onde 'minlex' signica 'minimizac~ao lexicograca' da
lista P
Apenas informac~ao ordinal e utilizada
A soluc~ao nal e muito sensvel a ordenac~ao
PAVF
c
1999 118
Metodos lexicogracos
Exemplo:
PSfrag replacements
x
f
1
f
2
x
1
x
2
x
3
Na situac~ao da gura, se P := ff
1
; f
2
g, ent~ao
1
=
fx : x
1
x x
2
g,
2
= fx
2
g e x
= x
2
Se P := ff
2
; f
1
g, ent~ao
1
=
2
= fx
3
g e x
= x
3
Variante do metodo lexicograco
A i-esima minimizac~ao na lista P e denida como
minimizar
x2
f
i
(x)
s.a f
j
(x) (1 +
j
)f
j
; j = 1; 2; : : : ; i 1
onde os f
j
's s~ao os valores otimos ate ordem i 1 e os
j
's (
j
0; 8 j) s~ao tolera^ncias em relac~ao aos f
j
's
PAVF
c
1999 119
Metodos lexicogracos
Exemplo:
PSfrag replacements
x
f
1
f
2
f
1
(1 + )f
1
x
1
x
2
x
3
x
4
Se P := ff
1
; f
2
g, ent~ao a variante do metodo lexico-
graco fornece x
= x
4
, que do ponto de vista de f
2
e melhor que x
2
Observac~oes
A racionalidade do metodo lexicograco baseia-se no
fato de que os individuos tendem a priorizar decis~oes
A soluc~ao pelo metodo lexicograco e sensvel a orde-
nac~ao
A aplicac~ao do metodo quando dois ou mais objetivos
possuem aproximadamente a mesma prioridade pode
levar a soluc~oes insatisfatorias
A variante do metodo lexicograco busca reduzir sen-
sibilidade a ordenac~ao
PAVF
c
1999 120
Programac~ao por metas
Caractersticas
Utilizac~ao coordenada de informac~oes ordinais e car-
dinais (metas)
O decisor fornece metas para os objetivos e prioriza
minimizac~oes de desvios em relac~ao as metas
Soluc~oes ecientes para problemas multiobjetivos li-
neares atraves de metodos do tipo simplex
Formulac~ao classica
minimizar
x;d
+
;d
0
@
m
X
i=1
(d
+
i
+ d
i
)
p
1
A
1=p
; p 1
s.a f
i
(x) d
+
i
+ d
i
= t
i
; i = 1; 2; : : : ;m
d
+
i
0; d
i
0; d
+
i
d
i
= 0; i = 1; 2; : : : ;m
x 2
t
i
: meta (goal, target) para o objetivo i estipulada
pelo decisor
d
+
i
> 0 : indica que o objetivo i cou acima de t
i
na quan-
tidade d
+
i
d
i
> 0 : indica que o objetivo i cou abaixo de t
i
na quan-
tidade d
i
PAVF
c
1999 121
Programac~ao por metas
Interpretac~ao
PSfrag replacements
f
i
f
i
f
i
(d
+
i
= d
i
= 0)t
i
d
+
i
d
i
Na formulac~ao classica, minimiza-se alguma (p) dista^ncia
de d
+
+ d
a origem
Assume que os desvios em relac~ao as metas s~ao igual-
mente importantes
Se o decisor for capaz de priorizar desvios, obtem-se a
formulac~ao alternativa
minlex
x;d
+
;d
f
1
(d
+
; d
);
2
(d
+
; d
); : : : ;
k
(d
+
; d
)g
s.a f
i
(x) d
+
i
+ d
i
= t
i
; i = 1; 2; : : : ;m
d
+
i
0; d
i
0; d
+
i
d
i
= 0; i = 1; 2; : : : ;m
x 2
onde
1
;
2
; : : : ;
k
s~ao func~oes dos desvios d
+
; d
PAVF
c
1999 122
Programac~ao por metas
Problemas lineares
Assuma que f
1
; f
2
; : : : ; f
m
s~ao func~oes lineares sobre o
poliedro
:= fx 2 R
n
: Ax = b; x 0g
onde A 2 R
pn
e b 2 R
p
s~ao matrizes dadas. Note que
f(x) =
2
6
6
6
6
6
6
4
f
1
(x)
f
2
(x)
.
.
.
f
m
(x)
3
7
7
7
7
7
7
5
= Cx; C 2 R
mn
e cada linha de C representa um objetivo
Assuma que
1
;
2
; : : : ;
m
s~ao func~oes lineares de d
+
; d
.
O modelo linear de programac~ao por metas seria
minlex
x;d
+
;d
f
1
(d
+
; d
);
2
(d
+
; d
); : : : ;
k
(d
+
; d
)g
s.a
n
X
j=1
a
ij
x
j
+
i
+
i
= b
i
; i = 1; 2; : : : ; p
n
X
j=1
c
ij
x
j
d
+
i
+ d
i
= t
i
; i = 1; 2; : : : ;m
+
i
0;
i
0;
+
i
i
= 0; i = 1; 2; : : : ; p
d
+
i
0; d
i
0; d
+
i
d
i
= 0; i = 1; 2; : : : ;m
x 0
PAVF
c
1999 123
Programac~ao por metas
Objetivos e restric~oes s~ao tratadas atraves do mesmo
formalismo
A minimizac~ao dos desvios
+
;
e sempre prioritaria
em relac~ao aos demais
Exemplo
Considere o problema
maximizar
x
f(x) = 0:4x
1
+ 0:3x
2
s.a g
1
(x) = x
1
+ x
2
400
g
2
(x) = 2x
1
+ x
2
500
x
1
0; x
2
0
Modelo de programac~ao por metas
minlex f(
+
1
+
+
2
); d
1
g
s.a x
1
+ x
2
+
1
+
1
= 400
2x
1
+ x
2
+
2
+
2
= 500
0:4x
1
+ 0:3x
2
+ d
1
d
+
1
= 240
+
i
0;
i
0;
+
i
i
= 0; i = 1; 2
d
+
1
0; d
1
0; d
+
1
d
1
= 0
x
1
0; x
2
0
PAVF
c
1999 124
Programac~ao por metas
PSfrag replacements
0
250
400
400 600
500
800
P
x
1
x
2
+
1
1
+
2
2
d
+
1
d
1
d
1
= 110
A minimizac~ao de
1
:=
+
1
+
+
2
fornece a regi~ao onde
+
1
=
+
2
= 0 e
1
= 0. Em seguida, resolve-se
minimizar d
1
s.a x
1
+ x
2
+
1
+
1
= 400
2x
1
+ x
2
+
2
+
2
= 500
0:4x
1
+ 0:3x
2
+ d
1
d
+
1
= 240
+
i
0;
i
0;
+
i
i
= 0; i = 1; 2
d
+
1
0; d
1
0; d
+
1
d
1
= 0
x
1
0; x
2
0
1
(
+
1
;
+
2
) =
1
PAVF
c
1999 125
Programac~ao por metas
Exemplo (cont.)
A soluc~ao e encontrada no ponto P= (100; 300), onde
+
1
=
+
2
= 0 garante
1
=
1
= 0, e
2
= d
1
= 110
Considere o problema alternativo
minlex f(
+
1
+
+
2
); d
2
; d
1
g
s.a x
1
+ x
2
+
1
+
1
= 400
2x
1
+ x
2
+
2
+
2
= 500
0:4x
1
+ 0:3x
2
+ d
1
d
+
1
= 240
x
1
+ d
+
2
d
2
= 300
PSfrag replacements
0
d
2
= 50
250 300 400
400
600
500
800
P
x
1
x
2
+
1
1
+
2
2
d
+
1
d
1
d
+
2
d
2
d
1
= 140
Soluc~ao: x
1
= 250; x
2
= 0;
+
1
=
+
2
= 0; d
1
=
140; d
2
= 50
PAVF
c
1999 126
Programac~ao por metas
Propriedades
Factibilidade: restric~oes s~ao tratadas como metas prio-
ritarias, podendo ou n~ao ser atendidas; os modelos de
programac~ao por metas s~ao sempre factveis
Implementabilidade: sempre que um desvio associado
a uma meta prioritaria for positivo, a soluc~ao obtida
n~ao e implementavel
Soluc~oes limitadas: a soluc~ao de um problema de pro-
gramac~ao por metas e sempre limitada
Implementac~ao atraves do metodo Simplex
minimiza-se
1
atraves do Simplex; eventualmente ocor-
rem soluc~oes multiplas
as multiplas soluc~oes de
1
est~ao expressas no tableau
otimo obtido
os custos relativos de
2
s~ao representados na base
otima obtida
minimiza-se
2
de forma a n~ao degradar o valor otimo
de
1
minimiza-se cada func~ao de forma a n~ao degradar os
valores obtidos nos passos anteriores ate que a lista de
desvios se esgote
PAVF
c
1999 127
Programac~ao por metas
Seja d := (d
+
; d
); d 2 R
q
e
S :=
2
4
A D
1
C D
2
3
5
; S 2 R
rv
onde D
1
2 R
pq
e D
2
2 R
mq
s~ao matrizes de 0's, 1's e
-1's relativas aos desvios; r := p+m, v := n+ q. O vetor
global de metas e
g :=
2
4
b
t
3
5
; t 2 R
r
Assuma que o modelo linear de programac~ao por metas
possui a seguinte forma cano^nica:
x
1
x
p
x
p+1
x
n
d
1
d
q
1 0 s
1;p+1
s
1;n
s
1;n+1
s
1;v
g
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 1 s
r;p+1
s
r;n
s
r;n+1
s
r;v
g
r
0 0
h
1;p+1
h
1;n
h
1;n+1
h
1;v
z
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0
h
k;p+1
h
k;n
h
k;n+1
h
k;v
z
k
Cada variavel possui associada uma coluna de custos re-
lativos (coluna nula se a variavel e basica)
PAVF
c
1999 128
Programac~ao por metas
Relativamente a base correspondente,
s
ij
: representac~ao de s
ij
(S := fs
ij
g)
g
i
: representac~ao de g
i
(goal)
h
ij
: custo relativo de
i
, variavel j
z
i
: valor de
i
O seguinte algoritmo e utilizado para obter o mnimo
lexicograco de f
1
;
2
; : : : ;
k
g:
1: Encontre uma soluc~ao basica factvel inicial; obtenha
os custos relativos de
1
;
2
; : : : ;
k
; faca l = 1
2: Se os custos de
l
forem n~ao-negativos, va para o passo
5. Sen~ao, va para o passo 3
3: Se nas colunas de custos relativos, todos os custos
negativos de
l
forem precedidos por pelo menos um
custo positivo de
i
; i = 1; 2; : : : ; l 1, va para o
passo 5. Caso contrario, va para o passo 4
4: Escolha uma variavel com custo negativo para entrar
na base; faca a atualizac~ao da base; repita o processo
enquanto houver custos negativos n~ao precedidos por
custos positivos; va para o passo 5
5: O valor de
l
n~ao pode continuar a ser reduzido: faca
l = l + 1. Se l > k pare; sen~ao, volte ao passo 2
PAVF
c
1999 129
Programac~ao por metas
Exemplo
minlex f(
+
1
+
+
2
); d
2
; d
1
g
s.a x
1
+ x
2
+
1
+
1
= 400
2x
1
+ x
2
+
2
+
2
= 500
0:4x
1
+ 0:3x
2
+ d
1
d
+
1
= 240
x
1
+ d
+
2
d
2
= 300
1
e minimizada na base inicial
x
1
x
2
+
1
+
2
d
+
1
d
+
2
1
2
d
1
d
2
b
1 1 -1 0 0 0 1 0 0 0 400
2 1 0 -1 0 0 0 1 0 0 500
0.4 0.3 0 0 -1 0 0 0 1 0 240
1 0 0 0 0 -1 0 0 0 1 300
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0
representac~ao de
2
;
3
na base otima de
1
x
1
x
2
+
1
+
2
d
+
1
d
+
2
1
2
d
1
d
2
b
1 1 -1 0 0 0 1 0 0 0 400
2 1 0 -1 0 0 0 1 0 0 500
0.4 0.3 0 0 -1 0 0 0 1 0 240
1 0 0 0 0 -1 0 0 0 1 300
0 0 1 1 0 0 0 0 0 0 0
-1 0 0 0 0 1 0 0 0 0 -300
-0.4 -0.3 0 0 1 0 0 0 0 0 -240
PAVF
c
1999 130
Programac~ao por metas
Exemplo (cont.)
Soluc~ao basica inicial, otima para
1
:
1
= 400;
2
= 500; d
1
= 240; d
2
= 300
+
1
=
+
2
= d
+
1
= d
+
2
= 0 (
1
= d
+
1
+ d
+
2
= 0)
x
1
= x
2
= 0
Na base corrente,
2
possui um custo relativo negativo;
se x
1
entrar na base, melhora o valor de
2
; a variavel
2
deve deixar a base
A mudanca de base n~ao altera o valor otimo de
1
x
1
x
2
+
1
+
2
d
+
1
d
+
2
1
2
d
1
d
2
b
0 0.5 -1 0.5 0 0 1 -0.5 0 0 150
1 0.5 0 -0.5 0 0 0 0.5 0 0 250
0 0.1 0 0.2 -1 0 0 -0.2 1 0 140
0 -0.5 0 0.5 0 -1 0 -0.5 0 1 50
0 0 1 1 0 0 0 0 0 0 0
0 0.5 0 -0.5 0 1 0 0.5 0 0 -50
0 -0.1 0 0 1 0 0 0.2 0 0 -140
N~ao e possvel melhorar
2
sem degradar
1
; n~ao e
possvel melhorar
3
sem degradar
2
; a base corrente e
o mnimo lexicograco:
1
= 150;
2
= 0; d
1
= 140; d
2
= 50
+
1
=
+
2
= d
+
1
= d
+
2
= 0
x
1
= 250; x
2
= 0
PAVF
c
1999 131
Programac~ao por metas
Exemplo - Zeleny (1982)
minlex fd
1
; (d
+
2
+ d
2
); d
3
g
s.a 4x
1
+ 3:2x
2
d
+
1
+ d
1
= 12
x
1
1:5x
2
d
+
2
+ d
2
= 0
2x
1
+ 4x
2
+ d
3
= 12
3x
1
+ 3x
2
+ d
4
= 12
Tableau inicial
x
1
x
2
d
+
1
d
+
2
d
1
d
2
d
3
d
4
b
4 3.2 -1 0 1 0 0 0 12
1 -1.5 0 -1 0 1 0 0 0
2 4 0 0 0 0 1 0 12
3 3 0 0 0 0 0 1 12
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 0
Forma cano^nica
x
1
x
2
d
+
1
d
+
2
d
1
d
2
d
3
d
4
b
4 3.2 -1 0 1 0 0 0 12
1 -1.5 0 -1 0 1 0 0 0
2 4 0 0 0 0 1 0 12
3 3 0 0 0 0 0 1 12
-4 -3.2 1 0 0 0 0 0 -12
-1 1.5 0 2 0 0 0 0 0
-2 -4 0 0 0 0 0 0 -12
PAVF
c
1999 132
Programac~ao por metas
Exemplo (cont.)
A func~ao
1
n~ao atingiu o valor otimo
Escolhe-se x
1
para entrar na base; d
2
deixa a base; apos
pivoteamento, obtem-se o novo tableau
x
1
x
2
d
+
1
d
+
2
d
1
d
2
d
3
d
4
b
0 9.2 -1 4 1 -4 0 0 12
1 -1.5 0 -1 0 1 0 0 0
0 7 0 2 0 -2 1 0 12
0 7.5 0 3 0 -3 0 1 12
0 -9.2 1 -4 0 4 0 0 -12
0 0 0 1 0 1 0 0 0
0 -7 0 -2 0 2 0 0 -12
1
ainda pode ser melhorada; x
2
entra e d
1
sai da base
x
1
x
2
d
+
1
d
+
2
d
1
d
2
d
3
d
4
b
0 1 -0.11 0.43 0.11 -0.42 0 0 1.3
1 0 -0.16 -0.35 0.16 0.35 0 0 1.9
0 0 0.77 -1 -0.77 1 1 0 2.9
0 0 0.82 0.22 -0.82 0.22 0 1 2.2
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 -0.77 1 0.77 -1 0 0 -2.9
1
e
2
atingem seus valores otimos;
3
pode ser melho-
rada com d
+
1
na base (sai d
4
)
PAVF
c
1999 133
Programac~ao por metas
Exemplo (cont.)
Tableau nal
x
1
x
2
d
+
1
d
+
2
d
1
d
2
d
3
d
4
b
0 1 0 0.4 0 -0.4 0 0.1 1.6
1 0 0 -0.4 0 0.4 0 0.2 2.4
0 0 0 -0.8 0 0.8 1 -0.9 0.8
0 0 1 -0.3 -1 0.3 0 1.2 2.7
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 0 0.8 0 -0.8 0 0.9 -0.8
N~ao e possvel melhorar
3
sem degradar
2
; a base
corrente e o mnimo lexicograco do problema
x
1
= 2:4; x
2
= 1:6; d
+
1
= 2:7; d
3
= 0:8
d
+
2
= d
1
= d
2
= d
4
= 0
1
= d
1
= 0;
2
= d
+
2
+ d
2
= 0;
2
= d
3
= 0:8
Ecie^ncia
Soluc~oes de problemas de programac~ao por metas n~ao
s~ao necessariamente ecientes
Soluc~oes ecientes s~ao geralmente obtidas quando as
metas n~ao s~ao atingidas
PAVF
c
1999 134
Programac~ao por metas
Variante
Um metodo popular baseado nos mesmos princpios e
conhecido como metodo da realizac~ao das metas
Formulac~ao do problema
minimizar
s.a f
i
(x) w
i
t
i
; i = 1; 2; : : : ;m
x 2 ; 2 R
t
i
: meta para o objetivo i
w
i
0 : ponderac~ao para o desvio do objetivo i; assume-
se w 2W
Interpretac~ao
PSfrag replacements
0
y
1
y
2
w
t
t
1
t
2
f
1
f
2
t+ w
Y
PAVF
c
1999 135
Programac~ao por metas
Propriedades
A variac~ao de w sobre W pode dar origem a e (),
mesmo que o problema n~ao seja convexo
Quanto menor w
i
, maior a importa^ncia atribuda a
meta t
i
O problema pode ser reformulado como (w > 0)
minimizar
s.a (1=w
i
)(f
i
(x) t
i
); i = 1; 2; ::;m
x 2 ; 2 R
ou ainda
minimizar
x2
max
i
f
i
(f
i
(x) t
i
)g
onde
i
:= 1=w
i
Minimiza-se a norma innito ponderada entre o ponto
t = (t
1
; t
2
; : : : ; t
m
) e o conjunto de soluc~oes factveis
O resultado e uma soluc~ao eciente (em geral) que
reete os valores relativos entre w
1
; w
2
; : : : ; w
m