Graduação em Engenharia Elétrica

Graduação em Engenharia Elétrica

MÉTODOS DE OTIMIZAÇÃO – ENE081

PROF. IVO CHAVES DA SILVA JUNIOR E-mail: [email protected]

Aula Número: 05

UNIVERSIDADE FEDERAL DE JUIZ DE FORA

Disciplina “Métodos de Otimização ENE081” – Aula Número: 05 – PROF. IVO CHAVES DA SILVA JUNIOR

Programação Linear

RESOLUÇÃO DE PROBLEMAS DE OTIMIZAÇÃO LINEAR

RESOLUÇÃO GRÁFICA (2 VARIÁVEIS)

RESOLUÇÃO PELO MÉTODO SIMPLEX (N VARIÁVEIS)

Consideração para o uso do Simplex: •  O problema deve estar escrito na forma PADRÃO


Programação Linear – Forma Padrão

0},,{:.

≥

≥≤=

=

xbAxas

xczMax T

0:.

≥

=

=

xbAxasxczMax T

Forma Geral Forma Padrão

Os termos independentes das restrições devem ser não negativos;

Todas as restrições, com exceção das de não negatividade, devem ser apresentadas na forma de igualdade;

As variáveis de decisão devem ser não negativas.



Por que da forma padrão ? A álgebra linear trata bem sistemas assim estruturados.

Qualquer que seja a estrutura do problema de programação linear, sempre é possível colocá-la na formar padrão.

0:.

≥

=

=

xbAxasxczMax T

Forma Padrão



Como passar da forma geral para forma padrão ? Como transformar inequações em equações? Resp: Inserção de novas variáveis nas inequações

[ ]

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

≥

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

0

00

:. 2

1

2

1

2

1

21

22221

11211

2

1

21

nmnmnmm

n

n

n

n

x

xx

b

bb

x

xx

aaa

aaaaaa

as

x

xx

ccczMax

e

Forma Padrão Matricial



ü  Relação entre inequações e equações

aij x jj=1

n

∑ ≤ bi ≡aij x j

j=1

n

∑ + Si = bi

0 ≤ Si ≤∞

%

&'

('

aij x jj=1

n

∑ ≥ bi ≡aij x j

j=1

n

∑ − Si = bi

0 ≤ Si ≤∞

%

&'

('

Variável de Folga (+S)

Variável de Excesso(-S)



Problema Original Forma Padrão

Exemplo:



Exercício 1 (sala): Coloque o problema de otimização na forma padrão

minZ = −2x1 + x2 + x3 −3x4 + x5s.ax1 + 2x2 − x3 + x4 +3x5 ≥ 54x1 + x3 − 2x4 − x5 ≤ 0−2x3 + x4 + 2x5 ≥ −73x1 + x2 − x4 + x5 = 8x1, x2, x5 ≥ 0x3 ≤ 0x4 qualquer

minZ = −2x1 + x2 + x3 −3x4 + x5s.ax1 + 2x2 − x3 + x4 +3x5 − s1 = 54x1 + x3 − 2x4 − x5 + s2 = 02x3 − x4 − 2x5 + s3 = 73x1 + x2 − x4 + x5 = 8x3 = −x3

'

x4 = x4' − x4

''

x1, x2, x5, s1, s2, s3, x3' , x4

' , x4'' ≥ 0



ü  Observações:

1.  A passagem para forma padrão se faz pelo simples acréscimo de uma variável de folga ou excesso para cada inequação existente.

2.  A forma padrão resultante sempre consiste em um sistema que tenha uma solução básica inicial mais fácil de ser encontrada.

Solução básica inicial (ESTRATÉGIA):

Anular as variáveis originais e obter os valores das variáveis de

folga e excesso

As variáveis nulas recebem o nome de NÃO BÁSICAS (VNB)

As variáveis não nulas recebem o nome de BÁSICAS(VB)



Exercício 2 (Sala) Encontre uma solução básica factível para:

max Z = 3x1 + 2,5x2 +1,2x3s.ax1 − 2x2 + 4x3 + x4 = 40x1 + x2 + 2x3 + x5 = 602x1 +3x2 + x3 − x6 =15x6 = −x6

*

x1,x2, x3, x4, x5, x6* ≥ 0

VNB = x1, x2, x3{ }⇒ x1 = 0, x2 = 0, x3 = 0

VB = x4, x5, x6*{ }⇒ x4 = 40, x5 = 60, x6

* =15

Z = 0

max Z = 3x1 + 2,5x2 +1,2x3s.ax1 − 2x2 + 4x3 ≤ 40x1 + x2 + 2x3 ≤ 602x1 +3x2 + x3 ≥15x1,x2, x3 ≥ 0

Solução Básica Factível (SBF) ?

Forma Padrão


Programação Linear – Método Simplex

Problemas de Programação

Linear

Método de SIMPLEX (1947)



•  O método Simplex evita a exploração exaustiva de soluções básicas.

Descrição Geral SIMPLEX

SBF Solução Básica Factível


Programação Linear – Tableau Simplex

Método SIMPLEX

Forma Tableau



Tableau SIMPLEX

Fluxograma

Maximização


Programação Linear – Tableau Simplex - Fluxograma

Início

Fim

Montar tableau Simplex com Solução Básica Inicial Factível

Existe custo (coeficientes) < 0 ?

Não

Escolher variável para entrar na base

Calcular razão ( bi / coluna)

Sim

Solução ótima

Fazer troca de base e recalcular

o tableau

Existe razão ≥ 0 finita ?

Solução ilimitada

Não

Sim

1

1 Escolher variável para sair da base

Variável com coeficiente

mais negativo na FOB

Menor razão positiva

Problema de Maximização



0,1823

1224:.

53

21

21

2

1

21

≥

≤+

≤

≤

+=

xxxx

xxas

xxzMax

Exemplo (fixação):

Resolva o Problema de PL via Tableau SIMPLEX



Max z−3 x1 − 5 x2 = 0s.a : x1 ≤ 4

2 x2 ≤123 x1 + 2 x2 ≤18x1, x2 ≥ 0

0,1823

1224:.

53

21

21

2

1

21

≥

≤+

≤

≤

+=

xxxx

xxas

xxzMax Reescrever a expressão da Função Objetivo



Max z−3 x1 − 5 x2 = 0s.a : x1 ≤ 4

2 x2 ≤123 x1 + 2 x2 ≤18x1, x2 ≥ 0

Colocar o problema na Forma Padrão

Max z−3 x1 − 5 x2 = 0s.a : x1 + S1 = 4

2 x2 + S2 =123 x1 + 2 x2 + S3 =18x1, x2,S1,S2,S3 ≥ 0



Achar uma solução básica inicial factível

Max z−3 x1 − 5 x2 = 0s.a : x1 + S1 = 4

2 x2 + S2 =123 x1 + 2 x2 + S3 =18x1, x2,S1,S2,S3 ≥ 0

01801204

3

22

11

==

==

==

zSxSxS

{ } { }32121 ,,, SSSVBxxVNB ==

Observação: A FOB deve ser sempre formada por VNB. (SEMPRE VERIFICAR ESSA CONDIÇÃO)



0,,,,1823

1224:.53

32121

321

22

11

21

≥

=++

=+

=+

−−

SSSxxSxx

SxSxas

xxzMax { } { }32121 ,,, SSSVBxxVNB ==

Base Z X1 X2 S1 S2 S3 b S1 S2 S3 Z

Tableau Simplex

Montar o Tableau SIMPLEX

Variáveis básicas +FOB

Variáveis básicas + Não Básicas+ FOB Termos Constante

das equações



0,,,,1823

1224:.53

32121

321

22

11

21

≥

=++

=+

=+

−−

SSSxxSxx

SxSxas

xxzMax { } { }32121 ,,, SSSVBxxVNB ==


Tableau Simplex

Montar o Tableau SIMPLEX

Base Z X1 X2 S1 S2 S3 b S1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 S3 0 3 2 0 0 1 18 Z 1 -3 -5 0 0 0 0

Preenchimento pelas linhas do Tableau

Restr.(1)

Restr.(2)

Restr.(3)

FOB




Tableau Simplex – Solução Inicial.

Verificar se a solução é ótima!

(Linha da FOB)


5 Variável com coeficiente mais negativo na FOB




+inf +6 +9

Entra na Base (X2)

Tableau Simplex

Saída (S2)

A menor razão mais positiva

Variável com coeficiente mais negativo na FOB



Base Z X1 X2 S1 S2 S3 b S1 0 1 0 1 0 0 4 X2 0 0 2 0 1 0 12 S3 0 3 2 0 0 1 18 Z 1 -3 -5 0 0 0 0

Entrou na Base (X2)

Tableau Simplex

Saíu da Base (S2)

Troca de Base: •  Cada nova equação (linha da Tabela)

deve possuir apenas uma VB com coeficiente unitário

•  Cada VB deve aparecer em uma só equação



Zerar a coluna de X2 com exceção da linha referente ao elemento pivô que deve assumir o valor unitário. Para tanto:

Linha 1 = Linha 1

Linha 3’ = Linha 3 - Linha 2

Linha 4’ = Linha 4 + 2,5*Linha 2

Linha 2’ = 0,5* Linha 2



Base Z X1 X2 S1 S2 S3 b S1 0 1 0 1 0 0 4

X2 0 0 1 0 1/2 0 6 S3 0 3 0 0 -1 1 6 Z 1 -3 0 0 5/2 0 30

Novo Tableau Simplex- Nova Solução

?



Base Z X1 X2 S1 S2 S3 b S1 0 1 0 1 0 0 4

X2 0 0 1 0 1/2 0 6 S3 0 3 0 0 -1 1 6 Z 1 -3 0 0 5/2 0 30

Novo Tableau Simplex- Nova Solução

Verificar se a nova solução é ótima!

(Linha da FOB)



Base Z X1 X2 S1 S2 S3 b S1 0 1 0 1 0 0 4

X2 0 0 1 0 1/2 0 6 S3 0 3 0 0 -1 1 6 Z 1 -3 0 0 5/2 0 30

+4 +inf +2

Entrada na Base (X1)

Saída (S3)

Linha 1’ = Linha 1 – (1/3)*Linha 3

Linha 2 = Linha 2

Linha 4’ = Linha 4 + Linha 3

Linha 3’ = (1/3) * Linha 3

Novo Tableau Simplex

Zerar a coluna de X1 com exceção da linha referente ao elemento pivô que deve assumir o valor unitário. Para tanto:

Variável com coeficiente mais negativo na FOB



Base Z X1 X2 S1 S2 S3 b S1 0 0 0 1 1/3 -1/3 2 X2 0 0 1 0 1/2 0 6 X1 0 1 0 0 -1/3 1/3 2 Z 1 0 0 0 3/2 1 36

Novo Tableau Simplex – Nova Solução

Verificar se a nova solução é ótima!

(Linha da FOB)



Base Z X1 X2 S1 S2 S3 b S1 0 0 0 1 1/3 -1/3 2 X2 0 0 1 0 1/2 0 6 X1 0 1 0 0 -1/3 1/3 2 Z 1 0 0 0 3/2 1 36

Tableau Simplex – Nova Solução

Fim do Processo de Maximização

Todos os coeficientes da última Linha (Z) positivos



0,1823

1224:.

53

21

21

2

1

21

≥

≤+

≤

≤

+=

xxxx

xxas

xxzMaxVar. Valor X1 2 X2 6 S1 2 S2 0 S3 0 Z 36

Solução Final Tableau Simplex



MATLAB



Tableau SIMPLEX

Fluxograma

Minimização


Programação Linear – Tableau Simplex - Fluxograma

Início

Fim

Montar tableau Simplex com solução básica inicial viável

Existe custo (Coeficientes) > 0 ?

Não

Escolher variável para entrar na base

Calcular razão ( bi / coluna)

Sim

Solução ótima

Fazer troca de base e recalcular

o tableau

Existe razão ≥ 0

finita ?

Solução ilimitada

Não

Sim

1

1 Escolher variável para sair da base

Variável com coeficiente mais positivo na FOB

Menor razão positiva

Problema de Minimização



Exercício:

Utilize o Tableau Simplex para resolver o seguinte problema de programação linear:

x1 =1/ 3; x2 = 0; x3 =13 / 3;

Z = −17

Solução


1° Passo: Forma Padrão




Saída (X6)


VNB = x1 = 0, x2 = 0, x3 = 0{ } VB = x4 = 9, x5 = 2, x6 = 4{ }

Tableau Simplex – Solução Inicial


Zerar Coluna de X3 com exceção da Linha referente a X6 que deve assumir o valor unitário (pivô). Para tanto:

Linha 1’ = Linha 1 - 4*Linha 4

Linha 2’ = Linha 2 - 2*Linha 4

Linha 3’ = Linha 3 + 1*Linha 4 Linha 4 = Linha 4




Saída (X4)

Zerar Coluna de X1 com exceção da Linha referente a X4 que deve assumir o valor unitário(pivô). Para tanto:

Linha 1’ = Linha 1 - Linha 2

Linha 3 = Linha 3

Linha 4’ = Linha 4 + (1/3)*Linha 2

Linha 2’ = (1/3)*Linha 2



Fim do Processo de Minimização

Todos os coeficientes da primeira Linha (FOB) negativos


170

;3/13;6;3/1

642

351

−====

===

Zxxx

xxx

Solução



Soluções Básicas Iniciais devem ser factíveis

Soluções factíveis são diretas quando todas as restrições do modelo são da forma ≤.

Como obter soluções inciais em modelos com restrições na forma ≥ ou = ?

Restrições do modelo na forma ≥ ou =não levam a obtenção direta de soluções iniciais factíveis.



Como obter soluções iniciais em modelos com restrições na forma ≥ ou = ?

Método das

Penalidades (BIG M)

Método das

Duas Fases


Programação Linear – Método Big M

Este método consiste em acrescentar à FOB do problema original (forma padrão) variáveis artificiais (a) e uma penalidade (M) com coeficientes:

Negativos muito grandes - Problemas de Maximização

Positivos muito grandes - Problemas de Minimização

aMxxzMax −+= 21 32

aMxxzMin ++= 21 32

Na solução final os valores das variáveis artificiais devem ser nulos (VNB).



Exemplo: Resolver o seguinte problema de PL



Forma Geral

Forma Padrão



Forma Padrão

Solução Básica Factível (SBF) inicial para o problema.

VNB = x1, x2{ }⇒ x1 = 0, x2 = 0

VB = x3, x4{ }⇒ x3 = 6, x4 = −8Z = 0

x4 = −8

x4 ≥ 0 ???Não possui

Solução Inicial Trivial

x1 + x2 = 6???



Forma Padrão Não possui


Inserção das Variáveis Artificiais e das Penalidades

Adiciona-se as variáveis artificiais nas equações do tipo:

Adiciona-se as variáveis artificiais e as penalidades (M) ao problema

≥ e =( )



Forma Padrão Não possui


Inserção das Variáveis Artificiais e das Penalidades Método Big M



Identificação das variáveis básicas e não básicas:

VNB = x1, x2, x4{ } VB = x3, x5, x6{ }

A aplicação do Método, a partir daqui, segue a procedimento Simplex.

Ok!! Mas a FOB não deve conter apenas VNB ???

Temos que eliminar x5 e x6 da FOB





Para eliminar X5 e X6 basta substituirmos suas expressões na FOB:

x5 = 8− x1 − 2x2 + x4 x6 = 6− x1 − x2

Z − 2x1 −3x2 +M (8− x1 − 2x2 + x4 )+M (6− x1 − x2 ) = 0

Expressão da FOB em função das VNB:

Z + (−2− 2M )x1 + (−3−3M )x2 +Mx4 +14M = 0




Solução Básica Factível (SBF) inicial para o problema.

VNB = x1, x2, x4{ }⇒ x1 = 0, x2 = 0, x4 = 0

VB = x3, x5, x6{ }⇒ x3 = 6, x5 = 8, x6 = 6Z = −14M

A partir daqui, segue o procedimento Tableau Simplex.

Z + (−2− 2M )x1 + (−3−3M )x2 +Mx4 +14M = 0



Tableau Inicial – Simplex- Método Big M

Base Z X1 X2 X3 X4 X5 X6 Z 1 (-2-2M) (-3-3M) 0 M 0 0

X3 0 -2 +3 1 0 0 0 X5 0 1 2 0 -1 1 0 X6 0 1 1 0 0 0 1

Solução Final.

VNB = x3, x5, x6{ }⇒ x3 = 0, x5 = 0, x6 = 0

VB = x1, x2, x4{ }⇒ x1 =125, x2 =

185, x4 =

85

Z = 785

b -14M

6

8

6

CONFERIR!!!



Min z = 4 x1 + x2s.a : x1 + x2 ≤ 3

x1, x2 ≥ 0

Exercício (sala):




Min z = 4 x1 + x2s.a : x1 + x2 ≤ 3

x1, x2 ≥ 0

1) Forma Padrão

Min z− 4 x1 − x2 = 0s.a : x1 + x2 + s = 3

x1, x2, s ≥ 0



Min z− 4 x1 − x2 = 0s.a : x1 + x2 + s = 3

x1, x2, s ≥ 0

2) Achar uma solução básica inicial factível

VNB = x1 = 0, x2 = 0{ } VB = s = 3{ }

Observação: A FOB deve ser formada apenas por VNB.



Tableau Simplex

Base Z X1 X2 S b S 0 1 1 1 3 Z 1 -4 -1 0 0

3) Montar o Tableau SIMPLEX

Se todos os coeficientes da FOB são negativos: SOLUÇÃO ÓTIMA

Min z− 4 x1 − x2 = 0s.a : x1 + x2 + s = 3

x1, x2, s ≥ 0

4) Verificar Solução

x1 = 0; x2 = 0;s = 3;Z = 0.



Exercício (Sala):


Min z = 4 x1 + x2s.a : x1 + x2 = 3

x1, x2 ≥ 0



Min z = 4 x1 + x2s.a : x1 + x2 = 3

x1, x2 ≥ 0

1) Forma Padrão

Min z− 4 x1 − x2 −MA = 0s.a : x1 + x2 + A = 3

x1, x2,A ≥ 0



Min z− 4 x1 − x2 −MA = 0s.a : x1 + x2 + A = 3

x1, x2,A ≥ 02) Achar uma solução básica inicial factível

VNB = x1 = 0, x2 = 0{ } VB = A = 3{ }

FOB formada por VB !!!!

Pergunta: Até aqui algum Problema?



Min z− 4 x1 − x2 −M (3− x1 − x2 ) = 0onde : A = 3− x1 − x2

Min z+ (M − 4)x1 + (M −1)x2 −3M = 0s.a : x1 + x2 + A = 3

x1, x2,A ≥ 0

2) Achar uma solução básica inicial factível

