Texto de pré-visualização
Notas de Aula da Disciplina de Otimização de Processos Prof Edgard Pedroso Arquivo de aulas n o 01 Apresentação do plano de ensino Conceitos Introdutórios Modelagem Matemática 2 Pesquisa Operacional PO A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais Tem como foco a tomada de decisões Para atingir seus objetivos aplica conceitos e métodos de outras áreas científicas para concepção planejamento ou operação de sistemas e processos Prof Edgard 3 Os Modelos são representações simplificadas da realidade que preservam para determinadas situações e enfoques uma equivalência adequada MODELAGEM Como o modelo é uma simplificação do problema real toda solução do modelo é uma aproximação da solução do problema real Prof Edgard 4 Suponha que por motivos justificáveis uma certa dieta alimentar esteja restrita a leite desnatado carne magra de boi carne de peixe e salada Sabese ainda que os requisitos nutricionais serão expressos em termos de vitaminas A B e C e controlados por suas quantidades mínimas em miligramas uma vez que são indispensáveis à preservação da saúde da pessoa que estará se submetendo à dieta A tabela a seguir resume a quantidade de cada vitamina em disponibilidade nos alimentos e a sua necessidade mínima diária de consumo para boa saúde da pessoa Problema da Dieta Exemplos de Problemas de Pesquisa Operacional 5 Problema da Dieta Alimento Vitamina Leite L Carne Kg Peixe Kg Salada 100g Requisito Nutricional Mínimo A 2 mg 2 mg 10 mg 20 mg 11 mg B 50 mg 20 mg 10 mg 20 mg 70 mg C 80 mg 70 mg 10 mg 80 mg 250 mg Custo R 200litro R 400Kg R 150Kg R 100100g Desejase obter o requisito nutricional mínimo com o menor custo possível Prof Edgard 6 Problema da Dieta Variáveis de Decisão ou Variáveis Estruturais ou Níveis de Atividade x1 Quantidade de litros de leite x2 Quantidade de Kg de carne x3 Quantidade de Kg de peixe x4 Quantidade de unidades pctes de 100g de salada 4 3 2 1 x x x x X das variáveis Vetor Prof Edgard 7 Problema a Dieta Função Objetivo ou função custo ou de critério x x x x 4 3 2 1 1 51 4 2 Z x x x x 4 3 2 1 1 51 4 2 Matricial Notação X Z C t 1 51 4 2 de custos Vetor 4 3 2 1 c c c c C X Min Z C t Generaliza ndo tem se Prof Edgard 8 Problema da Dieta Restrições ou vínculos ou restrições tecnológicas 80 10 70 80 20 10 20 50 20 10 2 2 dos coeficientes tecnológicos Matriz A 250 70 11 dos termos independentes RHS Vetor 3 2 1 b b b b 0 0 0 0 250 80 10 70 80 70 20 10 20 50 11 20 10 2 2 Restrições 4 3 2 negatividade não de Restrições x x x x x x x x x x x x x x x x 1 4 3 2 1 4 3 2 1 4 3 2 1 x x x x 4 3 2 1 250 70 11 80 10 70 80 20 10 20 50 20 10 2 2 Notação Matricial b X A 0 0 0 0 Notação Matricial 4 3 2 1 x x x x Ο X Problema da Dieta Formulação Final Forma Explícita x x x x 4 3 2 1 1 51 4 2 Z Min 0 250 80 10 70 80 70 20 10 20 50 11 20 10 2 2 4 3 2 x x x x x x x x x x x x x x x x 1 4 3 2 1 4 3 2 1 4 3 2 1 sa sujeita a Sistema de inequações lineares com infinitas soluções viáveis pode ser escrito assim Problema da Dieta Formulação Final Forma Matricial x x x x 4 3 2 1 1 51 4 2 Z Min x x x x a s 4 3 2 1 250 70 11 80 10 70 80 20 10 20 50 20 10 2 2 0 0 0 0 4 3 2 1 x x x x 2 88 unidades de 100 g ou seja 288 g 0 00 Kg 0 00 Kg 0 25 L x x x x 4 3 2 1 min R 338 Z Solução ótima LINGO Language for Interactive General Optimizer 12 Notação e Termilogia Forma generalizada explicita do modelo x x x b x a x a x a b a x a x x a b a x a x x a c x c x c x n m n mn m m n n n n n n 0 min 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 sa Z 13 sa min X b AX C X Z T Ο Forma generalizada matricial do modelo x x x b x a x a x a b a x a x x a b a x a x x a c x c x c x n m n mn m m n n n n n n 0 min generalizada explicita de um modelo Forma 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 sa Z 1 1 1 2 1 1 2 1 2 22 21 1 12 11 2 1 0 0 0 min n n n 2 1 m m n n 2 1 m n mn m m n n n 2 1 n x x x b b b x x x a a a a a a a a a x x x c c c sa Z ou Notação e Termilogia 14 0 min 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 n m n mn m m n n n n n n x x x b x a x a x a b a x a x x a b a x a x x a sa c x c x c x Z n j j x j c 1 m 1 2 b com i x a i j n 1 j ij 1 1 b x a j n 1 j j 2 2 b x a j n 1 j j m j n 1 j mj b x a Forma generalizada c somatório 1 2 n para j 0 min 1 j i j n 1 j ij n j j j x m 2 1 b com i x a a s x c Z Definições x x x b x a x a x a b x a x a x a b x a a x x a n m n mn m m n n n n 0 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 m 1 2 i com b x a i j n 1 j ij ou 1 Qualquer conjunto de valores para as variáveis x1 x2 xn que satisfaça todas as restrições é denominado solução viável ou factível 2 O conjunto de todas as soluções viáveis formam a Região Viável 3 Entre todas as soluções viáveis aquela que otimiza maximiza ou minimiza a função objetivo é denominada de solução ótima Sistema de inequações lineares com infinitas soluções viáveis 16 Técnicas aplicadas para resolução dos modelos matemáticos em PO Prof Edgard 17 Problema de Manufatura ou de Programação de Produção Uma fábrica de automotores produz Automóveis Caminhões A fábrica tem duas linhas de montagem Linha de Montagem 1 Estrutura Linha de Montagem 2 Acabamento 18 Problema de Manufatura Realiza operações básicas de montagem e trabalha com 05 homensdia em cada caminhão e com 02 homensdia cada automóvel Por causa de limitações de espaço e mão de obra qualificada a fábrica dispõe apenas de 180 homensdia nessa linha de montagem por semana Linha de Montagem 1 Prof Edgard 19 Problema de Manufatura Executa operações de acabamento ela trabalha com 3 homensdia em cada caminhão e 3 homensdia em cada automóvel que produz Por causa de limitações de espaço e mão de obra qualificada a fábrica dispõe apenas 135 homens dia nessa linha por semana Linha de Montagem 2 Prof Edgard 20 Problema de Manufatura Quantos caminhões e quantos automóveis a empresa deve fabricar por semana para obter lucro máximo Problema A divisão de custos da empresa estima que obtém um lucro de R 300000 em cada caminhão e R 200000 em cada automóvel Prof Edgard 21 Problema de Manufatura Variáveis de Decisão x1 Nº de carros fabricados em uma semana carrossemana x2 Nº de caminhões fabricados em uma semana caminhõessemana Função Objetivo custo x x 2 1 3000 2000 Z Linha de montagem Consumo de mão de obra em cada carro Consumo de mão de obra em cada caminhão Disponibilidade de mão de obra em cada linha por semana LM1 2 homensdiacarro 5 homensdiacaminhão 180 homensdiasemana LM2 3 homensdiacarro 3 homensdiacaminhão 135 homensdiasemana Lucro R 200000carro R 300000caminhão 22 Problema de Manufatura Restrições relativas as disponibilidades de mão de obra por semana 0 x x são inteiros 0 x x linha 2 3 x 135 3x linha 1 5 x 180 2x 2 1 2 1 2 1 2 1 Prof Edgard 23 Formulação Final x x 2 1 3000 2000 Max Z sa 0 x x são inteiros 0 x x 3 x 135 3x 5 x 180 2x 2 1 2 1 2 1 2 1 Problema de Manufatura Prof Edgard Prof Edgard 24 LINDO Linear Interactive and Discrete Optimizer 25 Problema da Cooperativa Agrícola Prof Edgard Uma cooperativa agrícola opera três fazendas cujas produtividades são consideradas iguais A produção da fazenda depende fundamentalmente da área disponível para plantio e da água de irrigação A cooperativa procura diversificar sua produção de modo a plantar três tipos de cultura em cada fazenda milho arroz e feijão Cada tipo de cultura demanda por certa quantidade de água Para reduzir o conflito no uso das colheitadeiras que são alugadas estabeleceramse limites de área de produção dentro de cada tipo de cultura As tabelas a seguir resumem os dados tecnológicos Pedese um programa de produção que defina a área de plantio de cada cultura em cada fazenda de modo a otimizar o lucro total da cooperativa 26 Problema da Cooperativa Agrícola Fazenda Área p cultivo acres Água disponível Litros 1 400 1800 2 650 2200 3 350 950 Prof Edgard Cultura Área máxima de cultivo por cultura para evitar o conflito das colheitadeiras acres Consumo de Água Litros por acre Lucro Rr por Acre Milho 660 55 5000 Arroz 880 40 4000 Feijão 400 35 800 1 acre4047 m2 27 Problema da Cooperativa Agrícola Variáveis de Decisão Áreas em acres a serem destinadas para cultivo de Feijão na fazenda 3 X Feijão na fazenda 2 X Feijão na fazenda 1 X Arroz na fazenda 3 X Arroz na fazenda 2 X Arroz na fazenda 1 X milho na fazenda 3 X milho na fazenda 2 X milho na fazenda 1 X 3F 2F 1F 3A 2A 1A 3M 2M 1M 28 Problema da Cooperativa Agrícola Função Objetivo Acre Lucro por de acres de Feijão Quant 3F 2F 1F Lucro por Acre de acres de Arroz Quant 3A 2A 1A Lucro por Acre de acres de Milho Quant 3M 2M 1M 800 X X X 4000 X X X 5000 X X X Z Prof Edgard 29 Problema da Cooperativa Agrícola Restrições De área a ser cultivada por fazenda 350 X X X 650 X X X 400 X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M Prof Edgard 30 Problema da Cooperativa Agrícola Restrições De litros de água disponível por fazenda 950 X 35 X 40 X 55 2200 X 35 X 40 X 55 1800 X 35 X 40 X 55 3F de feijão acre litros 3A de arroz acre litros 3M de milho acre litros 2F de feijão acre litros 2A de arroz acre litros 2M de milho acre litros 1F de feijão acre litros 1A de arroz acre litros 1M de milho acre litros Prof Edgard 31 Problema da Cooperativa Agrícola Restrições De área máxima de cultivo por cultura de forma a evitar o conflito das colheitadeiras 400 X X X 880 X X X 660 X X X 3F 2F 1F 3A 2A 1A 3M 2M 1M Restrições Nãonegatividade 0 X X X X X X X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M 32 Formulação Final 3F 2F 1F 3A 2A 1A 3M 2M 1M X X X 800 X X X 4000 X X X 5000 Max Z sa 350 X X X 650 X X X 400 X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M 950 35X 40X 55X 2200 35X 40X 55X 1800 35X 40X 55X 3F 3A 3M 2F 2A 2M 1F 1A 1M 400 X X X 880 X X X 660 X X X 3F 2F 1F 3A 2A 1A 3M 2M 1M 0 X X X X X X X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M Sejam quatro fornecedores de um determinado produto origem 1 origem 2 origem 3 origem 4 com suas capacidades de produção conhecidas 10 20 12 e 13 unidades respectivamente e três centros de distribuição destino 1 destino 2 destino 3 com suas demandas também conhecidas 8 32 e 15 unidades respectivamente Devese determinar que quantidades devem ser transportadas de cada origem para cada destino afim de minimizar o custo com transporte atendendo às restrições de oferta e demanda Na tabela a seguir são apresentados os custos unitários por unidade com transporte nos diversos roteiros possíveis Exemplo Problema de Transporte Exemplo A tabela abaixo mostra os custos unitários R com transporte a disponibilidade ou ofertas em unidades de produto nas origens fornecedores e as necessidades ou demandas em unidades de produto nos destinos centros de distribuição Custo de transporte por unidade Centros de Distribuição Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Fornecedores D1 8 D2 32 D3 15 O110 O220 O312 O413 6 13 10 5 12 1 9 7 6 5 4 8 Diagrama de Fluxo Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Nós de Oferta Nós de Demanda Modelo 0 x x x x x x x x x x x x 15 x x x x 32 x x x x 8 x x x x 13 x x x x 12 x x 20 x x x x x 10 x 4x 6x 10x 5x 9x 7 1x 12x 13x 8x 5x 6x 43 42 41 33 32 31 23 22 21 13 12 11 43 33 23 13 42 32 22 12 41 31 21 11 43 42 41 33 32 31 23 22 21 13 12 11 43 42 41 33 32 31 23 22 21 13 12 11 a s min Z Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Uma empreiteira dispõe de 4 gruas cada uma armazenada em uma de suas sedes 123 e 4 e necessita mandálas com urgência para cada uma de suas obras sediadas nas cidades 123 e 4 Determine o fluxo de designações que minimize a distância das alocações sendo dadas as distâncias em quilômetros dos diversos percursos possíveis Problema de Designação A tabela abaixo mostra as distâncias entre as origens e os destinos Distâncias em quilômetros Localização das obras Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 Sedes O11 O21 O31 O41 4 9 14 21 5 12 7 11 9 4 2 12 Diagrama de Fluxo possível Nós de Oferta Nós de Demanda Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 D1 1 D2 1 D3 1 D4 1 34 17 12 25 Modelo 10 1 x x x x 1 x x x x x 1 x x x 1 x x x x x 1 x x x x 1 x x x x 1 x x x x x x 1 x 2x 12x 9x 14x x 4 7x 25x 11x 12x 5x 9x 17x 12x 21x 4x 4x 3 44 34 24 14 43 33 23 13 42 32 22 12 41 31 21 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 ij X a s min Z Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 43 Um jovem atleta se sente atraído pela prática de dois esportes natação e ciclismo A natação exige um gasto de R 300 por seção de duas horas O ciclismo exige um gasto de R 200 por seção de duas horas Ele dispõe de R 7000 para este fim Seus afazeres disponibilizam em empregar para este fim no máximo 18 horas mensais e 80000 calorias Cada seção de natação consome 1500 calorias e ciclismo 1000 calorias O problema consiste em planejar seu treinamento de forma a maximizar o número de seções de treinamento Com base nestes dados faça a modelagem do problema como um problema de programação linear indicando a função objetivo e todas as restrições Determine ainda o vetor das variáveis de decisão X o vetor de custos C e Ct a matriz dos coeficientes das restrições A o vetor dos termos independentes b Represente o número de seções de natação por X1 e o número de seções de ciclismo por X2 Não é necessário a resolução do PL basta a modelagem No 01 TDE1 Um fabricante produz dois tipos de aço normal e especial Uma tonelada de aço normal necessita de 2 horas no forno de soleira aberta e 5 horas de molho uma tonelada do aço especial precisa de 2 horas de forno de soleira aberta e 3 horas de molho O forno de soleira aberta está disponível 8 horas por dia e o fosso onde as peças ficam de molho está disponível 15 horas por dia O lucro em uma tonelada de aço normal é de 12000 unidades monetárias e o lucro em uma tonelada de aço especial é de 10000 unidades monetárias Desejase determinar quantas toneladas de cada tipo de aço devem ser manufaturadas de modo a maximizar o lucro Com base nestes dados faça a modelagem do problema como um problema de programação linear indicando a função objetivo e todas as restrições Determine ainda o vetor das variáveis de decisão X o vetor de custos C e Ct a matriz dos coeficientes das restrições A o vetor dos termos independentes b Represente o número de toneladas de aço normal por X1 e o número de toneladas de aço especial por X2 Não é necessário a resolução do PL basta a modelagem No 02 TDE1 45 Respostas 80000 18 70 b b b e Vetor dos termos independentesb 1000 1500 2 2 2 3 d Matriz dos coeficientes das restrições 1 1 c c 1 C 1 c c c Vetor de custos C x x b Vetor das variáveis de decisão Z Naturais ou Inteiros não negativos ou x x x x 1000x 80000 1500x 2x 18 2x 2x 70 3x x x a Modelo matemático na Explícita 1 3 2 1 32 31 22 21 12 11 2 1 t 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 a a a a a a A X a s max Z 46 Respostas 15 8 b b b e Vetor dos termos independentes b 3 5 2 2 d Matriz dos coeficientes das restrições 100 120 c c 100 C 120 c c c Vetor de custos C x x b Vetor das variáveis de decisão 0 Reais não negativos x x 3x 15 5x 2x 2x 8 100x 120x a Modelo matemático na Explícita 2 2 1 22 21 12 11 2 1 t 2 1 2 1 2 1 2 1 2 1 2 1 a a a a A A X a s max Z Notas de Aula Prof Edgard Básica 1 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 2 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 3 TAHA Hamdy A Pesquisa operacional 8 ed São Paulo Pearson Prentice Hall 2008 Ebooks Complementar 4 BAZARAA M S JARVIS John J SHERALI Hanif D Linear programming and network flows 2nd ed New York J Wiley Sons c1990 5 BELFIORE Patrícia Prado FÁVERO Luiz Paulo Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2013 6 COLIN Emerson C Pesquisa operacional 170 aplicações em estratégia finanças logística produção marketing e vendas 2 Rio de Janeiro Atlas 2017 Ebooks 7 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 8 PIZZOLATO Nélio Domingues GANDOLPHO André Alves Técnicas de otimização Rio de Janeiro LTC 2009 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Otimização de Processos do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras
Texto de pré-visualização
Notas de Aula da Disciplina de Otimização de Processos Prof Edgard Pedroso Arquivo de aulas n o 01 Apresentação do plano de ensino Conceitos Introdutórios Modelagem Matemática 2 Pesquisa Operacional PO A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais Tem como foco a tomada de decisões Para atingir seus objetivos aplica conceitos e métodos de outras áreas científicas para concepção planejamento ou operação de sistemas e processos Prof Edgard 3 Os Modelos são representações simplificadas da realidade que preservam para determinadas situações e enfoques uma equivalência adequada MODELAGEM Como o modelo é uma simplificação do problema real toda solução do modelo é uma aproximação da solução do problema real Prof Edgard 4 Suponha que por motivos justificáveis uma certa dieta alimentar esteja restrita a leite desnatado carne magra de boi carne de peixe e salada Sabese ainda que os requisitos nutricionais serão expressos em termos de vitaminas A B e C e controlados por suas quantidades mínimas em miligramas uma vez que são indispensáveis à preservação da saúde da pessoa que estará se submetendo à dieta A tabela a seguir resume a quantidade de cada vitamina em disponibilidade nos alimentos e a sua necessidade mínima diária de consumo para boa saúde da pessoa Problema da Dieta Exemplos de Problemas de Pesquisa Operacional 5 Problema da Dieta Alimento Vitamina Leite L Carne Kg Peixe Kg Salada 100g Requisito Nutricional Mínimo A 2 mg 2 mg 10 mg 20 mg 11 mg B 50 mg 20 mg 10 mg 20 mg 70 mg C 80 mg 70 mg 10 mg 80 mg 250 mg Custo R 200litro R 400Kg R 150Kg R 100100g Desejase obter o requisito nutricional mínimo com o menor custo possível Prof Edgard 6 Problema da Dieta Variáveis de Decisão ou Variáveis Estruturais ou Níveis de Atividade x1 Quantidade de litros de leite x2 Quantidade de Kg de carne x3 Quantidade de Kg de peixe x4 Quantidade de unidades pctes de 100g de salada 4 3 2 1 x x x x X das variáveis Vetor Prof Edgard 7 Problema a Dieta Função Objetivo ou função custo ou de critério x x x x 4 3 2 1 1 51 4 2 Z x x x x 4 3 2 1 1 51 4 2 Matricial Notação X Z C t 1 51 4 2 de custos Vetor 4 3 2 1 c c c c C X Min Z C t Generaliza ndo tem se Prof Edgard 8 Problema da Dieta Restrições ou vínculos ou restrições tecnológicas 80 10 70 80 20 10 20 50 20 10 2 2 dos coeficientes tecnológicos Matriz A 250 70 11 dos termos independentes RHS Vetor 3 2 1 b b b b 0 0 0 0 250 80 10 70 80 70 20 10 20 50 11 20 10 2 2 Restrições 4 3 2 negatividade não de Restrições x x x x x x x x x x x x x x x x 1 4 3 2 1 4 3 2 1 4 3 2 1 x x x x 4 3 2 1 250 70 11 80 10 70 80 20 10 20 50 20 10 2 2 Notação Matricial b X A 0 0 0 0 Notação Matricial 4 3 2 1 x x x x Ο X Problema da Dieta Formulação Final Forma Explícita x x x x 4 3 2 1 1 51 4 2 Z Min 0 250 80 10 70 80 70 20 10 20 50 11 20 10 2 2 4 3 2 x x x x x x x x x x x x x x x x 1 4 3 2 1 4 3 2 1 4 3 2 1 sa sujeita a Sistema de inequações lineares com infinitas soluções viáveis pode ser escrito assim Problema da Dieta Formulação Final Forma Matricial x x x x 4 3 2 1 1 51 4 2 Z Min x x x x a s 4 3 2 1 250 70 11 80 10 70 80 20 10 20 50 20 10 2 2 0 0 0 0 4 3 2 1 x x x x 2 88 unidades de 100 g ou seja 288 g 0 00 Kg 0 00 Kg 0 25 L x x x x 4 3 2 1 min R 338 Z Solução ótima LINGO Language for Interactive General Optimizer 12 Notação e Termilogia Forma generalizada explicita do modelo x x x b x a x a x a b a x a x x a b a x a x x a c x c x c x n m n mn m m n n n n n n 0 min 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 sa Z 13 sa min X b AX C X Z T Ο Forma generalizada matricial do modelo x x x b x a x a x a b a x a x x a b a x a x x a c x c x c x n m n mn m m n n n n n n 0 min generalizada explicita de um modelo Forma 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 sa Z 1 1 1 2 1 1 2 1 2 22 21 1 12 11 2 1 0 0 0 min n n n 2 1 m m n n 2 1 m n mn m m n n n 2 1 n x x x b b b x x x a a a a a a a a a x x x c c c sa Z ou Notação e Termilogia 14 0 min 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 2 2 1 1 n m n mn m m n n n n n n x x x b x a x a x a b a x a x x a b a x a x x a sa c x c x c x Z n j j x j c 1 m 1 2 b com i x a i j n 1 j ij 1 1 b x a j n 1 j j 2 2 b x a j n 1 j j m j n 1 j mj b x a Forma generalizada c somatório 1 2 n para j 0 min 1 j i j n 1 j ij n j j j x m 2 1 b com i x a a s x c Z Definições x x x b x a x a x a b x a x a x a b x a a x x a n m n mn m m n n n n 0 2 1 2 2 1 1 2 2 2 22 1 21 1 1 2 12 1 11 m 1 2 i com b x a i j n 1 j ij ou 1 Qualquer conjunto de valores para as variáveis x1 x2 xn que satisfaça todas as restrições é denominado solução viável ou factível 2 O conjunto de todas as soluções viáveis formam a Região Viável 3 Entre todas as soluções viáveis aquela que otimiza maximiza ou minimiza a função objetivo é denominada de solução ótima Sistema de inequações lineares com infinitas soluções viáveis 16 Técnicas aplicadas para resolução dos modelos matemáticos em PO Prof Edgard 17 Problema de Manufatura ou de Programação de Produção Uma fábrica de automotores produz Automóveis Caminhões A fábrica tem duas linhas de montagem Linha de Montagem 1 Estrutura Linha de Montagem 2 Acabamento 18 Problema de Manufatura Realiza operações básicas de montagem e trabalha com 05 homensdia em cada caminhão e com 02 homensdia cada automóvel Por causa de limitações de espaço e mão de obra qualificada a fábrica dispõe apenas de 180 homensdia nessa linha de montagem por semana Linha de Montagem 1 Prof Edgard 19 Problema de Manufatura Executa operações de acabamento ela trabalha com 3 homensdia em cada caminhão e 3 homensdia em cada automóvel que produz Por causa de limitações de espaço e mão de obra qualificada a fábrica dispõe apenas 135 homens dia nessa linha por semana Linha de Montagem 2 Prof Edgard 20 Problema de Manufatura Quantos caminhões e quantos automóveis a empresa deve fabricar por semana para obter lucro máximo Problema A divisão de custos da empresa estima que obtém um lucro de R 300000 em cada caminhão e R 200000 em cada automóvel Prof Edgard 21 Problema de Manufatura Variáveis de Decisão x1 Nº de carros fabricados em uma semana carrossemana x2 Nº de caminhões fabricados em uma semana caminhõessemana Função Objetivo custo x x 2 1 3000 2000 Z Linha de montagem Consumo de mão de obra em cada carro Consumo de mão de obra em cada caminhão Disponibilidade de mão de obra em cada linha por semana LM1 2 homensdiacarro 5 homensdiacaminhão 180 homensdiasemana LM2 3 homensdiacarro 3 homensdiacaminhão 135 homensdiasemana Lucro R 200000carro R 300000caminhão 22 Problema de Manufatura Restrições relativas as disponibilidades de mão de obra por semana 0 x x são inteiros 0 x x linha 2 3 x 135 3x linha 1 5 x 180 2x 2 1 2 1 2 1 2 1 Prof Edgard 23 Formulação Final x x 2 1 3000 2000 Max Z sa 0 x x são inteiros 0 x x 3 x 135 3x 5 x 180 2x 2 1 2 1 2 1 2 1 Problema de Manufatura Prof Edgard Prof Edgard 24 LINDO Linear Interactive and Discrete Optimizer 25 Problema da Cooperativa Agrícola Prof Edgard Uma cooperativa agrícola opera três fazendas cujas produtividades são consideradas iguais A produção da fazenda depende fundamentalmente da área disponível para plantio e da água de irrigação A cooperativa procura diversificar sua produção de modo a plantar três tipos de cultura em cada fazenda milho arroz e feijão Cada tipo de cultura demanda por certa quantidade de água Para reduzir o conflito no uso das colheitadeiras que são alugadas estabeleceramse limites de área de produção dentro de cada tipo de cultura As tabelas a seguir resumem os dados tecnológicos Pedese um programa de produção que defina a área de plantio de cada cultura em cada fazenda de modo a otimizar o lucro total da cooperativa 26 Problema da Cooperativa Agrícola Fazenda Área p cultivo acres Água disponível Litros 1 400 1800 2 650 2200 3 350 950 Prof Edgard Cultura Área máxima de cultivo por cultura para evitar o conflito das colheitadeiras acres Consumo de Água Litros por acre Lucro Rr por Acre Milho 660 55 5000 Arroz 880 40 4000 Feijão 400 35 800 1 acre4047 m2 27 Problema da Cooperativa Agrícola Variáveis de Decisão Áreas em acres a serem destinadas para cultivo de Feijão na fazenda 3 X Feijão na fazenda 2 X Feijão na fazenda 1 X Arroz na fazenda 3 X Arroz na fazenda 2 X Arroz na fazenda 1 X milho na fazenda 3 X milho na fazenda 2 X milho na fazenda 1 X 3F 2F 1F 3A 2A 1A 3M 2M 1M 28 Problema da Cooperativa Agrícola Função Objetivo Acre Lucro por de acres de Feijão Quant 3F 2F 1F Lucro por Acre de acres de Arroz Quant 3A 2A 1A Lucro por Acre de acres de Milho Quant 3M 2M 1M 800 X X X 4000 X X X 5000 X X X Z Prof Edgard 29 Problema da Cooperativa Agrícola Restrições De área a ser cultivada por fazenda 350 X X X 650 X X X 400 X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M Prof Edgard 30 Problema da Cooperativa Agrícola Restrições De litros de água disponível por fazenda 950 X 35 X 40 X 55 2200 X 35 X 40 X 55 1800 X 35 X 40 X 55 3F de feijão acre litros 3A de arroz acre litros 3M de milho acre litros 2F de feijão acre litros 2A de arroz acre litros 2M de milho acre litros 1F de feijão acre litros 1A de arroz acre litros 1M de milho acre litros Prof Edgard 31 Problema da Cooperativa Agrícola Restrições De área máxima de cultivo por cultura de forma a evitar o conflito das colheitadeiras 400 X X X 880 X X X 660 X X X 3F 2F 1F 3A 2A 1A 3M 2M 1M Restrições Nãonegatividade 0 X X X X X X X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M 32 Formulação Final 3F 2F 1F 3A 2A 1A 3M 2M 1M X X X 800 X X X 4000 X X X 5000 Max Z sa 350 X X X 650 X X X 400 X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M 950 35X 40X 55X 2200 35X 40X 55X 1800 35X 40X 55X 3F 3A 3M 2F 2A 2M 1F 1A 1M 400 X X X 880 X X X 660 X X X 3F 2F 1F 3A 2A 1A 3M 2M 1M 0 X X X X X X X X X 3F 3A 3M 2F 2A 2M 1F 1A 1M Sejam quatro fornecedores de um determinado produto origem 1 origem 2 origem 3 origem 4 com suas capacidades de produção conhecidas 10 20 12 e 13 unidades respectivamente e três centros de distribuição destino 1 destino 2 destino 3 com suas demandas também conhecidas 8 32 e 15 unidades respectivamente Devese determinar que quantidades devem ser transportadas de cada origem para cada destino afim de minimizar o custo com transporte atendendo às restrições de oferta e demanda Na tabela a seguir são apresentados os custos unitários por unidade com transporte nos diversos roteiros possíveis Exemplo Problema de Transporte Exemplo A tabela abaixo mostra os custos unitários R com transporte a disponibilidade ou ofertas em unidades de produto nas origens fornecedores e as necessidades ou demandas em unidades de produto nos destinos centros de distribuição Custo de transporte por unidade Centros de Distribuição Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Fornecedores D1 8 D2 32 D3 15 O110 O220 O312 O413 6 13 10 5 12 1 9 7 6 5 4 8 Diagrama de Fluxo Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Nós de Oferta Nós de Demanda Modelo 0 x x x x x x x x x x x x 15 x x x x 32 x x x x 8 x x x x 13 x x x x 12 x x 20 x x x x x 10 x 4x 6x 10x 5x 9x 7 1x 12x 13x 8x 5x 6x 43 42 41 33 32 31 23 22 21 13 12 11 43 33 23 13 42 32 22 12 41 31 21 11 43 42 41 33 32 31 23 22 21 13 12 11 43 42 41 33 32 31 23 22 21 13 12 11 a s min Z Destino 1 Destino 2 Destino 3 Ofertas Origem 1 6 5 8 10 Origem 2 13 12 1 20 Origem 3 7 9 5 12 Origem 4 10 6 4 13 Demandas 8 32 15 55 Uma empreiteira dispõe de 4 gruas cada uma armazenada em uma de suas sedes 123 e 4 e necessita mandálas com urgência para cada uma de suas obras sediadas nas cidades 123 e 4 Determine o fluxo de designações que minimize a distância das alocações sendo dadas as distâncias em quilômetros dos diversos percursos possíveis Problema de Designação A tabela abaixo mostra as distâncias entre as origens e os destinos Distâncias em quilômetros Localização das obras Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 Sedes O11 O21 O31 O41 4 9 14 21 5 12 7 11 9 4 2 12 Diagrama de Fluxo possível Nós de Oferta Nós de Demanda Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 D1 1 D2 1 D3 1 D4 1 34 17 12 25 Modelo 10 1 x x x x 1 x x x x x 1 x x x 1 x x x x x 1 x x x x 1 x x x x 1 x x x x x x 1 x 2x 12x 9x 14x x 4 7x 25x 11x 12x 5x 9x 17x 12x 21x 4x 4x 3 44 34 24 14 43 33 23 13 42 32 22 12 41 31 21 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 ij X a s min Z Destino 1 Destino 2 Destino 3 Destino 4 Ofertas Origem 1 34 4 21 12 1 Origem 2 17 9 5 12 1 Origem 3 11 25 7 4 1 Origem 4 14 9 12 2 1 Demandas 1 1 1 1 4 43 Um jovem atleta se sente atraído pela prática de dois esportes natação e ciclismo A natação exige um gasto de R 300 por seção de duas horas O ciclismo exige um gasto de R 200 por seção de duas horas Ele dispõe de R 7000 para este fim Seus afazeres disponibilizam em empregar para este fim no máximo 18 horas mensais e 80000 calorias Cada seção de natação consome 1500 calorias e ciclismo 1000 calorias O problema consiste em planejar seu treinamento de forma a maximizar o número de seções de treinamento Com base nestes dados faça a modelagem do problema como um problema de programação linear indicando a função objetivo e todas as restrições Determine ainda o vetor das variáveis de decisão X o vetor de custos C e Ct a matriz dos coeficientes das restrições A o vetor dos termos independentes b Represente o número de seções de natação por X1 e o número de seções de ciclismo por X2 Não é necessário a resolução do PL basta a modelagem No 01 TDE1 Um fabricante produz dois tipos de aço normal e especial Uma tonelada de aço normal necessita de 2 horas no forno de soleira aberta e 5 horas de molho uma tonelada do aço especial precisa de 2 horas de forno de soleira aberta e 3 horas de molho O forno de soleira aberta está disponível 8 horas por dia e o fosso onde as peças ficam de molho está disponível 15 horas por dia O lucro em uma tonelada de aço normal é de 12000 unidades monetárias e o lucro em uma tonelada de aço especial é de 10000 unidades monetárias Desejase determinar quantas toneladas de cada tipo de aço devem ser manufaturadas de modo a maximizar o lucro Com base nestes dados faça a modelagem do problema como um problema de programação linear indicando a função objetivo e todas as restrições Determine ainda o vetor das variáveis de decisão X o vetor de custos C e Ct a matriz dos coeficientes das restrições A o vetor dos termos independentes b Represente o número de toneladas de aço normal por X1 e o número de toneladas de aço especial por X2 Não é necessário a resolução do PL basta a modelagem No 02 TDE1 45 Respostas 80000 18 70 b b b e Vetor dos termos independentesb 1000 1500 2 2 2 3 d Matriz dos coeficientes das restrições 1 1 c c 1 C 1 c c c Vetor de custos C x x b Vetor das variáveis de decisão Z Naturais ou Inteiros não negativos ou x x x x 1000x 80000 1500x 2x 18 2x 2x 70 3x x x a Modelo matemático na Explícita 1 3 2 1 32 31 22 21 12 11 2 1 t 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 a a a a a a A X a s max Z 46 Respostas 15 8 b b b e Vetor dos termos independentes b 3 5 2 2 d Matriz dos coeficientes das restrições 100 120 c c 100 C 120 c c c Vetor de custos C x x b Vetor das variáveis de decisão 0 Reais não negativos x x 3x 15 5x 2x 2x 8 100x 120x a Modelo matemático na Explícita 2 2 1 22 21 12 11 2 1 t 2 1 2 1 2 1 2 1 2 1 2 1 a a a a A A X a s max Z Notas de Aula Prof Edgard Básica 1 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 2 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 3 TAHA Hamdy A Pesquisa operacional 8 ed São Paulo Pearson Prentice Hall 2008 Ebooks Complementar 4 BAZARAA M S JARVIS John J SHERALI Hanif D Linear programming and network flows 2nd ed New York J Wiley Sons c1990 5 BELFIORE Patrícia Prado FÁVERO Luiz Paulo Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2013 6 COLIN Emerson C Pesquisa operacional 170 aplicações em estratégia finanças logística produção marketing e vendas 2 Rio de Janeiro Atlas 2017 Ebooks 7 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 8 PIZZOLATO Nélio Domingues GANDOLPHO André Alves Técnicas de otimização Rio de Janeiro LTC 2009 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Otimização de Processos do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras