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.