Disciplina: Programação Linear

PESQUISA OPERAIONAL

Veja a seguir os seguintes conteúdos já disponíveis. Para tomar conhecimento da lista completa dos conteúdos vistos nesta disciplina, clique no ícone "PROGRAMA" acima. OBSERVAÇÃO: Alguns dos assuntos estão divididos em partes as quais podem ser acessadas clicando nos links abaixo.

1) Sistemas Lineares:   Interpretação da Solução no Espaço das Colunas   / Algoritmo para o Escalonamento de um Sistema Linear: Pivotamento /

2) Shdow Price (ou Preço Sombra): Introdução / Interpretação Gráfica (Geométrica) do Shadow Price / 

Programação Linear

Origem: Wikipédia, a enciclopédia livre.

Em matemática, problemas de Programação Linear (PL) são Problemas de Optimização nos quais a Função Objetivo e as Restrições são todas lineares. Programação Linear é uma importante área da optimização por várias razões. Muitos problemas práticos em Pesquisa Operacional podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, tais como Problemas de Network Flow (Problemas de Fluxo em Redes) e Problema de Multicommodity Flow (Problema de de Fluxo Multiproduto) são considerados importantes o suficiente para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Vários algoritmos para outros tipos de problemas de optimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da Programação Linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações.

Índice 

1 Exemplo

2 Teoria

3 Algoritmos

4 Variáveis inteiras

5 Ver também

6 Bibliografia

7 Ligações externas

Exemplo de Poliedro Convexo (Bidimensional) resultante das Restrições de um Problema de Programação Linear.

Exemplo:

Aqui está um exemplo de problema de Programação Linear. Suponha que um fazendeiro tem um pedaço de terra de digamos, A km², para ser semeado com trigo ou cevada ou uma combinação de ambas. O fazendeiro tem uma quantidade limitada de fertilizante F permitido e de inseticida P permitido que podem ser usados, cada um deles sendo necessários em quantidades diferentes por unidade de área para o trigo (F1, P1) e para a cevada (F2, P2). Seja S1 o preço de venda do trigo, e S2 o da cevada. Se chamarmos a área plantada com trigo e cevada de x1 e x2 respectivamente, então o número ideal de km² de plantação com trigo vs. cevada pode ser expresso como um problema de Programação Linear:

Teoria

Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de Conjunto dos Pontos Viáveis. Uma vez que a função objectivo é também linear, todo ótimo local é automaticamente um ótimo global (É um Teorema dentro da Análise Matemática: Um estudo crítico do Cálculo Diferencial e Integral). A função objetivo ser linear também implica que uma solução ótima pode apenas ocorrer em um ponto da fronteira do conjunto de pontos viáveis. (É um Teorema dentro da Análise Matemática: Um estudo crítico do Cálculo Diferencial e Integral).

 

Existem duas situações nas quais uma solução ótima não pode ser encontrada. Primeiro, se as restrições se contradizem (por exemplo, x ≥ 2 e x ≤ 1) logo, a região factível é vazia e não pode haver solução ótima, já que não pode haver solução nenhuma. Neste caso, o PL é dito inviável.

Alternativamente, o poliedro pode ser ilimitado na direção da função objetivo (por exemplo: maximizar x1 + 3x2 sujeito a x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 10), neste caso não existe solução ótima uma vez que soluções arbitrariamente grandes da função objetivo podem ser construídas, e o problema é dito ilimitado.

 

Fora estas duas condições patológicas (que são frequentemente eliminadas por limitações dos recursos inerentes ao problema que está sendo modelado, como acima), o óptimo é sempre alcançado num vértice do poliedro (É um Teorema). Entretanto, o ótimo nem sempre é único (Problema de Unicidade de Soluções não é garantido neste caso de PL): é possível ter um conjunto de soluções ótimas cobrindo uma aresta ou face do poliedro, ou até mesmo o poliedro todo (Esta última situação pode ocorrer se a função objetivo for uniformemente igual a uma constante).

 

 

Algoritmos

