Introdução à Programação Linear na Pesquisa Operacional

1 Pesquisa Operacional 4 Programação Linear Faculdade de Engenharia Eng Celso Daniel Engenharia de Produção Profa Dra Lilian Kátia de Oliveira Programação Linear Um problema de programação matemática é um problema de otimização no qual o objetivo e as restrições são expressas como funções matemáticas e relações funcionais 1 2 1 1 1 2 2 2 1 2 1 2 Otimizar Sujeito a n n n n n n z f x x x b g x x x b g x x x b g x x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 2 1 2 1 1 2 2 n n n f x x x c x c x c x 1 2 1 1 2 2 i n i i in n g x x x a x a x a x Programação Linear Um problema de programação matemática é linear se a função objetivo e cada uma das restrições forem lineares das respectivas variáveis de entrada Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira A presença de qualquer das expressões abaixo tornam o problema não linear 1 1 1 1 x n n x 1 log com qualquer base x ax1 para qualquer valor de a 1 1 sen cos etc x x Quebrando a linearidade Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 3 1 2 1 2 1 2 1 2 ax sa 2 4 20 180 20 600 0 M x x x x x x x x 1 2 1 2 1 2 1 2 ax 2 sa 2 4 20 180 20 600 0 M x x x x x x x x Exemplos Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Existem 4 características para um problema na forma padrão A função objetivo é de Maximizar As restrições são todas com sinal de menor ou igual As constantes de todas as restrições são não negativas As variáveis são todas não negativas Programação Linear Forma Padrão Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 4 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 2 3 Maximizar sujeito a 0 n n n n n n m m mn n m n Z c x c x c x a x a x a x b a x a x a x b a x a x a x b x x x x não negativos Programação Linear Forma Padrão Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Os exemplos criados anteriormente além de serem lineares estão na forma padrão Exemplos 1 2 1 2 1 2 1 2 ax sa 2 4 20 180 20 600 0 M x x x x x x x x 1 2 1 2 1 2 1 2 ax 2 sa 2 4 20 180 20 600 0 M x x x x x x x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 5 FunçãoObjetivo 1 1 1 2 3 Maximizar Sujeito a 12 0 n i i i n ij j i j n Z c x a x b i m x x x x Restrições Forma Padrão Notação Somatório Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Áreas de aplicação da Programação Linear Administração da Produção Alocação de Recursos Limitados Análise de Investimentos Logística Custo de transporte Localização de rede de distribuição Alocação de Recursos em Marketing Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 6 Programação Linear Terminologia Solução no campo de Programação Linear é qualquer especificação de valores para as variáveis de decisão não importando se esta especificação se trata de uma escolha desejável ou permissível Exemplo 1 2 1 2 1 2 1 2 ax sa 2 4 20 180 100 800 0 M x x x x x x x x x1 3 x2 2 32 S x1 3 x2 4 34 S Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Solução Viável é uma solução em que todas as restrições são satisfeitas Solução Inviável é uma solução em que alguma das restrições ou as condições de nãonegatividade não são atendidas Classificação das Soluções Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 7 Classificação das Soluções 1 2 1 2 1 2 1 2 ax sa 2 4 20 180 100 800 0 M x x x x x x x x x1 3 x2 2 32 S solução viável todas as restrições são atendidas x1 3 x2 4 34 S solução inviável as restrições não são respeitadas Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira É especialmente importante verificar como fica o valor de Z nas soluções viáveis que podemos determinar 1 2 1 2 1 2 1 2 ax sa 2 4 20 180 100 800 0 M x x x x x x x x S 11 2 Z S 21 3 Z S 32 5 Z A Solução Ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 8 A Solução Ótima é uma solução viável especial De todas as soluções viáveis aquela que obtiver o valor da função objetivo mais adequado é chamada de ótima A grande questão é como determinar a solução ótima Isto veremos a seguir A Solução Ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira LACHTERMACHER G Pesquisa operacional na tomada de decisão modelagem em Excel 2ª edição revista e atualizada Editora Campus 2004 HILLIER F S Introdução à pesquisa operacional Rio de Janeiro Editora Campus 1988 ARENALES M ARMENTANO V MORABITO R e YANASSE H Pesquisa Operacional Rio de Janeiro Editora Campus 2007 Referências Bibliográficas Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira