[Robson] 5. Análise de Sensibilidade

Analise de Sensibilidade

Alexandre Salles da Cunha

DCC-UFMG, Abril 2010

Alexandre Salles da Cunha Analise de Sensibilidade

Par primal-dual

min c ′x

Ax = b

x ≥ 0

max p′b

p′A ≤ c ′

Analise de sensibilidade envolvera avaliar o impacto nas solucoes otimasx∗, p∗ do par primal-dual quando houver:

Adicao, remocao de uma nova variavel.

Adicao de uma restricao de desigualdade e igualdade.

Modificacoes nos vetores b, c .

Modificacoes em colunas basicas e nao basicas Aj .

A ideia da analise de sensibilidade consiste em tentar restaurar aotimalidade diante das perturbacoes acima, sem resolver o PL ”do zero”.


Adicao de uma nova variavel

Vamos supor que uma nova variavel xn+1 com custo cn+1 e colunatecnologica An+1 seja inserida no PL.

Claramente dispor de uma nova variavel nao altera a viabilidade dasolucao basica corrente. Em particular, (x∗, 0) e uma solucao basicaviavel para o novo programa linear.

Assim sendo, a solucao x∗ continuara basica otima se a restricao dualassociada a nova variavel for satisfeita pela base B associada a x∗.

Condicao a verificar

Diante da introducao de xn+1 x∗ permanece otima secn+1 = cn+1 − cBB−1An+1 ≥ 0.

Caso cn+1 < 0, continuamos o metodo Simplex tendo como baseinicial avancada a base otima do programa anterior.


Adicao de nova variavel - exemplo

Problema Original

min −5x1 − x2 + 12x3

3x1 + 2x2 + x3 = 10

5x1 + 3x2 + x4 = 16

x1 . . . x4 ≥ 0

cuja solucao otima e (2, 2, 0, 0) e oquadro otimo e:

x1 x2 x3 x4

w = 12 0 0 2 7

x1 = 2 1 0 -3 2x2 = 2 0 1 5 -3

Introduzindo a variavel x5 com custo c5 = −1 e A5 = (1 1)′, e notandoque neste caso B−1 e dada pelas duas ultimas colunas no Tableauanterior, temos o novo quadro:

x1 x2 x3 x4 x5

w = 12 0 0 2 7 - 4

x1 = 2 1 0 -3 2 -1x2 = 2 0 1 5 -3 2


Adicao de nova variavel - exemplo

Fazendo o pivoteamento correspondente a entrada de x5 e saıda de x2,temos:

Quadro original

x1 x2 x3 x4 x5

w = 12 0 0 2 7 - 4

x1 = 2 1 0 -3 2 -1x2 = 2 0 1 5 -3 2

Quadro otimo resultante

x1 x2 x3 x4 x5

w = 16 0 2 12 1 0

x1 = 3 1 0.5 -0.5 0.5 0x5 = 1 0 0.5 2.5 -1.5 1


Adicao de uma restricao - desigualdade

Vamos assumir que a′m+1x ≥ bm+1 seja inserida no PL.

Introduzimos uma variavel de folga xn+1, reescrevemos a restricaoa′m+1x − xn+1 = bm+1 para obter um problema novamente na forma

padrao, definido pelo poliedro P = {x ∈ Rn+1+ : Ax = b} onde:

A =

[

A 0a′m+1 −1

]

, b =

[

b

bm+1

]

Se B denota a base otima do programa anterior, a base associada ao

novo programa, B e dada por B =

[

B 0a′ −1

]

, onde a′ e o vetor de

m entradas de am+1 correspondente aos ındices das colunas basicas

que definem B . Nao e difıcil verificar que B−1

=

[

B−1 0a′B−1 −1

]

O novo vetor de custos reduzidos e dado por

c =[

c ′ 0]

−[

c ′B 0]

[

B−1 0a′B−1 −1

] [

A 0a′m+1 −1

]

=

[

(c ′ − c ′BB−1A) 0]

≥ 0, logo B−1

e dual viavel.


Introducao de uma desigualdade - exemplo

Introduzindo a restricao x1 + x2 ≥ 5 no PL do exemplo anterior:

Problema Original

min −5x1 − x2 + 12x3

3x1 + 2x2 + x3 = 10

5x1 + 3x2 + x4 = 16

x1 . . . x4 ≥ 0

Quadro otimo:

x1 x2 x3 x4

w = 12 0 0 2 7

x1 = 2 1 0 -3 2x2 = 2 0 1 5 -3

Quadro dual viavel, de partida para o Dual Simplex

x1 x2 x3 x4 x5

w = 12 0 0 2 7 0

x1 = 2 1 0 -3 2 0x2 = 2 0 1 5 -3 0x5 = -1 0 0 2 -1 1


Introducao de uma desigualdade - exemplo

Quadro dual viavel, de partida para o Dual Simplex

x1 x2 x3 x4 x5

w = 12 0 0 2 7 0

x1 = 2 1 0 -3 2 0x2 = 2 0 1 5 -3 0x5 = -1 0 0 2 -1 1

Sai da base: x5, entra na base: x4

Quadro final resultante

x1 x2 x3 x4 x5

w = 5 0 0 16 0 0

x1 = 0 1 0 1 0 0x2 = 8 0 1 -15 0 0x4 = 1 0 0 -2 1 -1


Introducao de restricao de igualdade

Adicionamos a restricao a′m+1x = bm+1, violada pela solucao otima do PLanterior.

Novo dual

max p′b + pm+1bm+1

p′A + pm+1am+1 ≤ c ′

Se p∗ denota a solucao basica otima do dual anterior, (p∗, 0) e umasolucao viavel para o novo dual.

Sendo p∗ basica, temos que m das restricoes duais p′A ≤ c ′ saolinearmente independentes e ativas.

Entretanto, para o novo ponto dual (p∗, 0), nao temos a garantia deque m + 1 restricoes duais li dentre p′A + pm+1am+1 ≤ c ′ seraojustas. Assim sendo, nao podemos garantir que (p∗, 0) e uma solucaobasica para o novo poliedro dual.


Introducao de restricao de igualdade

Assumimos que a′m+1x∗ > bm+1 e M suficientemente grande e

introduzimos o PL auxiliar:

min c ′ + Mxn+1

Ax = b

a′m+1x − xn+1 = bm+1

x ≥ 0, xn+1 ≥ 0

Uma base inicial viavel para o PL acima e obtida usando-se ascolunas basicas que definiem x∗ e a coluna associada a xn+1. A

matriz basica resultante B =

[

B 0a′ −1

]

e viavel para o PL auxiliar.

Por este motivo, reotimizamos com o Simplex Primal aplicadopartindo da base viavel B.

Se na solucao do PL otimizado, M for suficientemente grande e oprograma for viavel, teremos xn+1 = 0.


Modificacoes no vetor de fatores b

Desejamos avaliar as modificacoes implicadas por alterar b para b + δei :

Se B−1(b + δei ) ≥ 0, a otimalidade da solucao basica anterior egarantida (nada mudou no dual).

Avaliando condicoes para B−1(b + δei) ≥ 0

Seja g = (β1i , β2i , . . . , βmi ) a i -esima coluna de B−1.

Entao B−1(b + δei ) ≥ 0 implica que:

xB + δg ≥ 0 ou

xB(j) + δβji ≥ 0 j = 1, . . . ,m.

Equivalentemente:◮ δ ≥ −

xB(j)

βji, se βji > 0

◮ δ ≤ −xB(j)

βji, se βji < 0


Modificacoes no vetor de fatores b - exemplo

Vamos considerar modificar b1 para b1 + δ no Tableau Otimo dado por:

x1 x2 x3 x4

w = 12 0 0 2 7

x1 = 2 1 0 -3 2x2 = 2 0 1 5 -3

Observe que g = (−3 5) e entao temos:

x1 = 2− 3δ ≥ 0→ δ ≤ 23 .

x2 = 2 + 5δ ≥ 0→ δ ≥ −25


Modificacoes no vetor de custos c

Vamos considerar as implicacoes decorrentes de modificar cj para cj + δ, ocusto de uma variavel nao basica j :

A modificacao nao afeta a viabilidade primal, apenas a viabilidadedual (otimalidade dual).

Se cj + δ − cBB−1Aj ≥ 0 ou seja se δ ≥ −c j a base anterior continuaotima. Caso esta condicao nao se verifique, aplicamos o primalsimplex, introduzindo a variavel xj na base.


Modificacoes no custo de uma variavel basica

Vamos considerar as implicacoes decorrentes de modificar cj paracj + δ, o custo de uma variavel basica j .

Vamos assumir que j seja a variavel basica associada a l−esima linhado Tableau, isto e j = B(l) e entao cB = cB + δel .

Temos que assegurar que (cB + δel )B−1Ai ≤ ci ,∀i 6= j , uma vez que

todos os custos reduzidos, exceto c j sao afetados pela modificacao.

Definindo qli como a l -esima entrada do vetor B−1Ai temos queδqli ≤ c i ,∀i 6= j .


Exemplo - modificacoes nos custos

Para o exemplo anterior:

x1 x2 x3 x4

w = 12 0 0 2 7

x1 = 2 1 0 -3 2x2 = 2 0 1 5 -3

Modificacoes admissıveis (que ainda preservam a otimalidade da baseatual) nas variaveis:

Nao basicas:◮ δ3 ≥ −c3 = −2◮ δ4 ≥ −c4 = −7

Basicas: adicionando δ1 a c1, temos para j = 1,B(1) = 1,q12 = 0, q13 = −3, q14 = 2.

◮ δ1q12 ≤ c2, triv. satisfeita.◮ δ1q13 ≤ c3 → δ1 ≥ −

23

◮ δ1q14 ≤ c4 → δ1 ≥72


Mudancas no vetor tecnologico Aj

Caso 1: j e uma variavel nao basica:

A viabilidade da base otima (em relacao ao primal) nao e afetada.

E necessario verificar se a otimalidade (viab. dual) e afetada, atravesda nao negatividade do custo reduzido c j .

Vamos considerar que a entrada aij de A foi alterada para aij + δ.Entao precisamos garantir que cj − p′(Aj + δei ) ≥ 0 ouequivalentemente c j − δpi ≥ 0, onde p′ = c ′BB−1.

Caso a condicao acima seja violada, j deve entrar na base (PrimalSimplex).


Mudancas no vetor tecnologico Aj

Caso 2: j e uma variavel basica:

A viabilidade da base otima pode ser afetada, tanto no primal quantono dual.

Assumindo que aij seja alterado para aij + δ, o conjunto de valoresadmissıveis para a variacao resultar ainda em uma base otima e umintervalo (assim como nos casos anteriores).

Assumindo solucao primal e dual otimas nao dengeradas dadas porx∗, p, se a coluna Aj for modificada para Aj + δei temos que:

c ′x(δ) = c ′x∗ − δx∗

j pi + O(δ2)

Interpretacao em termos do problema da dieta: se aij aumenta em δ,ganhamos de graca, δ unidades do nutriente i por unidade doalimento j . Uma vez que pi denota o custo marginal do nutriente i ,δpix

∗

j denota a reducao de custo esperada.


Dependencia da otimalidade em funcao de b

Reescrevendo a regiao de viabilidade primal para deixar explıcita adependencia do vetor b, temos que

P(b) = {x : Ax = b, x ≥ 0}

Vamos definir S = {b : P(b) 6= ∅}.

Observe entao que S pode ser reescrito como S = {Ax : x ≥ 0} que eum conjunto convexo.

Para qualquer vetor b ∈ S , vamos redefinir o custo otimo doProblema primal como:

F (b) = minx∈P(b)c′x



Vamos assumir que o espaco dual p′A ≤ c ′ seja nao vazio.

Por dualidade, temos que F (b) >∞,∀b ∈ S , isto e, o problemaprimal admite otimo finito para todo b.