O Algoritmo Simplex resolve problemas de PL construindo uma solução admissível no vértice do poliedro, e então percorre os vértices do poliedro que sucessivamente possuem valores mais altos da função objectivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um óptimo global se certas condições para se evitar ciclos forem assumidas, ele é fraco no pior-caso (ver Ordem de Complexidade de Algoritmos): é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema. Na verdade, por algum tempo não se soube se problemas de programação linear eram NP-completos ou tinham solução em tempo polinomial.

 

O primeiro algoritmo de programação linear em tempo polinomial no pior-caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no [método do elipsóide] da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da [optimização convexa] de Arkadi Nemirovski, uma dos ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.

 

Entretanto, a performance prática do algoritmo de Khachiyan é desapontante: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa dos métodos de Pontos Interiores (Ponto Interior quando não é Ponto pertencente a Fronteira do Conjunto Viável - Ponto Interior ou Ponto de Fronteira são Conceitos ou Definições detro da Área da Topologia quer seja em Espaços Métricos ou não) - repetindo, um ponto é Interior quando não é um ponto de Fronteira. Ao contrário de algoritmo simplex, que apenas evolui ao longo de pontos na fronteira da região factível, métodos de ponto interior podem se mover pelo interior da região factível (Viável).

 

Em 1984, Narendra Karmarkar propôs seu método projetivo, que tornou-se o primeiro algoritmo a apresentar um bom desempenho tanto na teoria como na prática: seu pior-caso de Complexidade é Polimonial (Ver Ordem de Complexidade de Algoritmos) e os problemas práticos de experiência mostram que ele é razoavelmente eficiente em comparação com o algoritmo simplex. Desde o método de Karmarkar, muitos outros métodos de pontos interiores têm sido propotos e analisados. Um método bastante popular é o Método Preditor-Corretor de Mehrotra, cuja atuação possui bom desempenho na prática, ainda que pouco se saiba sobre ele na teoria.

 

A opinião mais recente entre os estudiosos é que a eficiência das boas implementações dos métodos baseados em simplex e dos pontos interiores são similiares para a aplicação de rotina no programa linear.

 

As soluções do programa linear estão em uso generalizado de otimização de diversos problemas na indústria, como a otimização de fluxo de transporte, que pode ser transformada em problemas de programação linear sem muitas dificuldades.

Texto a ser Editado, Aguedem!

Veja aqui uma Coletânea de Artigos, Apostilas, Slide (PowerPoint) e Livros correlacionados à Pesquisa Operacional/Simulação.

Programação Linear 

 

Apostila - Programação Linear - Prof. Mauricio Pereira dos Santos

Apostila de Programação Linear contém a matéria que era por mim lecionada na cadeira de programação linear do Instituto de Matemática e Estatística da Universidade do  Estado do Rio de Janeiro - UERJ. Ela está no formato ".PDF" e para ser aberta e impressa, é necessário se ter o Adobe Acrobat Reader ou similar. 

ATENÇÃO: a apostila está montada para ser impressa no formato Frente e Verso

Software para Pesquisa Operacional/Programação Linear

O software PO é um aplicativo de apoio no ensino dos tópicos de Pesquisa Operacional.É gratuito, podendo ser usado e copiado livremente.

Ressalte-se, no entanto, que o autor não tem qualquer responsabilidade pelo uso que dele for feito.
Na sua versão atual (10.4), em 11 diferentes módulos, ele resolve pequenos problemas dos seguintes tópicos:

  • Programação Linear

  • Transportes

  • Atribuição

  • Fluxo máximo

  • Árvore Tamanho Mínimo

  • Menor caminho em uma rede

  • Maior caminho em uma rede

  • Pert

  • Cpm

  • Filas

  • Simulação (Filas)

     

É um software do ambiente WINDOWS e roda em qualquer versão a partir do Windows 95. No WINDOWS VISTA, WINDOWS 7 ou WINDOWS 8, o executável da aplicação (Po.exe) deve ser colocado em modo de compatibilidade com o Windows XP (SP2).
 

A resolução do vídeo deve ser igual ou maior a 800 x 600. 
 

