PTC3420 - Programação Matemática

Aplicada a Controle

Método Simplex

PTC - EPUSP

Aula 10 - 2020
Agradecimento: Agradeço a Profa. Celma Ribeiro pelos arquivos latex do curso PRO-3341, usados

na preparação das aulas desse curso .

PTC-3420
Método Simplex - Forma Tableau
Sabemos como passar de um ponto extremo a outro. A questão é,
dada a função objetivo que se deseja minimizar, como determinar a
variável que deve entrar na base de forma a reduzir o valor da
função objetivo? Consideramos o problema de PL

min c0 x
s.a. Ax = b, x ≥ 0

Na representação canônica por tableau,

x1 x2 . . . xm xm+1 ... xn b
1 0 . . . 0 y1m+1 ... y1n δ1
0 1 . . . 0 y2m+1 ... y2n δ2
.. .. .. . .. .. .. ..
. . . .. . . . .
0 0 . . . 1 ymm+1 . . . ymn δm
 Método Simplex - Forma Tableau
O valor da função objetivo na base atual á dada por:

z0 = c1 δ1 + . . . + cm δm

e do tableau, as equações do sistema são, para i = 1, . . . , m,

n
X
xi = δ i − yij xj
j=m+1

PTC-3420
Método Simplex - Forma Tableau
Portanto o valor da função objetivo pode ser escrito como
n
X
z = c1 x1 + . . . + cm xm + cj xj
j=m+1
n
X n
X
= c1 (δ1 − y1j xj ) + . . . + cm (δm − ymj xj )
j=m+1 j=m+1
n
X
+ cj xj = z0 − rm+1 xm+1 − . . . − rn xn
j=m+1

onde para j = m + 1, . . . , n

m
X
rj = cj − zj , zj = ci yij
i=1
PTC-3420
Método Simplex - Forma Tableau
Portanto, temos que

z + rm+1 xm+1 + . . . + rn xn = z0

Temos as seguintes possibilidades (minimização):

1) rj ≤ 0 para todo j → solução atual é ótima.
1.a) rj < 0 para todo j → ótimo único
1.b) rj ≤ 0 para todo j mas com alguns rj = 0 → conjunto de
soluções ótimas é a combinação convexa dos pontos extremos
associados aos j tais que rj = 0.
 Método Simplex - Forma Tableau
2) rj > 0 para algum j → variável xq tal que rq = max{rj }
entra na base (vai reduzir a função objetivo)
2.a) Se yiq ≤ 0 para todo i = 1, . . . , m → solução ilimitada
2.b) Se yiq > 0 para algum i = 1, . . . , m → mudar de base, sai
variável xι tal que
xι xi
= min{ ; yiq > 0}
yιq yiq

(problema se der empate, teremos solução degenerada)

Observações:
A) Pegar o rq = max{rj } é apenas uma convenção, qualquer xj
tal que rj > 0 serviria no passo 2).
B) Para o problema de maximização inverter a desigualdade para
o rj , isto é,
1 No Passo 1), rj ≥ 0, e
2 No passo 2), rj < 0 para algum j.

PTC-3420
Método Simplex - Forma Tableau
Como obter rj diretamente do tableau? Introduzir a linha de
custos:

min z
s.a. z − c0 x = 0
Ax = b, x ≥ 0
Método Simplex - Forma Tableau
Pivotando (z sempre na base, mas não mostramos para simplificar
o tableau) obtemos

x1 x2 . . . xm xm+1 ... xn b
0 0 ... 0 rm+1 ... rn z0
1 0 . . . 0 y1m+1 ... y1n δ1
0 1 . . . 0 y2m+1 ... y2n δ2
.. .. .. . .. .. .. ..
. . . .. . . . .
0 0 . . . 1 ymm+1 . . . ymn δm
Algoritmo Simplex

Passo 1 Encontre uma solução básica inicial (um ponto

extremo inicial) e coloque o tableau na forma padrão
Passo 2 Se a solução é ótima (para todo j, minimização:
rj ≤ 0, maximização: rj ≥ 0 ), pare. Senão vá para o passo 3
Passo 3 Determine a variável não-básica que deve entrar na
base (minimização: rq > 0, maximização: rq < 0)
Passo 4 Determinar a variável básica que deve sair da base:
xι tal que
xι xi
= min{ ; yiq > 0}
yιq yiq
ou que o problema é ilimitado (yiq ≤ 0 para todo i). Nesse
caso, pare, problema ilimitado. Caso contrário, vá para Passo 5
Passo 5 Pivote o tableau e determine a nova solução básica
factível (ponto extremo adjacente), e vá para o Passo 2.
Exemplo
Vamos trabalhar com o problema

max z = 3x1 + 2x2

s.a x1 + x2 ≤7
x1 ≤4
x1 ≥ 0 x2 ≥ 0

1 Coloque o problema na forma padrão

2 Qual seria a melhor escolha para uma construir uma primeira matriz
básica? Lembre-se que vamos inverter matrizes
3 Quais são as correspondentes variáveis básicas? E as não básicas?
Quem são, no problema original, xB , xN , cB , cN .
4 Escreva as matrizes B e N (associadas às variáveis básicas e não
básicas) e B −1
5 Apresente o modelo na forma tabelau
 Exemplo 1

Vamos reescrever o problema na forma tableau

max z = 3x1 + 2x2 + 0s1 + 0s2

s.a x1 + x2 + s1 =7
x1 + s2 =4
x1 ≥ 0 x2 ≥ 0 s1 ≥ 0 s2 ≥ 0

Escolha para variáveis básicas, as variáveis de folga BV = {s1 , s2 }

PTC-3420
 Exemplo 1

Vamos reescrever o problema na forma tableau

max z = 3x1 + 2x2 + 0s1 + 0s2

s.a x1 + x2 + s1 =7
x1 + s2 =4
x1 ≥ 0 x2 ≥ 0 s1 ≥ 0 s2 ≥ 0

Escolha para variáveis básicas, as variáveis de folga BV = {s1 , s2 }

Seja
z = 3x1 + 2x2 + 0s1 + 0s2
Ou ainda,

z − 3x1 − 2x2 − 0s1 − 0s2 = 0

PTC-3420
 Exemplo 1

Variáveis básicas BV = {s1 , s2 } e as não básicas N = {x1 , x2 }

s1 = 7 e s2 = 4
x1 = 0 e x2 = 0
Valor da função nesse ponto extremo:

z =3×0+2×0+0×7+0×4=0

x1 x2 s1 s2
Linha 0 z −3 −2 0 0 =0
Linha 1 1 1 1 0 =7
Linha 2 1 0 0 1 =4

PTC-3420
 Exemplo
6 Qual o ponto extremo que está associado a essa variável? (dê
o vetor)
7 A base é ótima?
8 Reescreva o problema parametrizado em relação a essa
primeira base

PTC-3420
Exemplo 1

Variáveis básicas BV = {s1 , s2 } e as não básicas N = {x1 , x2 }

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 1 1 1 0 = 7 s1 = 7
Linha 2 1 0 0 1 = 4 s2 = 4
A solução básica é ótima?
Exemplo 1

Variáveis básicas BV = {s1 , s2 } e as não básicas N = {x1 , x2 }

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 1 1 1 0 = 7 s1 = 7
Linha 2 1 0 0 1 = 4 s2 = 4
A solução básica é ótima?

z = 3x1 + 2x2 + 0s1 + 0s2

Não! Vale a pena crescer x1 , pois o coeficiente associado a ela é
positivo (negativo, se você olhar o tableau)
Exemplo 1

Vou andar para um ponto extremo adjacente!

Alguma variável deve se anular!

Exemplo 1

Vou andar para um ponto extremo adjacente!

Alguma variável deve se anular!

Até onde é possível crescer x1 ?

Escrevendo na forma de um sistema...
Exemplo 1

Vou andar para um ponto extremo adjacente!

Alguma variável deve se anular!

Até onde é possível crescer x1 ?

Escrevendo na forma de um sistema...
z −3x1 −2x2 +0s1 +0s2 = 0
1x1 +1x2 +1s1 =7
1x1 +1s2 = 4 →
Exemplo 1

z −3x1 −2x2 +0s1 +0s2 = 0

1x1 +1x2 +1s1 =7
1x1 +1s2 = 4
Vamos escrever tudo em função das variáveis não básicas.
Exemplo 1

z −3x1 −2x2 +0s1 +0s2 = 0

1x1 +1x2 +1s1 =7
1x1 +1s2 = 4
Vamos escrever tudo em função das variáveis não básicas.

z = 0 −3x1 −2x2
s1 = 7 −1x1 −1x2
s2 = 4 −x1 →

Até onde é possível crescer x1 ?

 Exemplo 1

Voltemos ao tableau

Até onde é possível crescer x1 ?

↓
x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 1 1 1 0 = 7 s1 = 7
Linha 2 1 0 0 1 = 4 s2 = 4 →

PTC-3420
 Exemplo 1

Voltemos ao tableau

Até onde é possível crescer x1 ?

↓
x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 = 0 z=0
Linha 1 1 1 1 0 =7 s1 = 7
Linha 2 1 0 0 1 =4 s2 = 4 →
 
7 4
min , =4
1 1
s2 sai da base....
Variáveis básicas BV = {s1 , x1 } e as não básicas N = {s2 , x2 }

PTC-3420
Exemplo 1

Segundo ponto extremo

Para a nova base escreva:
1 As matrizes B, N, B −1
2 Quem são, no problema original, xB , xN , cB , cN
3 Qual o ponto extremo que está associado a essa variável?
4 Reescreva o problema parametrizado em relação à essa base
 Exemplo 1

A coluna associada a x1 deve virar uma coluna da identidade, pois

queremos escrever algo como

z = • − • x2 − • s 2
s1 = • − • x2 − • s2
x1 = • − • x2 − • s2
Ou seja, vamos parametrizar o problema em função das variáveis
não básicas.

PTC-3420
Exemplo 1

↓
x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 1 1 1 0 = 7 s1 = 7
Linha 2 1 0 0 1 = 4 s2 = 4 →
A coluna associada a x1 deve virar uma coluna da identidade
Exemplo 1

↓
x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 1 1 1 0 = 7 s1 = 7
Linha 2 1 0 0 1 = 4 s2 = 4 →
A coluna associada a x1 deve virar uma coluna da identidade

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4
Exemplo 1

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4

Escrevendo a função objetivo em relação às variáveis não básicas

obtemos: z = 12 + 2x2 − 3s2
Exemplo 1

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4

Escrevendo a função objetivo em relação às variáveis não básicas

obtemos: z = 12 + 2x2 − 3s2

x1 x2 s 1 s 2 Básicas
Linha 0 z 0 −2 0 3 = 12 z = 12
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4

A solução básica é ótima?

Exemplo 1

x1 x2 s1 s2 Básicas
Linha 0 z −3 −2 0 0 =0 z=0
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4

Escrevendo a função objetivo em relação às variáveis não básicas

obtemos: z = 12 + 2x2 − 3s2

x1 x2 s 1 s 2 Básicas
Linha 0 z 0 −2 0 3 = 12 z = 12
Linha 1 0 1 1 −1 = 3 s1 = 3
Linha 2 1 0 0 1 =4 x1 = 4

A solução básica é ótima?

Não! Vale a pena crescer x2
 Até onde é possível crescer x2 ?

↓
x1 x2 s1 s2 Básicas
Linha 0 z 0 −2 0 3 = 12 z = 12
Linha 1 0 1 1 −1 = 3 s1 = 3 →
Linha 2 1 0 0 1 =4 x1 = 4
( )
3 4
min , =3
1 //
0

s1 sai da base....
Variáveis básicas BV = {x2 , x1 } e as não básicas N = {s2 , s1 }

PTC-3420
Exemplo 1

Terceiro ponto extremo

Para a nova base escreva:
1 As matrizes B, N, B −1
2 Quem são, no problema original, xB , xN , cB , cN
3 Qual o ponto extremo que está associado a essa variável?
4 Reescreva o problema parametrizado em relação à essa base
 Exemplo 1

A coluna associada a x2 deve virar uma coluna da identidade

↓
x1 x2 s 1 s 2 Básicas
Linha 0 z 0 −2 0 3 = 12 z = 12
Linha 1 0 1 1 −1 = 3 x2 = 3
Linha 2 1 0 0 1 =4 x1 = 4

Escrevemos a função objetivo em relação às variáveis não básicas:

z = 17 − 2s1 − 1s2

x1 x2 s 1 s 2 Básicas
Linha 0 z 0 0 2 1 = 17 z = 18
Linha 1 0 1 1 −1 = 3 x2 = 3
Linha 2 1 0 0 1 =4 x1 = 4

PTC-3420
 Exemplo 1

A coluna associada a x2 deve virar uma coluna da identidade

↓
x1 x2 s 1 s 2 Básicas
Linha 0 z 0 −2 0 3 = 12 z = 12
Linha 1 0 1 1 −1 = 3 x2 = 3
Linha 2 1 0 0 1 =4 x1 = 4

Escrevemos a função objetivo em relação às variáveis não básicas:

z = 17 − 2s1 − 1s2