Vamos tentar compreender a estrutura da funcao F (b), b ∈ S . Paratanto, vamos nos fixar em um determinado b∗ ∈ S .

Vamos supor que o objetivo otimo F (b∗) e dada por uma base otimaB associada a uma solucao basica xB = B−1b∗ nao degenerada e queo correspondente vetor de custos reduzidos seja nao negativo.



Sendo nao denenerada, podemos modificar b∗ para b e desde queb∗ − b seja suficientemente pequena B−1b ≥ 0 sera uma solucaobasica viavel otima para o problema perturbado.

Logo, para b suficientemente proximo de b∗, F (b) = c ′BB−1b = p′b.

Isto e, nas vizinhancas de b∗, F (b) e uma funcao linear de b e seugradiente e dado por p.

Teorema

O custo otimo F (b) e uma funcao convexa de b no conjunto S .


Estrutura de F (b)

Teorema

O custo otimo F (b) e uma funcao convexa de b no conjunto S .

Prova

Tomemos b1, b2 ∈ S e seja x i : i = 1, 2 as correspondentes solucoesque minimizam F (b1),F (b2), respectivamente.

Tome um escalar λ ∈ [0, 1] e defina y = λx1 + (1− λ)x2:◮ y ∈ P(λb1 + (1− λ)b2)→ y e viavel.

Observe que:

F (λb1 + (1− λ)b2) ≤ c ′y

= λc ′x1 + (1− λ)c ′x2

= λF (b1) + (1− λ)F (b2)


Elaborando melhor o Teorema anterior

Vamos elaborar o Teorema, avaliando agora o dual abaixo, que assumimosser viavel:

max p′b

p′A ≤ c ′

Por dualidade, para todo b ∈ S , F (b) = ′b para algum p.

Sendo A uma matriz de posto m (completo), o poliedro dual possuipelo menos um ponto extremo.

Sejam p1, . . . , pN os pontos extremos do poliedro dual.

Entao temos que F (b) = maxi=1,...,N(pi )′b, b ∈ S


Interpretando F (b) = maxi=1,...,N(pi)′b, b ∈ S

F e dado pelo maximo de uma colecao finita de funcoes lineares.F e entao dado pelo envelope superior de um conjunto finito defuncoes lineares, sendo entao linear por partes e convexa (provaalternativa do teorema anterior).


Sobre a diferenciabilidade de F (b) em relacao a b

Para alguns valores de b (nos pontos onde duas funcoes lineares(pi)′b e (pj)′b se encontram), F (b) nao e diferenciavel.

Nestes pontos, o programa dual admite mais de uma solucao otima.Para tais valores de b, qualquer combinacao linear convexa de pi e pj

fornecem um vetor dual otimo (subgradiente de F (b) em b !).

Consequentemente, para estes valores de b a solucao primal edegenerada. Vimos que para uma solucao primal nao degenerada,F (b) e localmente linear com b, nao podendo ser associada a umponto nao diferenciavel de F (b).


Comportamento de F (b)

Vamos avaliar o comportamento de F (b) quando um determinadotipo de modifica cao ocorre em b∗.Vamos verificar o que ocorre com F (b) quando, para b∗ e d fixos,b = b∗ + θd , para θ um escalar.Pela definicao de F (b) temos que:

F (b(θ)) = F (θ) = maxi=1,...,N(pi)′(b∗ + θd), b∗ + θd ∈ S


O conjunto de solucoes duais otimas

Definicao - subgradiente

Seja F uma funcao convexa definida em um conjunto convexo S . Seja b∗

um elemento de S . Dizemos que um vetor p e um subgradiente de F emb∗ se:

F (b∗) + p′(b − b∗) ≤ F (b),∀b ∈ S

Para a definicao do subgradiente, nao e feita nenhuma hipotese dediferenciabilidade de F .

Observe que o subgradiente generaliza o conceito de gradiente parauma funcao convexa diferenciavel definida em um conjunto convexo.


Subgradientes de F (b)

