Investigação Operacional - ISUTC

Investigação Operacional

Regente: Prof. Dr. Cachimo Assane

Capítulo 2: Tema 3 - O Método Simplex Directo

Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I

Regente: Prof. Dr. Cachimo Assane (ISUTC) Investigação Operacional Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I 1 / 1

Fundamentação Teórica do Método Simplex� O método de simplex é um algoritmo exacto, extremamente eficiente, um dosmais utilizados para determinar a solução óptima de um PPL.

� É um procedimento baseado em Álgebra Linear. Entretanto, seus conceitossubjacentes são geométricos.

� Algumas notações da Algebra Linear:Ü Se v é um vector coluna ⇒ vT é um vector linha;Ü A•j representa a j-ésima coluna da matriz A;Ü Ai• representa a i-ésima linha da matriz A;Ü S indica a sequência de índices das colunas ⊂ {1 2 · · · n};Ü AS representa a submatriz relacionada a sequência S.

Dada a matriz A =[

1 2 0 34 1 3 2

]→ A•2 =

[21

]; e

A1• =[1 2 0 3

]. Da mesma forma:

Se S = {2, 4} ⇒ AS =[

2 31 2

].


Conceitos básicos: PPL na Forma Padrão1) Um PPL está na Forma padrão se e somente se está na forma:

Minimizar c1x1 + c2x2 + . . .+ cnxn

Sujeito a :

a11x1 + a12x2 + . . .+ a1nxn = b1

a21x1 + a22x2 + . . .+ a2nxn = b2

...am1x1 + am2x2 + . . .+ amnxn = bm

x1 ≥ 0, x2 ≥ 0, . . . xn ≥ 0.

Características do PPL na forma padrão:� a função objectivo deve ser de minimização;� as restrições são definidas por um sistema de equações lineares cujos ladosdireitos (os bi) são não-negativos;

� as condições de não-negatividade das variáveis de decisão (x ′i s)complementam as restrições do PPL.


Conceitos básicos: PPL na Forma Padrão

Notação matricial de um PPL na Forma padrão:

Minimizar cTxs.a :{

Ax = bx ≥ 0,

A =

a11 a12 · · · a1na21 a22 · · · a2n...

......

am1 am2 · · · amn

; cT = [c1 c2 · · · cn]; x =

x1x2...

xn

,

b =

b1b2...

bn

e 0 =

00...0

.Denota-se cT a transposta do vector c.


Transformação do PPL na forma padrão

� Restrições de desigualdade:Ü Suponha que a restrição i seja dada por

ai1x1 + ai2x2 + . . .+ ainxn ≤ bi

Para converter (≤) em (=), basta adicionar uma variável de folga não-negativa no lado esquerdo da restrição. Ou seja,

ai1x1 + ai2x2 + . . .+ ainxn + xk = bi , xk ≥ 0

Por exemplo, para restrição 3x1 + 4x2 − x3 ≤ 7, a forma padrão é:

3x1 + 4x2 − x3+x4 = 7, x4 ≥ 0

Ü Analogamente, se a restrição for da forma

ai1x1 + ai2x2 + . . .+ ainxn ≥ bi


Transformação do PPL na forma padrão

basta subtrair uma variável de excesso não-negativa no lado esquerdo dainequação para transformá-la em igualdade, ou seja,

ai1x1 + ai2x2 + . . .+ ainxn - xk = bi , xk ≥ 0

Por exemplo, para restrição 3x1 + 4x2 − x3 ≥ 7, tem-se:

3x1 + 4x2 − x3−x4 = 7, x4 ≥ 0

� Variáveis irrestritas (livres): Se xi é irrestrita de sinal do problema, entãoxi = x ′

i − x ′′

i , com x ′

i ≥ 0, x ′′

i ≥ 0

� Variáveis negativas: xi ≤ 0⇔ xi = −x ′

i , com x ′

i ≥ 0

� Função objectivo: Maximizar{F (x)} ⇔ −Minimizar{−F (x)}.


Transformação do PPL na forma padrãoExemplo: O seguinte PPL:

Maximizar Z = x1 − x3

Sujeito a :x1 + 2x2 − x3 ≥ 2x1 − x2 − 3x3 = 1x2 + x3 ≤ 5x1 irrestrito, x2 ≥ 0, x3≤ 0,

é equivalente ao problema na forma padrão:

−Minimizar Z = −(x′

1 − x′′

1 )− x′

3

Sujeito a :x ′

1 − x ′′

1 + 2x2 + x ′

3 − x4 = 2x ′

1 − x ′′

1 − x2 + x ′

3 = 1x2 − x ′

3 + x5 = 5x ′

1, x′′

1 , x2, x′

3, x4, x5 ≥ 0


Transformação do PPL na forma padrãoExemplo: O seguinte PPL:

Maximizar Z = x1 − x3

Sujeito a :x1 + 2x2 − x3 ≥ 2x1 − x2 − 3x3 = 1x2 + x3 ≤ 5x1 irrestrito, x2 ≥ 0, x3≤ 0,

é equivalente ao problema na forma padrão:

−Minimizar Z = −(x′

1 − x′′

1 )− x′

3

Sujeito a :x ′

1 − x ′′

1 + 2x2 + x ′

3 − x4 = 2x ′

1 − x ′′

1 − x2 + x ′

3 = 1x2 − x ′

3 + x5 = 5x ′

1, x′′

1 , x2, x′

3, x4, x5 ≥ 0


Conceitos básicos: PPL na Forma Canônica2) Se o PPL está na Forma padrão, e ∃ uma sequência S, t.q AS = I e CS = 0,

então o PPL está na forma canônica em relação à sequência S. I(S×S) é umamatriz identidade.

Exemplo: Minimizar 2x1 + x3 − x5 + x6

s.a

3x1 − 2x3 + x5 + x7 = 12x1 + x2 − 3x5 = 83x1 + 17x3 + x4 + x6 = 2xj ≥ 0 ∀j .

Reescrevendo o problema de forma matricial, tem-se:[x1 x2 x3 x4 x5 x6 x7

]Min

[2 0 1 0 −1 1 0

]s.a

3 0 −2 0 1 0 12 1 0 0 −3 0 03 0 17 1 0 1 0

=

182

Logo, o PPL está na forma canônica em relação S = {7, 2, 4}.


Conceitos básicos: PPL na Forma Canônica2) Se o PPL está na Forma padrão, e ∃ uma sequência S, t.q AS = I e CS = 0,

então o PPL está na forma canônica em relação à sequência S. I(S×S) é umamatriz identidade.

Exemplo: Minimizar 2x1 + x3 − x5 + x6

s.a

3x1 − 2x3 + x5 + x7 = 12x1 + x2 − 3x5 = 83x1 + 17x3 + x4 + x6 = 2xj ≥ 0 ∀j .

Reescrevendo o problema de forma matricial, tem-se:[x1 x2 x3 x4 x5 x6 x7

]Min

[2 0 1 0 −1 1 0

]s.a

3 0 −2 0 1 0 12 1 0 0 −3 0 03 0 17 1 0 1 0

=

182

Logo, o PPL está na forma canônica em relação S = {7, 2, 4}.


Conceitos básicos: Conjunto convexo� Conjunto convexo: Um conjunto C ⊆ Rn é convexo sse ∀x , y ∈ C ,

λx + (1− λ)y ∈ C ,∀λ ∈ [0, 1]

� Teorema: O conjunto C das soluções viáveis de um PPL é um conjuntoconvexo.

� Ponto extremo: u ∈ C é um ponto extremo (ou vértice) do conjunto C desoluções viáveis de um PPL, se > x , y ∈ C : u = λx + (1 − λ)y ,∀λ ∈ [0, 1].Ou seja u é ponto extremo se não for um ponto interior de uma linha rectaque conecta x e y .


Conceitos básicos: Solução básica de um PPL

Suponha um PPL na forma padrão:

Minimizar cTxs.a :{

Ax = bx ≥ 0,

onde A é uma matriz m × n (m < n); x é um vector n−dimensional (no devariáveis); b é um vector m−dimensional (no de equações).� Se igualarmos n − m variáveis zero (denominadas variáveis não básicas), edepois resolvermos as m equações para as m variáveis restantes (denominadasvariáveis básicas), a solução resultante, se for única é denominada SoluçãoBásica.

� Uma solução básica corresponde a um vértice ou ponto extremo (viável ou não)da região de soluções.


Conceitos básicos: Solução básica de um PPL

Exemplo: Considere o seguinte PPL com duas variáveis:

Maximizar Z = 2x1 + 3x3

s.a2x1 + x2 ≤ 4x1 + 2x2 ≤ 5x1, x2 ≥ 0

Na forma padrão, o problema fica:

Minimizar − Z = −2x1 − 3x3

s.a2x1 + x2 + x3 = 4x1 + 2x2 + x4 = 5x1, x2, x3, x4 ≥ 0

O sistema tem m = 2 equações e n = 4 variáveis. Assim, as soluções básicas(pontos extremos) podem ser determinadas algebricamente igualando n − m =4−2 = 2 variáveis em zero e, depois, resolvendo para as m = 2 variáveis restantes.


Conceitos básicos: Solução básica de um PPLRepresentação gráfica da região de soluções para o problema e os lugaresgeométricos (LG) de x1 = 0, x2 = 0, x3 = 0 e x4 = 0:

� Por exemplo, se fizermos x1 = 0 e x2 = 0, as equações dão solução (básica)única

x3 = 4, x4 = 5

� Esta solução corresponde ao ponto A na figura acima.Regente: Prof. Dr. Cachimo Assane (ISUTC) Investigação Operacional Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I 12 / 1

Conceitos básicos: Solução básica de um PPL� Um outro ponto pode ser determinado fazendo x3 = 0 e x4 = 0, e entãoresolvendo as duas equações

2x1 + x2 = 4x1 + 2x2 = 5

o que resulta na solução básica (x1 = 1, x2 = 2), que é o ponto C na figuraacima.

� O número máximo de soluções básicas de um PPL é

Cnm = n!

m!(n −m)! .

� Definição: Se todos os valores da solução básica forem não negativos, então asolução básica é Solução Básica Viável (SBV).

� Por exemplo, para determinar o ponto E , fazemos x2 = 0 3 x4 = 0. Resolvendoas equações, obtemos a solução básica única (x1 = 5, x3 = −6).

� Como x3 < 0, então a solução obtida é uma solução básica não viável (nãocandidata a solução óptima)


Conceitos básicos: Solução básica viável de um PPL

� Teorema (Equivalência entre pontos extremos e SBV): Toda SBV do sistemaAx = b é um ponto extremo (ou vértice) do conjunto C de soluções viáveis deum PPL.

� Teorema: A solução óptima de um PPL com um conjunto C de soluções viáveisserá atingida ao menos em um vértice de C (SBV óptima).

� Trabalho domiciliar:

Considerando o PPL deste exemplo, encontre soluções básicascorrespondentes aos vértices B,D e F , indicando as respectivas sequências.Identificar as soluções básicas viáveis.


O Algoritmo Simplex

� Sabe-se que as soluções básicas viáveis (candidatas a soluções óptimas) dequalquer PPL localizam-se sobre os vértices da região de soluções viáveis.

� A idéia básica do algoritmo simplex é: mover-se de um vértice (i.e, um pontoextremo da região de soluções viáveis) a outro vértice adjacente, sempre quefor possível melhorar o valor da função objectivo, até atingir a solução óptima(a melhor SBV);

� Portanto, o método simplex se concentra exclusivamente em SBV. Se o PPLtem (pelos menos) uma solução óptima, ela é a melhor SBV.

� Vantagem do método simplex: Na maioria dos casos, o método simplex nãoprecisará explorar todos os pontos extremos (SBV) para atingir uma soluçãoóptima.


O Algoritmo Simplex

� A forma mais conveniente para realizar as operações no método simplex éorganiza-las em tabelas, chamadas tabelas simplex.

� Basicamente, a tabela simplex apresenta os coeficientes das variáveis emcolunas e as restrições e função objectivo em linhas.

RESOLUÇÃO DE UM PPL USANDO A TABELA SIMPLEX

Como exemplo, considere o PPL:


Sujeito a :2x1 + x2 ≤ 4x1 + 2x2 ≤ 5x1, x2 ≥ 0.


O PROCEDIMENTO DO SIMPLEX� Passo 0: Transformar o PPL na forma canônicaPara este exemplo, a forma padrão do PPL fica:

Minimizar − Z = −2x1 − 3x2 + 0x3 + 0x4

Sujeito a :2x1 + x2 + x3 + 0x4 = 4x1 + 2x2 + 0x3 + x4 = 5x1, x2, x3, x4 ≥ 0

Observe que, para S = {3, 4}, AS =[

1 00 1

]= I e Cs = 0, então o PPL está

na forma canônica em relação a essa sequência.

� Passo 1: Encontrar a solução básica inicial e apresenta-la na forma tabular(tabela simplex inicial)“Sempre que possível, a inicialização do método simplex opta pela origem(todas as variáveis de decisão iguais a zero) como a SBV inicial.”(Hillier eLieberman, 2013).


O PROCEDIMENTO DO SIMPLEX� Passo 0: Transformar o PPL na forma canônicaPara este exemplo, a forma padrão do PPL fica:

Minimizar − Z = −2x1 − 3x2 + 0x3 + 0x4

Sujeito a :2x1 + x2 + x3 + 0x4 = 4x1 + 2x2 + 0x3 + x4 = 5x1, x2, x3, x4 ≥ 0

Observe que, para S = {3, 4}, AS =[

1 00 1

]= I e Cs = 0, então o PPL está

na forma canônica em relação a essa sequência.� Passo 1: Encontrar a solução básica inicial e apresenta-la na forma tabular(tabela simplex inicial)“Sempre que possível, a inicialização do método simplex opta pela origem(todas as variáveis de decisão iguais a zero) como a SBV inicial.”(Hillier eLieberman, 2013).


O PROCEDIMENTO DO SIMPLEXAssim, para o sistema de equações do exemplo,

2x1 + x2 + x3 + 0x4 = 4x1 + 2x2 + 0x3 + x4 = 5x1, x2, x3, x4 ≥ 0,

fixando x1 = 0 e x2 = 0, tem-se x3 = 4 e x4 = 5. Portanto, a SBV inicial (trivial)é x=(0,0,4,5), resultando no valor da F.O −Z = −2 · 0 − 3 · 0 + 0 · 4 + 0 · 5 =0⇔ Z = 0.A tabela simplex inicial ficará da seguinte forma:

VB x1 x2 x3 x4 bx3 2 1 1 0 4x4 1 2 0 1 5

F .O. -2 -3 0 0 −Z

Note que a equação da função objectivo sempre é escrita em termos das variáveisnão básicas. Para o exemplo,

−2x1 − 3x2 = −Z ,

onde Z é um parâmetro (variável) da função objectivo.Regente: Prof. Dr. Cachimo Assane (ISUTC) Investigação Operacional Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I 18 / 1

O PROCEDIMENTO DO SIMPLEX

� Observe ainda que na tabela acima:Ü As varáveis de folga (x3 e x4) são as variáveis básicas iniciais (formam uma

base canônica);Ü Cada variável básica tem coeficiente +1 em uma equação e 0 nas outras

(incluindo na função objectivo);Ü Cada equação possui exatamente uma variável básica com o coeficiente +1.

� Passo 2: Executar um teste de optimalidade: a SBV actual é óptima?Ü Se todos os coeficientes da função objectivo (última linha) forem não

negativos (≥ 0), então pare, a SBV actual é óptima;Ü Caso contrário, realize uma iteração para obter a próxima SBV (Passo 3).

Significa que a SBV actual pode ser melhorada.



� Passo 3: Determinar a variável a entrar na base:Seleciona-se a variável não básica com coeficiente “mais negativo” (maior valorabsoluto) na função objectivo. A coluna associada a essa variável é chamadacoluna pivô.

VB x1 x2 x3 x4 bx3 2 1 1 0 4x4 1 2 0 1 5

F .O -2 -3 0 0 −Z⇑

� Passo 4: Determinar a variável que sairá da base aplicando oteste da razão mínima (Condição de viabilidade):O Objectivo do teste é determinar a variável básica cai a zero primeiro, à medidaque a variável básica que entra é aumentada.

Para o Exemplo: Já que x2 vai tornar-se VB, x1 continuará não básica e igual azero.


O PROCEDIMENTO DO SIMPLEXAssim, as equações podem ser vistas como

x2 + x3 = 42x2 + x4 = 5

Uma das duas VB (x3 ou x4) deverá tornar-se variável não básica, mas a outranão pode ser negativa (Isso garante a viabilidade da próxima solução básica).Assim

x3 = 4− x2 ≥ 0x4 = 5− 2x2 ≥ 0

Escrevendo em função de x2, tem-se:

x2 ≤ 4x2 ≤ 5

2

Desse modo, x2 pode ser aumentada apenas até 52 , no qual o ponto x4 chega

a 0 e x3 continua positiva. Caso contrário, x4 seria negativa, o que violaria aviabilidade do problema. Assim, x4 é a VB que se torna variável não básica.



� Resumindo (Teste da Razão mínima): Esta verificação implica uma escolha dalinha com menor razão entre o lado direito das equações, bj , e o coeficiente dacoluna pivô que seja estritamente positivo (> 0).

A linha associada a variável que sai da base é chamada chamada linha pivô. Oponto de intersecção da linha pivô com a coluna pivô é conhecido como elementopivô

VB x1 x2 x3 x4 b Razãox3 2 1 1 0 4 4/1

⇐ x4 1 2 0 1 5 5/2← mín.F.O. -2 -3 0 0 −Z

⇑

� min{ 4

1 ,52}

= 52

� Então, x2 substitui x4 como variável básica.



� Passo 5: Construir uma nova tabela simplex com a nova SBVRecolocar o problema na forma canônica usando operações elementares emlinhas, chamadas operações de “pivoteamento” ou, simplesmente, deeliminação gaussiana.1) Linha pivô

i) Substituir a variável que sai da base pela variável que entra na base;ii) Nova linha pivô=Linha pivô actual÷ Elemento pivô

2) Todas as outras linhas, incluindo zNova Linha =(Linha actual)-(Seu coeficiente de coluna pivô)×(Nova linhapivô)

� Para o exemplo:Ü Já que x2 substitui x4 como variável básica, inicialmente, divide-se a linha

pivô (linha 2) pelo elemento pivô (2), obtendo-se:VB x1 x2 x3 x4 bx2 1/2 1 0 1/2 5/2



� Continuando:Ü Na linha 1, devemos encontrar 0 no coeficiente relativo a x2. Operaremos

com a linha 2, já modificada. Assim, deve-se fazer L′

1 = L1− L′

2. Encontra-se, então:

VB x1 x2 x3 x4 bx3 3/2 0 1 -1/2 3/2x2 1/2 1 0 1/2 5/2

Ü Para que o coeficiente de x2 na linha 3 (F.O) seja zero, deve-se fazer L′

3 =L3 + 3L′

2:VB x1 x2 x3 x4 bx3 3/2 0 1 -1/2 3/2x2 1/2 1 0 1/2 5/2F.O -1/2 0 0 3/2 −Z + 15/2

� Fim da primeira iteração (vá para o Passo 1).


