Aula 07 - Simplex Duas Fases

Prévia do material em texto

Aula 7 – Método Simplex Duas Fases 
Objetivos: 
Ao final desta aula, o estudante será capaz de: 
1. Resolver PPLs através do método Simplex duas fases. 
 
1. Introdução 
Em aulas anteriores, foi visto como aplicar o Método Simplex básico, que é indicado para 
PPLs que podem ser escritos da seguinte forma: 
max max 𝑧 = 𝑐𝑇𝑥 
s.a s.a.: 𝐴𝑥 ≤ 𝑏 
𝑥 ≥ 0 
Com a condição ainda de que 𝒃 ≥ 𝟎. O algoritmo Simplex básico para modelos no 
formato prévio encontra-se descrito no Fluxograma 7.1: 
Passo 3: A Solução 
básica é ótima ou 
ilimitada?
Início
Fim
Passo 1: Colocar o PPL na 
forma padrão.
Passo 4: Atualiza a solução 
básica.
Sim Não
Passo 2: Obtenção da 
solução básica inicial
 
Fluxograma 7.1 – Método Simplex Básico 
Quando não é possível colocar o modelo no formato requerido, então faz-se necessário 
um procedimento mais sofisticado do que o Passo 2 para obter-se uma solução básica inicial viável. 
Neste contexto, surge o método Simplex duas fases, que substitui os passos 2, 3 e 4 por duas etapas: 
uma etapa chamada de Fase 1 que apresenta uma metodologia para obtenção de uma solução básica 
viável e uma outra etapa chamada de Fase II que utiliza os passos 3 e 4 do método Simplex básico 
para obtenção da solução ótima ou para conclusão de que o modelo é ilimitado. 
Esta aula é dedicada a apresentar os detalhes do método Simplex duas fases. Para uma 
boa compreensão desta aula, faz-se necessário que o estudante esteja com os conceitos da Aula 5 
(Simplex básico) bem consolidados. Se necessário, revise esta aula. 
2. Método Simplex duas Fases 
O primeiro passo do método Simplex duas fases consiste em colocar o modelo na forma 
padrão, assim como já ocorria para o método Simplex básico. Em seguida, as duas Fases do método 
são aplicadas: 
Fase I: Apresenta uma metodologia para obtenção de uma solução viável e um dicionário válido 
(substitui o passo 2 do método Simplex). Caso tal solução não exista, o PPL é inviável. 
Fase II: A partir do dicionário gerado na Fase I, utiliza os passos 3 e 4 do método Simplex básico 
para obtenção da solução ótima ou para conclusão de que o modelo é ilimitado. 
O Fluxograma 7.2 resume as etapas do método Simplex duas Fases. 
Início
Fim
Colocar o PPL na forma padrão.
Fase I: Procedimento específico para 
obtenção de uma solução básica viável ou 
para conclusão de que o PPL é inviável.
Fase II: Repetição dos passos 3 e 4 do 
Simplex básico até que a solução ótima seja 
obtida ou que se conclua que o PPL é 
ilimitado.
O PPL é 
viável?
Não
Sim
 
Fluxograma 7.2: Método Simplex duas fases 
Agora, os detalhes do método Simplex duas fases são apresentados. Para facilitar o 
entendimento, considere o exemplo: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a.: 𝑥1 − 𝑥2 ≤ − 3 
2,5𝑥1 + 𝑥2 ≥ 10 
𝑥2 ≤ 11 
𝑥1, 𝑥2 ≥ 0 
Primeiro, deve-se colocar o modelo na forma padrão: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a.: 𝑥1 − 𝑥2 + 𝑅1 = −3 
2,5𝑥1 + 𝑥2 − 𝑅2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
Com o modelo na forma padrão, deve-se aplicar as Fases I e II. 
2.1 Descrição da Fase I 
A fase I é usada para se obter uma solução básica inicial viável. Para isso, cria-se um 
novo PPL com algumas variáveis artificiais cuja solução ótima gera uma solução básica viável 
para o PPL original. O processo de construção e resolução deste novo PPL é dividido nas seguintes 
etapas: 
• Etapa 1: multiplica-se cada restrição com lado direito negativo por -1. 
• Etapa 2: constrói-se um novo modelo PL adicionando-se uma variável artificial 
não negativa a cada restrição que originalmente é de igualdade e em cada restrição 
que a variável de folga ou excesso está com coeficiente negativo. A função 
objetivo é modificada para minimização da soma das variáveis artificiais criadas 
na etapa anterior. 
• Etapa 3: resolve-se o modelo da etapa anterior através do método Simplex. O 
dicionário ótimo deste modelo indica uma solução básica para o modelo original. 
A seguir, cada uma destas etapas é detalhada. 
Etapa 1: Multiplicação de cada restrição com lado direito negativo por -1. 
A primeira etapa da Fase I consiste em multiplicar cada restrição com lado direito 
negativo por -1: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a. – 𝑥1 + 𝑥2 − 𝑅1 = 3 
2,5𝑥1 + 𝑥2 − 𝑅2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
Note que no exemplo ilustrativo apenas a primeira restrição precisou ser modificada. 
Etapa 2: Construção de um novo modelo PL adicionando-se uma variável artificial não negativa a 
cada restrição que originalmente é de igualdade e em cada restrição que a variável de folga ou 
excesso está com coeficiente negativo. A função objetivo é modificada para minimização da soma 
das variáveis artificiais criadas na etapa anterior. 
Na segunda Etapa da Fase I, constrói-se um novo modelo PL adicionando-se uma variável 
artificial não negativa a cada restrição que originalmente é de igualdade e em cada restrição que a 
variável de folga ou excesso está com coeficiente negativo. No exemplo, nenhuma restrição 
original é de igualdade mas as variáveis 𝑅1 e 𝑅2 estão com coeficientes negativos. Assim, duas 
variáveis não negativas (𝐴1 e 𝐴2) são criadas e adicionadas ao modelo. A soma das variáveis 
artificiais é minimizada no novo modelo: 
𝑀𝑖𝑛 𝑧′ = 𝐴1 + 𝐴2 
s.a. – 𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 3 
2,5𝑥1 + 𝑥2 − 𝑅2 + 𝐴2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3, 𝐴1, 𝐴2 ≥ 0 
 
 
 
Etapa 3: resolve-se o modelo da etapa anterior através do método Simplex. O dicionário ótimo 
deste modelo indica uma solução básica para o modelo original. 
Na terceira etapa da fase I, o modelo construído na etapa anterior é resolvido através do 
método Simplex básico, tomando como solução básica inicial a solução que considera como 
variáveis básicas: 
• Cada uma das variáveis básicas artificiais na Etapa 2 (No exemplo, 𝐴1 e 𝐴2). 
• A variável de folga ou excesso de cada restrição não modificada na Etapa 2 (No 
exemplo, 𝑅3) 
No exemplo em questão, a solução possui variáveis 𝐴1, 𝐴2 e 𝑅3 e gera o seguinte 
dicionário: 
 
𝐴1 = 3 + 𝑥1 − 𝑥2 + 𝑅1 
𝐴2 = 10 − 2,5𝑥1 − 𝑥2 + 𝑅2 
𝑅3 = 11 − 𝑥2 
𝑧′ = 13 − 1,5𝑥1 − 2𝑥2 + 𝑅1 + 𝑅2 
 
Note que a linha 𝑧′ precisou ser manipulada algebricamente para que a mesma fique 
escrita em função das variáveis não básicas. Após a construção do dicionário, os Passos 3 e 4 
método Simplex básico é aplicado normalmente. No entanto, aqui vale uma observação 
importante: 
 
 
 
 
Observação: O modelo que é resolvido na Fase I via método Simplex é um modelo de 
minimização. Portanto, as variáveis candidatas a entrar na base são aquelas com coeficientes 
negativos na linha 𝑧′ 
Observação: O PPL desta etapa é sempre de minimização, independentemente se o modelo 
original é de minimização ou maximização. 
Seguem agora as iterações do método Simplex básico: 
Iteração 1 
Entra na base: 𝑥2 
Sai da base: 𝐴1 
𝑥2 = 3 + 𝑥1 + 𝑅1 − 𝐴1 
𝐴2 = 7 − 3,5𝑥1 + 𝑅2 − 𝑅1 + 𝐴1 
𝑅3 = 8 − 𝑥1 − 𝑅1 + 𝐴1 
𝑧′ = 7 − 3,5𝑥1 − 𝑅1 + 𝑅2 + 2𝐴1 
 
Iteração 2 
Entra na base: 𝑥1 
Sai da base: 𝐴2 
𝑥2 = 5 +
5
7
𝑅1 −
5
7
𝐴1 +
2
7
𝑅2 −
2
7
𝐴2 
𝑥1 = 2 +
2
7
𝑅2 −
2
7
𝑅1 +
2
7
𝐴1 −
2
7
𝐴2 
𝑅3 = 6 −
5
7
𝑅1 +
5
7
𝐴1 −
2
7
𝑅2 +
2
7
𝐴2 
𝑧′ = 0 + 𝐴1 + 𝐴2 
 
O PPL resolvido aqui na Fase I possui as mesmas restrições do modelo 1 acrescidas de 
algumas variáveis artificiais (no exemplo, 𝐴1 e 𝐴2). Assim, se na solução ótima do modelo da Fase 
I as variáveis artificiais não estiverem na base, o dicionário ótimo da Fase I apresenta uma solução 
básica viável para o modelo original que é então utilizada na Fase II. 
 
 
 
2.2 Descrição da Fase II 
Conforme já comentado, a ideia por trás do método é que a Fase I gere uma solução básica 
viável para o modelo original. Note que no exemplo apresentado, a Fase I gerou uma solução 
básica cuja as variáveis básicas são 𝑥2, 𝑥1 e𝑅3. 
Para dar prosseguimento ao método, monta-se um dicionário para o modelo original 
quase igual ao dicionário ótimo da Fase I, com as seguintes diferenças: 
• As variáveis artificiais criadas na Etapa 2 da Fase I são excluídas. 
• A linha 𝑧′ é substituída pela linha 𝑧 de acordo com a função objetivo original do 
modelo. 
Para o exemplo, tem-se: 
𝑥2 = 5 +
5
7
𝑅1 +
2
7
𝑅2 
Observação: Se no dicionário ótimo da Fase I existe alguma variável artificial na base então 
o problema original é inviável. Neste caso, o método pode parar. 
𝑥1 = 2 +
2
7
𝑅2 −
2
7
𝑅1 
𝑅3 = 6 −
5
7
𝑅1 −
2
7
𝑅2 
𝑧 = 9 +
6
7
𝑅2 +
1
7
𝑅1 
 
Note que a linha 𝑧 está escrita em função das variáveis não básicas 𝑅1 e 𝑅2. Tal cálculo 
foi feito da seguinte forma: 
𝑧 = 2𝑥1 + 𝑥2 = 2 (2 +
2
7
𝑅2 −
2
7
𝑅1) + 5 +
5
7
𝑅1 +
2
7
𝑅2 = 9 +
6
7
𝑅2 +
1
7
𝑅1 
A partir do dicionário, deve-se aplicar os passos 3 e 4 do método Simplex para obter a 
solução ótima. No PPL original em questão, que é um problema de minimização, a solução atual 
já é a ótima pois não existe variável não básica com coeficiente negativo na linha 𝑧. Logo, a solução 
ótima do problema é 𝑥1 = 2 e 𝑥2 = 5, com função objetivo 𝑧 = 9. 
2.3 Interpretação gráfica 
Durante a aplicação do método duas fases, as seguintes soluções foram obtidas para o 
exemplo: 
Solução Fase (𝑥1, 𝑥2) 
1 I (0,0) 
2 I (0,3) 
3 I (2,5) 
4 II (2,5) 
Graficamente, estas soluções representam o caminho destacado na Figura 7.1: 
 
Figura 7.1 - Caminho percorrido pelo método Simplex duas fases 
Note que a Fase I percorreu duas soluções inviáveis ((0,0) e (0,3)) antes de chegar na 
solução viável (2,5). A Fase I termina justamente quando uma solução viável é encontrada. A 
Fase II então inicia-se na solução viável e neste caso não houve a necessidade de percorrer outras 
soluções. 
3 Casos Especiais 
Além do caso em que o PPL pode ser inviável já discutido na Seção 2.1 desta aula, 
existem ainda mais três casos especiais: 
• PPL ilimitado. 
• Múltiplas soluções ótimas. 
• Degeneração. 
Os três casos prévios já foram discutidos na Aula 5, durante a explicação do método 
Simplex básico. Tudo que foi apresentado naquela Aula continua válido aqui para o método 
Simplex duas fases. Se necessário, revise a Aula 5. 
4. Exercícios 
Exercício 7.1 A seguir, são apresentados 3 PPLs com duas variáveis. Desenhe a região de soluções 
viáveis de cada um deles e encontre a solução ótima dos mesmos através do método gráfico e do 
método Simplex duas Fases. 
Item a) 
min 𝑧 = 𝑥1 − 2𝑥2 
𝑠. 𝑎 𝑥1 + 𝑥2 ≥ 2 
−𝑥1 + 𝑥2 ≥ 1 
𝑥2 ≤ 3 
𝑥1, 𝑥2 ≥ 0 
 
Item b) 
Item a) 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 ≥ 5 
−4𝑥1 + 𝑥2 ≥ −4 
−
1
2
𝑥1 + 𝑥2 ≤ 4 
𝑥1, 𝑥2 ≥ 0 
 
 
Item c) 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 ≥ 5 
−4𝑥1 + 𝑥2 = −4 
−
1
2
𝑥1 + 𝑥2 ≤ 4 
𝑥1, 𝑥2 ≥ 0 
 
Solução comentada do Exercício 7.2 item a 
A região de soluções viáveis do modelo é: 
 
A solução ótima do modelo utilizando o método gráfico é 𝑥1 = 0 e 𝑥2 = 3, que gera 𝑧 = −6 
(verifique enumerando todos os pontos extremos viáveis e retornando aquela com menor valor de 
𝑧). 
Para o Simplex, inicialmente escreve-se o modelo na forma padrão: 
min z = 𝑥1 − 2𝑥2 
𝑠. 𝑎 𝑥1 + 𝑥2 − 𝑅1 = 2 
−𝑥1 + 𝑥2 − 𝑅2 = 1 
𝑥2 + 𝑅3 = 3 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Início da Fase I 
Etapa 1: multiplica-se cada restrição com lado direito negativo por -1. No caso, nenhuma restrição 
precisa ser modificada. 
Etapa 2: Cria-se um novo PPL adicionando-se uma variável artificial não negativa a cada restrição 
que originalmente é de igualdade e em cada restrição que a variável de folga ou excesso está com 
coeficiente negativo. As duas primeiras restrições do modelo original precisam das variáveis 
artificiais. Além disso, minimiza-se a soma destas novas variáveis: 
min 𝑧′ = 𝐴1 + 𝐴2 
𝑠. 𝑎 𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 2 
−𝑥1 + 𝑥2 − 𝑅2 + 𝐴2 = 1 
𝑥2 + 𝑅3 = 3 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3, 𝐴1, 𝐴2 ≥ 0 
 
Etapa 3: Resolve-se o novo modelo através do Simplex básico tomando como dicionário inicial: 
𝐴1 = 2 − 𝑥1 − 𝑥2 + 𝑅1 
𝐴2 = 1 + 𝑥1 − 𝑥2 + 𝑅2 
𝑅3 = 3 − 𝑥2 
𝑧′ = 3 − 2𝑥2 + 𝑅1 + 𝑅2 
 
Dicionário prévio está associado no gráfico ao ponto extremo inviável (𝑥1, 𝑥2) = (0,0) 
Iteração 1: Entra 𝑥2. Sai 𝐴2 
𝐴1 = 1 − 2𝑥1 + 𝑅1 − 𝑅2 + 𝐴2 
𝑥2 = 1 + 𝑥1 + 𝑅2 − 𝐴2 
𝑅3 = 2 − 𝑥1 − 𝑅2 + 𝐴2 
𝑧′ = 1 − 2𝑥1 + 𝑅1 − 𝑅2 + 2𝐴2 
 
Dicionário prévio está associado no gráfico ao ponto extremo inviável (𝑥1, 𝑥2) = (0,1) 
Iteração 2: Entra 𝑥1. Sai 𝐴1 
𝑥1 = 
1
2
+
1
2
𝑅1 −
1
2
𝑅2 −
1
2
𝐴1 +
1
2
𝐴2 
𝑥2 = 
3
2
+
1
2
𝑅1 +
1
2
𝑅2 −
1
2
𝐴1 −
1
2
𝐴2 
𝑅3 = 
3
2
−
1
2
𝑅1 −
1
2
𝑅2 +
1
2
𝐴1 +
1
2
𝐴2 
𝑧′ = 0 + 𝐴1 + 𝐴2 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (
1
2
,
3
2
) 
Início da Fase II 
Como as variáveis artificiais 𝐴1 e 𝐴2 não estão na base do dicionário ótimo da fase I, então o 
modelo original do Item a é viável e pode-se prosseguir com a Fase II. 
Dicionário inicial da Fase II 
𝑥1 = 
1
2
+
1
2
𝑅1 −
1
2
𝑅2 
𝑥2 = 
3
2
+
1
2
𝑅1 +
1
2
𝑅2 
𝑅3 = 
3
2
−
1
2
𝑅1 −
1
2
𝑅2 
𝑧 = −
5
2
−
1
2
𝑅1 −
3
2
𝑅2 
 
A linha 𝑧 foi obtida através do cálculo: 
𝑧 = 𝑥1 − 2𝑥2 =
1
2
+
1
2
𝑅1 −
1
2
𝑅2 − 2 (
3
2
+
1
2
𝑅1 +
1
2
𝑅2) = −
5
2
−
1
2
𝑅1 −
3
2
𝑅2 
O modelo original é de minimização. Logo as variáveis candidatas a entrar na base são as que 
possuírem coeficientes negativos na linha 𝑧. 
Iteração 1: Entra 𝑅2. Pode sair tanto 𝑥1 quanto 𝑅3. Escolhendo arbitrariamente 𝑥1 
𝑅2 = 1 −
1
2
𝑥1 + 𝑅1 
𝑥2 = 2 −
1
4
𝑥1 + 𝑅1 
𝑅3 = 1 +
1
4
𝑥1 − 𝑅1 
𝑧 = −4 +
3
4
𝑥1 − 2𝑅1 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (0,2) 
 
Iteração 2: Entra 𝑅1. Sai 𝑅3 
𝑅2 = 2 −
1
2
𝑥1 − 𝑅3 
𝑥2 = 3 − 𝑅3 
𝑅1 = 1 +
1
4
𝑥1 − 𝑅3 
𝑧 = −6 +
3
4
𝑥1 + 2𝑅3 
 
Assim, a solução ótima do modelo original é 𝑥1 = 0 e 𝑥2 = 3, que gera 𝑧 = −6 
No gráfico, o caminho percorrido por todo o método foi: 
(0,0) → (0,1) → (
1
2
,
3
2
) → (0,2) → (0,3) 
Solução comentada do Exercício 7.2 item b 
A região de soluções viáveis do modelo é: 
 
A solução ótima do modelo utilizando o método gráfico é 𝑥1 =
16
7
 e 𝑥2 =
36
7
, que gera 𝑧 =
88
7
 
(verifique enumerando todos os pontos extremos viáveis e retornando aquela com menor valor de 
𝑧). 
Para o Simplex duas fases, inicialmente escreve-se o modelo na forma padrão é: 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 = 5 
−4𝑥1 + 𝑥2 − 𝑅2 = −4 
−
1
2
𝑥1 + 𝑥2 + 𝑅3 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Início da Fase I 
Etapa 1: multiplica-se cada restrição com lado direito negativo por -1: 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 = 5 
4𝑥1 − 𝑥2 + 𝑅2 = 4 
−
1
2
𝑥1 + 𝑥2 + 𝑅3 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Etapa 2: Cria-se um novo PPL adicionando-se uma variável artificial não negativa a cada restrição 
que originalmente é de igualdade e em cada restrição que a variável de folga ou excesso está com 
coeficiente negativo. No modelo em questão, apenas a primeira restrição precisa ser modificada. 
A função objetivo do novo PPL visa minimizar a soma das variáveis artificiais criadas: 
min 𝑧′ = 𝐴1 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 5 
4𝑥1 − 𝑥2 + 𝑅2 = 4 
−
1
2
𝑥1 + 𝑥2 + 𝑅3 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3, 𝐴1 ≥ 0 
 
Note que mesmo o modelo original sendo de maximização, o modelo da etapa 3 é de minimização. 
Etapa 3: Resolve-se o novo modelo através do Simplex básico tomando como dicionário inicial: 
𝐴1 = 5 −
5
3
𝑥1 − 𝑥2 + 𝑅1 
𝑅2 = 4 − 4𝑥1 + 𝑥2 
𝑅3 = 4 +
1
2
𝑥1 − 𝑥2 
𝑧′ = 5 −
5
3
𝑥1 − 𝑥2 + 𝑅1 
 
Dicionário prévio está associado no gráfico ao ponto extremo inviável (𝑥1, 𝑥2) = (0,0) 
Iteração 1: Entra 𝑥1.Sai 𝑅2 
𝐴1 = 
10
3
−
17
12
𝑥2 +
5
12
𝑅2 + 𝑅1 
𝑥1 = 1 +
1
4
𝑥2 −
1
4
𝑅2 
𝑅3 = 
9
2
−
7
8
𝑥2 −
1
8
𝑅2 
𝑧′ =
10
3
−
17
12
𝑥2 + 𝑅1 +
5
12
𝑅2 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (1,0) 
Iteração 2: Entra 𝑥2. Sai 𝐴1 
𝑥2 =
40
17
+
5
17
𝑅2 +
12
17
𝑅1 −
12
17
𝐴1 
𝑥1 =
27
17
+
3
17
𝑅1 −
3
17
𝑅2 −
3
17
𝐴1 
𝑅3 = 
83
34
−
21
34
𝑅1 −
13
34
𝑅2 
𝑧′ = 0 + 𝐴1 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (
27
17
,
40
17
) 
Início da Fase II 
Dicionário inicial da Fase II 
𝑥2 =
40
17
+
5
17
𝑅2 +
12
17
𝑅1 
𝑥1 =
27
17
+
3
17
𝑅1 −
3
17
𝑅2 
𝑅3 = 
83
34
−
21
34
𝑅1 −
13
34
𝑅2 
𝑧 =
107
17
+
27
17
𝑅1 +
7
17
𝑅2 
 
A função objetivo 𝑧 é de maximização. Logo, as variáveis com coeficientes positivos nesta linha 
são candidatas a entrar na base. 
Entra 𝑅1. Sai 𝑅3 
𝑥2 =
36
7
−
1
7
𝑅2 +
8
7
𝑅3 
𝑥1 =
16
7
−
2
7
𝑅2 −
2
7
𝑅3 
𝑅3 = 
83
21
−
13
21
𝑅2 −
34
21
𝑅3 
𝑧 =
88
7
−
4
7
𝑅2 −
18
7
𝑅3 
 
Assim, a solução ótima do modelo original é 𝑥1 =
16
7
 e 𝑥2 =
36
7
, que gera 𝑧 =
88
7
 
No gráfico, o caminho percorrido por todo o método foi: 
(0,0) → (1,0) → (
27
17
,
40
17
) → (
16
7
,
36
7
) 
Solução comentada do Exercício 7.2 item c 
Note que o modelo do item c é muito similar ao do item b. A diferença é que a segunda restrição 
agora é de igualdade. 
A região de soluções viáveis do modelo é: 
 
A região F é composta pelo segmento destacado em negrito. A solução ótima do modelo utilizando 
o método gráfico é 𝑥1 =
16
7
 e 𝑥2 =
36
7
, que gera 𝑧 =
88
7
 (verifique enumerando todos os pontos 
extremos viáveis e retornando aquela com menor valor de 𝑧). 
Para o Simplex, inicialmente escreve-se o modelo na forma padrão: 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 = 5 
−4𝑥1 + 𝑥2 = −4 
−
1
2
𝑥1 + 𝑥2 + 𝑅2 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2 ≥ 0 
 
Inicialmente, multiplica-se cada restrição com lado direito negativo por -1: 
max 𝑧 = 𝑥1 + 2𝑥2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 = 5 
4𝑥1 − 𝑥2 = 4 
−
1
2
𝑥1 + 𝑥2 + 𝑅2 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2 ≥ 0 
 
Resolve-se o seguinte modelo através do método Simplex básico: 
min 𝑧′ = 𝐴1 + 𝐴2 
𝑠. 𝑎 
5
3
𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 5 
4𝑥1 − 𝑥2 + 𝐴2 = 4 
−
1
2
𝑥1 + 𝑥2 + 𝑅2 = 4 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝐴1, 𝐴2 ≥ 0 
 
𝐴1 = 5 −
5
3
𝑥1 − 𝑥2 + 𝑅1 
𝐴2 = 4 − 4𝑥1 + 𝑥2 
𝑅2 = 4 +
1
2
𝑥1 − 𝑥2 
𝑧′ = 9 −
17
3
𝑥1 + 𝑅1 
 
Dicionário prévio está associado no gráfico ao ponto extremo inviável (𝑥1, 𝑥2) = (0,0) 
Iteração 1: Entra 𝑥1. Sai 𝐴2 
 
𝐴1 = 
10
3
−
17
12
𝑥2 +
5
12
𝐴2 + 𝑅1 
𝑥1 = 1 +
1
4
𝑥2 −
1
4
𝐴2 
𝑅2 = 
9
2
−
7
8
𝑥2 −
1
8
𝐴2 
𝑧′ =
10
3
−
17
12
𝑥2 + 𝑅1 +
17
12
𝐴2 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (1,0) 
Iteração 2: Entra 𝑥2. Sai 𝐴1 
𝑥2 =
40
17
+
5
17
𝐴2 +
12
17
𝑅1 −
12
17
𝐴1 
𝑥1 =
27
17
+
3
17
𝑅1 −
3
17
𝐴2 −
3
17
𝐴1 
𝑅2 = 
83
34
−
21
34
𝑅1 −
13
34
𝐴2 
𝑧′ = 0 + 𝐴1 + 𝐴2 
 
Dicionário prévio está associado no gráfico ao ponto extremo viável (𝑥1, 𝑥2) = (
27
17
,
40
17
) 
Início da Fase II 
Dicionário inicial da Fase II 
𝑥2 =
40
17
+
12
17
𝑅1 
𝑥1 =
27
17
+
3
17
𝑅1 
𝑅2 = 
83
34
−
21
34
𝑅1 
𝑧 =
107
17
+
27
17
𝑅1 
 
Entra 𝑅1. Sai 𝑅2 
𝑥2 =
36
7
∓
8
7
𝑅2 
𝑥1 =
16
7
−
2
7
𝑅2 
𝑅1 = 
83
21
−
34
21
𝑅2 
𝑧 =
88
7
−
18
7
𝑅3 
 
Assim, a solução ótima do modelo original é 𝑥1 =
16
7
 e 𝑥2 =
36
7
, que gera 𝑧 =
88
7
 
No gráfico, o caminho percorrido por todo o método foi: 
(0,0) → (1,0) → (
27
17
,
40
17
) → (
16
7
,
36
7
) 
Exercício 7.3 O PPL a Seguir é inviável. Verifique que esta característica é realmente verdadeira 
aplicando o método Simplex duas fases. 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a. −𝑥1 + 𝑥2 ≥ 3 
5
2
𝑥1 + 𝑥2 ≥ 10 
𝑥2 ≤ 3 
𝑥1 , 𝑥2 ≥ 0 
Solução comentada. O modelo na forma padrão é: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a. −𝑥1 + 𝑥2 − 𝑅1 = 3 
5
2
𝑥1 + 𝑥2 − 𝑅2 = 10 
𝑥2 + 𝑅3 = 3 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
Fase I 
𝑀𝑖𝑛 𝑧′ = 𝐴1 + 𝐴2 
s.a. −𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 3 
5
2
𝑥1 + 𝑥2 − 𝑅2 + 𝐴2 = 10 
𝑥2 + 𝑅3 = 3 
𝑥1 , 𝑥2, 𝑅1, 𝑅2, 𝑅3, 𝐴1, 𝐴2 ≥ 0 
 
𝐴1 = 3 + 𝑥1 − 𝑥2 + 𝑅1 
𝐴2 = 10 −
5
2
𝑥1 − 𝑥2 + 𝑅2 
𝑅3 = 3 − 𝑥2 
𝑧′ = 13 −
3
2
𝑥1 − 2𝑥2 + 𝑅1 + 𝑅2 
 
Iteração 1. Entra 𝑥2. Sai 𝐴1 
𝑥2 = 3 + 𝑥1 + 𝑅1 − 𝐴1 
𝐴2 = 7 −
7
2
𝑥1 − 𝑅1 + 𝑅2 + 𝐴1 
𝑅3 = 0 − 𝑥1 − 𝑅1 + 𝐴1 
𝑧′ = 7 −
7
2
𝑥1 − 𝑅1 + 𝑅2 + 2𝐴1 
 
Iteração 2. Entra 𝑥1. Sai 𝑅3 
 
𝑥2 = 3 − 𝑅3 
𝐴2 = 7 +
5
2
𝑅1 + 𝑅2 +
7
2
𝑅3 − 2𝐴1 
𝑥1 = −𝑅1 − 𝑅3 + 𝐴1 
𝑧′ = 7 +
5
2
𝑅1 + 𝑅2 +
7
2
𝑅3 −
3
2
𝐴1 
 
Iteração 3. Entra 𝐴1. Sai 𝐴2 
 
𝑥2 = 3 − 𝑅3 
𝐴1 = 
14
5
+ 𝑅1 +
2
5
𝑅2 + 1,4𝑅3 −
2
5
𝐴2 
𝑥1 =
14
5
+
2
5
𝑅2 +
2
5
𝑅3 −
2
5
𝐴2 
 𝑧′ =
14
5
+ 𝑅1 +
2
5
𝑅2 +
7
5
𝑅3 +
3
5
𝐴2 
 
Note que a variável artificial 𝐴1 está presente no dicionário ótimo da Fase I. Logo, o 
problema original é inviável. 
5 Conclusão 
Esta Aula apresentou os detalhes do método Simplex 2 fases, que permite a obtenção da 
solução ótima de PPLs não abrangidos pelo método Simplex básico aprendido na Aula 5. 
Foi visto nesta aula que o método Simplex duas fases inicia-se colocando o modelo na 
forma padrão. Em seguida, as duas fases são aplicadas. A Fase I descreve uma metodologia para 
a obtenção de uma solução básica viável para o problema original. A partir desta solução, a Fase 
II usa os passos 3 e 4 do método Simplex básico para obtenção da solução ótima do problema 
original. 
6 Resumo 
Esta Aula apresenta os detalhes do método Simplex duas fases, que é indicado para PPLs 
que não podem ser escritos como: 
max max 𝑐𝑇𝑥 
s.a s.a. 𝐴𝑥 ≤ 𝑏 
𝑥 ≥ 0 
Com a condição ainda de que 𝒃 ≥ 𝟎. Um exemplo de PPL em que o método Simplex 
duas fases é indicado é: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a. 𝑥1 − 𝑥2 ≤ − 3 
2,5𝑥1 + 𝑥2 ≥ 10 
𝑥2 ≤ 11 
𝑥1, 𝑥2 ≥ 0 
Para o Simplex duas fases, primeiramente deve-se colocar o modelo na forma padrão: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a. 𝑥1 − 𝑥2 + 𝑅1 = −3 
2,5𝑥1 + 𝑥2 − 𝑅2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Na Fase I, inicialmente multiplica-se as restrições com lado direito negativo por -1: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a.: −𝑥1 + 𝑥2 − 𝑅1 = 3 
2,5𝑥1 + 𝑥2 − 𝑅2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3 ≥ 0 
 
Em seguida, resolve-se o seguinte modelo através do Simplex básico: 
𝑀𝑖𝑛 𝑧′ = 𝐴1 + 𝐴2 
s.a. – 𝑥1 + 𝑥2 − 𝑅1 + 𝐴1 = 3 
2,5𝑥1 + 𝑥2 − 𝑅2 + 𝐴2 = 10 
𝑥2 + 𝑅3 = 11 
𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3, 𝐴1, 𝐴2 ≥ 0 
O modelo prévio é similar ao modelo anterior porém com duas diferenças: 
• Foi criada uma variável artificial para cada restrição que era originalmente de 
igualdade e para cada restrição em que o coeficiente da variável de folga ou de 
excesso é negativo. 
• A função objetivo agora é a minimização da soma das variáveis artificiais. 
 
O dicionário ótimo do modelo da Fase I é: 
𝑥2 = 5 +
5
7
𝑅1 −
5
7
𝐴1 +
2
7
𝑅2 −
2
7
𝐴2 
𝑥1 = 2 +
2
7
𝑅2 −
2
7
𝑅1 +
2
7
𝐴1 −
2
7
𝐴2 
𝑅3 = 6 −
5
7
𝑅1 +
5
7
𝐴1 −
2
7
𝑅2 +
2
7
𝐴2 
𝑧′ = 0 + 𝐴1 + 𝐴2 
 
Note que as variáveis artificiais saíram da base. Caso isto não acontecesse é porque o 
modelo original é inviável. O dicionário ótimo da Fase I gera o seguinte dicionário para a Fase II: 
𝑥2 = 5 +
5
7
𝑅1 +
2
7
𝑅2 
𝑥1 = 2 +
2
7
𝑅2 −
2
7
𝑅1 
𝑅3 = 6 −
5
7
𝑅1 −
2
7
𝑅2 
𝑧 = 9 +
6
7
𝑅2 +
1
7
𝑅1 
 
O dicionário prévio foi construído da seguinte forma: 
• As variáveis artificiais do dicionário ótimo da Fase I são retiradas. 
• A função objetivo volta para 𝑧, que dever ser escrita em função das variáveisnão 
básicas. 
 
Com base no dicionário prévio, aplica-se os passos 3 e 4 do método Simplex básico para 
obtenção da solução ótima do problema original. No exemplo em questão, o dicionário já é o 
ótimo. Logo, a solução ótima é 𝑥1 = 2 e 𝑥2 = 5, com função objetivo 𝑧 = 9. 
7 Informações sobre as próximas aulas 
Na próxima aula será discutida a Teoria da Dualidade em Programação Linear, que 
permite a obtenção do chamado modelo dual de qualquer modelo PL. As soluções viáveis deste 
modelo geram limites para o modelo original e a solução ótima do modelo dual permite também a 
obtenção da solução ótima do modelo original. 
Referências 
Chvatal, V., & Chvatal, V. (1983). Linear programming. Macmillan. 
Hillier, F. S., & Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw Hill Brasil.