Trabalho_feito_2010-1

Prévia do material em texto

O"mização

Implementação
do
Simplex
Revisado

Resolução
da
Tarefa
1.1

U"lização
da
Fase
1

Página
39,
Chvátal

•  Temos
o
problema:

Max.

 

x1
–


x2
+


x3



s.a.:

 2x1
–


x2
+
2x3


≤



4


 

 
 2x1
–
3x2
+


x3


≤

–5


 

 
 –x1
+


x2
–
2x3


≤

–1


 

 
 
 
 x1,
x2,
x3



≥



0

•  Agora
colocamos
o
problema
na
forma
padrão

Max.

 

x1
–


x2
+


x3


+


0s1

+


0s2

+


0s3



s.a.:

 2x1
–


x2
+
2x3


+




s1

 
 
 
 
 
=



4


 

 
 2x1
–
3x2
+


x3















+



s2














=

–5


 

 
 –x1
+


x2
–
2x3





























+


s3

=

–1


 

 
 
 
 x1,
x2,
x3,
s1,
s2,
s3



≥



0

•  Primeiro
passo:
Construção
da
primeira
base
(folgas
na
base).

Obtemos
o
dicionário:

s1
 =




4

–


2x1

+



x2

–


2x3
 
 
 
 
 
 
 s1

=




4


s2


=


–5

–


2x1

+

3x2

–




x3
 
 
 
 
 
 
 s2

=


–5



s3


=


–1

+




x1

–



x2

+


2x3
 
 
 
 
 
 
 s3

=


–1

___________________________________

Z


=

















x1

–



x2

+




x3

Observamos
porém
que
“setando”
as
variáveis
de
decisão
em
zero
vamos

contra
a
condição
de
o"malidade
que
força
as
variáveis
do
problema
de

serem
todas
maiores
ou
iguais
a
zero,
uma
vez
que
duas
folgas
ficam
com

valores
nega"vos
=>
Origem
inviável!



•  Podemos
resolver
esse
problema
usando
o
Problema

Auxiliar:

Max.
 
 ‐
x0



s.a.:
 
 2x1
–


x2
+
2x3

–

x0


≤



4


 
 
 
 2x1
–
3x2
+


x3

–

x0


≤

–5


 
 
 
 –x1
+


x2
–
2x3

–

x0


≤

–1


 
 
 
 
 
 x0,
x1,
x2,
x3




≥



0

Fazemos
isso,
pois
incluindo
a
variável
x0
“alargamos”
a
região

viável
do
problema,
fazendo
com
que
a
origem
possa
ser

incluída.

•  Na
forma
padrão:

Max.

 ‐
x0



s.a.:

 2x1
–


x2
+
2x3

+


s1
 
 













–

x0

=



4


 

 
 2x1
–
3x2
+


x3













+

s2












–

x0

=

–5


 

 
 –x1
+


x2
–
2x3























+


s3


–

x0

=

–1


 

 
 
 
 
 
















x0,
x1,
x2,
x3,
s1,
s2,
s3


≥



0

•  Obtemos
portanto,
o
primeiro
dicionário
(folgas

na
base):

s1
 

=




4

–


2x1

+



x2

–


2x3

+


x0

 
 
 
 

s2



=


–5

–


2x1

+

3x2

–




x3


+


x0

 
 
 
 
 
 

s3



=


–1

+




x1

–



x2

+


2x3


+


x0

____________________________________________

w


=















































–


x0

Na
fase
1
formamos
o
dicionário
acima.
Além
disso
é
realizada
a

primeira
troca
de
base,
colocando
x0
na
base
e
removendo
da
base

a
variável
cujo
valor
é
o
mais
inviável
(nesse
caso
a
variável
s2).

Transformamos
esse
dicionário
inviável
em
um
viável!


•  Para
isso
perguntamos
se
existe
algum
valor

nega"vo
em
b,
no
caso
afirma"vo,
rodamos
a

fase
1.
Do
contrário,
iremos
direto
para
a
fase
2.

•  Na
fase
1
são
construídas
as
matrizes
A
(forma

padrão),
B,
N,
e
o
vetor
c,
bem
como
os
vetores

de
índices
das
variáveis
básicas
e
não
básicas,

para
que
seja
montado
o
primeiro
dicionário.

•  Montado
o
dicionário,
este
viável,
fazemos
a

primeira
troca
de
base
(x0
na
base)
e
chamamos
a

fase
2
para
resolver
o
problema.


•  Uma
vez
na
fase
2,
podemos
observar
que
um
dicionário
é
escrito

na
forma
geral:

XB


=


B‐1b


–


B‐1NXN
________________________________________

Z




=


cBB‐1b


+


(cN
–
cBB‐1N)XN

cN
–
cBB‐1N
representa
os
coeficientes
das
variáveis
não
básicas.

Maximização
=>
se
cN
–
cBB‐1N
>
0
não
achou
ponto
ó"mo!

Declara
y
=
cBB‐1
=>
Se
ya
<
cj
ainda
não
achamos
um
ó"mo!

a
=
coluna
entrante
na
base.

cj
=
componente
do
vetor
cN
que
corresponde
a
variável
não
básica
que

