Cap4 Notas Aulas Valente

PAVF

c

1999 72

M�etodos com indica�c~ao a-posteriori

� Caracter��sticas dos m�etodos a-posteriori

� M�etodo das pondera�c~oes

� M�etodo das �-restri�c~oes

� Programa�c~ao linear multiobjetivo

PAVF

c

1999 73

M�etodo das pondera�c~oes

Caracter��sticas dos m�etodos a-posteriori

� Buscam gerar e� (), ou um subconjunto representa-

tivo de e� (), para posterior escolha de uma solu�c~ao

de compromisso

� Quase sempre incorporados a outros m�etodos (a-priori,

interativos) como ferramentas de gera�c~ao e an�alise de

alternativas


Se f

1

; f

2

; : : : ; f

m

s~ao convexas sobre , e� () pode ser

gerado resolvendo-se

P

w

: minimizar

x2

< w; f(x) >

varrendo-se o vetor w em W := fw : w � 0;

m

X

i=1

w

i

= 1g

� Na pr�atica, a gera�c~ao de e� () por P

w

(ou qualquer

outro m�etodo) �e invi�avel

� Gera�c~ao de subconjuntos de e� () caracterizados por

informa�c~oes (preferencias) contidas em w 2W �e usual

� Certas propriedades de P

w

s~ao �uteis ao desenvolvimen-

to de v�arios m�etodos multiobjetivos

PAVF

c

1999 74


Problemas convexos

Considere o problema

P

w

: minimizar

x2

w

T

f(x)

com w 2W . De�na

(w) := fx : x resolve P

w

g

e

f [(w)] := fy : y = f(x); x 2 (w)g

Teorema

Se f

1

; f

2

; : : : ; f

m

s~ao fun�c~oes convexas sobre convexo,

ent~ao para cada w 2 W; w > 0, f [(w)] �e um conjunto

convexo contido num mesmo hiperplano do R

m

Prova: O valor �otimo de P

w

; w 2 W , pode ser represen-

tado como

v(w) := w

T

f(x); 8x 2 (w)

PAVF

c

1999 75


Prova (cont.) No espa�co dos objetivos,

w

T

y = v(w); 8 y 2 f [(w)]

e qquer ponto de f [(w)] tamb�em pertence ao hiperplano

H := fy : w

T

y = v(w)g

ou seja, f [(w)] � H. Para mostrar que f [(w)] �e con-

vexo, sejam y

1

= f(x

1

); y

2

= f(x

2

) com x

1

; x

2

2 (w).

Como (w) �e convexo, para � 2 [0; 1],

v(w) = w

T

f(�x

1

+ (1� �)x

2

)

� w

T

[�f(x

1

) + (1� �)f(x

2

)]

� �[w

T

f(x

1

)] + (1� �)[w

T

f(x

2

)]

� �v(w) + (1� �)v(w) = v(w)

Como w > 0, para todo � 2 [0; 1],

�f(x

1

) + (1� �)f(x

2

) = f(�x

1

+ (1� �)x

2

)

ou seja, �y

1

+ ��y

2

2 f [(w)] 2

PAVF

c

1999 76

M�etodo das podera�c~oes

Problemas lineares

Se f

1

; f

2

; : : : ; f

m

s~ao lineares e �e um poliedro, e� ()

pode ser gerado por programa�c~ao linear param�etrica

� Resultados especiais para problemas bi-objetivos

P

w

: minimizar

x2

wf

1

(x) + (1� w)f

2

(x)

onde w 2 [0; 1]. De�na

x(w) := argmin

x2

wf

1

(x) + (1� w)f

2

(x)

� x(w) �e constante por partes:

x(w) = x

i

; w

i

� w � w

i+1

; i = 0; 1; : : : ; d

PSfrag replacements

x

i�1

x

i

x

i+1

w

i�1

w

i

w

i+1

0 = w

0

< w

1

< � � � < w

d

< w

d+1

= 1

PAVF

c

1999 77

M�etodo das �-restri�c~oes

� M�etodo mais geral para obten�c~ao de solu�c~oes e�cien-

tes (problemas n~ao-convexos)

� Multiplicadores de Kuhn-Tucker associados �as �-restri-

�c~oes interpretados como trade-o�s entre objetivos

Seja

P

k

(�) : minimizar

x2

f

k

(x)

s.a f

j

(x) � �

