[Robson] 3. Método Simplex

Metodo Simplex

Alexandre Salles da Cunha

DCC-UFMG, Marco 2010

Alexandre Salles da Cunha Metodo Simplex

Ideias centrais do metodo

Se um PL na forma padrao possui uma solucao otima, entao existeuma solucao basica viavel otima para o problema.

O Metodo Simplex baseia-se neste fato. Iniciando em uma solucaobasica viavel, move-se para uma solucao basica vizinha de menorcusto.

Este processo continua ate que uma direcao que permita reduzir afuncao objetivo nao seja encontrada, comprovando a otimalidade dasolucao em maos.


O Problema a ser resolvido

min c ′x

s.t.: Ax = b

x ≥ 0

onde A ∈ Rm×n, b ∈ R

a j-esima coluna de A e designada por Aj

a i -esima linha de A e designada por ai .


Uma ideia muito comum nos algoritmos de otimizacao

Dada uma solucao viavel, procure uma solucao viavel mais barata nasvizinhancas da solucao atual.

Esta procura de solucoes viaveis normalmente e feita tentandomovimentar sobre uma direcao viavel aprimorante.

Se uma direcao aprimorante nao existe, a solucao corrente e umotimo local para o problema (nao necessariamente global).

No caso do PL, todo otimo local e global, uma vez que o PL e uproblema de otimizacao convexa (minimizar uma funcao conexa sobreum conjunto convexo).

O Metodo Simplex explora exatamente esta ideia.


Direcao viavel

Seja x um ponto em um poliedro P . Um vetor d ∈ Rn e dito ser uma

direcao viavel em x , se existir um escalar positivo θ para o qualx + θd ∈ P .


Obtendo uma direcao viavel conveniente

Filosofia para escolha da direcao viavel

Vamos considerar a possibilidade de mover a partir de x para umasolucao basica vizinha (adjacente).

Por definicao, uma solucao basica adjacente a x deve compartilharn − 1 restricoes justas, cujos vetores de definicao sao l.i.

Como as restricoes a′ix = bi ,∀i = 1, . . . m precisam ser satisfeitas emqualquer solucao viavel, escolhemos uma direcao d para a qualpermitamos acrescer uma unica variavel nao basica.

Logo, para obter uma solucao basica adjacente a x precisarmos nosmovimentar ao longo de uma direcao viavel que permita que apenasuma componente nao basica de x torne-se basica.


Deducao algebrica da direcao

Para os ındices j 6∈ {B(1), . . . ,B(m)} das componentes nao basicas:◮ dj = 1 para uma unica variavel nao basica◮ dj = 0 para todas as demais variaveis nao basicas.◮ Vamos designar por j o ındice da coluna nao basica liberado para se

tornar basica.

Para os ındices j ∈ {B(1), . . . ,B(m)}◮ Uma vez que A(x + θd) ∈ P para algum θ > 0, temos que

Ax + θAd = b e entao Ad = 0.◮ Entao: 0 = Ad =

∑ni=1 Aidi =

∑mi=1 AB(i)di + Aj = Aj + BdB .

◮ Portanto dB = −B−1Aj uma vez que B admite inversa.

Direcao basica

Vamos chamar a direcao basica construıda acima como a j-esima direcaobasica


E a garantia das restricoes de nao negatividade

Temos que garantir que xB + θdB ≥ 0:

Apenas uma varivel nao basica, de ındice j , sera aumentada.

Logo temos que nos preocupar apenas com a variacao das variaveisbasicas. Temos dois casos a considerar:

◮ Vamos supor que xB seja nao degenerada. Entao xB > 0 e entao existeum θ > 0 suficientemente pequeno que garante a viabilidade.

◮ Se xB for degenerada, existe xB(i) = 0 para algumi ∈ {B(1), . . . , B(m)}. Neste caso, se para este ındice i tivermos−B−1

i d < 0, qualquer movimento no sentido de d faz com que arestricao xB(i) seja violada. Assim sendo, a direcao d neste caso nao eviavel.


Exemplo no caso degenerado onde d nao e viavel

Em E (basica nao degenerada), temos como basicas: x2, x4, x5 e nao basicas: x1, x3.Direcao viavel: segmento EF , que consiste em aumentar x1, mantendo x3 em zero.

