Método Simplex

Método Simplex

(Parte 1 de 2)

O Método Simplex

Cid C. de Souza cid@ic.unicamp.br

Instituto de Computacao – UNICAMP

Cid de Souza – Metodo Simplex– p.1/63

Definições e Resultados Básicos

S ⊆ R é convexo se e somente se todo ponto x que é uma combinação linear convexa de um par de pontos qualquer (x1,x2) de S também pertencer a S.

CONVEXONÃO CONVEXO Proposição: S = {x ∈ Rn : Ax ≤ b,x ≥ 0} é convexo.

Definições e Resultados Básicos

Definição (geométrica):

x é um ponto extremo de S se e somente se não existem pontos distintos x1 e x2 de S tal que αx1 + (1 − α)x2 = x com 0 < α < 1.

Definição (algébrica):

Seja S = {x ∈ Rn : Ax ≤ b,x ≥ 0} x não vazio, A : m × n, m ≤ n e ρ(A) = m. Se x é ponto extremo de S então x satisfaz n desigualdades linearmente independentes de S na igualdade.

Cid de Souza – Metodo Simplex– p.3/63

Definições e Resultados Básicos

(algébrica =⇒ geométrica) Seja Gx ≤ g o subsistema linear de S com n desigualdades LI satisfeitas na igualdade, ou seja,

Uma vez que G é inversível, isso obriga que x = x1 = x2. Logo, x deve ser extremo.

Definições e Resultados Básicos

(geométrica =⇒ algébrica) Supor que x satisfaz a apenas r < n desigualdades de S na igualdade. Sejam estas r desigualdades dadas por:

Afirmação: Existe d 6= 0 tal que Gd = 0 (as colunas de G são LD)

Portanto, existe um escalar ǫ > 0 tal que (x − ǫd) e (x + ǫd) estão ambos em S.

Cid de Souza – Metodo Simplex– p.5/63 Representação de Poliedros

Teorema de Caratheodory:

O poliedro não vazio S = {x ∈ Rn : Ax ≤ b,x ≥ 0} também pode ser representado na seguinte forma:

onde {x1,...,xp} são os pontos extremos de S e {d1,...,dq} são os raios extremos de S.

Representação de Poliedros x1 x2 x3d1 d2 x3 x4

Cid de Souza – Metodo Simplex– p.7/63 Soluções básicas

Se y ∈ S então y é uma solução viável.

i = m + 1,...,n e a matriz B = [A•1 A•2A•m] é

Então, x é uma solução básica se xi = 0 para todo inversível.

(assume-se que as colunas de A e as componentes de x tenham sido rearranjadas apropriadamente).

Soluções básicas

xB xN onde xB são as variáveis básicas e xN são as variáveis não básicas.

Cid de Souza – Metodo Simplex– p.9/63 Soluções básicas (exemplos)

x1=0

x2=0 x4=0 x3=0

Soluções básicas (exemplos)

é inversível.

é inversível.

Cid de Souza – Metodo Simplex– p.1/63 Soluções básicas (exemplos)

é inversível.

Solução inviável !

não é inversível.

Número de soluções básicas: n! m!(n−m)! (exponencial !)

Soluções Básicas e Pontos Extremos

Teorema: Seja S = {x ∈ Rn : Ax = b,x ≥ 0}. Então, x é um ponto extremo de S se e somente se x é uma solução básica viável.

(básica =⇒ extremo) Seja x uma solução básica e assuma por contradição que x = αy + (1 − α)z, y,z ∈ S − {x} e α ∈ (0,1).

Cid de Souza – Metodo Simplex– p.13/63

Soluções Básicas e Pontos Extremos

Além disso,

Conclui-se que x não pode ser escrita como combinação convexa estrita de dois pontos distintos de S. Logo, x é ponto extremo.

Soluções Básicas e Pontos Extremos

(extremo =⇒ básica) Como x é extremo, existem n restrições LI em S que são satisfeitas na igualdade. Logo existem n − m equações da

