PO1_Notas_Aula
21 pág.

PO1_Notas_Aula


DisciplinaProgramação Linear141 materiais745 seguidores
Pré-visualização4 páginas
Engenharia de Produção 
Pesquisa Operacional em Sistemas I - Notas de aula
Engenharia de Produção 
Pesquisa Operacional em Sistemas I - Notas de aula
Universidade Salgado de Oliveira \u2013 UNIVERSO BH
Engenharia de Produção
Pesquisa Operacional em Sistemas I
Notas de aula
\ufffd
Conteúdo
21 Pesquisa Operacional - Introdução	\ufffd
21.1 Conceito	\ufffd
21.2 Fases de um Estudo em P.O.	\ufffd
21.2.1 Formulação do Problema:	\ufffd
21.2.2 Construção do modelo do sistema:	\ufffd
21.2.3 Cálculo da solução através do modelo:	\ufffd
31.2.4 Teste do modelo e da solução:	\ufffd
31.2.5 Estabelecimento de controles da solução:	\ufffd
31.2.6 Implantação e acompanhamento:	\ufffd
31.3 Programação Matemática	\ufffd
31.3.1 Problemas de otimização	\ufffd
31.3.2 Programação Linear (PL)	\ufffd
41.3.3 Programação Inteira	\ufffd
41.3.4 Programação não-linear	\ufffd
41.3.5 Convenção da Solução	\ufffd
42. Programação Linear	\ufffd
42.1 Modelo em programação linear	\ufffd
52.2 Solução para Modelos de Programação Linear - Método gráfico	\ufffd
52.3 Solução para Modelos de Programação Linear \u2013 Método Simplex	\ufffd
52.3.1 Descrição do Método Simplex (Problemas de Maximização)	\ufffd
72.4 Exercícios.	\ufffd
123 Dualidade.	\ufffd
123.1 Montagem do Problema Dual	\ufffd
133.2 Propriedades	\ufffd
134 Análise de Sensibilidade.	\ufffd
144.1 Variação dos Recursos	\ufffd
164.2 Inclusão de uma nova variável	\ufffd
174.3 Mudança nos coeficientes das variáveis da função objetivo.	\ufffd
174.3.1 Variável básica.	\ufffd
194.3.2 Variável não básica.	\ufffd
205 Referências.	\ufffd
\ufffd
\ufffd
1 Pesquisa Operacional - Introdução
1.1 Conceito
Método científico de tomada de decisões. Consiste na descrição de um sistema organizado com o auxílio de um modelo, e através da experimentação com o modelo, na descoberta da melhor maneira de operar o sistema.
1.2 Fases de um Estudo em P.O.
1.2.1 Formulação do Problema: 
O administrador e o responsável pelo estudo em P.O. deverão analisar o problema para obter uma formulação clara e coerente, definindo os objetivos a alcançar e quais os possíveis caminhos alternativos para que isso ocorra.
Levantar limitações técnicas do sistema e as relações com outros sistemas da empresa ou do ambiente externo.
Validar as possíveis soluções considerando esses obstáculos.
Estabelecer uma medida de eficiência para ordenar as soluções encontradas.
1.2.2 Construção do modelo do sistema:
Construir modelos formados por equações e inequações (modelos matemáticos).
Uma das equações serve para medir a eficiência do sistema para cada solução proposta (função objetivo ou função de eficiência). As outras equações descrevem as restrições ou limitações técnicas do sistema
As variáveis que compõem as equações são de dois tipos:
a) Variáveis controladas ou de decisão: seus valores estão sob o controle do administrador.
b) Variáveis não controladas: seus valores são arbitrados por sistemas fora do controle do administrador.
1.2.3 Cálculo da solução através do modelo:
É feito por meio de técnicas matemáticas específicas. A construção de um modelo deve considerar uma técnica para o cálculo da solução.
1.2.4 Teste do modelo e da solução:
É realizado com dados empíricos do sistema. Usar dados históricos para comparar o desempenho do modelo com o desempenho do sistema.
Reformular ou abandonar o modelo.
1.2.5 Estabelecimento de controles da solução:
Identificar parâmetros fundamentais para a solução do problema. Controlar a mudança desses parâmetros para garantir a validade da solução adotada.
Cálculo de nova solução ou reformulação do modelo.
1.2.6 Implantação e acompanhamento:
Apresentação da solução ao administrador sem usar a linguagem técnica do modelo.
Observar o comportamento do sistema com a solução adotada.
Ajustes.
1.3 Programação Matemática
1.3.1 Problemas de otimização
Maximização ou minimização de uma quantidade específica, chamada objetivo, que depende de um número finito de variáveis de entrada. Estas variáveis podem ser independentes umas das outras ou podem ser relacionadas por meio de uma ou mais restrições.
Um problema de programação matemática é um problema de otimização em que o objetivo e as restrições são expressos como funções matemáticas e relações funcionais.
Nesse contexto a palavra programação significa planejamento e não deve ser confundida com programação de computadores.
1.3.2 Programação Linear (PL)
Um problema de programação matemática é linear se a função objetivo e as restrições são equações/inequações lineares. Será a ênfase do nosso curso.
1.3.3 Programação Inteira 
É um problema de programação linear com a restrição adicional de que os valores das variáveis de entrada são números inteiros. 
1.3.4 Programação não-linear
É utilizada em modelos contendo funções não- lineares. Isto é, tanto a função objetivo como o conjunto de restrições podem ser funções de grau maior que 1.
1.3.5 Convenção da Solução
Nos problemas de programação matemática busca-se uma solução. Se existir mais de uma solução igualmente ótimas, qualquer uma delas serve. Não há preferência entre soluções igualmente ótimas se não houver preferência estipulada nas restrições.
Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe).
2. Programação Linear
2.1 Modelo em programação linear
A programação linear é uma das técnicas mais utilizadas na abordagem de problemas em pesquisa operacional. Justifica-se sua aplicação pela simplicidade do modelo envolvido e a disponibilidade de uma técnica de solução programável em computador.
O modelo matemático de programação linear é composto de uma função objetivo linear e de restrições técnicas representadas por um grupo de inequações também lineares. A função objetivo ou função de eficiência mede o desempenho do sistema. As restrições garantem que essas soluções estão de acordo com as limitações técnicas impostas pelo sistema.
A construção do modelo matemático é a parte mais complicada de nosso estudo. Não regra fixa para esse trabalho, mas podemos seguir um roteiro que ajuda ordenar o raciocínio. O roteiro contém as seguintes etapas:
Etapa 1: Definir as variáveis de decisão.
Explicitar as decisões que devem ser tomadas e representar as possíveis decisões por meio de variáveis de decisão.
Etapa 2: Definir o objetivo.
Identificar o objetivo da tomada de decisão. A função objetivo é a expressão que calcula o valor do objetivo em função das variáveis de decisão.
Etapa 3: Estabelecer as restrições.
Cada restrição imposta na descrição do sistema deve ser expressa como uma relação linear (igualdade ou desigualdade), formuladas com as variáveis de decisão.
As etapas 1 e 2 do roteiro podem ser executadas simultaneamente.
2.2 Solução para Modelos de Programação Linear - Método gráfico
Resolve modelos de programação linear com duas variáveis de decisão. Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das possíveis soluções do problema, isto é, representar o conjunto de pontos que obedecem ao grupo de restrições impostas pelo sistema. O desempenho do modelo é avaliado pela representação gráfica da função objetivo.
2.3 Solução para Modelos de Programação Linear \u2013 Método Simplex
O Método Simplex é composto por critérios de escolha de soluções básicas que melhorem o desempenho do modelo e de um teste de \u201cotimalidade\u201d. Assim, o problema deve apresentar uma solução básica inicial e as soluções básicas subseqüentes são calculadas com a troca de variáveis básicas por não básicas, gerando novas soluções.
2.3.1 Descrição do Método Simplex (Problemas de Maximização)
Passo 1: Transformação do modelo.
Transformar