x1 x2 s 1 s 2 Básicas
Linha 0 z 0 0 2 1 = 17 z = 18
Linha 1 0 1 1 −1 = 3 x2 = 3
Linha 2 1 0 0 1 =4 x1 = 4
Não é possível aumentar a função objetivo: solução é ótima!
PTC-3420
 Exemplo 1
Baseado nos tableaux, determine, em cada iteração:
1 B −1 × b
2 B −1 × N
ctB B −1 × b


3

PTC-3420
 Exemplo 2

Vamos resolver o problema

max z = 60x1 + 30x2 + 20x3

s.a 8x1 + 6x2 + x3 ≤ 48
4x1 + 2x2 + 1.5x3 ≤ 20
2x1 + 1.5x2 + 0.5x3 ≤8
x2 ≤5
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0

PTC-3420
 Resolução

Defina as variáveis básicas BV = {s1 , s2 , s3 , s4 } e as não básicas

N = {x1 , x2 , x3 }
Escrevo o problema de outra forma

x1 x2 x3 s1 s2 s3 s4 Básicas
Linha 0 z −60 −30 −20 =0 z=0
Linha 1 8 6 1 1 = 48 s1 = 48
Linha 2 4 2 1, 5 1 = 20 s2 = 20
Linha 3 2 1, 5 0, 5 1 = 8 s3 = 8
Linha 4 1 1 = 5 s4 = 5

PTC-3420
 A solução básica é ótima?

z = 60x1 + 30x2 + 20x3

Até onde é possível crescer x1 ?

x1 x2 x3 s1 s2 s3 s4 Básicas
Linha 0 z −60 −30 −20 =0 z=0
Linha 1 8 6 1 1 = 48 s1 = 48
Linha 2 4 2 1, 5 1 = 20 s2 = 20
Linha 3 2 1, 5 0, 5 1 = 8 s3 = 8 →
Linha 4 1 1 = 5 s4 = 5

Considera-se
 
48 20 8
min , , , =4
8 4 2
de forma a preservar não negatividade das variáveis. Tomo x1 = 4
e s3 sai da base
PTC-3420
 Variáveis básicas BV = {s1 , s2 , x1 , s4 } e as não básicas
N = {s3 , x2 , x3 }

Para a nova base escreva:

1 As matrizes B, N,
2 Quem são, no problema original, xB , xN , cB , cN
3 Qual o vértice que está associado a essa variável?

PTC-3420
 Deve-se identificar o que ocorre ao considerar o valor da nova base
(x1 = 4 ). O coeficiente de x1 na linha 3 deve "virar"1 e os das
demais linhas devem "virar"0. Faço operações de pivotação.

↓
x1 x2 x3 s1 s2 s3 s4 Básicas
Linha 0 z −60 −30 −20 =0 z=0
Linha 1 8 6 1 1 = 48 s1 = 48
Linha 2 4 2 1, 5 1 = 20 s2 = 20
Linha 3 2 1, 5 0, 5 1 =8 s3 = 8
Linha 4 1 1 =5 s4 = 5

PTC-3420
 O coeficiente de x1 na linha 3 deve "virar"1.

↓
x1 x2 x3 s1 s2 s3 s4 Básicas
Linha 0 z 15 −5 30 = 240 z = 240
Linha 1 −1 1 −4 = 16 s1 = 16
Linha 2 −1 0, 5 1 −2 =4 s2 = 4 →
Linha 3 1 0, 75 0, 25 0, 5 =4 x1 = 4
Linha 4 1 1 =5 s4 = 5

Função objetivo: z = 240 − 15x2 + 5x3 − 30s3 ⇒ Cresço x3

Saída da base:  
4 4
min , =8
0.5 0.25
Sai s2

PTC-3420
 .

↓
x1 x2 x3 s 1 s2 s3 s4 Básicas
Linha 0 z 5 10 10 = 280 z = 280
Linha 1 −2 1 2 −8 = 24 s1 = 24
Linha 2 −2 1 2 −4 =8 x3 = 8
Linha 3 1 1, 25 −0, 5 1, 5 =2 x1 = 2
Linha 4 1 1 =5 s4 = 5

Função objetivo: z = 280 − 5x2 − 10s2 − 10s3

Não é possível aumentar a função objetivo: solução é ótima!

PTC-3420
 Exemplo 2
Baseado nos tableaux, determine, em cada iteração:
1 B −1 × b
2 B −1 × N
ctB B −1 × b


3

PTC-3420