programa˘c~ao de matem atica: teoria, algoritmos e aplica...

Programacao de Matematica: Teoria, Algoritmos e Aplicacoes na

Engenharia

Luiz Eloy VazAnderson PereiraIvan F. Menezes

Rio de Janeiro, 08 de agosto de 2012

Sumario

I Teoria e Algoritmos 3

1 Introducao 51.1 O Problema Geral de Programacao Matematica . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Exemplo de Aplicacao em Otimizacao de Estruturas . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Trelica Plana de Duas Barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Fundamentos de Otimizacao sem Restricoes (OSR) 132.1 Serie de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Condicoes de Mınimo no Problema de OSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.1 Condicao de Primeira Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Condicao de Segunda Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Metodos de Otimizacao sem Restricoes (OSR) 193.1 Metodos de Busca Unidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.1 Metodo de Passo Constante ou Incremental . . . . . . . . . . . . . . . . . . . . . . . . 203.1.2 Metodo de Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.3 Metodo da Bissecao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.4 Metodo da Secao Aurea (Golden Section, em ingles) . . . . . . . . . . . . . . . . . . . 203.1.5 Metodo da Ortogonalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.1.6 Metodo Secante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Metodos de Direcao de Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.1 Metodo Univariante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.2 Metodo de Powell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2.2.1 Direcoes Conjugadas no Metodo de Powell . . . . . . . . . . . . . . . . . . . 273.2.2.2 Convergencia do Metodo de Powell . . . . . . . . . . . . . . . . . . . . . . . 29

3.2.3 Metodo do Maximo Declive (Steepest Descent, em ingles) . . . . . . . . . . . . . . . . 323.2.4 Metodo de Fletcher–Reeves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.2.5 Metodo de Hestenes–Stiefel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.6 Metodo de Polak–Ribiere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.7 Metodo de Newton–Raphson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2.8 Metodos Quase–Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2.8.1 Algoritmo de Correcao de Posto Um . . . . . . . . . . . . . . . . . . . . . . . 383.2.8.2 Algoritmo de Correcao de Posto Dois ou DFP (Davison–Fletcher–Powell) . . 403.2.8.3 Algoritmo BFGS (Broyden–Fletcher–Goldfarb–Shanno) . . . . . . . . . . . . 40

4 Fundamentos de Otimizacao Com Restricoes (OCR) 434.1 Condicoes de Mınimo no Problema de OCR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.1.1 Condicoes de Primeira Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.1.1.1 Problemas com Restricoes de Igualdade . . . . . . . . . . . . . . . . . . . . . 434.1.1.2 Problemas com Restricoes de Desigualdade . . . . . . . . . . . . . . . . . . . 454.1.1.3 Problema Geral de Otimizacao com Restricoes . . . . . . . . . . . . . . . . . 47

4.1.2 Condicoes de Segunda Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1.2.1 Problemas com Restricoes de Igualdade . . . . . . . . . . . . . . . . . . . . . 47

i

ii SUMARIO

4.1.2.2 Problemas com Restricoes de Desigualdade . . . . . . . . . . . . . . . . . . . 48

4.2 Os Multiplicadores de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2.1 Exemplo de Aplicacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3 Dualidade de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.1 Exemplos Teoricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3.1.1 Programacao Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.3.1.2 Programacao Quadratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Metodos Indiretos em OCR 55

5.1 Metodo de Penalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2 Metodo de Barreira . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6 Problemas Especiais em OCR 61

6.1 O Problema de Programacao Linear (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.1.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.1.2 Fundamentos matematicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.1.2.1 Dependencia linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6.1.2.2 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.1.2.3 Posto (ranking) de uma matriz Amxn . . . . . . . . . . . . . . . . . . . . . . 66

6.1.2.4 Solucoes basicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.2.5 Pontos e conjuntos de pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.2.6 Teoremas importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.1.3 Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.1.3.1 Formulacao do problema de PL . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.1.3.2 Hipoteses preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.1.3.3 Reducao de uma solucao compatıvel qualquer para uma solucao compatıvelbasica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.1.3.4 Algumas definicoes e notacoes . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.1.3.5 Formulacao do metodo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.1.3.6 Solucoes ilimitadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.1.3.7 Condicoes de otimizacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.1.3.8 Alternativa otima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.1.3.9 Pontos extremos e solucoes compatıveis basicas . . . . . . . . . . . . . . . . . 84

6.1.3.10 Solucao compatıvel basica inicial . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.2 O Problema de Programacao Quadratica (PQ) . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.2.1 Eliminacao de restricoes de igualdade . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.2.2 Problemas de Programacao Linear Complementar (PLC) . . . . . . . . . . . . . . . . 90

6.2.3 Algoritmo de Lemke para a solucao do PLC . . . . . . . . . . . . . . . . . . . . . . . . 91

6.2.3.1 Esquema de Pivoteamento de Lemke . . . . . . . . . . . . . . . . . . . . . . . 91

7 O Problema Geral de Programacao Nao-Linear (PNL) 95

7.1 Metodo de Programacao Linear Sequencial (PLS) . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.2 Metodo dos Centros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

7.3 Metodo das Direcoes Viaveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7.3.1 Solucao Inicial Viavel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

7.3.2 Restricoes de Igualdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

7.4 Metodo do Gradiente Reduzido Generalizado (GRG) . . . . . . . . . . . . . . . . . . . . . . . 105

7.5 Metodo de Programacao Quadratica Sequencial (PQS) . . . . . . . . . . . . . . . . . . . . . . 107

7.5.1 Problema P1 (problema original) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.5.2 Problema P2 (subproblema de PQS relativo a P1) . . . . . . . . . . . . . . . . . . . . 108

SUMARIO 1

8 Analise de Sensibilidade 1118.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118.2 Metodos de Analise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

8.2.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118.2.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1128.2.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

8.3 Comparacao entre os Metodos de Analise de Sensibilidade . . . . . . . . . . . . . . . . . . . . 1138.4 Aplicacao dos Metodos de Analise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . 114

8.4.1 Analise Linear Elastica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1148.4.1.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1148.4.1.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158.4.1.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

8.4.2 Problema de Autovalores e Autovetores . . . . . . . . . . . . . . . . . . . . . . . . . . 1168.4.2.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1168.4.2.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1178.4.2.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

8.4.3 Problema de Analise Nao Linear Estatica . . . . . . . . . . . . . . . . . . . . . . . . . 1188.4.3.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1198.4.3.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1198.4.3.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

8.4.4 Problemas de Carga Limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1208.4.4.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1208.4.4.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1218.4.4.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

8.4.5 Problemas de Fluxo Termico Transiente . . . . . . . . . . . . . . . . . . . . . . . . . . 1228.4.5.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.4.5.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.4.5.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

8.4.6 Problemas de Analise Dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1248.4.6.1 Metodo das Diferencas Finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.4.6.2 Metodo Direto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.4.6.3 Metodo Adjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

A Exemplo de Analise de Sensibilidade 129

2 SUMARIO

Parte I

Teoria e Algoritmos

3

Capıtulo 1

Introducao

Programacao Matematica (PM) e a area da Matematica que trata dos problemas de minimizacao ou oti-mizacao de funcoes. Ela se ocupa tanto do tratamento teorico do problema quanto do desenvolvimento dealgoritmos para a sua solucao.

A funcao a ser minimizada ou otimizada num problema de PM e denominada de funcao objetivo, a qualpode ter um numero qualquer de variaveis, que por sua vez, podem estar sujeitas a restricoes de igualdadee/ou desigualdade. Restricoes de desigualdade que definem limites inferior e superior para as variaveis saochamadas de restricoes laterais.

Existem varios problemas particulares de PM. No problema geral as variaveis sao contınuas. Quando asvariaveis so podem assumir valores inteiros, diz-se que o problema e de Programacao Inteira (PI). Esse tipode problema nao sera tratado neste texto.

Os problemas de PM podem ainda ser classificados como de Programacao Restrita (PR) ou OtimizacaoCom Restricoes (OCR) e Programacao Irrestrita (PI) ou Otimizacao Sem Restricoes (OSR).

Nos problemas de OCR, quando a funcao objetivo e as restricoes do problema sao funcoes lineares dasvariaveis e todas as variaveis sao sujeitas a restricoes laterais do tipo ”maior ou igual a zero”, o problema echamado de problema padrao de Programacao Linear (PL).

Quando a funcao objetivo e quadratica e as restricoes do problema de OCR sao restricoes lineares dedesigualdade e todas as variaveis sao do tipo ”maior ou igual a zero”, o problema e chamado de problemapadrao de Programacao Quadratica (PQ). Esses problemas podem ser escritos na forma equivalente deproblemas de Programacao Linear Complementar (PLC).

No caso geral de problemas de OCR onde a funcao objetivo e as restricoes sao nao lineares o problema edito de Programacao Nao Linear (PNL).

Os algoritmos de PNL sao classificados em algoritmos de ordem zero, de primeira e de segunda ordem,dependendo se eles usam ou nao derivadas parciais de primeira e segunda ordem da funcao objetivo edas restricoes, respectivamente, nas suas operacoes numericas. O estudo das tecnicas de obtencao dessasderivadas para os diversos problemas ganhou a denominacao de analise de sensibilidade.

Problemas particulares de PM apresentam algoritmos especıficos para a sua solucao. Assim, o algoritmoSimplex tem sido usado para a solucao de problemas de PL, o algoritmo de Lemke tem sido aplicado nasolucao de problemas de PLC, dentre outros.

Varios problemas de Engenharia, quando adequadamente formulados, recaem em problemas de PM.Dentre esses problemas podem-se citar a analise de estruturas por elementos finitos com comportamentonao linear; a identificacao de parametros ou retro-analise; a analise limite de estruturas; as otimizacoestopologica, de dimensoes e de forma de estruturas; o problema de contato entre corpos elasticos; e a analisede confiabilidade.

Devido a crescente importancia da PM na engenharia, diversos programas comerciais de analise de estru-turas por elementos finitos ja incorporam algoritmos de PM em seus codigos. Entre eles estao o NASTRANe o ANSYS. Existem ainda programas comerciais especializados em resolver problemas de PM nos quaiso usuario tem que fornecer a funcao e as restricoes explicitamente. Dentre os mais conhecidos nessa areacitam-se LANCELOT [1], Lingo [5], Minos [6] e DOT.

5

6 CAPITULO 1. INTRODUCAO

1.1 O Problema Geral de Programacao Matematica

O problema geral de Programacao Matematica (PM) pode ser representado matematicamente como:min f (x) x ∈ ℜn

s.t. hk (x) = 0 k = 1 . . .mcl (x) ≤ 0 l = 1 . . . pxli ≤ xi ≤ xu

i i = 1 . . . n

(1.1)

e pode ser descrito nos seguintes termos: minimizar a funcao f(x), dita funcao objetivo, de n variaveiscontidas no vetor x, designado de vetor das variaveis de projeto, sendo que as n variaveis estao submetidas(“s.t.”, subjected to, em ingles) a m restricoes de igualdade hk(x), p restricoes de desigualdade cl(x) e n res-tricoes laterais do tipo maior ou igual a um limite inferior, xl

i (l, do ingles lower limit) e um limite superiorxui (u, do ingles upper limit).

O problema geral gera varios sub-problemas tais como:

1. Problema de Otimizacao Sem Restricoes (OSR), quando nenhuma das restricoes esta presente.

2. Problema padrao de Programacao Linear (PL), quando a funcao objetivo e as restricoes sao funcoeslineares das variaveis de projeto, as variaveis de projeto sao maiores ou iguais a zero e as restricoeslaterais sao do tipo maior ou igual a zero.

3. Problema padrao de Programacao Quadratica (PQ), quando a funcao objetivo e uma funcao quadratica,as variaveis de projeto sao maiores ou iguais a zero e as restricoes sao de desigualdade e sao funcoeslineares das variaveis de projeto.

4. Problema de Programacao Linear Complementar (PLC) que surge da aplicacao das condicoes de otimoao problema padrao de Programacao Quadratica.

1.2 Exemplo de Aplicacao em Otimizacao de Estruturas

Para os engenheiros de projeto, sejam eles civis, mecanicos, aeronauticos ou navais, a aplicacao classica doproblema de Programacao Matematica e a otimizacao de estruturas.

1.2.1 Trelica Plana de Duas Barras

Para se entender a importancia do estudo da otimizacao estrutural, considerar o problema apresentado naFigura 1.1.

Projetar a trelica apresentada na Figura 1.1, em funcao de r2 e H, raio da secao transversal da barra 2e altura da trelica respectivamente, de tal forma que ela apresente um volume mınimo e que as tensoes nasbarras sejam inferiores as tensoes de escoamento e de flambagem.

• Informacoes conhecidas:

– r1 (raio da secao transversal da barra 1)

– L (dimensao horizontal da trelica)

– P (forca vertical aplicada)

– E (modulo de elasticidade)

– σY (tensao de escoamento)

• Informacoes a serem obtidas (variaveis de projeto):

1.2. EXEMPLO DE APLICACAO EM OTIMIZACAO DE ESTRUTURAS 7

r

a

P

H

seçãotransversal

L

1

2

Figura 1.1: Trelica Plana de Duas Barras.

– r2 (raio da secao transversal da barra 2)

– H (dimensao vertical da trelica)

• Informacoes adicionais (restricoes laterais):

– 0.4 ≤ r2 ≤ 1 (intervalo de variacao de r2)

– 1 ≤ H ≤ 7 (intervalo de variacao de H)

Em funcao das variaveis r2 e H, o volume (V ) da barra 2 e dado por:

V = A2L2 (1.2)

onde, de acordo com a Figura 1.1, tem-se:

L2 =√H2 + L2

A2 = πr22

Portanto, o volume da barra 2 pode ser expresso como:

V (r2,H) = πr22√H2 + L2 (1.3)

Porem, as tensoes nas barras (σ) nao devem exceder os valores da tensao de escoamento do material (σY )e os da tensao crıtica de Euler (σCR), ou seja, deve-se ter: σ ≤ σY

eσ ≤ σCR

Calculo das Tensoes nas Barras

Fazendo-se o equilıbrio das forcas horizontais (vide Figura 1.2), tem-se:


a

PN1

N2

y

x

Figura 1.2: Esforcos nas Barras da Trelica.

N1 = N2 cos(α) (1.4)

onde

sen(α) =H√

H2 + L2

e

cos(α) =L√

H2 + L2

Na direcao vertical deve-se ter:

P = N2 sen(α) (1.5)

Combinando-se as Equacoes (1.4) e (1.5) chega-se a:

N1 = PL

H(1.6)

e

N2 = P

√H2 + L2

H(1.7)

Portanto:

σ1 =N1

A1=

PL

Hπr21

=PL

Hπr21(1.8)

e

σ2 =N2

A2=

P

√H2 + L2

Hπr22

=P√H2 + L2

Hπr22(1.9)

Como N1 < N2, tem-se que, a tensao crıtica e σ2.


Tensao Crıtica de Euler

σCR =π2EI

L2eA

(1.10)

onde Le e o comprimento efetivo da barra, I = πr4

4 e A = πr2, logo:

σCR =π2Er2

4L2e

Formulacao do Problema

Com as expressoes acime pode-se definir as restricoes como:

g1(r2,H) = σ1 − σe ≤ 0 ou g1(r2, H) =PL

Hπr21σe− 1 ≤ 0

g2(r2,H) = σ2 − σe ≤ 0 ou g2(r2,H) =P√L2 +H2

Hπr22σe− 1 ≤ 0

g3(r2, H) = σ2 − σCR ≤ 0 ou g3(r2,H) =4P(L2 +H2

)3/2Hπ3r42

− 1 ≤ 0

O problema proposto pode ser formulado da seguinte maneira:

min V (r2,H)

s.t. g1(r2,H) ≤ 0g2(r2,H) ≤ 0g3(r2,H) ≤ 0

0.4 ≤ r2 ≤ 11 ≤ H ≤ 7

(1.11)

Resultados

O problema proposto em 1.11 foi resolvido para diferentes dados de entrada conforme a tabela 1.1.

dados resultados restricoesfuncao objetivo modo de falha

σe r1 E r2 H g1 g2 g3350 0.3 2000 0.52012 2.0210 0 −0.24983 0 1.9164 1 e 3350 0.4 2000 0.49219 1.1368 0 0 −0.32885 1.1523 1 e 2350 0.5 2000 0.50718 1 −0.27244 0 −0.44856 1.1429 2500 0.3 2000 0.46664 1.4147 0 −0.28396 0 1.1852 1 e 3350 0.3 20000 0.45049 2.021 0 0 −0.8223 1.4376 1 e 2350 0.4 20000 0.49219 1.1368 0 0 −0.93288 1.1523 1 e 2350 0.5 20000 0.50718 1 −0.27243 0 −0.94486 1.1429 2500 0.3 20000 0.4 1.4147 0 −0.02549 −0.81478 0.8708 1

Tabela 1.1: Resultados.


r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(a) σE = 350 e r1 = 0.3

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(b) σE = 350 e r1 = 0.4

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(c) σE = 350 e r1 = 0.5

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(d) σE = 500 e r1 = 0.3

Figura 1.3: Curvas para o modulo de eslasticidade igual a 2000.


r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(a) σE = 350 e r1 = 0.3

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(b) σE = 350 e r1 = 0.4

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(c) σE = 350 e r1 = 0.5

r2

H

0.4 0.5 0.6 0.7 0.8 0.9 11

2

3

4

5

6

7

(d) σE = 500 e r1 = 0.3

Figura 1.4: Curvas para o modulo de eslasticidade igual a 20000.

Capıtulo 2

Fundamentos de Otimizacao semRestricoes (OSR)

2.1 Serie de Taylor

A aproximacao de uma funcao f(x) de uma variavel, em torno de um ponto x0, por meio da serie de Taylore um recurso utilizado em Programacao Matematica, e sera aqui apresentado para facilitar a compreensaode varias passagens matematicas e demonstracoes ao longo desse capıtulo.

A serie de Taylor, designada pela funcao s(x), e dada pela seguinte expressao:

s (x) ≈ f (x0) +1

1!

df (x)

dx

∣∣∣∣x=x0

(x− x0) +1

2!

d2f (x)

dx2

∣∣∣∣x=x0

(x− x0)2+ · · · (2.1)

A serie acima foi truncada no termo de segunda ordem (assim denominado por conter a segunda derivadade f) e apresenta o seguinte termo generico de ordem n:

1

n!

dnf (x)

dxn

∣∣∣∣x=x0

(x− x0)n

(2.2)

A aproximacao e tanto melhor quanto mais proximo x estiver de x0 e quanto mais termos a serie contiver.E possıvel observar as seguintes propriedades da funcao aproximadora s(x) no ponto x0:

1. s (x0) = f (x0)

2.ds (x)

dx

∣∣∣∣x=x0

=df (x)

dx

∣∣∣∣x=x0

3.d2s (x)

dx2

∣∣∣∣x=x0

=d2f (x)

dx2

∣∣∣∣x=x0

4. E assim sucessivamente ate o termo de ordem n,

dns (x)

dxn

∣∣∣∣x=x0

=dnf (x)

dxn

∣∣∣∣x=x0

A generalizacao da serie de Taylor para o caso de uma funcao de n variaveis, f(x), e dada por:

s (x) ≈ f (x0) + [g(x)]t∣∣∣x=x0

(x− x0) +1

2(x− x0)

tH(x)|x=x0

(x− x0) + · · · (2.3)

onde g(x) e o vetor gradiente de f(x), cujos componentes sao obtidos da seguinte forma:

gi(x) =∂f(x)

∂xi, i = 1 · · ·n (2.4)

13

14 CAPITULO 2. FUNDAMENTOS DE OTIMIZACAO SEM RESTRICOES (OSR)

e H(x) e a matriz Hessiana1 de f(x), cujos elementos sao dados por:

hij(x) =∂2f(x)

∂xi∂xj, i, j = 1 · · ·n (2.5)

Exemplo 2.1 – Serie de Taylor para Funcao de Uma Variavel

Aproximar f(x) = sin(x) em torno do ponto x0 = π4 .

Solucao:

As derivadas de f(x) sao:

df

dx= cos (x)

d2f

dx2= − sin (x)

d3f

dx3= − cos (x) (2.6)

Utilizando-se a Equacao (2.1), a expansao de primeira ordem para sin(x) em torno do ponto x0 = π4 e dada

por:

s1(x) = sin (x) ≈ sin(π4

)+ cos

(π4

)(x− π

4

)(2.7)

As expansoes de segunda e terceira ordem sao dadas, respectivamente, por:

s2(x) = s1(x)−1

2sin(π4

)(x− π

4

)2(2.8)

s3(x) = s2(x)−1

6cos(π4

)(x− π

4

)3(2.9)

A Figura 2.1 ilustra as aproximacoes em serie de Taylor de primeira, segunda e terceira ordens, respec-tivamente, da funcao sin(x).

�

Exemplo 2.2 – Serie de Taylor para Funcao de Duas Variaveis

Obter a aproximacao de f(x) = sin(x1) sin(x2) em torno do ponto x0 ={

π4 ,

π4

}t.

Solucao:

O vetor gradiente e a matriz Hessiana de f(x) no ponto x0 ={

π4 ,

π4

}tsao obtidos utilizando-se as

Equacoes (2.4) e (2.5), ou seja:

g(x) =

∂f(x)∂x1

∂f(x)∂x2

=

cos (x1) sin (x2)

sin (x1) cos (x2)

=

12

12

(2.10)

1A denominacao “Hessiana” e uma homenagem ao matematico alemao Ludwig Otto Hesse, que trabalhou no desenvolvimentoda teoria das Funcoes Algebricas e dos Invariantes.

2.1. SERIE DE TAYLOR 15

−pi/4 0 pi/4 pi/2 3*pi/4−1.5

−1

−0.5

0

0.5

1

1.5

2

x

appr

oxim

ação

de

sin(

x)

sin(x)s1(x)s2(x)s3(x)

pi/4

Figura 2.1: Aproximacoes em Serie de Taylor da Funcao sin(x).

H(x) =

∂2f(x)∂x2

1

∂2f(x)∂x1∂x2

∂2f(x)∂x2∂x1

∂2f(x)∂x2

2

=

− sin (x1) sin (x2) cos (x1) cos (x2)

cos (x1) cos (x2) − sin (x1) sin (x2)

=

−12

12

12 − 1

2

(2.11)

Substituindo-se as Equacoes (2.10) e (2.11) na Equacao (2.3) chega-se a:

s (x) = 12 +

12

12

t x1 − π

4

x2 − π4

+ 12

x1 − π4

x2 − π4

t −1/2 1/2

1/2 −1/2

x1 − π4

x2 − π4

= x1

2 −π4 + x2

2 + 12 −

x12

4 + x1x2

2 − x22

4

(2.12)

que e a aproximacao de segunda ordem para a funcao sin(x1) sin(x2). Calculando-se os valores da funcao e de

sua aproximacao no ponto{

π5 ,

3π10

}t, que representa uma variacao de 20% de x0, obtem-se f(π5 ,

3π10 ) = 0.47553

e s(π5 ,3π10 ) = 0.47533, respectivamente. A funcao s(x) apresentou uma otima aproximacao de f(x) com um

erro em torno de 0.05%, o que e bastante razoavel.�


2.2 Condicoes de Mınimo no Problema de OSR

2.2.1 Condicao de Primeira Ordem

A condicao de primeira ordem para que o vetor x seja um mınimo local x∗ da funcao f(x) e dada por:

g (x)|x=x∗ = g (x∗) = 0 (2.13)

ou seja, o vetor gradiente g(x) deve ser nulo em x = x∗.

Para provar essa condicao, considerar s(x) uma aproximacao de f(x) em serie de Taylor, em torno dex∗, ate o termo de segunda ordem:

s (x) ≈ f (x∗) + [g(x∗)]t(x− x∗) +

1

2(x− x∗)

tH (x∗) (x− x∗) (2.14)

Considerando-se que x esteja bem proximo de x∗ de tal maneira que o modulo de x − x∗ seja muitopequeno (∥x− x∗∥ ≪ ϵ), onde os elementos do vetor ϵ sao numeros muito menores que a unidade), osegundo termo da serie de Taylor, ou seja, o que contem o vetor g(x∗) predomina sobre o terceiro termo quecontem a matriz Hessiana H(x) e um termo quadratico em (x− x∗).

Num ponto de mınimo local, f(x) deve ser maior do que f(x∗) para um valor arbitrario de x em tornode x∗. Representando-se f(x) por sua aproximacao s(x) e desprezando-se o termo de segunda ordem emrelacao ao de primeira ordem tem-se:

f (x)− f (x∗) ≈ s (x)− f (x∗) ≈ [g(x∗)]t(x− x∗) (2.15)

ou ainda:

df (x∗) ≈ [g(x∗)]tdx (2.16)

onde df(x∗) e o incremento de f(x) em x∗ e dx o incremento de x∗. O produto interno que define df(x∗)pode ser reescrito usando seus modulos e o co-seno do angulo α entre os dois vetores, ou seja:

df (x∗) ≈ ∥g (x∗)∥ ∥dx∥ cos(α) (2.17)

Fixando-se o modulo de dx e deixando-se α variar, df(x∗) sera uma funcao apenas de α, ou seja:

df (α) ≈ ∥g (x∗)∥ ∥dx∥ cos(α) (2.18)

No mınino local deve-se ter, para arbitrario α:

df (α) ≈ ∥g (x∗)∥ ∥dx∥ cos(α) ≥ 0 (2.19)

A expressao acima representa o acrescimo da funcao f(x) a partir de x∗ para um passo de modulo ∥dx∥na direcao que forma um angulo α com o vetor g(x∗). Como cos(α) e arbitrario e o modulo do vetor dx naexpressao acima e uma constante pre–fixada, a unica possibilidade de se garantir que a Equacao (2.19) sejasatisfeita e:

∥g (x∗)∥ = 0 (2.20)

ou:

g (x∗) = 0 (2.21)

que e conhecida como a condicao de mınimo local de primeira ordem.

2.2. CONDICOES DE MINIMO NO PROBLEMA DE OSR 17

2.2.2 Condicao de Segunda Ordem

Se o ponto x∗ for um mınimo, ele devera satisfazer a condicao de primeira ordem, g (x∗) = 0 (Eq. 2.21)e, portanto, a serie de Taylor s(x) em torno de x∗ pode ser reescrita desprezando-se o segundo termo etruncada no terceiro termo, ou seja:

s (x) ≈ f (x∗) +1

2(x− x∗)

tH(x∗) (x− x∗) (2.22)

Analogamente as Equacoes (2.15) e (2.16), a Equacao (2.22) pode ser escrita como:

df (x∗) ≈ 1

2(x− x∗)

tH(x∗) (x− x∗) (2.23)

Para que x∗ seja um mınimo local, a Equacao (2.22) deve satisfazer:

df (x∗) ≥ 0 (2.24)

ou:

(x− x∗)tH(x∗) (x− x∗) ≥ 0 (2.25)

A restricao acima representa a condicao de segunda ordem para um mınimo local x∗ e significa que amatriz Hessiana de f(x), em x∗, deve ser positiva semi–definida.

Exemplo 2.3 – Exercıcio 2.1 de Nocedal & Wright [7] (Pag. 27)Calcular o gradiente ∇f(x) e a Hessiana ∇2f(x) da funcao de Rosenbrock

f(x) = 100(x2 − x2

1

)2+ (1− x1)

2.

Mostrar que x∗ = {1, 1}t e um ponto de mınimo local desta funcao, e que a matrix Hessiana neste ponto epositiva definida.

Solucao:

∇f(x) =

−400(x2 − x1

2)x1 − 2 + 2x1

200x2 − 200x21

∇2f(x) =

1200x12 − 400x2 + 2 −400x1

−400x1 200

A condicao de mınimo local, dada pela Equacao (2.13), requer que o gradiente no ponto x∗ = {1, 1}t seja

nulo. Desta forma:

∇f(x∗) = g(x∗) =

{00

}satisfazendo-se assim a condicao de mınimo de primeira ordem.A Hessiana de f(x) avaliada em x∗ e:

∇2f(x∗) = H(x∗) =

[802 −400−400 200

]Sabe-se que uma matriz A e positiva definida se todos os seus autovalores forem positivos, ou seja, se todosos valores de λ que satizfazem a equacao

|A− λI| = 0

forem positivos.


Usando-se os valores de H(x∗) na equacao acima tem-se:∣∣∣∣[ 802 −400−400 200

]− λ

[1 00 1

]∣∣∣∣ = ∣∣∣∣[ 802− λ −400−400 200− λ

]∣∣∣∣ = λ2 − 1002λ+ 400 = 0

Obtendo-se os valores λ1 = 0.39936 e λ2 = 1001.6. Como λ1 > 0 e λ2 > 0 pode-se concluir que H(x∗) epositiva definida.

Outra maneira de se testar se a matriz A e positiva definida envolve o calculo de n determinantes, ouseja:

A1 =∣∣ a11

∣∣A2 =

∣∣∣∣ a11 a12a21 a22

∣∣∣∣A3 =

∣∣∣∣∣∣a11 a12 a13a21 a22 a23a31 a32 a33

∣∣∣∣∣∣...

An =

∣∣∣∣∣∣∣∣∣∣∣

a11 a12 a13 · · · a1na21 a22 a23 · · · a2na31 a32 a33 · · · a3n...

an1 an2 an3 · · · ann

∣∣∣∣∣∣∣∣∣∣∣A matrix A sera positiva definida se todos os valores de A1, A2, A3, . . . , An forem positivos.Os determinantes das submatrizes quadradas de H sao:

H1 =∣∣ 802

∣∣ = 802 > 0

H2 =

∣∣∣∣ 802 −400−400 200

∣∣∣∣ = 802× 200− (−400)× (−400) = 400 > 0

Entao a matrix H e positiva definida e, portanto, o ponto x∗ = {1, 1}t corresponde a um ponto de mınimode f(x).

�

Capıtulo 3

Metodos de Otimizacao semRestricoes (OSR)

Neste capıtulo, estudaremos a minimizacao de uma funcao sem a presenca de restricoes, conhecida comominimizacao irrestrita, isto e, resolvemos o problema

min f (x) , x ∈ ℜn (3.1)

Em geral, os algoritmos de otimizacao sao procedimentos iterativos e geram uma sequencia de pontos ondeo valor da funcao no novo ponto decresce em relacao ao ponto anterior. Muitos algoritmos de otimizacaoirrestrita tem em comum a seguinte estrutura:

Escolha ϵ > 0, x0 e faca k = 0Enquanto ∥∇f

(xk)∥ ≥ ϵ

Passo 1: Encontre dk

Passo 2: Determine αk de modo que f(xk + αkd

k)< f

(xk)

Passo 3: Faca xk+1 = xk + αkdk

Fim enquantox∗ = xk

No passo 1, para um dado ponto xk, determina-se a direcao de descida, ou direcao de busca. No passo2 e realizada uma busca unidimensional para encontrar o tamanho do passo αk. No passo 3 um novo pontoe calculado atraves da formula de recorrencia xk+1 = xk + αkd

k e o processo se repete ate que o criterio deparada seja satisfeito.

Este capıtulo se divide em duas partes, a primeira, apresentada na secao 3.1, estuda os metodos de buscaunimensional para determinacao do tamanho do passo αk. A seguda parte, apresentada na secao 3.2, estudaos metodos de determinacao da direcao de busca dk.

3.1 Metodos de Busca Unidimensional

A minimizacao unidimensional surge como um subproblema do na maioria do metodos de otimizacao mul-tidimensionais. Precisa-se obter o valor αk, da variavel α, para que se possa avancar para o proximo pontoxk+1. Vale salientar que a incognita α e um escalar e, portanto, essa tarefa nao e das mais complexas, poisconsiste em se buscar o mınimo de uma funcao de uma variavel f(α). Essa tarefa e conhecida na literaturatecnica como busca unidimensional (line search, em ingles)1.

Os metodos de busca unidimensional apresentados nesse capıtulo sao: de Passo Constante ou Incremental;Armijo; Bissecao; Secao (ou Razao) Aurea; Ortogonalidade; e Secante.

1Em algumas referencias, o termo line search e traduzido como “busca linear” ou “busca unidirecional”.

19

20 CAPITULO 3. METODOS DE OTIMIZACAO SEM RESTRICOES (OSR)

3.1.1 Metodo de Passo Constante ou Incremental

Ometodo de passo constante ou incremental e o mais simples da famılia dos metodos de busca unidimensionale surgiu associado ao metodo de direcao de busca univariante, secao 3.2.1, tambem o mais primitivo da famıliados metodos de direcao de busca.

A ideia basica deste metodo de passo constante consiste na escolha de um incremento ∆α que sera usadona expressao:

αi+1 = αi +∆α, i = 0, . . . , n (3.2)

O valor de α0 na expressao (3.2) deve ser igual a zero e o numero de iteracoes deve ser o necessario parase obter o mınimo de f (α). A cada novo valor de α na iteracao i+ 1, f (α) deve ser avaliada para saber seseu valor e menor do que o encontrado na iteracao anterior. Caso nao seja, faz-se αk = αi, i.e., o valor de αque minimiza f (α) foi encontrado e e colocado em αk, para se avancar para xk+1.

O algoritmo de passo incremental adota ∆α constante nas duas primeiras iteracoes. A partir da terceiraiteracao o valor de ∆α vai sendo dobrado em relacao ao valor anterior. Os incrementos para cada novaiteracao, a partir da terceira, passam a ser 2∆α, 4∆α, 8∆α, · · · . Espera-se com isso acelerar o processoiterativo e diminuir o numero de avaliacoes de f (α). Como no caso de ∆α constante, o processo iterativo einterrompido assim que se obtem um αi+1 para o qual f (α) e maior do que na iteracao anterior.

A escolha de ∆α e uma tarefa delicada, pois o incremento tem que ser compatıvel com a ordem degrandeza da variavel x. Se a variavel x for uma dimensao em mm o valor do incremento ∆α deve serdiferente daquele para o qual a variavel x seja dada em Km. A precisao de αk depende do valor relativo de∆α em relacao ao valor de αk.

3.1.2 Metodo de Armijo

Esse metodo, assim como os de passo constante ou incremental, e chamado de metodo de busca inexata, poisnao se preocupa em obter o valor exato de α que minimiza f (α) e sim caminhar na direcao de decrescimoate que nao seja mais possıvel com o incremento ∆α escolhido. O metodo faz uso do conceito de “taxa dedecrescimo” m. O valor de α pode ser incrementado como no metodo de passo constante ou incremental. Adeterminacao de αk se da quando a seguinte restricao e violada:

f(xk + αdk) ≥ r(α) = f |α=0 −mα (3.3)

onde αk e o valor de α para o qual a funcao f e maior do que o valor da reta r que passa por f(xk) (quecorresponde ao valor de f para α = 0) e tem inclinacao −m. A taxa de decrescimo m deve ser um valorentre 0.2 e 0.4 dependendo do problema. Recomenda-se o valor m = 0.3.

3.1.3 Metodo da Bissecao

O metodo da Bissecao objetiva encontrar o mınimo de f (α) no intervalo ou regiao de busca 0 ≤ α ≤ β. Casoo mınimo nao esteja na regiao de busca pre-definida, o metodo converge para αk = 0 ou para αk = β. Paraa busca do mınimo, o intervalo e subdividido em dois intervalos iguais, pelo ponto α = β/2. Cada um dessesdois novos intervalos e, por sua vez, subdividido em outros dois intervalos iguais e assim sucessivamente. Emcada nova divisao, um intervalo e escolhido para continuar a busca do mınimo e o outro e descartado. Parase escolher o intervalo descartado, calcula-se f no ponto medio dos dois intervalos. O intervalo descartado eaquele que apresenta o maior valor de f no seu ponto medio. A ideia do metodo e reduzir progressivamentea regiao de busca em torno do mınimo. A precisao de αk depende do criterio de convergencia adotado parase interromper as iteracoes.

3.1.4 Metodo da Secao Aurea (Golden Section, em ingles)

Para se explicar o conceito da razao aurea, deve-se introduzir, inicialmente, a sequencia de Fibonacci. Essasequencia, denominada FN , gera numeros que comecam com N = 0 e F0 = 1 e segue com N = 1 e F1 = 1.A partir daı utiliza-se a seguinte formula de recorrencia:

3.1. METODOS DE BUSCA UNIDIMENSIONAL 21

aak

f( )a

r( )a

m

f( )a

Figura 3.1: Metodo da Armijo.

FN = FN−1 + FN−2 (3.4)

Com os numeros de Fibonacci FN , pode-se definir a razao de Fibonacci, RF , da seguinte forma:

RF =FN−1

FN(3.5)

A Tabela 3.1 mostra uma sequencia de numeros e razoes de Fibonacci desde N = 0 ate N = 10.

N FN RF

0 1 –1 1 1.00002 2 0.50003 3 0.66674 5 0.60005 8 0.62506 13 0.61547 21 0.61908 34 0.61769 55 0.6182

10 89 0.6180

Tabela 3.1: Sequencia de Fibonacci para N = 0 ate N = 10.

E interessante observar que a razao de Fibonacci converge para um determinado valor, proximo de 0.618,que se denomina razao aurea (RA). Esse numero aparece outras vezes nas relacoes da natureza, como porexemplo: o numero π e o numero Neperiano e. Varios artistas, como Leonardo da Vinci, usavam em seusquadros essa razao entre as dimensoes por acha-la harmonica. Da Vinci identificou tambem que essa razaopoderia ser encontrada entre dimensoes do corpo humano, como a razao entre a distancia da sola do pe aoumbigo e a altura total do indivıduo.


O metodo da Secao Aurea apresenta uma ideia semelhante ao da Bissecao. A diferenca esta na razaoutilizada para reduzir o intervalo de busca. No metodo da Bissecao essa razao e 0.5, enquanto que no metododa Secao Aurea utiliza-se a razao aurea. A partir do comprimento do intervalo de busca inicial β, dois novospontos sao determinados:

α1d = RAβ e α1e = (1−RA)β

que definem dois novos intervalos, 0 ≤ α ≤ α1d e α1e ≤ α ≤ β. Qual intervalo deve ser descartado naproxima iteracao? Para se tomar essa decisao, deve-se calcular f (α1d) e f (α1e); o ponto α correspondenteao maior valor da funcao f define este intervalo a ser descartado e, consequentemente, os novos limites dabusca. Se for α1d, o novo intervalo devera ser 0 ≤ α ≤ α1d, se for α1e , o novo intervalo sera α1e ≤ α ≤ β,conforme ilustrado na Figura 3.2. Os subscritos “d” e “e” caracterizam os pontos do intervalo localizadosna “direita” e na “esquerda”, respectivamente.

0 b

a1d=RAba b1 =(1-R )e A

Figura 3.2: Intervalos de Busca do Metodo da Secao Aurea.

A vantagem de se usar a razao aurea RA para dividir os intervalos e nao qualquer outra razao, esta nofato desta razao economizar uma avaliacao da funcao f por divisao de intervalo. Isso se deve a coincidenciaentre um dos pontos novos e um ponto antigo de extremidade de intervalo quando se usa a razao aurea.

Para esclarecer esse ponto, considere uma razao qualquer R no procedimento acima e que o segundointervalo α1e ≤ α ≤ β, tenha sido escolhido, conforme ilustrado na Figura 3.3.

O comprimento do novo intervalo e dado por:

β − α1e = β − (1−R)β = Rβ (3.6)

Como o ponto inicial do intervalo e α1e e seu comprimento Rβ, os dois novos pontos seriam:

α2d = α1e +R (Rβ) e α2e = β −R (Rβ) = (1−R2)β (3.7)

Para que o novo ponto α2e coincida com o antigo ponto α1d descartado, deve-se ter:

Rβ = (1−R2)β (3.8)

ou:

R2 +R− 1 = 0 (3.9)

com raızes iguais a:

R1 =−1 +

√5

2= 0.61803 . . . (3.10)

3.1. METODOS DE BUSCA UNIDIMENSIONAL 23

0 ba1d

a1e

a1e

a2e

a2d

a2d

b

a1e

a3e

a3d

a2d

a3e

a4d

a4e

a3e

a4d

a5e

a5d

a3e

a5d

a6e a6

d

Figura 3.3: Escolha dos Intervalos de Busca no Metodo da Secao Aurea.


R2 =−1−

√5

2= −1.61803 . . . (3.11)

Desprezando-se a raız negativa, o valor de R para poupar uma avaliacao de f em cada subdivisao dosintervalos e exatamente igual a razao aurea, i.e., RA = 0.61803 . . .

A precisao de αk depende, como nos metodos anteriores, do criterio de convergencia adotado no processoiterativo.

3.1.5 Metodo da Ortogonalidade

Sejam x(α) = xk + αdk, o proximo ponto para um determinado valor de α, e f [x(α)] o valor da funcao fnesse ponto. Derivando-se f [x(α)] em relacao a α, obtem-se:

df [x(α)]

dα=

∂f(x)

∂x

dx

dα= {g [x(α)]}t dk (3.12)

O valor αk de α que minimiza f [x(α)] a partir de xk na direcao dk e obtido da condicao:

df(α)

dα= 0 (3.13)

ou entao:

[g(xk + αdk)

]tdk = 0 (3.14)

O significado geometrico da Equacao (3.14) e que o valor αk de α que minimiza f (α), e o mesmo quetorna o vetor gradiente g (α) ortogonal ao vetor dk. Para se obter αk numericamente, deve-se incrementarα ate que se obtenha um valor que torne o produto escalar acima nulo, segundo uma tolerancia numericapre-estabelecida. A Figura 3.4 ilustra o comportamento do metodo da ortogonalidade.

xk

dk