Quando b∗ e um ponto para o qual (pi)′b∗ = (pj)′b∗, isto e b∗ defineuma quina de F (b), existem varios subgradientes.Quando F (b) e linear nas vizinhancas de b∗ ha apenas umsubgradiente.



Teorema

Assuma que o problema min c ′x , x ∈ P(b∗) assuma custo otimo finito.Entao o vetor p e uma solucao otima para o problema dual associado se esomente se p for um subgradiente de F (b) em b∗.

Prova: →

Por dualidade forte temos p′b∗ = F (b∗).

Tome b ∈ S e x ∈ P(b). Por dualidade fraca temos p′b ≤ c ′x .

Tomando o mınimo em x temos que p′b ≤ F (b).

Entao p′b − p′b∗ ≤ F (b)− F (b∗) que implica queF (b∗) + p′(b − b∗) ≤ F (b) e logo p e um subgradiente de F em b∗.



Prova: ←

Hipotese: F (b∗) + p′(b − b∗) ≤ F (b) (p e subgradiente).

Tome x ≥ 0, seja b = Ax e observe que x ∈ P(b).

Por dualidade fraca F (b) ≤ c ′x .

Entao temos:

p′Ax = p′b

≤ F (b)− F (b∗) + p′b∗

≤ c ′x − F (b∗) + p′b∗

Uma vez que p′Ax ≤ c ′x − F (b∗) + p′b∗ deve valer para qualquer x eque −F (b∗)p′b∗ e um valor que independe de x , p′A ≤ c ′. Logo p′ edual viavel.

Em particular para x = 0 temos F (b∗) ≤ p′b∗. Por dualidade fracatemos que toda solucao dual viavel q satisfaz q′b ≤ F (b∗) ≤ p′b∗.Logo p∗ e otima para o dual.


Avaliacao da otimalidade em funcao de c

Vamos desenvolver raciocınio analogo para a dependencia daotimalidade em funcao de modificacoes no vetor de custos c .Manteremos A e b fixos e perturbaremos c .

Para tanto, vamos considerar o espaco de viabiliade dual p′A ≤ c ′.

Vamos definir Q(c) = {p : p′A ≤ c ′} e T = {c : Q(c) 6= ∅}.

Dados c1, c2 ∈ T , existem p1, p2 (respectivamente) tais que(pi)′A ≤ c ′. Para qualquer escalar λ ∈ [0, 1], temos(λ(p1)′ + (1− λ)(p2)′)A ≤ λ(c1)′ + (1− λ)(c2)′ e portantoλ(p1)′ + (1− λ)(p2)′ ∈ T .

Consequentemente T e convexo.



Tomando c 6∈ T (dual inviavel), o problema primal e ilimitado. Poroutro lado, se c ∈ T o custo primal e finito.

Entao vamos assumir que c ∈ T e vamos denotar o custo primalotimo por G (c).

Vamos denotar por x1, . . . , xN as solucoes basicas do poliedro{x ∈ R

n+ : Ax = b}. Assim sendo, temos que

G (c) = mini=1,...,Nc ′x i

e G (c) corresponde ao envelope inferior de uma colecao de funcoes elineares, sendo uma funcao linear por partes concava.



Se para um valor c∗ o programa primal admite uma unica solucaootima x i , entao temos que (c∗)′x i < (c∗)′x j : ∀j 6= i .Para todo c suficientemente proximo a c∗, (c∗)′x i < (c∗)′x j : ∀j 6= i

deve continuar valendo. Desta forma, para solucoes primais unicasG (c) = c∗x i .Para o caso de solucao primal multipla, o correspondente valor de c

deve ser induzir uma quina de G (c).


Em sıntese

Teorema1 O conjunto T de todos os valores de c para os quais o custo otimo e

finito e convexo.

2 A funcao custo otimo G (c) e uma funcao concava de c em T .

3 Se para um determinado valor c , a solucao primal otima e unica,entao G e linear nas vizinhancas de c e seu gradiente e dado por x∗.


Documents

[Robson] 5. Análise de Sensibilidade