Em F (basica degenerada), vamos considerar que as variaveis nao basicas sejam x3, x5.Observe que x4 e basica em 0. Direcao basica: segmento FG , correpondendo a aumentarx3 e manter x5 em zero, e nao e viavel.


Qual o efeito na funcao objetivo de mover ao longo de d

Sendo d a j-esima direcao basica, ao mover no sentido positivo de d ,a taxa de variacao da funcao objetivo e por

∑ni=1

∂f∂xi

di =∑n

i=1 cidi .

Uma vez que dB = −B−1Aj temos que∑n

i=1 cidi = cj − cBB−1Aj ,onde cB = (cB(1), . . . , cB(m)).

◮ A parcela cj e a taxa unitaria de variacao por permitir j aumentar.◮ A parcela −cBB−1Aj e referente a compensacao das mudancas nas

variaveis basicas, necessaria para garantir a viabilidade, Ax = b.

Definicao

Seja x uma solucao basica, B a base associada a x e cB o vetor de custosdas variaveis basicas. Para todo j = 1, . . . , n, definimos o custo reduzidoc j da variavel xj por meio de :

c j = cj − c ′BB−1Aj


Exemplo

Vamos considerar o seguinte exemplo:

min c1x1 + c2x2 + ccx3 + c4x4

s.t.: x1 + x2 + x3 + x4 = 2

2x1 + 3x3 + 4x4 = 2

x ≥ 0

Fazendo B = [A1 A2], temos uma matriz cujas colunas sao l.i.

Fixando x3 = x4 = 0 e resolvendo o sistema, (x1, x2) = (1, 1).

Assumindo que d seja a direcao basica associada a variavel nao basicax3, temos: dB = −B−1A3 = [−3

212 ]′.

c3 = c3 − 3c1/2 + c2/2


Custo reduzido para as variaveis basicas

Aplicando a definicao: cB(i) = cB(i) − c ′BB−1AB(i) = cB(i) − c ′BeB(i),onde eB(i) e um vetor m dimensional com todas as entradas nulas,exceto a B(i)-esima entrada que e 1.

Logo, cB(i) = cB(i) − c ′BeB(i) = cB(i) − cB(i) = 0


Criterio de Otimalidade

Dada nossa interpretacao de custos reduzidos como a taxa de variacao dafuncao objetivo na medida em que movimentamos ao longo de umadirecao, temos o seguinte resultado:

Teorema

Considere uma solucao basica x associada a uma base B. Assuma que cseja o correspondente vetor de custos reduzidos.

1 Se c ≥ 0, entao x e uma solucao otima.

2 Se x e otima e nao degenerada, entao c ≥ 0.


Prova

Prova

(1):

Vamos assumir c ≥ 0 e que y denote uma solucao viavel qualquerpara o problema, para a qual determinamos uma direcao viaveld = y − x (e viavel por convexidade !).

A viabilidade de x , y implica que Ax = Ay = b e entao Ad = 0.

Entao Ad = 0 = BdB +∑

i∈N Aixi = 0 (N e o conj. dos ındices dasvariaveis nao basicas em x).

Logo dB = −∑

i∈N B−1Aidi

Entao temos:c ′d = c ′BdB +

∑

i∈N cidi =∑

i∈N(ci − c ′BB−1Ai)di =∑

i∈N c idi .

Para qualquer i ∈ N, temos que xi = 0 e entao di = yi − xi ≥ 0.Logo c ′d =

∑

i∈N c idi ≥ 0


Prova

Prova

(2), por contradicao:

Suponha que x seja uma solucao basica viavel otima, nao degeneradae que exista j : c j < 0.

Entao j necessariamente deve ser ındice de uma variavel nao basica,uma vez que c i = 0,∀i ∈ {B(1), . . . ,B(m)}.

Considere a direcao basica j, d. Esta direcao e necessariamente viaveldado que x e nao degenerada.

Entao existe θ > 0 tal que x + θd e uma solucao viavel. Por outrolado c ′(x + θd) = c ′x + θc ′d < c ′x, contrariando a hipotese de que xe ’otima.


Observacoes

Uma solucao otima x pode ser tal que o custo reduzido de algumavariavel nao basica e negativo.

De acordo com o teorema para decidir se uma solucao basica viavelnao degenerada x e otima, precisamos verificar os custos reduzidos desuas n − m componentes nao basicas.

No caso de uma solucao basica degenerada, um teste igualmentesimples nao e disponıvel.


Bases otimas

Definicao

Uma base B e otima se:

1 B−1b ≥ 0 e

2 c ′ = c ′ − c ′BB−1B−1A ≥ 0.

Observe que, diante desta definicao:

Se uma base otima B e encontrada, a solucao basica associada eviavel, satisfaz as condicoes de otimalidade e portanto e otima.

Por outro lado uma solucao basica viavel otima degenerada naonecessariamente garante custos reduzidos nao negativos.

Vale lembrar que mais de uma base podem ser associadas a mesmasolucao basica (no caso degenerado).


Desenvolvimento do metodo

De inıcio, vamos assumir a hipotese de que todos as solucoes basicasde P = {x ∈ R

n : Ax = b, x ≥ 0} sao nao degeneradas.

Em seguida relaxaremos esta hipotese.


Desenvolvimento do Metodo

Vamos supor que estejamos em um ponto x , solucao basica viavelnao degenerada de P e que tenhamos avaliado os custos reduzidos deforma que c j ≥ 0 : ∀j 6∈ {B(1), . . . ,B(m)}. Entao, pelo resultadoanterior, concluimos que x resolve o PL.

Caso contrario, existe j 6∈ {B(1), . . . ,B(m)} : c j < 0.

Entao a j−esima direcao basica d , obtida fazendo-se dB = −B−1Aj ,dj = 1 e dk = 0,∀k 6∈ {j ,B(1), . . . ,B(m)} e uma direcao viavel, dereducao de custo.

Movendo ao longo de d , a partir de x , a componente xj torna-sepositiva, as componentes xk : k 6∈ {j ,B(1), . . . ,B(m)} permanecemem 0 e as variaveis basicas sao alteradas.

Uma vez que d e uma direcao de aprimoramento de custos, edesejavel nos mover o quanto pudermos ao longo desta direcao.


Garantindo a satisfacao das restricoes de nao negatividade

x(θ) = x + θd , θ ≥ 0

O maximo que podemos andar na direcao d e dado porθ∗ = max{θ ≥ 0 : x + θd ∈ P}.

Dado que Ad = 0, Ax(θ) = b e precisamos verificar apenas asrestricoes de nao negatividade.

Se d ≥ 0, x(θ) ≥ 0 e entao θ∗ = ∞.

Caso contrario, existe i ∈ {B(1), . . . ,B(m)} : di < 0. Para garantirxi + θdi ≥ 0 temos que θ ≤ − xi

di.

Entao θ∗ = min{− xi

di: dB(i) < 0}

Observe que θ∗ > 0 como consequencia da nao degeneracao de x .


O novo ponto obtido

Assumindo que θ∗ e finito, y = x(θ∗) = x + θ∗d .

Entao:

yj = xj + θ∗ = −xB(l)

dB(l), onde l ∈ {B(1), . . . ,B(m)} denota o ındice da

variavel basica que definiu θ∗.

Todas as componentes basicas de x , pelo modo como θ∗ e definidocontinuam nao negativas.

Em particular, para l temos:

yB(l) = xB(l) + θdB(l) = xB(l) −xB(l)

dB(l)dB(l) = 0

o que sugere que a coluna Aj substitua a coluna AB(l) na base, umavez que houve uma troca das restricoes de nao negatividade queficaram justas.


Exemplo - continuacao

Considerando a solucao basica x = (1, 1, 0, 0) e lembrando quec3 = −3c1 + c2

2 + c3.

Se c = (2, 0, 0, 0) temos que c3 = −3. A correspondente direcaobasica e (−3

2 , 12 , 1, 0).

Considerando pontos da forma x + θd , θ > 0, a unica componente dex que cai e x1 (note que d1 < 0) e portanto θ∗ = − x1

d1= 2

3 .

O novo ponto obtivo e y = x + 23d = (0, 4

3 , 23 , 0).

Observe que as novas colunas associadas as variaveis basicas (x2, x3)sao l.i..


A nova base

A nova base B e dada por:

B = [AB(1), . . . ,AB(l−1),AB(j),AB(l+1), . . . ,AB(m)]

Equivalentemente, o novo conjunto de variaveis basicas e

{B(1), . . . ,B(l − 1),B(j),B(l + 1), . . . ,B(m)}

Mais formalmente:

Teorema1 As colunas AB(i) : i 6= l e Aj sao linearmente independentes e, assim,

B e uma matriz basica.

2 O vetor y = x + θ∗d e a solucao basica associada a B.