Assim, tem-se o sistema linear da forma Ax = b,xN = 0 que é satisfeito por x que, na forma matricial, é dado por:

Este sistema tem solução única pois as linhas de A são LI. Logo det(B) = det(A) e, portanto, B é inversível e a solução do sistema acima é básica.

Cid de Souza – Metodo Simplex– p.15/63

Pontos extremos e otimalidade

Teorema: S = {x ∈ Rn : Ax ≤ b,x ≥ 0} tem solução viável se e somente se S tem um ponto extremo.

Teorema: Seja S = {x ∈ Rn : Ax = b,x ≥ 0}. Considere o problema dado por z = min{cx : x ∈ S}. Se z tem valor finito então existe um ponto extremo ótimo. Além disso, se existir mais de um ponto extremo ótimo, toda combinação convexa destes pontos será uma solução ótima também.

Prova: Teorema de Caratheodory. .

Idéia do algoritmo Simplex

Encontrar um ponto extremo ( ≡ solução básica).

Sair do ponto extremo corrente e ir para um ponto extremo vizinho onde o valor da função objetivo é melhor.

Repetir o passo anterior enquanto for possível. Retornar o ponto extremo corrente (solução ótima !)

Solução básica:

Cid de Souza – Metodo Simplex– p.17/63

Algoritmo do Simplex Escrever a função objetivo e as variáveis básicas em função das variáveis não básicas:

Reescrevendo o PL: (custos reduzidos)

Simplex: exemplo

Cid de Souza – Metodo Simplex– p.19/63

Simplex: exemplo y1=0 x1=0

x2=0 y3=0

Simplex: exemplo

Primeira iteração: x1 = x2 = 0 variáveis básicas: y1,y2 e y3:

x2 entra na base e y2 sai da base

Segunda iteração: x1 = 0,x2 = 2 variáveis básicas: y1,x2 e y3:

x1 entra na base e y1 sai da base

Cid de Souza – Metodo Simplex– p.21/63 Simplex: exemplo

variáveis básicas: x1,x2 e y3:

Simplex: tableau

Segunda iteração:

Terceira iteração: tableau ótimo !

Pivoteamento, operações elementares e a inversa da base.

Cid de Souza – Metodo Simplex– p.23/63

Simplex: caso ilimitado

(0,3) s3=0 s4=0 s2=0 x1=0 x2=0 (1,0)

Simplex: caso ilimitado (cont.) penúltima iteração: vértice degenerado (1,0) última iteração: vértice degenerado (0,3) problema ilimitado ! direção extrema: d = 2 4 1

Cid de Souza – Metodo Simplex– p.25/63

Dualidade

Primal:

Dual:

Exemplo:

Dualidade (cont.)

Existe uma variável dual para cada restrição do primal e vice-versa.

Proposição: O dual do dual é o primal

Cid de Souza – Metodo Simplex– p.27/63

Dualidade (cont.)

Proposição: (Dualidade Fraca) Se x é uma solução primal viável e u é uma solução dual viável então cx ≤ z∗ ≤ w∗ ≤ ub.

Relação entre os valores ótimos primal e dual:

1. se z∗ → ∞ (P ilimitado) então D é inviável.

2. se w∗ → −∞ (D ilimitado) então P é inviável.

3. se P e D são ambos limitados então z∗ = w∗ (Dualidade Forte) .

4. P e D são ambos inviáveis.

Relações entre o primal e o dual

Primal: Ilimitado

Dual: Inviável

Cid de Souza – Metodo Simplex– p.29/63 Relações entre o primal e o dual

Primal: Inviável

Dual: Ilimitado

Relações entre o primal e o dual

Primal: Limitado

Dual: Limitado

Cid de Souza – Metodo Simplex– p.31/63

Relações entre o primal e o dual

Primal: Inviável

Dual: Inviável

Complementaridade de Folgas

Teorema das Folgas Complementares: (x∗,s∗) é uma solução ótima de P e (u∗,t∗) uma solução ótima de D se e somente se, para todo

Pela dualidade forte, conclui-se que: u∗s∗ + t∗x∗ = 0. Como x∗,s∗,u∗,t∗ ≥ 0 o resultado fica mostrado.

Cid de Souza – Metodo Simplex– p.3/63

Complementaridade de Folgas (cont.)

Prova: (⇐) Como (x∗,s∗) e (u∗,t∗) são viáveis para P e D respectivamente, tem-se:

ou ainda

Pela dualidade fraca, (x∗,s∗) deve ser uma solução ótima de P e (u∗,t∗) deve ser uma solução ótima de D.

Bases duais viáveis

s.a uA ≥ c

Solução básica primal: Ax = BxB + NxN = b

Definir: u = cBB−1 e t = uA − c (folgas duais).

Proposição: u é complementar a x = 2 4 xB

Cid de Souza – Metodo Simplex– p.35/63

Bases duais viáveis

Definição: Se cBB−1N ≥ cN então B é uma base dual viável.

Nota 1: cBB−1N ≥ cN ≡ custos reduzidos negativos.

Nota 2: Uma base pode ser só primal viável, só dual viável, nem primal e nem dual viável ou simultaneamente primal e dual viável.

Proposição: Se B é uma base primal e dual viável então

(xB | xN) = (B−1b | 0) é ótima para P e u = cBB−1 é ótima para D.

Primal-Simplex formalizado

Movendo de uma base para outra: aumenta uma variável não básica mantendo-se as outras em zero.

1. Se para todo i = 1,...,m, (yr)i ≤ 0, xr cresce indefinidamente e a base não muda.

Cid de Souza – Metodo Simplex– p.37/63 Primal-Simplex (cont.) xr entra na base com valor bs (yr)s e (xB)s sai da base.

Definição: uma soluçao primal viável é degenerada se xB = b e bi = 0 para algum i = 1,...,m.

Observação: se não existir nenhuma base degenerada então, definida uma variável não-básica para entrar na base, só haverá uma variável básica candidata a sair da base.

Primal-Simplex (cont.)

Corolário: Seja B uma base não degenerada primal viável mas dual inviável, i.e., existe xr não básica com custo reduzido cr = cr − cBB−1a•r = cr − cByr > 0.

1. Se yr ≤ 0 então z∗ → ∞ (primal ilimitado).

2. Se ∃s tal que (yr)s > 0 então é possível mover para uma única base B(r) de melhor custo.

Prova:

Cid de Souza – Metodo Simplex– p.39/63

Primal Simplex: Fase 2

Passo 1: encontrar base primal viável B ( FASE 1 ).

Passo 2: se (cN − cBB−1N) ≤ 0, PARE ! Retorne a solução ótima xB = B−1b,xN = 0. Se não (pricing) escolher r tal que cr = cr − cBB−1a•r > 0. Se yr = B−1a•r ≤ 0, PARE ! Retorne “problema ilimitado”.

Se não, escolher s tal que (yr)s > 0 e bs (yr)s

= min

(⋆ s sai da base e r entra na base ⋆)

Executar troca de base (pivoteamento): B ← B r {B•s} ∪ {a•r}. Voltar ao Passo 1.

Proposição: Não havendo soluções básicas degeneradas, o algoritmo primal simplex temina em um número finito de passos.

Primal Simplex: Fase 1

(xa: variáveis artificiais)

Observações:

Pa é viável pois tem solução básica dada por xa = b e x = 0. Pode ser resolvido pela Fase 2 !

Pa é limitado (za ≤ 0), portanto tem solução ótima em um vértice.

(x,xa) é viável para Pa e x viável para P se e somente se xa = 0. Se za < 0, Pa não tem solução viável com xa = 0 e P é inviável.

Cid de Souza – Metodo Simplex– p.41/63

Primal Simplex: Fase 1 (cont.)

Observações:

Se za = 0, toda solução ótima (x,xa) de Pa satisfaz xa = 0 com x viável para P.

No caso anterior, se todas as variáveis artificiais são não básicas, a base ótima de Pa é uma base viável para P. Pode-se remover as variáveis artificiais do problema !

Mas, é possível que algumas variáveis artificiais fiquem na base com o valor zero (base degenerada). Neste caso, se elas não forem removidas por pivoteamento, existem restrições redundantes no sistema Ax = b.

Algoritmo Dual Simplex

Comparativo entre os algoritmos Primal e Dual Simplex:

Primal Simplex: visita bases primais viáveis até que a base corrente se torne dual viável (custos reduzidos ≤ 0).

Dual Simplex: visita bases duais viáveis até que a base corrente se torne primal viável (variáveis básicas ≥ 0).

Proposição: Se B uma base dual viável e bs < 0 para algum s, então

1. Se (ys)j ≥ 0 para todo j ∈ N (não básica) então o problema é primal inviável.

2. Se não, existe uma base dual viável B(r) adjacente à base B corrente dada por B(r) = B ∪ {a•r} r {B•s} satisfazendo r ∈ N, (ys)r < 0 e

r = argmin j∈N

Cid de Souza – Metodo Simplex– p.43/63

Algoritmo Dual Simplex (cont.)

Prova:

Se (ys)j ≥ 0 para todo j ∈ N, toda solução com xj ≥ 0 para todo j ∈ N

2. Se xr entra na base e (xB)s sai, então

A base B(r) é dual viável pois: λ ≥ 0 (custo reduzido de (xB)s), cj − λ(ys)j ≤ cj ≤ 0 para todo j tal que (yj)s ≥ 0 e, pela escolha de r, cj − λ(ys)j ≤ 0 para todo j satisfazendo (ys)j < 0.

Algoritmo Dual Simplex

Passo 1: encontrar base dual viável B ( FASE 1 ).

Retorne a solução ótima (primal) xB = B−1b,xN = 0. Se não (pricing) escolher s tal que (xB)s < 0.

Se (ys)j ≥ 0 para todo j ∈ N, PARE ! Retorne “problema inviável”.

Se não, escolher r tal que r = argmin j∈N

(⋆ s sai da base e r entra na base ⋆)

Executar troca de base (pivoteamento): B ← Br{B•s}∪{a•r}. Voltar ao Passo 1.

Cid de Souza – Metodo Simplex– p.45/63 Dual Simplex: (cont.)

Observações:

A função objetivo do problema primal é monotonamente decrescente ao contrário do primal simplex.

O valor do decréscimo ao mudar a base é de ∣∣∣ crbs (ys)r ∣∣∣.

Não havendo degenerescência no problema dual, cr < 0 e o decréscimo é estrito.

Logo o algoritmo termina em tempo finito !

Dual Simplex: exemplo

Cid de Souza – Metodo Simplex– p.47/63 Dual Simplex: exemplo (cont.)

Tableau e variáveis duais

Se existirem colunas na matriz original A que formam uma matriz identidade e que correspondam a variáveis de folga (custos nulos), no tableau ótimo teremos nestas colunas que:

ou seja, na linha correspondente à função objetivo e nas colunas correspondentes à identidade teremos as variáveis duais ótimas.

Cid de Souza – Metodo Simplex– p.49/63

Primal ou Dual Simplex ? se cj ≤ 0 para todo j ∈ N e bi ≥ 0 para todo i ∈ B então a solução é ótima. Nada há a fazer ! se cj ≤ 0 para todo j ∈ N e ∃i ∈ B tal que bi < 0 então Primal Simplex tem Fase 1 mas o Dual Simplex passa direto à Fase 2 ! se ∃j ∈ N tal que cj > 0 e bi ≥ 0 para todo i ∈ B então Dual Simplex tem Fase 1 mas o Primal Simplex passa direto à Fase se ∃j ∈ N tal que cj > 0 e ∃i ∈ B tal que bi < 0 então Primal e Dual Simplex tem Fase 1.

