unidade III

Prévia do material em texto

Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
35 
5. O Método Simplex 
 
O Método Simplex é um procedimento geral para resolver um PPL. 
Os modelos de programação linear para serem devidamente solucionados por intermédio do algoritmo 
simplex devem apresentar o seguinte formato: 
 a função objetivo de maximização; 
 todas as variáveis de decisão não negativas; 
 restrições de igualdade 
 termos independentes (constantes do lado direito) não-negativas 
Caso isso não aconteça, deve-se procurar um modelo equivalente que possua essas características, para 
então usar o simplex. 
 
5.1. Redução de um PPL à forma padrão 
Como já discutido na unidade 2, a redução de um PPL à forma padrão requer procedimentos bastante 
simples: 
 
aa)) FFOO ddee MMiinniimmiizzaaççããoo 
 
Basta multiplicar a FO original dada pela sua simétrica, passando a maximizar esta última, ou seja, 
Min { z(x) } = - Max { -z(x) } 
 
Ex.: 
 
 Min z = 3 x 1 - 4 x 2 + x 3 
 x1 + x2 + x3  10 
 sa 2 x1 + x2 - x3  20 
 x1  0, x2  0, x3  0 
 
 Max (- z ) = - 3 x 1 + 4 x 2 - x 3 
 x1 + x2 + x3  10 
 sa 2 x1 + x2 - x3  20 
 x1  0, x2  0, x3  0 
 
Resolvido o modelo equivalente, tem-se a solução do modelo original com a troca do sinal de z. 
 
bb)) TTrraannssffoorrmmaaççããoo ddee ddeessiigguuaallddaaddeess eemm iigguuaallddaaddeess 
 
Para a utilização do algoritmo simplex é necessário que todas as desigualdades do conjunto de restrições 
sejam transformadas em igualdade e que seja conhecida uma solução inicial viável, não negativa. 
 
 Variáveis de Folga e Excesso 
 
As variáveis de um problema são chamadas de variáveis de decisão, ou seja, são aquelas que se deseja 
estabelecer os valores, a fim de encontrar a solução ótima. 
 
Uma restrição linear da forma 
 
pode ser convertida em igualdade pela adição de uma nova variável não negativa ao lado esquerdo da 
desigualdade. Tal variável é numericamente igual à diferença entre os valores à direita e à esquerda da 
desigualdade e é conhecida como VARIÁVEL DE FOLGA. Ela representa o desperdício acarretado pela 
parte do sistema modelada pela restrição em pauta. 
 
 
ijij bxa 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
36 
Por sua vez, uma restrição linear da forma 
 
 
pode ser convertida em igualdade subtraindo-se do lado esquerdo da desigualdade uma nova variável, 
não negativa. Tal variável é numericamente igual à diferença entre os valores à esquerda e à direita da 
desigualdade e é conhecida como VARIÁVEL DE EXCESSO. Ela representa um excesso das variáveis 
de entrada nesta parte do sistema modelada pela restrição em pauta. 
 
cc)) OOccoorrrrêênncciiaa ddee bbii << 00 
 
Basta multiplicarmos a restrição i por (-1), pois os coeficientes aij podem ter qualquer sinal. 
 x1 + 3x2  - 7 bi negativo 
 - x1 - 3x2  7 bi positivo 
 
 
dd)) PPrroobblleemmaa ddaa VVaarriiáávveell LLiivvrree 
 
Entende-se por variável livre as variáveis sem qualquer restrição de sinal, isto é, que podem assumir 
valores positivos, negativos ou zero. Qualquer variável livre xj, pode ser substituída por um par de 
variáveis não negativas xj
' 
 0 e xj
'' 
 0, fazendo xj = xj
' 
 - xj
'' 
e deste modo formulando de novo o problema 
em função destas duas novas variáveis. 
 
Ex. 
 Max ( z ) = x 1 + 2 x 2 + x 3 
 x1 + x2 + x3  10 
 sa 2 x1 + 3 x2  20 
 x1  0, x2 livre, x3  0 
 
Fazendo x 2 = x’2 - x”2 , com x’ 2  0 e x” 2  0 e substituindo no modelo anterior, tem-se o modelo 
equivalente: 
 
 Max ( z ) = x 1 + 2 (x’ 2 - x” 2 )+ x 3 
 x1 + x’ 2 - x” 2 + x3  10 
 sa 2 x1 + 3 (x’ 2 - x” 2 )  20 
 x1  0, x’2  0 , x”2  0, x3  0 
 
 
Onde todas as variáveis são não negativas. A solução deste modelo resolve o anterior. 
 
 
5.2. Fundamentos teóricos 
 
Conforme visto, todo PPL pode ser reduzido à forma 
 
Max z = c
t
 x ( I ) 
 Ax = b ( II ) 
 x 0 ( III ) 
 
 
Seja A uma matriz n x m tal que o posto (A) = m (Esta suposição se justifica, pois se posto (A) = r < m 
teríamos equações redundantes que poderiam ser eliminadas). Um conjunto de m vetores coluna aj de A 
linearmente independentes denomina-se base associada a A ou simplesmente base (Não existe base de 
uma matriz, mas trata-se de uma imprecisão usual na terminologia). Os vetores aj que formam a base 
denominam-se vetores base de A. Seja o PPL formado por (I), (II) e (III). As m componentes de x 
correspondentes aos vetores base denominam-se variáveis básicas. As demais (n-m) componentes são 
as variáveis não básicas. 
ijij bxa 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
37 
 
Anulando-se as (n – m) variáveis não básicas, obtemos um sistema compatível e determinado e as 
variáveis restantes são obtidas da resolução do sistema de equações. 
 
EExxeemmpplloo:: 
 
Seja o sistema abaixo: 
x1 + x2 + 3x3 – x4 + x5 = 16 
x1 - 2x2 + 2x3 –x4 + 2x5 = -2 
 
Temos n= 5 e m = 2 
 
Cada solução básica terá 3 variáveis iguais a zero, por exemplo x3, x4 e x5 e as 2 demais obtidas da 
resolução do sistema, ou seja, x1 = 10 e x2 = 6. 
 
É importante destacarmos que modificando as variáveis as quais se atribui zero teremos diferentes 
soluções básicas. No total temos: 
!
!( )!
n n
m m n m
 
 
 
 
 
Pode-se provar que: 
 
Teorema 1: O conjunto S das soluções viáveis de um PPL é um conjunto convexo. 
 
Teorema 2: X é um vértice do conjunto S de soluções viáveis de um PPL se e somente se X for uma 
solução básica viável. 
 
Teorema 3: Se uma função objetivo possui um único ponto ótimo finito, então este é um ponto extremo do 
conjunto de soluções viáveis (S). 
 
Teorema 4: Se um modelo de PPL possui uma única solução ótima, então ela é uma solução básica do 
sistema de equações lineares formado pelas restrições do modelo, acrescidas das suas respectivas 
variáveis de folga. 
 
Teorema 5: Se um PPL possui mais de uma solução ótima, possuirá uma infinidade de soluções ótimas. 
 
Teorema 6: Se uma solução básica é melhor que suas adjacentes, então ela é uma solução ótima. 
 
 
5.3. Essência do Método Simplex 
 
Se o ótimo existe, pelo menos um vértice do polígono/poliedro de soluções é ótimo. O método simplex é 
baseado fundamentalmente nesta idéia. 
 
Partindo-se do vértice inicialmente fornecido – solução inicial viável, procura-se, nos vértices adjacentes a 
ele um que melhore a solução atual, ou seja, que ao serem testadas suas coordenadas na Função 
Objetivo a tornem melhor; 
 
Escolhido este vértice, procura-se, mais uma vez, entre os adjacentes a este novo vértice, um capaz de 
melhorar a solução anterior, testando-se, novamente, o valor deste vértice na Função Objetivo; 
 
O processo termina no momento em que não for possível encontrar, entre os vértices adjacentes ao 
último escolhido, um vértice cujas coordenadas sejam capazes de melhorar ainda mais a Função 
Objetivo; pois se um vértice é melhor do que todos os seus vizinhos, é o melhor, já que o conjunto de 
restrições é convexo. 
 
Para bem compreendermos as bases do funcionamento do algoritmo Simplex iremos trabalhar 
inicialmente com um modelo de PL onde todas as restrições do são do tipo  e os bi não-negativos, pois 
nestes casos teremos sempre uma base óbvia, formada pelas variáveis de folga. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
38 
 
Dado um modelo qualquer, oprimeiro passo é colocá-lo na Forma Padrão. Ao resolvermos manualmente 
o um PPL é conveniente utilizarmos a representação tabular do método simplex. O quadro é montado 
seguindo a seguinte orientação: 
 
 
 
 
 
 
 
 
 
 
 
 
 
EQ VB Xt B 
Z - Ct 
1 
A 
 
2 
3 
 
 
 
 
 
 
 
 
 
 
 
EQ – Equações 
 
Esta coluna 
exibirá a relação 
de todas as linhas 
existentes no 
modelo, iniciando 
pela Função 
Objetivo. 
VB – Variáveis 
Básicas 
 
Coluna onde 
serão exibidas as 
Variáveis Básicas 
de cada uma das 
restrições. 
Xt – Vetor Linha 
das Variáveis 
 
Nesta linha serão 
listadas todas as 
variáveis do 
problema na Forma 
Normal. 
B – Vetor Coluna dos 
Termos Independentes 
 
Nesta coluna serão exibidas 
as constantes, lado direito, de 
cada uma das linhas do 
problema, inclusive a da 
Função Objetivo. 
Ct – Vetor Linha dos 
Coeficientes da Função 
Objetivo 
 
Nesta linha serão listados 
todos os coeficientes das 
variáveis na Função Objetivo. 
A – Matriz dos Coeficientes das 
Restrições 
 
Em cada linha de A serão listados 
os coeficientes das variáveis de 
cada uma das restrições do 
problema. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
39 
 
5.3.1. Algoritmo Simplex (versão simplificada) 
 
Passo 1: Reduza o PPL à forma padrão; 
 
Passo 2: Construir quadro inicial (solução básica inicial); 
 
Neste caso a solução básica inicial é trivialmente determinada: as variáveis de decisão são variáveis não 
básicas e as de folga (todas as demais) são as variáveis básicas. 
 
Passo 3: Avaliar: existe coeficiente cj < 0? 
 
3.1 Sim. 
Escolha o coeficiente negativo de maior módulo na equação de z; a variável correspondente será a 
nova variável básica (determina a coluna de trabalho); 
 
 Divida os termos independentes de cada equação de restrição (coluna b) pelo elemento positivo 
correspondente, pertencente à coluna pivô. O que resultar menor quociente será o elemento pivô 
(caracteriza a linha de trabalho e a variável que sai da base); 
 
 O elemento pertencente à interseção entre a coluna e a linha de trabalho é designado como pivô; 
 
 Efetue operações elementares de modo que a coluna trabalho fique com a mesma configuração da 
coluna da variável que sai da base. Isto é: 
 (i) pivô deve ser 1 
 (ii) os demais elementos da coluna devem ser 0. 
 Volte para (3). 
 
3.2 Não. 
Fim, a solução é ótima. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
40 
5.3.2. Exemplos de Aplicação do Algoritmo Simplex 
 
EExxeemmpplloo 11:: 
 
Consideremos o problema dado no EExxeemmpplloo 11 de modelagem apresentado na Unidade 2, cujo modelo é: 
 
Max z = 3 x1 + 5 x2 
 
 x1  4 
 2x2  12 
 3x1 + 2x2  18 
 x1  0, x2  0 
 
Como as desigualdades das restrições são do tipo ≤, atingimos a forma padrão acrescentando-se as 
variáveis de folga: 
 
Max z = 3 x1 + 5 x2 
x1 + xf1 = 4 
 2x2 + xf2 = 12 
3x1 + 2x2 + xf3 = 18 
 
Para obtermos a solução inicial viável devemos atribuir o valor 0(zero) para as variáveis de decisão 
e calcular o valor das variáveis de folga, em cada linha de restrições: 
Se x1 = 0 e x2 = 0, tem-se: 
 xf1 = 4 
 xf2 = 12 
 xf3 = 18 
Assim, as variáveis básicas do primeiro quadro simplex são as variáveis de folga e as variáveis de 
decisão são não básicas. 
Finalmente, a equação da função objetivo deve ser escrita de forma similar às demais, ou seja, 
todas as variáveis do lado esquerdo da igualdade e apenas constantes no lado direito. Então, 
deve-se passar as variáveis para o lado esquerdo: 
 
z = 3x1 + 5x2 
 
z - 3x1 - 5x2 = 0 
x1 + xf1 = 4 
 2x2 + xf2 = 12 x1, x2, xf1, xf2, xf3 >=0 
3x1 + 2x2 + xf3 = 18 
 
Como todas as variáveis são não negativas, é só transpor os valores das variáveis para o quadro 
simplex: 
 
 EQ VB X1 X2 xf1 xf2 xf3 B 
 Z - -3 -5 0 0 0 0 
 1 xf1 1 0 1 0 0 4 
 2 xf2 0 2 0 1 0 12 
 3 xf3 3 2 0 0 1 18 
As variáveis básicas formam a matriz identidade no quadro simplex. 
 
Seguindo os passos do algoritmo, deve-se escolher a coluna de x2 como coluna de trabalho. A coluna de 
trabalho contém a variável que irá entrar na base no quadro seguinte. 
Ao dividir o elemento do termo independente (B), pelos elementos positivos da coluna de trabalho, o 
menor quociente, 6, indica a linha de trabalho, e a variável que deverá sair da base no quadro seguinte. 
O elemento da interseção da linha e da coluna de trabalho, 2, é o elemento pivô. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
41 
 
 Quadro 1 
EQ VB X1 X2 xf1 xf2 xf3 B 
Z - -3 -5 0 0 0 0 
1 xf1 1 0 1 0 0 4 L1 
2 xf2 0 2 0 1 0 12 12/2 = 6 L2 
3 xf3 3 2 0 0 1 18 18/2 = 9 L3 
 
A primeira operação a ser realizada no próximo quadro é dividir-se a linha de trabalho pelo elemento pivô, 
a fim de que este elemento se transforme em 1. Assim, a nova linha 2 (L´2) será: L´2 = L2 /2. 
 
 Quadro 2 
EQ VB X1 X2 xf1 xf2 xf3 B 
Z - -3 -5 0 0 0 0 Z´=Z + 5*L´2 
1 xf1 1 0 1 0 0 4 L´1 = L1 
2 xf2 0 1 0 1/2 0 6 L´2 = L2/2 
3 xf3 3 2 0 0 1 18 L´3=L3-2*L´2 
 
A partir daí, deve-se efetuar operações com as demais linhas, inclusive a da função objetivo, a fim de que 
seu valor se transforme em 0. Note-se que no exemplo o valor do elemento da linha 1 já é zero. Logo, 
nesta linha não será necessário efetuar quaisquer alterações, L´1 = L1. 
A nova linha 3, L´3, e a nova linha da FO, Z´, serão calculadas a partir das linhas anteriores. 
 
 Quadro 3 
EQ VB X1 X2 xf1 xf2 xf3 B 
Z - -3 0 0 2,5 0 30 
1 xf1 1 0 1 0 0 4 
2 X2 0 1 0 0,5 0 6 
3 xf3 3 0 0 -1 1 6 
 
Agora que se completou o pivoteamento, pode-se analisar a nova solução atingida: 
Xf1 = 4 
X2 = 6 xf2 = x1 = 0 
Xf3 = 6 
Z = 30 
Substituindo-se o valor das variáveis na função objetivo original deve-se encontrar o mesmo valor para Z. 
Assim, em Max Z = 3 x1 + 5 x2, ao substituir-se x2 = 6 e x1 = 0, encontramos: Z = 3*0+5*6 = 30, como era 
esperado. 
Note-se que agora a variável x2, que entrou na base, passou a formar com as outras básicas a matriz 
identidade. 
 
Como ainda há elemento negativo na linha da FO, -3, ainda não se atingiu o ponto ótimo. Deve-se aplicar 
novamente o mesmo procedimento, até que não haja mais elementos negativos na linha de Z. 
Agora, a coluna de trabalho será a da variável x1, nova variável a entrar na base no próximo quadro. A 
linha de trabalho será a 3ª. Então, o elemento pivô será o 3. 
 
 Quadro 4 
EQ VB X1 X2 xf1 xf2 xf3 B 
Z - -3 0 0 2,5 0 30 Z´´=Z´+3*L´´3 
1 xf1 1 0 1 0 0 4 L´´1=L´1-1*L´´3 
2 X2 0 1 0 0,5 0 6 L´´2=L´2 
3 xf3 1 0 0 -1/3 1/3 2 L´´3 = L´3/3 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
42 
 
Efetuando-se as operações indicadas, obtemos: 
 
EQ VB X1 X2 xf1 xf2 xf3 B 
Z - 0 0 0 1,5 1 36 
1 xf1 0 0 1 0,3333 -0,333 2 
2 X2 0 1 0 0,5 0 6 
3 X1 1 0 0 -0,333 0,3333 2 
 
Como não temos mais nenhum elemento negativo na linha da FO, atingimos o ponto ótimo. 
Z = 36 
X1 = 2 
X2 = 6 
Xf1 = 2 
Xf2 = xf3 = 0 
 
Ao comparar o resultado ao obtido através da resolução gráfica, verifica-se que a solução ótima é a 
mesma.EExxeemmpplloo 22:: 
Máx Z = 5x1 +2x2 (Função objetivo), para as seguintes restrições: 
x1  3 
x2  4 
x1 + 2x2  9 
Sempre em qualquer problema, temos x1 e x2  0 
 
Problema já resolvido graficamente, na unidade 2. 
 
 
Inicialmente transformemos o sistema de restrições em igualdades com introdução das variáveis de folga, 
ficando o sistema com a seguinte disposição: 
 
 x1 + x3 = 3 
 x2 + x4 = 4 
x1 + 2x2+ x5 = 9 
 
 Sendo as variáveis x3, x4 e x5, as variáveis de folga. 
 
Apliquemos o algoritmo SIMPLEX ao problema. Considerando o sistema já com a inclusão das variáveis 
de folga, temos: 
 
 x1 + x3 = 3 
 x2 + x4 = 4 
x1 + 2x2 + x5 = 9, sendo a função objetivo na forma, Z - 5x1 - 2x2 = 0 
 
Q1 x1 x2 x3 x4 x5 b 
Z -5 -2 0 0 0 0 
x3 1 0 1 0 0 3 3/1 = 3 Menor quociente, indicação da variável que sai 
da base (x3) 
x4 0 1 0 1 0 4 - 
x5 1 2 0 0 1 9 9/1 = 9 
 O elemento a11 = 1 é exatamente o PIVÔ 
 Coeficiente menor, indica a variável que entra na base (x1) 
 
 
O Novo quadro tem a seguinte disposição: 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
43 
Obtenção das linhas do quadro Q2: 
 
a11 = 1/1 = 1 a21 = 0 - 1x0 = 0 a31 = 1 - 1x1 = 0 c1 = -5 - 1(-5) = 0 
a12 = 0/1 = 0 a22 = 1 - 0x0 = 1 a32 = 2 - 0x1 = 2 c2 = -2 - 0(-5) = -2 
a13 = 1/1 = 1 a23 = 0 - 1x0 = 0 a33 = 0 - 1x1 = -1 c3 = 0 - 1(-5) = 5 
a14 = 0/1 = 0 a24 = 1 - 0x0 = 1 a34 = 0 - 0x1 = 0 c4 = 0 - 0(-5) = 0 
a15 = 0/1 = 0 a25 = 0 - 0x0 = 0 a35 = 1 - 0x1 = 1 c5 = 0 - 0(-5) = 0 
a16 = 3/1 = 3 a26 = 4 - 3x0 = 4 a36 = 9 - 3x1 = 6 c6 = 0 - 3(-5) = 15 
 
 
Q2 x1 x2 x3 x4 x5 b 
Z 0 -2 5 0 0 15 
x1 1 0 1 0 0 3 - Primeira linha obtida 
x4 0 1 0 1 0 4 4/1 = 4 
x5 0 2 -1 0 1 6 6/2 = 3 O menor quociente indica a variável que sai da 
base: x5 
 
 Pivô = a32 = 2 
 O menor coeficiente na linha Z indica a varíavel x2 que entra na base 
 
No quadro temos: x1 = 3 
 x2 = 0, por não aparecer na base 
 
 Com esses valores na função objetivo temos Z = 15, que é exatamente o valor de Z obtido 
do quadro Q2. 
 
Q3 x1 x2 x3 x4 x5 b 
Z 2 0 7 0 0 21 SOLUÇÃO ÓTIMA: todos Cjs  0 
x1 1 0 1 0 0 3 
x4 0 0 ½ 1 -1/2 1 
x2 0 1 -1/2 0 ½ 3 Primeira linha obtida 
 
O quadro Q3 é solução ótima porque todos os coeficientes da linha Z ou são nulos ou positivos (Cjs 
 0). Temos: x1 = 3 e x2 = 3. Como Zmáx = 5x1 + 2x2, concluímos que o maior valor para Z é 21. 
 
Solução: 
x1 = 3 
x2 = 3 
Zmáx = 21 
 
 
EExxeemmpplloo 33:: 
 
Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente 
cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para 
fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro 
unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede-se: o 
modelo do sistema de produção do sapateiro, se o objetivo é maximizar se lucro por hora. Resolver 
graficamente e pelo Método Simplex. 
 
EExxeemmpplloo 44:: 
 
Uma empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor qualidade, requer o dobro 
do tempo de fabricação em relação ao modelo M2. Se todos os cintos fossem do modelo M2, a empresa 
poderia produzir 1.000 unidades por dia. A disponibilidade de couro permite fabricar 800 cintos de ambos 
os modelos por dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para M1 e 
700 para M2. Os lucros unitários são 4,00 u.m. para M1 e 3,00 u.m. para M2. Qual o programa ótimo de 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
44 
produção que maximiza o lucro total diário da empresa? Resolver o modelo do sistema descrito 
graficamente e pelo Método Simplex. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
45 
5.4. Método das Duas Fases 
5.4.1. Geração de Solução Inicial Viável 
 
Depois de transformadas todas as restrições lineares (com valores não negativos nos termos 
independentes) em igualdades, pela introdução das variáveis de folga e de excesso, onde for necessário, 
adiciona-se uma nova variável chamada variável artificial, no lado esquerdo de todas as restrições que 
não contenham uma variável de folga, a fim de formar uma base inicial imediata. 
 
Em conseqüência, todas as equações representando restrições, ou conterão variáveis de folga ou 
variáveis artificiais. Obtém-se uma solução inicial não negativa para este novo conjunto de restrições, 
fazendo-se cada variável de folga e cada variável artificial (básicas) igual ao valor do lado direito da 
equação, na qual a variável em questão aparece e igualando-se a zero todas as outras variáveis, inclusive 
as variáveis de excesso (não básicas). 
 
Em resumo, 
 Quando houver restrição do tipo MENOR OU IGUAL () a variável de folga introduzida servirá 
para base: 
 3x1 + x2  5 desigualdade 
 3x1 + x2 + xf1 = 5 igualdade 
 sempre x1, x2 e xf1  0 
xf1 será a variável básica desta linha. 
 
 Se a restrição for do tipo MAIOR OU IGUAL (), com bi positivo, introduz-se uma variável de 
excesso e uma variável artificial: 
 
 x1 + 3x2  5 desigualdade 
 x1 + 3x2 - Xe1 + xa1 = 5 igualdade 
 variável de artificial 
 variável de excesso 
 
 Da mesma forma, x1, x2, xe1 e xa1  0 
 
 Se a restrição for do tipo IGUAL ( = ), com bi positivo, introduz-se uma variável artificial: 
 2x1 + 7x2 = 10 
 2x1 + 7x2 + xa1 = 10 igualdade com variável artificial 
 
 Sendo, x1, x2 e xa1  0 
 
Tanto no caso de restrição do tipo , quanto de igualdade, a introdução da variável artificial é importante a 
fim de formar uma base inicial para o problema. 
 
a) A introdução de varáveis artificiais sempre implica no surgimento da FUNÇÃO OBJETIVO 
ARTIFICIAL, sendo o problema resolvido em duas fases. 
b) O quadro estruturado mostra explicitamente uma solução básica inicial. As variáveis básicas formam, 
com seus coeficientes, uma matriz identidade. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
46 
5.4.2. Exemplos de Aplicação do Algoritmo Simplex – Método das Duas Fases 
 
EExxeemmpplloo 11:: 
 
Consideremos o PPL: 
 
Máx Z = 5x1 + 2x2 
 x1  3 
 x2  4 
 x1 + 2x2  9 
-x1 + 3x2  3 
 x1 + 3x2  6 
 x1 e x2  0 
 
Como o exemplo também envolve restrições do tipo , caracteriza um problema de duas fases. Além das 
varáveis de folga, introduziremos também variáveis de excesso, artificiais e uma função objetivo artificial. 
 
Façamos a introdução das variáveis de folga, excesso e artificiais: 
 
Z – 5X1 – 2X2 = 0 
X1 + X3 = 3 
X2 + X4 = 4 
X2 + 2X2 + X5 = 9 
-X1 + 3X2 –X6 + X8 = 3 
X1 + 3X2 –X7 + X9 = 6 
 
Como as variáveis artificiais trazem um “custo” para as restrições em que são inseridas, precisam ter valor 
zero ao final do processo, pois, caso contrário, alterariam o valor das igualdades propostas. 
Assim, sempre que utilizarmos o Método das Duas Fases introduziremos a Função: 
 
Min W = 
 rtificiaisVariáveisA
 
 
Como as variáveis artificiais são básicas no 1º Quadro, é preciso efetuar-se uma alteração, a fim de 
garantir que elas formem a matriz identidade. A montagem da Função Objetivo Artificial é feita, utilizando-
se as restrições que possuem variáveis artificiais. Logo, 
 
Min W = X8 + X9 
Max (-W) = - X8 – X9 
 
-W + X8 + X9 = 0 
 
Subtrai-se desta equaçãoas equações que possuem variáveis artificiais, a fim de eliminá-las da equação 
da Função Objetivo Artificial: 
 
-W + X8 + X9 = 0 
-(-X1 + 3X2 –X6 + X8 = 3 
-( X1 + 3X2 –X7 + X9 = 6 
 
-W – 6 X2 + X6 + X7 = - 9 
 
A partir daí, podemos montar o quadro inicial e desenvolver o algoritmo: 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
47 
2ª FASE 
 
 
 
Q1 
X1 X2 X3 X4 X5 X6 X7 X8 X9 b Detalhes 
-W 0 -6 0 0 0 1 1 0 0 -9 
Z -5 -2 0 0 0 0 0 0 0 0 
X3 1 0 1 0 0 0 0 0 0 3 - 
X4 0 1 0 1 0 0 0 0 0 4 4/1=4 
X5 1 2 0 0 1 0 0 0 0 9 9/2=4,5 
X8 -1 3 0 0 0 -1 0 1 0 3 3/3=1 (X8, variável que sai da base) 
X9 1 3 0 0 0 0 -1 0 1 6 6/3=2 
 
Detalhes: 
 
a) A variável X2 é a que entra na base pelo fato de corresponder na linha –W ao menor coeficiente (-
6), não levando em consideração a coluna “b”. 
b) A variável X8 sai da base para ser substituída por X2 pelo fato de ter a menor divisão bi/aij (menor 
quociente positivo). 
 
 
 
Q2 X1 X2 X3 X4 X5 X6 X7 X8 X9 b Detalhes 
-W -2 0 0 0 0 1- 1 2 0 -3 
Z -17/3 0 0 0 0 -2/3 0 2/3 0 2 
X3 1 0 1 0 0 0 0 0 0 3 3/1=3 
X4 1/3 0 0 1 0 1/3 0 -1/3 0 3 3:1/3=9 
X5 5/3 0 0 0 1 2/3 0 -2/3 0 7 7:5/3=21/5=4,2 
X2 -1/3 1 0 0 0 -1/3 0 1/3 0 1 - 
X9 2 0 0 0 0 1 -1 -1 1 3 3/2=1,5 (Variável que sai da base). 
 
 
Seguindo a seqüência algorítmica temos os quadros seguintes: 
 
 
Q3 X1 X2 X3 X4 X5 X6 X7 X8 X9 b 
-W 0 0 0 0 0 0 0 1 1 0 
Z 0 0 0 0 0 13/6 -17/6 -13/6 17/6 21/2 
X3 0 0 1 0 0 -1/2 ½ ½ -1/2 3/2 
X4 0 0 0 1 0 1/6 1/6 -1/6 -1/6 5/2 
X5 0 0 0 0 1 -1/6 5/6 116 -5/6 9/2 
X2 0 1 0 0 0 -1/6 -1/6 1/6 1/6 3/2 
X1 1 0 0 0 0 ½ -1/2 -1/2 ½ 3/2 
 
 
1. No quadro acima todos os coeficientes da FUNÇÃO OBJETIVO ARTIFICIAL são maiores ou 
iguais a zero, fim da 2ª FASE. 
 
2. Para dar continuidade à FASE 1, deve-se excluir a linha da função objetivo artificial e as colunas 
das variáveis artificiais. 
 
Variável que entra na base 
Variável que entra na BASE 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
48 
1ª FASE 
 
 
Q4 X1 X2 X3 X4 X5 X6 X7 b 
Z 0 0 17/3 0 0 -2/3 0 19 
X7 0 0 2 0 0 -1 1 3 
X4 0 0 -1/3 1 0 1/3 0 2 
X5 0 0 -5/3 0 1 2/3 0 2 
 X2 0 1 1/3 0 0 -1/3 0 2 
X1 1 0 1 0 0 0 0 3 
 
 
A solução do quadro abaixo é ótima, já que todos os coeficientes na linha “Z” (função objetivos) são  0 
(Todos Cjs  0). 
 
Q5 X1 X2 X3 X4 X5 X6 X7 b 
Z 0 0 4 0 1 0 0 21 
X7 0 0 -1/2 0 3/2 0 1 6 
X4 0 0 ½ 1 -1/2 0 0 1 
X6 0 0 -5/2 0 3/2 1 0 3 
X2 0 1 -1/2 0 ½ 0 0 3 
X1 1 0 1 0 0 0 0 3 
 
 
Como solução da questão, temos: 
 
X1 = 3 
X2 = 3 
X4 = 1 
X6 = 3 
X7 = 6 
X3 = X5 = 0 
Zmáx = 21 
 
 
 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
49 
5.5. Análise de Soluções 
 
Ao analisar o quadro final de um Problema de Programação Linear pode-se avaliar o tipo de solução 
obtida. 
 
 
a) Problema de Degeneração 
 
No desenvolvimento do Simplex, a linha pivô é a restrição que apresenta o menor quociente não negativo, 
na divisão dos termos independentes pelos coeficientes positivos da variável que entra, coluna de 
trabalho. 
 
Pode ocorrer que haja mais de um resultado nessa condição. Deve-se escolher arbitrariamente um deles 
para calcular a solução. Entretanto, essa solução apresentará pelo menos uma variável básica com valor 
nulo. A saída de uma variável básica com valor zero provoca o aparecimento de outra variável básica na 
solução seguinte também com valor zero, sem alteração do valor objetivo. 
 
Neste caso, a solução é chamada degenerada. Se os coeficientes da função objetivo retornam não 
negativos em alguma iteração, o caso não apresenta dificuldade. O problema aparece quando as 
iterações levam a ciclos, sem caracterizar a solução ótima. Embora o caso seja muito raro, há maneiras 
de solucioná-lo. 
 
 
b) Problema da Solução Ilimitada 
 
Isto ocorre quando a variável que entra na base não possui em sua coluna nenhum coeficiente positivo. 
Os programas de computador, neste caso, apresentam a última solução básica antes que a solução se 
torne ilimitada. 
 
 
c) Soluções Múltiplas 
 
Se na solução ótima o coeficiente de uma variável não básica é zero, ele poderá entrar na base sem 
alterar o valor do objetivo, gerando outra solução ótima. Neste caso, qualquer combinação linear dessas 
duas soluções também será solução ótima. 
 
 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
50 
 
5.6. Ferramenta SOLVER 
 
SOLVER é uma ferramenta do EXCEL, cuja instalação não se dá automaticamente. 
Para instalá-la é necessário optar pela Instalação PERSONALIZADA, e marcar a opção SOLVER. 
A seguir seguem os passos a serem seguidos para a sua utilização: 
 
1º-Ao entrar no EXCEL,digite os parâmetros do modelo a ser resolvido em qualquer célula, a sua escolha. 
 
Por exemplo, para o modelo: 
Max Z = X1 + 3X2 + 4X3 
S. a 
 X1+X2+ X3 <= 5 
 2X1+ 4X3 >= 8 
5X1+2X2 = 10 
 X1, X2, X3>= 0 
tem-se: 
 
 E F G H 
 
10 X1 X2 X3 
11 
12 
13 
14 Z 
15 Restrição1 
16 Restrição2 
17 Restrição3 
18 
19 
20 
 
Escolhe-se uma célula para começar, no caso, F10. Assim, na linha 10 células F, G e H coloca-se uma 
legenda com as variáveis do problema (x1, x2 e x3). 
Resolver um PPL é encontrar os valores das variáveis do problema que otimizam a Função Objetivo. 
Então, ao ser resolvido o problema, nas células F11, G11 e H11 aparecerão os valores ótimos das 
variáveis x1, x2 e x3, respectivamente. 
 
A seguir é preciso escolher um local para introduzir as funções do PPL, no caso, a função objetivo e as 
três restrições do problema (F14, F15, F16 e F17). 
 
 E F G H 
 
10 X1 X2 X3 
11 
12 
13 Z =F11+3*G11+4*H11 <= 5 
14 Restrição1 =F11+G11+H11 >= 8 
15 Restrição2 =2*F11+4*H11 = 10 
16 Restrição3 =5*F11+2*G11 
17 
18 
19 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
51 
Digita-se, então, na célula escolhida a cada uma das equações, utilizando-se a célula escolhida como 
referência para a variável do problema. 
No caso, no lugar de x1 deve ser digitado (ou selecionada a célula) F11, G11 no lugar de x2 e H11 no 
lugar de x3. 
Para facilitar a entrada de dados, na célula ao lado, pode-se digitar o sentido da otimização e, na 
seguinte, os valores das limitações do PPL. 
 
2º Ao terminar a digitação de todos os parâmetros, escolha, no MENU Ferramentas, a opção SOLVER. 
 
Será, então apresentada a janela a seguir: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3º- Definir célula de destino escolhe-se a função digitada para a função objetivo, no caso, basta 
selecionar a célula F13, que contém o valor de Z. 
 
4º- Igual a: Opta-se por Max para funções de maximização e Mín para minimização. 
 
5º- Células variáveis: As células variáveis são as variáveis do problema. Deve-se então selecionar as 
células escolhidas para representa-las. No caso, basta clicar na célula F11 e arrastar até G11, 
selecionando X1 até X3. 
 
6º- Em Submeter às restrições: Essa opção serve para introduzir as restrições do PPL.Seleciona-se o 
botão Adicionar e surgirá a seguinte janela: 
 
 
 
 
 
 
 
 
 
 
Em Referência da célula: Deverão ser introduzidas, uma a uma, as equações das restrições, no caso, 
células F14, F15 e F16. Escolhe-se, então o sentido da otimização, <=, >=, =; e, finalmente,em Restrição 
introduz-se a constante do lado direito, que pode ser selecionada (H13, H14, H15), ou digitada. 
 
Finalmente deve-se informar as variáveis não negativas, informando, ainda nesta opção, as que forem >= 
0. 
 
7º Seleciona-se o botão Resolver. 
 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
52 
 
Uma vez resolvido o PPL, aparecerão os resultados desejados: 
 
 
 
 
 
 
 
 
 
 X1 X2 X3 
 1 2.5 1.5 
 
 Z 14.5 
 Restrição1 5 <= 5 
 Restrição2 8 >= 8 
 Restrição3 10 = 10 
 
 
 
 
 
 
 
 
 
 
 
 
Ou seja, a solução ótima para o modelo é: 
 
X1 = 1 
X2 = 2,5 
X3 = 1,5 
Z = 14,5. 
 
 
X1, X2 e X3 
inicialmente em 
branco. 
Preencher com 
a função Z = 
X1 + 3X2 + 
4X3 
Inserir as 
restrições: 
X1+X2+X3 
2X1+4X3 
5X1+2X2 
Limites das restrições. 
(Constantes do lado 
direito) 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
53 
 
 
ANEXO 1 – OUTRA APRESENTAÇÃO DO ALGORITMO SIMPLEX 
 
 
 
PASSO 1 - Verificar se os coeficientes Cjs da função objetivo Z são maiores ou iguais a zero, caso 
afirmativo, pare, a solução é ótima. Caso contrário, escolha a variável que tem o menor 
coeficiente Cj (Cs) para entrar na base. 
 
Cs = min (Cjs) 
Xs = variável que entra na base 
 
PASSO 2 - Verificar os coeficientes ais da variável xs que vai entrar na base. Se todos ais forem menores 
ou iguais a zero, pare, Z = infinito. Caso contrário, divida cada bi pelo respectivo ais > 0. O 
menor quociente bi/ais, ais > 0, indica a variável de índice r que sai da base. 
 
PASSO 3 - Calcular os novos coeficientes do quadro (operação de pivoteamento) para que a troca de 
variáveis na base se processe. Os novos coeficientes serão: 
 
ars = pivô 
 
nova linha r = (linha r anterior)/ars 
nova linha i i = r = (linha anterior) - (nova linha r) . ais 
 
PASSO 4 - Voltar ao PASSO 1. 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
54 
 
ANEXO 2 - ALGORÍTMO SIMPLEX COMPLETO INCLUINDO DUAS FASES 
 
 
 
OBSERVAÇÕES: 
a) Os d j s são os coeficientes das variáveis na função objetivo artif icial. 
b) Na fase 1 se operam com todos os coeficientes, inclusive os da linha Z, na operação de 
pivoteamento. 
c) Quando W = 0 e d j s  0, pode-se abandonar a l inha W e as colunas das variáveis 
artif iciais. 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
55 
ANEXO 3 - Algoritmo Simplex 
 
 
Passo 1: Inclui-se no quadro simplex, a linha da Função Objetivo Artificial, que passa a ser a 
primeira linha. 
 
Passo 2: Localize o número mais negativo da primeira linha do quadro simplex (Função 
Objetivo Artificial), excluída a última coluna (B); e chame a coluna em que este número 
aparece de coluna de trabalho. Se existir mais de um candidato a número mais negativo, 
escolha um. 
 
Passo 3: Forme quocientes da divisão do elemento da última coluna (B), pelo elemento da linha 
correspondente à coluna de trabalho (excluindo-se a primeira linha). Designe por PIVÔ o 
elemento da coluna de trabalho que conduz ao menor quociente. Se mais de um 
elemento conduzir ao mesmo menor quociente, escolha um. Se nenhum elemento da 
coluna de trabalho for positivo, o problema não terá solução. 
 
Passo 4: Use operações elementares sobre as linhas, a fim de converter o elemento pivô em 1 e, 
em seguida, reduzir a zero todos os outros elementos da coluna de trabalho. 
 
Passo 5: Substitua a variável x existente na linha pivô e primeira coluna (Variáveis Básicas), pela 
variável x da primeira linha (Lista de Variáveis) e coluna pivô. Esta nova primeira coluna 
é o novo conjunto de variáveis básicas. 
 
Passo 6: Repita os passos de 2 a 5 até a inexistência de números negativos na primeira linha, 
excluindo-se dessa apreciação a última coluna. 
 
 
Passo 7: Sempre que uma variável artificial deixa de ser básica, isto é, é removida da primeira 
coluna do quadro (Variáveis Básicas), como resultado do passo 4, ela será retirada da 
linha superior do quadro, bem como toda a coluna sob a variável em questão. 
Esta modificação simplifica os cálculos realizados manualmente, mas não é implementada 
em muitos programas computacionais. 
 
Passo 8: A primeira linha do quadro (Função Objetivo Artificial) pode ser eliminada sempre que 
constituída unicamente de zeros. 
 
Passo 9: Fase 2: Agora os passos 2, 3, 4 e 5 são aplicados aos elementos da ‘nova’ primeira linha 
(Função Objetivo). 
 
Passo 10: A solução ótima é obtida atribuindo-se a cada variável da primeira coluna o valor da linha 
correspondente, na última coluna. Às demais variáveis é atribuído o valor zero. O valor 
ótimo da Função Objetivo, associado a z, é o número resultante na primeira linha, última 
coluna, nos problemas de maximização, ou o negativo dele, nos problemas de 
minimização. 
 
Passo 11: Se variáveis artificiais não nulas estiverem presentes na solução final como variáveis 
básicas, então o problema não admitirá solução. 
Em contraste, podem aparecer variáveis artificiais nulas como variáveis básicas, na 
solução final, quando houver redundância de uma ou mais das equações originais de 
restrição. 
 
Métodos Quantitativos Aplicados 
Capítulo 5: Método Simplex 
Profª Márcia Machado. 
56 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
 
LACHTERMACHER, Gerson, Pesquisa Operacional na Tomada de Decisão, Rio de Janeiro, ed. Campus, 
2002. 
 
GOLDBARG, Marcos. C., LUNA, Henrique Pacca, Otimização Combinatória e Programação Linear, Rio 
de Janeiro, ed. Campus, 2000. 
 
ANDRADE, Eduardo Leopoldino, Introdução à Pesquisa Operacional, Ed. LTC, Rio de Janeiro, 2000. 
 
SILVA, Ermes Medeiros .et al., Pesquisa Operacional, Ed. Atlas, São Paulo, 1998. 
 
BREGALDA, Paulo. F., OLIVEIRA, Antônio. A., BORNSTEIN, Cláudio, Introdução à Programação Linear, 
Rio de Janeiro, ed. Campus, 1988. 
 
PUCCINI, Abelardo, Introdução à Programação Linear, São Paulo,ed. LTC, 1983. 
 
HAMACHER, Silvio, LUSTOSA, Leonardo., Sistemas de Modelagem: Evolução e Perspectivas, 
Proceedings of the IX CLAIO , Buenos Aires,1998. 
 
HILLIER, F. S., LIEBERMAN, G.J., Introdução à Pesquisa Operacional, Rio de Janeiro, ed Campus, 
1988. 
 
NEMHAUSER, L. G., Integer and Combinatorial Optimization, Wolsey Wiley-Interscience, 1999. 
 
TAHA, H., Operations Research : an introduction, Prentice Hall, 1996. 
 
WILLIAMS, H. P., Model Building in Mathematical Programming, John Wiley & Sons, 1999.