O PROCEDIMENTO DO SIMPLEX� A 2a iteração começa a partir da última tabela (Passo 1):

VB x1 x2 x3 x4 bx3 3/2 0 1 -1/2 3/2x2 1/2 1 0 1/2 5/2F.O -1/2 0 0 3/2 −Z + 15/2

� Passo 2 Teste de optimalidade: há possibilidade de melhorar a F.O? Sim, pois∃j tal que cj < 0.

� Passo 3: A coluna pivô será, obviamente x1;� Passo 4: Teste da razão mínima - min{ 3

2 ÷32 ; 5

2 ÷12} = 1. Portanto, x3 sai da

base (linha pivô). A nova SBV terá sequência {x1, x2}.� Passo 5: Operações de pivoteamento (eliminação de Gauss):

VB x1 x2 x3 x4 bL

′1 = (2/3)L1 x1 1 0 2/3 -1/3 1

L′2 = L2 − (1/2)L

′1 x2 0 1 -1/3 2/3 2

L′3 = L3 + (1/2)L

′1 F.O 0 0 1/3 4/3 −Z + 8

� SBV óptima alcançada: Esta solução é óptima, uma vez que ∀j , cj ≥ 0. Ovalor da função objectivo é 8, pois 0 = −Z + 8.



� SBV óptima alcançada: Esta solução é óptima, uma vez que ∀j , cj ≥ 0. Ovalor da função objectivo é 8, pois 0 = −Z + 8.

� A solução é x∗ =

x1x2x3x4

=

1200

, que resulta em Z∗ = 8.


CASOS ESPECIAIS DO MÉTODO SIMPLEX

Situações que podem surgir na utilização do método simplex:� Empate para a variável não básica que entraQuando duas ou mais variáveis não-básicas estão empatadas por terem o mesmocoeficiente “mais negativo” na função objetivo, a escolha da variável que entrana base é feita de forma arbitrária.