VNB = x1 = 0, x2 = 0{ } VB = A = 3{ }



Tableau Simplex -> M=100

Base Z X1 X2 A b A 0 1 1 1 3 Z 1 96 99 0 300

3) Montar o Tableau SIMPLEX

Como existe coeficientes da FOB positivos: Existe solução melhor que:


x1 = 0; x2 = 0;A = 3;Z = 0.

Min z+ (M − 4)x1 + (M −1)x2 −3M = 0s.a : x1 + x2 + A = 3

x1, x2, s ≥ 0



Tableau Simplex

Base Z X1 X2 A b A 0 1 1 1 3 Z 1 96 99 0 300

5) Obtenção da nova solução

Entra na Base (X2)

Saída (A)

Zerar Coluna de X2, com exceção da Linha referente a variável “A”, que deve assumir o valor unitário (pivô). Para tanto:

Linha 2’ = Linha 2 - 99*Linha 1 Tableau Simplex

Base Z X1 X2 A b X2 0 1 1 1 3 Z 1 -3 0 -99 3



Se todos os coeficientes da FOB são negativos: SOLUÇÃO ÓTIMA


Tableau Simplex

Base Z X1 X2 A b X2 0 1 1 1 3 Z 1 -3 0 -99 3

x1 = 0; x2 = 3;s = 0;Z = 3.

x1 = 0; x2 = 3;s = 0;Z = 3.

Nova Solução:


Programação Linear – Próxima Aula

Aula de Exercícios 06-05-2016 Trazer: •  Material de consulta (Notas de Aula)

•  Calculadora

Documents

Graduação em Engenharia Elétrica