Método Simplex

Prévia do material em texto

Aula 5 – Método Simplex 
Objetivos: 
Ao final desta aula, o estudante será capaz de: 
1. Encontrar a solução ótima de qualquer PPL aplicando os passos do algoritmo Simplex. 
 
1. Introdução 
Na Aula passada, o conceito de solução básica foi apresentado e foi mostrado que a solução ótima 
de um modelo PL está associada a uma solução do mesmo tipo. Vimos ainda que um modelo PL 
não ilimitado pode ser resolvido através do método de enumeração de soluções básicas viáveis. 
No entanto, tal método não é computacionalmente eficiente. Nesta aula, apresentamos os passos 
do método Simplex, que percorre iterativamente soluções básicas viáveis do modelo até que se 
tenha a garantia de que a solução ótima foi encontrada. O método permite ainda identificar se o 
modelo é ilimitado ou possui múltiplas soluções ótimas. 
2. Método Simplex básico 
O método Simplex apresentado nesta aula aplica-se a modelos PL que podem ser escritos da 
seguinte maneira: 
max max 𝑐𝑇𝑥 
s.a s.a. 𝐴𝑥 ≤ 𝑏 
𝑥 ≥ 0 
Com a condição ainda de que 𝒃 ≥ 𝟎. Caso o modelo trabalhado não possa ser convertido para este 
formato, deve-se então ser aplicado o método Simplex duas fases, que será explicado com maiores 
detalhes em aulas posteriores. 
O método Simplex consiste nos seguintes passos: 
Passo 1: Colocar o modelo na forma padrão. 
Passo 2: Obtenção da solução básica viável inicial. 
Passo 3: Verificar se a solução básica viável atual é ótima. Se sim, o algoritmo termina. Se não, 
vá para o Passo 4. 
Passo 4: Encontrar uma nova solução básica viável, decidindo qual variável entra na base (passa 
a ser básica) e qual variável sai da base (passa a ser não básica). Volte para o Passo 3. 
Agora, os passos prévios são detalhados com base no modelo genérico: 
max max 𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛𝑥𝑛 
s.a s.a. 
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ⋯ + 𝑎2𝑛𝑥𝑛 ≤ 𝑏2
⋮
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ⋯ + 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0
 
 
Assume-se aqui que 𝑏1, 𝑏2, … , 𝑏𝑚 são não negativos. 
Passo 1: Colocar o modelo na forma padrão. 
O primeiro passo é a conversão do modelo para o formato padrão. Assim, deve-se apenas 
transformar as restrições de ≤ em restrições de igualdade. Adiciona-se então uma variável de folga 
não negativa em cada uma destas restrições: 
max max 𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛𝑥𝑛 
s.a s.a.: 
𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛𝑥𝑛 + 𝑅1 = 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ⋯ + 𝑎2𝑛𝑥𝑛 + 𝑅2 = 𝑏2
⋮
𝑎𝑚1𝑥11 + 𝑎𝑚2𝑥12 + ⋯ + 𝑎𝑚𝑛𝑥1𝑛 + 𝑅𝑚 = 𝑏𝑚
 𝑥1, 𝑥2, … , 𝑥𝑛, 𝑅1, 𝑅2, … , 𝑅𝑚 ≥ 0
 
Passo 2: Obtenção da solução básica viável inicial. 
A solução básica inicial usada no método Simplex é destacada na seguinte tabela: 
Solução básica inicial 
Variáveis básicas 
(base) 
Variáveis não básicas 
 (zeradas) 
𝑅1, 𝑅2, … , 𝑅𝑚 𝑥1, 𝑥2, … , 𝑥𝑛 
 
Ainda no segundo passo, deve-se montar o chamado dicionário. Um dicionário é um conjunto de 
equações com as seguintes características: 
● 1 linha para cada variável básica em que esta variável é escrita matematicamente em função 
das variáveis não básicas. 
● Uma última linha com a função objetivo 𝑧 que também é escrita matematicamente em 
função das variáveis não básicas. 
 
O dicionário para a solução básica inicial é: 
𝑅1 = 𝑏1 − 𝑎11𝑥1 − 𝑎12𝑥2 − ⋯ − 𝑎1𝑛𝑥𝑛
⋮
𝑅𝑚 = 𝑏𝑚 − 𝑎𝑚1𝑥1 − 𝑎𝑚2𝑥2 − ⋯ − 𝑎𝑚𝑛𝑥𝑛
 
𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯ + 𝑐𝑛𝑥𝑛 
 
Um dicionário sempre mostra uma solução viável para o problema. Como as variáveis não básicas 
por definição assumem valor zero, o valor de cada variável básica vai ser a constante do lado 
direito da sua linha e o valor da função objetivo é a constante da linha 𝑧. 
No dicionário da solução inicial, tem-se 𝑅1 = 𝑏1, 𝑅2 = 𝑏2, … , 𝑅𝑚 = 𝑏𝑚, enquanto todas as 
variáveis 𝑥 assumem valor nulo, o que gera uma função objetivo com valor 𝑧 = 0. 
Passo 3: Verificar se a solução básica viável atual é ótima. Se sim, o algoritmo termina. Se não, 
vá para o Passo 4. 
O passo que é explicado agora serve para qualquer dicionário e não só para o dicionário inicial 
criado. Faz-se necessário saber agora se o dicionário atual está associado a uma solução ótima ou 
não. 
Se existir alguma variável não básica com coeficiente positivo na linha 𝑧 então a solução atual não 
é ótima e então deve-se ir para o Passo 4. Caso contrário, a solução atual é ótima e o algoritmo 
termina. 
Passo 4: Encontrar uma nova solução básica viável, decidindo qual variável entra na base (passa 
a ser básica) e qual variável sai da base (passa a ser não básica). Volte para o Passo 3. 
Nesta etapa, é escolhida arbitrariamente uma variável não básica com coeficiente positivo na linha 
𝑧 para entrar na base. Em seguida, deve-se identificar qual variável sai da base. Tal identificação 
é feita calculando-se qual o maior valor possível que a variável não básica escolhida para entrar 
pode assumir sem que alguma variável atualmente básica fique negativa. Tal cálculo é feito da 
seguinte maneira. Suponha que os valores da solução básica atual nas linhas 1,2, … , 𝑚 são 
respectivamente 𝑏1
′ , 𝑏2
′ , … , 𝑏𝑚
′ e a variável escolhida para entrar na base possua coeficientes 
𝑎1
′ , 𝑎2
′ , … , 𝑎𝑚
′ nas linhas 1,2, … , 𝑚 respectivamente. Calcula-se então: 
𝑚𝑖𝑛 {−
𝑏1
′
𝑎1
′ , −
𝑏2
′
𝑎2
′ , … , −
𝑏𝑚
′
𝑎𝑚
′
} 
Só são incluídas no cálculo do mínimo prévio as razões com denominadores negativos. Se tal 
mínimo é −
𝑏𝑘
′
𝑎𝑘
′ então a variável que sai da base é a variável associada a 𝑘-ésima linha. 
Caso todos os coeficientes 𝑎1
′ , 𝑎2
′ , … , 𝑎𝑚
′ sejam não negativos, então o problema original é 
ilimitado e o algoritmo pode ser parado. 
Após a decisão de qual variável entra na base e qual variável sai da base, o dicionário é atualizado 
através de manipulações algébricas e o Passo 3 é executado novamente. 
Exemplo 5.1 Aplique o método Simplex no seguinte PPL: 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a. 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥1 , 𝑥2 ≥ 0 
Solução: O modelo PL prévio foi estudado na Aula 02, onde foi desenhada a sua região de 
soluções viáveis: 
 
Além disso, na Aula 02 foi verificado via método gráfico que a solução ótima do problema é o 
ponto extremo 𝐶, com coordenadas 𝑥1 = 25, 𝑥2 = 7,5 e com função objetivo 𝑧 = 575. Esta 
mesma solução é agora obtida via método Simplex. 
Passo 1 
Primeiramente, transforma-se o modelo para o formato requerido pelo Simplex: 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a.: 3𝑥1 + 2𝑥2 + 𝑅1 = 90 
𝑥1 + 𝑅2 = 25 
𝑥1 , 𝑥2, 𝑅1, 𝑅2 ≥ 0 
Passo 2 
Em Seguida, constrói-se um dicionário inicial tomando 𝑅1 e 𝑅2 como variáveis básicas e efetuando 
simples manipulações: 
𝑅1 = 90 − 3𝑥1 − 2𝑥2 
𝑅2 = 25 − 𝑥1 
𝑧 = 20𝑥1 + 10𝑥2 
 
Este dicionário está associado a solução básica 𝑥1 = 0, 𝑥2 = 0, 𝑅1 = 90 e 𝑅2 = 25, que 
graficamente está associada ao ponto extremo 𝐴. O valor da função objetivo neste caso é 𝑧 = 0. 
Passo 3 
Como tanto 𝑥1 quanto 𝑥2 estão com coeficientes positivos na linha 𝑧, tem-se que a solução corrente 
não é ótima e qualquer uma destas duas variáveis pode ser escolhida para entrar na base. 
Passo 4 
Escolhendo-se arbitrariamente para entrar na base a variável com maior coeficiente, que é 𝑥1, 
deve-se responder a seguinte pergunta: 
Olhando para as linhas das variáveis básicas 𝑅1 e 𝑅2, qual maior valor que 𝑥1 pode assumir sem 
que alguma destas variáveis básicas fique negativa? Esta pergunta pode ser respondida de acordo 
com os cálculos apresentados anteriormente para o modelo genérico: 
 
𝑏1
′ = 90, 𝑏2
′ = 25 
𝑎1
′ = −3, 𝑎2
′ = −1 
 
Calcula-se então 
 
𝑚𝑖 𝑛 {−
90
−3
, −
25
−1
} = min{30,25} = 25 
 
Como 25 está associada a linha 𝑅2, esta variável sai da base. 
 
Intuitivamente, este valor 25 poderia ser encontrado apenas olhando para as linhas 𝑅1 e 𝑅2. 
 
Sabendo que 𝑥1 entra na base e 𝑅2 sai da mesma, deve-se isolar 𝑥1na linha 𝑅2 ( 
𝑥1 = 25 − 𝑅2) e fazer esta substituição nas demais linhas: 
 
𝑅1 = 15 + 3𝑅2 − 2𝑥2 
𝑥1 = 25 − 𝑅2 
𝑧 = 500 − 20𝑅2 + 10𝑥2 
 
A nova solução básica é 𝑥1 = 25, 𝑥2 = 0, 𝑅1 = 15, 𝑅2 = 0, gerando 𝑧 = 500. Graficamente, 
esta solução está representada pelo ponto extremo 𝐵. 
Passo 3 
Esta solução é ótima? A resposta é não pois ainda tem-se a variável 𝑥2 com coeficiente positivo 
na linha 𝑧 do dicionário. Portanto, esta variável entra na base. 
Passo 4 
Sabendo que 𝑥2 entra na base, deve-se agora identificar qual variável sai da mesma: 
𝑏1
′ = 15, 𝑏2
′ = 25 
𝑎1
′ = −2, 𝑎2
′ = 0 
Calcula-se: 
𝑚𝑖 𝑛 {−
15
−2
} = 7,5 
 
Note que, como 𝑎2
′ não é negativo, a segunda razão não entrou no cálculo. O valor 7,5 está 
associado a linha 𝑅1 e portanto esta variável é a que sai da base. Isola-se 𝑥2 na linha 𝑅1 ( 
𝑥2 = 7,5 + 1,5𝑅2 − 0,5𝑅1) e faz-se esta substituição nas demais linhas: 
𝑥2 = 7,5 + 1,5𝑅2 − 0,5𝑅1 
𝑥1 = 25 − 𝑅2 
 𝑧 = 575 − 5𝑅2 − 5𝑅1 
 
A nova solução básica é 𝑥1 = 25, 𝑥2 = 7,5, 𝑅1 = 0, 𝑅2 = 0, gerando 𝑧 = 575. Graficamente, 
esta solução está representada pelo ponto extremo 𝐶. 
Passo 3 
A solução atual é ótima? Sim, pois não existem mais variáveis com coeficientes positivos na linha 
𝑧. O algoritmo então termina. 
Note que o método percorreu iterativamente o caminho 𝐴 → 𝐵 → 𝐶, não precisando examinar o 
ponto extremo 𝐷 ou algum ponto extremo inviável: 
 
Exemplo 5.2 Considere o PPL a seguir e encontre a solução ótima do mesmo via método Simplex 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 , 𝑥2 ≥ 0 
Solução: O modelo prévio é o modelo do Exercício 2.1 da Aula 2 e a seguinte região de soluções 
viáveis foi obtida: 
 
A Solução ótima obtida via método gráfico foi o ponto extremo 𝐵. Neste exercício, esta solução é 
encontrada via método Simplex. O primeiro passo isso é a transformação do modelo para o formato 
padrão. Adicionam-se então as variáveis de folga não negativas 𝑅1, 𝑅2, 𝑅3: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 + 𝑅1 = 3 
𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
O próximo passo do método é obter o dicionário inicial tomando 𝑅1, 𝑅2, 𝑅3 como variáveis básicas: 
𝑅1 = 3 + 2𝑥1 − 𝑥2 
𝑅2 = 10 − 𝑥2 
𝑅3 = 14 − 3𝑥1 − 2𝑥2 
 𝑧 = 3𝑥1 + 𝑥2 
 
Note que o dicionário prévio foi obtido através de simples manipulações algébricas nas equações 
do modelo. Tal dicionário está associado a solução (𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) = (0,0,3,10,14), que gera 
uma função objetivo 𝑧 = 0. Graficamente, esta solução está representada pelo ponto A. A pergunta 
que surge agora é: esta solução é ótima? A resposta é não pois tanto 𝑥1 quanto 𝑥2 possuem 
coeficientes positivos na linha da função objetivo 𝑧. Logo, uma destas duas variáveis deve ser 
escolhida para entrar na base. Escolhendo-se arbitrariamente a com maior coeficiente na linha da 
função objetivo, que é 𝑥1, deve-se efetuar os cálculos para identificar qual variável sai da base: 
 
𝑏1
′ = 3, 𝑏2
′ = 10, 𝑏3
′ = 14 
𝑎1
′ = 2, 𝑎2
′ = 0, 𝑎3
′ = −3 
 
Calcula-se então 
 
𝑚𝑖 𝑛 { −
14
−3
} =
14
3
 
 
 
Note que só entram no cálculo do mínimo as razões com 𝑎′ negativo. O valor 
14
3
 está associado a 
linha 𝑅3 e, portanto, esta variável sai da base. Agora, deve-se isolar 𝑥1 na linha 𝑅3 (𝑥1 =
14
3
−
2
3
𝑥2 −
1
3
𝑅3) e fazer esta substituição nas demais linhas: 
 
 
𝑅1 =
37
3
−
7
3
𝑥2 −
2
3
𝑅3 
𝑅2 = 10 − 𝑥2 
𝑥1 =
14
3
−
2
3
𝑥2 −
1
3
𝑅3 
 𝑧 = 14 − 𝑥2 − 𝑅3 
 
Tal dicionário está associado a solução (𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) = (
14
3
, 0,
37
3
, 10,0), que gera uma 
função objetivo 𝑧 = 14. Graficamente, esta solução está representada pelo ponto 𝐵. A pergunta 
que surge agora é: esta solução é ótima? A resposta é sim pois os coeficientes das variáveis não 
básicas 𝑥2 e 𝑅3 são ambos negativos. 
 
3. Aplicação do Simplex em PPLs ilimitados 
 
Foi visto em aulas anteriores que existem alguns modelos PL que são classificados como 
ilimitados. Um PPL de maximização é classificado desta forma quando, para qualquer solução 
viável, existe alguma outra com função objetivo maior. Na descrição do passo 4, ao se decidir qual 
variável sai da base, está escrito: 
 
“Caso todos os coeficientes 𝑎1
′ , 𝑎2
′ , … , 𝑎𝑚
′ sejam não negativos, então o problema original é 
ilimitado e o algoritmo pode ser parado”. 
 
Para ilustrar este caso, segue um modelo ilimitado em que é feita a aplicação do método Simplex: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −𝑥1 + 𝑥2 ≤ 0 
−
1
2
𝑥1 + 𝑥2 ≤ 3 
𝑥1 , 𝑥2 ≥ 0 
O modelo prévio foi estudado na Aula 2, onde o mesmo foi classificado como ilimitado através do 
método gráfico: 
 
 
 
Para aplicar o método Simplex no modelo, deve-se inicialmente colocá-lo no formato requerido: 
 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −𝑥1 + 𝑥2 + 𝑅1 = 0 
−
1
2
𝑥1 + 𝑥2 + 𝑅2 = 3 
𝑥1 , 𝑥2, 𝑅1, 𝑅2 ≥ 0 
Em seguida, deve-se obter um dicionário inicial válido: 
 
𝑅1 = 𝑥1 − 𝑥2 
𝑅2 = 3 +
1
2
𝑥1 − 𝑥2 
𝑧 = 3𝑥1 + 𝑥2 
 
Escolhendo-se arbitrariamente 𝑥1 para entrar na base, deve-se decidir qual variável sai da base: 
 
𝑏1
′ = 0, 𝑏2
′ = 3 
𝑎1
′ = 1, 𝑎2
′ =
1
2
 
 
Como não existe 𝑎′ negativo, isto indica que a variável 𝑥1 pode aumentar indefinidamente sem 
tornar 𝑅1 ou 𝑅2 negativas. Este é o indicativo de que o modelo é ilimitado. Pode-se então parar o 
método e classificar o modelo desta forma. 
 
 
 
 
 
 
4. Aplicação do Simplex em PPLs com múltiplas soluções ótimas 
 
Considere o seguinte PPL: 
 
𝑀𝑎𝑥 𝑧 = 9𝑥1 + 6𝑥2 
s.a. −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 , 𝑥2 ≥ 0 
No exercício 2.4 da Aula 2, foi visto que o modelo prévio possui múltiplas soluções ótimas: 
 
Um PPL é ilimitado quando a variável a entrar na base pode aumentar indefinidamente sem 
tornar nenhuma variável básica negativa. 
 
 
Foi visto ainda naquela Aula que qualquer ponto do segmento 𝐶𝐵̅̅ ̅̅ é uma solução ótima do 
problema. 
 
O que aconteceria se o Simplex fosse aplicado a este PPL? É o que será visto agora. Transformando 
o modelo para o formato requerido pelo Simplex, tem-se: 
 
𝑀𝑎𝑥 𝑧 = 9𝑥1 + 6𝑥2 
s.a. −2𝑥1 + 𝑥2 + 𝑅1 = 3 
𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Iteração 1 
 
𝑅1 = 3 + 2𝑥1 − 𝑥2 
𝑅2 = 10 − 𝑥2 
𝑅3 = 14 − 3𝑥1 − 2𝑥2 
 𝑧 = 9𝑥1 + 6𝑥2 
 
Ponto extremo A do gráfico. 
Entrando 𝑥1. Saindo 𝑅3. 
 
Iteração 2 
 
𝑅1 =
37
3
−
7
3
𝑥2 −
2
3
𝑅3 
𝑅2 = 10 − 𝑥2 
𝑥1 =
14
3
−
2
3
𝑥2 −
1
3
𝑅3 
 𝑧 = 42 − 3𝑅3 + 0𝑥2 
 
Ponto extremo B do gráfico. 
 
Aqui tem-se um ponto importante. Não existem variáveis não básicas com coeficientes positivos 
na linha 𝑧. Isto indica que a solução atual é ótima. No entanto, a variável não básica 𝑥2 possui 
coeficiente nulo na linha 𝑧, indicando que esta variável não melhora e nem piora o valor da função 
objetivo caso ela entre na base. Em outras palavras, se esta solução for colocada na base, será 
obtida uma outra solução ótima com valor 𝑧 = 42. Tem-se então um caso de múltiplas soluções 
ótimas. Veja: 
 
Entrando 𝑥2. Saindo 𝑅1. 
 
Ponto extremo 𝐶 no gráfico. 
 
𝑥2 =
37
7
−
3
7
𝑅1 −
2
7
𝑅3 
𝑅2 =
33
7
+
3
7
𝑅1 +
2
7
𝑅3 
𝑥1 =
8
7
+
2
7
𝑅1 −
1
7
𝑅3 
 𝑧 = 42 − 3𝑅3 + 0𝑅1 
 
 
 
 
5. Exercícios 
 
Exercício 5.1 Considere o seguinte PPL: 
max 𝑧 =
3
2
𝑥1 + 𝑥2 
𝑠. 𝑎. : 2𝑥1 −
1
2
𝑥2 ≤ 4 
2𝑥1 +
3
2
𝑥2 ≤ 6 
2𝑥1 +
1
2
𝑥2 ≤ 4 
𝑥1, 𝑥2 ≥ 0 
 
Determine o valor ótimo e a solução ótima do PPL prévio aplicando o método Simplex. 
 
Solução comentada. Como o modelo original possui duas variáveis, pode-se desenhar o conjunto 
de soluções viáveis: 
Um PPL possui múltiplas soluções ótimas quando em um dicionário ótimo existe pelo menos 
uma variável não básica com coeficiente nulo na linha 𝑧. 
 
A região de soluçõesviáveis é limitada e possui quatro pontos extremos viáveis: 
Ponto extremo viável Valor da f.o. 𝑧 
𝐴 = (0,0) 0 
𝐵 = (2,0) 3 
𝐶 = (
3
2
, 2) 
17
4
 
𝐷 = (0,4) 4 
 
Note que a solução ótima é o ponto 𝐶, que gera o valor 
17
4
 na função objetivo. Esta mesma solução 
é agora encontrada via método Simplex. 
Primeiramente, o modelo é colocado na forma padrão: 
max 𝑧 =
3
2
𝑥1 + 𝑥2 
𝑠. 𝑎. : 2𝑥1 −
1
2
𝑥2 + 𝑅1 = 4 
2𝑥1 +
3
2
𝑥2 + 𝑅2 = 6 
2𝑥1 +
1
2
𝑥2 + 𝑅3 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Iteração 1 
𝑅1 = 4 − 2𝑥1 +
1
2
𝑥2 
𝑅2 = 6 − 2𝑥1 −
3
2
𝑥2 
𝑅3 = 4 − 2𝑥1 −
1
2
𝑥2 
𝑧 =
3
2
𝑥1 + 𝑥2 
 
Ponto extremo A na região de soluções viáveis. 
 
Entra na base: 𝑥1. Sai da base: 𝑅1 
 
Iteração 2 
𝑥1 = 2 −
1
2
𝑅1 +
1
4
𝑥2 
𝑅2 = 2 + 𝑅1 − 2𝑥2 
𝑅3 = 0 + 𝑅1 − 𝑥2 
𝑧 = 3 −
3
4
𝑅1 +
11
8
𝑥2 
 
Ponto extremo B na região de soluções viáveis. 
 
Entra na base: 𝑥2. Sai da base: 𝑅3 
 
Iteração 3 
𝑥1 = 2 −
1
4
𝑅1 −
1
4
𝑅3 
𝑅2 = 2 − 𝑅1 + 2𝑅3 
𝑥2 = 0 + 𝑅1 − 𝑅3 
𝑧 = 3 +
5
8
𝑅1 −
11
8
𝑅3 
 
Ponto extremo B na região de soluções viáveis. 
 
Note aqui que o ponto B apareceu novamente. Isto aconteceu porque o ponto B na verdade 
representa dois pontos extremos, sendo interseção de duas retas distintas com o eixo horizontal. 
 
Entra na base: 𝑅1. Sai da base: 𝑅2 
 
Iteração 4 
𝑥1 =
3
2
+
1
4
𝑅2 −
3
4
𝑅3 
𝑅1 = 2 − 𝑅2 + 2𝑅3 
𝑥2 = 2 − 𝑅2 + 𝑅3 
𝑧 =
17
4
−
5
8
𝑅2 −
1
8
𝑅3 
 
 
Ponto extremo C na região de soluções viáveis. 
Solução ótima: (𝒙𝟏, 𝒙𝟐) = (
𝟑
𝟐
, 𝟐 ), com valor ótimo 𝒛 =
𝟏𝟕
𝟒
 
O caminho para obtenção da solução ótima foi 𝐴 → 𝐵 → 𝐵 → 𝐶. Caso na iteração 1, a variável 
escolhida para entrar na base fosse 𝑥2 ao invés de 𝑥1, o caminho seria 𝐴 → 𝐷 → 𝐶 (pratique como 
exercício). 
Exercício 5.2 Considere o seguinte PPL: 
max 𝑧 = 3𝑥1 − 3𝑥2 + 𝑥3 
𝑠. 𝑎.: 𝑥1 + 2𝑥2 − 𝑥3 ≤ 5 
−3𝑥1 − 𝑥2 + 8𝑥3 ≤ 4 
𝑥1, 𝑥2, 𝑥3 ≥ 0 
 
Determine o valor ótimo e a solução ótima do PPL prévio aplicando o método Simplex. 
 
Solução comentada. O modelo na forma padrão é: 
max 𝑧 = 3𝑥1 − 3𝑥2 + 𝑥3 
𝑠. 𝑎.: 𝑥1 + 2𝑥2 − 𝑥3 + 𝑅1 = 5 
−3𝑥1 − 𝑥2 + 8𝑥3 + 𝑅2 = 4 
𝑥1, 𝑥2, 𝑥3, 𝑅1, 𝑅2 ≥ 0 
 
Iteração 1 
𝑅1 = 5 − 𝑥1 − 2𝑥2 + 𝑥3 
𝑅2 = 4 + 3𝑥1 + 𝑥2 − 8𝑥3 
𝑧 = 3𝑥1 − 3𝑥2 + 𝑥3 
 
Entra na base: 𝑥1. Sai da base: 𝑅1 
Iteração 2 
 
𝑥1 = 5 − 𝑅1 − 2𝑥2 + 𝑥3 
𝑅2 = 19 − 3𝑅1 − 5𝑥2 − 5𝑥3 
𝑧 = 15 − 3𝑅1 − 9𝑥2 + 4𝑥3 
 
Entra na base: 𝑥3. Sai da base: 𝑅2 
Iteração 3 
𝑥1 =
44
5
−
8
5
𝑅1 − 3𝑥2 −
1
5
𝑅2 
𝑥3 =
19
5
−
3
5
𝑅1 − 𝑥2 −
1
5
𝑥5 
𝑧 =
151
5
−
27
5
𝑅1 − 13𝑥2 −
4
5
𝑅2 
 
Solução ótima: (𝒙𝟏, 𝒙𝟐, 𝒙𝟑) = (
𝟒𝟒
𝟓
, 𝟎,
𝟏𝟗
𝟓
 ), com valor ótimo 𝒛 =
𝟏𝟓𝟏
𝟓
 
Exercício 5.3 Durante a resolução de um PPL de maximização via método simplex, o seguinte 
dicionário foi obtido: 
𝑥1 = 2 −
1
2
𝑅1 +
1
4
𝑥2 
𝑅2 = 2 + 𝑅1 + 2𝑥2 
𝑅3 = 0 + 𝑅1 + 5𝑥2 
𝑧 = 3 −
3
4
𝑅1 +
11
8
𝑥2 
 
O que se pode afirmar sobre este modelo? 
Solução comentada. De acordo com o dicionário apresentado, 𝑥2 é a única variável candidata a 
entrar na base. Pode-se notar ainda que 𝑥2 pode aumentar indefinidamente sem deixar as variáveis 
básicas negativas. Logo, o modelo em questão é ilimitado. 
Exercício 5.4 Durante a resolução de um PPL de maximização via método simplex, o seguinte 
dicionário foi obtido: 
𝑥1 =
3
2
+
1
4
𝑅2 −
3
4
𝑅3 
𝑅1 = 2 − 𝑅2 + 2𝑅3 
𝑥2 = 2 − 𝑅2 + 𝑅3 
𝑧 =
17
4
−
5
8
𝑅2 
 
O que se pode afirmar sobre este modelo? 
Solução comentada. De acordo com o dicionário fornecido, a solução atual é ótima pois não 
existem variáveis não básicas com coeficientes positivos na linha 𝑧. Além disso, a variável não 
básica 𝑅3 possui coeficiente nulo nesta linha, o que indica que o modelo possui múltiplas soluções 
ótimas. 
6. Conclusão 
Nesta aula, os passos do método Simplex foram apresentados em detalhes. Tal método percorre 
iterativamente soluções básicas viáveis até que se tenha garantias de que a solução ótima foi obtida. 
O simplex possui ainda as seguintes vantagens: 
• Não existe a necessidade de se percorrer todas as soluções básicas viáveis. 
• Os cálculos são facilmente atualizados de uma iteração para outra. 
• O método permite saber se o modelo é ilimitado ou possui múltiplas soluções ótimas. 
Resumo 
 
Esta aula apresentou os passos do método simplex, que podem ser aplicados em PPLs da seguinte 
forma: 
max max 𝑐𝑇𝑥 
s.a s.a. 𝐴𝑥 ≤ 𝑏 
𝑥 ≥ 0 
 Nesta aula, o método Simplex foi aplicado no seguinte PPL: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 , 𝑥2 ≥ 0 
O primeiro passo é a colocação do modelo na forma padrão: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 + 𝑅1 = 3 
 𝑥2 + 𝑅2 = 10 
3𝑥1 + 2𝑥2 + 𝑅3 = 14 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
Em seguida, deve-se montar o primeiro dicionário que está associado a solução básica com 
variáveis básicas 𝑅1, 𝑅2, 𝑅3: 
𝑅1 = 3 + 2𝑥1 − 𝑥2 
𝑅2 = 10 − 𝑥2 
𝑅3 = 14 − 3𝑥1 − 2𝑥2 
 𝑧 = 3𝑥1 + 𝑥2 
 
Qualquer dicionário tem sempre estas características: 
• Cada variável básica é escrita em função das variáveis não básicas (variáveis zeradas). 
• A função objetivo é escrita em função das variáveis não básicas (variáveis zeradas). 
 
Se na linha 𝑧 existir alguma variável não básica com coeficiente positivo então a solução atual não 
é ótima e uma variável com esta caraterística deve ser escolhida para entrar na base. Para o exemplo 
em questão será escolhida a variável 𝑥1. Deve-se agora saber qual o maior valor que 𝑥1 pode 
assumir de modo que nenhuma das variáveis básicas 𝑅1, 𝑅2 ou 𝑅3 fique negativa? Olhando para o 
dicionário, a resposta para a pergunta é 
14
3
 . Se 𝑥1assumir valor acima de 
14
3
, então 𝑅3 fica negativa. 
Assim, esta variável é a que sai da base. Isola-se 𝑥1 em função na linha 𝑅3 (𝑥1 =
14
3
−
2
3
𝑥2 −
1
3
𝑅3) 
e fazer esta substituição nas demais linhas: 
 
 
𝑅1 =
37
3
−
7
3
𝑥2 −
2
3
𝑅3 
𝑅2 = 10 − 𝑥2 
𝑥1 =
14
3
−
2
3
𝑥2 −
1
3
𝑅3 
 𝑧 = 14 − 𝑥2 − 𝑅3 
 
Tal dicionário está associado a solução (𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) = (
14
3
, 0,
37
3
, 10,0), que gera uma 
função objetivo 𝑧 = 14. A solução é ótima pois os coeficientes das variáveis não básicas 𝑥2 e 𝑅3 
na linha 𝑧 são ambos negativos. 
 
Foi visto ainda nesta aula quando identificar se um PPL é ilimitado ou possui múltiplas soluções 
ótima no método Simplex: 
 
• Um PPL é ilimitado quando a variável a entrar na base pode aumentar indefinidamente 
sem tornar nenhuma variável básica negativa. 
• Um PPL possui múltiplas soluções ótimas quando em um dicionário ótimo existe pelo 
menos uma variável não básica com coeficiente nulo na linha 𝑧. 
 
Informações sobre as próximas aulas 
 
Nas próximas aulas será estudado o método Simplex duas fases, que pode ser aplicado em PPLs 
não contemplados pelo método Simplex aprendido nesta aula. 
Referências 
Chvatal, V., & Chvatal, V. (1983). Linear programming. Macmillan. 
Hillier, F. S., & Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw Hill Brasil.