� Empate para a variável básica que sai (Degeneração)Quando duas ou mais variáveis básicas são candidatas a variável que sai dabase, isto é, quando ocorre empate na razão mínima, a escolha também éarbitrária. Quando isto acontece,Ü no mínimo uma variável básica (aquela não escolhida para sair da base) terá

um valor zero na nova SBV, e diz-se que a nova SBV é degenerada;Ü O PPL tem, no mínimo, uma restrição redundante (há superdeterminação

de pontos extremos).


CASOS ESPECIAIS DO MÉTODO SIMPLEXExemplo:


s.ax1 + 4x2 ≤ 8x1 + 2x2 ≤ 4x1, x2 ≥ 0.

-1 1 2 3 4 5

-1

1

2

3

x-axis

y-axis


CASOS ESPECIAIS: DEGENERAÇÃO

TABELA SBV VB x1 x2 x3 x4 bx3 1 4 1 0 8

INICIAL x4 1 2 0 1 4F.O -3 -9⇑ 0 0 −Z

L′1 = (1/4)L1 x2 1/4 1 1/4 0 2

L′2 = L2 − 2L′

1 x4 1/2 0 -1/2 1 0

L′3 = L3 + 9L′

1 F.O -3/4⇑ 0 9/4 0 −Z + 18L′

1 = L1 − (1/4)L′2 x2 0 1 1/2 -1/2 2

L′2 = 2L2 x1 1 0 -1 2 0

L′3 = L3 + (3/4)L′

2 F.O 0 0 3/2 3/2 −Z + 18

A solução óptima do problema é x∗ = [0, 2, 0, 0], com Z∗ = 18.� O empate no critério que determina a variável que sai (na tabela inicial), levaà degeneração na primeira iteração (x4 = 0);

� Na solução gráfica, observa-se que três rectas passam pelo vértice óptimo (x1 =0, x2 = 2).


CASOS ESPECIAIS DO MÉTODO SIMPLEX� Solução ilimitada (PPL ilimitado): ocorre quando a solução do PPL pode sermelhorada indefinidamente sem violar nenhuma das restrições. Suponha oseguinte PPL:

Maximizar Z = x1 + 3x2

s.a.−2x1 + x2 ≤ 2 R1x1 − 3x2 ≤ 3 R2x1, x2 ≥ 0 R3


CASOS ESPECIAIS: PPL ILIMITADONa forma tabular tem-se:

VB x1 x2 x3 x4 bx3 -2 1 1 0 2 2/1 = 2x4 1 -3 0 1 3 3/(−3) = -1F.O -1 -3 0 0 −Z

x2 é a variável que entrará na base, e por conseguinte, x1 continuará sendo nãobásica (x1 = 0). Para escolha da variável que sai da base, entre x3 e x4, observa-seo seguinte:

−2x1 + x2 + x3 = 2→ x3 = 2− x2 ≥ 0→ x2 ≤ 1x1 − 3x2 + x4 = 3→ x4 = 3 + 3x2 ≥ 0→ x2 ≥ −1

� Observe que a segunda equação não impõe nenhuma restrição sobre x2 (x2pode ser aumentada indefinidamente sem violar a restrição).

� Por isso, não se deve considerar o teste da razão quando o coeficiente da colunapivô (excluindo-se a linha da F.O.) é negativo ou então zero. Assim, x3 devesair da base.


CASOS ESPECIAIS: PPL ILIMITADODesta forma, a partir da SBV inicial:

VB x1 x2 x3 x4 bx3 -2 1 1 0 2x4 1 -3 0 1 3F.O -1 -3⇑ 0 0 −Z

Obtem-se a nova sequência {2, 4}Operações VB x1 x2 x3 x4 bL′

1 = L1 x2 -2 1 1 0 2L′

2 = L2 + 3L′

1 x4 -5 0 3 1 9L′

3 = L3 + 3L′

1 F.O -7⇑ 0 3 0 −Z + 6

� Como o coeficiente de x1 na linha da F.O. é negativo, então há possibilidadede melhorar a SBV.

� No entanto, nenhuma das restrições impõe limites ao crescimento de x1(coeficientes da coluna pivô negativos);

� Nenhuma variável básica pode sair da base; O PPL é ilimitado.Regente: Prof. Dr. Cachimo Assane (ISUTC) Investigação Operacional Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I 32 / 1