j

; 8 j 6= k

De�ne-se

k

(�) := fx 2 : f

j

(x) � �

j

; 8 j 6= kg e

E

k

:= f� :

k

(�) 6= ;g

Teorema

Sejam �

0

2 E

k

, x

0

uma solu�c~ao de P

k

(�

0

) e �

0

kj

os mul-

tiplicadores de Kuhn-Tucker de f

j

(x) � �

0

j

; 8 j 6= k. Se

a) x

0

�e um ponto regular de P

k

(�

0

)

b) x

0

satisfaz as condi�c~oes su�cientes de 2a. ordem

c) n~ao existem restri�c~oes degeneradas em x

0

ent~ao existe x(�) cont��nua em � tal que x(�

0

) = x

0

e

�

0

kj

= �

@f

k

@�

0

j

PAVF

c

1999 78


Considere

:= fx : g

i

(x) � 0; i = 1; 2; : : : ; pg

Fun�c~ao lagrangeana:

l(x; �; �) := f

k

(x) +

p

X

i=1

�

i

g

i

(x) +

X

j 6=k

�

kj

(f

j

(x)� �

0

j

)

Condi�c~oes de Kuhn-Tucker: se x

0

�e um m��nimo local de

f

k

sobre

k

(�

0

), existem multiplicadores �

0

i

� 0; i =

1; 2; : : : ; p e �

0

kj

� 0; 8 j 6= k tais que

a) g

i

(x

0

) � 0; i = 1; 2; : : : ; p

f

j

(x

0

) � �

0

j

; 8 j 6= k

b) �

0

i

g

i

(x

0

) = 0; i = 1; 2; : : : ; p

�

0

kj

(f

j

(x

0

)� �

0

j

) = 0; 8 j 6= k

c) rf

k

(x

0

) +

p

X

i=1

�

0

i

rg

i

(x) +

X

j 6=k

�

0

kj

rf

j

(x) = 0

Se f

j

(x

0

) � e

0

j

= 0, ent~ao �

0

kj

> 0 (n~ao-degenerescencia)

e como �

0

j

= f

j

(x

0

), obt�em-se (f

0

:= f(x

0

))

�

0

kj

= �

@f

k

@f

0

j

e �

0

kj

indica quanto f

k

(referencia) pode diminuir se f

j

aumentar em rela�c~ao a f

0

(trade-o�)

PAVF

c

1999 79


Observa�c~oes

� Condi�c~oes su�cientes permitem veri�car se �

0

gera uma

solu�c~ao e�ciente: x

0

2 e� () se

a) x

0

�e a solu�c~ao �unica de P

k

(�

0

)

b) x

0

resolve P

k

(�

0

) para k = 1; 2; : : : ;m

� Alguns m�etodos multiobjetivos baseiam-se em

1) Gerar solu�c~oes e�cientes obtendo os multiplicado-

res �

kj

associados

2) Determinar uma solu�c~ao e�ciente cujos multipli-

cadores casem com os trade-o�s do decisor

� As t�ecnicas de gera�c~ao atrav�es de P

w

e P

k

(�) s~ao ba-

seadas em escalariza�c~ao do problema multiobjetivo

� Se o problema multiobjetivo �e linear, pode-se gerar

e� () sem o uso direto de escalariza�c~ao

PAVF

c

1999 80

Programa�c~ao linear multiobjetivo

Problemas multiobjetivos lineares

minimizar

x2

f(x)

onde f

i

(x) = c

i

x; c

i

2 R

1�n

e

f(x) = Cx; onde C :=

2

6

6

6

6

6

6

4

c

1

c

2

.

.

.

c

m

3

7

7

7

7

7

7

5

; C 2 R

m�n

:= fx : Ax � b; x � 0g; A 2 R

p�n

; b 2 R

p

Forma matricial

minimizar

x

Cx s.a Ax � b; x � 0

Proposi�c~ao 1

Y := fy : y = Cx; x 2 g �e um conjunto convexo

Prova: Sejam y

1

= Cx

1

; y

2

= Cx

2

com x

1

; x

2

2 .

Ent~ao, 8� 2 [0; 1],

�y

1

+ (1� �)y

2

= C(�x

1

+ (1� �)x

2

| {z }

2

) 2 Y 2

PAVF

c

1999 81


Problemas multiobjetivos lineares

Se x

�

2 �e e�ciente, ent~ao n~ao existe qualquer x 2

tal que

Cx � Cx

�

e Cx 6= Cx

�

e� () : decis~oes e�cientes

e� (Y) := f(e� ()) : valores e�cientes

polit�opico

� possui um n�umero �nito de pontos extremos:

ex

:= fx

1

; x

2

; : : : ; x

v

g

� pode ser escrito como

= fx : x =

v

X

i=1

�

i

x

i

; �

i

� 0;

v

X

i=1

�

i

= 1g

� possui um n�umero �nito de pontos extremos e�cien-

tes:

e� ()

ex

:= e� () \

ex

PAVF

c

1999 82


Teorema

e� () � conv (e� ()

ex

)

Prova: Assuma que x

�

2 e� () e x

�

62 conv (e� ()

ex

).

Se �e um politopo e x

i

2

ex

; i = 1; 2; : : : ; v, existem

�

�

i

; i = 1; 2; : : : ; v tais que

x

�

=

v

X

i=1

�

�

i

x

i

; �

�

i

� 0;

v

X

i=1

�

�

i

= 1

Caso contr�ario, x

�

2 e� () seria um ponto extremo e

x

�

2 conv (e� ()

ex

). Existe ent~ao no m��nimo um k tal

que �

�

k

6= 0 e

x

�

= �

�

k

x

k

+

X

i 6=k

�

�

i

x

i

e x

k

62 e� (). Neste caso, �

�

k

< 1, pois se �

�

k

= 1, ent~ao

x

�

= x

k

contradiz x

�

2 e� (). Seja

x

�

= �

�

k

x

k

+ �

X

i 6=k

�

�

i

�

!

x

i

| {z }

x2

; �

�

k

+ � = 1

onde � :=

v

X

i 6=k

�

�

i

. Por outro lado, se x

k

62 e� (), existe

x

0

2 tal que

Cx

k

= Cx

0

+ �; � � 0; � 6= 0

PAVF

c

1999 83


Prova (cont.)

Mas neste caso,

Cx

�

= �

�

k

Cx

k

+ �Cx

= �

�

k

Cx

0

+ �Cx+ �

�

k

�

= C(�

�

k

x

0

+ �x

| {z }

2

) + �

�

k

�

e do mesmo modo, x

�

62 e� () (pois � � 0; � 6= 0),

contradizendo a hip�otese inicial 2

Gera�c~ao de e� ()

1: Identi�que

ex

2: Dentre

ex

, determine e� ()

ex

3: Obtenha e� () atrav�es de combina�c~oes convexas de

e� ()

ex

� Note que, em geral, e� () 6= conv (e� ())

� Em geral, e� () �e descrito por pontos extremos e

faces e�cientes

PAVF

c

1999 84


Exemplo

PSfrag replacements

e� ()

C

�

conv (e� ())

0

1

1

2

2

3

3

4

A

B

C

D

E

F

x

1

x

2

c

1

c

2

�

ex

= fA,B,C,D,E,Fg

� e� ()

ex

= fA,B,C,Dg

� e� () = ABCD

� Porque n~ao gerar apenas e� ()

ex

? A solu�c~ao do pro-

blema pode n~ao ser um ponto extremo ...

PAVF

c

1999 85


Programa�c~ao linear (revis~ao)

Considere o PL mono-objetivo na forma padr~ao

minimizar

x

cx; c 2 R

1�n

s.a Ax = b; rank(A) = p

x � 0

De�ni�c~ao - Solu�c~ao b�asica

Seja B 2 R

p�p

qquer submatriz n~ao-singular formada

por colunas de A e N 2 R

p�(n�p)

a matriz formada pelas

colunas restantes. De�nindo x := (x

B

; x

N

), �e poss��vel

escrever

Bx

B

+Nx

N

= b

e (x

B

; 0) �e uma solu�c~ao b�asica de Ax = b

� x

B

: vari�aveis b�asicas

� x

N

: vari�aveis n~ao-b�asicas

De�ni�c~ao - Solu�c~ao b�asica degenerada

Uma solu�c~ao b�asica (x

B

; 0) �e degenerada se uma ou

mais componentes de x

B

assume valor nulo

PAVF

c

1999 86


De�ni�c~ao - Solu�c~ao b�asica fact��vel

Uma solu�c~ao b�asica (x

B

; 0) �e fact��vel se x

B

� 0. Uma

solu�c~ao b�asica fact��vel �e degenerada se uma ou mais com-

ponentes de x

B

assume valor nulo

Teorema 1 (Teorema fundamental da PL)

Dado um problema linear,

a) Se existe uma solu�c~ao fact��vel, existe uma solu�c~ao b�asica

fact��vel

b) Se existe uma solu�c~ao �otima fact��vel, existe uma so-

lu�c~ao �otima b�asica fact��vel

Implica�c~ao pr�atica

A busca por uma solu�c~ao �otima pode �car restrita �as

solu�c~oes b�asicas, cujo no. m�aximo �e

0

@

n

p

1

A

=

n!

p!(n� p)!

M�etodo Simplex

Evolui de uma solu�c~ao b�asica fact��vel �a outra de maneira

a decrescer continuamente o valor da fun�c~ao objetivo

PAVF

c

1999 87


Forma canonica

Bx

B

+Nx

N

= b

x

B

+ B

�1

Nx

N

= B

�1

b

x

1

x

2

� � � x

p

x

p+1

x

p+2

� � � x

n

1 0 � � � 0 �a

1;p+1

�a

1;p+2

� � � �a

1;n

�

b

1

0 1 � � � 0 �a

2;p+1

�a

2;p+2

� � � �a

1;n

�

b

2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

0 0 � � � 1 �a

p;p+1

�a

p;p+2

� � � �a

p;n

�

b

r

� Relativamente �a base formada (spg) pelas primeiras p

colunas de A,

�a

ij

: representa�c~ao de a

ij

(A := fa

ij

g)

�

b

i

: representa�c~ao de b

i

� No caso,

x

B

= (x

1

; x

2

; : : : ; x

p

) = (

�

b

1

;

�

b

2

; : : : ;

�

b

p

)

x

N

= (x

p+1

; x

p+2

; : : : ; x

n

) = (0; 0; : : : ; 0)

� Assume-se a existencia de uma solu�c~ao b�asica fact��vel:

x

B

= (

�

b

1

;

�

b

2

; : : : ;

�

b

p

; 0; 0; : : : ; 0)

PAVF

c

1999 88


Fun�c~ao objetivo

z = cx = c

1

x

1

+ c

2

x

2

+ � � �+ c

n

x

n

= c

B

x

B

+ c

N

x

N

e em rela�c~ao a qualquer solu�c~ao b�asica, z = z

0

:= c

B

x

B

.

Por outro lado,

z = c

B

[B

�1

b� B

�1

Nx

N

] + c

N

x

N

= c

B

B

�1

b+ [c

N

� c

B

B

�1

N ]x

N

= z

0

+ [c

N

� c

B

B

�1

N ]

| {z }

custos relativos

x

N

De�ne-se

J : ��ndices das vari�aveis b�asicas

J : ��ndices das vari�aveis n~ao-b�asicas

I := J [ J = f1; 2; : : : ; ng

Teorema 2 (Condi�c~ao de otimalidade)

Se para alguma solu�c~ao b�asica fact��vel

r

j

:= [c

N

� c

B

B

�1

N ]

j

� 0; 8 j 2 J

ent~ao a solu�c~ao b�asica considerada �e �otima

PAVF

c

1999 89


Algoritmo Simplex

1: Obtenha a forma canonica do problema linear; deter-

mine uma solu�c~ao b�asica fact��vel inicial. O problema

�e infact��vel caso n~ao exista tal solu�c~ao

2: Se r

j

� 0; 8 j 2 J pare: a base corrente �e �otima.

Sen~ao, v�a para o passo 3

3: Selecione q tal que r

q

< 0. A vari�avel n~ao-b�asica x

q

dever�a entrar na base. V�a para o passo 4

4: Calcule as raz~oes

�

b

i

=�a

iq

para todo �a

iq

> 0; i = 1; : : : ; p.

Se �a

iq

� 0; i = 1; : : : ; p, pare: o problema �e ilimitado.

Caso contr�ario, selecione o ��ndice s correspondente �a

menor raz~ao e v�a para o passo 5

5: Introduza a vari�avel x

q

na base atrav�es de pivoteamen-

to sobre o elemento sq e volte ao passo 2

Caracter��sticas

� Convergencia �nita: existe um no. �nito de solu�c~oes

b�asicas fact��veis

� Existem algoritmos mais e�cientes para certos tipos de

problemas lineares

PAVF

c

1999 90


Simplex Multiobjetivo

Na forma canonica inicial,

I B

�1

N B

�1

b

0 c

1

N

� c

1

B

B

�1

N �z

10

0 c

2

N

� c

2

B

B

�1

N �z

20

.

.

.

.

.

.

.

.

.

0 c

m

N

� c

m

B

B

�1

N �z

m0

c

i

B

; c

i

N

: custos b�asicos e n~ao-b�asicos do objetivo i

z

i0

= c

i

B

B

�1

b : valor corrente do objetivo i

x

1

x

2

� � � x

p

x

p+1

x

p+2

� � � x

n

1 0 � � � 0 �a

1;p+1

�a

1;p+2

� � � �a

1;n

�

b

1

0 1 � � � 0 �a

2;p+1

�a

2;p+2

� � � �a

1;n

�

b

2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

0 0 � � � 1 �a

p;p+1

�a

p;p+2

� � � �a

p;n

�

b

p

0 0 � � � 0 r

1;p+1

r

1;p+2

� � � r

1;n

�z

10

0 0 � � � 0 r

2;p+1

r

2;p+2

� � � r

1;n

�z

20

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

0 0 � � � 0 r

m;p+1

r

m;p+2

� � � r

m;n

�z

m0

De�ne-se o vetor de custos relativos da vari�avel x

j

como

r

j

:= [r

1;j

r

2;j

� � � r

m;j

]

T

; j 2 J

PAVF

c

1999 91


� Para todo j 2 J determina-se

�

j

:= min

i

f

�

b

i

=�a

ij

; �a

ij

> 0g

� Se a coluna j 2 J for introduzida na base, ser�a obtida

uma nova solu�c~ao que se relaciona com a anterior atrav�es

de

z

2

= z

1

+ �

j

r

j

onde z

i

:= [z

i

10

z

i

20

� � � z

i

m0

]

T

Proposi�c~ao 2

Dada uma solu�c~ao b�asica fact��vel e assumindo �

j

> 0

para algum j 2 J , ent~ao

a) Se r

j

� 0 e r

j

6= 0, ent~ao a base corrente n~ao �e

e�ciente

a) Se r

j

� 0 e r

j

6= 0, ent~ao a introdu�c~ao da vari�avel (co-

luna) x

j

na base conduz a uma solu�c~ao n~ao-e�ciente

Proposi�c~ao 3

Dada uma solu�c~ao b�asica fact��vel, se existem colunas

l; k 2 J tais que �

l

r

l

� �

k

r

k

e �

l

r

l

6= �

k

r

k

, ent~ao a

solu�c~ao resultante de se introduzir a coluna k �e dominada

pela solu�c~ao de se introduzir a coluna l na base

PAVF

c

1999 92


Proposi�c~ao 4

Dada uma solu�c~ao b�asica fact��vel, se r

i;j

� 0; 8 j 2 J ,

ent~ao o objetivo i est�a no seu valor m��nimo. Se a solu�c~ao

for �unica (r

i;j

> 0; 8 j 2 J ), a solu�c~ao b�asica corrente �e

e�ciente

As proposi�c~oes anteriores

� fornecem informa�c~oes limitadas acerca de uma dada

solu�c~ao b�asica ser e�ciente ou n~ao

� indicam que determinadas mudan�cas de base levam a

solu�c~oes b�asicas n~ao-e�cientes

� n~ao garantem que, mesmo exclu��das as mudan�cas ex-

plicitamente vedadas, a solu�c~ao b�asica seguinte ser�a

e�ciente

Considere o Problema Auxiliar (PA)

maximizar

x;�

m

X

i=1

�

i

s.a Ax = b

Cx+ � = Cx

0

x � 0; � � 0

� := (�

1

; �

2

; : : : ; �

m

)

x

0

2 : solu�c~ao fact��vel qualquer

PAVF

c

1999 93


Teorema 3

Dado x

0

2 , seja � o valor �otimo do problema auxiliar

(� � 0). Ent~ao x

0

2 e� () se e somente se � = 0

Prova: Seja x

�

2 ; �

�

� 0 uma solu�c~ao �otima do proble-

ma auxiliar e suponha que � > 0. Ent~ao existe ao menos

um k tal que �

�

k

> 0 e

c

k

x

�

< c

k

x

0

e portanto x

0

62 e� (). Se � = 0, ent~ao �

�

i

= 0; i =

1; 2; : : : ;m e n~ao existe x 2 tal que

Cx � Cx

0

e Cx 6= Cx

0

ou seja, x

0

2 e� () 2

� PA: usado para veri�car se uma dada solu�c~ao b�asica �e

ou n~ao e�ciente

� pode ser formulado e resolvido a partir do tableau que

expressa a solu�c~ao b�asica objeto da veri�ca�c~ao

� parte essencial de qualquer algoritmo destinado a gerar

solu�c~oes b�asicas e�cientes do problema multiobjetivo

PAVF

c

1999 94


Formula�c~ao do PA

Seja B uma base associada ao problema multiobjetivo e

x

0

a solu�c~ao b�asica correspondente. O tableau do problema

auxiliar �e

A

p�n

I

p�p

0

p�m

b

p�1

C

m�n

0

m�p

I

m�m

Cx

0

0

1�n

0

1�p

e

1�m

0

e := [1 1 � � � 1]

Em termos da base B,

B

�1

A B

�1

0

p�m

B

�1

b

C � c

B

B

�1

A �c

B

B

�1

I

m�m

0

m�1

e[c

B

B

�1

A� C] ec

B

B

�1

0

1�m

0

que fornece a solu�c~ao b�asica (x; e) = (x

0

; 0) para o proble-

ma auxiliar. Note que c

B

B

�1

b = Cx

0

e se

e[c

B

B

�1

A� C j c

B

B

�1

] � 0

ent~ao x

0

tamb�em resolve PA

PAVF

c

1999 95


Algoritmo Simplex Multiobjetivo (Zeleny, 1982)

1: Determine uma solu�c~ao b�asica fact��vel inicial x

0

; fa�ca

k = 0 (no. de bases) e l = 0 (no. bases e�cientes)

2: Se x

k

minimiza algum objetivo, ent~ao x

k

(ou alguma

solu�c~ao �otima alternativa) �e e�ciente; registre x

k

, fa�ca

l = l + 1 e v�a para 5. Sen~ao, v�a para 3

3: Se r

j

� 0; r

j

6= 0 para algum j 2 J , ent~ao x

k

62

e� (). Se a introdu�c~ao de j leva a uma base n~ao

explorada, fa�ca a atualiza�c~ao, k = k + 1 e volte para

2; sen~ao, v�a para 8. Se n~ao existe j 2 J tal que

r

j

� 0; r

j

6= 0, v�a para 4

4: Formule e resolva o problema auxiliar (PA). Se x

k

�e

e�ciente, registre x

k

e fa�ca l = l + 1; v�a para 5

5: Veri�que se existe coluna dominante. Se existe e a base

resultante ainda n~ao foi explorada, fa�ca a atualiza�c~ao,

k = k + 1 e v�a para 2; se a base j�a foi explorada, v�a

para 8. Se n~ao existe coluna dominante, v�a para 8 se

x

k

62 e� () ou para 6 se x

k

2 e� () e/ou l = 0

6: Veri�que se existem colunas r

j

; j 2 J n~ao com-

par�aveis com o vetor 0. Se existem colunas deste tipo,

v�a para 7; se n~ao existem, v�a para 8

7: Armazene todas as colunas (bases) n~ao exploradas que

n~ao levariam a solu�c~oes dominadas; v�a para 8

8: Se existirem bases armazenadas a explorar, selecione

uma delas, fa�ca a atualiza�c~ao, k = k + 1 e v�a para 2;

sen~ao, �m

PAVF

c

1999 96


Exemplo

minimizar

x

(f

1

(x); f

2

(x))

s.a g

i

(x) � 0; i = 1; 2; 3; 4

x

1

; x

2

� 0

f

1

(x) = �5x

1

+ 2x

2

f

2

(x) = x

1

� 4x

2

g

1

(x) = �x

1

+ x

2

� 3

g

2

(x) = x

1

+ x

2

� 8

g

3

(x) = x

1

� 6

g

4

(x) = x

2

� 4

PSfrag replacements

C

�

0

1

1

2

2

3

3

4

4 5 6

A

B

C D

E

F

g

1

g

2

g

3

g

4

x

1

x

2

c

1

c

2

e� () = CDEF

ex

= fA,B,C,D,E,Fg

e� ()

ex

= fC,D,E,Fg

PAVF

c

1999 97


1: Solu�c~ao inicial

x

1

x

2

x

3

x

4

x

5

x

6

-1 1 1 0 0 0 3

1 1 0 1 0 0 8

1 0 0 0 1 0 6

0 1 0 0 0 1 4

-5 2 0 0 0 0 0

1 -4 0 0 0 0 0

� x

0

= A = (0; 0; 3; 8; 6; 4); k = 0; l = 0

2: Nenhum objetivo no valor �otimo

3: Nenhuma coluna r

j

� 0; r

j

6= 0 para algum j 2 J

4: Formular e resolver o problema auxiliar

x

1

x

2

x

3

x

4

x

5

x

6

�

1

�

2

-1 1 1 0 0 0 0 0 3

1 1 0 1 0 0 0 0 8

1 0 0 0 1 0 0 0 6

0 1 0 0 0 1 0 0 4

-5 2 0 0 0 0 1 0 0

1 -4 0 0 0 0 0 1 0

4 2 0 0 0 0 0 0 0

PAVF

c

1999 98


4: O valor do PA pode ser melhorado introduzindo a va-

ri�avel x

1

; �

2

deixa a base; o novo tableau �e

x

1

x

2

x

3

x

4

x

5

x

6

�

1

�

2

0 -3 1 0 0 0 0 1 3

0 5 0 1 0 0 0 -1 8

0 4 0 0 1 0 0 -1 6

0 1 0 0 0 1 0 0 4

0 -18 0 0 0 0 1 5 0

1 -4 0 0 0 0 0 1 0

0 18 0 0 0 0 0 -4 0

Pode-se introduzir x

2

, com a sa��da de x

5

, mas o pivo-

temanto produzir�a �

1

= 6� (18=4) = 27. Portanto � > 0

e x

0

62 e� ()

5: N~ao existe coluna dominante

6: (l = 0) As colunas de custos 1 e 2 n~ao s~ao compar�aveis

com 0

7: Bases a explorar: J

1

= f1; 3; 4; 6g; J

2

= f2; 4; 5; 6g,

relativas as colunas 1 e 2

PAVF

c

1999 99


8: Existem bases a explorar; escolhe-se J

2

; x

2

entra na

base, sai x

3

; o tableau ap�os pivotemento �e

x

1

x

2

x

3

x

4

x

5

x

6

-1 1 1 0 0 0 3

2 0 -1 1 0 0 5

1 0 0 0 1 0 6

1 0 -1 0 0 1 1

-3 0 -2 0 0 0 -6

-3 0 4 0 0 0 12

� x

1

= B = (0; 3; 0; 5; 6; 1); k = 1


3: r

1

� 0; r

1

6= 0; a base corrente n~ao �e e�ciente; intro-

duzir x

1

com a sa��da de x

6

leva a uma base n~ao explorada

(J = (1; 2; 4; 5)); pivoteando ...

x

1

x

2

x

3

x

4

x

5

x

6

0 1 0 0 0 -1 4

0 0 1 1 0 -2 3

0 0 1 0 1 -1 5

1 0 -1 0 0 1 1

0 0 -5 0 0 3 -3

0 0 1 0 0 3 15

� x

2

= C = (1; 4; 0; 3; 5; 0); k = 2

PAVF

c

1999 100


2: O objetivo f

2

est�a no �otimo; a solu�c~ao �e �unica; x

2

�e

e�ciente; l = 1

5: A coluna 3 �e dominante em rela�c~ao a 6; a base resultante

(J = (1; 2; 3; 5)) n~ao foi explorada; pivoteando

x

1

x

2

x

3

x

4

x

5

x

6

0 1 0 0 0 -1 4

0 0 1 1 0 -2 3

0 0 0 -1 1 1 2

1 0 0 1 0 1 4

0 0 0 5 0 -7 12

0 0 0 -1 0 5 12

� x

3

= D = (4; 4; 3; 0; 2; 0); k = 3


3: Nenhuma coluna r

j

� 0; r

j



x

1

x

2

x

3

x

4

x

5

x

6

�

1

�

2

0 1 0 0 0 -1 0 0 4

0 0 1 1 0 -2 0 0 3

0 0 0 -1 1 1 0 0 2

1 0 0 1 0 1 0 0 4

0 0 0 5 0 -7 1 0 0

0 0 0 -1 0 5 0 1 0

0 0 0 -4 0 2 0 0 0

PAVF

c

1999 101


4: O valor de PA pode ser melhorado introduzindo a va-

ri�avel x

6

na base, saindo �

2

; pivoteando ...

x

1

x

2

x

3

x

4

x

5

x

6

�

1

�

2

0 1 0 1/5 0 0 0 -1/5 4

0 0 1 3/5 0 0 0 2/5 3

0 0 0 -4/5 1 0 0 -1/5 2

1 0 0 6/5 0 0 0 -1/5 4

0 0 0 18/5 0 0 1 7/5 0

0 0 0 -1/5 0 1 0 1/5 0

0 0 0 -18/5 0 0 0 -2/5 0

� O valor �otimo de PA foi atingido com � = 0; x

3

�e

e�ciente; l = 2


6: As colunas 4 e 6 s~ao n~ao compar�aveis com 0

7: Bases a explorar: J

3

= f1; 2; 4; 5g, j�a explorada, e

J

4

= f1; 2; 3; 6g, relativas as colunas 4 e 6

8: As bases existentes s~ao J

1

= f1; 3; 4; 6g e J

4

= f1; 2; 3; 6g;

escolhe-se introduzir a coluna 6, levando �a base J

4

; pivo-

teando ...

PAVF

c

1999 102


x

1

x

2

x

3

x

4

x

5

x

6

0 1 0 1 -1 0 2

0 0 1 -1 2 0 7

0 0 0 -1 1 1 2

1 0 0 0 1 0 6

0 0 0 -2 7 0 26

0 0 0 4 -5 0 2

� x

4

= E = (6; 2; 7; 0; 0; 2); k = 4


3: Nenhuma coluna r

j

� 0; r

j



x

1

x

2

x

3

x

4

x

5

x

6

�

1

�

2

0 1 0 1 -1 0 0 0 2

0 0 1 -1 2 0 0 0 7

0 0 0 -1 1 1 0 0 2

1 0 0 0 1 0 0 0 6

0 0 0 -2 7 0 1 0 0

0 0 0 4 -5 0 0 1 0

0 0 0 -2 -2 0 0 0 0

� x

4

resolve PA e � = 0; x

4

�e e�ciente; l = 3

PAVF

c

1999 103



6: Nenhuma coluna de custos compar�avel com 0

8: Base a explorar: J

1

= f1; 3; 4; 6g; entra x

4

, sai x

2

;

pivoteando, ...

x

1

x

2

x

3

x

4

x

5

x

6

0 1 0 1 -1 0 2

0 1 1 0 1 0 9

0 1 0 0 0 1 4

1 0 0 0 1 0 6

0 2 0 0 5 0 30

0 -4 0 0 -1 0 -6

� x

5

= F = (6; 0; 9; 2; 0; 4); k = 5

2: O objetivo f

1

est�a no �otimo; a solu�c~ao �e �unica; x

5

�e

e�ciente; l = 4

5: A coluna 2 �e dominante, mas a base J = f1; 2; 4; 6g j�a

foi explorada

8: N~ao existem bases armazenadas a explorar; �m

PAVF

c

1999 104


Resumo

x

1

x

2

x

3

x

4

x

5

x

6

f

1

f

2

A 0 0 3 8 6 4 0 0

B 0 3 0 5 6 1 6 -12

C 1 4 0 3 5 0 3 -15

D 4 4 3 0 2 0 -12 -12

E 6 2 7 0 0 2 -26 -2

F 6 0 9 2 0 4 -30 6

� A base A �e dominada por D e E; B �e dominada por C;

C,D,E e F s~ao solu�c~oes b�asicas e�cientes

� Os valores ut�opicos de f

1

e f

2

s~ao y

1

= �30 e y

2

=

�15, respectivamente

� O exemplo teve in��cio com uma solu�c~ao n~ao e�ciente

(A); uma maneira de obter uma base inicial e�ciente

seria resolver

minimizar

x

m

X

i=1

w

i

c

i

x s.a Ax � b; x � 0

para qualquer w 2 W com w > 0. A solu�c~ao deste

problema ponderado �e uma base e�ciente do problema

� Outros m�etodos poderiam ser usados para obter uma

base inicial e�ciente

Documents

Cap4 Notas Aulas Valente