Baixe o app para aproveitar ainda mais
Prévia do material em texto
Modelos de Programação Linear Fabiana Gomes dos Passos Roteiro da aula • Programação Linear – Modelo de Programação Linear – Pressupostos de um modelo de Programação Linear – Passos básicos de Programação Linear – Exemplos de Aplicação da Programação Linear Programação Linear • Um problema de programação linear é um problema de programação matemática estática onde a função objetivo e as restrições são funções lineares. • ÁREAS DE APLICAÇÃO – Administração da Produção – Análise de Investimento – Alocação de recursos limitados – Logística – Custo de Transporte – Localização da rede de distribuição – Alocação de recursos em marketing entre diversos meios de comunicação Programação Linear • MODELO DE PROGRAMAÇÃO LINEAR Programação Linear • Onde Para i = 1, ..., m • n é o número de variáveis • m é o número de restrições do problema • i é o índice de uma determinada restrição Programação Linear • Existem 4 características para um problema na forma padrão: – A função objetivo é de Maximizar; – As restrições têm o sinal de menor ou igual; – As constantes de todas as restrições são não negativas; – As variáveis de decisão são não negativas. Programação Linear • Ou na forma reduzida Maximizar: Z = Sujeito a: x1, x2, ..., xn ≥ 0 n j jjxc 1 n j ijij mibxa 1 ),...,2,1( Programação Linear • Ou na forma matricial Maximizar: Sujeito a: Ax ≤ b x≥0 onde: – A = matriz (mxn) dos coeficientes das variáveis de decisão nas restrições – x = vetor coluna (nx1) das variáveis de decisão – b = vetor coluna (mx1) do lado direito das restrições, – c = vetor linha (1xn) dos coeficientes das variáveis de decisão função objetivo cxz Programação Linear - Exemplos Problema de Minimização Min Custo = 80X1 + 10X2 Sujeito a 9X1 + 3X2 ≥ 30 X1 + 8X2 ≥ 20 X1, X2 ≥ 0 Problema de Maximização Max Lucro = 110X1 + 65X2 Sujeito a 2X1 + X2 ≤ 7 7X1 + 7X2 ≤ 30 X1, X2 ≥ 0 Pressupostos de um Modelo de Programação Linear • Proporcionalidade O valor da função objetivo é diretamente proporcional ao nível de atividade de cada variável de decisão, ou seja, o valor da função objetivo se altera de um valor constante dada uma variação constante da variável de decisão. Pressupostos de um Modelo de Programação Linear • Aditividade Não existe interdependência entre as variáveis de decisão do modelo, isto é, não permiti a existência de termos cruzados , tanto na função-objetivo como nas restrições. Pressupostos de um Modelo de Programação Linear • Divisibilidade Qualquer variável de decisão pode assumir qualquer valor fracionário. Pressupostos de um Modelo de Programação Linear • Certeza Todos os parâmetros do modelo são constantes conhecidas (a,b,c) provocando a análise de sensibilidade dos resultados. Modelagem em Programação Linear • Passos básicos na obtenção de modelos de P.L: 1. Identificar as variáveis de decisão, representá-las em simbologia algébrica; 2. Identificar as restrições do problema, expressá-las como equações ou inequações lineares em termos das variáveis de decisão; 3. Identificar o objetivo de interesse no problema, representá-lo como função linear em termos das variáveis de decisão, que deverá ser maximizada ou minimizada. Exemplo – Determinação do Mix de Produção Uma companhia deseja programar a produção de um utensílio de cozinha que requer usos de dois tipos de recursos – mão de obra e material. A companhia está considerando a fabricação de três modelos e o seu departamento de engenharia forneceu os dados contidos na tabela abaixo. O suprimento de material é de 200 quilos por dia. A disponibilidade diária de mão de obra é 150 horas. Formule um modelo de programação linear para determinar a produção diária de cada um dos modelos de modo a maximizar o lucro total da companhia. Setor Produtivo Modelo A B C Mão de obra (horas por unidade) 7 3 6 Material (quilos por unidade) 4 4 5 Lucro Unitário 4 2 3 • Variáveis X1 = produção diária do produto A; X2 = produção diária do produto B; X3 = produção diária do produto C; Z = lucro total da companhia. • Restrições a) Limitação da mão de obra; b) Limitação do material; c) quantidades não negativas. • Objetivo Maximizar o lucro total da companhia 0,, 200544 150637:. 324 321 321 321 321 xxx xxx xxxas xxxZMax Setor Produtivo Modelo A B C Mão de obra (horas por unidade) 7 3 6 Material (quilos por unidade) 4 4 5 Lucro Unitário 4 2 3 Exemplo – Fabricação de Produtos Exemplo – Fabricação de Produtos A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos produtos. A demanda é muito maior que a capacidade disponível (toda produção poderá ser vendida). Através dos dados contidos na tabela, logo abaixo, formule um modelo de programação linear para determinar a produção diária de cada um dos modelos de modo a maximizar o lucro total da companhia. Setor Produtivo Produto Capacidade Disponível Janelas Portas Montagem 1 hora/unid. - 4.000 horas/mês Laminação - 2 hora/unid. 12.000 horas/mês Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês Lucro Unitário $ 3,00 $ 5,00 • Variáveis X1 = qtde. de janelas, em milhares de unidades; X2 = qtde. de portas, em milhares de unidades; Z = lucro total obtido com novos produtos. • Restrições a) disponibilidade do setor de montagem; b) disponibilidade do setor de laminação; c) disponibilidade do setor de corte; d) quantidades não negativas. • Objetivo Maximizar o lucro total da empresa 0, 60023 4002 33,133:. 53 21 21 2 1 21 xx xx x xas xxZMax Setor Produtivo Produto Capacidade Disponível Janelas Portas Montagem 1 hora/unid. - 4.000 horas/mês Laminação - 2 hora/unid. 12.000 horas/mês Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês Lucro Unitário $ 3,00 $ 5,00 Exemplo – Fabricação de Produtos Conceitos de Solução num Problema de Programação Linear • Solução – qualquer valor para as variáveis de decisão, independente de ser uma escolha desejável ou permissível; • 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 ulguma das restrições ou as condições de não negatividade não são atendidas; • Solução ótima – uma solução viável que maximiza (ou minimiza) a função objetivo em toda região viável (conjunto admissível), podendo ser única ou não. Estrutura Algorítmica da Programação Linear Exercício de Fixação Uma fábrica pretende produzir dois produtos, o produto 1 e o produto 2. Ambos os produtos passam por três fases de desenvolvimento durante o processo de manufatura, cada uma das quais se realiza num departamento diferente. No próximo mês, cada um dos departamentos tem um determinado números disponível de horas por máquina, para ser utilizado na concepção destes dois produtos. Por sua vez, cada um dos produtos requer, por unidade, um dado tempo de utilização de cada máquina. Tempo disponível (h) Tempo requeridopor unidade (h) Produto 1 Produto 2 1 0 0 2 2 3 4 12 18 Departamentos 1 2 3 Para manter o problema simples, vamos assumir que os custos de produção de cada produto são constantes, independentemente da quantidade produzida. Supondo que o lucro, por unidade, de cada produto são de R$ 3 para o produto 1 e R$ 5 para o produto 2. Formule um modelo de programação linear para determinar a produção diária de cada um dos modelos de modo a maximizar o lucro total da companhia. • Variáveis X1 = produção diária do produto 1; X2 = produção diária do produto 2; Z = lucro total obtido com os dois produtos. • Restrições a) Tempo disponível para fabricar no departamento 1; b) Tempo disponível para fabricar no departamento 2; c) Tempo disponível para fabricar no departamento 3; d) quantidades não negativas. • Objetivo Maximizar o lucro total da companhia 0, 1823 122 4:. 53 21 21 2 1 21 xx xx x xas xxZMax Exercício de Fixação Tempo disponível (h) Tempo requerido por unidade (h) Produto 1 Produto 2 1 0 0 2 2 3 4 12 18 Departamentos 1 2 3 Referências • ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional: métodos e modelos para análise de decisões. 3. ed. Rio de Janeiro: LTC, 2004.192 p. • LACHTERMACHER, Gerson. Pesquisa operacional na tomada de decisões. 2. ed. rev. e atual. Rio de Janeiro: Elsevier, 2004. 384 p.
Compartilhar