Adição de nova restrição após otimização max z′ = cx s.a Ax = b

Cid de Souza – Metodo Simplex– p.51/63

Adição de nova restrição (cont.)

Usando a antiga base B podemos escrever xn+1 como função de xN:

Linha do novo tableau: xn+1 + (dN − dBB−1N)xN = d0 − dBb. Novo tableau: (xB,xN,xn+1 ≥ 0 e c′N = novos custos reduzidos)

Adição de nova restrição (cont.)

Proposição: A nova base B′ é dual viável. Prova:

custos reduzidos:

Cid de Souza – Metodo Simplex– p.53/63

Adição de nova restrição (cont.) Prova: (cont.)

Logo, cB′(B′)−1N′ = cBB−1N, ou seja, os custos reduzidos das variáveis não básicas permanecem inalterados !

Portanto, a nova base ainda é dual viável.

Conclusão: após adicionar uma nova restrição, deve-se dar preferência ao uso do algoritmo dual simplex !

Adição de nova restrição: exemplo

Folga da primeira restrição: y1.

Folga da segunda restrição: y2.

x2=0 x1=0

6 y1=0 y2=0

Cid de Souza – Metodo Simplex– p.5/63 Adição de nova restrição: exemplo

Tableau ótimo ! Inversa da base: B−1

Nova restrição:

x2=0 x1=0

6 y1=0 y2=0 2 y3=0

Adição de nova restrição: exemplo

Novo Tableau:

Escrever y3 em função das variáveis não-básicas.

Base não é primal viável mas é dual viável.

Usar o dual simplex !

Cid de Souza – Metodo Simplex– p.57/63 Adição de nova restrição: exemplo

Base é primal viável e é dual viável.

Tableau ótimo !

Simplex para variáveis limitadas

Definição: Uma partição das colunas de A tal que A = [B | N1 | N2] corresponde a uma solução básica [xB | xN1 | xN2

] se B é inversível,

A solução básica será viável se 0 ≤ B−1(b − N2hN2 ) ≤ hB.

Cid de Souza – Metodo Simplex– p.59/63

Simplex para variáveis limitadas (cont.)

Existem dois tipos de variáveis não básicas: as que estão no seu limite inferior (xN1 ) e as que estão no seu limite superior (xN2

Escrevendo a F.O. em função das variáveis não-básicas (VNB):

ou ainda

custos reduzidos das

VNB no limite superior custos reduzidos das

VNB no limite inferior

Simplex para variáveis limitadas (cont.)

Para uma solução básica temos as seguintes folgas:

Proposição: Seja B uma base e u = cBB−1. Se vB = 0, vN1 = 0 e

− cBB−1N2 então (u,v) é complementar a x, ou seja, xt = 0 e

Cid de Souza – Metodo Simplex– p.61/63

Simplex para variáveis limitadas (cont.)

Proposição: As variáveis duais u e v com os valores definidos tais como na proposição anterior formam uma solução dual viável se e somente se

Observação: (u,v) é dual viável se e somente se o custo reduzido das variáveis no limite inferior é ≤ 0 e o custo reduzido das variáveis no limite superior é ≥ 0.

Bases adjacentes:

2. B′ = B (a base não muda) mas |N′1 \ N1| + |N′2 \ N2| = 1, ou seja, alguma VNB passa do seu limite superior para o seu limite inferior ou vice-versa !

Simplex para variáveis limitadas (cont.)

Observações finais:

Os algoritmos primal e dual simplex necessitam de pequenas modificações para passarem a tratar o caso de variáveis limitadas.

A vantagem de usar esta versão modificada dos algoritmos é que pode-se tabalhar com uma base de dimensão menor (m×m em vez de (m+n)×(m+n) . Menos memória !

(Parte 1 de 2)

Comentários