entrará
na
base.




•  Variável
que
sairá
da
base:


valor
t
da
variável
não
básica
entrante


mantendo
zeradas
as
outras
não
básicas.

Conforme
t


,
para
preservar
Ax
=
b,
os
valores

das
variáveis
básicas


,
até
que
uma
variável

cujo
valor
é
o
primeiro
a
ir
para
zero
saia
da

base.

•  Como
vimos,
as
primeiras
linhas
do
dicionário
podem
ser
escritas
como:

XB


=


B‐1b


–


B‐1NXN


 Início:
Folgas
na
base,
então,
xB
=
b,
pois
B
é
a
iden"dade.

Depois
xB
muda
para
xB
–
td,
onde
d
=
B‐1a.

Temos
então
que
achar
o
maior
t
tal
que
xB
–
td
≥
0.
(teste
da
razão)

t
não
existe
=>
problema
é
ilimitado.

Do
contrário,
pelo
menos
uma
componente
da
desigualdade
é
igual
a
zero

e
a
variável
correspondente
é
a
que
sai
da
base.

Ao
final
do
método,
atualizamos
os
vetores
de
índices
de
variáveis
básicas

e
não
básicas
e
rodamos
novamente
até
que
se
mostre
que
o
problema
ou

é
inviável,
ou
é
ilimitado
ou
tem
ponto
ó"mo.



• Após
a
implementação
do
método,
obtemos:

Existe
ponto
ó"mo!


O
estado
é
igual
a
1.


O
valor
ó"mo
da
função
obje"vo
é
0.600000.


O
ponto
ó"mo
é:


x
=










0





2.8000





3.4000

Vetor
de
folgas
das
restrições:


s
=






0






0






3

Vetor
de
variáveis
duais
associadas
às
restrições:


y
=





0.4000



0.2000








0

Vetor
de
índices
rela"vos
às
variáveis
básicas:


base
=






6




3




2

Vetor
de
índices
rela"vos
às
variáveis
não
básicas:


nbase
=






1




4




5

Neste
problema
foram
realizadas
4
iterações,
totalizando
um
tempo
de
execução
de
0.030000.

Resolução
da
Tarefa
1.2

Problema
ilimitado

Página
44,
exercício
3.9,
letra
(c),

Chvátal

•  Temos
o
problema:

Max.
 
 

3x1


+


x2



s.a.:
 
 



x1


–


x2


≤


–1


 
 
 
 

–x1


–


x2


≤


–3


 
 
 
 

2x1


–


x2


≤




2


 
 
 
 
 


x1,
x2



≥




0

Onde:














1



‐1


















‐1




















3







 
 
A
=




‐1



‐1








b
=




‐3









c
=





























2



‐1




















2




















1


•  Após
a
implementação
do
método
obtemos:

Problema
ilimitado!


O
estado
é
igual
a
0.


Vetor
de
direção
extrema:


x
=






1






2

Neste
problema
foram
realizadas
4
iterações,
totalizando
um
tempo
de

execução
de
0.000000.

•  Se
plotarmos
o
problema,
podemos
ver
as
restrições
e
o
vetor
de
direção
extrema,
valor
esse

atribuído
ao
vetor
x.

(1)

‐>





x1


–


x2


=


–1



(2)

‐>



–x1


–


x2


=


–3



(3)  ‐>



2x1


–


x2


=




2

d
=
(1,2)
‐>
Vetor
de
direção
extrema

Resolução
da
Tarefa
2

•  Produção
de
uma
fábrica:
n
"pos
de
produtos

diferentes.

•  Obje"vo:
Maximização
dos
lucros
definindo
a

quan"dade
ó"ma
a
produzir
de
cada
produto.

•  Limite:
m
restrições
devido
a
m
recursos

(consumo
de
matéria
prima,
disponibilidade

de
mão
de
obra,
espaço
de
armazenagem
...).

Max.
 
 L1x1
+
L2x2
+
...
+
Lnxn



s.a.:
 
 a11x1

+


a12x2

+

...

+

a1nxn


≤


disp1


 
 
 
 a21x1

+


a22x2

+
...

+


a2nxn


≤




disp2


 

 
 
 
 
 






 
 ...


 
 
 
 am1x1

+

am2x2

+
...

+

amnxn


≤


disp
m


 

 
 
 
 
 
 
 x1,
x2,
...,
xn




≥


0


 
 
 




Li
é
o
lucro
do
produto
i


 Onde:





amn
corresponde
ao
recurso
m
do
produto
n


 
 
 


 






disp
m
corresponde
a
disponibilidade
dos

m
recursos






 
 
 
 
 
 
 
 

•  Gerando
vetores
de
lucros,
de
recursos
e
de

disponibilidades
para
diferentes
instâncias

obtemos:

•  Geramos
o
gráfico:

Tamanho
da
instância
[m
x
n]

Te
m
po
s

de

e
xe
cu
çã
o

[s
]

Tempo
de
execução
do
algoritmo

Tempo
de
execução
do
linprog

•  Número
de
iterações
ao
longo
das
instâncias

Instâncias

It
er
aç
õe
s