CASOS ESPECIAIS DO MÉTODO SIMPLEX� Infinitas (Múltiplas) soluções óptimas: Quando a F.O. tem uma direcçãoparalela a uma das restrições e seu valor óptimo se encontra exatamentesobre a recta dessa restrição.

Exemeplo : Minimizar Z = −2x1 − 4x2

s.a.x1 + 2x2 ≤ 4 R1−x1 + x2 ≤ 1 R2x1, x2 ≥ 0 R3


CASO DE MÚLTIPLAS SOLUÇÕES ÓPTIMASResolução do PPL usando a tabela simplex:

VB x1 x2 x3 x4 bx3 1 2 1 0 4x4 -1 1 0 1 1

F.O -2 -4⇑ 0 0 Z

Usando operações elementares de Gauss, obtem-se:

Operações VB x1 x2 x3 x4 bL

′1 = L1 − 2L

′2 x3 3 0 1 -2 2

L′2 = L2 x2 -1 1 0 1 1

L′3 = L3 + 3L

′1 F.O -6⇑ 0 0 4 Z + 4

L′1 = (1/3)L1 x1 1 0 1/3 -2/3 2/3

L′2 = L2 + L

′1 x2 0 1 1/3 1/3 5/3

L′3 = L3 + 6L

′1 F.O 0 0 2 0 Z + 8

� A SBV actual é óptima, x = (2/3, 5/3, 0, 0), Z = −8.

� Note que, o coeficiente de x4 (não básica) na linha de F.O. é zero; Isto significaque existe uma solução óptima alternativa.


CASO DE MÚLTIPLAS SOLUÇÕES ÓPTIMAS

� Para verificar qual é essa solução, força-se a entrada de x4 na base.VB x1 x2 x3 x4 bx1 1 0 1/3 -2/3 2/3x2 0 1 1/3 1/3 5/3

F.O 0 0 2 0⇑ Z + 8L

′1 = L1 + (2/3)L

′2 x1 1 2 1 0 4

L′2 = 3L2 x4 0 3 1 1 5

L′3 = L3 F.O 0 0 2 0 Z + 8

� O método simplex determina apenas os dois pontos extremos:xA = [2/3, 5/3, 0, 0] e xB = [4, 0, 0, 5];

� Todas as outras soluções óptimas são obtidas como uma combinação linearconvexa dessas duas SBV óptimas: x∗ = αxA + (1− α)xB , 0 ≤ α ≤ 1.

� Quando α = 0⇒ x∗ = xB . Se α = 1⇒ x∗ = xA.� Para valores de α entre 0 e 1, x∗ está entre os pontos de xA e xB .


SÍNTESE DO ALGORITMO SIMPLEX

Considere um PPL escrito na forma canônica.� Passo 1: Determine uma tabela simplex inicial.

� Passo 2: Aplique o teste de optimalidade: Se todos os coeficientes da funçãoobjectivo (última linha) forem não negativos (≥ 0), então pare, a SBV actualé óptima; Caso contrário, vá para o Passo 3.

� Passo 3: Encontre a variável que entra na base (coluna pivô), selecionando avariável não básica com coeficiente mais positivo da função objetivo. Se houverempate na escolha da coluna pivô, a decisão é arbitrária;


SÍNTESE DO ALGORITMO SIMPLEX

� Passo 4: Aplique o teste da razão mínima para encontrar a variável básica quesai na base (linha pivô). Escolha a linha com menor razão entre o lado direitodas equações, bj , e o coeficiente da coluna pivô que seja estritamente positivo(> 0). Se houver empate, a escolha é arbitrária. Se todos os coeficientes dacoluna pivô forem negativos, então pare, o PPL não tem uma solução óptima,mas sim uma solução ilimitada.

� Passo 5: Obtenha uma nova tabela simplex (O PPL deverá estar na formacanônica com nova SBV) usando operações elementares em linha. Então,retorne ao Passo 2.


FLUXOGRAMA PARA O ALGORITMO SIMPLEX

Não

Sim

Não

Sim

Determine uma tabela inicial

coeficiente negativo na

linha da F.O?

O PPL não tem solução óptima finita

PARE

Obtenha a coluna pivô

coeficiente positivo na coluna pivô?

A solução actual é óptima

PARE

Obtenha a linha pivô

Obtenha uma nova tabela aplicando o

pivoteamento


Documents

Investigação Operacional - ISUTC