Introdução à Pesquisa Operacional: Tomada de Decisão e Modelagem Matemática

Pesquisa Operacional Prof Victor Gonçalves Conteúdos do Capítulo Introdução a Pesquisa Operacional Tomada de Decisão Fatores Relevantes Classificação Abordagem de Management Science no processo de tomada de decisão Processo de Modelagem Modelos Matemáticos Modelagem de Problemas em Planilhas Eletrônicas A Pesquisa Operacional PO como ciência surgiu para resolver de uma forma mais eficiente os problemas na administração das organizações originados pelo acelerado desenvolvimento provocado pela revolução industrial Para quê a Pesquisa Operacional PO Origem da Pesquisa Operacional Origem da Pesquisa Operacional Produção Distribuição de recursos Utilização ótima de recursos Gestão da Organização Mais desenvolvimento mais complexidade na PO e Gestão A partir da Revolução Industrial aumentam os problemas na gestão das organizações Os diferentes componentes dentro duma organização são sistemas autônomos com objetivos e gestão próprios os objetivos cruzamse o que pode ser melhor para uns pode ser prejudicial para outros O Problema Como gerir para obter uma melhor eficácia dentro de toda a organização A origem da PO como ciência é atribuído à coordenação das operações militares durante a 2ª Guerra Mundial quando os líderes militares solicitaram que cientistas estudassem problemas como posicionamento de radares armazenamento de munições e transporte de tropa etc A aplicação do método científico e de ferramentas matemáticas em operações militares passou a ser chamado de Pesquisa Operacional Quando é que surgiu a PO Surgimento da PO Em 1947 George Dantzig e outros cientistas do Departamento da Força Aérea Americana apresentaram um método denominado Simplex para a resolução dos problemas de Programação Linear PL Outros cientistas que dedicaram os seus estudos a PO à pesquisa do ótimo foram na Antiguidade Euclides Newton Lagrange no século XX Leontief Von Neumann Kantarovich Surgimento da PO Pesquisa estudo das Operações atividades O que é a Pesquisa Operacional Pesquisa das operações atividades de uma organização Natureza da PO 1 Uma abordagem científica na tomada de decisões O que é a Pesquisa Operacional Um conjunto de métodos e modelos matemáticos aplicados à resolução de complexos problemas nas operações atividades de uma organização Natureza da PO 2 A PO tem provocado um significativo impacto na gestão e administração de empresas em diferentes organizações Os serviços militares dos EUA continuaram a trabalhar ativamente nesta área Com o desenvolvimento da informática nas últimas décadas a PO tem sido estendida a numerosas organizações Impacto da PO PO Ciência da Administração Denominada a ciência da administração a sua utilização e implementação tem sido estendida à business economia industria industria militar engenharia civil governos hospitais etc Quais são os ramos mais importantes desenvolvidos na PO Os Ramos da PO PROGRAMAÇÃO MATEMÁTICA Programação Linear LP Problemas de distribuição de recursos Problemas de transporte Problemas de planejamento da produção Problemas de corte de materiais etc Programação Não Linear Programação Dinâmica Programação Inteira otimização Global Programação planejamento de atividades Outros Ramos da PO Quais são outros ramos da PO OUTROS RAMOS DA PO são Análise Estatística Teoria de Jogos Teoria de Filas organização do tráfego aéreo Construção de barragens etc Simulação Gestão de estoques etc Exemplos de Problemas de Decisão Se existem vários caminhos que ligam duas cidades qual é a que propicia o mínimo de gasto de combustível Se um dado combustível é obtido de uma mistura de produto de preços variados qual a composição de menor custo com poder calorífico suficiente Se tanto a Matéria Prima quanto a Mão de Obra são limitados qual a quantidade produtos que maximiza o lucro da empresa Se em uma região existem casas que devem ser interconectados com uma rede de água qual a que minimiza o gasto com tubulação Se existem vários ativos financeiros qual a combinação que melhor reflete o compromisso entre o risco e o retorno Se o espaço para armazenamento é limitado de quanto deve ser o pedido de material para atender a demanda de um certo período Exemplos de Problemas de Decisão Exemplo 1 Um problema de PO que determina um plano ótimo de Produção Uma empresa produz três tipos de portas a partir de um determinado material Sabendo que diariamente a empresa dispõe de 500 kg de material e 600 horas de trabalho determinar um plano ótimo de produção que corresponda ao maior lucro A tabela seguinte indica a quantidade de material e horas de trabalho necessárias para a produção de uma porta de cada tipo assim como o lucro unitário de cada uma delas Recursos Porta 1 Porta 2 Porta 3 Quantidade de material 8 kg 4kg 3 kg Horas de Trabalho 7 horas 6 horas 8 horas Lucro Unitário 50 Euros 40 Euros 55 Euros Decisão a ser tomada Qual será a quantindade de portas a serem produzidas para obterse o máximo lucro PESQUISA OPERACIONAL Uma empresa pode fabricar dois produtos 1 e 2 Na fabricação do produto 1 a empresa gasta nove horas homem e três horasmáquina a tecnologia utilizada é intensiva em mãodeobra Na fabricação do produto 2 a empresa gasta uma hora homem e uma horamáquina a tecnologia é intensiva em capital A empresa dispõe de 18 horashomem e 12 horas máquina para um período de produção Sabese que os lucros líquidos dos produtos são 4 e 1 respectivamentesendo x qtd Quanto a empresa deve fabricar de cada produto para ter o maior lucro Caso se obtenha algum recurso financeiro externo para investimento em expansão em quais dos recursos a empresa deveria aplicálo Qual seria o impacto no lucro se alguns trabalhadores faltassem ao trabalho limitando as horas homens disponíveis em 15 horas Figura 11 Passos para implementação de PO O PPL A função lucro Não havendo economia de escala É claro que o lucro máximo seria ilimitado se não fosse a escassez de recursos Em outros problemas a demanda do mercado também é um fator limitador 2 4 1 x x L As restrições Não se pode utilizar o que não se tem A quantidade utilizada deve ser menor ou igual a quantidade disponível As quantidades de fabricação devem ser não negativas 18 9 2 1 x x H H 0 0 2 1 x x 12 3 2 1 x x HM 18 9 2 1 x x H H 0 0 2 1 x x 12 3 2 1 x x M H 2 1 4 2 1 x x L Max x x Função Objetivo Matriz Tecnológica Variáveis de Decisão Limitações Conjunto das Possibilidades de Produção Valores Possíveis quando 0 0 2 1 x x 1x 2 x 0 18 9 2 1 x x Valores Possíveis quando 2 18 1x 2x 0 18 9 2 1 x x 12 3 2 1 x x Valores Possíveis quando 4 12 1x 2x 0 12 3 2 1 x x Conjunto de Possibilidades 12 2 1x 2 x 0 L x x L x x 1 2 2 1 4 4 Para cada valor de L temse uma reta no plano x2 vs x1 Dado um valor de L é possível traçar um lugar geométrico uma reta onde as várias combinações de produção dão o mesmo lucro essas curvas são conhecidas como isolucros Retas com inclinações negativas 1x 2 x 0 5 L 7 L 9 L Direção de Crescimento do Lucro Conjunto de Possibilidades 12 2 1x 2 x 0 13 L 1 9 Que características permitiram a solução O conjunto de possibilidades era convexo Um conjunto é convexo quando toda combinação convexa de dois elementos dele pertence a ele Uma combinação convexa de dois elementos x e y é um terceiro elemento z tal que zax1ay onde 0 a 1 É possível definir combinação convexa de n elementos Valores p Restrição 1 Conjunto de Possibilidades é vazio Não há solução compatível Exemplo 1 x 2 x 0 Valores p Restrição 2 Conjunto de Possibilidades A solução é ilimitada Não há como definir a decisão Exemplo 1 x 2 x 0 Direção de Crescimento do Lucro Conjunto de Possibilidades 1x 2 x 0 As soluções são combinações lineares dos pontos extremos Isolucro AULA 3 PESQUISA OPERACIONAL CONSIDEREMOS UM PROBLEMA DE PROGRAMAÇÃO LINEAR PPL QUALQUER O CONJUNTO DE TODAS AS SOLUÇÕES QUE SATISFAZEM AS RESTRIÇÕES DO PPL É CHAMADO CONJUNTO DE SOLUÇÕES VIÁVEIS OU REGIÃO VIÁVEL DO PPL MINIMIZAR C1X1 C2X2 SUJEITO A A11X1 A12X2 B1 A21X1 A22X2 B2 A31X1 A32X2 B3 X1 0 X2 0 c1x1 c2x2 z1 c1x1 c2x2 z2 z1 c1x1 c2x2 z3 z2 A O D C B ANÁLISE DE TODAS AS POSSIBILIDADES AO REPRESENTARMOS GRAFICAMENTE A REGIÃO VIÁVEL DE UM PPL COM DUAS VARIÁVEIS OU SEJA NO R2 VAMOS CONSIDERAR PARA ISSO UM PPL ONDE DESEJARMOS MAXIMIZAR SUA FUNÇÃO OBJETIVO A UMA ÚNICA SOLUÇÃO ÓTIMA B TODOS OS PONTOS DE UM SEGMENTO DE RETA SÃO SOLUÇÕES ÓTIMAS E FORNECEM O MESMO VALOR DA FUNÇÃO OBJETIVO C SOLUÇÃO ILIMITADA OU SEJA DADA QUALQUER SOLUÇÃO VIÁVEL PARA O PPL SEMPRE PODEMOS ENCONTRAR UM OUTRO PONTO DENTRO DA REGIÃO VIÁVEL QUE AUMENTE O VALOR DA FUNÇÃO OBJETIVO D TODOS OS PONTOS DE UMA SEMIRETA SÃO SOLUÇÕES ÓTIMAS E FORNECEM O MESMO VALOR DA FUNÇÃO OBJETIVO O espaço tem que ser convexo EX CONJUNTOS CONVEXOS EM ℝ² EX CONJUNTOS NÃO CONVEXOS EM ℝ² 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 9 2 6 2 2 2 1 2 1 2 1 2 1 x x x x x x x x httpwwwquickmathcomwebMathematica3quickm athgraphsinequalitiesadvancedjsp 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 3 3 2 2 2 1 2 1 2 1 x x x x x x 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 240 30 40 160 40 20 2 1 2 1 2 1 x x x x x x 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 28 8 7 6 2 2 1 2 1 2 1 x x x x x x Uma grande fábrica de móveis dispõe em estoque de 300m de tábuas 600m de pranchas e 500m de painéis de aglomerado Oferece normalmente 4 modelos de móveis Escrivaninha Mesa Armário e Prateleira Os modelos são vendidos respectivamente por 10000 8000 12000 3000 E consomem Escrivaninha 1m tábua 3m de painéis Mesa 1m tábua 1m prancha 2m painéis Armário 1m tábua 1m prancha 4 painéis Prateleira 4m tábua 2 de prancha A empresa objetiva a maximização dos lucros Certa empresa fabrica 2 produtos P1 e P2 O lucro por unidade de P1 é de 100 reais e o lucro unitário de P2 é de 150 reais A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2 O tempo mensal disponível para essas atividades é de 120 horas As demandas esperadas para os dois produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês A empresa objetiva maximizar o lucro da empresa Um fazendeiro tem que decidir o quanto vai plantar de milho e de alfafa Os lucros são de R200000 por alqueire de milho e de R100000 por alqueire de alfafa Suponha que suas limitações sejam terra disponível é de 8 alqueires e água disponível para irrigação de 80000 litros sendo que desejase plantar no máximo 4 alqueires de milho Cada alqueire de milho requererá 10000 litros de água para irrigação e cada alqueire de alfafa requererá 20000 litros de água Modele o PPL de maneira a maximizar o lucro do fazendeiro AULA 4 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 9 3 6 2 4 2 1 2 1 2 1 2 1 x x x x x x x x 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 3 3 2 2 2 1 2 1 2 1 x x x x x x 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 240 30 40 160 40 20 2 1 2 1 2 1 x x x x x x 1 Construa o conjunto de possibilidades delimitados pelas funções 0 0 28 8 7 6 2 2 1 2 1 2 1 x x x x x x Um carpinteiro possui 6 peças de madeira e dispõe de 28 horas de trabalho para confeccionar biombos ornamentais Dois modelos venderam muito bem no passado de maneira que ele se limitou a esses dois tipos Ele estima que o modelo I requer 2 peças de madeira e 7hs de trabalho enquanto o modelo II necessita de 1 peça de madeira e 8hs de trabalho Os preços dos modelos são respectivamente R12000 e R 8000 Quantos biombos de cada modelo o carpinteiro deve montar se deseja maximizar o rendimento obtido com as vendas Determinar as quantidades de cada tipo de ração que devem ser dadas diariamente a cada animal de forma a conseguir uma certa qualidade nutritiva a um custo mínimo Os dados relativos ao custo de cada tipo de ração às quantidades mínimas diárias de ingredientes nutritivos básicos a fornecer a cada animal bem como às quantidades destes existentes em cada tipo de ração gkg constam no quadro seguinte Monte e Resolva o PPL Minimize z 10x 5y O administrador de uma pequena fábrica de móveis está pensando em otimizar a utilização dos recursos de seu estoque Essa fábrica produz poltronas em dois modelos Albany e Bridget forradas em brim e lona Ele sabe que para forrar uma poltrona Albany são precisos 2 m2 de brim e 6 m2 de lona Já para forrar uma poltrona Bridget são precisos 4 m2 de brim e 4 m2 de lona No estoque a fábrica dispõe de 160 m2 de brim e 240 m2 de lona Qualquer dos modelos de poltrona é vendido por R 16000 Com essas informações de que modo o administrador pode sugerir à produção da fábrica para obter a máxima renda Em outras palavras qual é o número de poltronas de cada modelo que devem ser forradas para otimizar a renda Uma fábrica tem três tipos de máquinas M₁ M₂ M₃ cada uma das quais dever ser usada na manufatura de seus produtos P₁ e P₂ Sabendo que o lucro por unidade de P₁ é 40 um e o lucro por unidade de P₂ é 60 um decida quanto fabricar de cada produto por semana a fim de maximizar os lucros de acordo com a seguinte tabela Considere que uma doceira deseja abrir um pequeno negocio para produção de balas A principio ela esta considerando produzir dois tipos de balas caramelo e nozes Na produção são utilizados três ingredientes leite açúcar e nozes A doceira tem em estoque 10kg de açúcar 1kg de nozes e 6l de leite A composição da bala de caramelo e 40 de leite e 60 de açúcar e para as balas de nozes os ingredientes devem ser misturados na seguinte proporção 40 de leite 50 de açúcar e 10 de nozes Cada quilo de bala de caramelo pode ser vendido a R1000 enquanto um quilo de bala de nozes pode ser vendido por R1300 Qual deve ser a produção de cada tipo de bala para obter a maior receita Em uma dieta cada 100 g de alimento A e B fornecem os seguintes elementos nutritivos em unidades Variáveis de decisão x₁ quantidade de A em 100 g x₂ quantidade de B em 100 g Objetivo min z₁ 50x₁ 25x₂ minimizar o custo min z₂ 300x₁ 500x₂ minimizar quantidade de calorias Restrições x₁ 3x₂ 8 quantidade de carboidratos 3x₁ 4x₂ 19 quantidade de vitaminas 3x₁ x₂ 7 quantidade de proteínas x₁ x₂ 0 condição de nãonegatividade Por simples inspeção visual é possível identificar o ponto 14 do plano cartesiano como sendo o ponto onde a função custo é minimizada obtendo um custo mínimo de 150 um com consumo total de 2300 kcal enquanto o ponto 51 minimiza a quantidade de calorias 2000 kcal com custo de 275 um Um individuo deve seguir uma dieta balanceada por recomendação medica baseada no consumo de diversos tipos de alimentos de forma a suprir suas necessidades diárias de energia que pode variar de 3100 a 3300 kcal e nutrientes essenciais para a boa saúde Uma porção de cada alimento fornece uma porcentagem da Quantidade Diária Recomentada QDR de diferentes nutrientes de acordo com a tabela Preço e quantidade calórica de cada porção também são informados na tabela Desejase saber qual a combinação ideal de alimentos com custo mínimo e que satisfaça as necessidades nutricionais unidade QDR Alimentos 1 2 3 4 5 6 7 Valor energético kcal 225 170 76 300 146 45 160 Proteína g 37 35 3 48 8 13 06 8 Vitamina A mg 900 7 2 Vitamina C mg 300 3 Ferro mg 10 29 13 16 1 Cálcio mg 500 5 12 27 16 Custo R 050 014 019 020 010 030 min z 05x1 014x2 019x3 015x4 02x5 01x6 03x7 AULA 5 PESQUISA OPERACIONAL Determinar as quantidades de cada tipo de ração que devem ser dadas diariamente a cada animal de forma a conseguir uma certa qualidade nutritiva a um custo mínimo Os dados relativos ao custo de cada tipo de ração às quantidades mínimas diárias de ingredientes nutritivos básicos a fornecer a cada animal bem como às quantidades destes existentes em cada tipo de ração gkg constam no quadro seguinte Monte e Resolva o PPL Minimizar z 10x 5y Uma fábrica tem três tipos de máquinas M1 M2 M3 cada uma das quais dever ser usada na manufatura de seus produtos P1 e P2 Sabendo que o lucro por unidade de P1 é 40 um e o lucro por unidade de P2 é 60 um decida quanto fabricar de cada produto por semana a fim de maximizar os lucros de acordo com a seguinte tabela Máquinas Horas P1 Horas P2 Horas disponíveis M1 2 1 70 M2 1 1 40 M3 1 3 90 Considere que uma doceira deseja abrir um pequeno negocio para produção de balas A principio ela esta considerando produzir dois tipos de balas caramelo e nozes Na produção são utilizados três ingredientes leite açúcar e nozes A doceira tem em estoque 10kg de açúcar 1kg de nozes e 6l de leite A composição da bala de caramelo e 40 de leite e 60 de açúcar e para as balas de nozes os ingredientes devem ser misturados na seguinte proporção 40 de leite 50 de açúcar e 10 de nozes Cada quilo de bala de caramelo pode ser vendido a R1000 enquanto um quilo de bala de nozes pode ser vendido por R1300 Qual deve ser a produção de cada tipo de bala para obter a maior receita RESOLVA O PPL Em uma dieta cada 100 g de alimento A e B fornecem os seguintes elementos nutritivos em unidades Elemento nutritivo A B Carboidratos 1 3 Vitaminas 3 4 Proteínas 3 1 As quantidade mínimas necessárias de elementos nutritivos por dia são 8 unidades de carboidratos 19 unidades de vitaminas e 7 unidades de proteínas Cada 100 g do alimento A contém 300 kcal kilocalorias e custa 50 um enquanto cada 100 g do alimento B tem 500 kcl e custa 25 um Como é possível minimizar o custo e a quantidade de calorias da dieta formada pelos alimento A e B Variáveis de decisão x₁ quantidade de A em 100 g x₂ quantidade de B em 100 g Objetivo min z₁ 50x₁ 25x₂ minimizar o custo min z₂ 300x₁ 500x₂ minimizar quantidade de calorias Restrições x₁ 3x₂ 8 quantidade de carboidratos 3x₁ 4x₂ 19 quantidade de vitaminas 3x₁ x₂ 7 quantidade de proteínas x₁ x₂ 0 condição de nãonegatividade Por simples inspeção visual é possível identificar o ponto 14 do plano cartesiano como sendo o ponto onde a função custo é minimizada obtendo um custo mínimo de 150 um com consumo total de 2300 kcal enquanto o ponto 51 minimiza a quantidade de calorias 2000 kcal com custo de 275 um Um individuo deve seguir uma dieta balanceada por recomendação medica baseada no consumo de diversos tipos de alimentos de forma a suprir suas necessidades diárias de energia que pode variar de 3100 a 3300 kcal e nutrientes essenciais para a boa saúde Uma porção de cada alimento fornece uma porcentagem da Quantidade Diária Recomentada QDR de diferentes nutrientes de acordo com a tabela Preço e quantidade calórica de cada porção também são informados na tabela Desejase saber qual a combinação ideal de alimentos com custo mínimo e que satisfaça as necessidades nutricionais unidade QDR Alimentos 1 2 3 4 5 6 7 Valor energético kcal 225 170 76 300 146 45 160 Proteína g 37 35 3 48 8 13 06 8 Vitamina A mg 900 7 2 Vitamina C mg 300 3 Ferro mg 10 29 13 16 1 13 02 09 Cálcio mg 500 5 12 27 16 49 45 285 Custo R 050 014 019 020 010 030 min z 0 5x₁ 0 14x₂ 0 19x₃ 0 15x₄ 0 2x₅ 0 1x₆ 0 3x₇ Aula 6 Pesquisa Operacional Prof Victor Gonçalves Questão 1 aula 6 Resolva o PPL Variáveis de decisão x₁ quantidade de A em 100 g Por simples inspeção visual é possível identificar o ponto 14 do plano cartesiano como sendo o ponto onde a função custo é minimizada obtendo um custo mínimo de 150 um com consumo total de 2300 kcal enquanto o ponto 51 minimiza a quantidade de calorias 2000 kcal com custo de 275 um Questão 2 Aula 6 Uma empresa tem a capacidade de produzir dois tipos de brinquedos com algumas restrições esta empresa deseja maximizar seu lucro Os dados disponibilizados são Fabricação de dois modelos de brinquedos B1 e B2 Lucros unitáriosdúzia R8 para B1 e R5 para B2 Recursos disponíveis 1000 kg de plástico especial 40 horas 2400 minutos para produção semanal Requisitos do Departamento de Marketing Produção total não pode exceder 700 dúzias Dados técnicos B1 requer 2 kg de plástico e 3 minutos por dúzia B2 requer 1 kg de plástico e 4 minutos por dúzia perguntas i Monte o problema PPL para que o lucro da fábrica seja maximizado ii Esboce o conjunto de possibilidades colocando X2representando a produção semanal de B2 na vertical e X1 na horizontal iii Encontre a melhor solução ou seja o par ordenado que maximize o lucro iv Encontre o lucro máximo v Esboce um novo gráfico com o conjunto de possibilidades e a reta de lucro que tangencia o ponto de máximo lucro Questão 3 aula 6 Dadas as seguintes restrições monte o conjunto de possibilidades Questão 4 aula 6 Monte o PPL Considere que uma doceira deseja abrir um pequeno negocio para produção de balas A principio ela esta considerando produzir dois tipos de balas caramelo e nozes Na produção são utilizados três ingredientes leite açúcar e nozes A doceira tem em estoque 10kg de açúcar 1kg de nozes e 6l de leite A composição da bala de caramelo e 40 de leite e 60 de açúcar e para as balas de nozes os ingredientes devem ser misturados na seguinte proporção 40 de leite 50 de açúcar e 10 de nozes Cada quilo de bala de caramelo pode ser vendido a R1000 enquanto um quilo de bala de nozes pode ser vendido por R1300 Qual deve ser a produção de cada tipo de bala para obter a maior receita O problema da Dieta Monte o PPL Um individuo deve seguir uma dieta balanceada por recomendação medica baseada no consumo de diversos tipos de alimentos de forma a suprir suas necessidades diárias de energia que pode variar de 3100 a 3300 kcal e nutrientes essenciais para a boa saúde Uma porção de cada alimento fornece uma porcentagem da Quantidade Diária Recomentada QDR de diferentes nutrientes de acordo com a tabela Preço e quantidade calórica de cada porção também são informados na tabela Desejase saber qual a combinação ideal de alimentos com custo mínimo e que satisfaça as necessidades nutricionais Valor energético kcal 225 170 76 300 146 45 160 min z 0 5x1 0 14x2 0 19x3 0 15x4 0 2x5 0 1x6 0 3x7 Simplex Prof Victor Gonçalves Método Simplex 1 3 x 4 R 2 2 x 12 2 R 1 2 3 2 18 x x 1 R 1x 2x 00 06 60 43 26 09 40 46 Começa do valor da FO de um vértice qualquer que pertença a o espaço de soluções viáveis É um procedimento iterativo que permite ir melhorando a solução de um PPL a cada passo O processo termina quando não é possível seguir melhorando uma determinada solução Caminha pelos vértices até encontrar uma solução que não possua soluções vizinhas melhores que ela Método Simplex A solução ótima pode não existir Quando não há uma solução viável restrições incompatíveis Quando não há um valor máximo ou mínimo da FO 1 ou mais variáveis tendem ao infinito e as restrições continuarem sendo satisfeitas Procedimentos forma canônicaforma padrão FORMA CANÔNICA FORMA PADRÃO 1 2 1 2 1 2 1 2 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x x x x x x 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x f x f x x f x x f f f O problema se transformou em encontrar uma solução de um sistema de equações lineares que maximize a FO Variáveis n5 Restrições m3 n m Método de Enumeração das Soluções Básicas Analisando podemos dizer que atribuir zero a uma variável significa não produzir um dos produtos ou utilizar toda a disponibilidade de recursos O número de soluções básicas possíveis 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x f x f x x f x x f f f nm variáveis iguais a zero solução básica C n m n n m m n m 5 3 5 5 C 10 3 3 2 soluções básicas possíveis Método de Enumeração das Soluções Básicas Variáveis não básicas São as variáveis zeradas igual a nm variáveis 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x f x f x x f x x f f f Variáveis básicas São as variáveis cujos valores são calculados pelo sistema de equações 1ª Combinação Variáveis Não Básicas 1 2 00 x x Variáveis Básicas 1 2 3 41218 f f f Solução Básica 1 2 1 2 3 0041218 x x f f f Solução Viável Z 0 Método de Enumeração das Soluções Básicas 2ª Combinação Variáveis Não Básicas 1 1 00 x f Variáveis Básicas 2 2 3 x f f Solução Básica Não existe Não existe Base Associada 3ª Combinação Variáveis Não Básicas 1 2 00 x f Variáveis Básicas 2 1 3 646 x f f Solução Básica 1 2 1 2 3 06406 x x f f f Solução Viável 30 Z 4ª Combinação Variáveis Não Básicas 1 3 00 x f Variáveis Básicas 2 1 2 94 6 x f f Solução Básica 1 2 1 2 3 094 60 x x f f f Solução Inviável Continuar Método de Enumeração das Soluções Básicas Solução Básica x1 x2 f1 f2 f3 FO Observação 1 004128 0 Viável 2 Não existe 3 06406 30 Viável 4 09460 Inviável 5 400126 12 Viável 6 Não existe 7 602120 Inviável 8 46006 Inviável 9 43060 27 Viável 10 26200 36 Viável Método de Enumeração das Soluções Básicas Solução Básica x1 x2 f1 f2 f3 FO Observação 1 004128 0 Viável 2 Não existe 3 06406 30 Viável 4 09460 Inviável 5 400126 12 Viável 6 Não existe 7 602120 Inviável 8 46006 Inviável 9 43060 27 Viável 10 26200 36 Viável 1 3 x 4 R 2 2 x 12 2 R 1 2 3 2 18 x x 1 R 1x 2x 00 06 60 43 26 09 40 46 Método de Enumeração das Soluções Básicas No problema vimos que n5 número de variáveis e m3 número de restrições tem 5 3 5 5 C 10 3 3 2 soluções básicas possíveis No caso de n10 e m5 teremos 10 5 10 10 C 252 5 5 5 No caso de n20 e m10 teremos 20 10 20 20 C 184756 10 10 10 Problemas de grande porte Simplex Desenvolvimento do Método Simplex Problemas Reais Método gráfico e enumeração Inviável Sistemática Qual o sistema de equações que deve ser resolvido Qual é o próximo sistema a ser resolvido que fornecerá uma solução melhor que os anteriores Como identificar uma solução ótima uma vez que tenhamos encontrado Método Simplex Passo 1 Transformar o PPL da sua forma Canônica para sua forma Padrão FORMA CANÔNICA 1 2 1 2 1 2 1 2 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x x x x x x FORMA PADRÃO 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x f x f x x f x x f f f O modelo Padrão na Forma Matricial 0 x b x A a s c x L Max x Modelo Padrão Todo modelo de programação linear pode ser posto na forma padrão que não é limitativa Um problema de minimização por exemplo pode ser resolvido pela maximização do negativo da função objetivo Restrições de podem ser multiplicadas por 1 para se tornarem restrições padrão Variáveis que possam assumir qualquer valor e não apenas valores positivos podem ser substituídas pela diferença de duas variáveis positivas Na modelagem de um problema de programação linear algumas situações específicas podem ocorrer o que pode levar a casos em uma forma matemática diferente da apresentada até o momento Entretanto alguns artifícios matemáticos ajudam a reduzir o modelo obtido à forma padrão estudada Estes artifícios são mostrados a seguir 451 Minimização de uma função A minimização de uma função zx é matematicamente análoga à maximização da negativa desta função zx Exemplo minimizar z c1 x1 c2 x2 cn xn é equivalente a maximizar z c1 x1 c2 x2 cn xn com z z Essa é uma das formas de se resolver os problemas de minimização utilizando o mesmo algoritmo Caso que queira resolver diretamente devemos alterar o critério de entrada das variáveis na base A variável que entra na base passa a ser aquela que tem o maior valor positivo na linha ztransformada Caso todas tenham coeficientes negativos ou nulos a solução obtida é ótima 452 Restrições de limite inferior Uma desigualdade em uma direção ou pode ser mudada para uma desigualdade na direção oposta pela multiplicação de ambos os lados da desigualdade por 1 Exemplo a1 x1 a2 x2 b é equivalente a a1 x1 a2 x2 b 453 Restrições de igualdade Uma equação pode ser substituída por duas desigualdades de direções opostas Exemplo a1 x1 a2 x2 b é equivalente a duas desigualdades simultâneas a1 x1 a2 x2 b a1 x1 a2 x2 b E assim Simplex Passo 1 Introdução das variáveis de folga passo 2 Montagem do quadro de coeficientes Passo 3 Criação da solução básica inicial passo 4 Variável que entra na base A Aquela que tem o maior valor negativo na linha da função objetivo B Quando não houver mais coeficientes negativos na linha da função objetivo a solução encontrada é ótima E assim Passo 5 Variável que sai da base A Dividir os termos independentes pelos coeficientes da coluna de trabalhocoluna da variável que entra B O menor coeficiente indica a variável que deve sair da baseobs entrar sempre no lugar da folga Passo 6 Transformar a matriz encontrandose a nova base Operação de Transformação 1 Na variável que entrou divida toda linha pelo valor do pivôtransformar o pivô em 1 2 Nas outras linhas zerar os valores da coluna de trabalho diferentes do pivôque será 1 para fazer isso sempre troque a linha por ela mais uma operação com a linha do pivô Método Simplex Passo 1 Transformar o PPL da sua forma Canônica para sua forma Padrão FORMA CANÔNICA 1 2 1 2 1 2 1 2 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x x x x x x FORMA PADRÃO 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x sujeito a x f x f x x f x x f f f Método Simplex Passo 2 Montar um quadro para ordenarmos as operações colocando neles apenas os coeficientes das variáveis 1 2 3 5 0 MAX Z x x Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 1 2 1 1 2 2 1 2 3 1 2 1 2 3 3 5 4 2 12 3 2 18 0 MAX Z x x s a x f x f x x f x x f f f Quadro Inicial A solução inicial será sempre obtida fazendo as variáveis originais do modelo iguais a zero e achando o valor das demais Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Quadro Inicial Das variáveis não básicas na primeira solução qual devese tornar positiva Das 3 variáveis básicas na primeira solução qual deverá ser anulado Deve ser a variável que MAIS CONTRIBUI para o lucro Entra x2 40 1226 1829 Será aquela associada à linha que tiver o menor quociente entre o elemento da última coluna e o correspondente elemento da coluna de entrada Sai f2 Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Quadro Inicial Pivô EquaçãoP ivô Para a mudança da base na busca por outra solução empregase 2 operações de cálculo 1 Na equação do Pivô 2 Nas demais equações incluindo Z Nova Equação do Pivô Equação do Pivô Pivô Coeficiente da Nova Equação Nova Equação Equaçãoanterior Coluna de Entrada do Pivô Gera uma nova solução básica Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 x2 0 1 0 12 0 6 f3 Z Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 x2 0 1 0 12 0 6 f3 Z Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 x2 0 1 0 12 0 6 f3 3 0 0 1 1 6 Z Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 x2 0 1 0 12 0 6 f3 3 0 0 1 1 6 Z 3 0 0 52 0 30 Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 f2 0 2 0 1 0 12 f3 3 2 0 0 1 18 Z 3 5 0 0 0 0 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 x2 0 1 0 12 0 6 f3 3 0 0 1 1 6 Z 3 0 0 52 0 30 Método Simplex Passo 3 Quadro I Como nos elementos da ÚLTIMA LINHA Equação do Z existe ainda um NÚMERO NEGATIVO significa que NÃO CHEGAMOS AINDA À SOLUÇÃO ÓTIMA do PPL Temos que REPETIR o processo Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 1 0 1 0 0 4 x2 0 1 0 12 0 6 f3 3 0 0 1 1 6 Z 3 0 0 52 0 30 Método Simplex Passo 3 Quadro I 414 60 632 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 0 0 1 13 13 2 x2 0 1 0 12 0 6 x1 1 0 0 13 13 2 Z 0 0 0 32 1 36 Quadro II Método Simplex Passo 3 Variáveis na Solução Variáveis de Decisão Valores da Solução x1 x2 f1 f2 f3 f1 0 0 1 13 13 2 x2 0 1 0 12 0 6 x1 1 0 0 13 13 2 Z 0 0 0 32 1 36 Quadro II Como todas as VARIÁVEIS NA ÚLTIMA LINHA tem COEFICIENTES POSITIVOS foi encontrado a SOLUÇÃO ÓTIMA 1 2 x 2 6 x SOLUÇÃO ÓTIMA Z 36 Exercícios Turma Uma empresa pode fabricar dois produtos 1 e 2 Na fabricação do produto 1 a empresa gasta nove horashomem e três horasmáquina a tecnologia utilizada é intensiva em mãodeobra Na fabricação do produto 2 a empresa gasta uma hora homem e uma horamáquina a tecnologia é intensiva em capital A empresa dispõe de 18 horashomem e 12 horas máquina para um período de produção Sabese que os lucros líquidos dos produtos são 4 e 1 respectivamente Transformando os dados em expressões matemáticas As restrições Não se pode utilizar o que não se tem A quantidade utilizada deve ser menor ou igual a quantidade disponível As quantidades de fabricação devem ser não negativas 18 9 2 1 x x H H 0 0 2 1 x x 12 3 2 1 x x H M O modelo do problema 18 9 2 1 x x H H 0 0 2 1 x x 12 3 2 1 x x M H 2 1 4 2 1 x x L Max x x Função Objetivo Matriz Tecnológica Variáveis de Decisão Limitações Conjunto das Possibilidades de Produção Solução Gráfica Construindo o conjunto de possibilidades Valores Possíveis quando 0 0 2 1 x x 1x 2 x 0 18 9 2 1 x x Valores Possíveis quando Solução Gráfica Construindo o conjunto de possibilidades 2 18 1x 2x 0 18 9 2 1 x x 12 3 2 1 x x Valores Possíveis quando Solução Gráfica Construindo o conjunto de possibilidades 4 12 1x 2x 0 12 3 2 1 x x Solução Gráfica Construindo o conjunto de possibilidades Conjunto de Possibilidades 12 2 1x 2 x 0 Solução Gráfica Definindo as Curvas de Níveis do Objetivo L x x L x x 1 2 2 1 4 4 Para cada valor de L temse uma reta no plano x2 vs x1 Dado um valor de L é possível traçar um lugar geométrico uma reta onde as várias combinações de produção dão o mesmo lucro essas curvas são conhecidas como isolucros Retas com inclinações negativas Solução Gráfica Desenhando as Curvas de Níveis do Objetivo 1x 2 x 0 5 L 7 L 9 L Direção de Crescimento do Lucro Solução Gráfica Reunindo os componentes e resolvendo Conjunto de Possibilidades 12 2 1x 2 x 0 13 L 1 9 Resolvendo por simplex 18 9 2 1 x x H H 0 0 2 1 x x 12 3 2 1 x x M H 2 1 4 2 1 x x L Max x x Só para lembrar LISTA DE EXERCÍCIOS 1 PESQUISA OPERACIONAL MODELAGEM 1 Um alfaiate tem disponíveis os seguintes tecidos 16 metros de algodão 11 metros de seda e 15 metros de lã Para um terno são necessários 2 metros de algodão 1 metro de seda e 1 metro de lã Para um vestido são necessários 1 metro de algodão 2 metros de seda e 3 metros de lã Se um terno é vendido por 30000 e um vestido por 50000 quantas peças de cada tipo o alfaiate deve fazer de modo a maximizar o seu lucro Encontre a solução ótima do problema e interprete sua resposta 2 Uma companhia de aluguel de caminhões possuíaos de dois tipos o tipo A com 2 metros cúbicos de espaço refrigerado e 4 metros cúbicos de espaço não refrigerado e o tipo B com 3 metros cúbicos refrigerados e 3 não refrigerados Uma fábrica precisou transportar 90 metros cúbicos de produto refrigerado e 120 metros cúbicos de produto não refrigerado Quantos caminhões de cada tipo ela deve alugar de modo a minimizar o custo se o aluguel do caminhão A era 030 por km e o do B 040 por km Elabore o modelo de programação linear 3 Uma confeitaria produz dois tipos de bolos de soverte chocolate e creme Cada lote de bolo de chocolate é vendido com um lucro de 3 um e os lotes de bolo de creme com um lucro de 1 um Contratos com várias lojas impõem que sejam produzidos no mínimo 10 lotes de bolos de chocolate por dia e que o total de lotes fabricados nunca seja menos que 20 O mercado só é capaz de consumir até 40 lotes de bolos de creme e 60 de chocolate As máquinas de preparação do sorvete disponibilizam 180 horas de operação sendo que cada lote de bolos de chocolate consomem 2 horas de trabalho e cada lote de bolos de creme 3 horas Formule apenas o modelo do problema 4 A Fashion Things Ltda é uma pequena empresa fabricante de diversos tipos de acessórios femininos entre eles bolsas de modelos diferentes A empresa foi convencida pelo seu distribuidor de que existe mercado tanto para bolsas do modelo padrão preço médio quanto para as bolsas do modelo luxo preço alto A confiança do distribuidor é tão acentuada que ele garante que ele irá comprar todas as bolsas que forem produzidas nos próximos três meses Uma análise detalhada dos requisitos de fabricação resultaram na especificação da tabela abaixo a qual apresenta o tempo despendido em horas para a realização das quatro operações que constituem o processo produtivo assim como o lucro estimado por tipo de bolsa Produto Corte e coloração Costura Acabamento Inspeção e Empacotamento Lucro por bolsa Padrão 710 12 1 110 R1000 De luxo 1 56 23 14 R900 Tempo disp 630 600 700 135 5 A indústria Alumilândia SA iniciou suas operações em janeiro de 2001 e já vem conquistando espaço no mercado de laminados brasileiro tendo contratos fechados de fornecimento para todos os 3 tipos diferentes de lâminas de alumínio que fabrica espessuras fina média ou grossa Toda a produção da companhia é realizada em duas fábricas uma localizada em São Paulo e a outra no Rio de Janeiro Segundo os contratos fechados a empresa precisa entregar 16 toneladas de lâminas finas 6 toneladas de lâminas médias e 28 toneladas de Lâminas grossas Devido à qualidade dos produtos da AlumiLândia SA há uma demanda extra para cada tipo de lâminas A fábrica de São Paulo tem um custo de produção diária de R 10000000 para cada capacidade produtiva de 8 toneladas de lâminas finas 1 tonelada de lâminas médias e 2 tonelada de Lâminas grossas por dia O custo de produção diário da fábrica do Rio de Janeiro é de R 20000000 para cada produção de 2 toneladas de lâminas finas 1 tonelada de lâminas médias e 7 tonelada de Lâminas grossas por dia Quantos dias cada uma das fábricas deverá operar para atender aos pedidos ao menor custo possível Elabore o modelo 6 Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas Ele já transporta 200 caixas de laranjas a 20 um de lucro por caixa por mês Ele necessita transportar pelo menos 100 caixas de pêssegos a 10 um de lucro por caixa e no máximo 200 caixas de tangerinas a 30 um de lucro por caixa De que forma deverá ele carregar o caminhão para obter o lucro máximo 7 Uma rede de televisão local tem o seguinte problema foi descoberto que o programa A com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30000 telespectadores enquanto o programa B com 10 minutos de música e 1 minuto de propaganda chama atenção de 10000 telespectadores No decorrer de uma semana o patrocinador insiste no uso de no mínimo 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de telespectadores Elabore o modelo 8 A empresa Have Fun SA produz uma bebida energética muito consumida pelos frequentadores de danceterias noturnas Dois dos componentes utilizados na preparação da bebida são soluções compradas de laboratórios terceirizados solução Red e solução Blue e que provêem os principais ingredientes ativos do energético extrato de guaraná e cafeína A companhia quer saber quantas doses de 10 militros de cada solução deve incluir em cada lata da bebida para satisfazer às exigências mínimas padronizadas de 48 gramas de extrato de guaraná e 12 gramas de cafeína e ao mesmo tempo minimizar o custo de produção Por acelerar o batimento cardiáco a norma padrão também prescreve que a quantidade de cafeína seja de no máximo 20 gramas por lata Uma dose da solução Red contribui com 8 gramas de extrato de guaraná e 1 grama de cafeína enquanto uma dose da solução Blue contribui com 6 gramas de extrato de guaraná e 2 gramas de cafeína Uma dose de solução Red custa R 006 e uma dose de solução Blue custa R 008 9 Um fabricante de bombons tem estocado bombons de chocolate sendo 130 kg com recheio de cerejas e 170 kg com recheio de menta Ele decide vender o estoque na forma de dois pacotes sortidos diferentes Um pacote contém uma mistura com metade do peso dos bombons de cereja e metade em menta e vende por R 2000 por kg O outro pacote contém uma mistura de um terço de bombons de cereja e dois terços de menta e vende por R1250 por kg O vendedor deveria preparar quantos quilos de cada mistura a fim de maximizar seu lucro nas vendas 10 Uma mulher tem R 1000000 para investir e seu corretor sugere investir em dois títulos A e B O título A é bastante arriscado com lucro anual de 10 e o título B é bastante seguro com um lucro anual de 7 Depois de algumas considerações ela resolve investir no máximo R 600000 no título A no mínimo R 200000 no título B Como ela deverá investir seus R 1000000 a fim de maximizar o rendimento anual 11 Uma pessoa precisa de 10 12 e 12 unidades dos produtos químicos A B e C respectivamente para o seu jardim Um produto contém 5 2 e 1 unidade de A B e C respectivamente por vidro um produto em pó contém 1 2 e 4 unidades de A B e C respectivamente por caixa Se o produto líquido custa 300 por vidro e o produto em pó custa 200 por caixa quantos vidros e quantas caixas ele deve comprar para minimizar o custo e satisfazer as necessidades 12 Certa empresa fabrica dois produtos P1 e P2 O lucro unitário do produto P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2 O tempo anual de produção disponível para isso é de 1200 horas A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2 Qual é o plano de produção para que a empresa maximize seu lucro nesses itens Construa o modelo de programação linear para esse caso 13 Um carpinteiro dispõe de 90 80 e 50 metros de compensado pinho e cedro respectivamente O produto A requer 2 1 e 1 metro de compensado pinho e cedro respectivamente O produto B requer 1 2 e 1 metros respectivamente Se A é vendido por 12000 e B por 10000 quantos de cada produto ele deve fazer para obter um rendimento bruto máximo Elabore o modelo 14 A Esportes Radicais SA produz páraquedas e asadeltas em duas linhas de montagem A primeira linha de montagem tem 100 horas semanais disponíveis para a fabricação dos produtos e a segunda linha tem um limite de 42 horas semanais Cada um dos produtos requer 10 horas de processamento na linha 1 enquanto que na linha 2 o páraquedas requer 3 horas e a asadelta requer 7 horas Sabendo que o mercado está disposto a comprar toda a produção da empresa e que o lucro pela venda de cada páraquedas é de R6000 e para cada asadelta vendida é de R4000 encontre a programação de produção que maximize o lucro da Esportes Radicais SA Elabore o modelo 15 No programa de produção para o próximo período a empresa Beta Ltda escolheu três produtos P1 P2 e P3 O quadro abaixo mostra os montantes solicitados por unidade na produção Produto Contribuição lucro por unidade Horas de trabalho Horas de uso de máquinas Demanda máxima P1 2100 6 12 800 P2 1200 4 6 600 P3 600 6 2 600 Os preços de venda foram fixados por decisão política e as demandas foram estimadas tendo em vista esses preços A firma pode obter um suprimento de 4800 horas de trabalho durante o período de processamento e pressupõese usar três máquinas que podem prover 7200 horas de trabalho Estabelecer um programa ótimo de produção para o período Faça a modelagem desse problema 16 Uma refinaria produz três tipos de gasolina verde azul e comum Cada tipo requer gasolina pura octana e aditivo que são disponíveis nas quantidades de 9600000 4800000 e 2200000 litros por semana respectivamente As especificações de cada tipo são um litro de gasolina verde 022 litro de gasolina pura 050 litro de octana e 028 litro de aditivo um litro de gasolina azul requer 052 litro de gasolina pura 034 litro de octana e 014 litro de aditivo um litro de gasolina comum requer 074 litro de gasolina pura 020 litro de octana e 006 litro de aditivo Como regra de produção baseada em demanda de mercado o planejamento da refinaria estipulou que a quantidade de gasolina comum deve ser no mínimo igual a 16 vezes a quantidade de gasolina verde e que a quantidade de gasolina azul seja no máximo igual a 600000 litros por semana A empresa sabe que cada litro de gasolina verde azul e comum dá uma margem de contribuição para o lucro de 030 025 e 020 respectivamente e seu objetivo é determinar o programa de produção que maximiza a margem total de contribuição para o lucro Construa o modelo do problema LISTA DE EXERCÍCIOS 1 PESQUISA OPERACIONAL MODELAGEM RESPOSTAS 1 RESPOSTA Max Z 300x1 500x2 Sujeito a 2x1 x2 16 restrição do algodão x1 2x2 11 restrição da seda x1 3x2 15 restrição da lã x1 0 x2 0 2 RESPOSTA Min Z 030x1 040x2 Sujeito a 2x1 3x2 90 restrição do esp refrigerado 4x1 3x2 120 restrição do esp não refrigerado x1 0 x2 0 3 RESPOSTA Max Z x1 3x2 Sujeito a x1 40 x2 60 x2 10 x1 x2 20 3x1 2x2 180 x1 0 x2 0 4 RESPOSTA Max Z 10x1 9x2 Sujeito a 710x1 x2 630 12x1 56x2 600 x1 23x2 700 110x1 14x2 135 x1 0 x2 0 5 RESPOSTA Min Z 100000x1 200000x2 Sujeito a 8x1 2 x2 16 restrição lâminas finas x1 x2 6 restrição lâminas médias 2x1 7x2 28 restrição lâminas grossas x1 0 x2 0 6 RESPOSTA Max Z 10x1 30x2 4000 Sujeito a x1 x2 600 x1 100 x2 200 x1 0 x2 0 7 RESPOSTA Max Z 30000x1 10000x2 Sujeito a 20x1 10x2 80 x1 x2 5 x1 0 x2 0 8 RESPOSTA Min Z 006x1 008x2 Sujeito a 8x1 6x2 48 x1 2x2 12 x1 2x2 20 x1 0 x2 0 9 RESPOSTA Max Z 20x1 1250x2 Sujeito a 12x1 13x2 130 12x1 23x2 170 x1 0 x2 0 10 RESPOSTA Max Z 010x1 007x2 sa 1 2 10000 x x 1 2 6000 2000 x x x1 x2 0 11 RESPOSTA Min Z 3x1 2x2 Sujeito a 5x1 x2 10 2x1 2x2 12 x1 4x2 12 x1 0 x2 0 12 RESPOSTA Max Z 1000x1 1800x2 Sujeito a 20x1 30x2 1200 x1 40 x2 30 x1 0 x2 0 13 RESPOSTA Max Z 120x1 100x2 Sujeito a 2x1 x2 90 x1 2x2 80 x1 x2 50 x1 0 x2 0 14 RESPOSTA Max Z 60x1 40x2 Sujeito a 10x1 10x2 100 3x1 7x2 42 x1 0 x2 0 15 RESPOSTA Max Z 2100x1 1200x2 600x3 Sujeito a 6x1 4x2 6x3 4800 12x1 6x2 2x3 7200 x1 800 x2 600 x3 600 x1 0 x2 0 x3 0 16 RESPOSTA Max Z 030x1 025x2 020x3 Sujeito a 022x1 052x2 074x3 9600000 050x1 034x2 020x3 4800000 028x1 014x2 006x3 2200000 x3 16x1 x2 600000 x1 0 x2 0 x1 0 LISTA DE EXERCÍCIOS 2 PESQUISA OPERACIONAL MODELAGEM 1 Uma pequena metalúrgica deseja maximizar sua receita com a venda de dois tipos de finas fitas de aço que se diferenciam em qualidade no acabamento de corte As fitas são produzidas a partir do corte de bobinas de grande largura Existem duas máquinas em operação Uma das máquinas é mais antiga e permite o corte diário de 4000m de fita A outra mais nova corta até 6000m A venda das chapas no mercado varia com a qualidade de cada uma Fitas produzidas na máquina antiga permitem um lucro de 3 um por mil metros de produção Fitas cortadas na máquina mais moderna produzem um lucro de 5 um por mil metros de produção Cada mil metros de fita cortada na máquina antiga consome 3 homens x hora de mãodeobra Na máquina moderna são gastos apenas 2 homens x hora Diariamente são disponíveis 18 homens x hora para a operação de ambas as máquinas Determinar a produção que otimiza o lucro da metalúrgica Elabore o modelo 2Um pequeno entregador pode transportar madeira ou frutas em seu carrinho de mão mas cobra 40 reais para cada fardo de madeira e 25 reais para cada saco de frutas Os fardos pesam 1kg e ocupam 2 dm3 de espaço Os sacos de frutas pesam 3 kg e ocupam 2 dm3 de espaço O carrinho tem capacidade de transportar 12 kg e 35 dm3 e o entregador pode levar quantos sacos e quantos fardos desejar Elabore o modelo para maximizar o lucro do entregador 3 Uma companhia de investimento dispõe de R 150000 para investir em ações e letras imobiliárias Sua política de aplicação consiste em aplicar no máximo 50 do disponível em ações aplicar no máximo 65 do disponível em letras imobiliárias Através de uma pesquisa de mercado a companhia verificou que deveria aplicar no máximo 40 do disponível na diferença entre a quantidade aplicada em ações e a quantidade aplicada em letras e aplicar 10 no máximo do disponível na soma da sétima parte aplicada em ações com a quarta parte aplicada em letras As ações produzem uma rentabilidade de 5 ao mês e as letras 4 ao mês Qual é o investimento ótimo que maximiza o lucro da companhia Formule o modelo do problema 4 Uma pessoa tem até R 1500000 para investir e seu corretor sugere investir em dois títulos A e B O título A é bastante arriscado com lucro anual de 15 e o título B é bastante seguro com um lucro anual de 82 Depois de algumas considerações ela resolve investir no máximo R 650000 no título A no mínimo R 250000 no título B Como ela deverá investir seus R 1500000 a fim de maximizar o rendimento anual Elabore o modelo 5 A empresa de logística Deixa Comigo SA tem duas frotas de caminhões para realizar transportes de cargas para terceiros A primeira frota é composta por caminhões médios e a segunda por caminhões gigantes ambas com condições especiais para transportar sementes e grãos prontos para o consumo como arroz e feijão A primeira frota tem a capacidade de peso de 70000 quiligramas e um limite de volume de 30000 pés cúbicos enquanto a segunda pode transportar até 90000 quilogramas e acomodar 40000 pés cúbicos de volume O próximo contrato de transporte referese a uma entrega de até 100000 quilogramas de sementes e 85000 quilogramas de grãos sendo que a Deixa Comigo SA pode aceitar levar tudo ou somente uma parte da carga deixando o restante para outra transportadora entregar O volume ocupado pelas sementes é de 04 pé cúbico por quilograma e o volume dos grãos é de 02 pé cúbico por quilograma Sabendo que o lucro para transportar as sementes é de R012 por quilograma e o lucro para transportar os grãos é de R035 por quilograma Faça a modelagem do problema com objetivo de encontrar a quantidade de quilogramas de sementes e a quantidade de quilogramas de grãos a Deixa Comigo SA deve transportar para minimizar o seu lucro Elabore o modelo 6 Um fabricante de fantasias tem em estoque 32 m de brim 22 m de seda e 30 m de cetim e pretende fabricar dois modelos de fantasias O primeiro modelo M1 consome 4m de brim 2 m de seda e 2 m de cetim O segundo modelo M2 consome 2 m de brim 4 m de seda e 6 m de cetim Se M1 é vendido a 6000 um e M2 a 10000 um quantas peças de cada tipo o fabricante deve fazer para obter a receita máxima Elabore o modelo 7Uma determinada confecção opera com dois produtos calças e camisas Como tratamse de produtos semelhantes possuem uma produtividade comparável e compartilham os mesmos recursos A programação da produção é realizada por lotes de produto O departamento de produção informa que são necessários 10 homens x hora para um lote de calças e 20 homens x hora para um lote de camisas Sabe se que não é necessária mãodeobra especializada para a produção de calças mas são necessários 10 homens x hora desse tipo de mãodeobra para produzir um lote de camisas O departamento de pessoal informa que a força máxima de trabalho disponível é de 30 homens x hora de operários especializados e de 50 homens x hora de não especializados Da planta de produção sabemos que existem apenas duas máquinas com capacidade de produzir os dois tipos de produto sendo que a máquina 1 pode produzir um lote de calças a cada 20 horas e um lote de camisas a cada 10 horas não podendo ser utilizada por mais de 80 horas no período considerado A máquina 2 pode produzir um lote de calças a cada 30 horas e um lote de camisas a cada 35 horas não podendo ser utilizada por mais de 130 horas no período considerado São necessários dois tipos de matériaprima para produzir calças e camisas Na produção de um lote de calças são utilizados 12 quilos de matériaprima A e 10 da B Na produção de um lote de camisas são utilizados 8 quilos da matériaprima A e 15 da B O almoxarifado informa que por imposições de espaço só pode fornecer 120 quilos de A e 100 quilos de B no período considerado Sabendose que o lucro pela venda é de 800 reais nos lotes de camisas e de 500 reais nos lotes de calças Formule o modelo 8 Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas A Arrendamento Destinar certa quantidade de alqueires para a plantação de canadeaçucar a uma usina local que se encarrega da atividade e paga aluguel da terra 30000 por alqueire por ano P Pecuária Usar outra parte para a criação de gado de corte A recuperação das pastagens requer adubação 100 kgAlq e irrigação 100000 litros de águaAlq por ano O lucro estimado nessa atividade é de 40000 por alqueire no ano S Plantio de Soja Usar uma terça parte para o plantio de soja Essa cultura requer 200 kg por alqueire de adubos e 200000 litros de águaAlq para irrigação por ano O lucro estimado nessa atividade é de 50000 Alqueire no ano Disponibilidade de recursos por ano 12750000 litros de água 14000 kg de adubo 100 alqueires de terra Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno Construa o modelo 9 Uma marcenaria deseja estabelecer uma programação diária de produção Atualmente a oficina faz apenas dois produtos mesa e armário ambos de um só modelo Para efeito de simplificação vamos considerar que a marcenaria tem limitações em somente dois recursos madeira e mãodeobra cujas disponibilidades diárias são mostradas na tabela a seguir Recurso Disponibilidade Madeira 12m2 Mãodeobra 8 Hh O processo de produção é tal que para fazer 1 mesa a fábrica gasta 2m2 de madeira e 2 Hh de mãode obra Para fazer um armário a fábrica gasta 3m2 de madeira e 1 Hh de mãodeobra Além disso o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de R400 e cada armário de R100 O problema do fabricante é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro Elabore o modelo 10 Uma companhia fabrica dois produtos P1 e P2 que utilizam os mesmos recursos produtivos matéria prima forja e polimento Cada unidade de P1 exige 4 horas de forjaria 2 h de polimento e utiliza 100 unidades de matériaprima Cada unidade de P2 requer 2 horas de forjaria 3 h de polimento e 200 unidades de matériaprima O preço de venda de P1 é 1900 um e de P2 2100 um Toda produção tem mercado garantido As disponibilidades são de 20 h de forja 10 h de polimento e 500 unidades de matériaprima por dia Elabore o modelo linear para o problema LISTA DE EXERCÍCIOS 2 PESQUISA OPERACIONAL MODELAGEM RESPOSTAS 1 RESPOSTA Max Z 3x1 5x2 Sujeito a x1 4 x2 6 3x1 2x2 18 x1x2 0 2 RESPOSTA Max Z 40x1 25 x2 sa x1 3x2 12 2x1 2x2 35 x1 x2 0 3 RESPOSTA Max Z 005x1 004x2 Sujeito a x1 75000 x2 97500 x1 x2 60000 17x1 14x2 15000 x1 0 x2 0 4 RESPOSTA Max Z 015x1 0082x2 sa 1 2 15000 x x 1 2 6500 2500 x x x1 x2 0 5 RESPOSTA x1 sementes transportadas kg 012 x2 grãos transportados kg 035 Teremos uma restrição para a carga A quantidade de sementes quantidade de grãos não pode ultrapassar 160000 Kg 70000 90000 x1 x2 160000 Temos uma restrição para o volume 04x1 02x2 70000 30000 40000 Temos a restrição do transporte das sementes Transporta até 100000 kg de sementes x1 100000 Temos a restrição do transporte dos grãos Transporta até 85000 kg de sementes x2 85000 Modelo Max Z 012x1 035x2 Sujeito a x1 x2 160000 04x1 02x2 70000 x1 100000 x2 85000 x1 0 x2 0 6 RESPOSTA Max Z 300x1 500x2 Sujeito a 4x1 2x2 32 2x1 4x2 22 2x1 6x2 30 x1 0 x2 0 7 RESPOSTA x1 camisas 800 reais x2 calças 500 reais CAMISAS CALÇAS SINAL DISPONÍVEL Mão de obra não esp 20 10 50 Mão de obra especial 10 30 Tempo da Máquina 1 20 10 80 Tempo da Máquina 2 35 30 130 Matéria prima A 8 12 120 Matéria prima B 15 10 100 Max Z 800x1 500x2 Sujeito a 20x1 10x2 50 10x1 30 20x1 10x2 80 35x1 30x2 130 8x1 12x2 120 15x1 10x2 100 x1 0 x2 0 8 RESPOSTA Max Z 300x1 400x2 500x3 Sujeito a x1 x2 x3 100 100x2 200x3 14000 100000x2 200000x3 12750000 x1 0 x2 0 x1 0 9 RESPOSTA Max Z 4x1 x2 Sujeito a 2x1 3x2 12 2x1 x2 8 x1 0 x2 0 10 RESPOSTA Max Z 1900x1 2100x2 Sujeito a 100x1 200x2 500 4x1 2x2 20 2x1 3x2 10 x1 0 x2 0