Baixe o app para aproveitar ainda mais
Prévia do material em texto
EAD 350 Pesquisa Operacional Aula 06 Prof. Cesar Alexandre de Souza calesou@usp.br FEA/USP Essa é uma aula de autoinstrução. Leia atentamente os slides e realize os exemplos e atividades como solicitado Boa aula!! Aviso! - Dia 30/09/14 - Prova Cai: elaboração do modelo matemático, resolução gráfica, análise de sensibilidade, preço sombra e elaboração e análise dos resultados no Solver do Excel, incluindo relatório de análise de sensibilidade Prova em sala de Aula, Individual e sem consulta Próxima aula (23/09) no lab.info e Prova (30/09) na sala de aula Aula 06 - Objetivos Apresentar a diferença entre a Programação Linear e a Programação Linear Inteira Apresentar como modelar a Programação Linear Inteira no Solver do Excel Apresentar os conceitos da Programação Binária Apresentar como modelar a Programação Binária no Solver do Excel Exercitar a Programação Binária no Solver por meio das atividades 6a e 6b Aula 06 - Agenda Resolução da atividade 5a (Gasolinas) Resolução da atividade 5b (escala de atendimento) Programação Linear Inteira Conceituação Como realizar no Excel Programação Binária Conceituação Como realizar no Excel Atividade 6a e 6B (programação binária) Aula 06 - Instruções Essa é uma aula realizada por meio de auto-instrução (ensino à distância), com tempo estimado de 100 minutos para sua realização Leia atentamente os slides dessa apresentação, bem como analise com cuidados as planilhas de gabarito das atividades Para o item “Programação Linear Inteira”, use a planilha “Ativ5b-gabarito-2014-2sem.xlxs” para acompanhar o desenvolvimento da solução Para o item “Programação Linear Inteira”, desenvolva nova planilha para a solução do exemplo apresentado Desenvolva em duplas as planilhas de solução para as atividades 6a e 6b e envie pelo Erudito até sexta 19/9, 23h59m Resolução das Atividades 5a e 5b Petróleo Máxima quantidade disponível Custo unitário A 100 6 B 200 3 Gasolina Mínima % A requerida Preço de venda unitária 1 60 8 2 30 5 Deseja-se saber a quantidade de cada gasolina que deve ser fabricada de tal maneira que o lucro seja máximo. Elaborar o Modelo matemático (pode ser na própria planilha) Elaborar o Modelo no Excel e Resolver com o Solver – Gerar o Relatório de Sensibilidade a) Uma refinaria fabrica dois tipos de gasolina (1 e 2) a partir de dois tipos de petróleo bruto (A e B). Os custos, os preços de venda e matéria-prima para fabricar as gasolinas são: Ativ 5a – Resolução PA PB G1 G2 xA1+xA2 < 100 xB1+xB2 < 200 xA1+xB1 xA2+xB2 Mín 60% Mín 30% XA1 XA2 XB1 XB2 Total G1: Total G2: Total PB: Total PA: (Preço: 8) (Preço: 5) (Custo: 6) (Custo: 3) xA1: quantidade de petróleo A p/ produzir gasolina 1 xA2: quantidade de petróleo A p/ produzir gasolina 2 xB1: quantidade de petróleo B p/ produzir gasolina 1 xB2: quantidade de petróleo B p/ produzir gasolina 2 Variáveis decisórias Ativ 5a – Resolução Função Objetiva Max L= 8(xA1+xB1) + 5(xA2+xB2) - 6(xA1+xA2) - 3(xB1+xB2) → Max L= 2 xA1 - 1xA2 + 5xB1 + 2xB2 Restrições xA1 + xA2 < 100 xB1 + xB2 < 200 xA1 / (xA1 + xB1) > 0,6 → 0,4 xA1- 0,6 xB1 > 0 xA2 / (xA2 + xB2) > 0,3 → 0,7 xA2 - 0,3 xB2 > 0 xij > 0 Ativ 5a – Resolução : Modelo Matemático Ativ 5a – Resolução – Planilha Excel (veja arquivo no Erudito) B) O supervisor do centro de suporte da empresa Alpha precisa elaborar a escala de seu pessoal. O centro de suporte fica aberto das 8 da manhã até meia-noite. O supervisor monitorou as quantidades de chamados por período e determinou que o seguinte número de analistas seriam necessários por período Podem ser contratados dois tipos de analistas: em tempo integral e estagiários tempo parcial. Os analistas em tempo integral trabalham por oito horas seguidas em três tipos de turno (8h às 16h, 12h às 20h ou 16h às 00h) e recebem $14 por hora. Os estagiários em tempo parcial podem ser contratados para os períodos de 4 horas indicados na tabela anterior e recebem $12 por hora. Durante qualquer período, deve haver pelo menos dois analistas tempo integral para cada estagiário em tempo parcial. Como atender a esses requisitos com o custo mínimo? Elaborar e escrever o modelo matemático (na própria planilha) Elaborar a o modelo em Excel e resolver com o Solver – gerar o relatório de análise de sensibilidade Ativ 5b – Resolução Período do Dia Estagiários Analistas Manhã Analistas Tarde Analistas Noite Número mínimo de Atendentes 8h - meio dia e1 a1 --- --- 4 meio dia - 16h e2 a2 --- 8 16h - 20h e3 --- a3 10 20h - meia noite e4 --- --- 6 A tabela abaixo indica as variáveis de decisão e1, e2, e3 e e4 referentes aos estagiários (tempo parcial) em cada um dos turnos de 4 horas e as variáveis a1, a2 e a3 referentes aos analistas em cada um dos turnos de 8 horas, bem como as quantidades mínimas para cada turno de 4 horas O modelo matemático pode então ser assim descrito: Minimizar o custo: ((e1+e2+e3+4e) x 10 x 4) + ((a1+a2+a3) x 14 x 8) Sujeito a: e1+a1>=4 e2+a1+a2>=8 e3+a2+a3 >=10 e4+a3>=6 a1 - 2e1 >= 0 a1+a2 - 2e2 >= 0 a2+a3 – 2e3 >=0 a3 – 2e4 >=0 Nota importante: as últimas quatro restrições NÃO poderiam ser deixadas escritas como: a1/e1 >= 2 (a1+a2) / e2 >= 2 (a2+a3) / e3 >= 2 a3 / e4 >= 2 Pois essa formulação infringe as regras da programação linear Nro. Mínimo de atendentes Mínimo de 2 analistas para cada estagiário no turno Ativ 5b – Resolução – Modelo Matemático 13 Ativ 6b – Resolução – Planilha Excel (veja arquivo no erudito) Programação Linear Inteira Programação Linear Inteira Como pode ser percebido na solução da atividade 5b, a Programação Linear fornece soluções com valores contínuos (isso é, não necessariamente inteiros) Isso pode ser um problema quando é necessário que os valores sejam inteiros, como é o caso da atividade 5b (não é possível contratar 1,3333 estagiários para o primeiro turno, por exemplo) Simplesmente “arredondar” os valores para cima ou para baixo não resolve o problema, pois a solução arredondada pode não ser viável (infringir alguma das restrições) ou pode não ser a ótima Programação Linear Inteira Por Exemplo, arredondando os valores do exercício 5b para cima ou para baixo (considerando o valor mais próximo) temos a tabela abaixo, com Z (custo) mínimo R$ 1.552: Esta não é a solução ótima possível com valores inteiros. Vamos realizar novamente o procedimento do Solver, agora impondo a solução inteira e verificar os resultados (descrito nos próximos slides, passo a passo) Programação Linear Inteira no Excel No solver, a programação linear inteira é obtida acrescentando-se mais uma restrição, aplicada às células que contêm os valores das variáveis de decisão 1) Abra a planilha “Ativ5b-gabarito-2014-2sem.xlxs” 2) Na aba “Ex5b” está a planilha com os dados do exercício 3) Abra a janela de parâmetros do Solver e clique no adicionar restrições Programação Linear Inteira no Excel 4) na caixa “referencia de célula” marque a área correspondente às variáveis de decisão (B15 a H15) 5) Na caixa dropdown para o tipo de restrição, note que além do “<=“, “=“ e “>=“ que já conhecemos, há também duas outras opções: Int – especifica números inteiros Bin – especifica números binários (0 ou 1) 6) Selecione a opção “Int” e clique no OK 7) Note que uma restrição “= número inteiro” é adicionada OBS – No Excel 2007 ou anteriores, a opção para números inteiros é “núm”, e não “int” Programação Linear Inteira no Excel 8) Antes de executar o Solver, verifique na janela de opções se a opção “ignorar restrições de números inteiros” está desmarcada (clique no botão opções na janela de parâmetros do solver) 9) Clique no “Resolver” 10) Note que no caso da programação linear inteira, não é gerado relatório de sensibilidade Ativ 5b – Resposta com Programação Linear Inteira Veja o resultado ótimo inteiro Programação Binária Programação Binária- Conceito A programação binária é um caso especial da programação inteira Quando as variáveis de decisão em um problema só são permitidas a assumir valores 0 ou 1, tem-se o caso de programação binária. O número de aplicações para este tipo de problema é muito grande: sempre que se deseja indicar como solução um conjunto de decisões do tipo sim/não interdependentes pode-se aplicar a programação binária Uma decisão do tipo sim/não pode ser modelada por uma variável binária, fazendo-se 1=sim e 0=não Programação Binária - Exemplo Uma empresa está considerando uma expansão por meio de uma nova fábrica em Los Angeles ou São Francisco (ou em ambas as cidades). Também está considerando construir armazéns, mas, somente na(s) cidade(s) em que também houver construído uma fábrica. A empresa pode investir até $ 10 milhões nesses projetos A tabela a seguir mostra o VPL (valor presente líquido), ou seja o resultado, e o investimento necessário para cada um dos projetos Quais devem ser os projetos executados, considerando-se a restrição de capital e interrelações entre as decisões (somente construir depósito em cidade em que for construída fábrica)? Programação Binária - Exemplo Para modelar esse problema com a programação binária utilizaremos 4 variáveis binárias representando a decisão (0=não faz o projeto; 1 = faz o projeto) A partir daí, elabora-se o modelo matemático: Função Objetivo: Max Z (VPL) = 9X1+5X2+6X3+4X4 Restrições: Capital: 6X1+3X2+5X3+2X4 <= 10 Depósito somente onde há fábricas: X3 <= X1 -X1+X3 <=0 X4 <= X2 -X2+X4 <=0 Variáveis X1, X2, X3 e X4 Binárias Programação Binária no Excel No solver, a programação Binária também é obtida acrescentando-se mais uma restrição, aplicada às células que contêm os valores das variáveis de decisão Ao invés de selecionar “Int” deve-se selecionar “Bin” para a restrição adicionada Também dever ser verificado se opção “ignorar restrições de números inteiros” está desmarcada na janela de opções Atividades da Aula (6a e 6b) Entregar pelo Erudito Elabore a planilha excel com o modelo matemático e a solução em solver para o problema apresentado como exemplo: Uma empresa está considerando uma expansão por meio de uma nova fábrica em Los Angeles ou São Francisco (ou em ambas as cidades). Também está considerando construir armazéns, mas, somente na(s) cidade(s) em que também houver construído uma fábrica. A empresa pode investir até $ 10 milhões nesses projetos A tabela a seguir mostra o VPL (valor presente líquido), ou seja o resultado, e o investimento necessário para cada um dos projetos Quais devem ser os projetos executados, considerando-se a restrição de capital e interrelações entre as decisões (somente construir depósito em cidade em que for construída fábrica)? Ativ 6 A– Entregar Pelo Erudito, em Grupos de 2 alunos, até o dia 19/09, 23h59m Leia atentamente a descrição da situação empresarial abaixo, elabore o modelo matemático para o problema e resolva utilizando o solver. Um agente de compra e venda de terrenos pretende vender três terrenos e recebeu ofertas para cada um deles de quatro incorporadores diferentes. Devido ao capital necessário, essas ofertas foram feitas de maneira que nenhum incorporador compraria mais do que um terreno. Cada terreno só pode ser vendido para um único incorporador (!). As ofertas em R$ mil estão apresentadas na tabela abaixo. Dica: pense inicialmente quantas decisões sim/não estão implícitas nessa tabela e como representar as inter-relações entre elas O problema guarda semelhança ao problemas de transporte da ativ 4b Ativ 6 B– Entregar Pelo Erudito, em Grupos de 2 alunos, até o dia 19/09, 23h59m
Compartilhar