g[ )]ax(x

k+1

Figura 3.4: Comportamento do Metodo da Ortogonalidade.

3.2. METODOS DE DIRECAO DE BUSCA 25

3.1.6 Metodo Secante

O metodo de Newton faz uso das segundas derivadas para minimizar uma funcao f(α), ou seja:

αk+1 = αk − f ′(αk)

f ′′(αk)

Aproximando-se a segunda derivada f ′′ por:

f ′(αk)− f ′(αk−1)

αk − αk−1

pode-se obter o seguinte algoritmo:

αk+1 = αk − αk − αk−1

f ′(αk)− f ′(αk−1)f ′(αk)

o qual e conhecido como algoritmo secante. Pode-se ainda reescrever esse algoritmo da seguinte forma:

αk+1 =f ′(αk) αk−1 − f ′(αk−1) αk

f ′(αk)− f ′(αk−1)

3.2 Metodos de Direcao de Busca

Nesta secao, serao apresentados os seguintes metodos de direcao de busca: Univariante; Powell; MaximoDeclive; Fletcher–Reeves; Hestenes–Stiefel; Polak–Ribiere; e Newton-Raphson, alem dos metodos Quase-Newton: de Correcao Um; DFP e BFGS.

Os metodos Univariante e de Powell sao da famılia dos metodos de ordem zero, os de Maximo Declive,Fletcher–Reeves, Hestenes–Stiefel e Polak–Ribiere pertencem a famılia dos metodos de primeira ordem e,finalmente, o metodo de Newton-Raphson pertence a famılia dos metodos de segunda ordem. Os metodosQuase-Newton, apesar de serem efetivamente de primeira ordem, tem ambicao de funcionar como metodosde segunda ordem. Os metodos de direcao de busca define uma expressao para de obter dk. A partir daı, omınimo de f (x (α)) sera procurado ao longo da reta x (α) = xk + αdk.

3.2.1 Metodo Univariante

No metodo Univariante, a direcao de busca na iteracao k e definida por:

dk = ek, k = 1, · · · , n (3.15)

onde ek e um vetor com elementos nulos, exceto na posicao k, onde o elemento vale 1. Esse procedimentoe equivalente a modificar uma variavel de cada vez no processo iterativo, ou seja, apenas a variavel na posicaok do vetor de variaveis x, e modificada na iteracao k. Para um problema com n variaveis, se, ao final den iteracoes, a posicao x nao tiver convergido para a solucao x∗, entao um novo ciclo de iteracoes deve seriniciado com as mesmas direcoes usadas no primeiro ciclo, e assim sucessivamente ate a convergencia.

3.2.2 Metodo de Powell

O metodo Univariante e computacionalmente pouco eficiente e requer, em geral, muitas iteracoes ate asolucao. Uma maneira de acelerar esse processo e incorporar uma nova direcao de busca, denominadade movimento padrao, ao conjunto de n direcoes de busca, no final de cada ciclo iterativo formado por niteracoes. Durante os n primeiros ciclos, uma direcao padrao e incorporada, ao fim de cada ciclo, ao conjuntodas n direcoes de busca do ciclo, substituindo uma das direcoes univariantes que e descartada. Depois de nciclos, nenhuma direcao univariante deve restar no conjunto de direcoes de busca. Essas novas direcoes debusca foram propostas por Powell e sao obtidas de acordo com a expressao abaixo:


-2 -1 0 1

-2

-1

1

2

3

4

5

Ponto inicial

Ponto final

Figura 3.5: Univariante.


dj = xn − x0, j = 1, · · · ,m (3.16)

onde xn e o ponto obtido no final de cada ciclo de n iteracoes e x0 e o ponto inicial. Para cada novociclo, caso nao haja convergencia, uma nova direcao padrao e criada com esse mesmo procedimento, ou seja:ponto final menos ponto inicial.

A metodologia do metodo de Powell pode ser resumida nos seguintes passos:

1. Inicializar j = 1;

2. Realizar um ciclo de n iteracoes (com as direcoes univariantes ek, k = 1 . . . n), do ponto x0 ate o pontoxn;

3. Criar uma direcao de movimento padrao dj = xn − x0;

4. Minimizar f(x) na direcao dj , determinando-se o novo ponto x0;

5. Substituir ej por dj da seguinte forma: ei = ei+1, i = 1, · · ·n− 1; en = dj ; j = j + 1;

6. Repetir os passos de 2 a 5, enquanto j ≤ n;

7. Reinicializar as direcoes ek e voltar para o passo 1, ate que a convergencia numerica seja atingida.

3.2.2.1 Direcoes Conjugadas no Metodo de Powell

Consideracoes Iniciais

• Se um determinado metodo de minimizacao sempre encontra o mınimo de uma funcao quadratica emum numero de passos (operacoes) proporcional ao tamanho do problema (n variaveis), este metodo edito “quadraticamente convergente” [3].

• Se um metodo quadraticamente convergente e aplicado a uma funcao generica para a qual a serie deTaylor e dominada pelo seu termo quadratico, espera-se que o metodo tenha uma convergencia rapida.

• Muitos metodos quadraticamente convergentes se baseiam no conceito de “direcoes conjugadas”.

• Se uma funcao quadratica q(x), de n variaveis, e minimizada sequencialmente, uma vez em cada direcaode um conjunto de n direcoes linearmente independentes (LI) e Q–conjugadas (a definicao de Q seravista adiante), o mınimo global sera obtido em ate n passos, independentemente do ponto inicial x0.

Proposicao

Seja q(x) uma funcao quadratica dada por:

q(x) =1

2xtQ x− btx (3.17)

onde Q e uma matriz quadrada, positiva semi-definida e b um vetor. Dados dois pontos xa e xb e umadirecao de busca da, e supondo-se que ya e yb sejam, respectivamente, os mınimos de q(x) na direcao da

partindo-se de xa e xb, mostrar que as direcoes da e(ya − yb

)sao Q–conjugadas.

Demonstracao

A condicao de mınimo dessa funcao quadratica e garantida apenas pela condicao de primeira ordem,fazendo-se com que o gradiente de q(x) seja igual a um vetor nulo. A condicao de segunda ordem estapreviamente satisfeita pelo fato da matriz Q (Hessiana de q(x)) ser positiva semi-definida. Portanto:


g (x) = Q x− b = 0 (3.18)

ou:

Q x = b (3.19)

Para se obter a solucao do problema acima por meio da formula de recorrencia, parte-se de:

xk+1 = xk + αkdk, k = 0, · · · , n− 1 (3.20)

onde as direcoes de busca dk serao direcoes Q–conjugadas, ou seja:(di)tQ dj = 0, ∀i = j (3.21)

Considere-se, inicialmente, o ponto xa e a direcao de busca da. Deve-se determinar αa na expressao dadaa seguir, que e o valor de α que minimiza q (x) a partir do ponto xa na direcao da.

x(α) = xa + αda (3.22)

Uma vez obtido αa, chega-se ao ponto x(αa) que, doravante, sera denominado de ya, ou seja:

ya = xa + αada (3.23)

e, da condicao de mınimo em ya:

dq [x(α)]

dα=

∂q(x)

∂x

dx(α)

dα= {g [x(αa)]}t da = 0 (3.24)

onde:

g [x(αa)] = Q x(αa)− b (3.25)

Partindo-se de ya na direcao de da, pode-se prever que αa = 0 pois ya e um mınimo nessa direcao. Logo:

[Q (ya + 0da)− b]tda = 0 (3.26)

ou:

[Q ya − b]tda = 0 (3.27)

Considerando-se agora a minimizacao de q(x) a partir de xb, na mesma direcao da, tem-se:

x (α) = xb + αda (3.28)

Denominando-se x(αb) doravante de yb e, com raciocınio analogo ao anterior, tem-se em yb:

yb = xb + αbda (3.29)

dq [x(α)]

dα=

∂q(x)

∂x

dx(α)

dα={g[x(αb)

]}tda = 0 (3.30)

onde:

g[x(αb)

]= Q x(αb)− b (3.31)

Analogamente, partindo-se de yb na mesma direcao de da, pode-se prever que αb = 0 pois yb e ummınimo nessa direcao. Logo:

yb = xb + αbda (3.32)


[Q (yb + 0da)− b

]tda = 0 (3.33)

[Q yb − b

]tda = 0 (3.34)

Subtraindo-se as Expressoes (3.27) e (3.34), obtem-se:

(da)tQ (ya − yb) = 0 (3.35)

o que demonstra que as direcoes da e(ya − yb

)sao Q–conjugadas. A Figura 3.6 ilustra o processo

iterativo descrito acima ate as posicoes ya e yb, respectivamente.

yb

xa

xb

ya y -

ay

b

da

da

Figura 3.6: Direcoes Q–Conjugadas do Metodo Powell [3].

Se da foi criada no final de um dado ciclo como movimento padrao, as duas operacoes anteriores saoexatamente o que recomenda o metodo de Powell. A primeira operacao corresponde ao passo dado no finalde cada ciclo e a segunda corresponde ao primeiro passo de cada novo ciclo, onde a direcao de busca da,criada no final de um ciclo, e repetida no inıcio do novo ciclo.

3.2.2.2 Convergencia do Metodo de Powell

Proposicao 1

O metodo de Powell converge para o mınimo de uma funcao quadratica, q(x), de n variaveis, em umnumero finito de iteracoes, dado por (n+ 1)2.

Demonstracao

Inicia-se mostrando que o conjunto de vetores di, Q–conjugados, e linearmente independente (LI). Comodito anteriormente, dois vetores di e dj sao Q–conjugados (ou Q–ortogonais) quando:


(di)tQ dj = 0, ∀i = j (3.36)

A prova se dara por contradicao. Supor que existam αi, nao todos nulos, que satisfacam a seguinteequacao:

α0d0 + α1d1 + · · ·+ αn−1dn−1 = 0 (3.37)

Nesse caso, os vetores di sao linearmente dependentes. Pre-multiplicando-se a equacao acima por(di)tQ,

chega-se a:

αi

(di)tQ di = 0 (3.38)

uma vez que as demais parcelas se anulam porque o conjunto de vetores e Q–conjugado. Todavia, como Qdeve ser positiva semi-definida em q (x), entao:(

di)tQ di ≥ 0, logo: αi = 0

o que contradiz a hipotese inicial, de αi nao serem todos nulos, e assim o conjunto de vetores di e LI.Dessa forma, o conjunto dos n vetores di pode formar uma base para o espaco de n–dimensoes e, portanto,o vetor x∗ desse espaco, solucao do problema de minimizacao de q (x), pode ser representado nessa base por:

x∗ = α0d0 + α1d1 + · · ·+ αn−1dn−1 (3.39)

Pre-multiplicando-se ambos os lados da equacao acima por(di)tQ e considerando-se o que ja foi visto

ate o momento, obtem-se:

αi =

(di)tQ x∗

(di)tQ di

=

(di)tb

(di)tQ di

(3.40)

Conclui-se portanto, que, quando se tem um conjunto de n vetores Q–conjugados, pode-se obter x∗

usando a expressao (3.39) e com os valores de αi calculados segundo (3.40) a partir da matriz Q, do vetorb e do conjunto de vetores di, como indicado.

A solucao x∗ pode ser vista como uma aplicacao da formula geral de recorrencia dos metodos de OSR,partindo-se de x0 = 0 e indo-se, sucessivamente, aos pontos x1, x2, · · · , ate o ponto xk+1, ou seja:

xk+1 = α0d0 + α1d1 + · · ·+ αkdk; (3.41)

Apos n passos, chega-se ao ponto x∗:

x∗ = α0d0 + α1d1 + · · ·+ α(n−1)dn−1 (3.42)

Proposicao 2

A partir de um ponto inicial x0, arbitrario, e um conjunto de n vetores Q–conjugados, a sequencia geradapor:

xk+1 = xk + αkdk (3.43)

αk =−(gk)tdk

(dk)tQ dk

(3.44)

sendo:

gk = Q xk − b (3.45)


converge para a solucao x∗ que minimiza q(x) depois de n passos, ou seja: xn = x∗.

Demonstracao

Como os vetores di sao LI, e possıvel representar qualquer vetor do espaco de x usando esses vetorescomo base do espaco, ou seja:

x∗ − x0 = α0d0 + α1d

1 + · · ·+ αn−1dn−1 (3.46)

Pre-multiplicando-se a expressao acima por(dk)tQ, obtem-se:

αk =

(dk)tQ(x∗ − x0

)(dk)

tQ dk

(3.47)

Considerando-se a expressao acima como um processo iterativo, ter-se-ia na iteracao k o ponto xk, ouseja:

xk − x(0) = α0d0 + α1d1 + · · ·+ αk−1dk−1 (3.48)

Pre-multiplicando-se mais uma vez por(dk)tQ e lembrando-se que o conjunto e Q–conjugado, obtem-se:

(dk)tQ(xk − x0

)= 0 (3.49)

A expressao de αk na Equacao (3.47) pode ser reescrita como:

αk =

(dk)tQ[(x∗ − xk

)+(xk − x0

)](dk)

tQ dk

(3.50)

Como:

Q x∗ = b (3.51)

e, considerando-se a Equacao (3.45):

Q xk = gk + b (3.52)

finalmente, considerando-se a Equacao (3.49), chega-se a:

αk =−(gk)tdk

(dk)tQ dk

(3.53)

Vale observar que esse valor de αk e justamente o que minimiza a funcao q (x) a partir de xk na direcaodk.

Considerar que q (x) seja representada por uma serie de Taylor de segunda ordem dada por s2(x), a partirdo ponto xk, com um passo αdk. Como a funcao q (x) e quadratica, a aproximacao por serie de Taylor deq (x), s2(x), ate o termo de segunda ordem e exata, ou seja:

s2(xk + αdk) = q(xk) + α

(gk)tdk +

1

2α2(dk)tQ dk (3.54)

Para se obter α que minimiza s2(x), calcula-se:

ds2(xk + αdk)

dα= 0 (3.55)

obtendo-se: (gk)tdk + α

(dk)tQ dk = 0 (3.56)

que fornece o mesmo valor de αk, ou seja:


α = αk =−(gk)tdk

(dk)tQ dk

(3.57)

A Figura 3.7 ilustra o processo de convergencia do metodo de Powell.

1

2

3

2

3

4

Figura 3.7: Passos do Metodo de Powell.

3.2.3 Metodo do Maximo Declive (Steepest Descent, em ingles)

O metodo do Maximo Declive utiliza o gradiente como sendo a direcao de busca, ou seja:

dk = −gk (3.58)

Para se demonstrar que a direcao definida pela expressao (3.58) e a direcao de maior decrescimo dafuncao f(x), no ponto x, considerar a expansao de f(x) em serie de Taylor de primeira ordem, s1(x), emtorno do ponto (x+ s):

s1 (x+ s) ≈ f(x) + [g(x)]ts (3.59)

onde g(x) e o gradiente de f(x) no ponto x. O crescimento da funcao f(x) quando se vai do ponto xpara (x+ s) e dado por:

df(x) ≈ [g(x)]ts (3.60)


ou ainda:

df(x) ≈ ∥g(x)∥ ∥s∥cos(θ) (3.61)

onde θ e o angulo entre os vetores g(x) e s. Para um dado ponto x, df depende apenas de θ, ja que osmodulos dos vetores s e gradiente de f em x sao conhecidos.

O valor de θ que minimiza df e θ = π, quando cos(θ) = −1, ou seja, quando s tem a direcao de:

s = d = −g(x)

3.2.4 Metodo de Fletcher–Reeves

O metodo de Fletcher–Reeves e uma extensao do Metodo dos Gradientes Conjugados. Utilizando-se daformula geral de recorrencia dos metodos de OSR, o metodo dos Gradientes Conjugados visa, de formaiterativa, minimizar somente funcoes quadraticas q (x). Ele apresenta uma expressao para gerar direcoesde busca dk+1, na iteracao k + 1, que tem a propriedade de serem Q–conjugadas em relacao a todas ask direcoes geradas anteriormente. Essa propriedade garante que o processo iterativo para minimizar umafuncao quadratica q (x) converge em n passos. Vale lembrar que, ao minimizar a funcao quadratica q (x), ometodo tera encontrado a solucao do sistema de equacoes lineares Q x = b.

Os principais passos do algoritmo que representa o metodo dos Gradientes Conjugados sao:

1. k = 0; Dado: x0;

2. g0;

3. Se: g0 = 0 =⇒ Fim;

4. d0 = −g0

5. αk =−(gk)

tdk

(dk)tQ dk ;

6. xk+1 = xk + αkdk;

7. gk+1;

8. Se: gk+1 = 0 =⇒ Fim;

9. βk =(gk+1)

tQ dk

(dk)tQ dk ;

10. dk+1 = −gk+1 + βkdk;

11. k = k + 1;

12. Volta para o passo 5.

A formula que permite o calculo de βk (passo 9 do algoritmo acima) e obtida pre-multiplicando-se a

expressao que calcula a direcao dk+1 (passo 10 do algoritmo acima) por(dk)tQ, ou seja:(

dk)tQ dk+1 =

(dk)tQ(−gk+1 + βkdk

)= 0 (3.62)

Como as direcoes dk e dk+1 sao Q–conjugadas, chega-se a:

βk =

(gk+1

)tQ dk

(dk)tQ dk

(3.63)


Exemplo 3.1 – Metodo dos Gradientes Conjugados

Considerar a seguinte funcao quadratica:

f(x1, x2, x3) =1

2x21 + 2x1x3 +

3

2x22 + x2x3 +

5

2x23 − 5x1 − x2 − 10x3

Calcular o mınimo dessa funcao usando como ponto inicial: x0 = {0, 0, 0}t.

Solucao:

A funcao f pode ser representada por:

f(x) =1

2xtQ x− xt b

onde:

Q =

1 0 20 3 12 1 5

b =

5110

Pode-se calcular:

g(x) = ∇f(x) = Q x− b ={

x1 + 2x3 − 5, 3x2 + x3 − 1, 2x1 + x2 + 5x3 − 10}t

g0 = ∇f(x0) = {−5,−1,−10}t

d0 = −g0

α0 =−(g0)td0

(d0)tQ d0

=63

374= 0.1684

x1 = x0 + α0d0 = {0.8422, 0.1684, 1.6840}t

Na proxima iteracao, k = 1, tem-se:

g1 = ∇f(x1) = {−0.7888, 1.1900, 0.2754}t

β0 =

(g1)tQ d0

(d0)tQ d0

= 0.01678

d1 = −g1 + β0d0 = {0.8726,−1.1730,−0.1076}t

α1 =−(g1)td1

(d1)tQ d1

= 0.4381

x2 = x1 + α1d1 = {1.2250,−0.3455, 1.6370}t

Para a segunda iteracao tem-se:

g2 = ∇f(x2) = {−0.5008,−0.3992, 0.2903}t


β1 =

(g2)tQ d1

(d1)tQ d1

= 0.2339

d2 = −g2 + β1d1 = {0.7049, 0.1248,−0.3155}t

α2 =−(g2)td2

(d2)tQ d2

= 6.775

x3 = x2 + α2d2 = {6.0000, 0.5000,−0.5000}t

Notar que, como f e uma funcao quadratica de tres variaveis, e esperado que:

g3 = ∇f(x3) = {0, 0, 0}t

Desta forma: x∗ = x3 e o valor da funcao objetivo no ponto de mınimo e: −12.7500.�

O metodo de Fletcher–Reeves e uma adaptacao do Metodo dos Gradientes Conjugados que o torna capazde ser usado para minimizar uma funcao qualquer f(x) e nao apenas uma funcao quadratica q(x). Paratanto, duas alteracoes sao feitas no algoritmo correspondente ao metodo dos Gradientes Conjugados: (a) ocalculo de αk (vide passo 5 do algoritmo correspondente ao metodo dos Gradientes Conjugados) passa a serfeito por meio de busca unidimensional; e (b) o calculo de βk (vide passo 9 do mesmo algoritmo) passa a serfeito utilizando-se a expressao (3.64), que e computacionalmente mais eficiente por envolver apenas produtosde vetores:

βk =

(gk+1

)tgk+1

(gk)tgk

(3.64)

3.2.5 Metodo de Hestenes–Stiefel

Este metodo se diferencia do metodo de Fletcher–Reeves no calculo do parametro βk, o qual e dado pelaseguinte expressao:

βk =

(gk+1

)t [gk+1 − gk

](dk)

t[gk+1 − gk]

(3.65)

3.2.6 Metodo de Polak–Ribiere

Semelhantemente ao metodo de Hestenes–Stiefel, o metodo de Polak–Ribiere apresenta uma expressao par-ticular para o calculo do parametro βk, a qual e dada por:

βk =

(gk+1

)tgk+1 −

(gk+1

)tgk

(gk)tgk

(3.66)


3.2.7 Metodo de Newton–Raphson

No metodo de Newton–Raphson, a direcao de busca e dada por:

dk = −(Hk)−1

gk (3.67)

Para se entender a expressao da direcao de busca dk no metodo de Newton–Raphson, deve-se, inicial-mente, representar a funcao f(x) no ponto

(xk + dk

)por uma aproximacao em serie de Taylor de segunda

ordem s2(x) na vizinhanca do ponto xk, onde gk e Hk sao, respectivamente, o gradiente e a matriz Hessianade f(x) avaliados no ponto xk:

s2(xk + dk

)= f

(xk)+(gk)tdk +

1

2

(dk)tHkdk (3.68)

Para se obter o mınimo de s2, em relacao a direcao dk, calcula-se:

ds2(xk + dk

)ddk

= 0 (3.69)

onde se obtem:

dk = −(Hk)−1

gk (3.70)

3.2.8 Metodos Quase–Newton

Os metodos Quase-Newton sao assim chamados devido a semelhanca da sua expressao para obtencao dadirecao de busca com a expressao do metodo de Newton-Raphson (vide Equacao 3.70).

Uma das versoes mais utilizadas do metodo Quase-Newton e a que consiste na aproximacao da inversada matriz Hessiana. Nessa versao, a direcao de busca e obtida da seguinte forma:

dk = −Skgk (3.71)

onde Sk e uma aproximacao da inversa da matriz Hessiana,(Hk)−1

.Quando o metodo Quase-Newton utiliza uma aproximacao da inversa da Hessiana na expressao de dk,

diz-se que o metodo e de atualizacao inversa e quando se utiliza uma aproximacao da Hessiana para obtencaode dk, diz-se que o metodo e de atualizacao direta. O metodo de aproximacao inversa tem a grande vantagemde dispensar o calculo da inversa de Hk ou a solucao de um sistema de equacoes lineares para se obter adirecao de busca, como indicado a seguir:

Hkdk = −gk (3.72)

A formula de recorrencia dos metodos Quase-Newton pode ser expressa por:

xk+1 = xk − αkSkgk (3.73)

onde αk e obtido por busca unidimensional.A ideia basica por tras de todos os metodos Quase-Newton e a de poder minimizar uma funcao quadratica

q(x), sendo x um vetor de n variaveis, em n+1 passos. Isso equivale a se obter a verdadeira inversa da matrizHessiana de q(x), aqui denominada de Q−1, depois de n passos. No passo n + 1 a solucao e obtida. Nessesentido, ele e equivalente ao metodo dos Gradientes Conjugados que tambem converge no mesmo numero depassos.

Para efeito de comparacao, o metodo de Newton-Raphson realizaria tal tarefa em apenas um passo en-quanto o metodo de Powell necessitaria de (n+1)2 passos. Vale dizer, todavia, que o trabalho computacionalpara cada um dos passos dos diferentes metodos e bem diferente.

Apesar dos metodos Quase-Newton terem sido desenvolvidos com base na ideia de minimizar funcoesquadraticas em n + 1 passos, eles nao foram pensados para se limitar apenas a solucao dessa tarefa. Asexpressoes desenvolvidas para a atualizacao da aproximacao da inversa da Hessiana da funcao quadraticaq(x) podem ser utilizadas para aproximar a inversa da Hessiana de qualquer funcao f(x) e e aı que reside o


interesse nesses metodos. Nesse caso, nao ha garantia de convergencia para a solucao num dado numero depassos.

As formulas para a atualizacao da aproximacao da inversa da Hessiana Sk utilizam informacoes obtidasem iteracoes anteriores, como o vetor do incremento do passo δkx e o vetor de incremento do gradiente δkg ,ou seja:

δkx = xk+1 − xk

δkg = gk+1 − gk

(3.74)

Seja a funcao quadratica q(x):

q(x) =1

2xtQ x− bt x (3.75)

g(x) = Q x− b (3.76)

Definindo-se os seguintes vetores:

gk = Q xk − b (3.77)

gk+1 = Q xk+1 − b (3.78)

gk+1 − gk = Q(xk+1 − xk

)(3.79)

ou ainda:

δkg = Q δkx (3.80)

δkx = Q−1 δkg (3.81)

A Expressao (3.80) e denominada equacao secante ou Quase-Newton.Se forem gerados n vetores δkx linearmente independentes e com eles forem obtidos n vetores δkg por meio

da equacao Quase-Newton, e possıvel agrupar os vetores δkx na matriz D e os vetores δkg na matriz Q ereescrever as Equacoes (3.80) e (3.81) da seguinte forma:

Q = Q D (3.82)

ou:

D = Q−1 Q (3.83)

ou ainda:

Q = Q D−1 (3.84)

As aproximacoes para a inversa de Q vao sendo geradas sucessivamente ao final de cada iteracao. Quandose chega ao ponto xk; gera-se a aproximacao Sk para Q−1 com as informacoes das iteracoes passadas δkx eδkg ; obtem-se αk por busca unidimensional; e avanca-se para o proximo ponto:

xk+1 = xk − αkSkgk (3.85)

A matriz Sk+1 gerada no novo ponto xk+1, na iteracao k + 1, deve satisfazer a equacao Quase-Newton

Sk+1δig = δix, 0 ≤ i ≤ k (3.86)

para que Sk+1 seja uma boa aproximacao de Q−1.


3.2.8.1 Algoritmo de Correcao de Posto Um

Um dos esquemas mais antigos e conhecidos para a obtencao da aproximacao da inversa de Q e a correcaode posto um (rank one correction, em ingles), que e realizada a partir da seguinte expressao basica:

Sk+1 = Sk + akzk(zk)t

(3.87)

O termo “correcao de posto um” se deve ao fato de que a atualizacao de Sk e feita atraves de sua somacom uma matriz de posto um, uma vez que ela e obtida pelo produto de um vetor coluna pelo mesmo vetortransposto sendo o resultado multiplicado por um escalar:

posto[zk(zk)t]

= posto

zk1...zkn

[ zk1 · · · zkn] = 1 (3.88)

Qualquer matriz inicial S0 dos metodos Quase-Newton deve ser simetrica e positiva definida e as ex-pressoes de atualizacao preservam essas propriedades. Para i = k, a equacao secante e dada por:

δkx = Sk+1δkg (3.89)

Substituindo-se Sk+1 pela expressao basica de correcao de posto um (3.87) , chega-se a:

δkx = Skδkg + akzk(zk)tδkg (3.90)

Duas expressoes podem ser obtidas da expressao (3.90). A primeira e obtida explicitando-se o vetor zk,ou seja:

zk =δkx − Skδkg

ak (zk)tδkg

(3.91)

e a segunda e obtida fazendo-se o produto interno da expressao (3.90) por(δkg

)t:(

δkg

)tδkx −

(δkg

)tSkδkg = ak

[(zk)tδkg

]2(3.92)

ou, alternativamente: (δkg

)t (δkx − Skδkg

)= ak

[(zk)tδkg

]2(3.93)

Substituindo-se a expressao obtida para zk na formula basica de recorrencia que permite obter Sk+1 nometodo de correcao de posto um, chega-se a:

Sk+1 = Sk +ak

(δkx − Skδkg

)(δkx − Skδkg

)tak

[(zk)

tδkg

]ak

[(zk)

tδkg

] (3.94)

ou:

Sk+1 = Sk +

(δkx − Skδkg

)(δkx − Skδkg

)tak

[(zk)

tδkg

]2 (3.95)

ou ainda, utilizando-se a Equacao (3.93):

Sk+1 = Sk +

(δkx − Skδkg

)(δkx − Skδkg

)t(δkg

)t (δkx − Skδkg

) (3.96)


A expressao (3.96) e a proposta para a atualizacao da inversa de Q para a correcao de posto um. Ela foiobtida fazendo-se i = k na equacao Quase-Newton. Todavia, a aproximacao da inversa de Q deve satisfazera equacao Quase-Newton para valores de i < k, ou seja:

δix = Sk+1δig, ∀i < k (3.97)

Revendo-se o que foi dito ate aqui, o metodo parte de um ponto inicial x0 e de uma aproximacao inicialS0. A partir desse ponto, calcula-se g0, obtem-se α0 e utiliza-se a formula de recorrencia para se chegar aonovo ponto x1. Na iteracao i o esquema se repete, ou seja:

xi+1 = xi − αiSigi, i = 0, 1, · · · (3.98)

A obtencao da aproximacao Si+1 nesse ponto e feita calculando-se em sequencia:

gi+1 (3.99)

δix = xi+1 − xi (3.100)

δig = gi+1 − gi (3.101)

Si+1 = Si +

(δix − Siδig

) (δix − Siδig

)t(δig)t (

δix − Siδig) (3.102)

ou:

Si+1 = Si + yi(δix − Siδig

)t(3.103)

onde:

yi =δix − Siδig(

δig)t (

δix − Siδig) (3.104)

Quando se chega ao ponto xk+1 e se obtem Sk+1, deve-se ter:

δix = Sk+1δig, ∀i < k (3.105)

A prova da validade da expressao (3.105) se dara por inducao, ou seja, supondo-se que ela e valida paraSk e i < k, ou seja, para as etapas anteriores.

Como a expressao foi provada ser verdadeira para i = k, entao vale:

δ0x = S1δ0g (3.106)

Pos-multiplicando-se a expressao (3.103) com i = k por δig obtem-se:

Sk+1δig = Skδig + yk

[(δkx

)tδig −

(δkg

)tSkδig

](3.107)

onde:

yk =δkx − Skδkg(

δkg

)t (δkx − Skδkg

) (3.108)

Pela hipotese de inducao:

Sk+1δig = δix + yk

[(δkx

)tδig −

(δkg

)tδix

](3.109)


onde: (δkx

)tδig −

(δkg

)tδix = 0 (3.110)

pois:

δig = Q δix e δkg = Q δkx (3.111)

assim:

Sk+1δig = δix (3.112)

3.2.8.2 Algoritmo de Correcao de Posto Dois ou DFP (Davison–Fletcher–Powell)

No algoritmo de posto dois a expressao para a atualizacao de Sk e dada por:

Sk+1 = Sk +δkx

(δkx

)t(δkx

)tδkg

−Sk δkg

(δkg

)tSk(

δkg

)tSk δkg

(3.113)

Da-se o nome de atualizacao de posto dois, pelo fato da matriz que se adiciona a Sk ser de posto dois.

3.2.8.3 Algoritmo BFGS (Broyden–Fletcher–Goldfarb–Shanno)

A expressao para a atualizacao de Sk no metodo BFGS e apresentada a seguir:

Sk+1 = Sk +

[(δkx

)tδkg +

(δkg

)tSk δkg

]δkx

(δkx

)t[(

δkx

)tδkg

]2 −Sk δkg

(δkx

)t+ δkx

(Sk δkg

)t(δkx

)tδkg

(3.114)

ou ainda,

Sk+1 =

[I− γk δkx

(δkg

)t]Sk

[I− γk δkg

(δkx

)t]+ γk δkx

(δkx

)t(3.115)

onde:

γk =1(

δkg

)tδkx

(3.116)

O metodo BFGS pode ser implementado de uma forma alternativa muito mais eficiente, conforme indicadoa seguir:

Sk+1 =[I+wk

(vk)t]

Sk[I+ vk

(wk)t]

(3.117)

E importante observar que durante a implementacao do algoritmo, Sk+1 nao deve ser obtida explicita-mente de Sk, como indicado na Equacao (3.117), mas, alternativamente, deve-se obter dk+1 diretamentecomo indicado na expressao (3.118). Nota-se que S0 deve ser igual a matriz identidade I ou a β I, onde βe um escalar ≪ 1. Sendo assim, a expressao (3.118) so apresenta operacoes de produtos de vetores que emuito mais eficiente, do ponto de vista computacional, do que operacoes de produtos de matrizes por vetores,como seria necessario caso Sk+1 fosse efetivamente calculada. Por outro lado, vale observar que para aplicara expressao (3.118), e necessario armazenar todos os vetores vk e wk desde a iteracao 0 ate a iteracao k.Recomenda-se, todavia, guardar somente os 10 ultimos vetores vk e wk e, caso nao haja convergencia nesseciclo de 10 iteracoes, comecar um novo ciclo com S0 = I.

dk+1 = −[I+wk

(vk)t] · · · [I+w0

(v0)t]

S0[I+ v0

(w0)t] · · · [I+ vk

(wk)t]

gk+1 (3.118)


[I+w0

(v0)t]

S0[I+ v0

(w0)t]︸︷︷︸[

I+w1(v1)t]

S1[I+ v1

(w1)t]︸︷︷︸

...

dk+1 = −[I+wk

(vk)t]

Sk[I+ vk

(wk)t]

gk+1

(3.119)

onde: vk = gk

[1 + αk

√∣∣∣∣ (dk)t δkg

(δkx)

tgk

∣∣∣∣]− gk+1

wk =δkx

(δkx)

tδkg

(3.120)

Implementacao do metodo Quase-Newton BFGS

• Inicializacao e primeira iteracao (k = 0):

1. Escolher x0 e S0, aproximacao de H−1, geralmente como sendo a matriz identidade (I);

2. Calcular g0 a partir de x0 e d0 = −S0 g0;

3. Obter α0 por busca unidimensional minimizando f(x0 + αd0);

4. Avancar para a proxima iteracao: x1 = x0 + α0d0;

• Iteracao k + 1

1. Calcular gk+1 a partir de xk+1;

2. Obter os vetores δkx e δkg (vide Equacoes 3.74);

3. Calcular os vetores vk e wk (vide Equacoes 3.120);

4. Calcular a direcao de busca dk+1 (vide Equacao 3.118);

5. Obter αk+1 por busca unidimensional minimizando f(xk+1 + αdk+1);

6. Avancar para a proxima iteracao: xk+2 = xk+1 + αk+1dk+1.

Capıtulo 4

Fundamentos de Otimizacao ComRestricoes (OCR)

No problema geral de otimizacao com restricoes, deve-se minimizar uma funcao f(x), com as variaveis xsubmetidas a restricoes, que podem ser de igualdade, desigualdade e/ou laterais, conforme indicado a seguir:

min f(x)

s.t. hk(x) = 0, k = 1 . . .mcl(x) ≤ 0, l = 1 . . . pxi

l ≤ xi ≤ xiu, i = 1 . . . n

(4.1)

As restricoes laterais limitam o valor da variavel xi ao valor mınimo de xli e ao valor maximo de xu

i .

4.1 Condicoes de Mınimo no Problema de OCR

4.1.1 Condicoes de Primeira Ordem

4.1.1.1 Problemas com Restricoes de Igualdade

Considerar o seguinte problema de otimizacao com restricoes de igualdade apenas: min f(x)

s.t. hk(x) = 0, k = 1 . . .m(4.2)

Seja x∗ um mınimo local desse problema. Portanto, nao e possıvel dar um passo viavel, a partir de x∗,que seja tambem um passo de decrescimo de f(x).

A serie de Taylor de primeira ordem para a restricao hk(x), em torno do ponto x∗ e com um passo s,fornece:

hk(x∗ + s) ≈ hk(x

∗) + st ∇h∗k (4.3)

onde o vetor ∇h∗k e o gradiente de hk(x) em x∗.

Para que o passo s seja viavel, e preciso que a restricao hk seja satisfeita no ponto (x∗ + s). Como ela esatisfeita em x∗ (ou seja: hk(x

∗) = 0), isso significa que deve-se ter:

st ∇h∗k = 0 (4.4)

A serie de Taylor de primeira ordem para a funcao objetivo f(x), em torno do ponto x∗ e com um passos, e dada por:

43

44 CAPITULO 4. FUNDAMENTOS DE OTIMIZACAO COM RESTRICOES (OCR)

f(x∗ + s) ≈ f(x∗) + st g∗ (4.5)

onde g∗ e o vetor gradiente de f(x) em x∗.Para que o passo s seja de decrescimo, e preciso que f(x∗ + s) seja menor do que f(x∗), ou seja:

st g∗ ≤ 0 (4.6)

Mostra-se que, se g∗ for expresso por:

g∗ = −m∑

k=1

λ∗k ∇h∗

k (4.7)

entao nao e possıvel dar um passo viavel e de decrescimo s a partir de x∗ e, consequentemente, x∗ e ummınimo local do problema representado pela Equacao (4.2).

A Equacao (4.7) significa que g∗, vetor gradiente de f(x) em x∗, deve ser uma combinacao linear dosgradientes das restricoes em x∗, ou ainda, o vetor g∗ deve pertencer ao espaco cuja base e definida pelosvetores ∇h∗

k. O escalar λk e denominado multiplicador de Lagrange associado a restricao k.

A prova de que a condicao acima e necessaria e suficiente para que x∗ seja um mınimo local e dada porcontradicao. Se a condicao (4.7) nao for necessaria, pode-se entao escrever:

g∗ = u −m∑

k=1

λ∗k ∇h∗

k (4.8)

onde o vetor u = 0 e uma componente do vetor g∗ ortogonal aos vetores ∇h∗k, ou seja, que nao pertence

ao espaco definido pela base de vetores ∇h∗k. Imagine-se que, a partir de x∗, e dado um passo s = −u. Logo,

s satisfaz:

st ∇h∗k = −ut ∇h∗

k = 0 (4.9)

pois u e ortogonal a ∇h∗k e, de acordo com a expressao (4.4), s e um passo viavel a partir de x∗. Deve-se

verificar se s e tambem um passo de decrescimo a partir de x∗. Para que isto ocorra, s deve satisfazer aEquacao (4.6), ou seja:

st g∗ ≤ 0 (4.10)

Substituindo-se s por −u na Equacao (4.10) e g∗ pela expressao (4.8) obtem-se:

st g∗ = −ut

[u−

m∑k=1

λ∗k ∇h∗

k

]= −∥u∥2 + 0 ≤ 0 (4.11)

Portanto, s, alem de ser um passo viavel, e tambem um passo de decrescimo a partir de x∗.

Ao se supor que g∗ nao esta no espaco definido pelos vetores ∇h∗k, foi possıvel encontrar um passo

s = −u, que era, ao mesmo tempo, viavel e de decrescimo, o que nao e possıvel se x∗ for um mınimo local.Conclui-se, entao, que s deve ser nulo e que g∗ deve pertencer ao espaco cuja base e definida pelos vetores∇h∗

k. A expressao (4.7) apresenta, portanto, uma condicao necessaria de primeira ordem para que x∗ sejaum mınimo local do problema de otimizacao com restricoes de igualdade definido em (4.2). Esta condicaoconduz ao metodo dos multiplicadores de Lagrange.

Para se encontrar x∗ e λ∗k que satisfacam as equacoes:

g(x∗) = −m∑

k=1

λ∗k ∇hk(x

∗) (4.12)

hk(x∗) = 0, k = 1, . . .m (4.13)

4.1. CONDICOES DE MINIMO NO PROBLEMA DE OCR 45

e conveniente definir a funcao Lagrangeana como:

L(x,λ) = f(x) +m∑

k=1

λk hk(x) (4.14)

Para se encontrar o mınimo da funcao Lagrangeana, deve-se ter:

∂L(x,λ)∂x

= g(x∗) +

m∑k=1

λ∗k ∇hk(x

∗) = 0 (4.15)

∂L(x,λ)∂λk

= hk(x∗) = 0, k = 1 . . .m (4.16)

As Equacoes (4.15) e (4.16) correspondem exatamente as condicoes de primeira ordem que um ponto x∗

deve satisfazer para ser um mınimo local do problema de otimizacao com restricoes de igualdade. Em outraspalavras, se x∗ e λ∗ forem um ponto estacionario da funcao Lagrangeana, eles serao, respectivamente, ovetor que representa o mınimo local e vetor com os multiplicadores de Lagrange associados ao problema deminimizacao com restricoes de igualdade.

4.1.1.2 Problemas com Restricoes de Desigualdade

Considerar, agora, o seguinte problema de otimizacao com restricoes de desigualdade apenas: min f(x)

s.t. cl(x) ≤ 0, l = 1 . . . p(4.17)

Seja x∗ um mınimo local desse problema. Portanto, nao e possıvel dar um passo viavel, a partir de x∗,que tambem seja um passo de decrescimo de f(x).

A serie de Taylor de primeira ordem para a restricao cl(x), em torno do ponto x∗ e com um passo s, edada por:

cl(x∗ + s) ≈ cl(x

∗) + st ∇c∗l (4.18)

onde o vetor ∇c∗l e o gradiente de cl(x) em x∗.

Serao consideradas apenas as restricoes j ativas1 em x∗. Para que o passo s seja viavel a partir de x∗, epreciso que a restricao cj seja satisfeita em (x∗ + s). Como ela e ativa em x∗, isso significa que:

st ∇c∗j ≤ 0 (4.19)

Como visto anteriormente no caso de restricoes de igualdade, se x∗ e um mınimo local, entao, nao devemexistir nem passos viaveis e nem de decrescimo de f(x) em x∗. Vale lembrar que, passos de decrescimo saoaqueles que satisfazem a expressao:

st g∗ ≤ 0 (4.20)

Mostra-se que, se, para as restricoes ativas j, g∗ for expresso por:

g∗ = −∑j

µ∗j ∇c∗j (4.21)

eµ∗j ≥ 0 (4.22)

entao, nao havera nem passos viaveis e nem de decrescimo em x∗ e, consequentemente, esse ponto cor-respondera a um mınimo local. A prova se dara por contradicao.

1cj(x∗) e dita ativa se cj(x

∗) = 0.


Seja s um passo que satisfaz:

st ∇c∗j = 0, j = q (4.23)

e

st ∇c∗q = −1 (4.24)

Nota-se que o passo s, definido acima, e viavel pois st ∇c∗j ≤ 0 para todo j, inclusive j = q. Agrupando-se todos os vetores coluna ∇c∗j em uma matriz, denominada A∗, as Equacoes (4.23) e (4.24) podem serreescritas como:

(A∗)ts = −eq (4.25)

onde eq e um vetor com tantos elementos nulos quantos forem as restricoes ativas menos um, o elementocorrespondente a linha q, que vale −1. Logo, pode-se escrever:

s =[(A∗)

t]+

eq (4.26)

onde o sımbolo “+” significa a inversa generalizada2 de (A∗)t. Supondo-se m restricoes ativas e sabendo-

se que o vetor s tem a dimensao do vetor x, ou seja n, a matriz (A∗)ttera a dimensao m× n, e sua inversa

generalizada n×m.O conceito de matriz inversa generalizada e aplicado a matrizes retangulares. Seja uma matriz retangular

Bm×n. Chama-se inversa generalizada a esquerda de Bm×n a matriz B+n×m com a seguinte propriedade:

B+n×mBm×n = In×n (4.27)

onde In×n e a matriz identidade de ordem n. Pode-se adiantar que uma maneira simples de se obter ainversa generalizada a esquerda da matriz Bm×n e:

B+n×m =

[Bt

n×mBm×n

]−1Bt

n×m (4.28)

pois:

B+n×mBm×n =

[Bt

n×mBm×n

]−1 [Bt

n×mBm×n

]= In×n (4.29)

Verifica-se agora se a direcao viavel s definida na Equacao (4.26) e tambem uma direcao de decrescimo,levando-se em consideracao as relacoes entre g∗, ∇c∗j e µ∗

j (vide expressoes 4.21 e 4.22), ou seja:

st g∗ = −st∑j

µ∗j ∇c∗j = µ∗

q (4.30)

Ve-se, nesse caso, que a direcao viavel s nao e de decrescimo, pois o produto interno entre os vetoresg∗ e s deveria ser negativo para se ter uma direcao de decrescimo, e ele e maior ou igual a zero por serigual a µ∗

q . Portanto, para direcoes estacionarias s, ou seja, aquelas para as quais st g∗ = 0, as condicoes deKarush-Kuhn-Tucker (KKT) de primeira ordem sao dadas por:

g∗ = −∑l

µ∗l ∇c∗l , l = 1 . . . p (4.31)

cl(x∗) ≤ 0, l = 1 . . . p (4.32)

µ∗l ≥ 0, l = 1 . . . p (4.33)

µ∗l c∗l = 0, l = 1 . . . p (4.34)

A expressao (4.34) e chamada de condicao de complementaridade e significa que, se a restricao de desi-gualdade nao estiver ativa, o multiplicador de Lagrange associado deve ser nulo.

2Mais detalhes sobre a teoria de matrizes inversas generalizadas podem ser vistos na Referencia [8].


4.1.1.3 Problema Geral de Otimizacao com Restricoes

Seja um problema geral de OCR: min f(x)

s.t. hk(x) = 0, k = 1 . . .mcl(x) ≤ 0, l = 1 . . . p

A funcao Lagrangeana associada e dada por:

L(x,λ,µ) = f(x) +m∑

k=1

λk hk(x) +

p∑l=1

µl cl(x)

e as condicoes necessarias (condicoes de primeira ordem) de KKT sao dadas pelas seguintes expressoes:

g∗ = −∑k

λ∗k ∇h∗

k −∑l

µ∗l ∇c∗l , k = 1 . . .m ; l = 1 . . . p

hk(x∗) = 0, k = 1 . . .m

cl(x∗) ≤ 0, l = 1 . . . p

λ∗k = ∀ valor, k = 1 . . .m

µ∗l ≥ 0, l = 1 . . . p

λ∗k h∗

k = 0, k = 1 . . .m

µ∗l c∗l = 0, l = 1 . . . p

4.1.2 Condicoes de Segunda Ordem

4.1.2.1 Problemas com Restricoes de Igualdade

Considerar que os vetores ∇h∗k sao linearmente independentes em x∗. Da definicao de funcao Lagrangeana,

pode-se escrever que, para o ponto (x∗ + s):

L(x∗ + s,λ∗) = f (x∗ + s) +

m∑k=1

λ∗k hk(x

∗ + s) (4.35)

ou, pela serie de Taylor de segunda ordem:

L (x∗ + s,λ∗) = L (x∗,λ∗) + st ∇L∗ +1

2st W∗ s (4.36)

onde W∗ e a Hessiana da funcao Lagrangeana L no ponto (x∗,λ∗) e L,x, e o vetor das derivadas parciaisde L em relacao as variaveis x. Como a funcao Lagrangeana no ponto (x∗,λ∗) e dada por:

L(x∗,λ∗) = f (x∗) +m∑

k=1

λ∗k hk(x

∗) (4.37)

ehk (x

∗) = 0, k = 1 . . .m (4.38)

Da condicao de primeira ordem vale:∇L∗ = 0 (4.39)


pode-se reescrever a aproximacao de Taylor, como:

L (x∗ + s,λ∗) = f (x∗) +1

2st W∗ s (4.40)

Para que s seja uma direcao viavel, deve-se ter:

hk (x∗ + s) = 0, k = 1 . . .m (4.41)

o que tambem significa dizer, considerando (4.35), que:

L (x∗ + s,λ∗) = f (x∗ + s) (4.42)

Combinando-se as Equacoes (4.40) e (4.42) obtem-se:

f (x∗ + s) = f (x∗) +1

2st W∗ s (4.43)

E, se x∗ e um mınimo local, entao:

st W∗ s ≥ 0 (4.44)

Em outras palavras, se s e um vetor numa direcao viavel, ou seja:

st ∇h∗k = 0 (4.45)

a Hessiana da funcao Lagrangeana deve ser positiva semi–definida em relacao ao vetor s, das direcoesviaveis estacionarias.

4.1.2.2 Problemas com Restricoes de Desigualdade

As condicoes de segunda ordem para problemas com restricoes de desigualdade so serao estudadas em relacaoas restricoes ativas, pois, para restricoes inativas, µ∗

l = 0, e portanto, elas nao estarao presentes na funcaoLagrangeana. Como no item anterior, da definicao de funcao Lagrangeana, pode-se escrever para o ponto(x∗ + s):

L(x∗ + s,µ∗) = f (x∗ + s) +

p∑l=1

µ∗l cl(x

∗ + s) (4.46)

ou, pela serie de Taylor de segunda ordem:

L (x∗ + s,µ∗) = L (x∗,µ∗) + st ∇L∗ +1

2st W∗ s (4.47)

onde, novamente, W∗ e a Hessiana da funcao Lagrangeana L no ponto (x∗,µ∗) e ∇L e o vetor dasderivadas parciais da funcao Lagrangeana em relacao as variaveis x. Como a funcao Lagrangeana no ponto(x∗,µ∗) e dada por:

L(x∗,µ∗) = f (x∗) +

p∑l=1

µ∗l cl(x

∗) (4.48)

e,

cl (x∗) ≤ 0, l = 1 . . . p

µ∗l ≥ 0, l = 1 . . . p

µ∗l c∗l = 0, l = 1 . . . p

(4.49)

e a condicao de primeira ordem impoe:

∇L∗ = 0 (4.50)

Pode-se reescrever a aproximacao de Taylor como:


L (x∗ + s,µ∗) = f (x∗) +1

2st W∗ s (4.51)

Todavia, no ponto x∗ e para um passo s viavel a partir de x∗ sobre as restricoes ativas j, pode-se escrever:

cj (x∗ + s) ≤ 0 e µ∗

j ≥ 0 (4.52)

Nessas condicoes, nada se pode afirmar sobre o sinal do produto:

st W∗ s (4.53)

pois, pelo exposto acima:

f (x∗ + s) +

p∑l=1

µ∗l cl(x

∗ + s) = f (x∗) +1

2st W∗ s (4.54)

ou:

f (x∗ + s) − f (x∗) = −p∑

l=1

µ∗l cl(x

∗ + s) +1

2st W∗ s (4.55)

Observe-se que, para as restricoes inativas, as parcelas do somatorio sao nulas, uma vez que µ∗l = 0. As

parcelas relativas as restricoes ativas sao positivas no somatorio. Sendo assim, vale o seguinte raciocınio:uma parcela positiva (a esquerda do sinal de igualdade), deve ser igual a soma de uma parcela positiva(primeira parcela a direita do sinal de igualdade) com uma outra parcela (segunda parcela a direita do sinalde igualdade) que pode ter qualquer sinal, uma vez que se desconhece o valor relativo das duas parcelasanteriores. Se, todavia, for imposto que:

cj (x∗ + s) = 0 (4.56)

isto significa afirmar que:

st ∇c∗j = 0 (4.57)

pois, pela expansao de primeira ordem em serie de Taylor:

cj (x∗ + s) = cj (x

∗) + st ∇c∗j e ainda: cj (x∗) = 0 (ou seja: ativa)

entao:

f (x∗ + s)− f (x∗) =1

2st W∗ s (4.58)

e, se x∗ e um mınimo local, entao:

st W∗ s ≥ 0 (4.59)

Vale observar que, se s satisfaz a Equacao (4.57) e, no ponto x∗ tem-se:

g∗ = −∑j

µ∗j ∇c∗j (4.60)

entao:

st g∗ = −st∑j

µ∗j ∇c∗j = 0 (4.61)

E assim, s e uma direcao estacionaria, ou seja, que nao produz decrescimo nem acrescimo na funcaoobjetivo f avaliada em x∗, ja que na expansao em serie de Taylor de f(x) em torno de x∗, o produtoapresentado na Equacao (4.61) representa a variacao da funcao nesse ponto. Mais ainda, s e uma direcaoviavel e estacionaria.


Portanto, se s e um vetor numa direcao viavel em relacao as direcoes ativas:

st ∇c∗j = 0 (4.62)

entao, a Hessiana da funcao Lagrangeana deve ser positiva semi-definida em relacao ao vetor s, querepresenta direcoes viaveis estacionarias, ou seja:

st W∗ s ≥ 0 (4.63)

4.2 Os Multiplicadores de Lagrange

Os multiplicadores de Lagrange representam a sensibilidade da funcao objetivo ou da funcao Lagrangeanana solucao em relacao a uma perturbacao em uma dada restricao ativa. Em outras palavras, o quanto afuncao objetivo (ou Lagrangeana) mudaria, caso houvesse uma perturbacao numa dada restricao ativa. Parasimplificar a demonstracao, sera considerado um problema de minimizacao com uma restricao de igualdadeapenas. Matematicamente, a mudanca na funcao objetivo (ou Lagrangeana) para uma dada perturbacao εpode ser medida na restricao por:

dL∗

dε=

df∗

dε= λ (4.64)

onde L∗ e f∗ sao, respectivamente, os valores de L e f avaliados na solucao x∗.Para se demonstrar a expressao (4.64) deve-se comecar imaginando uma perturbacao ε na restricao de

igualdade h(x), ou seja:

h(x) = ε (4.65)

A expressao da funcao Lagrangeana do problema de otimizacao na solucao, onde x = x∗ e λ = λ∗, comofuncao da perturbacao ε em uma restricao de igualdade h(x) e dada por:

L [x∗(ε), λ∗(ε), ε] = f [x∗(ε)] + λ∗(ε) [h(x)− ε] (4.66)

Pela regra da cadeia:

dLdε

=∂L∂x

dx

dε+

∂L∂λ

dλ

dε+

∂L∂ε

(4.67)

como, na solucao, as condicoes de KKT impoem que:

∂L∗

∂x= 0 e

∂L∗

∂λ= 0

entao:

dLdε

=∂L∂ε

= −λ (4.68)

Por outro lado,

L (x, λ, ε) = f(x) + λ [h(x)− ε] (4.69)

logo:

dLdε

=df

dε+

dλ

dε[h(x)− ε] + λ

[dh(x)

dε− 1

](4.70)

Porem, na solucao:

h(x)− ε = 0 (4.71)

e, consequentemente:

4.3. DUALIDADE DE WOLFE 51

dh(x)

dε− 1 = 0 (4.72)

assim, pode-se afirmar que:

dLdε

=df

dε(4.73)

e, finalmente, chega-se a:

df

dε= −λ (4.74)

Pode-se interpretar a expressao (4.74) da seguinte maneira: se o modulo do multiplicador de Lagrangetem um valor alto, isso significa que qualquer relaxacao na restricao a ele associada, vai significar umaalteracao correspondente na funcao objetivo. Essa informacao, pode auxiliar o projetista, na comparacao dograu de importancia de cada restricao no valor da funcao objetivo obtido na otimizacao.

4.2.1 Exemplo de Aplicacao

4.3 Dualidade de Wolfe

O conceito de dualidade permite, a partir de um dado problema de programacao matematica, chamadoprimal, obter um outro problema, chamado dual, cuja solucao tem relacao com a solucao do problema primal.Alem disso e possıvel, conhecendo-se a solucao de um deles, obter a solucao do outro. Essa possibilidade einteressante por varios motivos. O primeiro deles e que, muitas vezes, e mais conveniente, sob o ponto devista da eficiencia computacional, resolver o problema dual ao inves do primal (e vice-versa). Em outrassituacoes, a formulacao de um problema de programacao matematica resulta da aplicacao de um teoremadas ciencias de engenharia. Quando isso acontece, o problema dual de programacao matematica representa,normalmente, a formulacao de um teorema dual ao primeiro. Esse e o caso da analise limite de estruturasvia programacao matematica. A teoria da plasticidade das estruturas apresenta dois teoremas para o calculodo fator de colapso em estruturas que sao os teoremas do limite inferior e do limite superior. Quando seformulam os dois teoremas como problemas de programacao matematica, eles se apresentam como duais, ouseja, um seria o primal e o outro o dual. Mesmo que so houvesse um teorema da analise limite, a dualidadepermitiria formular dois problemas duais.

A dualidade de Wolfe permite mostrar que, dado um problema primal (PP):min f(x)

s.t. hk(x) = 0, k = 1 . . .mcl(x) ≤ 0, l = 1 . . . p

(4.75)

e sua respectiva funcao Lagrangeana (que deve ser uma funcao convexa):

L(x,λ,µ) = f(x) +m∑

k=1

λk hk(x) +

p∑l=1

µl cl(x) (4.76)

seu problema dual (PD) e dado por:max L(x,λ,µ)

s.t. ∂L(x,λ,µ)∂x = 0

λk ≥ 0, k = 1 . . .mµl ≥ 0, l = 1 . . . p

(4.77)

As solucoes dos problemas primal e dual se relacionam da seguinte forma:


• O valor da funcao objetivo na solucao do PP, f(x∗), e igual ao valor da funcao objetivo na solucao doPD, L(x∗,λ∗,µ∗).

• O vetor x∗ do PP e igual ao vetor (λ∗,µ∗) do PD e vice versa.

Para se provar a dualidade de Wolfe, comeca-se relembrando a funcao Lagrangeana do PP na solucao,ou seja:

L(x∗,λ∗,µ∗) = f(x∗) +

m∑k=1

λ∗k hk(x

∗) +

p∑l=1

µ∗l cl(x

∗) (4.78)

e as condicoes de KKT:

g∗ = −∑

k λ∗k ∇h∗

k −∑

l µ∗l ∇c∗l , k = 1 . . .m ; l = 1 . . . p

hk(x∗) = 0, k = 1 . . .m

cl(x∗) ≤ 0, l = 1 . . . p

λ∗k = ∀ valor, k = 1 . . .m

µ∗l ≥ 0, l = 1 . . . p

λ∗k h∗

k = 0, k = 1 . . .m

µ∗l c∗l = 0, l = 1 . . . p

(4.79)

Na solucao do PP, onde x = x∗, λ = λ∗ e µ = µ∗, e valem as condicoes KKT, pode-se escrever:

L(x∗,λ∗,µ∗) = f(x∗) (4.80)

Por outro lado, deixando-se variar os multiplicadores de Lagrange e mantendo-se x = x∗, obtem-se:

L(x∗,λ,µ) = f(x∗) +

m∑k=1

λk hk(x∗) +

p∑l=1

µl cl(x∗) (4.81)

Impondo-se as restricoes:

λk ≥ 0, k = 1 . . .m e µl ≥ 0, l = 1 . . . p (4.82)

para todos os multiplicadores de Lagrange, pode-se afirmar que:

L(x∗,λ∗,µ∗) ≥ L(x∗,λ,µ) (4.83)

pois, com os multiplicadores de Lagrange positivos, ter-se-ia:

m∑k=1

λk hk(x∗) +

p∑l=1

µl cl(x∗) ≤ 0 (4.84)

uma vez que:

hk(x∗) = 0 e cl(x

∗) ≥ 0

Considerando-se, como suposto inicialmente, que a funcao Lagrangeana L e convexa, tem-se:

L(x∗,λ,µ) ≥ L(x,λ,µ) + (x∗ − x)t ∂L(x,λ,µ)

∂x(4.85)

Se for imposta a restricao:

4.3. DUALIDADE DE WOLFE 53

∂L(x,λ,µ)∂x

= 0 (4.86)

entao, pode ser dito que:

L(x∗,λ,µ) ≥ L(x,λ,µ) (4.87)

e, consequentemente, conforme ja foi demonstrado anteriormente:

L(x∗,λ∗,µ∗) ≥ L(x∗,λ,µ) ≥ L(x,λ,µ) (4.88)

ou, simplesmente:

L(x∗,λ∗,µ∗) ≥ L(x,λ,µ) (4.89)

Vale lembrar que so foi possıvel obter a expressao acima com a imposicao de duas restricoes, nomeada-mente:

∂L(x,λ,µ)∂x

= 0, λ ≥ 0 e µ ≥ 0

Logo, resolvendo-se o seguinte problema:max L(x,λ,µ)

s.t. ∂L(x,λ,µ)∂x = 0

λk ≥ 0, k = 1 . . .mµl ≥ 0, l = 1 . . . p

(4.90)

que e o problema dual de Wolfe, obtem-se como solucao, x = x∗, λ = λ∗ e µ = µ∗, pois esses sao os valoresque maximizam L(x,λ,µ), caso sejam impostas as restricoes mencionadas.

4.3.1 Exemplos Teoricos

4.3.1.1 Programacao Linear

Considerando-se o problema de programacao linear padrao (PL) formulado a seguir como um problemaprimal:

min z = ct x+ f0

s.t. At x ≤ bx ≥ 0

(4.91)

onde, a funcao objetivo z e um hiper–plano no espaco das variaveis x positivas e o vetor b ≥ 0. Osvetores coluna x e c tem dimensao n× 1, o vetor b tem dimensao m× 1 e a matriz A das restricoes linearesn×m. Introduzindo-se os multiplicadores λ e π associados, respectivamente, ao primeiro e ao segundo grupode restricoes, pode-se obter a funcao Lagrangeana do problema e seu vetor gradiente em relacao a x:

L(x,λ,π) = ct x+ λt (At x− b)− πt x+ f0 (4.92)

∂L(x,λ,π)∂x

= c+A λ− π (4.93)

Parte-se agora para formular o problema dual associado ao problema primal, ou seja:max ct x+ λt (At x− b)− πt x+ f0

s.t. c+A λ− π = 0λ ≥ 0π ≥ 0

(4.94)


Explicitando-se o vetor c na restricao acima e substituindo-o na funcao objetivo, obtem-se:

(−Aλ+ π)tx+ λt (At x− b)− πt x = −bt λ+ f0 (4.95)

Pode-se agora, considerando que π ≥ 0, reescrever o problema dual simplesmente como:max −bt λ

s.t. −A λ ≤ cλ ≥ 0

(4.96)

Observe-se que o PD obtido tambem e um problema de programacao linear e quando se tem menosrestricoes do que variaveis no problema primal (m < n), o problema dual tera menos variaveis do querestricoes e vice-versa.

4.3.1.2 Programacao Quadratica

Considerando-se agora um problema primal de programacao quadratica padrao, ou seja: min 12 xt Q x+ f t x

s.t. At x ≤ b(4.97)

onde os vetores coluna x e f tem dimensao n×1, o vetor b tem dimensao m×1, a matriz A, das restricoeslineares, tem dimensao n×m e, finalmente, a matriz Q, positiva-definida, tem dimensao n×n. Introduzindo-se m multiplicadores λ associados as restricoes, pode-se obter a funcao Lagrangeana do problema e seu vetorgradiente em relacao a x da seguinte forma:

L(x,λ) = 1

2xt Q x+ f t x+ λt (At x− b) (4.98)

∂L(x,λ)∂x

= Q x+ f +A λ (4.99)

Com eles, e possıvel formular o problema dual de Wolfe associado ao problema primal, ou seja:max 1

2 xt Q x+ f t x+ λt (At x− b)

s.t. Q x+ f +A λ = 0λ ≥ 0

(4.100)

Explicitando-se x no primeiro grupo de restricoes:

x = Q−1 (−A λ− f) (4.101)

E usando-se essa expressao para eliminar x da funcao objetivo, como foi feito no exemplo anterior,chega-se ao problema dual: max − 1

2λt (At Q−1 A) λ− λt (b+At Q−1 f)− 1

2 f t Q−1 f

s.t. λ ≥ 0(4.102)

Vale observar que o PD obtido tambem e um problema de programacao quadratica com variaveis λ. O PDtem m variaveis e m restricoes e pode ser mais conveniente de ser resolvido do ponto de vista computacionaldo que o PP se m < n. Uma vez obtido λ∗, o vetor x∗ pode ser recuperado da seguinte forma:

Q x∗ = −A λ∗ − f (4.103)

Capıtulo 5

Metodos Indiretos em OCR

Historicamente, as primeiras tentativas de se resolver o problema de otimizacao com restricoes (OCR) foramfeitas utilizando-se os metodos indiretos, nomeadamente, os metodos de penalidade e os de barreira. Essesmetodos resolvem problemas de OCR por meio de uma sequencia de solucoes de problemas de OSR. Paraque isso seja possıvel, as restricoes dos problemas de OCR sao incorporadas a funcao objetivo criando-se aschamadas funcoes de penalidade (e de barreira) que sao usadas nos problemas de OSR. A ideia da funcao depenalidade (e de barreira) e criar um alto custo pela violacao das restricoes o que forca a solucao a atenderas restricoes.

Os metodos indiretos apresentam, em geral, dificuldades computacionais e por isso vem sendo substituıdospelos metodos diretos. Eles tem, no entanto, o atrativo de serem metodos simples de se resolver problemas deOCR e apresentam uma importancia historica no desenvolvimento de metodos de programacao matematica.

5.1 Metodo de Penalidade

Para se ilustrar o metodo de penalidade, proposto por Courant em 1947, considera-se um problema simplesde minimizacao de uma funcao com uma restricao de igualdade: min f(x)

s.t. h(x) = 0(5.1)

A funcao de penalidade para esse problema e dada por:

Φ(x, rp) = f(x) +1

2rp [h(x)]

2(5.2)

onde rp e o fator de penalidade.

E possıvel mostrar, como sera visto mais adiante, que a solucao do problema de OCR proposto acima,x∗, e um ponto limite de uma sequencia a ser definida, ou seja, que essa sequencia converge para x∗.

Principais Passos do Metodo de Penalidade:

1. Escolher uma sequencia de valores para rp tendendo a infinito, com k a partir de 1, por exemplo:rkp = 10k−1 , e um valor inicial x = x0;

2. Para cada rkp , formar a funcao de penalidade Φ(x, rkp), conforme indicado acima, e obter xk resolvendo-se o seguinte problema de OSR:

xk ←− minΦ(x, rkp) (5.3)

3. Repetir a operacao indicada no item 2 com o valor inicial da iteracao k igual ao valor obtido naotimizacao da iteracao k − 1.

55

56 CAPITULO 5. METODOS INDIRETOS EM OCR

4. Terminar o processo iterativo quando houver convergencia de xk.

Mostra-se agora que o ponto limite do metodo de penalidade, xk, converge para x∗. Para tal, parte-seinicialmente para se mostrar que, se rkp →∞, entao:

1. Φ(xk, rkp) e nao decrescente.

2.[h(xk)

]2e nao crescente.

3. f(xk) e nao decrescente.

Seja rkp < rlp, entao:

Φ(xk, rkp) ≤ Φ(xl, rkp) (5.4)

pois xk minimiza Φ(x, rkp). Por outro lado:

Φ(xl, rkp) ≤ Φ(xl, rlp) (5.5)

pois rkp < rlp. Analogamente:

Φ(xl, rlp) ≤ Φ(xk, rlp) (5.6)

pois xl minimiza Φ(x, rlp).Com as desigualdades definidas acima e possıvel escrever a cadeia completa de desigualdades, ou seja:

Φ(xk, rkp) ≤ Φ(xl, rkp) ≤ Φ(xl, rlp) ≤ Φ(xk, rlp) (5.7)

Comparando-se o primeiro e o terceiro termos da cadeia de desigualdades:

Φ(xk, rkp) ≤ Φ(xl, rlp) (5.8)

o que demonstra 1.Comparando-se o quarto e o primeiro termos da cadeia:

f(xk) +1

2rkp[h(xk)

]2 ≤ f(xk) +1

2rlp[h(xk)

]2(5.9)

ou:

(rlp − rkp)[h(xk)

]2 ≥ 0 (5.10)

Analogamente, comparando-se o terceiro e o segundo termos da cadeia:

(rlp − rkp)[h(xl)

]2 ≥ 0 (5.11)

Como na cadeia, a diferenca entre o quarto e o primeiro termos e maior do que a diferenca entre o terceiroe segundo, e possıvel afirmar que, observando-se as duas ultimas desigualdades:

(rlp − rkp){[

h(xk)]2 − [h(xl)

]2} ≥ 0 (5.12)

As duas parcelas a esquerda da desigualdade acima sao positivas, ja que o produto das duas e positivo e aprimeira delas tambem e positiva (pois rlp > rkp). Como a segunda parcela da desigualdade acima e positiva,entao: [

h(xk)]2 ≥ [h(xl)

]2(5.13)

o que demonstra 2.Voltando-se para a primeira das desigualdades apresentada nessa demonstracao, ou seja:

5.1. METODO DE PENALIDADE 57

Φ(xk, rkp) ≤ Φ(xl, rkp) (5.14)

pode-se escrever:

f(xk) +1

2rkp[h(xk)

]2 ≤ f(xl) +1

2rkp[h(xl)

]2(5.15)

ou ainda: [f(xl)− f(xk)

]+

1

2rkp

{[h(xl)

]2 − [h(xk)]2} ≥ 0 (5.16)

Analisando-se a desigualdade acima, pode-se dizer que a segunda parcela entre chaves, {}, e negativa(vide expressao 5.13). Logo, pode-se afirmar que a primeira parcela entre colchetes e positiva, pois estasendo diminuıdo um valor dessa parcela e, ainda assim, obtem-se um resultado positivo, o que prova 3, ouseja:

f(xl) ≥ f(xk) (5.17)

Definindo-se f∗ como:

f∗ = min f(x) { ∀x | h(x) = 0 } (5.18)

onde f∗ e o valor da funcao de objetivo f(x) no ponto x∗, ponto que minimiza f(x) e atende a restricaoh(x) = 0. Entao e possıvel afirmar que:

Φ(xk, rkp) ≤ Φ(x, rkp) { ∀x | h(x) = 0 } = f∗ (5.19)

pois, por definicao, xk e o ponto que minimiza Φ(x, rkp) e x∗ nao. Logo, em resumo:

Φ(xk, rkp) ≤ f∗ (5.20)

Baseado nas conclusoes acima, pode-se construir a Figura 5.1, que mostra como se da a convergencia dasiteracoes do metodo de penalidade para a solucao do problema de OCR.

A deducao acima pode ser facilmente generalizada para varias restricoes de igualdade. Nesse caso, a novafuncao de penalidade seria dada por:

Φ(x, rp) = f(x) +1

2rp

m∑k=1

[hk(x)]2

(5.21)

e o processo iterativo seria o mesmo adotado no caso anterior.

Para o problema de OCR com uma restricao de desigualdade, ou seja: min f(x)

s.t. c(x) ≤ 0(5.22)

a funcao de penalidade e modificada para:

Φ(x, rp) = f(x) +1

2rp {max [0, c(x)]}2 (5.23)

de forma a penalizar a funcao objetivo apenas quando a restricao for violada. Quando existem variasrestricoes de desigualdade, a funcao de penalidade e dada por:

Φ(x, rp) = f(x) +1

2rp

p∑l=1

{max [0, cl(x)]}2 (5.24)


r <rk k+1

f,f

x1x1=b

f = x( )x a 1

f1

f2

f3f( )r1

f( )r2

f( )r3

*

*

*

x*

C cj j j{c ( )}={min[0, ]}x2

( )x

Figura 5.1: Processo de Convergencia do Metodo de Penalidade.

5.2 Metodo de Barreira

O metodo de penalidade para restricoes de desigualdade e tambem chamado de metodo exterior porque eletem a caracterıstica de se aproximar da solucao pela regiao nao viavel, ou seja, violando as restricoes. Essacaracterıstica nao e vantajosa porque, se o processo iterativo for interrompido por qualquer razao, como malcondicionamento numerico, a solucao obtida nao e uma solucao viavel do problema.

No metodo da barreira (ou metodo interior), a convergencia se da do interior da regiao das solucoesviaveis para o contorno dela. Essa caracterıstica torna a solucao em cada iteracao do processo uma solucaoviavel, o que e interessante. O metodo usa a denominacao barreira porque a funcao de barreira se tornainfinita no contorno da regiao viavel. As funcoes de barreira mais usadas por esse metodo sao mostradas aseguir para restricoes de desigualdade.

• Funcao de Barreira Inversa (Carrol, 1961) [2]:

Φ(x, rb) = f(x) + rb

p∑l=1

[−cl(x)]−1(5.25)

• Funcao de Barreira Logaritmica (Frisch, 1955) [4]:

Φ(x, rb) = f(x) + rb

p∑l=1

{− log [−cl(x)]}2 (5.26)

No caso de funcoes de barreira, a sequencia rkb no processo iterativo deve tender para zero, ou seja:

rkb = 101−k (5.27)

O processo iterativo do metodo de barreira segue os mesmos passos que foram definidos para o metodode penalidade. As restricoes de igualdade podem ser introduzidas de forma semelhante a que foi apresentadano Metodo de Penalidade, ou seja:

5.2. METODO DE BARREIRA 59

Φ(x, rp, rb) = f(x) +1

2rp

m∑k=1

[hk(x)]2+ rb

p∑l=1

[−cl(x)]−1(5.28)

A Figura 5.2 ilustra o comportamento dos dois metodos.

r >rk k+1

f,f

x1x1=b

f = x( )x a 1

f1

f2

f3

f( )r2x,

f( )r3x,

*

f( )r1x,

*

*

x*

C cj j{ ( )}=1/x cj( )x

Figura 5.2: Comportamento dos Metodos de Penalidade e de Barreira.

Capıtulo 6

Problemas Especiais em OCR

No capıtulo 5 foi visto como resolver problemas de OCR usando metodos indiretos que transformam oproblema de OCR num problema de OSR equivalente e resolve esse ultimo. Nesse capıtulo serao estudadosos metodos diretos de solucao de problemas especiais em OCR, nomeadamente, o problema de ProgramacaoLinear (PL) e o Problema de Programacao Quadratica (PQ). Os metodos diretos para resolver problemasde OCR estao relacionados ao tipo de problema em questao. Assim, o Metodo Simplex e um metodo para seencontrar a solucao de problemas de PL, o algoritmo de Lemke e um algoritmo para se resolver problemas dePLC, e, como tal, pode ser empregado tambem para se obter a solucao de problemas de PQ, etc.. Exemplosde aplicacao em engenharia civil serao formulados e resolvidos pelos algoritmos propostos.

6.1 O Problema de Programacao Linear (PL)

6.1.1 Introducao

O problema de Programacao Linear (PL) e um problema de otimizacao onde a funcao objetivo e as restricoessao funcoes lineares de variaveis nao negativas.

O problema de PL com 2 variaveis pode ser resolvido graficamente como exemplificado a seguir.

Seja o problema:

min f (x1, x2) = −5x1 − 3x2

s.t. g1 (x1, x2) = 3x1 + 5x2 ≤ 15g2 (x1, x2) = 5x1 + 2x2 ≤ 10x1 ≥ 0x2 ≥ 0

(6.1)

A solucao grafica do problema esta indicada a seguir

61

62 CAPITULO 6. PROBLEMAS ESPECIAIS EM OCR

0 1 2 3 4 5 60

1

2

3

4

5

6

3x1

+ 5x2

= 15

5x1

+ 2x2

= 10

x1

x2

f=-6

f=-2

f=-12.37

f=-18A

Figura 6.1: Representacao grafica do problema de PL.

Na Figura (6.8) a area cinza representa a regiao viavel, ou seja, a regiao dos pontos que satisfazem todasas restricoes do problema.

A solucao do problema acima esta no ponto A com coordenadas x1 = 1, 053 e x2 = 2, 368.

f (x1, x2) = −12, 368

As Figuras abaixo ilustram graficamente que o problema de PL pode ter solucoes ilimitadas (Figura 6.2(a)),nao ter solucao, caso as restricoes sejam incompatıveis tornando a regiao viavel inexistente (Figura 6.2(b)),ter varias solucoes (Figura 6.2(c)), ou ainda, apresentar solucao apesar de ter restricoes redundantes (Fi-gura 6.2(d)).

6.1. O PROBLEMA DE PROGRAMACAO LINEAR (PL) 63

x1

x2 direção de

crescimento de f

(a) Solucoes ilimitadas

x1

x2

direção decrescimento de f

(b) Solucao inexistente

x1

x2 direção de

crescimento de f

(c) Solucoes multiplas

x1

x2

direção decrescimento de f

(d) Restricoes redundantes

Figura 6.2: Anomalias em modelos de Programacao Matematica.

Como um exemplo pratico, o problema da otimizacao da producao de uma oficina, ilustra bem o problemade PL.

Seja uma oficina que possui tres tipos de maquinas A, B e C que podem produzir quatro tipos deprodutos 1, 2, 3 e 4. Cada um dos produtos tem que passar por alguma operacao em cada um dos tres tiposde maquinas (maquina de tornear, perfurar e laminar, por exemplo). Considere-se que o tempo para passaro produto de uma maquina para outra e desprezıvel. A Tabela 6.1.1 mostra na primeira coluna o numerode horas requeridas em cada maquina A, B e C para produzir uma unidade do produto do tipo 1 e porultimo o lucro obtido com a venda de uma unidade desse produto. As segunda, terceira e quarta colunasmostram os mesmos dados para a producao de uma unidade do produto do tipo 2, 3 e 4, respectivamente.Na ultima coluna, a direita, esta o tempo total em horas que cada tipo de maquina pode ser utilizada porsemana considerando-se que se tenha 50 maquinas do tipo A, 200 do tipo B e 125 do tipo C e uma semanade 40 horas semanais.

Suponha que xj seja o numero de unidades do tipo j produzidas por semana.

Pretende-se saber quantas unidades devem ser produzidas do tipo 1, 2, 3 e 4 para que o lucro da oficinaseja maximo, como definido na Equacao (6.2).

Considerem-se as restricoes impostas pelo tempo de disponibilidade de cada maquina por semana,


Tipo de MaquinaTipo de produto Tempo total em horas por

1.0 2.4 3.0 4.0 maquina por semanaA 1.5 1.0 2.0 1.0 2000B 1.0 5.0 1.0 3.5 8000C 1.5 3.0 3.5 1.0 5000Unidade de lucro (em reais) 5.24 7.30 8.34 4.18

1, 5x1 + x2 + 2, 4x3 + x4 ≤ 2000 (maquina A)x1 + 5, 0x2 + x3 + 3, 5x4 ≤ 8000 (maquina B)

1, 5x1 + 3, 0x2 + 3, 5x3 + x4 ≤ 5000 (maquina C)(6.2)

As restricoes do tipo xj ≥ 0 sao obvias uma vez que a quantidade de produtos deve ser nao negativa.Pretende-se maximizar o lucro da oficina por semana, desse modo, a funcao objetivo deve ser:

5, 24x1 + 7, 30x2 + 8, 34x3 + 4, 18x4 (6.3)

A primeira parcela da funcao objetivo representa o lucro obtido com a producao de um numero x1 deprodutos do tipo 1. Do mesmo modo, a segunda a terceira e a quarta parcelas representam o lucro obtidocom os produtos do tipo 2, 3 e 4 respectivamente.

A solucao desse problema e:x1 = 294, 118, x2 = 1500, x3 = 0, x4 = 58, 824 e o lucro correspondente f (x1, x2, x3, x4) = 12740 reais.No problema em questao os resultados devem ser arredondados para numeros inteiros por representarem

numero de unidades produzidas.

6.1.2 Fundamentos matematicos

Nesse item serao revisitados alguns conceitos basicos de algebra linear que facilitam a compreensao doalgoritmo simplex que sera apresentado no proximo item.

6.1.2.1 Dependencia linear

Um vetor a pertencente a um espaco n dimensional En e dito ser uma combinacao linear dos vetoresa1,a2, . . . ,ak pertencentes a En se a pode ser escrito como:

a = λ1a1 + λ2a2 + · · ·+ λkak (6.4)

Para arbitrarios λi.Um conjunto de vetores a1, . . . ,am pertencentes a Em e dito ser linearmente dependente (LD) se existe

escalares λi, nao todos nulos, tais que:

λ1a1 + λ2a2 + · · ·+ λmam = 0 (6.5)

Se o unico conjunto de escalares λm para a qual a expressao (6.5) permanece valida for

λ1 = λ2 . . . = λm = 0 (6.6)

Entao os vetores sao chamados de linearmente independente (LI).Uma definicao alternativa para um conjunto de vetores linearmente dependentes e que: um conjunto de

vetores a1, . . . ,am pertencentes a Em e linearmente dependente se, e somente se, um dos vetores for umacombinacao linear dos outros.

am =m−1∑λ=1

λiai oum−1∑i=1

λiai − am = 0 (6.7)

Considerando em (6.5) que λm = 0, vem:


am = −m−1∑λ=1

λi

λmai (6.8)

6.1.2.2 Bases

Uma base para En e um subconjunto de vetores de En linearmente independentes (LI) que geram todo oespaco En.

Um espaco En pode ter um numero infinito de bases. A representacao de um vetor do espaco En numadada basica e unica. Para provar isto, seja um vetor b pertence a En e um conjunto a1, . . . ,ar uma base doreferido espaco. Se for possıvel representar b de duas maneiras diferentes na mesma base vale:

b =r∑

i=1

λiai e b =r−1∑i=1

µiai (6.9)

ou, subtraindo

r∑i=1

(λi − µi)ai = 0 (6.10)

Como uma base e formada por vetores LI,

λi − µi = 0 i = 1, . . . , r (6.11)

e portanto a representacao de b e unica.Seja uma base vetorial a1, . . . ,ar para En e um outro vetor b pertencente a En. O vetor b pode ser

representado na base dada como,

b =r∑

i=1

αiai (6.12)

Se qualquer vetor ai para o qual αi = 0 for retirado da base e substituıdo por b, o novo conjunto etambem uma base.

Seja αr = 0, entao a1,a2, . . . ,ar−1,b forma uma nova base e portanto formam um conjunto LI.Para provar que o novo conjunto e LI, pode-se comecar supondo o contrario, ou seja, o novo conjunto

nao e LI. Nesse caso vale:

r−1∑i=1

δiai + δb = 0 (6.13)

Para pelo menos um δi ou δ diferente de zero.δ nao pode ser igual a zero em (6.13) pois isso iria contradizer a hipotese de que o conjunto ai, i =

1, . . . , r − 1 seja LI.Eliminando b de (6.13) com o uso de (6.12), vem

r−1∑i=1

(δi + αiδ)ai + δαrar = 0 (6.14)

e δαr = 0. No entanto, isto contradiz o fato de que o conjunto ai, i = 1, . . . , r seja L.I. Portanto, ahipotese inicial de que o conjunto formado por a1,a2, . . . ,ar,b e LD levou a uma contradicao e assim nao everdadeira. Conclui-se entao que o conjunto e L.I.

Seja o vetor x representado na base a1, . . . ,ar.

x =r∑

i=1

γiai (6.15)


Ele pode ser representado na nova base a1, . . . ,ar−1,b onde, b e o vetor definido em (6.12).

De (6.12) ar pode ser escrito como:

ar =−αi

αr

r−1∑i=1

ai +1

αr· b (6.16)

Substituindo (6.16) em (6.15), vem:

x =r−1∑i=1

(γi −

αi

αrγr

)ai−

γrαr

b (6.17)

que expressa x como uma combinacao linear de a1, . . . ,ar−1,b, logo, esse novo conjunto e uma base paraEn.

Toda a base para En contem n vetores.

Inicialmente e necessario provar que toda base para En deve ter o mesmo numero de vetores. Se as duasbases para En forem a1, . . . ,au e b1, . . . ,bv, deve-se ter u = v.

Seja a representacao de bv na base a1, . . . ,au.

bv =u∑

i=1

λiai com λu = 0 (6.18)

Assim, como ja foi demonstrado, a1, . . . ,au−1,bv, e tambem uma base de En.

O vetor bv−1 pode agora ser representado nessa base

bv−1 =u−1∑i=1

δiai + δbv (6.19)

com pelo menos um δi = 0 pois caso contrario, o conjunto dos vetores bj nao seria L.I.

Seja δu−1 = 0, entao a1, . . . ,au−2, bv−1, bv e uma nova base para En.

Esse processo pode ser repetido ate que se chegue a uma base com duas formas possıveis, nomeadamente,

a1, . . . ,au−v,b1, . . . ,bv ou b1, . . . ,bv (6.20)

caso u > v ou u = v, respectivamente.

Se u < v chega-se a uma situacao em que sobram alguns bj fora da base que poderiam ser representadospelos vetores da base. Isso e impossıvel pois para ser uma base o conjunto deve ser L.I, logo u ≥ v.

E possıvel agora comecar com a base bj e inserir os vetores aj nessa base. Isso iria a conduzir a queentao v ≥ u.

A unica solucao possıvel para as condicoes u ≥ v e v ≥ u e u = v.

Para se determinar o numero de vetores necessarios para formar uma base do espaco En e suficienteencontrar somente uma base, todas as outras bases devem ter entao o mesmo numero de vetores do que essabase encontrada. Como se sabe que n vetores unitarios ei formam uma base para o espaco En, entao todasas bases devem ter n vetores.

6.1.2.3 Posto (ranking) de uma matriz Amxn

As colunas de Amxn podem ser consideradas vetores do espaco En.

O posto de uma matriz A, mxn, expresso por r(A), e o numero maximo de colunas linearmente inde-pendentes em A.


6.1.2.4 Solucoes basicas

Seja o sistema de equacoes

Ax = b (6.21)

onde Am×n, xn×1 e bm×1, n > m e r(A) = m, ou seja, existem m colunas, m×1, retiradas de A formamum conjunto de vetores L.I.

Se uma submatriz qualquer B, m×m e formada com m vetores aj retirados de A, uma solucao para osistema de Equacoes (6.21) pode ser encontrada com

xb = B−1b (6.22)

e com todas as n − m variaveis nao associadas as colunas retiradas de A iguais a zero. O vetor xb,m × 1, e chamado de solucao basica de (6.21) e as m variaveis associadas as m colunas retiradas de A saodenominadas de variaveis basicas.

Uma solucao basica e dita degenerada se uma ou mais das variaveis basicas se anula.

6.1.2.5 Pontos e conjuntos de pontos

A notacao

X = {x|P (x)} (6.23)

Indica que o conjunto de pontos X = {x} possui a propriedade P (x).Em E2, por exemplo, um conjunto de pontos limitado por uma circunferencia de raio unitario com centro

na origem, isto e, o conjunto de pontos que satisfaz a desigualdade x21 + x2

2 < 1 pode ser representado por:

x ={[x1, x2]|x2

1 + x22 < 1

}(6.24)

Uma hiperesfera em En com centro em a e raio ε > 0 pode ser definida como:

x = {x| |x− a| = ε} (6.25)

E o interior da hiperesfera

x = {x| |x− a| < ε} (6.26)

Uma vizinhanca ε em torno do ponto a e definida como o conjunto de pontos no interior da hiperesferade centro em a e raio ε.

Um ponto a e um ponto interior de um conjunto A se existir uma vizinhanca ε em torno de A quecontenha somente pontos do conjunto A.

O ponto a e um ponto limite (ou de acumulacao) do conjunto A se toda vizinhanca ε em torno de a(indiferente de quao pequeno ε > 0 possa ser) contenha pontos que pertencam e pontos que nao pertencamao conjunto A.

Um conjunto A e um conjunto aberto se contiver somente pontos interiores.Um conjunto A e um conjunto fechado se contiver todos os pontos limites.Um conjunto e um conjunto limitado inferiormente se existir um r com cada componente finito tal

que para todo a ∈ A, r ≤ a.Em En, a reta que passa por dois pontos x1 e x2,x1 = x2, pode ser definida como o conjunto de pontos.

x = {x|x = λx2 + (1− λ)x1 todo realλ} (6.27)

O segmento de reta que une dois pontos x1 e x2 e definido como o conjunto de pontos.

x = {x|x = λx2 + (1− λ)x1; 0 ≤ λ ≤ 1} (6.28)

Em En, o conjunto de pontos x que satisfaz


ctx = z (nao todos ci nulos), (6.29)

sendo c e x vetores coluna n× 1 e z um escalar, e um hiperplano.Em E2 esse hiperplano se degenera numa reta e em E3 num plano.Se z = 0 o hiperplano passa pela origem, ou seja, o vetor x = 0 pertence ao hiperplano:

ctx = 0 (6.30)

A expressao (6.30) implica que o vetor c seja normal a todo vetor x do hiperplano, ou seja, que c eortogonal ao hiperplano.

Sejam x1 e x2 dois pontos do hiperplano definido por (6.29) e z = 0.Nesse caso vale, {

ctx1 = zctx2 = z

(6.31)

Subtraindo a segunda da primeira expressao em (6.31), vem:

ct(x1 − x2) = 0 (6.32)

que significa que o vetor c e ortogonal a todo vetor x1 − x2 contido no hiperplano, ou seja, e ortogonalao hiperplano.

O vetor c e denominado entao de vetor normal ao hiperplano e o vetor definido por

±c|c|

(6.33)

e denominado vetor unitario normal ao hiperplano.Dois hiperplanos sao ditos paralelos se possuırem o mesmo unitario normal.Seja o hiperplano

ctx = zo (6.34)

e o conjunto de pontos

x1 = x0 + λc com λ > 0 e ctxo = zo

Deve-se observar que xo pertence ao hiperplano definido em (6.34) e x1 pertence ao hiperplano

ct(xo + λc) = zo + λ |c|2 = z1 com z1 > zo (6.35)

Assim os pontos x1 pertencentes ao hiperplano ctx1 = z1 satisfazem a ctx1 > zo.Isto significa que o hiperplano ctx1 = z1 pode ser obtido deslocando-se o hiperplano ctxo = zo paralela-

mente a si mesmo na direcao de c.O hiperplano ctx = z divide o espaco En em tres conjuntos mutuamente exclusivos e completos, nomea-

damente X1 = {x| ctx < z}X2 = {x| ctx = z}X3 = {x| ctx > z}

(6.36)

Os conjuntos X1 e X3 sao chamados semi-espacos abertos. Se os sinais < e >, respectivamente em X1

e X3, forem substituıdos por ≤ e ≥ , os conjuntos sao chamados de semi-espacos fechados. O hiperplanoformado pelo conjunto X2 pode ser definido como a intersecao desses dois novos conjuntos fechados.

Um hiperplano e um conjunto fechado porque todo ponto pertencente a um hiperplano e um ponto limite.Um conjunto e um conjunto convexo se, para dois pontos quaisquer x1 e x2 pertencentes ao conjunto,

o segmento de reta que une os dois pontos tambem pertencer ao conjunto.Um conjunto convexo nao pode conter “buracos” nem ser “reentrante”.


Um ponto x e um ponto extremo de um conjunto convexo se, e somente se, nao houver outros doispontos x1 e x2,x1 = x2, pertencentes ao conjunto, tais que:

x = λx2 + (1− λ)x1, 0 < λ < 1 (6.37)

O conjunto da Figura 6.3 nao e um conjunto convexo pois a linha reta que une x1 e x2 nao pertence aoconjunto.

x1

x2

x1

x2

Figura 6.3: Representacao grafica de um conjunto nao convexo.

O hiperplano e um conjunto convexo. Para provar essa afirmacao basta observar que se x1 e x2 pertencemao hiperplano, isto e,

ctx1 = z e ctx2 = z (6.38)

entao,

x = λx2 + (1− λ)x1

tambem pertence ao hiperplano uma vez que

ctx = ct {λx2 + (1− λ)x1} = λ+ (1− λ)z = z (6.39)

A intersecao de dois conjuntos convexos e um conjunto convexo.Sejam dois conjuntos convexos X1 e X2 e x1, x2 dois pontos quaisquer pertencentes ao conjunto X3

intersecao de X1 e X2, ou seja, X3 = X1 ∩X2.Logo, λx2 + (1− λ)x1 ∈ X1, 0 ≤ λ ≤ 1

λx2 + (1− λ)x1 ∈ X2, 0 ≤ λ ≤ 1(6.40)

Assim,

λx2 + (1− λ)x1 ∈ X1 ∩X2 = X3, 0 ≤ λ ≤ 1 (6.41)

e deste modo, X3 e convexo. Se X1 e X2 sao conjuntos fechados, X3 tambem e fechado. Para verificaresse fato, basta notar que todo ponto limite de X3 e um ponto limite de X1 ou de X2.


Como X1 e X2 sao fechados logo X3 contem todos os seus pontos limites e tambem e fechado.Os resultados acima mostram que a intersecao de um, numero finito de hiperplanos, ou de semi-espacos

ou de ambos, e um conjunto convexo fechado.Uma combinacao convexa de um numero finito de pontos x1, . . . ,xm e definida como

x =m∑i=1

µixi, µi ≥ 0, i = 1, . . . ,m;m∑i=1

µi = 1 (6.42)

O poliedro convexo gerado por n+1 pontos em En que nao pertenca a um hiperplano e chamado simplex.Em E2, um triangulo e seu interior formam um simplex. Os tres pontos que geram um simplex sao os

vertices do triangulo.Seja o ponto ω no interior do triangulo como representado na Figura 6.4.

x1

x2

x3

x1

x2

v

w

Figura 6.4: Ponto no interior de um triangulo.

Da Figura e possıvel escrever

v = λ1x1 + (1− λ1)x3; 0 ≤ λ1 ≤ 1 (6.43)

ω = λ2x2 + (1− λ2)v; 0 ≤ λ2 ≤ 1 (6.44)

Substituindo v em (6.44) vem

ω = λ2x2 + (1− λ2)λ2x1 + (1− λ1)(1− λ2)x3 (6.45)

Seja agora,

µ1 = (1− λ2)λ1; µ2 = λ2 e µ3 = (1− λ1)(1− λ2) (6.46)

E obvio que µi ≥ 0 e µ1 + µ2 + µ3 = 1, assim

ω =3∑

i=1

µixi; µi ≥ 0;3∑

i=1

µi = 0 (6.47)

ou seja, os pontos w de um triangulo em E2 representam uma combinacao convexa dos vertices dotriangulo.


6.1.2.6 Teoremas importantes

Nesse item serao listados alguns teoremas sem preocupacao com demonstracoes.

1. Teorema I: Dado qualquer conjunto fechado X, um ponto y ou pertence ao conjunto X, por exemploy1, ou existe um hiperplano que contem y, por exemplo y2, tal que todo o conjunto X esta contidoem um semi-espaco gerado por aquele hiperplano.

A Figura 6.5 esclarece:

x1

x2

y2

y1

X

c yt

1< z

c yt

2 = z

Figura 6.5: Conjunto fechado X limitado por ctx <= z.

E possıvel demonstrar que dado um ponto limite w de um conjunto convexo X, entao, ctx = z echamado um hiperplano suporte de w se ctw = z e se todo o conjunto X estiver contido no semi-espaco fechado produzido pelo hiperplano, isto e, ctu ≥ z, ou entao, ctu ≤ z para todo u ∈ x. AFigura 6.7 esclarece:

2. Teorema II: Se w e um ponto limite de um conjunto convexo fechado, entao ha pelo menos umhiperplano suporte de w.

3. Teorema III: Um conjunto convexo fechado que seja limitado inferiormente tem um ponto extremopertencente a cada hiperplano suporte.

A demonstracao desse teorema sera apresentada aqui devido a sua importancia na compreensao doalgoritmo Simplex de programacao linear.

O hiperplano ctx = z sera suposto como hiperplano suporte de x0 para o conjunto convexo fechadoX, limitado inferiormente.

A intersecao de X e S = {x| ctx = z} sera expressa por T que nao e um conjunto vazio porque x0 ∈ T .Sendo X e S conjuntos convexos fechados, T tambem o sera.

Vamos mostrar que qualquer ponto extremo de T e tambem um ponto extremo de X. Se t e um pontoqualquer de T e, se

t = λx2 + (1− λ)x1; 0 < λ < 1; x1,x2 ∈ x (6.48)


x1

x2

w2

u

X

c ut

< z

c wt

= z

Figura 6.6: Hiperplano suporte de w.

entao

x1,x2 ∈ T

Isso e verdade porque ctt = λctx2 + (1− λ) ctx1 = z

ctx1 ≥ z, ctx2 ≥ z(6.49)

pois ctx e um hiperplano suporte.

Considerando que λ ≥ 0 e 1− λ > 0 pode-se concluir que ctt = z exige que

ctx1 = ctx2 = z (6.50)

ou seja, x1,x2 ∈ T . Assim, se t e um ponto extremo de T , nao existem outros pontos x1 e x2 em Xtais que t possa ser escrito como uma combinacao convexa desses pontos, com 0 < λ < 1. Portanto,um ponto extremo em T e um ponto extremo em X.

6.1.3 Algoritmo Simplex

6.1.3.1 Formulacao do problema de PL

Num problema de PL procura-se encontrar r variaveis nao-negativas xj ≥ 0, j = 1, . . . , r que devem maxi-mizar ou minimizar uma funcao linear

z = c1x1 + c2x2 + · · ·+ crxr (6.51)

satisfazendo m desigualdades ou igualdades lineares da forma

ai1x1 + ai2x2 + · · ·+ airxr{≤ ou = ou ≥}bi, i = 1, . . . ,m (6.52)

supondo-se que todas as constantes aij , bi e cj sejam conhecidas.


x0

x2

X

x1 t

x2 t

= z}S={x | c w

T X S={ }

U

Figura 6.7: Espaco T.

E mais conveniente trabalhar com equacoes de igualdade do que com desigualdades. Por essa razao, asrestricoes de desigualdades em (6.52) sao transformadas em restricoes de igualdade com o uso de variaveis defolga ou de excesso. Outra transformacao que deve ser feita inicialmente e aquela que faz com que todos os bisejam nao-negativos, ou seja, bi ≥ 0. Para tanto, ambos os lados das equacoes com bi < 0 sao multiplicadospor -1 e o sinal e invertido, caso a restricao seja de desigualdade.

Considere-se primeiramente as restricoes de desigualdade do tipo ≤,r∑

j=1

ahjxj ≤ bh (6.53)

E possıvel introduzir no lado esquerdo da desigualdade (6.53) uma variavel nao-negativa xr+h, denomi-nada variavel de folga de modo que a desigualdade pode ser reescrita como igualdade

r∑j=1

ahjxj + xr+h = bh (6.54)

Analogamente, para as restricoes de desigualdade do tipo ≥,r∑

j=1

akjxj ≥ bk (6.55)

pode-se introduzir uma nova variavel nao-negativa xr+h, denominada variavel de excesso e reescrever adesigualdade (6.55) como restricao de igualdade,

r∑j=1

akjxj − xr+k = bk (6.56)

Deste modo, as restricoes originais se transformam num sistema de restricoes de igualdade

r∑j=1

ahjxj + xr+h = bh; h = 1, . . . , u

r∑j=1

akjxj − xr+k = bk; k = u+ 1, . . . , v

r∑j=1

apjxj = bp; p = v + 1, . . . ,m

(6.57)

Na forma matricial o sistema descrito em (6.57) pode ser escrito como

Ax = b (6.58)


onde A e uma matriz m× (r + v), x um vetor (r + v)× 1 e b um vetor m× 1.Observe que o numero de variaveis no problema transformado e igual a r+ v porque foram adicionadas v

variaveis (u de folga e v−u de excesso) as r variaveis iniciais, uma variavel para cada restricao de desigualdade≥ ou ≤.

Como novas variaveis de folga e de excesso foram introduzidas no problema, e necessario atualizar afuncao objetivo z como

z = c1x1 + c2x2 + · · ·+ crxr + 0xr+1 + · · ·+ 0xr+v (6.59)

ou sucintamente,

z =r+v∑j

cjxj (6.60)

ou matricialmente,

z = ctx (6.61)

onde c e x sao vetores colunas (r + v)× 1O problema de PL pode ser agora reescrito de forma sucinta como min ou max z = ctx

s.t Ax = bx ≥ 0

(6.62)

Sendo x e c vetores colunas n× 1, sendo n = r + v, b um vetor coluna m× 1 e A uma matriz m× n.

6.1.3.2 Hipoteses preliminares

De inıcio, as seguintes suposicoes sao admitidas como verdadeiras. r (A) = r (Ab) sendo Ab = (A, b)

r (A) = m(6.63)

onde m e o numero de restricoes.A e a matriz dos coeficientes e Ab a matriz aumentada. Se isto nao for verdadeiro as equacoes sao

inconsistentes e nao ha solucao para o problema de PL.Num problema tıpico de PL ha mais variaveis que restricoes e r(A) = m assegura que nenhuma equacao

e redundante.

6.1.3.3 Reducao de uma solucao compatıvel qualquer para uma solucao compatıvel basica

Nessa secao sera mostrado que se houver uma solucao compatıvel para as equacoes de restricao em (6.62),entao ha uma solucao compatıvel basica (ver eq. (6.22)), ou seja, com nao mais que m variaveis diferentesde zero.

Se r(A) = m, b pode ser escrito como uma combinacao linear de m colunas L.I. de A.Formalmente, pode-se enunciar:Dado esse conjunto de m equacoes lineares simultaneas a n incognitas (n ≥ m)

Ax = b com r(A) = m (6.64)

Entao, se ha uma solucao compatıvel, ou seja, que satisfaca (6.64) e x ≥ 0, ha tambem uma solucaocompatıvel basica xb que satisfaz

Bxb = b (6.65)

sendo B uma matriz m × m formada com m colunas L.I de A e com as demais n − m variaveis de xiguais a zero, com x satisfazendo (6.64).


Seja uma solucao compatıvel com p ≤ n variaveis positivas. Supondo-se que as primeiras p variaveissejam positivas, a solucao compatıvel pode ser escrita

p∑j=1

xjaj = b (6.66)

com

xj > 0 (j = 1, . . . , p) e xj = 0 (j = p+ 1, . . . , n) (6.67)

Os vetores aj sao colunas de A associadas as variaveis xj , podendo ser L.I. ou L.D.Para que os vetores aj sejam L.I, entao p ≤ m ja que r(A) = m.Se p < m, entao ha (m − p) colunas de A que, junto com as p colunas, formam uma base para Em e

produzem uma matriz B, m × m, nao singular. Assim, e possıvel formar uma solucao compatıvel basicadegenerada com (m− p) das variaveis basicas iguais a zero.

Se p = m a solucao compatıvel basica e automaticamente uma solucao compatıvel basica nao degenerada.Resta examinar o caso p > m quando o conjunto dos vetores aj passa a ser L.D.Nessas condicoes e possıvel reduzir passo a passo o numero de variaveis positivas ate que as colunas

associadas as variaveis positivas sejam L.I., ou seja, ate que se tenha m colunas.Quando os aj(j = 1, . . . , p) sao L.D., existe αj nao todos nulos, tal que

p∑j=1

αjaj = 0 (6.68)

Usando a equacao (6.68) e possıvel reduzir algum xr na solucao compatıvel definida em (6.66) a zero.Usando (6.68), qualquer vetor ar para o qual αr = 0 pode ser expresso em termos dos p − 1 vetores

restantes. Assim

ar = −p−1∑j = 1j = r

αj

αraj (6.69)

Substituindo em (6.66), vem:

p−1∑j = 1j = r

(xj − xr

αj

αr

)aj = b (6.70)

ou

p−1∑j = 1j = r

xj .aj = b (6.71)

Em (6.71) temos uma solucao com p-1 variaveis nao-nulas. Entretanto, nao ha certeza de que todas asnovas variaveis xj sejam nao-negativas. Para que a solucao satisfaca plenamente (6.66), ou seja, para queas novas variaveis xj sejam maiores do que zero, ou seja, compatıveis, a escolha da variavel a ser eliminadanao pode ser arbitraria.

O que se deseja e que

xj = xj − xrαj

αr≥ 0 (j = 1, . . . , p) j = r (6.72)

Para qualquer j para o qual αj = 0, (6.72) sera satisfeita automaticamente.Quando αj = 0 as seguintes condicoes devem ser satisfeitas


xj

αj− xr

αr≥ 0 se αj > 0

xj

αj− xr

αr≤ 0 se αj < 0

(6.73)

As equacoes (6.73) podem ser interpretadas como:xj

αjdeve estar entre o menor valor positivo e o maior

valor negativo entre todos o xr

αr.

Desse modo, as equacoes (6.73) serao satisfeitas se

xr

αr= min

j

{xj

αj

}, αj > 0 (6.74)

ou seja, a variavel a ser eliminada deve ser a variavel xr que corresponde ao menor valor dexj

αjcom

αr > 0.Deve haver sempre algum valor positivo de αj . Se todos forem negativos a equacao (6.68) deve ser

multiplicada por −1.Esse procedimento deve ser repetido ate que as colunas correspondentes as variaveis positivas sejam L.I.

quando entao chega-se a solucao compatıvel basica com m variaveis.

6.1.3.4 Algumas definicoes e notacoes

Conforme visto no item 6.1.2.1, as restricoes de um problema de PL sao agora escritas como um conjuntode m equacoes lineares e n incognitas

Ax = b (6.75)

sendo que para que a solucao seja compatıvel todo xj ≥ 0 (j = 1, . . . , n).Seja a matriz B, m ×m, formada com m colunas aj de A. as colunas de B formam uma base para o

espaco Em e ela e nao singular porque suas colunas sao L.I.As colunas de B serao denominadas de b1, . . . ,bm. E importante notar que b1 pode ser qualquer coluna

de A, por exemplo, a17 e o mesmo vale para as outras colunas.Qualquer coluna aj de A pode ser representada como uma combinacao linear das colunas de B ja que

estas formam uma base para o espaco vetorial Em.

aj =

m∑i=1

biyij = Byj (6.76)

ou

yj = B−1aj (6.77)

O vetor yj contem as coordenadas do vetor aj na base B.Qualquer matriz B determina uma solucao basica xb com m componentes

xb = B−1b (6.78)

Correspondendo a cada xb, pode-se obter um vetor cb com m componentes contendo os valores corres-pondentes as variaveis basicas.

Os componentes de cb, ou seja, os cbi correspondem a variavel basica xbi. Se a17 estiver na coluna 2 deB, entao cb2 = c17.

Para qualquer solucao basica xb, o valor da funcao objetivo z e dado por

z = ctb · xb (6.79)

Uma equacao similar a equacao (6.79) pode ser definida como

zj = ctb · yj (6.80)


ja que tanto o vetor cb como yj , sao vetores coluna m× 1.Para cada aj em A e possıvel calcular um vetor yj segundo (6.76) e um zj segundo (6.80). A definicao

de zj sera importante na formulacao do metodo Simplex.

6.1.3.5 Formulacao do metodo Simplex

O metodo Simplex pressupoe que uma solucao compatıvel basica xb e conhecida para o sistema (6.75).A obtencao de uma solucao basica inicial sera discutida mais adiante.Para se obter a solucao basica xb, uma matriz B foi formada com m colunas LI de A.

xb = B−1b (6.81)

Com B e xb e possıvel obter

z = ctb · xb (6.82)

e yj = B−1aj

zj = ctb · yj

(6.83)

para toda coluna aj nao pertencente a B.Sera provado mais adiante que a solucao de um problema de PL e uma solucao compatıvel basica.A ideia basica do Metodo Simplex e:“Partindo-se de uma solucao basica inicial, encontrar uma nova solucao basica com valor da funcao

objetivo correspondente melhorado, ou seja, menor para um problema de minimizacao e maior para umproblema de maximizacao”.

Sabendo, a priori, que a solucao do problema e uma solucao compatıvel basica, uma nova solucao basicadeve ser obtida retirando-se uma coluna da base B e substituindo-a por uma coluna aj fora da base.

Duas duvidas devem ser esclarecidas nesse processo:

1. Qual coluna de B deve sair da base?

2. Qual coluna aj fora da base deve entrar na base?

Para responder a primeira questao e necessario obter as expressoes da nova solucao basica a partir da solucaobasica anterior.

Seja a solucao basica inicial dada por:

m∑i=1

xbibi = b (6.84)

E as colunas fora da aj representadas por

aj =m∑i=1

yijbi (6.85)

Entao, um dado aj , pode substituir um dado br para o que yrj = 0 e o novo conjunto fornecera umanova base.

De (6.85) pode-se escrever:

br =1

yrjaj −

m∑i = 1i = r

yijyrj· bi (6.86)

Substituindo-se a expressao da coluna br dada em (6.86) na expressao (6.84), obtem-se:


m∑i = 1i = r

(xbi − xbr

yijyir

)bi +

xbr

yrjaj = b (6.87)

A nova solucao basica deve ser compatıvel portanto,{xbi = xbi − yij

yirxbr ≥ 0; i = r

xbr = xbr

yrj≥ 0

(6.88)

Nao e possıvel remover qualquer coluna br de B com yrj = 0 e esperar que as condicoes (6.88) sejamsatisfeitas.

Inicialmente, pode-se observar que sendo xbr ≥ 0 deve-se ter yrj > 0 para que a nova variavel xbr ≥ 0.Se aj tem pelo menos um yij > 0, e possıvel remover uma coluna br de B e substituı-la por aj e com a

nova base obter uma solucao basica compatıvel.Se yrj > 0 e os demais yij ≤ 0 (i = r) em (6.88) entao, a nova solucao basica e automaticamente

compatıvel.Quando houver houver mais de um yij > 0, a seguinte condicao deve ser satisfeita para todo yij > 0 para

que a nova solucao basica seja compatıvel

xbi

yij− xbr

yrj≥ 0 (6.89)

Essa condicao corresponde a primeira das condicoes (6.88) quando se divide a expressao pelo valor positivoyij .

Se escolhermos a coluna br a ser removida usando a condicao dada a seguir

xbr

yrj= min

i

(xbi

yij, yij > 0

)= θr. (6.90)

entao, a nova solucao basica sera compatıvel.O que a expressao (6.90) define e:“Se a coluna aj for escolhida para entrar na base, a coluna br, escolhida segundo o criterio definido por

(6.90), deve sair da base para que a nova solucao basica seja compatıvel”.A pergunta (a) esta respondida, mas nao a pergunta (b) pois nao esta definido qual coluna aj deve entrar

na base no lugar de br.Essa resposta sera dada ao examinarmos qual coluna aj corresponde ao melhor valor da funcao objetivo

z.O valor da funcao objetivo para a solucao basica original e

z = ctbxb =m∑i=1

cbixbi (6.91)

O novo valor da funcao objetivo para a nova solucao compatıvel basica e

z =

m∑i = 1i = r

cbi

(xbi − xbr

yijyrj

)+

xbr

yrjcj (6.92)

Esse novo valor foi obtido de,

z = ctb · xb =

m∑i=1

cbixbi (6.93)

Observe que cbi = cbi (i = r) e cbr = cj .

E conveniente incluir no somatorio em (6.92) o termo nulo


cbr

(xbr − xbr

yrjyrj

)= 0 (6.94)

o que permite escrever

z =

m∑i=1

cbi

(xbi − xbr

yijyrj

)+

xbr

yrjcj (6.95)

ou

z =m∑i=1

cbixbi −xbr

yrj

(m∑i=1

cbiyij - cj

)(6.96)

ou ainda

z = z +xbr

yrj(cj − zj) (6.97)

e, finalmente, considerando (6.90),

z = z + θr (cj − zj) (6.98)

Se o problema de PL for de maximizar z entao z deve ser maior que z para se ter uma nova solucaobasica melhorada, ou seja, θr (cj − zj) > 0. Como θr ≥ 0 entao e suficiente que

cj − zj ≥ 0 (6.99)

para que z > zA expressao (6.98) vai responder a pergunta (b), ou seja, qual coluna aj deve entrar na base.Para se obter o maior crescimento de z a coluna a entrar na base deve ser aquela que fornecer o maior

valor para

θr (cj − zj) (6.100)

Para que a escolha nao dependa tambem da coluna br a ser retirada, e possıvel usar simplificadamentea expressao (6.99) no lugar de (6.100) para definir qual coluna aj deve entrar na base, ou seja, aquele quefornecer o maior valor de cj − zj .

Caso todos os cj − zj sejam negativos e de se esperar que a solucao otima tenha sido encontrada pois naosera mais possıvel aumentar o valor de z. Essa suspeita sera demonstrada no item 6.1.3.7.

Exemplo:

max 3x1 + 2x2 + x3

s.t.

[3 2 23 4 1

] x1

x2

x3

=

{87

}ou seja

c =

321

A =

[3 2 23 4 1

]e

b =

{87

}


Seja a matriz B formada com as colunas a3 na coluna 1 e a2 na coluna 2.

B =

[2 21 4

]

B−1 =1

6

[4 −2−1 2

]a solucao basica correspondente e compatıvel.

xb = B−1b =

{31

}e

y1 = B−1a1 =

{11/2

}o vetor cB e formado com os valores do vetor c correspondentes as colunas 3 e 2 que formaram a matriz B.Assim

cb =

{12

}A unica coluna fora da base e a1, logo,

z = ctbxb = 5

z1 = ctby1 = 2

e

c1 − y1 = 1

Como c1 − z1 ≥ 0 e possıvel ainda melhorar o valor de z com uma nova solucao basica.Determinacao da coluna a ser removida da base:

xbr

yr1= min

(xbi

yij, yi1 > 0

)ou

xbr

yr1= min

(xb1

y11=

3

1;xb2

y21=

11/2

)= 2

o que significa que a coluna 2 em B e que deve ser substituıda pela coluna 1 de A fornecendo a novamatriz base B.

B =

[2 31 3

]e B−1 =

1

3

[3 −3−1 2

]

xb = B−1b =

{12

}

cb =

{13

}(6.101)

e

z = ctbxb = 7 > z = 5 (6.102)

A nova solucao basica com z > z.


6.1.3.6 Solucoes ilimitadas

A Figura 6.2(a) do item 6.1.1 mostra que e possıvel se ter uma solucao ilimitada para um problema da PL.O algoritmo Simplex e capaz de indicar quando o problema tem solucao ilimitada.Seja uma coluna aj fora da base para a qual todo yij < 0, i = 1, . . . ,m.Seja a solucao basica

m∑i=1

xbibi = b (6.103)

e o valor da funcao objetivo correspondente

z = ctbxb (6.104)

Somando e subtraindo θaj , θ qualquer escalar, em (6.103) vem

m∑i=1

xbibi − θaj + θaj = b (6.105)

mas

−θaj = −θm∑

m=1

yijbi (6.106)

logo, substituindo (6.106) em (6.105),

m∑i=1

(xbi − θyij)bi + θaj = b (6.107)

Quando θ > 0, e todo yij < 0 entao (6.107) representa uma solucao compatıvel para a qual m+1 variaveispodem ser diferentes de zero, nao sendo em geral uma solucao basica.

O valor de z para essa solucao seria

z =∑

cixi =m∑i=1

cbi (xbi − θyij) + cjθ (6.108)

ou

z = z + θ (cj − zj) (6.109)

Para θ suficientemente grande, z pode ser arbitrariamente grande se cj − zj > 0 e arbitrariamentepequeno se cj − zj < 0. Entao, nesse caso, existem solucoes compatıveis nas quais (m + 1) variaveispodem ser diferentes de zero, com o valor da funcao objetivo sendo arbitrariamente grande (cz − zj > 0) ouarbitrariamente pequeno(cj − zj < 0). Diz-se que em tal caso o problema tem uma solucao ilimitada.

Em resumo: o problema de PL tera uma solucao ilimitada se houver uma coluna aj fora da base B paraa qual

yij ≤ 0 (i = 1, . . . ,m) e cj − zj > 0 ou cj − zj < 0 (6.110)

6.1.3.7 Condicoes de otimizacao

Seja uma solucao compatıvel basica que satisfaz

Bxb = b (6.111)

para o problema de PL dado a seguir:


max z = ctxs.t

Ax = bx ≥ 0

(6.112)

O valor da funcao objetivo para a solucao compatıvel basica sera

zo = ctbxb (6.113)

Alem disso, seja cj − zj ≤ 0 para toda coluna aj de A nao pertencente a matriz B da base.

E possıvel mostrar entao que z0 e o valor maximo da funcao objetivo z.Seja uma solucao compatıvel do problema (6.112) dada por

xj ≥ 0; j = 1, . . . , n; x1a1 + · · ·+ xnan = b (6.114)

O valor correspondente da funcao objetivo, expresso por z∗, e

z∗ = c1x1 + · · ·+ cnxn (6.115)

Qualquer vetor aj pertencente a matriz A pode ser escrito como uma combinacao linear dos vetores dabase B.

aj =m∑i=1

yij · bi (6.116)

Substituindo (6.116) em (6.114), vem:

x1

m∑i=1

yi1 · bi + · · ·+ xn

m∑i=1

yinbi =b (6.117)

Ou, reagrupando: n∑j=1

xjy1j

b1 + · · ·+

n∑j=1

xjymj

bm = b (6.118)

no entanto, reescrevendo (6.111), como

xb1b1 + · · ·+ xbmbm = b (6.119)

E comparando (6.119) com (6.118), verifica-se que:

xbi =n∑

j=1

xjyij ; i = 1, . . . ,m (6.120)

Por hipotese, zj ≥ cj para toda coluna de A nao pertencente a base. Para as colunas de A pertencentesa base pode-se afirmar que

yj = B−1aj = B−1Bei = ei (6.121)

Se aj estiver na coluna i de B. assim,

zj = ctbyj = ctbei = cbi = cj (6.122)

logo, para as colunas aj que formam a base B

zj − cj = 0 (6.123)


e, devido a hipotese inicial de que zj ≥ cj para as colunas fora da base B, verifica-se que a hipotese everdadeira para todas as colunas de A, as que pertencem e as que nao pertencem a base B.

Consequentemente, se zj ≥ cj ; para todo j, e possıvel afirmar que, se zj substituir cj em (6.115), entao

z1x1 + · · ·+ znxn ≥ z∗ (6.124)

ja que para uma solucao compatıvel xj ≥ 0 para todo j.Usando a definicao de zj

zj =m∑i=1

cbiyij (6.125)

em (6.124), e reagrupando, vem:n∑

j=1

xjy1j

cb1 + · · ·+

n∑

j=1

xjymj

cbm ≥ z∗ (6.126)

e usando (6.120)

xb1cb1 + · · ·+ xbmcbm ≥ z∗ (6.127)

Observe agora que o somatorio do lado esquerdo da expressao (6.127) e igual a z0 conforme definido em(6.113), logo,

zo ≥ z∗

Isto prova que z0 e, pelo menos, tao grande quanto z* que corresponde ao valor da funcao objetivo paraqualquer outra solucao compatıvel do problema (6.112) e por isso, uma vez obtida, a solucao compatıvelbasica xb com cj − zj ≤ 0 para todas as colunas aj fora da base, essa solucao e a que maximiza z.

6.1.3.8 Alternativa otima

O valor otimo da funcao objetivo para qualquer problema de PL e unico, mas o conjunto de variaveis queproduz o valor otimo da funcao objetivo nao e necessariamente unico.

Sejam k diferentes solucoes compatıveis basicas xb1,xb2, . . . ,xbk que sejam tambem otimas.Seja qualquer combinacao convexa dessas solucoes

x =k∑

i=1

µixbi, µi ≥ 0, i = 1, . . . , k,k∑

i=1

µi = 1; (6.128)

Ja que cada xbi ≥ 0 e µi ≥ 0 segue que x ≥ 0.Alem disso, como para cada i, Axbi = b, vem

Ax = Ak∑

i=1

µixbi =k∑

i=1

µiAxbi =k∑

i=1

µib = b (6.129)

e portanto x definindo em (6.128) e tambem uma solucao compatıvel, mas nao necessariamente basica.Se,

zo = max z = ctxbi; i = 1, . . . , k (6.130)

o valor da funcao objetivo para x e

ctx = ctk∑

i=1

µixbi =k∑

i=1

µictxbi =

k∑i=1

µizo = zo (6.131)

portanto x e tambem uma solucao otima.


Em resumo, pode-se enunciar que:“Se xb1,xb2, . . . ,xbk sao k solucoes compatıveis basicas otimas diferentes para um problema de PL, entao,

qualquer combinacao convexa dessas solucoes sera tambem uma solucao otima”.Isso mostra que se houver duas ou mais solucoes compatıveis basicas otimas, havera um numero infinito

de solucoes otimas nao necessariamente basicas.

xb1

x2

x

xb2

a x3 3

=b

a x1 1

=b

a x2 2

=b

x x= +m1 b1

m2 b2x

Figura 6.8: Alternativa Otima.

6.1.3.9 Pontos extremos e solucoes compatıveis basicas

Nesse item sera mostrado que toda solucao compatıvel basica e um ponto extremo do conjunto convexode solucoes compatıveis, e que todo ponto extremo e uma solucao compatıvel basica para o conjunto derestricoes.

Seja a solucao compatıvel basica, xb, m× 1

xb = B−1b (6.132)

e o vetor x

x =

{xb

0

}; Ax = b; (6.133)

onde x e n× 1, A, m× n e b, m× 1.Para demonstrar que x e um ponto extremo deve-se mostrar que nao existem duas solucoes compatıveis

diferentes, x1 e x2, tal que

x = λx1 + (1− λ)x2; 0 < λ < 1 (6.134)

Admitindo-se que existam essas solucoes compatıveis

x1 =

{u1

v1

}e x2 =

{u2

v2

}(6.135)

sendo u1 e u2 vetores m× 1 e v1 e v2 vetores (n−m)× 1.Substituindo x dado em (6.133), e x1 e x2, dados em (6.135) na expressao (6.134) vem{

xb

0

}= λ

{u1

v1

}+ (1− λ)

{u2

v1

}(6.136)


Examinando o segundo grupo de equacoes em (6.136), ou seja

0 = λv1 + (1− λ)v2 (6.137)

Pode-se afirmar que v1 = v2 = 0 pois λ e (1− λ) ≥ 0 e v1, v2 ≥ 0. Assim,

Ax1 = Bu1 = b e Ax2 = Bu2 = b (6.138)

Como o vetor que representa as coordenadas do vetor b na base B e unico, entao

xb = u1 = u2;x = x1 = x2 (6.139)

Os argumentos acima mostram que nao existem solucoes compatıveis diferentes de x de tal modo que(6.134) seja satisfeita.

Consequentemente, x e um ponto extremo, isto e, qualquer solucao compatıvel basica e um ponto extremodo conjunto de solucoes compatıveis.

Para mostrar que qualquer ponto extremo x∗ = {x1, . . . ,xn} do conjunto de solucoes compatıveis e umasolucao basica, deve-se provar que os vetores associados aos componentes positivos de x∗ sao L.I.

Supondo k componentes de x∗ nao nulos

Ax∗ =k∑

i=1

x∗i ai = b; x∗

i > 0; i = 1, . . . , k (6.140)

Se os vetores colunas ai forem L.D., entao existem k valores λi, nao todos nulos, tal que

k∑i=1

λiai = 0 (6.141)

Agora, suponha que

η = mini

x∗i

|λi|, λi = 0, i = 1, . . . , k (6.142)

Observe que η e um numero positivo. Seja ε um valor tal que, 0 < ε < η, entao,

x∗i + ελi > 0 e x∗

i − ελi > 0; i+ 1, . . . , k (6.143)

Seja um vetor coluna λ com n componentes diferentes de zero que tenha os λi nas k primeiras posicoese zero nas demais (n− k) componentes, entao, observando (6.143), pode-se escrever{

x1 = x∗ + ελx2 = x∗ − ελ

(6.144)

,alem disso, devido a (6.141),

Aλ = 0 (6.145)

logo {Ax1 = Ax∗ + εAλ = bAx2 = Ax∗ − εAλ = b

(6.146)

Segue que x1 e x2 sao solucoes compatıveis diferentes de x∗, e

x∗ =1

2x1 +

1

2x2 (6.147)

Isto contradiz o fato de que x∗ seja um ponto extremo.Por isso, as colunas de A associadas aos componentes nao-nulos de qualquer ponto extremo do conjunto

convexo de solucoes compatıveis devem ser L.I. Nao pode haver mais do que m colunas L.I. em A, e por issoum ponto extremo nao pode ter mais do que m componentes positivas.

Em resumo, toda solucao compatıvel basica para Ax = b e um ponto extremo do conjunto convexo desolucoes compatıveis e todo ponto extremo e uma solucao compatıvel basica.


6.1.3.10 Solucao compatıvel basica inicial

O ponto de partida na solucao de problemas de PL pelo Metodo Simplex e uma solucao compatıvel basicainicial xb. Essa solucao inicial corresponde a uma dada matriz basica B formada por m colunas L.I. damatriz das restricoes A, sendo m o numero de linhas de A ou de restricoes do problema.

Bxb = b (6.148)

Encontrar uma matriz B com m colunas da A que sejam L.I., nem sempre e um problema trivial.Consequentemente, tambem nao e uma tarefa simples encontrar uma solucao compatıvel basica inicial deum problema de PL.

Como vimos nos itens anteriores, uma vez encontrada uma solucao compatıvel basica inicial, o algoritmoSimplex pode encontrar, em cada nova iteracao, uma nova solucao compatıvel basica que corresponde a umvalor “melhorado” da funcao objetivo em relacao ao valor da iteracao anterior e assim sucessivamente.

Em teoria, o processo leva a solucao do problema de PL como visto anteriormente, ja que, pelo menos,uma das solucoes compatıveis basicas e uma solucao possıvel do problema de PL.

Um problema de PL para o qual, uma solucao compatıvel basica pode ser facilmente encontrada e aqueleque, na formulacao original, todas as restricoes sao de desigualdade do tipo menor ou igual. Para esse tipode problema, uma variavel de folga e adicionada a cada restricao de desigualdade para transforma-la emrestricao de igualdade no problema modificado. Nesse caso a matriz A gerada pode ser escrita como,

A = (R, I) (6.149)

sendo I uma matriz identidade de ordem m ( numero de restricoes de desigualdade do problema original) e R a matriz dos coeficientes das incognitas nas restricoes de desigualdade do problema original.

O vetor das incognitas x deve ser reescrito entao como,

x = (xr,xs) (6.150)

onde xr contem as variaveis do problema original e xs as variaveis de folga introduzidas em cadarestricao de desigualdade.

Ao fazer xr = 0 em Ax = b, vem,

Ixs = b (6.151)

O vetor xs representa uma solucao compatıvel basica para o problema modificado correspondente a B = Ija que ele satisfaz (6.151) o que assegura tambem que xs ≥ 0, pois xs = b e b ≥ 0.

Nesse caso os vetores yj serao,

yj = B−1aj = Iaj = aj ; j = 1, . . . , n (6.152)

Como os custos associados as variaveis de folga sao nulos,

cb = 0; (6.153)

consequentemente, o valor inicial da funcao objetivo z e zero.Para o tipo de problema mencionado, uma solucao compatıvel basica inicial pode ser facilmente encon-

trada. Todavia, na grande maioria dos casos, nenhuma matriz de identidade quadrada aparecera na matrizA do problema modificado ao se transformar as restricoes de desigualdade do problema original em restricoesde igualdade no problema modificado.

Uma maneira de contornar esse problema e atraves do uso de variaveis artificiais. Considerando queja foi obtida a matriz de restricoes A do problema modificado via uso de variaveis de folga e de excesso noproblema original, vale,

Ax = b (6.154)

Com o uso das variaveis artificiais a expressao (6.154) pode ser reescrita como,


Axr + Ixa = b; (6.155)

onde xa e o vetor das variaveis artificiais m × 1, I e uma matriz identidade m × m e xr o vetor dasvariaveis originais n×1 de (6.149). Seja M um numero grande e i um vetor m×1 com todas as componentesiguais a 1.

Seja o problema original dado por, max z = ctxs.t Ax = b

x ≥ 0(6.156)

e o problema modificado com o uso das variaveis artificiais dado por,

max z = ctxr −M itxa

s.tAxr + Ixa = bxr ≥ 0;xa ≥ 0;

(6.157)

O vetor das variaveis no problema (6.157) e xr, xa. Uma solucao compatıvel basica inicial para o problemamodificado (6.157) pode ser xb = 0, xa que satisfaz as restricoes em (6.157), ja que xa = b e b ≥ 0.

Vale observar ainda que a solucao do problema (6.157) e a mesma solucao do problema (6.156) uma vezque, na solucao de (6.157) o vetor das variaveis artificiais xa deve ser nulo de modo a maximizar z. Comxa = 0, os dois problemas sao identicos, mas em (6.157), uma solucao compatıvel basica inicial pode serfacilmente encontrada, o que nao acontece com (6.156).

O metodo descrito acima para se obter uma solucao compatıvel basica inicial e conhecido como Metodode Charnes.

Esse metodo apresenta algumas dificuldades. A primeira delas e a escolha do valor de M. Se ele formuito maior do que os coeficientes da matriz A do problema, podem surgir problemas numericos durante aresolucao pelo Metodo Simplex e uma resposta incorreta pode ser obtida. Outra dificuldade e o aumentosignificativo do numero de variaveis no problema modificado (6.157) em relacao ao problema original (6.156).

Um metodo alternativo para a obtencao da solucao compatıvel basica inicial do problema de PL quecontorna alguns dos problemas do Metodo de Charnes e o Metodo das Duas Fases desenvolvido por Dantziget all.

Na primeira fase desse metodo, o seguinte problema e resolvido,

max z = −it xa

s.tAxr + Ixa = b

xr ≥ 0; xa ≥ 0;

(6.158)

A solucao compatıvel basica inicial desse problema pode ser a mesma solucao compatıvel basica inicialdo problema (6.157), ou seja, xb = {0,xa}.

Ao se resolver o problema (6.158), o vetor xa sera nulo e a solucao x∗r sera uma solucao compatıvel basica

tambem para o problema original, mas nao a solucao compatıvel basica otima do problema original, uma vezque as funcoes objetivas dos dois problemas (6.156) e (6.158) sao diferentes. Ela pode, todavia ser adotadacomo solucao compatıvel basica inicial para o problema original.

Na segunda fase do metodo, o problema original e resolvido usando a solucao otima de (6.158) comosolucao compatıvel basica inicial.

Em resumo, as duas fases seriam,Fase I: resolve-se o problema dado a seguir,

max z = itxa

s.t Axr + Ixa = bxr ≥ 0;xa ≥ 0;

Fase II: resolve-se o problema original dado a seguir usando como solucao compatıvel basica inicial a

solucao otima do problema da fase I.


max z = ctxs.t. Ax = b

x ≥ 0

6.2 O Problema de Programacao Quadratica (PQ)

O problema de programacao quadratica e definido como,

min q (x) =1

2xtQx+ f tx

s.t. Ntx = nAtx ≥ b

(6.159)

Onde,x e o vetor das variaveis n× 1,Q e uma matriz quadrada n× n positiva-definida,f um vetor n× 1,N uma matriz p× n (p restricoes de igualdade),A uma matriz m× n (m restricoes de desigualdade),n um vetor p× 1 eb um vetor m× 1.

O problema de PQ se caracteriza, portanto por uma funcao objetivo q(x) quadratica e restricoes lineares.No problema padrao de PQ existem apenas restricoes de desigualdade lineares e as variaveis sao positivas.Ele pode entao ser escrito na seguinte forma,

min q (x) =1

2xtQx+ f tx

s.t. Atx ≥ bx ≥ 0

(6.160)

6.2.1 Eliminacao de restricoes de igualdade

Em geral, qualquer problema de programacao quadratica pode ser colocado na forma padrao eliminando-seas restricoes de igualdade e transladando-se as variaveis para que elas se tornem positivas. Uma operacaoinversa a translacao permite recuperar o valor inicial das variaveis. Nesse item sera mostrado como e possıveleliminar as restricoes de igualdade lineares via inversa generalizada.

Seja a restricao de igualdade dada por (com n ≥ m):

Atm×nxn×1 = bm×1

Sejam e as matrizes,

An×m, Sn×m e Zn×(n−m)

Sendo que,

Atm×nSn×m = Im×m

Atm×nZn×(n−m) = 0m×(n−m)

Onde Im×m e uma matriz identidade e 0m×(n−m) uma matriz nula. Nesse caso, diz-se que Sn×m e ainversa generalizada a direita de At

m×n (ou que a matriz Stm×n e a inversa generalizada a esquerda de

An×m) e que Zn×(n−m) e a matriz do espaco nulo de Atm×n.

E possıvel mostrar que o vetor das variaveis xn×1 pode ser escrito como,

xn×1 = Sn×mbm×1 + Zn×(n−m)y(n−m)×1 (6.161)

6.2. O PROBLEMA DE PROGRAMACAO QUADRATICA (PQ) 89

Ou seja, o vetor xn×1, com n variaveis, pode ser escrito em funcao do vetor y(n−m)×1 com n − mvariaveis independentes sendo m ≤ n. Em outras palavras, o vetor xn×1 pode ser eliminado do problema dePQ geral com restricoes de igualdade e substituıdo pela expressao acima na funcao objetivo e nas restricoesde desigualdade, levando a um problema de PQ padrao com restricoes de desigualdade apenas e n − mvariaveis. As duas parcelas da expressao acima a direita do sinal de igual sao chamadas respectivamente desolucao particular (a primeira) e solucao homogenea (a segunda). Para mostrar que o vetor xn×1 definidoacima satisfaz a restricao de igualdade, basta substituir xn×1 nessa equacao e observar as propriedades dasmatrizes Sn×m e Zn×(n−m) em relacao a At

m×n.

Atm×nxn×1 = At

m×n

(Sn×mbm×1 + Znx(n−m)y(n−m)x1

)= bm×1 (6.162)

Uma tecnica muito utilizada para obter as matrizes Sn×m e Zn×(n−m) e a partir da decomposicao QRou de Householder da matriz An×m. O algoritmo de fatorizacao QR pode ser encontrado no livro de Klaus-Jurgen Bathe [10]. A fatorizacao QR-Householder decompoe a matriz An×m em,

An×m = Qn×n

[Rm×m

0(n−m)×m

]n×m

=[Q1n×m Q2n×(n−m)

]n×n

[Rm×m

0(n−m)×m

]n×m

(6.163)

logo,

An×m = Q1n×mRm×m (6.164)

onde Q e uma matriz ortogonal n× n (QtQ = I), R e uma matriz triangular superior m×m, Q1 e umasubmatriz n×m deQ ortogonal, (Q1

tQ1 = I) eQ2 e uma submatriz n×(n−m) deQ ortogonal, (Q2tQ2 = I).

Alem disso,

QtQ =

{Q1

t

Q2t

}{Q1 Q2

}=

[Q1

tQ1 Q1tQ2

Q2tQ1 Q2

tQ2

]=

[I 00 I

] (6.165)

Vale notar que, devido a ortogonalidade de Q,

Q1tQ2 = 0m×(n−m) e Q2

tQ1 = 0(n−m)×m (6.166)

e que,

Q1tQ1 = Im×m e Q2

tQ2 = I(n−m)×(n−m) (6.167)

Vamos verificar o produto

R−1Q1tA (6.168)

Como, de (6.164)

A = Q1R (6.169)

Vem,

R−1Q1tA = R

−1Q1

tQ1R = R−1R = I (6.170)

Por outro lado, vamos verificar agora o produto,

AtQ2 (6.171)


De novo, considerando a decomposicao de A, dada em (6.164),

AtQ2 = RtQ1tQ2 = 0, (6.172)

Sendo assim, observando (6.170), podemos dizer que,

St = R−1Q1t (6.173)

Pois,

AtS = StA = R−1Q1tA = I (6.174)

e,

Z = Q2 (6.175)

Pois, obersevando (6.172),

AtZ = AtQ2 = 0 (6.176)

6.2.2 Problemas de Programacao Linear Complementar (PLC)

Vimos que um problema de PQ padrao e definido como,

min q (x) =1

2xtQx+ f tx

s.t. Atx ≥ bx ≥ 0

(6.177)

Vamos agora introduzir os multiplicadores de Lagrange y e u associados respectivamente ao primeiro esegundo grupo de restricoes e obter a funcao lagrangeana do problema,

L (x,y,u) = 1

2xtQx+ f tx− yt

(Atx− b

)− utx (6.178)

As condicoes se K-K-T do problema acima sao,

dL (x,y,u)dx

= 0; u−Qx+Ay = f ;

Atx− b ≥ 0; y ≥ 0;x ≥ 0; u ≥ 0;

yt (Atx− b) = 0; utx = 0;

(6.179)

Introduzindo vetores v e t com variaveis de folga positivas, vem,

u−Qx+Ay = f (6.180)

Atx− b− v = 0; y ≥ 0; v ≥ 0 (6.181)

x− t = 0; u ≥ 0; t ≥ 0 (6.182)

yt(Atx− b

)= 0; utx = 0; vty = 0 (6.183)

Podemos agora definir,

w =

{uv

}; z =

{xy

}; q =

{f−b

}; M =

[Q −AAt 0

]; (6.184)

E as condicoes de K-K-T podem ser reescritas de forma compacta, simplesmente como,


w = q+Mz (6.185)

w ≥ 0 ; z ≥ 0 ; wtz = 0 ; (6.186)

O problema definido acima e denominado Problema Linear Complementar (PLC), e ele corresponde ascondicoes de K-K-T do problema quadratico padrao. Um dos algoritmos mais eficientes para resolver esseproblema e o algoritmo de Lemke.

6.2.3 Algoritmo de Lemke para a solucao do PLC

O conjunto w, z e uma solucao do PLC se, e somente se, ele satisfizer a equacao basica,

w = q+Mz (6.187)

A solucao e viavel se, e somente se, o conjunto satisfizer ainda as restricoes de nao-negatividade e serestritamente complementar,

w ≥ 0 ; z ≥ 0 ; wtz = 0 (6.188)

O vetor z contem as variaveis nao-basicas e w as basicas. Chamemos de L o conjunto de solucoes e deK o conjunto de solucoes viaveis. Estamos interessados em encontrar solucoes para descricoes equivalentesde K. As descricoes equivalentes de K podem ser encontradas usando-se pivoteamento em um par pivotwr, zr, ou seja, executar troca de posicao dos elementos do par pivot na equacao basica, zr se torna umavariavel basica, e wr nao-basica. O par pivot nao pode ser escolhido arbitrariamente porque senao a solucaonao sera viavel.

6.2.3.1 Esquema de Pivoteamento de Lemke

O esquema de pivoteamento de Lemke permite encontrar a solucao viavel de um PLC.Considere uma variavel escalar adicional z0 e um vetor coluna com todos os elementos iguais a 1 e com a

mesma dimensao n de w e z. A equacao basica do PLC e entao modificada fornecendo um PLC aumentadocom uma equacao basica aumentada como indicado a seguir,

w = q+Mz+ ez0 (6.189)

onde e e um vetor coluna unitario.O novo conjunto de variaveis nao-basicas tem entao n + 1 componentes, sendo n componentes em z e

mais z0. As novas equacoes basicas aumentadas podem ser reescritas como,

w = q+M′z

′(6.190)

Sendo,

M′=[M e

](6.191)

e

z′=

{zz0

}(6.192)

O esquema de pivoteamento de Lemke gera uma sequencia de solucoes viaveis para o problema aumentadoque nao sao necessariamente solucoes do problema original. E possıvel demonstrar que nenhuma solucaoocorre duas vezes durante o esquema, logo ele e proprio. O esquema tem inıcio transformando z0 de umavariavel basica em nao-basica de modo a obter uma nova solucao viavel para o problema aumentado. Para tale preciso encontrar um par pivot apropriado para z0. Pivoteamentos sao feitos sucessivamente, tomando-seo cuidado de sempre obter uma nova solucao viavel. O esquema termina quando z0 volta a ser uma variavelnao-basica quando entao a solucao do PLC aumentado e solucao tambem do PLC original.


O exemplo a seguir esclarece. Seja o PLC original, w1

w2

w3

=

−302

+

2 −1 1−1 2 1−1 −1 0

z1z2z3

(6.193)

O problema aumentado correspondente com o vetor coluna unitario e e a variavel nao-basica z0, seria, w1

w2

w3

=

−302

+

2 −1 1 1−1 2 1 1−1 −1 0 1

z1z2z3z0

(6.194)

Inicializacao

z1 = z2 = z3 = 0 (6.195)

Logo,

w = q+ ez0 (6.196)

Determinacao do par pivot,

Primeira linha; −3 + 1z0 = 0→ z0 = 3;Segunda linha; 0 + 1z0 = 0→ z0 = 0;Terceira linha; 2 + 1z0 = 0→ z0 = −2;

Para que o vetor satisfaca w ≥ 0 na primeira iteracao, escolhe-se o maior z0 = 3 e seu par e w1 (primeiralinha). O par pivot e (w1,z0)

Assim, explicitando-se z0 na primeira linha de (6.194), obtem-se: z0 = 3− 2z1 + 1z2 − 1z3 + 1w1

w2 = 0− 1z1 + 1z2 − 1z3 + 1z0w3 = 2− 1z1 + 1z2 − 1z3 + 1z0

(6.197)

Substituindo z0 da primeira expressao acima na segunda e terceira expressao, chega-se a,

z0w2

w3

=

335

+

−2 1 −1 1−3 3 0 1−3 0 −1 1

z1z2z3w1

(6.198)

Observe que, com o pivoteamento, o vetor q se tornou positivo e se mantera assim durante os novospivoteamentos, o que leva a solucoes equivalentes viaveis do PLC aumentado. A solucao, no entanto nao euma solucao complementar estrita porque tanto w1 como z1, que deveriam ser estritamente complementaresna solucao do PLC original, sao nulos. Devemos, portanto, realizar um novo pivoteamento ate encontrar asolucao viavel estritamente complementar. Para se obter complementaridade estrita, z1 ≥ 0,

Primeira linha; 3− 2z1 = 0→ z1 = 3/2Segunda linha; 3− 3z1 = 0→ z1 = 1Terceira linha; 5− 3z1 = 0→ z1 = 5/3

Para que o vetor satisfaca w ≥ 0 a partir da segunda iteracao, escolhe-se o menor z1 positivo, z1 = 1 eseu par e w2 (segunda linha). O par pivot e (w2,z1)

Assim, explicitando-se z1 na segunda linha de (6.198), obtem-se: z0 = 3− 2z1 + 1z2 − 1z3 + 1w1

z1 = 1− 13w2 + 1z2 + 0z3 +

13w1

w3 = 5− 3z1 + 0z2 − 1z3 + 1w1

(6.199)

Substituindo z1 da segunda expressao acima na primeira e terceira expressao, chega-se a,


z0z1w3

=

112

+

2/3 −1 −1 1/3−1/3 1 0 1/31 −3 −1 0

w2

z2z3w1

(6.200)

Agora o par w2, z2 e nulo e devemos fazer novo pivoteamento. Para se obter complementaridade estrita,z2 ≥ 0,

Primeira linha; 1− 1z2 = 0→ z2 = 1Segunda linha; 1 + 1z2 = 0→ z2 = −1Terceira linha; 2− 3z2 = 0→ z2 = 2/3

Para que o vetor satisfaca w ≥ 0, escolhe-se o menor z2 positivo, z2 = 2/3 e seu par e w3 (terceira linha).O par pivot e (w3,z2)

Assim, explicitando-se z2 na terceira linha de (6.200), obtem-se: z0 = 1 + 23w2 − 1z2 − 1z3 +

13w1

z1 = 1− 13w2 + 1z2 + 0z3 +

13w1

z2 = 23 + 1

3w2 − 13w3 − 1z3 + 0w1

(6.201)

Substituindo z2 da terceira da expressao acima na primeira e segunda expressao, chega-se a,

z0z1z2

=

1/35/32/3

+

1/3 1/3 −2/3 1/30 −1/3 −1/3 1/31/3 −1/3 −1/3 0

w2

w3

z3w1

(6.202)

Agora o par w3, z3 e nulo e devemos fazer novo pivoteamento. Para se obter complementaridade estrita,z3 ≥ 0,

Primeira linha; 1/3− 2/3z3 = 0→ z3 = 1/2Segunda linha; 5/3− 1/3z3 = 0→ z3 = 5Terceira linha; 2/3− 1/3z3 = 0→ z3 = 2

Para que o vetor satisfaca w ≥ 0, escolhe-se o menor z3 positivo, z3 = 1/2 e seu par e z0 (primeira linha).O par pivot e (z3,z0)

Assim, explicitando-se z3 na primeira linha de (6.202), obtem-se:z3 =

1

2+

1

2w2 +

1

2w3 −

3

2z3 +

1

2w1

z1 =5

3+ 0w2 −

1

3w3 −

1

3z3 +

1

3w1

z2 =2

3+

1

3w2 −

1

3w3 −

1

3z3 + 0w1

(6.203)

Substituindo z3 da primeira da expressao acima na segunda e terceira expressao, chega-se a,

z3z1z2

=

1/23/21/2

+

1/2 1/2 −3/2 1/2−1/6 −1/2 1/2 1/61/6 −1/2 1/2 −1/6

w2

w3

z0w1

(6.204)

Como z0 voltou ao lado direito da expressao e passa a ser nulo, a solucao alternativa viavel encontradapara o PLC aumentado e tambem solucao viavel do PLC original e o processo iterativo termina. A solucaoe entao,

w2 = w3 = z0 = w1 = 0 (6.205)

e,


z3 =1

2; z1 =

3

2; z2 =

1

2(6.206)

Formando os pares estritamente complementares,

z1 > 0; w1 = 0z2 > 0; w2 = 0z3 > 0; w3 = 0

(6.207)

Capıtulo 7

O Problema Geral de ProgramacaoNao-Linear (PNL)

Para se solucionar o problema geral de Programacao Matematica, ou seja, um problema de ProgramacaoNao Linear (PNL) com restricoes de igualdade, desigualdade e laterais, varios algoritmos tem sido emprega-dos. Alguns sao mais eficientes quando o problema tem predominancia de restricoes de igualdade e outros,ao contrario, quando o numero de restricoes de desigualdade e significativamente maior que o numero derestricoes de igualdade.

Nesse capıtulo serao apresentados varios algoritmos para a solucao de problemas de OCR. Uma discussaosobre a eficiencia dos algoritmos para solucao de cada tipo de problema sera apresentada. Exemplos deaplicacao na Engenharia Civil serao formulados e resolvidos pelos algoritmos propostos.

Como mencionado no capıtulo 4, o problema geral de OCR e definido da seguinte forma:min f(x)

s.t. hk(x) = 0, k = 1 . . .mcl(x) ≤ 0, l = 1 . . . pxl

i ≤ xi ≤ xui, i = 1 . . . n

(7.1)

onde x e o vetor das variaveis de projeto, f(x) a funcao objetivo a ser minimizada, hk(x) as restricoesde igualdade, cl(x) as restricoes de desigualdade, e xl

i e xui, respectivamente, os limites inferior e superior

da variavel xi que definem as restricoes laterais.O problema geral de OCR e resolvido de forma iterativa. Em cada iteracao, um subproblema “s” e

gerado com o resultado da iteracao anterior, doravante denominado x0, e um novo incremento δx para ovetor das variaveis e obtido a partir da solucao do subproblema. Os subproblemas gerados sao do tipo dosproblemas apresentados no Capıtulo 6 (PL e PLC).

Uma vez obtida a solucao do subproblema, o vetor das variaveis x e atualizado com a determinacao dopasso α por meio de uma busca unidimensional, ou seja:

x = x0 + δx e δx = α d (7.2)

onde d e uma direcao de busca. Nesse capıtulo serao apresentados somente metodos de primeira ordem, ouseja, metodos que utilizam os gradientes da funcao objetivo e das restricoes para a definicao do subproblemanuma dada iteracao.

7.1 Metodo de Programacao Linear Sequencial (PLS)

Seja x0 a solucao do subproblema de uma dada iteracao do Metodo PLS. A partir dessa solucao, tanto afuncao objetivo como as restricoes sao aproximadas via expansao em series de Taylor truncadas nos termos deprimeira ordem. O subproblema gerado usando as aproximacoes lineares da funcao objetivo e das restricoes

95

96 CAPITULO 7. O PROBLEMA GERAL DE PROGRAMACAO NAO-LINEAR (PNL)

e um subproblema de Programacao Linear e pode ser resolvido, por exemplo, usando-se o algoritmo Simplex.As variaveis sao entao atualizadas como indicado na Equacao 7.2.

As aproximacoes lineares fornecem:

min f(x) ≈ f(x0) + [∇f(x0)]

ts

s.t.

cl(x) ≈ cl(x0) + [∇cl(x0)]ts ≤ 0 l = 1 . . . p

hk(x) ≈ hk(x0) + [∇hk(x0)]ts = 0 k = 1 . . .m

xli ≤ x0i + si ≤ xu

i; i = 1 . . . n

(7.3)

O vetor s representa as incognitas do problema de PL acima. A Figura 7.1 representa graficamente comoa solucao aproximada do subproblema de duas variaveis e obtida usando-se as aproximacoes lineares a partirde x0.

x1

x2

Aproximaçãolinear para

( )=0c2

x0

( )=0c2

x

( )=0c1

x

Aproximaçãodo ponto ótimo

Ponto ótimoverdadeiro

x0

Figura 7.1: Problema Linearizado.

E possıvel notar que a solucao nao e viavel. Todavia, tal fato nao representa um obstaculo para se obtera solucao do problema original de PNL apos algumas iteracoes. Uma dificuldade para se obter a solucaoaparece quando o problema e subrestringido, ou seja, quando ha mais variaveis que restricoes como indicadona Figura 7.2. Nessa mesma figura estao representados os “limites ao movimento” que sao impostos asvariaveis para se evitar que a regiao viavel das variaveis fique ilimitado. A escolha dos “limites de movimento”assim como dos “fatores de reducao” associados e uma dificuldade no uso do metodo.

7.2. METODO DOS CENTROS 97

x1

x2

x0

Aproximaçãolinear para

( )=0c1

x0

Ponto ótimoverdadeiro

Limitesao movimento

Figura 7.2: Exemplo de Problema Subrestringido.

7.2 Metodo dos Centros

O metodo dos centros foi idealizado como uma alternativa para o metodo PLS que fornece solucoes viaveisem cada subproblema. Obter solucoes viaveis em cada iteracao pode ser desejavel quando se esta resolvendoproblemas reais de engenharia, pois, mesmo que a solucao otima nao tenha sido atingida, a solucao obtidaem cada iteracao pode ser usada uma vez que ela e viavel e de custo inferior ao da solucao inicial.

A ideia basica do Metodo dos Centros e que a solucao s do subproblema leve o vetor x, solucao atualizadado problema original, a partir da solucao inicial x0:

x = x0 + s (7.4)

ao centro da hiperesfera de maior raio inscrita no hiperpoliedro gerado pelas funcoes objetivo e restricoeslinearizadas. A Figura 7.3, para um problema com duas variaveis, ajuda a esclarecer o texto.

Devido a propriedade descrita acima, o Metodo dos Centros e tambem conhecido como Metodo dasHiperesferas Inscritas. O metodo e recomendado quando o problema tem apenas restricoes de desigualdade.


x0

Ñf( )x0

Ñci( )x

Ñck( )x Ñcj( )x

dhj

dhk

dhi

dfs

dx

Linearizaçãode ( )=0ci x

Linearizaçãode f( )x0

Linearizaçãode ( )=0cj x

Linearizaçãode ( )=0ck x

x1

x2

A

Figura 7.3: Ilustracao do Centro da Hiperesfera Inscrita.

Para se obter o ponto x, centro da maior hiperesfera que cabe no espaco viavel linearizado, um subpro-blema adequado deve ser formulado. Inicialmente, calculam-se as distancias df e dhl do centro da referidahiperesfera a funcao objetivo e as restricoes cl(x) linearizados, respectivamente.

Observando-se a Figura 7.3 pode-se verificar que:

df = − [∇f(x0)]t

∥∇f(x0)∥s (7.5)

dhl =[∇cl(x)]

t

∥∇cl(x0)∥(δx− s) (7.6)

Por outro lado, observando-se que o vetor s e o passo dado de x0 ate x no contorno que corresponde arestricao linearizada cl(x) = 0, pode-se escrever:

cl(x) = cl(x0) + [∇cl(x0)]tδx = 0 (7.7)

ou:

[∇cl(x0)]tδx = −cl(x0) (7.8)

logo, considerando-se ainda que:

∇cl(x) = ∇cl(x0) (7.9)

devido a aproximacao linear, tem-se:

dhl = −cl(x0) + [∇cl(x0)]

ts

∥∇cl(x0)∥(7.10)

Seja agora r o raio da maior hiperesfera inscrita no espaco viavel linearizado. Como as distancias doscontornos linearizados ao centro da hiperesfera nao podem ser maiores do que o raio, deve-se ter:

7.3. METODO DAS DIRECOES VIAVEIS 99

r ≤ dhl l = 1 . . . pr ≤ df

(7.11)

usando-se as expressoes 7.5 e 7.6 pode-se formular agora o subproblema do metodo dos Centros, apossimples manipulacoes algebricas, como:

max r

s.t. [∇f(x0)]ts+ ∥∇f(x0)∥ r ≤ 0

[∇cl(x0)]ts+ ∥∇cl(x0)∥ r ≤ −cl(x0) l = 1 . . . p

(7.12)

O subproblema acima e um problema de PL e pode ser resolvido pelo Metodo Simplex. A solucao dosubproblema fornece r e s. O vetor s e utilizado para se obter a solucao final da iteracao por meio de umabusca unidimensional, ou seja:

x = x0 + s (7.13)

As iteracoes terminam quando o valor de r for menor do que uma dada tolerancia. No caso de problemassubrestringidos, o Metodo dos Centros sofre das mesmas restricoes que o Metodo de PLS e necessita dadefinicao de “limites de Movimento” para convergir para a solucao.

7.3 Metodo das Direcoes Viaveis

O Metodo das Direcoes Viaveis e apropriado para problemas com restricoes de desigualdade apenas. Assimcomo os metodos apresentados nos itens anteriores, ele produz uma sequencia de subproblemas a partir dex0, solucao do subproblema gerado na iteracao anterior. Se o ponto x0 nao estiver sobre um contorno daregiao viavel, ou seja, nao ativar uma ou mais restricoes de desigualdade, o subproblema a ser resolvido eum problema de OSR. Todavia, deve ser feito um controle durante as buscas unidimensionais do algoritmode OSR para se garantir que a solucao esteja no espaco viavel, ou seja, que nenhuma restricao seja violada.Nota-se, portanto, que o algoritmo e de pontos interiores e uma solucao inicial viavel deve ser adotada.

Durante uma busca unidimensional duas situacoes sao possıveis: ou se encontra um mınimo dentro daregiao viavel ou se atinge um contorno da regiao viavel ativando uma ou mais restricoes. No primeiro caso,a solucao do problema foi encontrada, o que e pouco provavel ja que solucoes otimas sempre ativam umaou mais restricoes. No segundo caso, ou seja quando x0 esta sobre o contorno da regiao viavel, trata-se debuscar uma direcao viavel e de decrescimo. O subproblema do metodo das direcoes viaveis e formulado parase encontrar uma direcao, conforme ilustrado na Figura 7.4:


Ñf( )x0

Ñc1( )x

( )=0c2 x

( )=0c1 x

x1

x2

s

f( )=const.x

Figura 7.4: Exemplo de Direcoes Viaveis.

A Figura 7.4 auxilia a compreensao das condicoes necessarias para que uma direcao de busca, definida apartir de um ponto sobre o contorno da regiao viavel, seja viavel e de decrescimo.

Para que a direcao de busca s seja uma direcao de decrescimo da funcao objetivo ela deve fazer um angulomaior do que 90o com o vetor gradiente da funcao objetivo no ponto x0, tal como ilustrado na Figura 7.4.Isso significa que o produto interno entre ∇f(x0) e s deve ser negativo, ou seja:

[∇f(x0)]ts < 0 (7.14)

Para que a direcao de busca s seja uma direcao viavel ela deve fazer um angulo maior do que 90o com ovetor gradiente da restricao ativa no ponto x0. Isso significa que o produto interno entre ∇cl(x0) e s deveser negativo, ou seja:

[∇cl(x0)]ts < 0 (7.15)

Observe-se que no setor util viavel, a direcao de busca mais eficiente seria aquela que minimiza a ex-pressao 7.14 e satisfaz e expressao 7.15. Essa direcao pode ser encontrada ao se formular o seguinte subpro-blema a partir do ponto x0:

min [∇f(x0)]ts

s.t. [∇cl(x0)]ts ≤ −θ

(7.16)

onde θ e simplesmente uma constante nao-negativa que assegura que o co-seno do angulo entre ∇cl(x0) es seja estritamente negativo, ou seja, que o angulo entre esses dois vetores seja maior do 90o. O parametro θe denominado “push-off factor”. Esse nome traduz a sua funcao na formulacao que e a de empurrar o vetorda direcao de busca s para fora do plano tangente no contorno que passa pelo ponto x0.

As condicoes 7.14 e 7.15 podem ser reunidas em uma unica condicao ja que a expressao 7.14 deve sernegativa:


[∇cl(x0)− θ ∇f(x0)]ts ≤ 0 (7.17)

Minimizar a expressao 7.14 e equivalente a maximizar β na seguinte desigualdade:

[∇f(x0)]ts+ β ≤ 0 (7.18)

ou ainda:

[∇cl(x0)]ts+ θ β ≤ 0 (7.19)

uma vez que β = − [∇f(x0)]ts para que β seja maximo. Considerando as expressoes acima, o seguinte

subproblema alternativo ao subproblema definido na expressao 7.16, pode ser definido para se encontrar umadirecao util-viavel:

max β

s.t. [∇f(x0)]ts+ β ≤ 0

[∇cl(x0)]ts+ θl β ≤ 0 l = 1 . . . p

∥s∥ ≤ γ

(7.20)

onde “l” sao as restricoes ativas do problema e γ um parametro escalar.

A ultima restricao do subproblema definido em 7.20 procura limitar o modulo do vetor s pois o que sepretende e maximizar o produto interno dos vetores ∇f(x0) e s sem que o modulo de s seja maximizado, oque tambem aumentaria o valor do produto interno.

Algumas questoes ainda precisam ser definidas, tais como:

1. Quando uma restricao de desigualdade esta ativa?

2. Como se escolher os valores de θl?

3. Como limitar o modulo do vetor s, ou seja, qual deve ser o valor de γ ?

As questoes (1) e (2) sao correlacionadas. Em termos numericos, uma restricao esta ativa quando elaesta “proxima” do contorno, ou seja, cl(x) ≥ ε, onde ε pode variar no intervalo [−0.1,−0.001], dependendose as iteracoes estao no inıcio ou no final do processo de solucao do problema. Uma boa expressao para adeterminacao de θl e dada por:

θl(x) =

∣∣∣∣1− cl(x)

ε

∣∣∣∣2 θ0 (7.21)

sendo θ0 = 1.0. A expressao 7.21 mostra que θl(x) varia de 0.0 a cl(x) = ε, ou seja, quando x esta auma distancia ε da superfıcie do contorno ate θl = 1.0, quando cl(x) = 0, ou seja, quando x esta sobre asuperfıcie do contorno. A Figura 7.5 esclarece.


( )=0c x

x1

x2

s( = )q ¥

s( 1)q»

s( = )q 0

f( )=const.x

Figura 7.5: Influencia de θl na Direcao de Busca.

Considera-se que a restricao esta ativa quando θl(x) estiver entre 0.0 e θ0.

Quanto a limitacao do modulo de s, varias estrategias podem ser usadas. E possıvel limitar as compo-nentes do vetor s da seguinte forma:

−1 ≤ si, i = 1 . . . n (7.22)

O uso da expressao 7.22 para limitar o modulo de s tem a vantagem de transformar o subproblema(7.20) em um problema de PL, o que nao aconteceria se o modulo de s, propriamente dito, fosse utilizadona expressao de limitacao do modulo.

Apesar da vantagem apresentada acima o uso da expressao (7.22) apresenta a desvantagem de forcar adefinicao da melhor direcao do vetor s na direcao de um dos vertices do hipercubo de lado 2 e centro emx0 como apresentado na Figura 7.5. Isso acontece porque o modulo de s e maximo no vertice do hipercuboquando se usa a expressao (7.22) para limitar o modulo.

Desse modo, a expressao:

st s ≤ 1 (7.23)

tem sido utilizada pois ela limita o quadrado do raio da hiperesfera a um valor unitario.

A Figura 7.6 esclarece a diferenca das solucoes obtidas nos dois casos, ou seja, com as expressoes (7.22)e (7.23).


( )=0c x

x1

x2

-1 £ sj £ 1

s s× £ 1

s1

s2

f( )=const.x

Figura 7.6: Exemplos de Direcoes de Busca Uteis e Viaveis.

Ao substituir a expressao (7.22) para limitar o modulo do vetor s pela expressao (7.23) o subproblema(7.20) deixa de ser um problema de PL o que torna a sua solucao mais complexa. Alguns autores sugerema conversao do subproblema (7.20) num problema equivalente de PLC por meio do uso das condicoes deKuhn-Tucker.

Reescrevendo o subproblema (7.20) numa forma compacta como indicado a seguir, facilita a tarefa de seobter as condicoes de Kuhn-Tucker, ou seja:

max pt y

s.t. A y ≤ 0yt y < 1

(7.24)

onde:

y =

δx1

δx2

...δxn

β

p =

00...01

(7.25)

A =

[∇c1(x0)]

tθ1

[∇c2(x0)]t

θ2...

...

[∇cp(x0)]t

θp[∇f(x0)]

t1

(7.26)


A ultima equacao em (7.26) e similar a Equacao 8.24. A unica diferenca e que o quadrado do modulo des e limitado a “1− β2”, onde β2 e um pequeno valor positivo, ao inves de ser limitado a 1.

As condicoes de Kuhn-Tucker do subproblema descrito em (7.24) sao:

p = Atλ+ µ′ (2 y) ;A y ≤ 0; yty − 1 ≤ 0;λ ≥ 0; µ′ ≥ 0;

λtAy = 0; µ′ (yty − 1) = 0

(7.27)

onde λ e µ′ sao os multiplicadores de Lagrange associados respectivamente as restricoes Ay ≤ 0 eyt y − 1 ≤ 0.

Seja agora:

µ = −2µ′ e z = −Ay (7.28)

logo, as expressoes 7.26 podem-se ser reescritas como:

p = At λ+ µ yz ≥ 0; yty − 1 ≤ 0;λ ≥ 0; µ ≥ 0λtz = 0; µ (yty − 1) = 0

(7.29)

Pre-multiplicando-se a primeira expressao em (7.29) por “−A” obtem-se:

−Ap = −AAtλ− µAy (7.30)

e considerando-se:

v = −µ A y = µ z

ec = −A p

(7.31)

as expressoes 7.29 podem-se ser reescritas como:−A Atλ+ v = c

z ≥ 0; v ≥ 0;yty − 1 ≤ 0; λ ≥ 0; µ ≥ 0λtv = 0; µ (yty − 1) = 0

(7.32)

Observe-se que ao agrupar algumas das expressoes acima, elas formam um problema de PLC:−A At λ+ v = c

λ ≥ 0; v ≥ 0; λt v = 0;(7.33)

que pode ser resolvido pelo algoritmo de Lemke obtendo-se como resposta os vetores λ e v, sendoconhecidos a matriz AAt e o vetor c. A partir de λ e v e possıvel recuperar o vetor y usando-se a primeiradas expressoes em (7.29), onde µ e arbitrariamente fixado igual a 1, sem comprometer as restricoes e ascondicoes de Kuhn-Tucker.

y = −p−At λ (7.34)

O vetor y representa a solucao do subproblema do Metodo das Direcoes Viaveis pois ele contem o vetors que representa a direcao do passo a ser dado de x0 ate a solucao x da iteracao em questao. Uma buscaunidimensional, a partir de x0, na direcao s, atualiza x.

7.4. METODO DO GRADIENTE REDUZIDO GENERALIZADO (GRG) 105

7.3.1 Solucao Inicial Viavel

O Metodo das Direcoes Viaveis e um metodo de primeira ordem (pois utiliza as primeiras derivadas de f(x)e cl(x) para definir seu subproblema). Foi desenvolvido para problemas que tenham apenas restricoes dedesigualdade e e tambem um metodo de pontos interiores, ou seja, onde todas as solucoes parciais obtidasem cada iteracao bem, como a solucao inicial ‘x0, devem estar contidas na regiao viavel.

Uma questao que surge na aplicacao pratica do metodo e: como se obter uma solucao inicial viavel?

O enfoque basico e formular um subproblema na primeira iteracao que, a partir de um vetor arbitrariox0, permita obter um outro vetor que seja viavel. A ideia basica desse subproblema e desprezar a restricaoque impoe que a solucao do subproblema (7.20) seja util, ou seja, que a solucao forneca uma funcao objetivomenor ou igual a solucao inicial nao viavel x0.

Se uma restricao cl(x0) e radicalmente violada, seu correspondente valor de θl torna-se muito alto. Porrazoes numericas, se θl > 50 considera-se θl = 50.

Considerando-se as observacoes acima, o subproblema definido em (7.35) pode fornecer um passo s queaponte para dentro da regiao viavel a partir de uma solucao inicial nao viavel x0.

7.3.2 Restricoes de Igualdade

Como ja mencionado, o Metodo das Direcoes Viaveis e basicamente um metodo para problemas com apenasdesigualdades. Uma maneira de utilizar o metodo em problemas que tambem apresentem restricoes deigualdade e converter essas restricoes em desigualdades equivalentes, conforme indicado a seguir:

min ϕ(x) = f(x)−l∑

k=1

rkhk(x)

hk(x) ≤ 0; k = 1 . . . l

(7.35)

onde hk(x) sao restricoes de igualdade no problema original que se transformaram em restricoes dedesigualdade no novo problema equivalente. Valores de rk recomendados da pratica podem ser obtidos por:

rk =10 ∥∇f(x0)∥∥∇hk(x0)∥

(7.36)

Os rk sao numeros grandes, positivos e agem como um fator de penalidade para empurrar x para hk(x) =0, enquanto se minimiza ϕ(x), ja que hk(x) deve ser sempre menor ou igual a zero. ϕ(x) e chamado de funcaopseudo-objetivo.

7.4 Metodo do Gradiente Reduzido Generalizado (GRG)

O Metodo do Gradiente Reduzido Generalizado e uma extensao de um metodo de gradiente reduzido an-terior, que resolvia apenas problemas com restricao de igualdade. Na versao generalizada as restricoes dedesigualdade sao transformadas em restricoes de igualdade usando o artifıcio de se acrescentar uma variavelde folga para cada restricao de desigualdade.

A ideia basica do metodo e encontrar uma direcao de busca que permita, a partir de um ponto viavel,ou seja, sobre as superfıcies que representam as restricoes viaveis, encontrar um novo ponto viavel com valorda funcao objetivo menor de que o valor anterior.

Devido as nao-linearidades das restricoes essa direcao pode nao ser encontrada. O que se faz entao edeterminar uma direcao que siga “de perto” as restricoes para um passo pequeno. Como o passo dadoconduz a um ponto que nao satisfaz precisamente as restricoes devido as nao linearidades, o metodo deNewton Raphson e usado para se encontrar um novo ponto, a partir da solucao encontrada na primeiraetapa (a qual satisfaz as restricoes). Como ja mencionado, o problema e modificado com a introducao dasvariaveis de folga, ou seja:


min f(x)

s.t. cl(x) + xl+n = 0 l = 1 . . .m

hk(x) = 0 k = 1 . . . l

xli ≤ xi ≤ xn

i

xl+n ≥ 0

i = 1 · · ·n

l = 1 · · ·m

(7.37)

Observe-se que m variaveis de folga, nao negativas, foram adicionadas ao problema original (7.1) forne-cendo um total de n + m variaveis. Se o numero de restricoes de desigualdade e muito alto, este artifıcioaumenta significativamente o esforco computacional para a resolucao do problema. Como no problema mo-dificado o numero total de variaveis, n+m, e quase sempre maior do que o numero de restricoes m + l (asrestricoes xl+n ≥ 0 sao satisfeitas naturalmente), e possıvel separa-las em m+ l variacoes dependentes (umapara cada restricao), e n− l variaveis independentes, ou seja, as restantes (n+m)− (m+ l) = n− l variaveis.Assim o vetor x e subdividido em:

x =

{zy

}n− l variaveis independentesm+ l variaveis dependentes

(7.38)

Como, no problema modificado, todas as restricoes sao de igualdade, elas serao designadas como:

hk(x) = 0; k = 1 · · ·m+ l (7.39)

e as restricoes laterais como sendo:

xli ≤ xi ≤ xu

i i = 1 · · ·n+m (7.40)

Agora, e possıvel escrever: df(x) = [∇f(x)]

t,z dz + [∇f(x)]

t,y dy

dhk(x) = [∇hk(x)]t,z dz + [∇hk(x)]

t,y dy

(7.41)

Ao se supor que o vetor inicial x0 satisfaz as restricoes de igualdade:

hk(x0) = 0; k = 1 · · ·m+ l (7.42)

para que o novo ponto x, dado por:

x = x0 + s, ou

{zy

}=

{z0y0

}+

{dzdy

}(7.43)

seja um ponto viavel, entao:

dhk(x) = 0; k = 1 · · ·m+ l (7.44)

ou, para uma aproximacao linear do vetor dh(x) que contem as componentes dhk(x):

dh(x0) = A(x0) dz +B(x0) dy = 0 (7.45)

onde: {[aj(x0)]

t= [∇hk(x0)]

t,z k = 1 · · ·m+ l

[bj(x0)]t= [∇hk(x0)]

t,y k = 1 · · ·m+ l

(7.46)

sao as linhas de matriz A(x0) e B(x0).

7.5. METODO DE PROGRAMACAO QUADRATICA SEQUENCIAL (PQS) 107

Vale observar que para um vetor arbitrario dz, relativo as variaveis independentes, uma mudanca cor-respondente deve ser obtida para dy, vetor das variaveis dependentes, de modo que a expressao (7.45) sejasatisfeita, ou seja, dh(x) = 0. Portanto:

dy = − [B(x0)]−1

A(x0) dz (7.47)

Substituindo-se agora dy na primeira das expressoes (7.45), obtem-se:

df(x0) = [∇f(x0)]t,z dz − [∇f(x0)]

t,y [B(x0)]

−1A(x0) dz (7.48)

ou:

df(x0) ={[∇f(x0)]

t,z − [∇f(x0)]

t,y [B(x0)]

−1A(x0)

}dz (7.49)

A expressao (7.49) define o gradiente reduzido generalizado gR(x0), ou seja:

gR(x0) = [∇f(x0)]t,z −

{[B(x0)]

−1A(x0)

}t

[∇f(x0)],y (7.50)

O gradiente reduzido generalizado pode agora ser utilizado para determinar uma direcao de busca paraatualizar as variaveis independentes z por meio de uma busca unidimensional, ou seja:

z = z0 + dz (7.51)

As variaveis dependentes podem ser atualizadas utilizando-se o metodo de Newton-Raphson de modoque o ponto x satisfaca as restricoes h(x) = 0, ou seja:

h(z,yi) +[∇h(z,yi)

],y

(yi+1 − yi

)= 0 (7.52)

ou:

yi+1 = yi −[∇h(zi,yi)

],y

h(z,yi) (7.53)

Observe-se que, durante as iteracoes do metodo de Newton-Raphson, o valor das variaveis do vetorz, atualizadas segundo a expressao (7.51) ficam fixos, e somente o vetor y, das variaveis dependentes, eatualizado de modo que o vetor x satisfaca as restricoes.

Vale salientar tambem que se a atualizacao fosse feita com o uso de expressao (7.47), as restricoes naoseriam satisfeitas, ja que sao nao lineares e a expressao (7.47) e obtida com a hipotese de linearizacao dasrestricoes.

7.5 Metodo de Programacao Quadratica Sequencial (PQS)

A ideia fundamental do metodo de PQS e aproximar a funcao objetivo por uma funcao quadratica e asrestricoes por funcoes objetivos em torno de xo para formular o seguinte subproblema:

minf(xo) +∇f(xo)

ts+ 12s

tW(xo) s

s.t. gj(xo) +∇gj(xo)ts ≤ 0; j = 1, ...,m

hh(xo) +∇hh(xo)ts = 0 h = 1, ..., ℓ

(7.54)

Como foi feito no metodo do gradiente reduzido generalizado as restricoes de igualdade podem ser elimi-nadas do subproblema o que resulta num problema padrao de programacao quadratica tendo apenas o passodas variaveis independentes dz como incognitas.

O novo subproblema de PQ pode ser transformado num problema equivalente de programacao linearcomplementar (PLC) que e entao resolvido pelo algoritmo de linha fornecendo o passo a ser dado nasvariaveis independentes dz.


A atualizacao das variaveis dy pode ser feita como no metodo do gradiente reduzido generalizado via ometodo de Newton-Raphson.

Uma curiosidade a respeito da aproximacao quadratica usada para representar a funcao objetivo nosubproblema e que a matriz heniana que aparece no ultimo termo da funcao e a matriz heniana da funcaolagrangeana do problema original e nao a matriz heniana da funcao objetivo (f(x).

Esse fato pode ser explicado comparando-se as condicoes de Kuhn-Toucher dos problemas P1 e P2 aseguir. Nos dois problemas e usada apenas uma restricao de igualdade para efeito de simplicidade.

7.5.1 Problema P1 (problema original)

min f (x)s.t. h (x) = 0

}(7.55)

Funcao lagrangeana do problema P1

L1(x, λ) = f(x)− λh(x) (7.56)

condicoes de Kuhn-Tucher de P1

∇L1(x, λ),x = ∇f(x)− λ∇h(x) = 0h(x) = 0

(7.57)

O primeiro passo da solucao das condicoes de Kuhn-Tucher via metodo de Newton-Raphson e,

∇L1,x

(xk + δxk, λk + δλk

)= 0

h(xk + δxk

)= 0

(7.58)

ou

∇Lk1,x +Wk

1δxk − δλk∇hk

,x = (7.59)

hk +∇hkt,xδx

k = 0 (7.60)

onde Wk1 e a matriz hessiana de L1(x, λ) na iteracao k.

7.5.2 Problema P2 (subproblema de PQS relativo a P1)

min f(xo)ts+ 1

2stW1(xo)s

h(xo) +∇h(xo)ts = 0

}(7.61)

Funcao lagrangeana do problema P2

L2 (s, λ) = ∇f (xo)ts+

1

2stW1 (xo) s− λ

(h (xo) +∇h (xo)

ts)

(7.62)

Condicoes de Kuhn-Tucher de P2

∇L2 (s, λ),s = ∇f (xo) +W1 (xo) s− λk+1∇h (xo) (7.63)

ou

∇f (xo)− λk∇h (xo) +W1 (xo) s− δλk∇h (xo) = 0 (7.64)

ou ainda

∇L1 (xo, λ),x +W1 (xo) s− δλk∇h (xo) = 0

h (xo) +∇h (xo)ts = 0

(7.65)

Vale observar que as equacoes (7.55) e (7.58) sao identicas ao se substituir xk e δxk em (7.55) por xo es em (7.58). Isso significa que resolver o subproblema P2 de PQ do problema original P1 equivale a obter

7.5. METODO DE PROGRAMACAO QUADRATICA SEQUENCIAL (PQS) 109

a primeira iteracao da solucao via Newton-Raphson das equacoes correspondentes as condicoes de Kuhn-Tucher de P1. Esse fato justifica o uso da heniana da funcao lagrangeana de P1 no lugar da heniana dafuncao objetivo na definicao do subproblema de PQS.

Uma vez que a determinacao de matrizes henianas e muitas vezes de difıcil obtencao ou pouco eficientecomputacionalmente, recomenda-se usar uma aproximacao via o metodo Quase-Newton BFGS visto no item3.1.7.

Capıtulo 8

Analise de Sensibilidade

8.1 Introducao

A analise de sensibilidade tratada neste capıtulo se refere a meios contınuos modelados por elementos finitos,tambem conhecida como analise de sensibilidade discreta.

Matematicamente, a analise de sensibilidade e dada pela derivada:

∂rj (x)

∂xi(8.1)

onde rj (x) e a componente j de um vetor de resposta da estrutura e xi e a componente i de um vetor xde variaveis de projeto ou de parametros da estrutura. Assim, rj pode ser um deslocamento ou um conjuntode deslocamentos associados a certos graus de liberdade, uma componente ou um vetor de tensoes ou umafrequencia propria, e xi pode ser a area da secao transversal de um elemento de trelica, a altura da secaotransversal retangular de um elemento de uma viga ou coluna, ou ainda, o modulo de elasticidade do materialde uma dada estrutura. Conceitualmente, a analise de sensibilidade mede o grau de influencia da variavelou parametro xi na resposta rj (x) da estrutura.

Quando se utilizam algoritmos de programacao matematica de primeira e segunda ordens para se obtero projeto otimo de uma estrutura discretizada por elementos finitos, a analise de sensibilidade precisa serempregada.

Analogamente, quando se faz uma analise de confiabilidade pelos metodos FORM ou SORM , e necessariofazer uso da analise de sensibilidade.

Na proxima secao serao apresentados os principais metodos de analise de sensibilidade, tais como: ometodo das diferencas finitas, os metodos diretos analıtico e semi-analıtico e os metodos adjuntos analıticoe semi-analıtico.

Nas secoes seguintes essas tecnicas serao empregadas para se obter a analise de sensibilidade de diferentesrespostas estruturais, tais como: deslocamentos em problemas estaticos e dinamicos, tensoes, frequenciasproprias e carga limite.

8.2 Metodos de Analise de Sensibilidade

8.2.1 Metodo das Diferencas Finitas

O Metodo das Diferencas Finitas (MDF) mais simples e o Metodo Frontal. Nele, a Equacao (8.1) e aproxi-mada por:

∂r (x)

∂xi≈ ∆r

∆xi=

r (x+∆xiei)− r(x)

∆xi(8.2)

onde r (x) e um vetor de respostas da estrutura, ∆xiei e uma perturbacao na componente xi do vetordas variaveis x e ei e um vetor com a componente i igual a 1 e demais componentes 0.

111

112 CAPITULO 8. ANALISE DE SENSIBILIDADE

Outra aproximacao frequentemente usada e conhecida como Metodo das Diferencas Centrais, ou seja:

∂r (x)

∂xi≈ ∆r

∆xi=

r(x+∆xiei)− r(x−∆xiei)

2∆xi(8.3)

Em geral, o valor do tamanho do passo ∆xi varia de 10−4xi a 10−2xi. O tamanho do passo nao deveser nem muito alto, para nao produzir erro de truncamento, nem muito baixo, para nao causar erro dearredondamento.

8.2.2 Metodo Direto

Seja um conjunto de restricoes de igualdade que definem as equacoes de estado do problema, por exemplo, asequacoes de equilıbrio estatico de uma estrutura de comportamento linear elastico discretizada pelo metododos elementos finitos:

c (r (x) ,x) = 0 (8.4)

sendo r(x) um vetor de respostas da estrutura.Utilizando-se a regra da cadeia, e simplificando a notacao:

dc(r,x)

dxi=

∂c(r,x)

∂xi+

∂c(r,x)

∂r

dr

dxi(8.5)

ou ainda, sucintamente:

dc

dxi= pi + Z

∂r

∂xi(8.6)

onde:

Z =∂c(r,x)

∂re pi =

∂c(r,x)

∂xi(8.7)

Observe que ∂ c∂ r denota a derivada total do vetor c em relacao a r, enquanto que ∂ r

∂ xie a derivada explıcita

do vetor r em relacao a componente xi do vetor x. A derivada total dcdxi

e a soma da derivada explıcita coma parcela implıcita.

Derivando-se os dois lados da Equacao (8.4) e usando a Equacao (8.6), obtem-se:

pi + Z∂r

∂xi= 0 (8.8)

logo:

Z∂r

∂xi= −pi (8.9)

Quando a derivada explıcita e obtida analiticamente, o metodo direto e chamado de analıtico, enquantoque, quando alguma parcela da derivada explıcita e obtida por meio de diferencas finitas, o metodo edenominado de semi-analıtico.

8.2.3 Metodo Adjunto

Seja a restricao de igualdade1 de um problema de otimizacao dada por:

h (r(x),x) = 0 (8.10)

Os algoritmos de programacao matematica de primeira e segunda ordens requerem o calculo da derivada:

d h

d xi=

∂ h

∂ xi+ µt d r

d xi(8.11)

1As deducoes feitas aqui tambem se aplicam a restricoes de desigualdade.

8.3. COMPARACAO ENTRE OS METODOS DE ANALISE DE SENSIBILIDADE 113

que representa a analise de sensibilidade da restricao h em relacao a variavel ou ao parametro xi, e µ ovetor linha dado por:

µ =∂ h

∂ r(8.12)

O procedimento do metodo adjunto consiste em se somar a derivada total das equacoes de estado, pre-multiplicadas pelo vetor λ de multiplicadores de Lagrange, a derivada total das restricoes. O numero decomponentes do vetor λ, tambem chamado de vetor adjunto, deve ser igual ao numero de equacoes de estadodo problema. A nova derivada total de h passa a ser dada por:

d h

d xi=

dh

dxi︷︸︸︷∂ h

∂ xi+ µt d r

d xi+λt

dc

dxi︷︸︸︷(p+ Z

d r

d xi

)(8.13)

Como, conforme a Equacao (8.8), a parcela pre-multiplicada por λt e um vetor nulo, entao, a Equacao (8.13)representa a sensibilidade de h em relacao a xi.

Reagrupando-se os termos da Equacao (8.13), chega-se a:

d h

d xi=

∂ h

∂ xi+(µt + λt Z

) d r

d xi+ λt p (8.14)

A segunda parcela do lado direito da Equacao (8.14) pode ser eliminada fazendo-se:

Zt λ = −µ (8.15)

A Equacao (8.15) permite a obtencao de λ, o que possibilita calcular finalmente:

d h

d xi=

∂ h

∂ xi+ λt p (8.16)

O Metodo Adjunto tambem pode ser analıtico ou semi-analıtico, dependendo de como as derivadasexplıcitas sao obtidas na Equacao (8.16).

8.3 Comparacao entre os Metodos de Analise de Sensibilidade

A primeira observacao a ser feita aqui e que tanto o Metodo das Diferencas Finitas quando o Metodo Diretofornecem:

d r

d xi

enquanto que o Metodo Adjunto permite obter:

d h

d xi

Na verdade, o que se procura e obter d hd xi

pois os algoritmos de programacao matematica de primeiraordem precisam desta grandeza durante suas iteracoes no processo de otimizacao. No entanto, como vistoanteriormente:

d h

d xi=

∂ h

∂ xi+ µt d r

d xi(8.17)

onde tanto ∂ h∂ xi

quanto µ sao, em geral, facilmente obtidos. Desse modo e possıvel usar d rd xi

, calculado

pelos dois primeiros metodos citados acima, para se obter ∂h∂xi

sem grandes esforcos.O Metodo das Diferencas Finitas tem a vantagem da sua simplicidade conceitual e de poder ser aplicado

a qualquer tipo de problema. Todavia, ele e computacionalmente pouco eficiente, principalmente quando


a avaliacao da resposta da estrutura exige muito esforco computacional, como e o caso em estruturas comcomportamento nao linear e/ou com muitos graus de liberdade. Vale salientar que, no Metodo das DiferencasFinitas, uma nova analise da estrutura deve ser feita para se obter a analise de sensibilidade em relacao a cadavariavel de projeto ou a cada parametro. O Metodo Direto e computacionalmente eficiente, especialmenteo analıtico. O esforco computacional deste metodo nao cresce na mesma proporcao do numero de variaveis(ou parametros) para os quais a analise de sensibilidade deve ser feita, como acontece com o Metodo dasDiferencas Finitas.

O Metodo Adjunto e apropriado para problemas onde ha poucas restricoes e muitas variaveis de projeto,ao contrario do Metodo Direto. Isto se deve ao fato do vetor λ so depender do numero de equacoes deestado, e nao do numero de variaveis, e tambem das derivadas explıcitas (vide Equacao 8.14) serem de facilobtencao para cada nova variavel.

8.4 Aplicacao dos Metodos de Analise de Sensibilidade

8.4.1 Analise Linear Elastica

A equacao de estado deste problema e da seguinte forma:

c (u(x),x) = K(x)u(x)− fa(x) = 0 (8.18)

onde: K representa a matriz de rigidez da estrutura discretizada por elementos finitos, fa e o vetor dascargas nodais aplicadas e u e o vetor dos deslocamentos nodais.

No MEF as tensoes em cada elemento sao dadas por:

σe = CBe ue (8.19)

onde: ue e o vetor dos deslocamentos nodais do elemento e, Be e a matriz de compatibilidade cinematicado elemento, que relaciona deslocamentos nodais com deformacoes, C e a matriz constitutiva, que transformadeformacoes em tensoes e que depende do modulo de elasticidade e do coeficiente de Poisson, e σe e o tensordas tensoes no elemento.

8.4.1.1 Metodo das Diferencas Finitas

Caso a analise de sensibilidade desejada seja a relacionada ao vetor dos deslocamentos nodais u(x) em relacaoa componente xi do vetor de variaveis de projeto, deve-se calcular: K(x)u(x) = fa(x) =⇒ u(x)

K(x+∆xiei)u(x+∆xiei) = fa(x+∆xiei) =⇒ u(x+∆xiei)(8.20)

e, em seguida:

du

d xi=

u(x+∆xiei)− u(x)

∆xi(8.21)

Como mencionado anteriormente, uma nova analise deve ser feita para se obter u(x+∆xiei), o que implicaem uma nova montagem da matriz de rigidez “K(x+∆xiei)” e do vetor de forcas nodais “fa(x+∆xiei)”.

Quando se deseja calcular a sensibilidade das tensoes em relacao a xi, deve-se proceder da seguinte forma: σe(x) = C(x)Be(x)ue(x)

σe(x+∆xiei) = C(x+∆xiei)Be(x+∆xiei)ue(x+∆xiei)(8.22)

e, em seguida:

dσe

d xi=

σe(x+∆xiei)− σe(x)

∆xi(8.23)

8.4. APLICACAO DOS METODOS DE ANALISE DE SENSIBILIDADE 115

Na segunda das Equacoes (8.22), Be seria perturbada caso xi fosse uma coordenada nodal do elementoou uma area de secao transversal de uma barra de trelica e C seria perturbada caso xi fosse um parametromecanico (propriedade fısica), como por exemplo o modulo de elasticidade ou o coeficiente de Poisson domaterial.

8.4.1.2 Metodo Direto

A expressao da analise de sensibilidade da resposta r no Metodo Direto e dada pela Equacao (8.9), ou seja:

Z∂ r

∂ xi= −pi

Com Z e pi definidos em (8.7).Para a analise de sensibilidade dos deslocamentos, tem-se r = u.O problema linear elastico c e dado pela Equacao (8.18), ou seja:

c (u(x),x) = K (x) u (x)− fa (x) = 0

logo: Z = K

pi =∂ K∂ xi

u− ∂ fa∂ xi

(8.24)

Entao:

du

d xi= −K−1 pi (8.25)

O vetor pi e usualmente denominado vetor das pseudo-forcas.No Metodo Direto Analıtico as derivadas explıcitas em pi sao calculadas analiticamente, enquanto que

no Metodo Direto Semi-Analıtico as mesmas derivadas sao obtidas por diferencas finitas.

8.4.1.3 Metodo Adjunto

Neste metodo, a sensibilidade da restricao h e dada pela Equacao (8.16), ou seja:

d h

d xi=

∂ h

∂ xi+ λt pi

onde: λ e obtido pela Equacao (8.15):

Zt λ = −µ

sendo Z e pi, definidos na Equacao (8.7):

pi =∂ c

∂ xie Z =

∂ c

∂ r

e µ definido na Equacao (8.12):

µ =∂ h

∂ r

Caso h seja uma restricao que limite a componente j do vetor de deslocamentos nodais, u, a um valorprescrito uj , ou seja:

h (u(x),x) = uj(x)− uj ≤ 0

e c seja dado conforme a Equacao (8.18):

c (u(x),x) = K(x)u(x)− fa(x)


Obtem-se: Z = ∂ c

∂ u = K

pi =∂ c∂ xi

= ∂ K∂ xi

u− ∂ fa∂ xi

µ = ∂ h∂ u = ej

(8.26)

onde ej e um vetor com valor 1 na posicao j e 0 nas demais.

Assim, as Equacoes (8.15) e (8.16) podem ser reescritas como:Kt λ = −ej

d hd xi

= 0+ λt(

∂ K∂ xi

u− ∂ fa∂ xi

) (8.27)

8.4.2 Problema de Autovalores e Autovetores

A equacao de estado do problema de vibracoes nao amortecidas e do problema de analise de carga crıtica deuma estrutura discretizada por elementos finitos e dada por:

K Φ− αM Φ = 0 (8.28)

onde K e a matriz de rigidez e M e a matriz de massa (problemas de vibracao) ou a matriz de rigidezgeometrica (problemas de analise de carga crıtica). Para o problema de vibracao, α representa o quadradode uma frequencia natural da estrutura (α = w2) e Φ o vetor dos modos de vibracao. Para o problema decalculo de carga crıtica, α representa o fator de carga crıtica e Φ o modo de flambagem. As duas matrizesK e M sao simetricas e K e positiva semi-definida.

O vetor Φ e, geralmente, normalizado em relacao a matriz de massa de modo que:

Φt M Φ = 1 (8.29)


No Metodo das Diferencas Finitas a equacao de estado do problema deve ser resolvida duas vezes, uma paraa variavel nao perturbada e outra para a perturbada. Para se obter a sensibilidade da resposta em relacaoa uma nova variavel, uma nova solucao, com a nova variavel perturbada, torna-se necessaria. Assim:

K(x) Φ− αM(x) Φ = 0 =⇒

α(x)

Φ(x)(8.30)

e:

K(x+∆xiei) Φ− αM(x+∆xiei) Φ = 0 =⇒

α(x+∆xiei)

Φ(x+∆xiei)(8.31)

As sensibilidades de α e Φ sao, entao, obtidas de:dαd xi≈ ∆α

∆ xi= α(x+∆ xiei)−α(x)

∆ xi

dΦd xi≈ ∆Φ

∆ xi= Φ(x+∆ xiei)−Φ(x)

∆xi

(8.32)



O problema em questao e definido por duas equacoes de estado, (8.28) e (8.29), ou seja:c1(α,Φ) = K Φ− αM Φ = 0

c2(α,Φ) = 1−Φt M Φ = 0(8.33)

Nesse caso, o vetor r e formado por dois tipos de respostas, os autovalores (α) e os autovetores (Φ).Desse modo, para se obter Z e preciso proceder como indicado:

d c1

d xi= ∂ c1

∂ xi+ ∂ c1

∂ αdαd xi

+ ∂ c1

∂ ΦdΦd xi

= 0

d c2

d xi= ∂ c2

∂ xi+ ∂ c2

∂ αdαd xi

+ ∂ c2

∂ ΦdΦd xi

= 0(8.34)

ou, reagrupando-se os termos na forma matricial: ∂ c1

∂ Φ∂ c1

∂ α

∂ c2

∂ Φ∂ c2

∂ α

dΦd xi

dαd xi

= −

∂ c1

∂ xi

∂ c2

∂ xi

(8.35)

Efetuando-se as derivacoes na Equacao (8.35), por meio das equacoes de estado definidas em (8.33),chega-se a: K− αM −MΦ

−Φt M 0

dΦd xi

dαd xi

= −

(

dKd xi− α dM

d xi

)Φ

−12 Φ

t dMd xi

Φ

(8.36)

Na segunda das Equacoes (8.36) foi feito uso da simetria da matriz M.Comparando-se a Equacao (8.36) com a expressao geral (Equacao 8.9), e possıvel afirmar que:

Z =

K− αM −MΦ

−Φt M 0

e

pi =

(

dKd xi− α dM

d xi

)Φ

− 12 Φ

t dMd xi

Φ

(8.37)

Resolvendo-se o sistema de equacoes (8.36), as sensibilidades de α e Φ sao obtidas uma vez que essasvariaveis tenham sido previamente calculadas. Se as derivadas explıcitas de K e M em relacao a xi, queaparecem no vetor pi, forem obtidas analiticamente, o metodo e dito Direto Analıtico. No entanto, casoo metodo das Diferencas Finitas tenha sido utilizado para se obter as mencionadas derivadas (conformemostrado nas Equacoes 8.38), entao o metodo e dito Direto Semi-Analıtico:

dKd xi≈ K(x+∆ xiei)−K(x)

∆xiei

dMd xi≈ M(x+∆ xiei)−M(x)

∆ xiei

(8.38)

Como mencionado anteriormente:

w2 = α (8.39)

Logo, derivando-se os dois lados da Equacao (8.38) em relacao a xi:


2wdw

dxi=

dα

dxi=⇒ dw

dxi=

1

2w

dα

dxi(8.40)

com dαd xi

obtido a partir da Equacao (8.36).


As expressoes gerais para a analise de sensibilidade da restricao h em relacao a variavel de projeto ouparametro xi sao dadas nas Equacoes (8.15) e (8.16) para o Metodo Adjunto. As expressoes gerais paraa matriz Z e o vetor pi, utilizados em (8.15) e (8.16), respectivamente, estao definidas na Equacao (8.7),enquanto que para o vetor µ a expressao geral e dada na Equacao (8.12).

Utilizando-se as expressoes acima referidas e as expressoes de estado do problema em questao, dadaspelas Equacoes (8.28) e (8.29), foram obtidas no item anterior as expressoes de Z e pi para o problemaparticular de autovalores e autovetores definidas em (8.37).

Um restricao tıpica do problema de autovalor e autovetor procura impor limites inferiores e superiorespara as frequencias proprias no problema dinamico e um limite inferior para o parametro de carga crıtica noproblema de analise de carga crıtica.

Tomando-se esse ultimo caso para se definir uma restricao, obtem-se:

h(α,Φ) = α− αmin ≤ 0 (8.41)

Nesse caso, o vetor µ, definido em (8.26), passa a ser dado por:

µ =

{∂ h∂ α∂ h∂ Φ

}= e1 (8.42)

o que permitiria obter λ e d hd xi

por meio das Equacoes (8.15) e (8.16), respectivamente, sendo:

∂ h

∂ xi= 0

8.4.3 Problema de Analise Nao Linear Estatica

A equacao de estado para a analise nao linear de estruturas pode ser escrita como:

f(u,x) = α fa(x) (8.43)

onde f(u,x) e o vetor das forcas internas resistentes nodais geradas pelos deslocamentos u e α fa(x) e ovetor das forcas externas aplicadas.

Em analises nao lineares, o modulo do vetor da resposta em deslocamentos u nao e proporcional a α,como nas analises lineares. Para se obter a curva |u| × α e preciso incrementar α gradualmente e, para cadavalor de α, obter o correspondente vetor u.

A equacao basica do Metodo de Newton-Raphson para a analise de estruturas de comportamento naolinear pode ser obtida derivando-se a Equacao (8.43) em relacao ao vetor u (ver item XXXX), ou seja:

Kt(u0,x) ∆u = α fa(x)− f(u0,x) (8.44)

onde u0 sao os deslocamentos acumulados ate o penultimo incremento de α, Kt(u0,x) e a matriz derigidez tangente, avaliada em u = u0, e ∆u sao os deslocamentos da ultima iteracao do incremento atual.

O vetor u deve ser atualizado da seguinte forma:

u = u0 +∆u (8.45)

O processo iterativo termina quando o modulo de ∆u for menor do que uma dada tolerancia numerica.



Para a analise de sensibilidade do vetor de deslocamentos u em relacao a uma dada variavel (ou parametro)xi, o primeiro passo consiste em realizar uma analise nao linear com valores de α e x que forneca u(x). Paraessa analise pode-se usar o Metodo de Newton–Raphson, um Metodo Quase–Newton ou outros que fornecau(x), ou seja:

f(u,x) = α fa(x) =⇒ u(x) (8.46)

Em seguida, uma nova analise nao linear deve ser realizada para um valor de xi perturbado de ∆xi, talque forneca u(x+∆xiei), isto e:

f(u,x+∆xiei) = α fa(x+∆xiei) =⇒ u(x+∆xiei) (8.47)

A sensibilidade de u em relacao a xi e, entao, dada por:

du

d xi≈ ∆u

∆xi=

u(x+∆xiei)− u(x)

∆xi(8.48)


Reescrevendo-se a equacao de estado (8.43) como:

c (u(x),x) = f (u(x),x)− α fa(x) = 0 (8.49)

pode-se obter as expressoes dadas em (8.7) particularizadas para o problema nao linear, ou seja:

Z =∂ c

∂ u= Kt (u(x),x) (8.50)

e:

pi =∂ c

∂ xi=

∂ f [u(x),x]

∂ xi− α

∂ fa(x)

∂ xi(8.51)

que permitem obter a sensibilidade de u em relacao a xi para o problema em questao, resolvendo-se aEquacao (8.9) aqui particularizada como:

Kt (u(x),x)du

d xi= −

{∂ f [u(x),x]

∂ xi− α

∂ fa(x)

∂ xi

}(8.52)

Se as derivadas explıcitas que aparecem no vetor pi forem obtidas analiticamente, diz-se que o MetodoDireto e Analıtico. Se, por outro lado, essas derivadas forem obtidas por diferencas finitas, o Metodo Diretoe denominado de Semi-Analıtico.


Para aplicar o Metodo Adjunto na analise de sensibilidade e necessario obter, alem da matriz Z e do vetorpi, obtidos no item anterior, o vetor µ, definido em (8.12), para se obter o vetor adjunto λ.

Para se obter µ, conforme a Equacao (8.12), e preciso definir uma restricao h. Seja, por exemplo, h umarestricao em deslocamento do tipo:

h (uj(x),x) = uj − uj ≤ 0 (8.53)

onde uj e a componente j do vetor de deslocamentos nodais u e uj e um deslocamento prescrito associadoao mesmo grau de liberdade. Sendo, neste caso, r = u, tem-se:

µ =∂ h

∂ r=

∂ h

∂ u= ej (8.54)

Com µ pode-se calcular λ por meio da Equacao (8.15) e, em seguida, a sensibilidade de h em relacao axi por meio da Equacao (8.16), considerando-se que a derivada explıcita de h em relacao a xi e nula.


8.4.4 Problemas de Carga Limite

Para um fator de carga crıtica α∗ a matriz de rigidez tangente Kt(u(x),x) torna-se singular. Nesse caso,diz-se que a estrutura atingiu um ponto de bifurcacao ou de carga limite. E possıvel descobrir qual dos doiscasos ocorre ao se diferenciar a Equacao (8.43) em relacao a um parametro β que cresce monotonicamente,ou seja:

Kt(u(x),x)du

d β=

dα

dβfa(x) (8.55)

Em um ponto crıtico, Kt e singular. Denominando-se de v, o autovetor associado ao autovalor nulo deKt no ponto crıtico, pode-se escrever:

vt K∗t = 0 (8.56)

onde o asterisco (∗) designa grandezas calculadas no ponto crıtico.

Pre-multiplicando-se a Equacao (8.55) por vt, obtem-se:

dα

dβvt fa(x) = 0 (8.57)

Em um ponto limite:

dα

dβ= 0 (8.58)

porque a carga atinge um valor maximo. Nesse caso, comparando-se as Equacoes (8.55) e (8.56), econsiderando-se a Equacao (8.58), verifica-se que o modo de flambagem associado ao ponto limite e igual aderivada de u em relacao ao parametro β.

Em um ponto de bifurcacao:

dα

dβ= 0 (8.59)

Logo:

vt fa(x) = 0 (8.60)

indicando que o modo de flambagem v e ortogonal ao vetor de cargas fa.


Supondo-se que varias analises nao lineares foram realizadas para valores crescentes de α e utilizando-se asEquacoes (8.56) e (8.57), um ponto limite e identificado, ou seja, Kt e singular e:

vt fa(x) = 0

para um dado valor de α. Nesse caso, α e o valor de carga limite α∗(x).

No Metodo das Diferencas Finitas, para se obter a sensibilidade de α∗ em relacao a xi, o valor de xi eperturbado de ∆xi e uma nova analise nao linear e realizada ate que um novo ponto limite seja encontrado,ou seja, ate que α∗(x+∆xiei) seja determinado.

A sensibilidade de α∗ em relacao a xi e dada entao por:

dα∗

d xi≈ ∆α∗

∆xi=

α∗(x+∆xiei)− α∗(x)

∆xi(8.61)



As equacoes de estado que identificam um ponto limite sao (vide Equacao 8.49, fazendo-se α = α∗):

c [u∗(x),x] = f(u∗,x)− α∗ fa(x) (8.62)

Alem disso, a matriz de rigidez tangente em u∗, ou seja:

K∗t =

∂ f

∂ u

∣∣∣∣u=u∗

deve ser singular e seu autovetor associado ao autovalor nulo deve satisfazer:

vt K∗t = 0

O vetor r das respostas e formado nesse caso por u∗ e α∗, assim, a derivada da Equacao (8.62) em relacaoa xi fornece:

d c

d xi= K∗

t

du∗

d xi+

∂ f∗

∂ xi− dα∗

d xifa − α∗ ∂ fa

∂ xi= 0 (8.63)

Pre-multiplicando-se a Equacao (8.63) por vt, considerando-se a Equacao (8.56) e explicitando-se dα∗

d xi

obtem-se:

dα∗

d xi=

vt(

∂ f∗

∂ xi− α∗ ∂ fa

∂ xi

)vt fa

(8.64)

A partir da Equacao (8.62) e possıvel obter tambem a matriz Z e o vetor pi, ou seja:

Z =∂ c

∂ r=[

∂ c∂ u∗

∂ c∂ α∗

]=[K∗

t −fa]

(8.65)

e

pi =∂ c

∂ xi=

{∂ f∗

∂ xi− α∗ ∂ fa

∂ xi

}(8.66)

que deveria permitir a analise de sensibilidade das respostas u∗ e α∗ em relacao a xi com o uso daEquacao (8.8), ou seja:

[K∗

t −fa] { du∗

d xidα∗

d xi

}+

{∂ f∗

∂ xi− α∗ ∂ fa

∂ xi

}= 0 (8.67)

O sistema de Equacoes (8.67) tem, todavia, mais incognitas do que equacoes, porem, ao se multiplicar aexpressao (8.67) por vt, o vetor du∗

d xie eliminado do sistema, pois:

vt K∗t = 0

e, assim, a solucao apresentada na Equacao (8.64) e obtida. Vale observar que o vetor pi, em (8.66),representa a sensibilidade da forca desequilibrada em relacao a xi, que pode ser obtida pelo metodo analıticoou semi-analıtico.


No Metodo Adjunto, como ja visto anteriormente, e necessario obter o vetor µ, alem da matriz Z e do vetorpi, para se obter a sensibilidade da restricao h em relacao a xi.

Seja a restricao h dada por:

h(u∗, α∗) = α∗ − α∗min ≥ 0 (8.68)

A sensibilidade de h e apresentada na Equacao (8.16), ou seja:


d h

d xi= 0 + λt p (8.69)

com µ e λ obtidos, respectivamente, pelas Equacoes (8.12) e (8.15). Para a restricao definida naEquacao (8.68), tem-se, uma vez que r = r(u∗, α∗):

µ =

∂ h∂ u∗

∂ h∂ α∗

=

0

1

(8.70)

sendo µ um vetor de dimensao n× 1, onde n e o numero de graus de liberdade do sistema.Particularizando a Equacao (8.15) para o presente problema, tem-se: (K∗

t )t

− (fa)t

λ = −

0

1

(8.71)

Na Equacao (8.71), o vetor λ multiplica uma matriz Z de dimensao (n+1)×n e o produto e igual a umvetor µ de dimensao (n+ 1)× 1. A dimensao de λ e, portanto, n× 1.

E importante observar que, se λ for dado por:

λ = λα v (8.72)

onde v e o autovetor associado ao autovalor nulo de K∗t , ele satisfaz a Equacao (8.71), desde que:

λα

(−f ta v

)= −1 ou λα =

1

f ta v(8.73)

Substituindo-se λ na Equacao (8.69), chega-se a:

∂ h

∂ xi=

vt pi

vt fa(8.74)

que, nao por acaso, e a mesma expressao dada em (8.64) para a sensibilidade de α∗ em relacao a xi peloMetodo Direto, ja que a derivada explıcita de h em relacao a xi e nula.

8.4.5 Problemas de Fluxo Termico Transiente

A equacao de estado de um problema de fluxo termico transiente com o meio discretizado por elementosfinitos e dada por:

K T+C T = q(t) (8.75)

onde K e a matriz de condutividade termica, positiva semi-definida, C e a matriz de capacidade termica,T e o vetor das temperaturas nodais, T e a derivada de T em relacao ao tempo t e q(t) e o vetor das cargastermicas.

Quando se usam algoritmos de integracao direta para resolver o sistema representado pela Equacao (8.75)o vetor T e interpolado no intervalo de tempo ∆ t, entre os tempos t0 e t1. Uma das maneiras de se fazeristo e usar uma interpolacao linear do tipo:

T(t) =

[1−

(t− t0∆ t

)]T0 +

(t− t0∆ t

)T1 (8.76)

com T0 e T1 sendo, respectivamente, os valores de T nos instantes t0 e t1.O vetor T(t) pode ser obtido a partir da Equacao (8.76) por derivacao no tempo, ou seja:

T(t) =1

∆ t(T1 −T0) (8.77)


A Equacao (8.75) pode ser escrita para um dado instante no intervalo ∆ t. Pode-se escolher qualquerinstante normalizado entre t0 e t1, ou seja:

ξ =t− t0∆ t

(8.78)

sendo 0 ≤ ξ ≤ 1, logo: T(ξ) = (1− ξ) T0 + ξ T1

T(ξ) = 1∆ t (T1 −T0)

(8.79)

O vetor das cargas nodais tambem pode ser interpolado de modo analogo ao vetor T, ou seja:

q = (1− ξ) q0 + ξ q1 (8.80)

onde q0 e q1 sao os vetores das cargas termicas nodais nos instantes t0 e t1, respectivamente.Substituindo-se as Equacoes (8.79) e (8.80) em (8.75) e reagrupando-se os termos, obtem-se:

[C+ ξ∆tK] T1 = [C− (1− ξ)∆tK] T0 +∆t [(1− ξ) q0 + ξ q1] (8.81)

O algoritmo de integracao direta, com ξ = 0 e denominado explıcito. Para ξ = 1 o algoritmo e ditoimplıcito e para ξ = 1

2 tem-se o algoritmo mais preciso, sendo tambem incondicionalmente estavel, e porisso e o mais utilizado. O algoritmo para ξ = 1

2 e conhecido na literatura tecnica como algoritmo de Crank-Nicholson, Central ou Trapezoidal. Valores de ξ entre 1

2 e 1 fornecem algoritmos incondicionalmente estaveise convergem para qualquer valor de ∆t.

A Equacao (8.81) e a equacao de estado do problema de fluxo termico transiente entre os instantes t0 et1. Para uma analise ao longo do tempo, ela deve ser resolvida a cada passo, adotando-se T0 como sendo ovalor de T1 do passo anterior.


No Metodo das Diferencas Finitas a solucao da Equacao (8.81) deve ser obtida passo a passo (de ∆ t em∆ t), ao longo do tempo para x e para x + ∆xiei, ou seja, com as matrizes K e C e os vetores q0 e q1

montados com x na primeira analise e x + ∆xiei na segunda. Na primeira analise obtem-se T(t,x) e nasegunda T(t,x+∆xiei) no instante t. Caso a sensibilidade para uma nova variavel xi seja necessaria, umanova analise ao longo do tempo precisa ser feita ate o instante t.

A sensibilidade de T em relacao a xi no instante t e dada entao por:

dT

d xi

∣∣∣∣t=tp

≈ ∆T(tp)

∆x=

T(tp,x+∆xiei)−T(tp,x)

∆xi(8.82)


A equacao de estado do problema de fluxo termico transiente e dada pela expressao (8.81) para uma analisevia algoritmo de integracao direta do tipo definido em (8.79) sendo o vetor resposta r igual ao vetor Tavaliado no instante t1 (ou seja, T1):

c (T1(x),x) = [C+ ξ∆tK] T1 − [C− (1− ξ)∆tK] T0 −∆t [(1− ξ)q0 + ξ q1] = 0 (8.83)

A partir da Equacao (8.83) e possıvel obter Z e pi, ou seja:

Z = ∂ c

∂ T1= [C+ ξ∆tK]

pi =∂ c∂ xi

=[∂ C∂ xi

+ ξ∆t ∂ K∂ xi

]T1 −

[∂ C∂ xi− (1− ξ)∆t ∂ K

∂ xi

]T0 −∆t

[(1− ξ) ∂ q0

∂ xi+ ξ ∂ q1

∂ xi

] (8.84)

que permitem obter a sensibilidade de T1 em relacao a xi conforme a Equacao (8.9), ou seja:


ZdT1

d xi= −pi (8.85)

Observe que para a analise de sensibilidade no instante tp, tanto a analise passo a passo, propriamentedita e definida em (8.81), como a analise de sensibilidade definida em (8.85), tambem realizada passo a passo,devem ser feitas ate o instante tp. Vale salientar que para se fazer a analise de sensibilidade do instante t0ao instante t1, tanto T0 quanto T1, obtidos da analise propriamente dita, sao necessarios porque aparecemno vetor pi.

As derivadas explıcitas de C, K, q0 e q1 em pi podem ser feitas analiticamente ou por diferencas finitas.


Como ja foi visto anteriormente, no Metodo Adjunto e preciso obter, alem de Z e pi o vetor µ para secalcular a sensibilidade da restricao h em relacao a xi. Seja a restricao h dada por:

h (T1i) = T1i −T1i ≤ 0 (8.86)

onde T1i e a componente i do vetor T1 e T1i e um valor prescrito para esta variavel.O vetor µ para o problema em questao vale:

µ =∂ h

∂T1i

= ei (8.87)

A partir do vetor µ pode-se obter o vetor λ por meio da Equacao (8.15), ou seja:

Zt λ = −µ =⇒ λ

e, finalmente, a sensibilidade de h e obtida por meio da Equacao (8.16), ou seja:

d h

d xi=

∂ h

∂ xi+ λt pi

onde:

∂ h

∂ xi= 0

Observe que λ so precisa ser calculado uma unica vez e que apenas o vetor pi se modifica ao longo dotempo para o calculo da sensibilidade de h em relacao a xi pelo Metodo Adjunto, enquanto que uma solucaodo sistema de equacoes do tipo (8.85) precisa ser obtida em cada passo de tempo no Metodo Direto.

8.4.6 Problemas de Analise Dinamica

A equacao de equilıbrio de um problema de analise dinamica para uma estrutura discretizada por elementosfinitos e:

M a+C v +K u = f(t) (8.88)

onde M e a matriz de massa, C e a matriz de amortecimento, K e a matriz de rigidez, u, v e a sao,respectivamente, os vetores de deslocamento, velocidade e aceleracao e f(t) e o vetor de cargas nodais aplica-das. Quando se utilizam algoritmos de integracao direta para a solucao do sistema de equacoes diferenciaisde segunda ordem dado em (8.88), um sistema de equacoes algebricas deve ser resolvido em cada passode tempo para se obter as respostas no final do intervalo. Para exemplificar a analise de sensibilidade emproblemas dinamicos resolvidos por integracao direta, o algoritmo de Newmark sera utilizado.

No Metodo de Newmark as seguintes equacoes cinematicas sao adotadas: u1 = u0 +∆ t v0 +∆ t2[(

12 − α

)a0 + α a1

]v1 = v0 +∆ t [(1− δ) a0 + δ a1]

(8.89)


onde, na Equacao (8.89), ∆ t e o intervalo de tempo entre os instantes inicial (t0) e final (t1), ou seja:

∆ t = t1 − t0, (8.90)

u0, v0 e a0 sao, respectivamente, os vetores de deslocamentos, velocidades e aceleracoes no instante t0, u1,v1 e a1 sao as mesmas grandezas no instante t1 e, finalmente, α e δ sao parametros do algoritmo. Um dosmais populares algoritmos da famılia dos algoritmos de Newmark e o que considera α = 1

4 e δ = 12 . Este

algoritmo e incondicionalmente estavel. Para esses valores de α e δ as expressoes (8.89) podem ser rescritascomo: u1 = u0 +∆ t v0 +

∆ t2

4 (a0 + a1)

v1 = v0 +∆ t2 (a0 + a1)

(8.91)

Explicitando-se a1 na primeira das Equacoes (8.91) e substituindo-se na segunda, obtem-se: a1 = 4∆ t2 (u1 − u0)− 4

∆ t v0 − a0

v1 = 2∆ t (u1 − u0)− v0

(8.92)

Substituindo-se as expressoes de v1 e a1, dadas em (8.92), na equacao de equilıbrio dinamico (8.88) parao instante t = t1, ou seja:

M a1 +C v1 +K u1 = f1 (8.93)

e, reagrupando-se os termos, obtem-se:

[K+

2

∆ tC+

4

∆ t2M

]u1 =

[2

∆ tC+

4

∆ t2M

]u0 +

[C+

4

∆ tM

]v0 +M a0 + f1 (8.94)

A Equacao (8.94) e resolvida em cada passo ∆ t fornecendo a solucao no instante t1 em funcao da cargaexterna no instante t1 e das respostas u0, v0 e a0 no instante t0.


Para se obter a analise de sensibilidade da resposta em relacao a uma variavel ou parametro no Metodo dasDiferencas Finitas a expressao (8.94) deve ser resolvida duas vezes ate o instante para o qual se deseja obtera analise de sensibilidade. Na primeira solucao as variaveis ou parametros em relacao aos quais a analise desensibilidade sera feita sao considerados com seus valores iniciais. Em seguida, a variavel ou parametro emquestao deve ser perturbada e uma nova analise deve ser realizada ate o instante desejado. Para o caso dese desejar a sensibilidade do vetor de deslocamentos no instante t = tp deve-se fazer:

du

d xi

∣∣∣∣t=tp

≈ ∆u

∆xi

∣∣∣∣t=tp

=u(tp,x+∆xiei)− u(tp,x)

∆xi(8.95)


A equacao de estado do problema de analise dinamica para uma analise via algoritmo de integracao diretade Newmark com α = 1

4 e δ = 12 pode ser escrita com base na Equacao (8.94), onde r = u1, ou seja:

c (u1(x)) =

[K+

2

∆ tC+

4

∆ t2M

]u1−

[2

∆ tC+

4

∆ t2M

]u0−

[C+

4

∆ tM

]v0−M a0−f1 = 0 (8.96)

A partir da Equacao (8.96) pode-se obter Z e pi conforme a Equacao (8.7) da seguinte forma:


Z = ∂ c∂ r = ∂ c

∂ u1=[K+ 2

∆ t C+ 4∆ t2 M

]pi = ∂ c

∂ xi=[∂ K∂ xi

+ 2∆ t

∂ C∂ xi

+ 4∆ t2

∂ M∂ xi

]u1 −

[2∆ t

∂ C∂ xi

+ 4∆ t2

∂ M∂ xi

]u0−[

∂ C∂ xi

+ 4∆ t

∂ M∂ xi

]v0 − ∂ M

∂ xia0 − ∂ f1

∂ xi

(8.97)

que permitem obter:

∂ u1

∂ xi= Z−1 pi

Quando as derivadas explıcitas de K, C e M sao obtidas analiticamente o metodo Direto e dito Analıtico,se obtidas por diferencas finitas, o metodo e dito Semi-analıtico.


Como ja mencionado, para a analise de sensibilidade pelo Metodo Adjunto uma restricao deve ser definida.Seja a restricao:

h (u1i) = u1i − u1i ≤ 0 (8.98)

onde u1i e u1i sao, respectivamente, a componente i do vetor de respostas u1 num dado instante t = tpe o valor prescrito para esta componente i de u1i no mesmo instante.

O vetor µ para este problema e dado por:

µ =∂ h

∂ u1= ei (8.99)

O vetor λ pode ser obtido a partir de µ usando a Equacao 8.15, ou seja:

Zt λ = −µ =⇒ λ

e finalmente a sensibilidade de h usando a Equacao 8.16, ou seja:

d h

d xi=

∂ h

∂ xi+ λtpi

onde:

∂ h

∂ xi= 0

As observacoes feitas no final da secao sobre problemas de fluxo termico transiente valem tambem agora.

Referencias Bibliograficas

[1] Conn, A. R., Gould, N. I. M. e Toint, P. L., ‘LANCELOT: A Fortran Package for Large-Scale Nonlinear

Optimization (Release A)’, Spring Series in Computational Mathematics, USA, 1992.

[2] Carrol, C. W., ‘The Created Response Surface Technique for Optimizing Nonlinear Restrained Systems’,

Operations Research, 9, 169–184, 1961.

[3] Fox, R. L., ‘Optimization Methods for Engineering Design’, Addison-Wesley, 1971.

[4] Frisch, K. R., ‘The Logarithmic Potential Method of Convex Programming’, University Institute of

Economics (manuscript), Oslo, Norway, 1955.

[5] Lindo Systems Inc., ‘Lingo Manual for Release 5.3’, Chicago, 1997.

[6] Murtagh, B. A e Saunders, M, A., ‘Minos 5.5 User’s Guide’, California: Universidade de Stanford, 1998.

[7] Nocedal, J. e Wright, S. J., ‘Numerical Optimization’, Segunda Edicao, Springer, 2006.

[8] Ben-Israel, A. e Greville, T. N. E., ‘Generalized Inverses: Theory and Applications’, Segunda Edicao,

Springer, 384 pag., 2003.

[9] Jasbir S. Arora, ‘Introduction to Optimum Design’, McGraw-Hill, 1989.

[10] Bathe, Klaus-Jurgen., ‘Finite Element Procedures in Engineering Analysis’, Prentice Hall Inc. 1996.

127

128 REFERENCIAS BIBLIOGRAFICAS

Apendice A

Exemplo de Analise de Sensibilidade

Neste apendice sera apresentada a analise de sensibilidade analıtica da matriz de rigidez de um elementoisoparametrico bilinear de 4 nos para problemas de estado plano em relacao a uma coordenada nodal.

A analise de sensibilidade da matriz de rigidez de um elemento finito e usada na otimizacao de formade estruturas modeladas por elementos finitos onde as coordenadas nodais sao as variaveis de projeto doproblema de otimizacao.

Um elemento finito e dito isoparametrico quando as mesmas funcoes de interpolacao sao usadas parainterpolar nao apenas grandezas cinematicas ( deslocamentos ), como e usual nos elementos finitos conven-cionais, mas tambem as grandezas geometricas, no caso coordenadas.

Coordenadas parametricas sao usadas nas funcoes de interpolacao. Assim,{x (ξ, η) =

∑4i=1 Ni(ξ, η)xi;

y (ξ, η) =∑4

i=1 Ni(ξ, η)yi;(A.1)

{u (ξ, η) =

∑4i=1 Ni(ξ, η)ui;

v (ξ, η) =∑4

i=1 Ni(ξ, η)vi;(A.2)

Onde, xi e yi sao as coordenadas nodais relativas aos eixos x e y, respectivamente, e ui e vi sao osdeslocamentos nodais relativos aos eixos x e y, respectivamente.

As funcoes de interpolacao Ni(ξ, η) sao dadas por:

N1 (ξ, η) =14 (1− ξ)(1− η) ;

N2 (ξ, η) =14 (1 + ξ)(1− η) ;

N3 (ξ, η) =14 (1 + ξ)(1 + η) ;

N4 (ξ, η) =14 (1− ξ)(1 + η) ;

(A.3)

As expressoes A.1 permitem mapear um ponto P (ξ, η) do quadrado representado no plano parametricopara um ponto P (x, y) no quadrilatero representado no plano cartesiano como indicado na Figura A.1.

Seja uma funcao ϕ(x, y). Se x e y forem definidos conforme as expressoes A.1, a relacao entre as derivadasde ϕ em relacao as coordenadas cartesianas e as derivadas de ϕ em relacao as coordenadas parametricas edada pela regra da cadeia: {

dϕdξ = dϕ

dxdxdξ + dϕ

dydydξ ;

dϕdη = dϕ

dxdxdη + dϕ

dydydη ;

(A.4)

ou, matricialmente, {dϕdξdϕdη

}=

[dxdξ

dydξ

dxdη

dydη

]{dϕdxdϕdy

}; (A.5)

129

130 APENDICE A. EXEMPLO DE ANALISE DE SENSIBILIDADE

Figura A.1: Mapeamento de um ponto P (ξ, η) do espaco parametrico para um ponto P (x, y) espaco carte-siano.

Pode-se definir agora a matriz Jacobiana J(ξ, η) como,

J (ξ, η) =

[dxdξ

dydξ

dxdη

dydη

]; (A.6)

e, fazendo uso de A.1, obtem-se:

J (ξ, η) =

[ ∑4i=1

dNi(ξ,η)dξ xi

∑4i=1

dNi(ξ,η)dξ yi∑4

i=1dNi(ξ,η)

dη xi

∑4i=1

dNi(ξ,η)dη yi

]; (A.7)

ou, matricialmente,

J (ξ, η) =

[N1(ξ, η),ξ N2(ξ, η),ξ N3(ξ, η),ξ N4(ξ, η),ξN1(ξ, η),η N2(ξ, η),η N3(ξ, η),η N4(ξ, η),η

]x1 y1x2 y2x3 y3x4 y4

; (A.8)

onde o sub-ındice ,ξ ou ,η significam a derivada em relacao a ξ e η respectivamente.

Sucintamente, A.8 pode ser reescrita como:

J (ξ, η)2×2 = DNx (ξ, η)2×4X4×2; (A.9)

Observando-se A.5, pode-se deduzir que a inversa da matriz Jacobiana Γ (ξ, η), dada por,

Γ (ξ, η) = J (ξ, η)−1

; (A.10)

transforma derivadas parametricas de ϕ em derivadas cartesianas de ϕ. Sendo assim, pode-se escrever:

131

u,x

u,y

v,xv,y

=

[Γ (ξ, η)2×2 02x2

02x2 Γ (ξ, η)2×2

]u,ξ

u,η

v,ξv,η

; (A.11)

ou, sucintamente,

u,c4×1 = Γu (ξ, η)4×4u,p4×1; (A.12)

Onde, u,c e o vetor que contem as derivadas cartesianas das componentes de deslocamentos u e v, u,p

o vetor que contem as derivadas parametricas das componentes de deslocamentos u e v e Γu a matriz quetransforma derivadas parametricas dos deslocamentos em derivadas cartesianas dos deslocamentos.

As expressoes A.2 permitem escrever:u,ξ

u,η

v,ξv,η

=

N1(ξ, η),ξ 0 N2(ξ, η),ξ 0

N1(ξ, η),η 0 N2(ξ, η),η 0

0 N1(ξ, η),ξ 0 N2(ξ, η),ξ0 N1(ξ, η),η 0 N2(ξ, η),η

· · · N3(ξ, η),ξ 0 N4(ξ, η),ξ 0

· · · N3(ξ, η),η 0 N4(ξ, η),η 0

· · · 0 N3(ξ, η),ξ 0 N4(ξ, η),ξ· · · 0 N3(ξ, η),η 0 N4(ξ, η),η

u1

v1u2

v2u3

v3u4

v4

(A.13)

ou, sucintamente,

u,p4×1 = DNd (ξ, η)4×8d4×1 (A.14)

sendo d o vetor dos deslocamentos nodais.E possıvel demonstrar tambem que o determinante da matriz Jacobiana e o fator de escala que transforma

a area elementar dξdη no quadrado parametrico em area elementar correspondente no quadrilatero do planocartesiano dA, como indicado a seguir.

dA = det (J (ξ, η))dξdη; (A.15)

A matriz de rigidez de um elemento finito qualquer pode ser obtida por:

K =

∫BtCBdv; (A.16)

onde a matriz B e a matriz de compatibilidade cinematica que transforma deslocamentos nodais emdeformacoes no interior do elemento.

ε = Bd; (A.17)

E a matriz C e a matriz constitutiva que transforma o vetor de deformacoes ε em vetor de tensoes σpara o material de comportamento linear elastico ( lei de Hooke ).

σ = Cε; (A.18)

No caso de um problema plano, as componentes do vetor de deformacao ε sao:

εx = u,x

εy = v,yγxy = u,y + v,x

(A.19)

132 APENDICE A. EXEMPLO DE ANALISE DE SENSIBILIDADE

ou, matricialmente,

εxεyγxy

=

1 0 0 00 0 0 10 1 1 1

u,x

u,y

v,xv,y

(A.20)

ou, sucintamente,

ε = Hu,c (A.21)

Usando agora A.12 e A.14, a expressao A.21 pode ser reescrita como:

ε = H Γu (ξ, η)DNd (ξ, η) d; (A.22)

O que permite concluir que para o elemento em questao vale,

B (ξ, η)3×8 = H3×4Γu (ξ, η)4×4DNd (ξ, η)4×8; (A.23)

e a matriz de rigidez pode ser dada por:

K8×8 = t

∫ 1

−1

∫ 1

−1

B (ξ, η)t8×3C3×3B (ξ, η)3×8det (J (ξ, η))dξdη; (A.24)

Sendo t a espessura do elemento. A integracao da matriz de rigidez e feita no plano parametrico porintegracao numerica porque, para o elemento isoparametrico, as funcoes em questao estao definidas no planoparametrico.

A matriz C vale para problemas de estado plano de tensao:

C =E

1− υ2

1 υ 0υ 1 00 0 1−υ

2

; (A.25)

Para problema de estado plano de deformacao:

C =E (1− υ)

(1 + υ) (1− 2υ)

1 υ(1−υ) 0

υ(1−υ) 1 0

0 0 1−2υ2 (1−υ)

; (A.26)

sendo E o modulo de elasticidade e ν o coeficiente de Poisson do material.A integracao da matriz de rigidez e feita por integracao numerica pelo Metodo de Gauss. Se forem usados

ng pontos de Gauss com coordenadas parametricas ξgi e ηgi e pesos de integracao wξi e wηi, A.24 pode serreescrita como:

K8×8 = t

ng∑i=1

B (ξgi, ηgi)t8×3C3×3B (ξgi, ηgi)3×8det (J (ξgi, ηgi))wξiwηi; (A.27)

Agora, uma vez revisitada a formulacao da matriz de rigidez K de um elemento isoparametrico quadri-lateral de 4 nos, a questao da analise de sensibilidade da matriz de rigidez K em relacao a uma coordenadanodal arbitraria pode ser formulada. A coordenada sera designada por xij que corresponde a coordenada nalinha i (no i ) e coluna j (x para j = 1 e y para j = 2) da matriz X definida em A.8 e A.9.

A expressao A.27 nos permite obter a expressao para a derivada de K em relacao a coordenada xij :

dK

dxij 8×8

= t{∑ng

i=1

[dBi

dxij

t

8×3C3×3Bi3×8 +Bi

t8×3C3×3

dBi

dxij 3×8

]det (Ji) +

Bti8×3C3×3Bi3×8

d(detJi)dxij

}wξiwηi;

(A.28)

133

Onde Bi e Ji sao agora os valores das matrizes B (ξ, η) e J (ξ, η) calculados nos pontos de Gauss ξgi, ηgi.Fazendo k = 2/j, a sensibilidade do determinante da matriz Jacobiana em qualquer ponto ξ, η em relacao axij pode ser obtida por:

d(det (J(ξ, η))

dxij= (−1)kDNx(ξ, η)1,i

{∑4m=1 DNx (ξ, η)2,mXm,k

}+

(−1)jDNx (ξ, η)2,i

{∑4m=1 DNx (ξ, η)1,mXm,k

};

(A.29)

A sensibilidade da matriz B em relacao a xij e dada por:

dB(ξ, η)

dxij 3×8

= H3×4d(Γu (ξ, η))

dxij 4×4

DNd (ξ, η)4×8; (A.30)

sendo que,

dΓu(ξ, η)

dxij 4×4

=

dΓ(ξ,η)dxij 2×2

02×2

02×2dΓ(ξ,η)dxij 2×2

; (A.31)

A sensibilidade da inversa da matriz Jacobiana, Γ(ξ, η) em relacao a coordenada xij pode ser obtida apartir do produto indicado a seguir:

JΓ = I; (A.32)

Derivando-se os dois lados da equacao A.32 chega-se a,

d(JΓ)

dxij=

d(J)

dxijΓ+ J

d(Γ)

dxij= 0; (A.33)

Da qual se pode obter,

d(Γ)

dxij= −J−1 d(J)

dxijΓ = −Γd(J)

dxijΓ; (A.34)

A sensibilidade da matriz Jacobiana J (ξ, η) em relacao a coordenada xij pode ser obtida por:

d (J (ξ, η))

dxij= DNx (ξ, η)

d (X)

dxij= DNx (ξ, η)E; (A.35)

sendo que os elementos da matriz E de dimensao 4 × 2, como a matriz X, serao todos nulos a excecao doelemento eij da linha i e coluna j que devera ter o valor 1.

programa˘c~ao de matem atica: teoria, algoritmos e aplica...

Documents