Para instalar o software você precisa baixar o arquivo de instalação clicando em: instalação PO (Instalar.exe). 
Um arquivo, chamado instalar.exe, será baixado e gravado no seu micro. Para fazer a instalação, basta executar este programa e seguir as instruções. Normalmente no final é solicitado que se reinicie o Windows. Os arquivos do programa serão gravados na pasta C:\Po exceto se for escolhido outro disco e/ou pasta. Após a instalação ter sido concluída, para executar o programa basta clicar no ícone (Po) criado no desktop.

 

  • ATENÇÃO: Antes de comunicar um eventual êrro existente no programa, verifique se está sendo utilizada a última versão (10.4) postada no site. Pode ser que o êrro já tenha sido identificado e corrigido na versão disponível para download. Novas versões podem ser instaladas sem precisar desinstalar a anterior.

 

Se você tiver alguma sugestão ou encontrou algum problema, por favor mande email para: mauriciopereira@pobox.com 

Leitura Complementar: Páginas em Slide!

 

1) Pesquisa Operacional: Programação Linear

Veja a página em Slide

Sites Relacionados:

 

1) Programação Linear em Pesquisa Operacional: 

PHPSimplex é uma ferramenta online para a resolução de Problemas de Programação Linear. Seu uso é livre e gratuito. Para acessá-lo basta clicar sobre o ícone à esquerda, ou em «PHPSimplex» no menu principal.

PHPSimplex tem a capacidade de solucionar problemas pelo Método Simplex, o Método das Duas Fases, e o Método Gráfico, e não tem limitações quanto ao número de variáveis de decisão ou de restrições dos problemas.

Esta ferramenta foi concebida para ajudar os alunos de engenharia ou cursos de Pesquisa Operacional em suas aprendizagens, pois não só apresenta os resultados finais, mas também as operações intermediárias ajudando a aprender e compreender os métodos utilizados. Ela também oferece a solução direta para uso profissional. Outras vantagens são: ela não exige nenhuma linguagem para introduzir o problema, oferece uma interface amigável próxima ao usuário, é fácil e intuitiva, você não precisa instalar nada para usar a ferramenta, e está disponível em vários idiomas (se você deseja PHPSimplex em seu idioma, por favor entre em contacto conosco).

É disponível um manual de ajuda de PHPSimplex para aprender rapidamente a usar a ferramenta.

Também nesta página você encontrará a teoria dos métodos utilizados, os casos especiais a considerar, os exemplos de problemas resolvidos passo a passo, uma comparação entre o método Simplex e o método gráfico, história da Pesquisa Operacional, etc.

Leitura Suplementar:

 

Livro: "Programação Linear": Mauricio Pereira dos Santos. Departamento de Matemática Aplicada - Instituto de matemática e Estatística - Universidade do Estado do Rio de Janeiro-RJ. Livro Completo Total de Páginas = 137 - Arquivo Formato ".PDF" - Tamanho do Arquivo = 889kb.

 

Livro: "Pesquisa Operacional": Mauricio Pereira dos Santos. Departamento de Matemática Aplicada - Instituto de matemática e Estatística - Universidade do Estado do Rio de Janeiro-RJ. Livro Completo Total de Páginas = 243 - Arquivo Formato ".PDF" - Tamanho do Arquivo = 1.536kb.

 

Livro: "Introdução à Simulação Discreta": Mauricio Pereira dos Santos. Departamento de Matemática Aplicada - Instituto de matemática e Estatística - Universidade do Estado do Rio de Janeiro-RJ. Livro Completo Total de Páginas = 157 - Arquivo Formato ".PDF" - Tamanho do Arquivo = 1.252kb.

Texto a ser Editado. Aguardem!

  A partir de 23 Ago de 2018

Você é o Visitante de Número

ensinoeinformacao - Programação Linear: Introdução

 

Publicado em 29 de fev de 2016

Uma Introdução à Programação Linear onde são abordados três aspectos:

  • Formulação de Modelos;

  • Solução Gráfica (em R²); e

  • Forma Padrão

 

________

ERRATA: Aos 03 minutos no início da Vídeo Aula quando decidimos mencionar a Grande Área a PESQUISA OPERACIONAL, falou-se: "...A Programação Dinâmica ela compreende algumas Áreas como a Programação Matemática...". Mas o CORRETO é: "A PESQUISA OPERACIONAL ela compreende algumas Áreas como a Programação Matemática...".

 

Nossa Revista: Ensino&Informação (no Facebook)

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos