Aula 04 - Soluções Básicas

Prévia do material em texto

CURSO: Engenharia de Produção 
DISCIPLINA: Pesquisa Operacional I 
PROFESSORES 
Marcos Costa Roboredo 
Felipe Pereira do Carmo 
Aula 4 – Soluções Básicas de um Problema de Programação Linear 
Objetivos: 
Ao final desta aula, o estudante será capaz de: 
1. Entender o conceito do que são soluções básicas em modelos PL e como encontrá-las. 
2. Encontrar a solução ótima de modelos PL não ilimitados através do método da 
enumeração das soluções básicas viáveis. 
1. Introdução 
Na aula passada, foi visto como transformar um modelo PL para a forma padrão. Neste formato, 
as restrições do modelo (com exceção das de não-negatividade) são de igualdade, ou seja, formam 
um sistema de equações lineares. Seja 𝑛 o número de variáveis e 𝑚 o número de equações deste 
sistema. Quando zeram-se arbitrariamente 𝑛 − 𝑚 variáveis e resolve-se o sistema resultante, 
obtém-se uma solução básica (base) para o modelo. Nesta aula é mostrado que a solução ótima de 
um modelo PL não ilimitado é dada por uma solução básica viável. Assim, torna-se possível a 
obtenção de tal solução através da enumeração dessas soluções. 
É importante ressaltar que esta aula assume que diversos conceitos de álgebra linear são 
conhecidos pelo estudante. Dentre os quais, destacam-se: 
• A identificação de quando um sistema linear é determinado, indeterminado ou 
inconsistente. 
• A resolução de sistemas de equações lineares. 
2. Soluções básicas 
Conforme já visto em aulas anteriores, um modelo PL na forma padrão tem a forma 
 
max max (min) 𝑐𝑇𝑥 
s.a s.a.: 𝐴𝑥 = 𝑏 
𝑥 ≥ 0 
 Note que as restrições definem um sistema linear 𝐴𝑥 = 𝑏 com o complicador 𝑥 ≥ 0. 
 
Assume-se daqui para frente que no sistema 𝐴𝑥 = 𝑏 o número de variáveis 𝑚 é maior que o 
número de equações 𝑛, que é o que acontece para grande maioria dos modelos PL. Assim, o 
sistema 𝐴𝑥 = 𝑏 é inconsistente (não possui solução) ou indeterminado (possui infinitas soluções). 
 
Algumas soluções de 𝐴𝑥 = 𝑏 (quando existem) podem ser obtidas zerando-se 𝑛 − 𝑚 variáveis e 
resolvendo o sistema linear resultante. Estas soluções recebem um nome especial e são chamadas 
de soluções básicas. As 𝑛 − 𝑚 variáveis zeradas são chamadas de variáveis não-básicas e as 
demais 𝑛 variáveis são chamadas de variáveis básicas. 
 
Durante o processo de obtenção de uma solução básica, o sistema resultante pode ser de dois tipos: 
 
1. Determinado com todas as variáveis assumindo valores não negativos. 
2. Inconsistente ou indeterminado com alguma variável assumindo valor negativo. 
 
No caso 1, diz-se que foi encontrada uma solução básica viável enquanto que no caso 2 diz-se 
que foi encontrada uma solução básica é inviável. 
 
Definição 4.1: Seja 𝐴𝑥 = 𝑏 um sistema associado a restrições de um modelo PL. Uma solução 
do sistema é dita básica quando é obtida zerando-se 𝑛 − 𝑚 variáveis e resolvendo o sistema linear 
resultante. 
 
Definição 4.2: Em uma solução básica, as 𝑛 − 𝑚 variáveis zeradas são chamadas de variáveis 
não-básicas e as demais 𝑛 variáveis são chamadas de variáveis básicas ou simplesmente base. 
 
 
Durante o processo de obtenção de uma solução básica, se o sistema resultante for viável e todas 
as variáveis assumirem apenas valores não negativos, tem-se uma solução básica viável. 
 
 
 
Durante o processo de obtenção de uma solução básica, o sistema resultante pode ser inconsistente 
ou gerar uma solução com alguma variável negativa. Neste caso, diz-se que a solução básica é 
inviável. 
 
 
Os conceitos prévios são reforçados agora através do Exemplo 4.1. 
 
Exemplo 4.1 Para o seguinte PPL, encontre todas as soluções básicas, classificando cada uma em 
viável ou inviável. 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a.: 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥1 , 𝑥2 ≥ 0 
 
Solução: O primeiro passo é colocar o modelo na forma padrão. Para isso, são criadas duas 
variáveis de folga não negativas, que são denotadas aqui por 𝑅1 e 𝑅2. 
 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 + 0𝑅1 + 0𝑅2 
s.a. 3𝑥1 + 2𝑥2 + 𝑅1 = 90 
𝑥1 + 𝑅2 = 25 
𝑥1, 𝑥2, 𝑅1, 𝑅2 ≥ 0 
O sistema associado as restrições do problema é: 
 
{
3𝑥1 − 2𝑥2 + 𝑅1 = 90
𝑥1 + 𝑅2 = 25
 
 
O sistema prévio possui 4 variáveis e 2 equações. Logo, cada solução básica é obtida zerando-se 
4 − 2 = 2 variáveis e resolvendo o sistema resultante. A Tabela 4.1 apresenta tais soluções. 
 
Tabela 4.1 - Soluções básicas do Exemplo 4.1 
Nº Variáveis 
Não 
básicas 
(zeradas) 
Variáveis 
básicas 
(base) 
Sistema 
Resultante 
Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) 
Solução 
básica 
viável ou 
inviável? 
1 𝑥1, 𝑥2 𝑅1, 𝑅2 
{
𝑅1 = 90
𝑅2 = 25
 
(0, 0, 90, 25) Viável 
2 𝑥1, 𝑅1 𝑥2, 𝑅2 
{
2𝑥2 = 90
𝑅2 = 25
 
(0, 45, 0, 25) Viável 
3 𝑥1, 𝑅2 𝑥2, 𝑅1 {
2𝑥2 + 𝑅1 = 90
0 = 25
 Sistema 
inconsistente 
Inviável 
4 𝑥2, 𝑅1 𝑥1, 𝑅2 
{
3𝑥1 = 90
𝑥1 + 𝑅2 = 25
 
(30,0,0, −5) Inviável 
5 𝑥2, 𝑅2 𝑥1, 𝑅1 
{
3𝑥1 + 𝑅1 = 90
𝑥1 = 25
 
(25, 0, 15, 0) Viável 
6 𝑅1, 𝑅2 𝑥1, 𝑥2 
{
3𝑥1 + 2𝑥2 = 90
𝑥1 = 25
 
(25, 7,5, 0, 0) Viável 
 
Note que a solução básica encontrada é classificada como viável apenas no caso em que todas as 
variáveis assumem valores não negativos após a resolução do sistema. Assim, o modelo PL prévio 
possui 4 soluções básicas viáveis e 2 soluções básicas inviáveis. 
 
Observe agora a região de soluções viáveis do Exemplo 4.1: 
 
 
 
Note que existe uma relação entre as soluções básicas e os pontos extremos da região de soluções 
viáveis. A Tabela 4.2 a seguir mostra tal relação: 
 
Tabela 4.2 – Relação entre soluções básicas e pontos extremos 
Nº Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) 
Viável ou inviável? Ponto extremo associado 
1 (0, 0, 90, 25) Viável 𝐴 = (0,0) 
2 (0, 45, 0, 25) Viável 𝐷 = (0,45) 
3 Sistema inconsistente Inviável - 
4 (30,0,0, −5) Inviável (30,0) 
5 (25, 0, 15, 0) Viável 𝐵 = (25,0) 
6 (25, 7,5, 0, 0) Viável 𝐶 = (25, 7,5) 
 
Note que cada solução básica viável está associada a um ponto extremo viável. Note ainda que o 
modelo apresentou duas soluções básicas inviáveis. Até mesmo a solução básica inviável 
(𝑥1, 𝑥2, 𝑥3, 𝑅1, 𝑅2) = (30,0,0, −5) pode ser encontrada graficamente no ponto (30,0), que é um 
ponto extremo inviável. Quando a solução básica nº 3 da tabela é investigada, as variáveis 𝑥1 e 𝑅2 
são zeradas e um sistema inconsistente foi gerado. Isto acontece porque que a reta 𝑥1 = 25 não 
toca o eixo vertical. Caso tocasse, geraria um outro ponto extremo (viável ou não). 
 
Agora, alguns teoremas importantes são apresentados. Estes teoremas não são aqui demonstrados 
matematicamente, mas são discutidos com mais detalhes nas referências indicadas nesta Aula. 
 
Teorema 4.1: O número de soluções básicas de um PPL é finito. 
 
Teorema 4.2: Cada ponto extremo viável está associado uma solução básica viável e vice-versa. 
 
Teorema 4.3: A solução ótima de um PPL viável e não ilimitado é uma solução básica viável. 
 
O Teorema 4.1 diz que o número de soluções básicas de um modelo PL é finito. Sendo mais 
específico, o número de soluções básicas é dado por no máximo: 
 
(
𝑛
𝑛 − 𝑚
) =
𝑛!
𝑚! (𝑛 − 𝑚)!
 
 
Além disso, o Teorema 4.3 diz que a solução ótima de um modelo PL viável e não ilimitado está 
associado a uma solução básica viável. Assim, uma maneira de encontrar a solução ótima de um 
modelo deste tipo é enumerando todas as soluções básicas viáveis, retornando aquela com maior 
valor (problemas de maximização) ou menor valor (problemas de minimização) na função 
objetivo. Este método é agora aplicado ao Exemplo 4.1. Este exemplo não é ilimitado e é de 
maximização. Além disso, o modelo gerou quatro soluções básicas viáveis. Pode-se então verificar 
qual delas gera maior valor para função objetivo: 
 
Solução básica viável 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) 
Valor na função objetivo 
𝑧 = 20𝑥1 + 10𝑥2 + 0𝑅1 + 0𝑅2 
(0, 0, 90, 25) 0 
(0, 45, 0, 25) 450 
(25, 0, 15, 0) 500 
(25, 7,5, 0, 0) 575Assim, a solução ótima é (𝑥1, 𝑥2, 𝑥3, 𝑅1, 𝑅2) = (25, 7,5, 0, 0), que gera 𝑧 = 575. 
 
3. Soluções básicas e o método Simplex 
 
Apesar do método de enumeração das soluções básicas viáveis sempre gerar a solução ótima de 
um modelo PL viável não ilimitado, ele não é o mais indicado pois: 
 
• O número de soluções básicas viáveis pode ser grande e de difícil enumeração até mesmo 
para um computador. 
• Para se obter cada solução básica viável, faz-se necessário a resolução de um sistema linear. 
• É aplicável apenas em modelos não ilimitados. 
 
Para contornar os problemas prévios, existe o método Simplex. Tal método também percorre 
soluções básicas viáveis, uma de cada vez, porém com as seguintes vantagens: 
 
• O algoritmo é capaz de identificar se o modelo é ilimitado. 
• Não é necessário enumerar todas as soluções básicas viáveis. 
• Os cálculos são facilmente atualizados de uma solução básica para outra. 
 
Na próxima aula, todos os detalhes do método Simplex serão dados. 
 
4. Exercícios 
 
Exercício 4.1 Considere os modelos dos Exercícios 2.1 e 2.2 (Aula 2): 
 
Modelo do Exercício 2.1 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 ≤ 3; 
𝑥2 ≤ 10; 
3𝑥1 + 2𝑥2 ≤ 14; 
𝑥1 ≥ 0; 
𝑥2 ≥ 0 
Modelo do Exercício 2.2 
 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 
s.a.: 𝑥1 + 𝑥2 = 9; 
−2𝑥1 + 𝑥2 ≤ 6; 
−𝑥1 + 𝑥2 ≥ 2; 
𝑥1 ≥ 0; 
𝑥2 ≥ 0 
 
Para cada um dos modelos prévios, faça uma tabela descrevendo as soluções básicas do modelo, 
discriminando as variáveis básicas e não-básicas e classificando cada solução encontrada como 
viável ou inviável. Para cada solução básica viável, encontre o valor na função objetivo. Ao final, 
aponte a solução ótima do modelo. 
 
Solução comentada: O modelo associado ao Exercício 2.1 já 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 
O sistema linear associado ao modelo possui 5 variáveis e 3 restrições. Assim, o número de 
soluções básicas é: 
(
5
5 − 3
) =
5!
3! 2!
= 10 
Cada uma destas 10 soluções pode ser obtida zerando-se 5-3=2 variáveis e resolvendo o sistema 
resultante. 
Nº Variáveis 
Não 
básicas 
(zeradas) 
Variáveis 
básicas 
(base) 
Solução do sistema resultante Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) 
Solução 
básica 
viável ou 
inviável? 
Valor da 
função 
objetivo 𝑧 
1 𝑥1, 𝑥2 𝑅1, 𝑅2, 𝑅3 𝑅1 = 3, 𝑅2 = 10, 𝑅3 = 14 (0, 0, 3, 10, 14) Viável 𝑧 = 0 
2 𝑥1, 𝑅1 𝑥2, 𝑅2, 𝑅3 𝑥2 = 3, 𝑅2 = 7, 𝑅3 = 8 (0, 3, 0, 7, 8) Viável 𝑧 = 3 
3 𝑥1, 𝑅2 𝑥2, 𝑅1, 𝑅2 𝑥2 = 10, 𝑅1 = −7, 𝑅3 = −6 (0, 10, -7, 0, -6) Inviável - 
4 𝑥1, 𝑅3 𝑥2, 𝑅1, 𝑅2 𝑥2 = 7, 𝑅2 = 3, 𝑅1 = −4 (0, 7, -4, 3, 0) Inviável - 
5 𝑥2, 𝑅1 𝑥1, 𝑅2, 𝑅3 
𝑥1 = −
3
2
, 𝑅2 = 10, 𝑅3 =
37
2
 (-
3
2
, 0, 0, 10, 
37
2
) Inviável - 
6 𝑥2, 𝑅2 𝑥1, 𝑅1, 𝑅3 Inconsistente - Inviável - 
7 𝑥2, 𝑅3 𝑥1, 𝑅1, 𝑅2 
𝑥1 =
14
3
, 𝑅1 =
37
3
, 𝑅2 = 10 (
14
3
, 0, 
37
3
, 10, 0) Viável 𝑧 = 14 
8 𝑅1, 𝑅2 𝑥1, 𝑥2, 𝑅3 
𝑥1 =
7
2
, 𝑥2 = 10, 𝑅3 = −
33
2
 (
7
2
, 10, 0,0, −
33
2
) Inviável - 
9 𝑅1, 𝑅3 𝑥1, 𝑥2, 𝑅2 
𝑥1 =
8
7
, 𝑥2 =
37
7
, 𝑅2 =
53
7
 (
8
7
,
37
7
, 0,
53
7
, 0) 
Viável 
𝑧 =
61
7
 
10 𝑅2, 𝑅3 𝑥1, 𝑥2, 𝑅1 𝑥1 = −2, 𝑥2 = 10, 𝑅1 = −1 (-2, 10, -1, 0, 0) Inviável - 
 
Uma vez que o problema é de maximização, a solução ótima é a solução básica viável com maior 
valor na função objetivo 𝑧. Assim, a solução ótima é a de número 7, com valores 𝑥1 = 14, 𝑥2 =
0, 𝑅1 =
37
7
, 𝑅2 = 10, 𝑅3 = 0 e que gera um valor 𝑧 = 14. 
No Exercício 2.1 da Aula 2, a região de soluções viáveis do modelo foi desenhada: 
 
Repare que cada solução básica que não gerou um sistema inconsistente está associada a um ponto 
extremo (interseção de restrições) e, quando a solução básica é viável, o ponto extremo associado 
também é viável. 
Nº Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2, 𝑅3) 
Solução básica viável 
ou inviável? 
Ponto extremo 
associado 
(𝑥1, 𝑥2) 
1 (0, 0, 3, 10, 14) Viável 𝐴 = (0,0) 
2 (0, 3, 0, 7, 8) Viável 𝐷 = (0,3) 
3 (0, 10, -7, 0, -6) Inviável (0,10) 
4 (0, 7, -4, 3, 0) Inviável (0,7) 
5 (-
3
2
, 0, 0, 10, 
37
2
) Inviável (-
3
2
, 0) 
6 Sistema inconsistente Inviável - 
7 (
14
3
, 0, 
37
3
, 10, 0) Viável 
𝐵 = (
14
3
, 0) 
8 (
7
2
, 10, 0,0, −
33
2
) Inviável 
(
7
2
, 10) 
9 
(
8
7
,
37
7
, 0,
53
7
, 0) 
Viável 
𝐶 = (
8
7
,
37
7
) 
10 (-2, 10, -1, 0, 0) Inviável (−2,10) 
 
O modelo associado ao Exercício 2.2 já na forma padrão é: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 
s.a. 𝑥1 + 𝑥2 = 9 
−2𝑥1 + 𝑥2 + 𝑅1 = 6 
−𝑥1 + 𝑥2 − 𝑅2 = 2 
𝑥1 , 𝑥2, 𝑅1, 𝑅2 ≥ 0 
O modelo na forma padrão possui 4 variáveis e 3 restrições. Assim, o número de soluções básicas 
é 
(
4
4 − 3
) =
4!
3! 1!
= 4 
Cada uma destas 4 soluções pode ser obtida zerando-se 4-3=1 variável e resolvendo o sistema 
resultante. 
Nº Variáveis 
Não 
básicas 
(zeradas) 
Variáveis 
básicas 
Solução do sistema resultante Solução Básica 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) 
Solução 
básica 
viável ou 
inviável? 
Valor da 
função 
objetivo 𝑧 
1 𝑥1 𝑥2, 𝑅1, 𝑅2 𝑥2 = 9, 𝑅1 = −3, 𝑅2 = 7 (0, 9, -3, 7) Inviável - 
2 𝑥2 𝑥1, 𝑅1, 𝑅2 𝑥1 = 9, 𝑅1 = 24, 𝑅2 = −11 (9, 0, 24, -11) Inviável - 
3 𝑅1 𝑥1, 𝑥2, 𝑅2 𝑥1 = 1, 𝑥2 = 8, 𝑅2 = 5 (1, 8, 0, 5) Viável 𝑧 = 26 
4 𝑅2 𝑥1, 𝑥2, 𝑅1 
𝑥1 =
7
2
, 𝑥2 =
11
2
, 𝑅1 =
15
2
 (
7
2
,
11
2
,
15
2
, 0) 
Viável 𝑧 = 23,5 
 
Uma vez que o problema é de minimização, a solução ótima é a solução básica viável com menor 
valor na função objetivo 𝑧. Assim, a solução ótima é a de número 4, com valores 𝑥1 =
7
2
, 𝑥2 =
11
2
, 𝑅1 =
15
2
, 𝑅2 = 0 e que gera um valor 𝑧 = 23,5. 
Na Aula 2, a região de soluções viáveis do modelo foi encontrada: 
 
 
 
Note que a região possui 2 pontos extremos viáveis A e B, que estão associados as soluções básicas 
viáveis 3 e 4, respectivamente. Além disso, as duas soluções básicas inviáveis estão associadas a 
pontos extremos inviáveis do modelo. 
5. Conclusão 
Esta aula apresentou o importante conceito de soluções básicas em modelos PL no formato padrão 
com 𝑛 variáveis e 𝑚 restrições, que são obtidas através da resolução de sistemas de equações 
lineares quando 𝑛 − 𝑚 variáveis são arbitrariamente zeradas. Foi visto ainda que cada solução 
básica pode ser classificada em viável ou inviável e que a solução ótima do modelo está associada 
a uma solução básica viável. 
Resumo 
Foi visto em aulas anteriores que um modelo PL encontra-se na forma padrão quando todas as 
variáveis são não negativas e todas as restrições são de igualdade (exceto as de não negatividade). 
Um exemplo de modelo PL na forma padrão é o que segue: 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 + 0𝑅1 + 0𝑅2 
s.a. 3𝑥1 + 2𝑥2 + 𝑅1 = 90 
𝑥1 + 𝑅2 = 25 
𝑥1, 𝑥2, 𝑅1, 𝑅2 ≥ 0 
Note que este modelo possui 4 variáveis (𝑥1, 𝑥2, 𝑅1, 𝑅2) e 2 restrições de igualdade. Para obter-se 
uma das chamadas soluções básicas do modelo, deve-se então zerar 4 - 2 = 2 variáveis do modelo 
e resolver o sistema resultante. Zerando-se, por exemplo, 𝑥1 e 𝑅1, obtém-se o seguinte sistema: 
 
{
2𝑥2 = 90
𝑅2 = 25
 
A solução do sistema prévio é 𝑥2 = 45 e 𝑅2 = 25. Assim, uma solução básica do modelo é 
(𝑥1, 𝑥2, 𝑅1, 𝑅2) = (0,45,0,25) 
Como o sistema resultante foi viável e nenhuma variável assumiu valor negativo, pode-se afirmar 
que a solução é uma solução básica viável. 
Nesta aula, foi visto ainda que a solução ótima de um modelo PL não ilimitado está sempre 
associada a uma solução básica viável. Assim, uma maneira de se resolver este tipo de modelo é 
enumerando todas as soluções básicas viáveis e retornando aquela que mais otimiza a função 
objetivo. 
Informações sobre as próximas aulas 
Na próxima aula o principal método de resolução de PPLs conhecido como será detalhado. Tal 
método é conhecido como método Simplex. Este método percorre iterativamente soluções básicas 
viáveis.Em cada iteração, é verificado se a solução corrente é ótima ou não. Em caso de resposta 
positiva, o método termina. 
Referências 
Chvatal, V., & Chvatal, V. (1983). Linear programming. Macmillan. 
Hillier, F. S., & Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw Hill Brasil.