Baixe Apresentação TCC LUCYAN e outras Teses (TCC) em PDF para Matemática, somente na Docsity! Introdução Modelagem Método Gráfico Método Simplex O Problema de Programação Linear José Lucyan Mendonça de Almeida Universidade Federal de Alagoas Instituto de Matemática Apresentação do Trabalho de Conclusão do Curso de Licenciatura em Matemática Maceió-AL, Março de 2010 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Banca Examinadora Prof. Dimas Martínez Morera (Orientador) Prof. Adán José Corcho Fernández Profa. Luana Giarola Contiero José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex O Problema do Caixeiro Viajante: Origina-se de um jogo proposto em 1857 por Willian Rowan Hamilton denominado Around the World feito sobre um dodecaedro. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex O Problema da Dieta: É associado a uma dieta para uma redução calorica, em que as quantidades de certos alimentos devem ser ingeridos diariamente de modo que alguns requisitos nutricionais sejam rigorosamente obedecidos a um custo mínimo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = c1x1 + c2x2 + . . . cnxn satisfazendo às restrições: a11x1 + a12x2 + . . . + a1nxn ≤ b1 a21x1 + a22x2 + . . . + a2nxn ≤ b2 ... ... ... ... am1x1 + am2x2 + . . . + amnxn ≤ bm x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = n∑ j=1 cjxj satisfazendo as restrições: n∑ j=1 aijxj ≤ bi , (i = 1,2, . . . ,m) e, xj ≥ 0 , (j = 1,2, . . . ,n). José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Ou ainda na notação matricial. Sejam: A =  a11 a12 · · · a1n a21 a22 · · · a2n ... ... . . . ... am1 am2 · · · amn , x =  x1 x2 ... xn , b =  b1 b2 ... bn  e, c = [ c1 c2 · · · cn ] . José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = cx sujeito a Ax ≤ b e, x ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Objetivo Minimizar f (x) = c1x1 + c2x2 + . . . cnxn , de modo que x1, x2, x3, . . . , xn satisfaça as restrições: a11x1 + a12x2 + . . . + a1nxn ≥ b1 a21x1 + a22x2 + . . . + a2nxn ≥ b2 ... ... ... ... am1x1 + am2x2 + . . . + amnxn ≥ bm e as condições de não-negatividade: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo 1 f (x) = c1x1 + c2x2 + . . . cnxn representa o custo bruto em Reais da quantidade do alimento consumido. 2 As restrições indicam que o total da vitamina i obtida dos n alimentos deve ser maior ou igual que a quantidade mínima bi desta vitamina. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Maximizar f (x) = c1x1 + c2x2 sujeita as restrições:  a1,1x1 + a1,2x2 ≤ b1 a2,1x1 + a2,2x2 ≤ b2 ... ... ar ,1x1 + ar ,2x2 ≤ br e as condições de não-negatividade x1 ≥ 0 e x2 ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Figura: Duas de suas retas de nível da função f (x). José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Definição Dizemos que qualquer atribição de valores para as variáveis do modelo é uma Solução. Definição A solução que satisfaz todas as restrições do modelo considerado é definida como Solução Compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Definição Dizemos que a solução pertencente à região compatível do modelo e que otimiza o valor da função objetivo é a Solução Ótima. Definição A solução que não satisfaz alguma das restrições do modelo considerado é definida como Solução Incompatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Figura: O ponto S maximiza a função objetivo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 1◦ Caso: José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 2◦ Caso: José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 Possíveis Regiões Compatíveis no R2 1 Pode ser vazia. 2 Ter apenas um ponto. 3 Ser um polígono convexo. 4 Região poligonal convexa ilimitada. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Maximizar f (x) = 3x1 + 5x2 s.a: x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 x1 ≥ 0 x2 ≥ 0 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Figura: Região que satisfaz todas as restrições do problema. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Figura: O ponto C maximiza a função objetivo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Método Simplex ( Dantzing - 1947) José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Sejam A1,A2, . . . ,An pontos pertencentes ao Rm e α1, α2, . . . , αn ∈ R+ tal que n∑ i=1 αi = 1. Dizemos que o ponto b = αiA1 + α2A2 + . . .+ αnAn é uma Combinação Convexa dos pontos A1,A2, . . . ,An. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Figura: Somente as duas primeiras figuras são convexas. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Dados a1,a2, . . . ,an,b ∈ R, chamamos de Semi-espaço a reunião dos pontos pertencentes ao conjunto X = {(x1, x2, . . . , xn) ∈ Rn; a1x1 + a2x2 + · · ·+ anxn ≤ b}. Lema Todo Semi-espaço é um conjunto convexo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Lema Sejam C1,C2, . . . ,Cn conjuntos convexos, então C = ∩ni=1Ci é convexo. Teorema O conjunto de todas as soluções compatíveis do problema de programação linear é um conjunto convexo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Chamamos de Solução Básica à solução obtida quando em um conjunto com m equações linearmente independentes com n incógnitas, tal que n > m, consideramos o conjunto de equações onde n −m variáveis são anuladas e as que sobraram são encontradas através da resolução do sistema de equações. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Toda solução compatível básica do sistema Ax = b é um ponto extremo do conjunto das soluções compatíveis, ou seja, do conjunto convexo do teorema anterior. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Considere o conjunto convexo formado por Ax = b e x ≥ 0, (1) ou seja:  a11 · · · a1m a1m+1 · · · a1n a21 · · · a2m a2m+1 · · · a2n · · · · · · · · · · · · · · · · · · am1 · · · amm amm+1 · · · amn   x1 x2 ... xn  =  b1 b2 ... bn  . (2) José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Se a função objetivo admite um máximo (mínimo) finito, então ao menos uma solução ótima é um ponto extremo do conjunto convexo do 1◦ teorema. Teorema Se a função objetivo assume o máximo (mínimo) em mais de um ponto extremo, então assume o mesmo valor para qualquer combinação convexa desses pontos extremos. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Se a função objetivo admite um máximo (mínimo) finito, então ao menos uma solução ótima é um ponto extremo do conjunto convexo do 1◦ teorema. Teorema Se a função objetivo assume o máximo (mínimo) em mais de um ponto extremo, então assume o mesmo valor para qualquer combinação convexa desses pontos extremos. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Definição As variáveis acrescentadas em inequações para torná-las equações são denominadas Variáveis de Folga. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Seja um problema de programação linear na sua forma matricial: Minimizar f (x) = cx s.a Ax = b e x ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Podemos transformar a equação da função objetivo f (x) = c1x1 + c2x2 + . . .+ cnxn na equação f (x)− c1x1 − c2x2 − · · · − cnxn = 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Equação f (x) x1 x2 · · · xn b 0 1 −c1 −c2 · · · −cn 0 1 0 a11 a12 · · · a1n b1 2 0 a21 a22 · · · a2n b2 ... ... ... ... . . . ... ... n 0 am1 am2 · · · amn bm José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex A solução básica inicial é dada por: xi = bi , se 1 ≤ i ≤ m e xi = 0, se m + 1 ≤ i ≤ n. f (x) + csxs + . . .+ cnxn = f (x). Logo, f (x) = f (x). E além disso, b ≥ 0, por se tratar de uma solução compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex A solução básica inicial é dada por: xi = bi , se 1 ≤ i ≤ m e xi = 0, se m + 1 ≤ i ≤ n. f (x) + csxs + . . .+ cnxn = f (x). Logo, f (x) = f (x). E além disso, b ≥ 0, por se tratar de uma solução compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex f (x) = f (x)− csxs − · · · − cnxn. Se c j ≤ 0 para todo o j /∈ J então o valor da função objetivo em qualquer outra solução compatível básica é maior ou igual a f (x). Senão, seja ck = max{c j ; c j > 0}, xk é a nova variável básica. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Se aik ≤ 0 para todo 1 ≤ i ≤ m então α pode aumentar indefinidamente. Se pelo contrário existir um i ∈ {1, . . . ,m} tal que aik > 0 então α tem que satisfazer a condição: α ≤ biaik ,∀ i ∈ {1, . . . ,m} tal que aik > 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex O Problema de Programação Linear José Lucyan Mendonça de Almeida Universidade Federal de Alagoas Instituto de Matemática Apresentação do Trabalho de Conclusão do Curso de Licenciatura em Matemática Maceió-AL, Março de 2010 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Banca Examinadora Prof. Dimas Martínez Morera (Orientador) Prof. Adán José Corcho Fernández Profa. Luana Giarola Contiero José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex O Problema do Caixeiro Viajante: Origina-se de um jogo proposto em 1857 por Willian Rowan Hamilton denominado Around the World feito sobre um dodecaedro. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex O Problema da Dieta: É associado a uma dieta para uma redução calorica, em que as quantidades de certos alimentos devem ser ingeridos diariamente de modo que alguns requisitos nutricionais sejam rigorosamente obedecidos a um custo mínimo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = c1x1 + c2x2 + . . . cnxn satisfazendo às restrições: a11x1 + a12x2 + . . . + a1nxn ≤ b1 a21x1 + a22x2 + . . . + a2nxn ≤ b2 ... ... ... ... am1x1 + am2x2 + . . . + amnxn ≤ bm x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = n∑ j=1 cjxj satisfazendo as restrições: n∑ j=1 aijxj ≤ bi , (i = 1,2, . . . ,m) e, xj ≥ 0 , (j = 1,2, . . . ,n). José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Ou ainda na notação matricial. Sejam: A =  a11 a12 · · · a1n a21 a22 · · · a2n ... ... . . . ... am1 am2 · · · amn , x =  x1 x2 ... xn , b =  b1 b2 ... bn  e, c = [ c1 c2 · · · cn ] . José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Modelo de Programação Linear Maximizar ou Minimizar f (x) = cx sujeito a Ax ≤ b e, x ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Objetivo Minimizar f (x) = c1x1 + c2x2 + . . . cnxn , de modo que x1, x2, x3, . . . , xn satisfaça as restrições: a11x1 + a12x2 + . . . + a1nxn ≥ b1 a21x1 + a22x2 + . . . + a2nxn ≥ b2 ... ... ... ... am1x1 + am2x2 + . . . + amnxn ≥ bm e as condições de não-negatividade: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo 1 f (x) = c1x1 + c2x2 + . . . cnxn representa o custo bruto em Reais da quantidade do alimento consumido. 2 As restrições indicam que o total da vitamina i obtida dos n alimentos deve ser maior ou igual que a quantidade mínima bi desta vitamina. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Maximizar f (x) = c1x1 + c2x2 sujeita as restrições:  a1,1x1 + a1,2x2 ≤ b1 a2,1x1 + a2,2x2 ≤ b2 ... ... ar ,1x1 + ar ,2x2 ≤ br e as condições de não-negatividade x1 ≥ 0 e x2 ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Figura: Duas de suas retas de nível da função f (x). José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Definição Dizemos que qualquer atribição de valores para as variáveis do modelo é uma Solução. Definição A solução que satisfaz todas as restrições do modelo considerado é definida como Solução Compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Definição Dizemos que a solução pertencente à região compatível do modelo e que otimiza o valor da função objetivo é a Solução Ótima. Definição A solução que não satisfaz alguma das restrições do modelo considerado é definida como Solução Incompatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Interpretação Geométrica no R2 Figura: O ponto S maximiza a função objetivo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 1◦ Caso: José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 2◦ Caso: José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Possíveis Regiões Compatíveis no R2 Possíveis Regiões Compatíveis no R2 1 Pode ser vazia. 2 Ter apenas um ponto. 3 Ser um polígono convexo. 4 Região poligonal convexa ilimitada. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Maximizar f (x) = 3x1 + 5x2 s.a: x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 x1 ≥ 0 x2 ≥ 0 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Figura: Região que satisfaz todas as restrições do problema. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Figura: O ponto C maximiza a função objetivo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Método Simplex ( Dantzing - 1947) José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Sejam A1,A2, . . . ,An pontos pertencentes ao Rm e α1, α2, . . . , αn ∈ R+ tal que n∑ i=1 αi = 1. Dizemos que o ponto b = αiA1 + α2A2 + . . .+ αnAn é uma Combinação Convexa dos pontos A1,A2, . . . ,An. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Figura: Somente as duas primeiras figuras são convexas. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Dados a1,a2, . . . ,an,b ∈ R, chamamos de Semi-espaço a reunião dos pontos pertencentes ao conjunto X = {(x1, x2, . . . , xn) ∈ Rn; a1x1 + a2x2 + · · ·+ anxn ≤ b}. Lema Todo Semi-espaço é um conjunto convexo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Lema Sejam C1,C2, . . . ,Cn conjuntos convexos, então C = ∩ni=1Ci é convexo. Teorema O conjunto de todas as soluções compatíveis do problema de programação linear é um conjunto convexo. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Definição Chamamos de Solução Básica à solução obtida quando em um conjunto com m equações linearmente independentes com n incógnitas, tal que n > m, consideramos o conjunto de equações onde n −m variáveis são anuladas e as que sobraram são encontradas através da resolução do sistema de equações. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Toda solução compatível básica do sistema Ax = b é um ponto extremo do conjunto das soluções compatíveis, ou seja, do conjunto convexo do teorema anterior. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Considere o conjunto convexo formado por Ax = b e x ≥ 0, (1) ou seja:  a11 · · · a1m a1m+1 · · · a1n a21 · · · a2m a2m+1 · · · a2n · · · · · · · · · · · · · · · · · · am1 · · · amm amm+1 · · · amn   x1 x2 ... xn  =  b1 b2 ... bn  . (2) José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração: Suponha que x não seja um ponto extremo do conjunto Ax = b tal que x ≥ 0. Logo x = αy + (1− α)z; 0 ≤ α ≤ 1 (3) com Ay = b, Az = b, y ≥ 0 e z ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Se a função objetivo admite um máximo (mínimo) finito, então ao menos uma solução ótima é um ponto extremo do conjunto convexo do 1◦ teorema. Teorema Se a função objetivo assume o máximo (mínimo) em mais de um ponto extremo, então assume o mesmo valor para qualquer combinação convexa desses pontos extremos. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Teoremas Fundamentais Teorema Se a função objetivo admite um máximo (mínimo) finito, então ao menos uma solução ótima é um ponto extremo do conjunto convexo do 1◦ teorema. Teorema Se a função objetivo assume o máximo (mínimo) em mais de um ponto extremo, então assume o mesmo valor para qualquer combinação convexa desses pontos extremos. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Definição As variáveis acrescentadas em inequações para torná-las equações são denominadas Variáveis de Folga. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Seja um problema de programação linear na sua forma matricial: Minimizar f (x) = cx s.a Ax = b e x ≥ 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Podemos transformar a equação da função objetivo f (x) = c1x1 + c2x2 + . . .+ cnxn na equação f (x)− c1x1 − c2x2 − · · · − cnxn = 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Equação f (x) x1 x2 · · · xn b 0 1 −c1 −c2 · · · −cn 0 1 0 a11 a12 · · · a1n b1 2 0 a21 a22 · · · a2n b2 ... ... ... ... . . . ... ... n 0 am1 am2 · · · amn bm José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex A solução básica inicial é dada por: xi = bi , se 1 ≤ i ≤ m e xi = 0, se m + 1 ≤ i ≤ n. f (x) + csxs + . . .+ cnxn = f (x). Logo, f (x) = f (x). E além disso, b ≥ 0, por se tratar de uma solução compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex A solução básica inicial é dada por: xi = bi , se 1 ≤ i ≤ m e xi = 0, se m + 1 ≤ i ≤ n. f (x) + csxs + . . .+ cnxn = f (x). Logo, f (x) = f (x). E além disso, b ≥ 0, por se tratar de uma solução compatível. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex f (x) = f (x)− csxs − · · · − cnxn. Se c j ≤ 0 para todo o j /∈ J então o valor da função objetivo em qualquer outra solução compatível básica é maior ou igual a f (x). Senão, seja ck = max{c j ; c j > 0}, xk é a nova variável básica. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Se aik ≤ 0 para todo 1 ≤ i ≤ m então α pode aumentar indefinidamente. Se pelo contrário existir um i ∈ {1, . . . ,m} tal que aik > 0 então α tem que satisfazer a condição: α ≤ biaik ,∀ i ∈ {1, . . . ,m} tal que aik > 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Se aik ≤ 0 para todo 1 ≤ i ≤ m então α pode aumentar indefinidamente. Se pelo contrário existir um i ∈ {1, . . . ,m} tal que aik > 0 então α tem que satisfazer a condição: α ≤ biaik , ∀ i ∈ {1, . . . ,m} tal que aik > 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Demonstração do Método Simplex Seja brark = min{ bi aik ; ais > 0}. Se xk assumir o valor α = brark então xr = 0. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Resumo do Método Simplex 1 Seja x uma solução básica compatível inicial associada a um conjunto J. 2 Se c j ≤ 0 para todo j /∈ J, finalize pois x é a solução ótima. Senão, determine ck a partir de ck = min{c j ; c j < 0}. 3 Se aik ≤ 0, ∀ 1 ≤ i ≤ m, finalize pois o problema é ilimitado.Senão, calcule r a partir de br ark = min{ biaik ; ais > 0}. Atualize o conjunto J para J → (J − {t}) ∪ {k}. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Resumo do Método Simplex 1 Seja x uma solução básica compatível inicial associada a um conjunto J. 2 Se c j ≤ 0 para todo j /∈ J, finalize pois x é a solução ótima. Senão, determine ck a partir de ck = min{c j ; c j < 0}. 3 Se aik ≤ 0, ∀ 1 ≤ i ≤ m, finalize pois o problema é ilimitado.Senão, calcule r a partir de br ark = min{ biaik ; ais > 0}. Atualize o conjunto J para J → (J − {t}) ∪ {k}. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Resumo do Método Simplex 1 Seja x uma solução básica compatível inicial associada a um conjunto J. 2 Se c j ≤ 0 para todo j /∈ J, finalize pois x é a solução ótima. Senão, determine ck a partir de ck = min{c j ; c j < 0}. 3 Se aik ≤ 0, ∀ 1 ≤ i ≤ m, finalize pois o problema é ilimitado. Senão, calcule r a partir de br ark = min{ biaik ; ais > 0}. Atualize o conjunto J para J → (J − {t}) ∪ {k}. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Maximizar f (x) = 3x1 + 5x2 s.a:  x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 x1 ≥ 0 x2 ≥ 0 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo  f (x)− 3x1 − 5x2 = 0 x1 + x3 = 4 2x2 + x4 = 12 3x1 + 2x2 + x5 = 18 Tabela Equação Base f (x) x1 x2 x3 x4 x5 b 0 1 - 3 - 5 0 0 0 0 1 1 x3 0 1 0 1 0 0 4 2 x4 0 0 2 0 1 0 12 3 x5 0 3 2 0 0 1 18 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo  f (x)− 3x1 − 5x2 = 0 x1 + x3 = 4 2x2 + x4 = 12 3x1 + 2x2 + x5 = 18 Tabela Equação Base f (x) x1 x2 x3 x4 x5 b 0 1 - 3 - 5 0 0 0 0 1 1 x3 0 1 0 1 0 0 4 2 x4 0 0 2 0 1 0 12 3 x5 0 3 2 0 0 1 18 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Tabela Equação Base f (x) x1 x2 x3 x4 x5 b 0 1 - 3 - 5 0 0 0 0 1 1 x3 0 1 0 1 0 0 4 2 x4 0 0 2 0 1 0 12 3 x5 0 3 2 0 0 1 18 0 1 -3 0 0 52 0 30 2 1 x3 0 1 0 1 0 0 4 2 x2 0 0 1 0 12 0 6 3 x5 0 3 0 0 -1 1 6 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo A solução básica é: (x1, x2, x3, x4, x5) = (0,6,4,0,6), sendo f (x) = 30. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Tabela Equação Base f (x) x1 x2 x3 x4 x5 b 0 1 -3 0 0 52 0 30 2 1 x3 0 1 0 1 0 0 4 2 x2 0 0 1 0 12 0 6 3 x5 0 3 0 0 - 1 1 6 0 1 3 1 x3 0 2 x2 0 3 x1 0 1 0 0 - 13 1 3 2 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Problemas com Variáveis Irrestritas em Sinal Definição São definidas como variáveis irrestritas em sinal as variáveis que podem assumir qualquer valor. José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo Minimizar f (x) = x1 + 4x2 + 2x3 + x4 s.a: x1 + 4x2 + 9x3 + x4 ≤ 8 2x1 + 5x2 + 2x3 + 6x4 ≤ 14 2x1 + 3x2 + 2x3 + 5x4 ≤ 26 x1, x2, x3 ≥ 0 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear Introdução Modelagem Método Gráfico Método Simplex Exemplo x4 = x5 − x6, tal que x5 ≥ 0 e x6 ≥ 0. Minimizar f (x) = x1 + 4x2 + 2x3 + x5 − x6 s.a: x1 + 4x2 + 9x3 + x5 − x6 ≤ 8 2x1 + 5x2 + 2x3 + 6x5 − 6x6 ≤ 14 2x1 + 3x2 + 2x3 + 5x5 − 5x6 ≤ 26 x1, x2, x3, x5, x6 ≥ 0 José Lucyan Mendonça de Almeida IM-UFAL O Problema de Programação Linear