Prova

Prova

(1): por contradicao:

Vamos supor que os vetores AB(i) sejam l.d. Entao, existem

coeficientes λ1, . . . , λm, nao todos nulos, tais que∑m

i=1 λiAB(i) = 0.

Multiplicando por B−1 temos∑m

i=1 λiB−1AB(i) = 0 e os vetores

B−1AB(i) tambem sao l.d. Vamos mostrar que este nao e o caso.

Observe que B−1B = I . Logo B−1AB(i) = ei , i 6= l (ei denota o vetorde zeros, exceto na i esima entrada, que e 1). Todos os vetoresB−1AB(i) possuem um 0 na l−esima entrada. Logo, B−1AB(i), i 6= lsao l.i..

Por outro lado B−1AB(l) = B−1Aj = −dB .

Por definicao, dB(l) < 0. Logo B−1Aj e B−1AB(i), i 6= l sao l.i..

Logo, B e uma base.


Prova

Prova

(2):

Temos que y ≥ 0,Ay = b.

Alem disto yi = 0,∀i 6∈ {B(i), . . . ,B(i)}.

Acabamos de mostrar que AB(i), . . . ,AB(i) sao l.i..

Portanto, segue que y e uma solucao basica associada a B


Observacoes

Uma vez que θ∗ > 0, segue que y e uma solucao basica distinta de x ,uma vez que d e uma direcao de reducao de custos e entao c ′y < c ′x .

Em parte, cumprimos nosso proposito inicial de mover para umasolucao basica adjacente, de menor custo.

Vamos enunciar uma iteracao tıpica do Metodo Simplex, definindoum vetor u = (u1, . . . , um), de forma que u = −dB = B−1Aj , onde Aj

e a coluna que entra na base. Ou seja, ui = −dB(i) : i = 1, . . . ,m.


Metodo Simplex: Iteracao Tıpica

1 Inicie a iteracao com as colunas basicas B(1), . . . ,B(m) e a solucaobasica viavel associada x . Seja N o conjunto dos ındices das variaveisnao basicas.

2 Calcule os custos reduzidos c j = cj − c ′BB−1Aj ,∀j ∈ N. Se c ≥ 0,pare, a solucao x e otima. Caso contrario, escolha j ∈ N : c j < 0.

3 Calcule u = B−1Aj . Se u ≤ 0, temos que θ∗ = ∞ e o custo otimo e−∞. Pare, o problema e ilimitado.

4 Se alguma componente de u e positiva, faca θ∗ = mini∈1,...,m:ui>0xB(i)

ui.

Seja l tal que θ∗ =xB(l)

ul.

5 Forme uma nova base substituindo AB(l) por Aj . Denote por y a novasolucao basica viavel. Entao yj = θ∗ e yB(i) = xB(i) − θ∗ui , i 6 l .


Na ausencia de degeneracao, O Metodo Simplex converge

Teorema

Assuma que o conjunto de solucoes viaveis do PL e nao vazio e que todasolucao basica e nao degenerada. Entao, o Metodo Simplex termina aposum numero finito de iteracoes. Ao final, temos duas possibilidades:

1 Dispomos de uma base otima B e a correspondente solucao basicaotima.

2 Encontramos um vetor d : Ad = 0, d ≥ 0 e c ′d < 0. Portanto o custootimo e −∞.


Prova

Prova

Se o algoritmo termina no passo 2, as condicoes de otimalidadepropostas previamente foram satisfeitas e B e uma base otima.

Se o algoritmo termina no passo 3, estamos em uma solucao basica xe descobrimos uma variavel nao basica xj tal que c j < 0. A j−esimadirecao basica j satisfaz Ad = 0, d ≥ 0. Em particular temos quex + θd ∈ P para θ tao grande quanto queiramos. Uma vez quec ′d = c j , o custo pode ser feito tao negativo quanto queiramos.

Em cada iteracao do algoritmo, nos movemos uma quantidade θ∗ > 0ao longo de uma direcao basica d satisfazendo c ′d < 0. Assim sendo,a cada iteracao o custo diminui e portanto nao visitamos a mesmasolucao basica mais de uma vez.

Como o numero de solucoes basicas e finito, o algoritmo entaotermina.


Metodo Simplex para problemas degenerados

Vamos considerar a partir de agora, como se comporta o algoritmodescrito anteriormente, diante da degeneracao:

1 Se a solucao basica corrente x for degenerada, θ∗ pode ser nulo, casoxB(l) = 0 e dB(l) < 0. Por este motivo, a nova solucao obtida y e

identica a x . Ainda assim, podemos definir uma nova matriz B com aentrada da coluna Aj e a saıda de AB(l) de forma que B sera umabase.

2 Mesmo se θ∗ > 0, pode acontecer de mais de uma variavel basica setornar zero no novo ponto x + θ∗d . Uma vez que apenas uma destasvariaveis basicas que se tornou nula saira da base para a entrada dacoluna Aj , a nova solucao encontrada y = x + θ∗d sera degenerada.


Efeito da degeneracao

As mudancas de base associadas a mesma solucao basica podem, emalguns casos, nao ser inuteis, levando a descobrir uma direcao basicade reducao de custo.

Por outro lado, uma sequencia de mudancas de base associadas aomesmo ponto x pode levar a repeticao das colunas associadas arepresentacao da base, ocasionando a ciclagem.

Para problemas altamente estruturados (fluxo em redes, etc) apossibilidade nao e remota.

A ciclagem pode ser evitada atraves do uso de regras adequadas dequais variaveis entrarao e/ou sairao da base.


Ilustracao dos dois casos em uma solucao degenerada

Neste exemplo temos n − m = 2. Vale observar a solucao degenerada x .


O Metodo Simplex pode nao terminar ?

Quadro 1, B = {5, 6, 7}, entra x1, sai x5

x5 = − 0.5x1 + 5.5x2 + 2.5x3 − 9x4

x6 = − 0.5x1 + 1.5x2 + 0.5x3 − x4

x7 = 1 − x1

z = + 10x1 − 57x2 − 9x3 − 24x4


x1 = + 11x2 + 5x3 − 18x4 − 2x5

x6 = − 4x2 − 2x3 + 8x4 + x5

x7 = 1 − 11x2 − 5x3 + 18x4 + 2x5

z = + 53x2 + 41x3 − 204x4 − 20x5




x2 = − 0.5x3 + 2x4 + 0.25x5 − 0.25x6

x1 = − 0.5x3 + 4x4 + 0.75x5 − 2.75x6

x7 = 1 + 0.5x3 − 4x4 − 0.75x5 − 13.25x6

z = + 14.5x3 − 98x4 − 6.75x5 − 13.25x6


x3 = + 8x4 + 1.5x5 − 5.5x6 − 2x1

x2 = − 2x4 − 0.5x5 + 2.5x6 + x1

x7 = 1 − x1

z = + 18x4 + 15x5 − 93x6 − 29x1




x4 = − 0.25x5 + 1.25x6 + 0.5x1 − 0.5x2

x3 = − 0.5x5 + 4.5x6 + 2x1 − 4x2

x7 = 1 − x1

z = + 10.5x5 − 70.5x6 − 20x1 − 9x2


x5 = + 9x6 + 4x1 − 8x2 − 2x3

x4 = − x6 − 0.5x1 + 1.5x2 + 0.5x3

x7 = 1 − x1

z = + 24x6 + 22x1 − 93x2 − 21x3


O Metodo Simplex pode nao terminar ? Sim, caso cicle.

O proximo quadro e igual ao quadro inicial !


x6 = − 0.5x1 + 1.5x2 + 0.5x3 − x4

x5 = − 0.5x1 + 5.5x2 + 2.5x3 − 9x4

x7 = 1 − x1

z = + 10x1 − 57x2 − 9x3 − 24x4


Possibilidades para implementar o pivoteamento

Ate o momento, nao particularizamos regra alguma para escolher asregras de pivoteamento, isto e, escolher qual variavel entra e sai dabase. Em particular, na descricao que apresentamos do Metodo Simplex,temos flexibilidade quanto a escolha de:

1 Qual coluna nao basica com custo reduzido e negativo deve ser eleitapara entrar na base;

2 Diante de mais de uma variavel que definam θ∗, qual escolher paradeixar a base.


Algumas provaveis candidatas a regras de pivotemento :

Escolher para entrar na base, a coluna nao basica Aj que possui ocusto reduzido c j mais negativo.

Escoher para entrar na base, a coluna nao basica Aj que promova omaior reducao na funcao objetivo, isto e θ∗c j . Esta regra podeacelerar a queda da funcao objetivo, mais paga-se maior precocomputacional, para se avaliar o θ∗ associado a entrada de cadacoluna que possua c j . A experiencia computacional existe sugere queo tempo global de cpu nao decresce com a adocao desta estrategia.

Mesmo a primeira estrategia acima pode ser muito cara paraproblemas de larga escala (requer que todas as colunas tenham seuscustos reduzidos avaliados). Assim sendo, uma regra simples consistena regra de escolher a coluna com custo reduzido negativo, de menorındice.


Implementacoes do Simplex

Os vetores B−1Aj sao de fundamental importancia no algoritmo, umavez que com estas informacoes podemos obter:

◮ Custos reduzidos c j = cj − c ′

BB−1Aj

◮ A direcao de busca d◮ O valor de θ∗

Por este motivo, a diferenca entre as implementacoes alternativas doMetodo Simplex residem em como esta informacao e calculada equais informacoes sao preservadas de iteracao para iteracao.

Dado que B e uma matriz m × m temos:◮ Custo de resolver Bx = b: O(m3)◮ Custo de efetuar a mutiplicacao Bb: O(m2)◮ Custo de calcular o produto interno de dois vetores m dimensionais:

O(m).


Implmentacao Inocente

1 Nenhuma informacao adicional sera transportada de iteracao paraiteracao no metodo.

2 Em cada iteracao tıpica, conhecemos os ındices B(1), . . . ,B(m) dasvariaveis basicas.

3 Montamos a matriz B e resolvemos o sistema linear p′B = c ′B .

4 O custo reduzido para qualquer coluna j e obtido via c j = cj − p′Aj .

5 Dependendo da regra de pivoteamento adotado, podemos evitarcalcular todos os custos reduzidos.

6 Uma vez que escolhemos a coluna Aj para entrar na base, resolvemosBu = Aj (ou u = B−1Aj).

7 A partir de entao, podemos calcular θ∗ e definir qual variavel saira dabase.


Implementacao inocente - complexidade computacional

Resolver os sistemas lineares (p′B = c ′B e u = B−1Aj): O(m3).Dependendo da estrutura da matriz B , este custo pode ser reduzidosensivelmente (exemplo: Problemas de Fluxo em Redes)

Calculo do custo reduzido para todas as colunas: O(mn)

Custo total por iteracao: O(nm + m3).

Veremos como fazer a iteracao a um custo de O(m2 + mn)


Simplex Revisado

Boa parte do custo computacional por iteracao e relacionado aresolucao de dois sistemas lineares.

Neste metodo, a matriz B−1 e explicitamente mantida em cadaiteracao e os vetores c ′BB−1 e B−1Aj sa determinados viamultiplicacao matricial.

Para ser eficiente, o metodo requer um esquema eficiente deatualizacao de B−1 quando implementarmos uma operacao depivoteamento.


Simplex Revisado

Base no inıcio da iteracao: B = [AB(1), . . . ,AB(m)]

Base ao fim da iteracao:B = [AB(1), . . . ,AB(l−1),AB(j),AB(l+1), . . . ,AB(m)]

Todas, exceto uma coluna de B e B sao compartilhadas.

Em funcao disto, e razoavel esperar que B−1 contenha informacao

que possa ser usada na determinacao de B−1

.


Como aproveitar informacoes de B−1 para avaliar B−1

Definicao

Dada uma matriz, nao necessariamente quadrada, a operacao de adicionarum multiplo de uma linha a mesma linha ou a outra linha da matriz echamada de operacao linha elementar (nao muda as informacoes dossistemas lineares representados pela matriz).

Exemplo

Digamos que queiramos multiplicar a terceira linha da matriz C abaixo por2 para somar a primeira linha da matriz. Isto equivale a multiplicar C pelamatriz Q dada abaixo.

C =

1 23 45 6

Q =

1 0 20 1 00 0 1

QC =

11 143 45 6


Generalizando este exemplo

Multiplicar a j−esima linha de uma matriz por β e adicionar esteproduto a i−esima linha da matriz, equivale a pre mutiplicar a matrizpor Q = I + Dij , onde Dij e uma matriz de zeros, exceto em suaentrada na i−esima linha e j−esima coluna que e β.

Observe que a matriz Q possui determinante 1 e entao admite inversa.

Suponha que queiramos fazer uma sequencia de K operacoes linhaelementares, cada qual correspondento a pre-multiplicacao por umamatriz Qk correspondente. Esta sequencia de operacoes consiste empre multiplicar a matriz sobre a qual sao feitas as operacoes por:QKQK−1 . . . Q2Q1.


Aplicando esta ideia no Metodo Simplex

Uma vez que B−1B = I , temos que B−1AB(i) = ei , onde ei e umvetor de zeros exceto pela i−esima entrada que e 1.

Usando esta observacao temos B−1B =

1 u1

. . ....ul...

. . .

um 1

Para transformar a matriz acima na identidade:◮ Para cada i 6= l , adicionamos o produto da l− esima linha (linha pivot)

por −ui

ule somamos a i− esima linha. Observe que ul 6= 0 e entao esta

operacao substitui ui por 0 na correspondente i−esima linha.◮ Dividimos a l− esima linha por ul .

Seja Q o produto destas m operacoes linha elementares. Temos entao

que QB−1B = I , logo B−1

= QB−1.


Exemplo

Vamos considerar l = 3 (a terceira coluna de B sera alterada paracompor B) e

B−1 =

1 2 3−2 3 14 −3 −2

u =

−422

Entao temos: Q =

1 0 20 1 −1

0 0 12

B−1

=

9 −4 −1−6 6 3

2 −1.5 −1


Metodo Simplex Revisado

Vamos adicionar o seguinte passo ao final da quinta operacao na iteracaotıpica:

Forme a matriz m × (m + 1) dada por: [B−1 | u].Faca as operacoes linha elementares necessarias para transformar aultima coluna desta matriz no vetor unitario el .

As primeiras m colunas da matriz resultante fornece B−1

.

Observe que recalcular a inversa da base agora custa O(m2). Desta forma,apenas na primeira inversao da base, pagamos o O(m3). Desta forma,reduzimos o custo de cada iteracao para O(nm + m2)


Regras anti-ciclagem

Regra lexicografica, adequada a implementacao da versao Full tableimplementation que, por ter o comportamento assintotico pior que aversao do Simplex Revisado, nao sera discutida.

Regra de Bland - compatıvel com a implementacao do SimplexRevisado.


Regra de Bland

Pivoteamento de Bland1 Encontre o menor ındice j para o qual o custo reduzido c j e negativo.

2 Dentre as variaveis basicas xi que se anularem primeiro com oincremento da variavel xj (para as quais houver empate nadeterminacao de θ∗), escolha aquela com o menor ındice i .

Observacoes:

Esta regra nao nos obriga a calcular todos os custos reduzidos.

E compatvel com a implementacao do Simplex Revisado, na qual oscustos reduzidos sao calculados na ordem natural das variaveis.

Diante desta regra e provado que nao pode haver ciclagem e oMetodo Simplex converge apos um numerol finito de mudancas debase.


Encontrando uma base inicial viavel

No Metodo Simplex, assumimos dispor de uma solucao basica viavelinicial. Nao descrevemos ainda como obter esta solucao.

Em alguns casos, encontrar esta solucao e trivial. Exemplo:P ′ = {x ∈ R

n+ : Ax ≤ b} e o vetor b ≥ 0. Neste caso, introduzindo as

variaveis de folga temos P = {(x , s) ∈ (Rn+, Rm

+) : Ax + Is = b} e ovetor (x , s) = (0, b) e uma solucao basica viavel.

De um modo geral, encontrar esta solucao nao e tao trivial,requerendo a solucao de um problema linear auxiliar (Fase 1).


Construcao de um problema auxiliar

Problema Original

min c ′x

Ax = b

x ≥ 0

Assumimos sem perda de generalidade que b ≥ 0 (caso contrario,multiplicamos alguma linha do sistema linear por −1)


Construcao de um problema auxiliar - Fase 1

Problema Auxiliar (PA)

minm

∑

i=1

yi

Ax + y = b

x ≥ 0

y ≥ 0

Introduzimos as variaveis artificiais y ∈ Rm+.

Uma solucao basica inicial para o Prob. Auxiliar e dada por(x , y) = (0, b).

Resolvemos PA. Se a funcao objetivo otima for 0 sabemos que hasolucao viavel para o problem original. Caso contrario, o problemaoriginal e inviavel.

Como obter a solucao basica inicial para o problema original ?


Obtendo uma solucao viavel inicial a partir de PA

Para iniciar o Metodo Simplex, necessitamos de uma solucao basica iniciale a matriz basica associada. Vamos assumir que no otimo de PA tenhamos∑m

j=1 yj = 0 (prob. original e viavel).

Analisando a solucao do PA:

1 Se ao final da resolucao de PA as colunas basicas na solucao otimaforem exclusivamente as variaveis x , basta tomarmos esta solucaocomo uma sol. basica viavel inicial (e as correspondentes colunascompondo a base) para iniciar o problema original.

2 Se existirem variaveis yj basicas (necessariamente degeneradas) nasolucao otima de PA, devemos fazer operacoes de pivoteamentoforcado para remove-las da base.


Eliminando as variaveis y para fora da base

Vamos supor (como de costume) que posto(A) = m.

Vamos assumir que k < m colunas de A aparecem na base otima dePA. Os ındices das variaveis basicas associadas a estas colunas saoB1, . . . ,Bk

Vale observar que as colunas AB(1), . . . ,AB(k) sao linearmenteindependentes, uma vez que estao na base.

Como a matriz A ∈ Rm×n possui posto m, suas colunas geram o

espaco Rm. Logo, e possıvel escolher outras m − k colunas de A, que

sejam linearmente independentes a AB(1), . . . ,AB(k).

Vamos identificar estas colunas, eliminando as colunas associadas a yda base.


Eliminando as variaveis artificiais

Vamos supor que a l−esima (l > k) variavel basica seja artificial.Dentre as variaveis xj : j 6∈ {B(1), . . . ,B(m)}, procuramos umacoluna j tal que B−1Aj 6= 0.

Claramente Aj e l.i. com AB(1), . . . ,AB(k) (por que ?)

Entao fazemos um pivoteamento forcado, no qual trazemos a colunaAj para a base e eliminados a coluna da variavel artificial da base.

Repetimos o processo enquanto houver colunas basicas associadas avariaveis artificiais.


Complexidade computacional do metodo simplex

A complexidade do metodo Simplex depende:

1 da complexidade computacional em cada iteracao (O(nm), porexemplo, no caso do Simplex Revisado)

2 do numero de iteracoes, ou operacoes de pivoteamento.

Na pratica: ao longo dos anos observou-se que o metodonormalmente executa O(m) operacoes de pivoteamento na media.

Pior caso: esta observacao que ocorre na pratica nao e verdadeirapara qualquer Programa Linear e qualquer regra de pivoteamento. Haexemplos de problemas nao degenerados nos quais o metodo percorretodos os vertices do poliedro ate encontrar a solucao otima.


Complexidade no pior caso

Vamos considerar o problema de minimizar −xn sobre o cuboP = {x ∈ R

n : 0 ≤ xi ≤ 1, i = 1 dots, n}. Estes cubo possui 2n

vertices, metade dos quais possuem custo 0 e a outra metade custo−1. Assim sendo, a funcao objetivo nao pode decrescermonotonicamente ao longo das iteracoes do Simplex.

Por este motivo, vamos perturbar o cubo, mantendo o numero devertices, impondo as seguintes restricoes, para ǫ ∈ (0, 1

2)

ǫ ≤ x1 ≤ 1,

ǫxi−1 ≤ xi ≤ 1 − xi−1, i = 2, . . . , n

de forma a criar uma sequencia de vertices adjacentes para os quais afuncao objetivo seja reduzida quando nos movemos de um vertice para ooutro.


Criamos um caminho que percorre todos os vertices

Existe uma regra de pivoteamento que faz o metodo percorrer todos osvertices (ver a prova em Papadimitrou e Steiglitz, pp. 166-170).

min −xn

ǫ ≤ x1 ≤ 1,

ǫxi−1 ≤ xi ≤ 1 − xi−1, i = 2, . . . , n


Existe regra de pivoteamento imune a esta patologia ?

Questao em aberto

Para varias regras populares de pivotemento, ha exemplos como oindicado anteriormente, que fazem o metodo percorrer todos osvertices.

Entretanto, estes exemplos nao excluem a possibilidade de existir umaregra de pivotemento que nao apresente o comportamento de piorcaso exponencial.

Esta e uma das questoes mais importantes em Teoria de ProgramacaoLinear, ainda em aberto.

O fato e que nao se conhece uma regra de pivoteamento imune a estapatologia.

O Problema de Programacao Linear e polinomialmente soluvel(Algoritmo do Elipsoide).


Documents

[Robson] 3. Método Simplex