Método Simplex

Prévia do material em texto

C A P Í T U L O 3 
Método Simplex 
 
1. Soluções Básicas Admissíveis 
 Considere um problema de PL representado nas suas formas padrão e matricial. Uma base é 
um conjunto de m variáveis, tais que a matriz dos coeficientes do sistema de equações lineares (3.2) é 
não singular (isto é, cujo determinante é não nulo). Por outras palavras, é toda a submatriz quadrada 
regular (m×m) contida em A (m×n)  existe pelo menos uma, já que car (A) = m < n. 
 Então, pode-se rescrever a matriz A da seguinte forma : 
 A = [ ]NB 
onde N é a submatriz formada pelas colunas de A que não estão na base B. 
 Da mesma forma, se pode particionar o vector X em 
 X = [ ] TNB XX 
e o vector C em 
 C = [ ]NB CC . 
Portanto, o problema pode ser representado da seguinte forma : 
 Maximizar [ ] 


×=
N
B
NB
X
X
CCZ 
 Sujeito a [ ] bXNXBb
X
X
NB NB
N
B =+⇔=


× 
 X ≥ 0 
 
28 Método Simplex 
Considere-se as seguintes definições : 
¾ variáveis básicas (VB) : as m variáveis que formam a base do sistema 
¾ variáveis não básicas (VNB) : as restantes n-m variáveis 
¾ solução básica (SB) : solução cujos valores das VNB são nulos (X com XN = 0 e XB = B-1 b) 
¾ solução básica admissível (SBA) : SB com todas as VB não negativas (XB ≥ 0) 
¾ SBA não degenerada : SBA em que as VB são estritamente positivas (XB > 0) 
¾ SBA degenerada : SBA em que uma ou mais VB são nulas 
¾ base admissível : uma base que corresponde a uma solução básica admissível 
¾ um ponto x ∈ X é ponto extremo se e só se constituir uma SBA do problema de PL 
¾ o conjunto dos vértices de um politopo X = { x : A x = b, x ≥ 0, x ∈ Rn } corresponde ao conjunto 
de soluções básicas admissíveis 
¾ o conjunto dos PE da região admissível corresponde ao conjunto das SBA e são ambos não 
vazios, desde que a região admissível seja não vazia. Cada SBA é equivalente a um PE, mas 
podem existir várias SBA correspondendo ao mesmo PE. 
Propriedades dos pontos extremos admissíveis : 
1. Se existe apenas uma solução óptima, então tem de ser um PE admissível. 
2. Se existem várias soluções óptimas, então pelo menos 2 são PE admissíveis adjacentes. 
3. Existe um número finita de PE admissíveis. 
4. Se um PE admissível não tem PE admissíveis adjacentes melhores, então esse PE é óptimo. 
As propriedades 1 e 2, implicam que a pesquisa de uma solução óptima pode ser reduzida, 
considerando apenas os PE admissíveis; desta forma, existe um número finito de soluções a 
considerar (propriedade 3). A propriedade 4 fornece um teste de optimalidade muito conveniente. 
2. Método Simplex 
 O método Simplex explora as 4 propriedades dos pontos extremos admissíveis apresentadas no 
sub-capítulo anterior (1), apenas examinando relativamente poucos PE admissíveis e parando logo 
que um deles passe o teste de optimalidade. Desta forma, o método Simplex move-se repetidamente 
(iterativamente) do PE admissível actual para um melhor PE admissível, até que a solução actual não 
tenha nenhum PE admissível adjacente melhor. Este processo é composto pelos seguintes passos : 
1º) Iniciação : Começar com um PE admissível. Qualquer PE admissível pode ser adoptada como 
solução inicial; no entanto, uma boa hipótese para a SBA inicial será considerar as slacks como 
VB e as originais como VNB. 
2º) Iteração : Mover-se para um melhor PE admissível adjacente. (Repetir este passo quantas 
vezes forem necessárias). Este movimento implica a conversão de uma VNB numa VB 
Método Simplex 
Algoritmo Primal Simplex (problema de maximização) 29 
(chamada a variável básica de entrada) e, simultaneamente, a conversão de uma VB numa 
VNB (chamada variável básica de saída), para depois identificar a nova SBA. 
3º) Teste de optimalidade : O PE admissível actual é óptimo se nenhum dos PE admissíveis seus 
adjacentes são melhores. 
3. Algoritmo Primal Simplex (problema de maximização) 
 Considere-se um problema de PL de maximização na sua forma padrão (Error! Reference 
source not found.). Na resolução de um problema através do algoritmo de Simplex, recorre-se ao 
chamado quadro Simplex. Supondo que as variáveis básicas são as primeiras m, 
 xB = (x1, ..., xm) e 
 xN = (xm+1, ..., xm+n), 
o quadro Simplex padrão assume o seguinte aspecto : 
XB xB xN 2º membro 
 Im NBA 1−= bBxb 1B −== 
zj − cj 0 NB CAC − bCZ BB = 
Passo inicial : 
Construir o quadro Simplex, considerando como SBA inicial, as m variáveis slacks, ficando o quadro 
Simplex com o seguinte aspecto : 
XB x1 . . . xn xn+1 . . . xn+m 2º m. 
xn+1 a11 . . . a1n 1 . . . 0 b1 
. . . . . . . . . . . . . . . . . . . . . . . . 
xn+m am1 . . . amn 0 . . . 1 bm 
zj − cj − c1 − cn 0 . . . 0 0 
Passo principal : Considerar o quadro Simplex padrão. 
1) Seja zk − ck = mínimo { zj − cj : j ∈ R }, onde R é o conjunto dos índices das VNB (candidatas a 
entrarem na base) 
Se zk − ck ≥ 0 então a SBA actual é óptima senão continuar (teste de optimalidade) 
2) Examinar a coluna k do quadro ( kA ) : 
Se ikA ≤ 0 ∀ i então o problema tem óptimo ilimitado (+∞) senão continuar. 
3) A variável xk entra na base e a xt sai da base, sendo t determinado pelo seguinte teste : 
 



 >== 0a,
a
bmin
a
bx ik
ik
i
tk
t
t . 
Método Simplex 
30 Algoritmo Primal Simplex (problema de maximização) 
Se existirem mais do que uma variável nestas condições, qualquer uma pode ser usada (conduz 
a soluções degeneradas). 
4) Actualizar o quadro Simplex, sendo o “pivot” o valor de tka , utilizando o método de 
eliminação de Gauss, de forma que o quadro apresente as seguintes alterações : 
a) na coluna k aparece tudo a 0, excepto na posição do “pivot” onde aparece 1, 
b) a linha zj − cj recalculada. 
Exemplo : 
 Uma empresa fabrica dois tipos de produtos : A e B. O lucro unitário líquido de cada um é 45 
(A) e 30 u.m. (B). Numa máquina, os produtos são processados durante 2 min. (A) e 1 min. (B). A 
máquina está disponível 1000 min.. Cada um dos produtos requer 1 min. de mão-de-obra directa. A 
disponibilidade de mão-de-obra é 800 min.. 
 Estudos de mercado indicam que a procura dos produtos A e B não excede 400 e 700 unidades, 
respectivamente. 
 Quantas unidades de A e B devem ser fabricadas de modo a maximizar o lucro ? 
Formalização do problema : 
 x1 = quantidade de unidades do produto A 
 x2 = quantidade de unidades do produto B 
 Max 45 x1 + 30 x2 (lucro) 
 s. a 2 x1 + x2 ≤ 1 000 (máquina) 
 x1 + x2 ≤ 800 (mão-de-obra) 
 x1 ≤ 400 (procura de A) 
 x2 ≤ 700 (procura de B) 
 x1, x2 ≥ 0 
Passar o problema para a sua forma padrão : 
 Determinar xi ≥ 0 , i = 1,...,6 de modo a 
 Max 45 x1 + 30 x2 
 s. a 2 x1 + x2 + x3 = 1 000 
 x1 + x2 + x4 = 800 
 x1 + x5 = 400 
 x2 + x6 = 700 
 xi ≥ 0 , i = 1,...,6 
Método Simplex 
Algoritmo Primal Simplex (problema de maximização) 31 
Resolução do problema, utilizando o algoritmo Simplex : 
Passo inicial : 
 XB x1 x2 x3 x4 x5 x6 2º m. 
L1 − 2 L3 x3 2 1 1 0 0 0 1 000 1000/2 = 500
L2 − L3 x4 1 1 0 1 0 0 800 800/1 = 800
L3 Í x5 1 0 0 0 1 0 400 400/1 = 400
L4 x6 0 1 0 0 0 1 700 ( − ) 
L5 + 45 L3 zj − cj −45 −30 0 0 0 0 0 
 Ï 
1ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 2º m. 
L1 Í x3 0 1 1 0 −2 0 200 200/1 = 200
L2 − L1 x4 0 1 0 1 −1 0 400 400/1 = 400
L3 x1 1 0 0 0 1 0 400 ( − ) 
L4 − L1 x6 0 1 0 0 0 1 700 700/1 = 700
L5 + 30 L1 zj − cj 0 −30 0 0 45 0 18 000 
 Ï 
2ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 2º m. 
L1 + 2 L2 x2 0 1 1 0 −2 0 200 ( − ) 
L2 Í x4 0 0 −1 1 1 0 200 200/1 = 200
L3 − L2 x1 1 0 0 0 1 0 400 400/1 = 400
L4 − 2 L2 x6 0 0 −1 0 2 1 500 500/2 = 250
L5 + 15 L2 zj − cj 0 0 30 0 −15 0 24 000 
 Ï 
3ª Iteração: 
 XB x1 x2 x3 x4 x5 x6 2º m. 
 x2 0 1 −1 2 0 0 600 ← x2 (opt) 
 x5 0 0 −1 1 1 0 200 ← x5 (opt) 
 x1 1 0 1 −1 0 0 200 ← x1 (opt) 
 x6 0 0 1 −2 0 1 100 ← x6 (opt) 
 zj − cj 0 0 15 15 0 0 27 000 ← Zmax 
 Como os elementos da linha (zj − cj) são todos não negativos, a solução presente é óptima : 
 x* = (200, 600, 0, 0, 200, 100) com z* = 27 000. 
Método Simplex 
32 Técnica da base artificial 
4. Problemas com restrições ≤, = e ≥ 
 Considere-se um problema de PL, apresentando a seguinte forma : 
 Max C X 
 s. a A X ∇ b ∇ ∈ { ≤, =, ≥ } 
 X ≥ 0 
em que todas as componentes de b são não negativas. 
 Restrição ≤ ⇒ variável slack 
coeficiente 1 (coluna I) • 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
quando o valor de b excede o lado esquerdo 
coeficiente nulo na função objectivo 
corresponde à quantidade de recurso não consumido 
 Restrição ≥ ⇒ variável slack 
coeficiente −1 
quando o lado esquerdo excede o valor de b 
coeficiente nulo na função objectivo 
corresponde à quantidade de recurso consumido além do mínimo requerido 
 Restrições ≥ e = ⇒ variável artificial 
coeficiente 1 (coluna I) 
não pode aparecer na solução óptima 
coeficiente negativo muito elevado na função objectivo 
5. Técnica da base artificial 
 Como não existe qualquer variável que possa ser imediatamente tornada como básica, isto é, a 
matriz dos coeficientes A não contém uma submatriz identidade (b ≥ 0), é necessário introduzir 
algumas variáveis artificiais, tantas quanto as necessárias, para se conseguir arranjar um submatriz 
identidade de ordem m. 
 As variáveis artificiais, ao contrário das slacks, não têm significado de natureza económica, 
sendo apenas um mero artifício matemático  daí a designação de artificiais. 
 O objectivo consiste em anular as variáveis artificiais, pois só desta forma será possível a 
obtenção de uma solução do problema inicial. No entanto, qualquer solução do problema original é 
também solução do problema aumentado, com as variáveis artificiais a zero. O inverso também é 
verdade, desde que as variáveis artificiais valem zero. 
 Para conseguir tal objectivo, irão ser estudados 2 métodos diferentes, que são 2 variantes do 
método Simplex : método do M−Grande (Penalidades) e método das Duas−Fases. 
Método Simplex 
Técnica da base artificial 33 
5.1. Método do M−Grande (ou das Penalidades) 
 Neste método, as variáveis artificiais são “fortemente“ penalizadas na função objectivo, de 
modo a “provocar“ rapidamente o seu anulamento. O método Simplex, tenderá “naturalmente“ a 
eliminar da base as variáveis artificiais, como se pretende, dado que aquelas estão penalizadas com 
coeficientes arbitrariamente grandes : (−M) na maximização e (+M) na minimização. 
 Considere-se um problema de PL na forma padrão : 
 Maximizar Z = c1 x1 + … + cn xn 
 Sujeito a a11 x1 + … + a1n xn = b1 
 . . . 
 am1 x1 + … + amn xn = bm 
 xi ≥ 0, i = 1,…,n 
 Por aplicação do método do M-Grande, passa-se ao seguinte problema aumentado : 
 Maximizar Z = c1 x1 + … + cn xn – M xn+1 – … – M xn+m 
 Sujeito a a11 x1 + … + a1n xn + xn+1 = b1 
 . . . 
 am1 x1 + … + amn xn + xn+m = bm 
 xi ≥ 0, i = 1,…, n+m 
em que as variáveis xi (i = n+1, …, n+m) são artificiais e –M o coeficiente de penalização. 
 No entanto, os valores dos coeficientes de custo da função objectivo (linha de custo), associados 
às variáveis artificiais são não nulos (cj = −M, j é índice de variável artificial)  o que não pode 
acontecer, pois todos aqueles valores têm quer ser nulos. 
 Logo, é necessário determinar uma nova função objectivo, que seja equivalente à anterior, mas 
em que os coeficientes de custo das variáveis artificiais sejam nulos. Para tal, calcula-se a nova função 
objectivo, em função da anterior e das restrições onde existam as referidas variáveis. 
Exemplo : 
 Uma pequena empresa fabrica 3 tipos de kits electrónicos : A, B e C. O lucro unitário líquido de 
cada um é 5 (A), 10 (B) e 15 u.m. (C). O tempo disponível limita o número total de kits que podem ser 
fabricados, a 500. Estudos de mercado indicam que o total de kits tipos A e B deve ser pelo menos 
100. O total de kits tipo A deve exceder exactamente em 120 o total de kits tipos B e C. 
 Quantas unidades de A, B e C devem ser fabricadas de modo a maximizar o lucro ? 
Método Simplex 
34 Técnica da base artificial 
Formalização do problema : 
 x1 = quantidade de unidades do kit A 
 x2 = quantidade de unidades do kit B 
 x3 = quantidade de unidades do kit C 
 Max Z = 5 x1 + 10 x2 + 15 x3 (lucro) 
 s. a x1 + x2 + x3 ≤ 500 (capacidade) 
 x1 + x2 ≥ 100 (procura de A e B) 
 x1 − x2 − x3 = 120 (excedente de A) 
 x1, x2, x3 ≥ 0 
Passar o problema para a sua forma padrão : 
 Max Z = 5 x1 + 10 x2 + 15 x3 
 s. a x1 + x2 + x3 + x5 = 500 
 x1 + x2 − x4 = 100 
 x1 − x2 − x3 = 120 
 xi ≥ 0 , i = 1,...,5 
Como não é possível “arranjar“ uma matriz identidade, terão que ser introduzidas variáveis artificiais 
no problema. Desta forma, o problema passará a ter a seguinte forma : 
 Max Z = 5 x1 + 10 x2 + 15 x3 + 0 x4 + 0 x5 − M x6 − M x7 (M ≈ +∞) 
 s. a x1 + x2 + x3 + x5 = 500 
 x1 + x2 − x4 + x6 = 100 
 x1 − x2 − x3 + x7 = 120 
 xi ≥ 0 , i = 1,...,7 (x6, x7  variáveis artificiais) 
Aplicando o algoritmo Simplex a este problema, tem-se : 
Passo inicial : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
L1 − L2 x5 1 1 1 0 1 0 0 500 
L2 Í x6 1 1 0 −1 0 1 0 100 
L3 − L2 x7 1 −1 −1 0 0 0 1 120 
 (1) zj − cj −5 −10 −15 0 0 M M 0 
L4 + (2M+5) L2 (2) zj − cj −2M−5 −10 M−15 M 0 0 0 −220 M 
 Ï 
Método Simplex 
Técnica da base artificial 35 
(1) Como os valores de zj − cj (j = 6, 7) são não nulos (M) e x6 e x7 são variáveis básicas (portanto, para 
que se possa aplicar o algoritmo Simplex têm que ter zj − cj = 0, j = 6, 7), é necessário construir uma 
nova linha para zj − cj, o que se faz da seguinte forma : 
Linha 4 [ −5 −10 −15 0 0 M M 0 ]
Linha 2 (x6) −M [ 1 1 0 −1 0 1 0 100 ]
Linha 3 (x7) −M [ 1 −1 −1 0 0 0 1 120 ]
Nova linha 4 [ −2M−5 −10 M−15 M 0 0 0 −220 M ]
Desta forma, o primeiro quadro Simplex será o anterior, em que a linha zj − cj será a (2). 
1ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
L1 − L3 x5 0 0 1 1 1 −1 0 400 
L2 + L3 x1 1 1 0 −1 0 1 0 100 
L3 Í x7 0 −2 −1 1 0 −1 1 20 
L4 + (M+5) L2 zj − cj 0 2M−5 M−15 −M−5 0 2M+5 0 −20 M+500 
 Ï 
2ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
½ L1 Í x5 0 2 2 0 1 0 −1 380 
L2 + ½ L1 x1 1 −1 −1 0 0 0 1 120 
L3 + ½ L1 x4 0 −2 −1 1 0 −1 1 20 
L4 + 10 L1 zj − cj 0 −15 −20 0 0 M M+5 600 
 Ï 
3ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
 x3 0 1 1 0 0.5 0 −0.5 190 
 x1 1 0 0 0 0.5 0 0.5 310 
 x4 0 −1 0 1 0.5 −1 0.5 210 
 zj − cj 0 5 0 0 10 M M−5 4 400 
 Como todos os elementos da linha (zj − cj) são não negativos, então a solução presente é óptima : 
x* = (310, 0, 190, 210, 0, 0, 0) com z* = 4 400. 
 No quadro inicial as variáveis artificiais x6 e x7 são VB ⇒ R2 e R3 são violadas. 
 No 2º quadro a variável artificial x7 é VB ⇒ R3 é violada. 
 No 3º quadro a variável artificial x6 e x7 são VNB ⇒ Solução admissível. 
Método Simplex 
36 Técnica da base artificial 
5.2. Método das Duas-Fases 
 Nesta variante, o problema de PL é resolvido em duas fases distintas : na primeira, procura-se 
determinar se existem soluções admissíveis para o problema inicial e, caso existam, obtém-se uma 
SBA que será a solução de partida (inicial), da fase seguinte; a segunda, consiste simplesmente na 
aplicação do algoritmo do Simplex, tal como foi descrito inicialmente. 
 A 1ª fase consiste em remover da base todas as variáveis artificiais,de forma a obter uma SB 
apenas com variáveis não artificiais do problema. Para tal, resolve-se o seguinte problema de PL 
(problema auxiliar), começando com (X, Xa) = (0, b) como SBA : 
 Minimizar Z’ = ∑ Xa 
 Sujeito a A X = b 
 X ≥ 0 
em que Xa é o vector das variáveis artificiais e o objectivo consiste, nesta fase, em minimizar a sua 
soma (função objectivo artificial), quer o problema inicial seja de maximização quer seja de 
minimização. 
 Portanto, obtida uma solução para o problema auxiliar com as variáveis artificiais nulas, fica 
determinada a SBA de partida para o problema inicial. É evidente que uma solução nestas condições 
só se verifica com o valor da FO artificial igual a zero (Z’ = 0). 
 No entanto, outros situações podem acontecer. Portanto, no fim do 1ª fase, em que se atingiu a 
solução óptima do problema auxiliar, está-se numa das situações seguintes : 
i) z’ > 0  existe pelo menos uma variável artificial básica com valor estritamente positivo ⇒ o 
problema inicial é impossível (região admissível vazia); 
ii) z’ = 0 com todas as variáveis artificiais não básicas  a solução em presença é uma SBA de 
partida para o problema inicial ⇒ passar directamente à 2ª fase. 
iii) z’ = 0 com pelo menos uma variável artificial básica (nula)  a solução encontrada é uma 
solução admissível para o problema inicial. Se existir algum vector não artificial fora da base em 
condições de substituir um vector artificial procede-se à substituição, sendo a solução obtida 
degenerada; caso contrário, tira-se do quadro Simplex a linha respectiva (e a variável artificial 
associada). Em qualquer dos casos, após estas operações, passar à 2ª fase. 
 A 2ª fase consiste em considerar a solução obtida na fase anterior como primeira SBA, e aplicar 
o método Simplex normalmente até se atingir a solução óptima. Nesta fase, os vectores artificiais 
podem ser suprimidos dos respectivos quadros; no entanto, é vantajoso a sua manutenção, sem 
contudo questionar a sua possível reentrada na base. 
Método Simplex 
Técnica da base artificial 37 
Exemplo : 
Considere o seguinte problema de PL (minimização) : 
 Min Z = 3 x1 + 2 x2 
 s. a x1 ≤ 3 
 x2 ≤ 4 
 x1 + x2 ≤ 5 
 x1 + 5 x2 ≥ 5 
 5 x1 + 2 x2 ≥ 10 
 x1, x2 ≥ 0 
Este problema é equivalente ao seguinte problema de maximização : 
 Maximizar − Z = − 3 x1 − 2 x2 
 Sujeito a (x1, x2) ∈ X (mesmas restrições anteriores) 
Passar o problema para a sua forma padrão : 
 − Maximizar Z = − 3 x1 − 2 x2 
Sujeito a x1 + x5 = 3
 x2 + x6 = 4
 x1 + x2 + x7 = 5
 x1 + 5 x2 − x3 + x8 = 5
 5 x1 + 2 x2 − x4 + x9 = 10
 xi ≥ 0 , i = 1,...,9 (x8, x9  variáveis artificiais) 
1ª Fase : 
 Resolver o seguinte problema de PL auxiliar : 
 Minimizar Z’ = x8 + x9 
 sujeito a x ∈ X 
o qual é equivalente ao seguinte problema de maximização : 
 − Maximizar Z’ = − x8 − x9 
 sujeito a x ∈ X 
Método Simplex 
38 Técnica da base artificial 
Aplicando o algoritmo Simplex a este problema de maximização, tem-se : 
Passo inicial : 
 XB x1 x2 x3 x4 x5 x6 x7 x8 x9 2º m. 
L1 x5 1 0 0 0 1 0 0 0 0 3 
L2 − (1/5) L4 x6 0 1 0 0 0 1 0 0 0 4 
L3 − (1/5) L4 x7 1 1 0 0 0 0 1 0 0 5 
(1/5) L4 Í x8 1 5 −1 0 0 0 0 1 0 5 
L5 − (2/5) L4 x9 5 2 0 −1 0 0 0 0 1 10 
 (1) z’j − c’j 0 0 0 0 0 0 0 1 1 0 
L6 + (7/5) L4 (2) z’j − c’j −6 −7 1 1 0 0 0 0 0 −15 
 Ï 
(1) Como os valores de zj − cj (j = 8, 9) são não nulos (1), x8 e x9 são variáveis básicas (portanto, para 
que se possa aplicar o algoritmo Simplex têm que ter zj − cj = 0, j = 8, 9), é necessário construir uma 
nova linha para zj − cj, o que se faz da seguinte forma : 
Linha 6 [ 0 0 0 0 0 0 0 1 1 0 ]
Linha 4 (x8) − [ 1 5 0 0 0 0 0 1 0 5 ]
Linha 5 (x9) − [ 5 2 0 −1 0 0 0 0 1 10 ]
Nova linha 6 [ −6 −7 0 1 0 −1 0 0 0 −15 ]
Desta forma, o primeiro quadro Simplex será o anterior, em que a linha zj − cj será a (2). 
1ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 x7 x8 x9 2º m. 
L1 − (5/23) L5 x5 1 0 0 0 1 0 0 0 0 3 
L2 + (1/23) L5 x6 −1/5 0 1/5 0 0 1 0 −1/5 0 3 
L3 − (4/23) L5 x7 4/5 0 1/5 0 0 0 1 −1/5 0 4 
L4 − (1/23) L5 x2 1/5 1 −1/5 0 0 0 0 1/5 0 1 
(5/23) L5 Í x9 23/5 0 2/5 −1 0 0 0 −2/5 1 8 
L6 + L5 z’j − c’j −23/5 0 −2/5 1 0 0 0 7/5 0 −8 
 Ï 
2ª Iteração : 
 XB x1 x2 x3 x4 x5 x6 x7 x8 x9 2º m. 
 x5 0 0 −2/23 5/23 1 0 0 2/23 −5/23 29/23 
 x6 0 0 5/23 −1/23 0 1 0 −5/23 1/23 77/23 
 x7 0 0 3/23 4/23 0 0 1 −3/23 −4/23 60/23 
 x2 0 1 −5/23 1/23 0 0 0 5/23 −1/23 15/23 
 x1 1 0 2/23 −5/23 0 0 0 −2/23 5/23 40/23 
 z’j − c’j 0 0 0 0 0 0 0 1 1 0 
Método Simplex 
Técnica da base artificial 39 
 Como z’j − c’j ≥ 0, ∀j, a solução actual é óptima, para o problema auxiliar, que será a SBA de 
partida para o problema inicial. Esta solução é a seguinte : 
 

=
23
60,
23
77,
23
29,0,0,
23
15,
23
40*x e z’* = 0. 
2ª Fase : 
 Resolver o problema inicial utilizando o algoritmo Simplex, em que a SBA de partida é a 
solução óptima do problema auxiliar. 
 Portanto, retoma-se a função objectivo inicial, pelo que o 1º quadro desta fase apenas difere do 
último da 1ª fase no que diz respeito aos zj − cj. 
 Como x1 e x2 fazem parte da SBA de partida, então valores de zj − cj (j = 1, 2) têm de ser nulos, o 
que não acontece (c1 = −3 e c2 = −2). Para tal, é necessário alterar a linha que corresponde a estes 
valores, da seguinte forma : 
 XB x1 x2 x3 x4 x5 x6 x7 x8 x9 2º m. 
 x5 0 0 −2/23 5/23 1 0 0 2/23 −5/23 29/23 
 x6 0 0 5/23 −1/23 0 1 0 −5/23 1/23 77/23 
 x7 0 0 3/23 4/23 0 0 1 −3/23 −4/23 60/23 
 x2 0 1 −5/23 1/23 0 0 0 5/23 −1/23 15/23 
 x1 1 0 2/23 −5/23 0 0 0 −2/23 5/23 40/23 
 (1) zj − cj 3 2 0 0 0 0 0 0 0 0 
 (2) zj − cj 0 0 4/23 13/23 0 0 0 −4/24 −13/23 −150/23 
 ↑Zmax 
(1) Como os valores de zj − cj (j = 1, 2) são não nulos (3, 2), x1 e x2 são variáveis básicas (portanto, para 
que se possa aplicar o algoritmo Simplex têm que ter zj − cj = 0, j = 1, 2), é necessário construir uma 
nova linha para zj − cj, o que se faz da seguinte forma : 
(1) Linha 6 [ 3 2 0 0 0 0 0 0 0 0 ]
Linha 4 (x8) −2 [ 0 1 −5/23 1/23 0 0 0 5/23 −1/23 15/23 ]
Linha 5 (x9) −3 [ 1 0 2/23 −5/23 0 0 0 −2/23 5/23 40/23 ]
(2) Nova linha 6 [ 0 0 4/23 13/23 0 0 0 −4/23 −13/23 −150/23 ]
Desta forma, o primeiro quadro Simplex será o anterior, em que a linha zj − cj será a (2). 
 Como zj − cj ≥ 0, ∀ j, a solução associada ao quadro é óptima. Esta é a seguinte : 
 

=
23
60,
23
77,
23
29,0,0,
23
15,
23
40*x com ( )maxmin Z23
150 −==Z 
Método Simplex 
40 Problemas de minimização 
 Resolução gráfica do problema : 
 
6. Problemas de minimização 
 Até aqui, o método Simplex apenas tem sido aplicado a problemas que consistem na 
maximização das funções de custo. No entanto, este método também se pode aplicar a problemas de 
minimização. Para tal, não será necessário alterar o algoritmo Simplex, descrito anteriormente, 
podendo aquele ser aplicando a problemas de minimização, pois pode-se converter um problema 
daquele tipo num problema de maximização equivalente, da seguinte forma : 
 Minimizar Z = c1 x1 + c2 x2 + … + cn xn 
 Sujeito a (x1, x2, … , xn) ∈ X 
é equivalente a 
 − Maximizar Z = − c1 x1 − c2 x2 − … − cn xn 
 Sujeito a (x1, x2, … , xn) ∈ X 
Método Simplex 
Propriedades do quadro Simplex 41 
7. Interpretação económica das variáveis folga (“slack“) 
 Uma variável “slack“, corresponde à quantidade de recurso não consumido (com coeficiente 
+1), ou à quantidade de recurso consumido além do mínimo requerido (com coeficiente −1). 
 Considere-se a solução óptima encontrada para o exemplo descrito em (5.1) : 
 X* = (310, 0, 190, 210, 0) ⇒ Z* = 4 400 { b = (500, 100, 120) } 
Estes valores significam o seguinte : 
 x1 (quantidade do kitA produzida) = 310 
 x2 (quantidade do kit B produzida) = 0 
 x3 (quantidade do kit C produzida) = 190 
 x4 (quantidade de kits do tipo A e B produzidos, além do mínimo exigido) = 210 
 x5 (quantidade de horas que restam) = 120 
Por outro lado, 
 zj = c1 x1j + c2 x2j + . . . + cm xmj 
corresponde ao valor do rendimento que se deixa de ter pela activação unitária de cada uma das 
actividades excluídas  custo de oportunidade. 
 cj  rendimento directo. 
8. Propriedades do quadro Simplex 
• Cada quadro contém uma matriz identidade de ordem m (Im). 
• Todas as componentes de b são positivas ( 0≥b ). 
• zj − cj negativo ⇒ função objectivo pode ser melhorada. 
• Mesmo valor de zj − cj para diferentes j ⇒ qualquer um pode ser utilizado (heurística : escolher 
o de menor índice). 
• Existe zj − cj negativo mas apenas há elementos não positivos na coluna “pivot” ⇒ solução não 
limitada. Acontece, normalmente, quando o problema está mal formulado. 
• Variável artificial na solução óptima ⇒ solução inexistente (região admissível vazia). 
• Empate na escolha do elemento “pivot” ⇒ qualquer um pode ser usado (conduz a soluções 
degeneradas). 
• zj − cj nulo e xj é VNB ⇒ óptimos alternativos. Se xj entrar na base, obtém-se a solução 
alternativa (também PE admissível); portanto, qualquer solução resultante da combinação 
convexa daquelas soluções, será também solução óptima. 
Método Simplex 
42 Degenerescência e entrada em ciclo (Técnica da Perturbação) 
9. Degenerescência e entrada em ciclo (Técnica da Perturbação) 
 Como a quantidade de SBA de um problema de PL é finito, o algoritmo Simplex garante a 
convergência para a solução óptima, desde que o valor da FO vá sempre melhorando (em sentido 
estrito) em cada iteração  soluções não degeneradas. Desta forma, a solução óptima é atingida ao 
fim de um número finito de iterações, uma vez que cada SBA do problema aparecerá, quando muito, 
apenas uma vez ao longo do processo. 
 No entanto, pode acontecer que, ao passar-se de uma SBA para outra, esta tenha associado um 
valor da função objectivo igual ao da anterior, podendo esta situação manter-se no decurso de uma 
sucessão de iterações, e até mesmo acontecer que, após algumas iterações, estar-se perante uma SBA 
já anteriormente considerada. A aplicação do algoritmo Simplex, reproduzirá periodicamente as 
mesmas SB, mantendo-se constante o valor da FO, entrando-se em ciclo; nestas condições, a solução 
óptima nunca será atingida. 
 O algoritmo Simplex apenas entra em ciclo em situação de degenerescência. A degenerescência 
pode surgir logo na SBA inicial, ou após a ocorrência de empate no critério de saída, mesmo quando a 
SBA em presença é não degenerada. Neste caso, dado que existe melhoria da FO, apesar de existirem 
várias variáveis que podem sair da base, a nova SBA será degenerada. 
 Geralmente, a entrada em ciclo depende do tipo de SBA degenerada em presença; tal só é 
possível quando nesta existir mais do que uma variável básica nula. 
 Para casos destes, em que existe a possibilidade de entrada em ciclo, existem métodos que 
permitem eliminar a ambiguidade no critério de saída, mercê da determinação de uma única variável 
de entrada, sendo o que está em causa é a escolha correcta do vector a sair da base. Um desses 
métodos é a “Técnica da Perturbação”. 
Técnica da Perturbação. 
 Esta técnica consiste em formular um novo problema, sem degenerescência, em que o vector 
formado pelos segundos membros das restrições, são obtidos deslocando ligeiramente 
(“perturbando”) o mesmo vector do problema inicial. 
 Esta técnica consiste nos seguintes passos : 
Passo 1. Calcular 
 



 >= 0a,
a
bminx ik
ik
i
i
t 
Se tx é único, então o processo a seguir é o normal, de acordo com o processo descrito no 
algoritmo Simplex; neste caso não há lugar à técnica da perturbação. 
Método Simplex 
Degenerescência e entrada em ciclo (Técnica da Perturbação) 43 
 Se, pelo contrário, houver empate no critério de saída, isto é, 
 
qr
q
sr
s
ik
ik
i
i
t
a
b
a
b0a,
a
bminx ===



 >= L 
passa-se ao passo seguinte. 
Passo 2. Calcular 
 



 >= 0aa
amin ik
ik
1i
q,...,si
 
para i correspondente aos vectores empatados. Se o mínimo desta expressão for único, então a 
variável associada àquele valor sai da base, de acordo com o processo descrito. 
 Se, pelo contrário, o empate ainda persiste, isto é, 
 
qr
1q
sr
1s
ik
ik
1i
i a
a
a
a0a,
a
amin ===



 > L 
passa-se ao passo seguinte. 
Passo 3. Calcular 
 



 >= 0aa
amin ik
ik
2i
q,...,si
 
 para i correspondente aos vectores ainda empatados. 
Se o mínimo desta expressão for único, então a variável associada àquele valor sai da 
base, utilizando o mesmo processo. 
 Se, pelo contrário, o empate ainda persistir, repetir o processo com 
 m ..., 4,3, = j para0a,
a
a
min ik
ik
ij
i 




 > , 
havendo a garantia de existir desempate, pois j percorre o conjunto dos índices dos vectores x1, 
x2, ..., xm, e estes constituem uma matriz identidade. 
Exemplo : 
Considere-se o quadro seguinte, correspondente à resolução de um problema de maximização. 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
 x1 1 0 0 1/4 −8 −1 9 0 
 Í x2 0 1 0 1/2 −12 −1/2 3 0 
 x3 0 0 1 0 0 1 0 1 
 zj − cj 0 0 0 −3/4 20 −1/2 6 0 
 Ï 
 { }{ } 2,10,0min:i
2
1
0,
4
1
0min:iI0 ==











= { } 
Método Simplex 
44 Degenerescência e entrada em ciclo (Técnica da Perturbação) 
 Como I0 não é singular (situação de empate), então passar ao Passo 2. 
 { }{ } { } 11 xcoluna20,4min:i
2
1
0,
4
1
1min:i →==












=I 
 Como I1 é singular, então a variável que “sai na base” é a x2 (a 2ª na base). Logo, o quadro a 
passa a ter o seguinte aspecto : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
 x1 1 −1/2 0 0 −2 −3/4 15/2 0 
 x4 0 2 0 1 −24 −1 6 0 
 Í x3 0 0 1 0 0 1 0 1 
 zj − cj 0 3/2 0 0 2 −5/4 21/2 0 
 Ï 
 { }{ } { }31min:i
1
1min:i0 ==






=I 
 Como I0 é singular, então a variável que “sai na base” é a x3 (a 3ª na base). Logo, o quadro a 
passa a ter o seguinte aspecto : 
 XB x1 x2 x3 x4 x5 x6 x7 2º m. 
 x1 1 −1/2 3/4 0 −2 0 15/2 3/4 
 x4 0 2 1 1 −24 0 6 1 
 x6 0 0 1 0 0 1 0 1 
 zj − cj 0 3/2 5/4 0 2 0 21/2 5/4 
 Como zj − cj ≥ 0, ∀j, a solução actual é óptima. Esta solução é a seguinte : 
 
4
5*zcom0,1,0,1,0,0,
4
3*x =

= . 
 
Método Simplex 
	Método Simplex
	Soluções Básicas Admissíveis
	Método Simplex
	Algoritmo Primal Simplex \(problema de maximiza�
	Problemas com restrições \(, = e \(
	Técnica da base artificial
	Método do M\(Grande \(ou das Penalidades\)
	Método das Duas-Fases
	Problemas de minimização
	Interpretação económica das variáveis folga \�
	Propriedades do quadro Simplex
	Degenerescência e entrada em ciclo \(Técnica d