Aula 01 - Introdução à Pesquisa Operacional

Prévia do material em texto

<p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Pesquisa Operacional</p><p>Professor: Fernando Stela</p><p>E-mail: fernando.stela@docente.unip.br</p><p>1</p><p>mailto:fernando.stela@docente.unip.br</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Pesquisa Operacional</p><p>• O que é Pesquisa Operacional?</p><p>• Quando Surgiu a Pesquisa Operacional?</p><p>• O Processo de Solução de Problemas</p><p>• Modelagem Matemática para Programação Linear</p><p>• Solução Gráfica</p><p>2</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Pesquisa Operacional</p><p>• “É o uso do método científico com o objetivo de prover departamentos executivos de</p><p>elementos quantitativos para a tomada de decisões com relação a operações sob seu</p><p>controle";</p><p>• “Propõe uma abordagem científica na solução de problemas: observação, formulação do</p><p>problema, e construção de modelo científico (matemático ou de simulação”);</p><p>• “É a modelagem e tomada de decisão em sistemas reais, determinísticos ou</p><p>probabilísticos, relativos à necessidade de alocação de recursos escassos”</p><p>3</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>O que é Pesquisa Operacional?</p><p>• A pesquisa operacional (PO) é uma ciência aplicada que utiliza</p><p>técnicas científicas conhecidas (ou as desenvolve quando</p><p>necessário), tendo como ponto de referência a aplicação do</p><p>método científico procurando obter a melhor solução - ou</p><p>solução ótima - para um problema. (MOREIRA, 2010)</p><p>4</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Objetivos</p><p>• Solucionar problemas, que apresentem variáveis que possam ser</p><p>medidas e cujos relacionamentos possam ser expressos por meio</p><p>de equações e/ou inequações lineares, também chamadas de</p><p>função objetivo. De acordo com o objetivo da otimização, o modelo</p><p>linear, respeitando as restrições impostas pela situação, poderá</p><p>minimizar ou maximizar o resultado dessa função. (MOREIRA,</p><p>2010)</p><p>5</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>O que é Pesquisa Operacional?</p><p>• É aplicada a problemas associados à condução e a coordenação de</p><p>operações ou atividades numa organização;</p><p>• Adota um enfoque sistêmico para os problemas;</p><p>• Busca a solução “ótima” para o problema;</p><p>• Usa uma metodologia de trabalho em equipe (engenharia, computação,</p><p>economia, estatística, administração, matemática, ciências</p><p>comportamentais).</p><p>6</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Origens da Pesquisa Operacional</p><p>• Século III A.C. quando Hieron, Imperador da Siracusa, solicitou de Arquimedes a</p><p>idealização de meios para acabar com o cerco naval dos romanos. (Lóss, 1981)</p><p>• Século XVII, Pascal e Fermat, inventores da noção de esperança matemática, e</p><p>mais recentemente, Taylor, Borel e Erlang modelaram alguns problemas e</p><p>forneceram soluções para os respectivos modelos. (Lóss, 1981)</p><p>• Em seguida a 1a . Revolução Industrial, em aplicações industriais, as sementes</p><p>da PO foram lançadas nas tentativas de usar o método cientifico na gerência de</p><p>sistemas e organizações de grande porte. (Lóss, 1981)</p><p>7</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Origens da Pesquisa Operacional</p><p>• Pesquisa Operacional (PO) surgiu no século passado, concebida por</p><p>cientistas para analisar situações militares na Segunda Guerra Mundial,</p><p>onde os recursos eram restritos e as necessidades operacionais careciam</p><p>de efetividade, que a atividade de PO teve seu início. Moreira (2010)</p><p>• No pós-guerra, o sucesso da PO fez com que essa prática se estendesse</p><p>para as organizações civis, visto que a indústria estava em expansão e</p><p>sua complexidade necessitava de técnicas mais eficientes para análise de</p><p>seus problemas. Moreira (2010)</p><p>8</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>O Processo de Solução de Problemas</p><p>1) Definição da situação do problema: quais são os objetivos desejados, quais são as restrições,</p><p>os recursos, etc</p><p>2) Formulação de um modelo quantitativo: formalizar as informações em termos matemáticos</p><p>3) Resolução do modelo: manipular os valores das variáveis para obter a melhor solução possível</p><p>4) Consideração de fatores imponderáveis: analisar a solução encontrada e verificar se precisa</p><p>adicionar variáveis ao modelo</p><p>5) Implementação da solução: é executada a solução na prática</p><p>9</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Modelagem Matemática para Programação Linear</p><p>• Os modelos matemáticos mais populares são denominados Modelos de Programação Linear</p><p>• Estes modelos servem para representar problemas em que a relação entre as variáveis destes</p><p>problemas possam ser expressas na forma de equações ou inequações lineares</p><p>• Existe uma combinação de variáveis que deve ser maximizada ou minimizada</p><p>• Exemplo: o custo de uma operação industrial é dado por uma combinação de variáveis chamada</p><p>de função objetivo</p><p>• São chamadas de variáveis de decisão: Por exemplo: 7𝑥 + 2𝑦</p><p>10</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Exemplo 1:</p><p>• A esteira de uma seção de uma fábrica possui 70 metros.</p><p>Sabendo que cada peça ocupa um espaço de 3,5 metros,</p><p>maximize o número de peças que serão colocadas na esteira.</p><p>11</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>• Passo 1: Identificar variáveis: defina-se, então: 𝒄𝒑 comprimento</p><p>da peça e 𝒙 o número de peças a serem colocadas na esteira</p><p>• Passo 2: Identificar a Função Objetivo: Pode-se dizer que a</p><p>função objetivo do problema é maximizar o número de peças na</p><p>esteira: 𝒇. 𝒐. : 𝒎𝒂𝒙 𝒙</p><p>• Passo 3: Identificar as Restrições: 𝒕𝒐𝒕𝒂𝒍_𝒄𝒑 ≤ 𝟕𝟎</p><p>12</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>• Entretanto, 𝒕𝒐𝒕𝒂𝒍_𝒄𝒑 é um valor que precisa estar relacionado com 𝑥.</p><p>Se tivermos 1 peça, o comprimento total será 1 * 3,5;</p><p>Se tivermos 2 peças, o comprimento total será 2 * 3,5;</p><p>Se tivermos 3 peças, o comprimento total será 3 * 3,5;</p><p>Assim:</p><p>Se tivermos x peças, o comprimento total será x * 3,5;</p><p>Pode-se escrever, então:</p><p>Comprimento total ocupado pelas peças = 3,5 * x</p><p>13</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>𝒇. 𝒐. : 𝒎𝒂𝒙 𝒙</p><p>𝒔. 𝒂. ∶ 𝟑, 𝟓 ∗ 𝒙 ≤ 𝟕𝟎</p><p>Função</p><p>Objetivo</p><p>Sujeito à</p><p>Variáveis de Decisão são</p><p>valores que podem ser alterados</p><p>e se deseja determinar</p><p>Parâmetros são valores</p><p>que são fornecidos e</p><p>não se pode mexer</p><p>14</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>𝒙 = 20</p><p>𝟑, 𝟓 ∗ 𝟐𝟎 ≤ 𝟕𝟎</p><p>𝟕𝟎 ≤ 𝟕𝟎</p><p>20 é o valor que irá retornar o maior valor que não passe de 70!</p><p>15</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Exemplo 2:</p><p>• Uma fábrica produz dois produtos, A e B. Cada um deve ser processado por duas máquinas, M1 e</p><p>M2. Devido à programação de outros produtos que também usam estas máquinas, estão</p><p>disponíveis para os produtos A e B apenas 24 horas da máquina M1 e 16 horas da máquina M2.</p><p>• Para produzir uma unidade do produto A, são necessárias 4 horas em cada uma das máquinas e</p><p>para produzir uma unidade do produto B, são necessárias 6 horas em M1 e 2 horas em M2. Cada</p><p>unidade de A vendida gera um lucro de R$ 80,00 e cada unidade de B vendida gera um lucro de</p><p>R$ 60,00.</p><p>• Existe uma previsão de demanda máxima de 3 unidades para B, mas nenhuma restrição de</p><p>demanda para A. Deseja-se saber: quanto produzir de cada produto para maximizar o lucro?</p><p>16</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>• O primeiro passo que auxilia muito na solução, é fazer um</p><p>pequeno quadro de informações. Por exemplo:</p><p>Produto Horas de M1 Horas de M2 Demanda Max Lucro Unitário</p><p>A 4 4 - 80</p><p>B 6 2 3 60</p><p>Horas Disp. 24 16 - -</p><p>17</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>Considerando o número de unidades de 𝑨 vendidas como 𝒙𝒂 e o número de unidades de B</p><p>vendidas como 𝒙𝒃, é possível dizer que:</p><p>𝑙𝑢𝑐𝑟𝑜_𝐴 = 80 ∗ 𝑥𝑎</p><p>𝑙𝑢𝑐𝑟𝑜_𝑏 = 60 ∗ 𝑥𝑏</p><p>𝑙𝑢𝑐𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 = 80 ∗ 𝑥𝑎 + 60 ∗ 𝑥𝑏</p><p>• A função objetivo pode ser formalizada como:</p><p>𝒇. 𝒐. : 𝒎𝒂𝒙 𝟖𝟎 ∗ 𝒙𝒂 + 𝟔𝟎 ∗ 𝒙𝒃</p><p>18</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>Tempo de 𝒎𝟏 gasto com produção de 𝑨: 𝟒 ∗ 𝒙𝒂</p><p>Tempo de 𝒎𝟏 gasto com produção de 𝑩: 𝟔 ∗ 𝒙𝒃</p><p>Tempo total de 𝒎𝟏: 𝟒 ∗ 𝒙𝒂 + 𝟔 ∗ 𝒙𝒃 e 𝐦𝟏 ≤ 𝟐𝟒</p><p>Resultando em:</p><p>𝟒 ∗ 𝒙𝒂 + 𝟔 ∗ 𝒙𝒃 ≤ 24</p><p>Usando o mesmo raciocínio em 𝒎2 temos:</p><p>𝟒 ∗ 𝒙𝒂 + 2 ∗ 𝒙𝒃 ≤ 16</p><p>19</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução:</p><p>Modelo final: 𝒇. 𝒐. : 𝒎𝒂𝒙 𝟖𝟎 ∗ 𝒙𝒂 + 𝟔𝟎 ∗ 𝒙𝒃</p><p>Restrições:</p><p>𝟒 ∗ 𝒙𝒂 + 𝟔 ∗ 𝒙𝒃 ≤ 24 Restrição do números de horas de 𝑚1</p><p>𝟒 ∗ 𝒙𝒂 + 2 ∗ 𝒙𝒃 ≤ 16 Restrição do números de horas de 𝑚2</p><p>𝒙𝒃 ≤ 3 Restrição de demanda para 𝐵</p><p>𝒙𝑎 ≥ 0; 𝑥𝑏 ≥ 0 Restrição de não-negatividade</p><p>Onde as variáveis de decisão são 𝒙𝑎 e 𝑥𝑏</p><p>Agora que o modelo final está pronto</p><p>vamos fazer a solução gráfica</p><p>20</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• O primeiro passo é desenhar</p><p>um plano cartesiano, onde</p><p>serão traçadas, uma a uma,</p><p>as áreas representadas pelas</p><p>inequações:</p><p>21</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• Deve ser traçada, então, a</p><p>reta equivalente à primeira</p><p>restrição:</p><p>𝟒 ∗ 𝒙𝒂 + 𝟔 ∗ 𝒙𝒃 ≤ 24</p><p>22</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• Agora, deve-se traçar a reta</p><p>que representa a equação</p><p>relacionada à segunda</p><p>restrição:</p><p>𝟒 ∗ 𝒙𝒂 + 2 ∗ 𝒙𝒃 ≤ 16</p><p>23</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• Assim, a área permissível</p><p>pelas duas restrições</p><p>mostrando como acrescentar</p><p>a restrição reduziu o espaço</p><p>de soluções:</p><p>24</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• A terceira restrição é mais</p><p>simples:</p><p>𝒙𝒃 ≤ 3</p><p>25</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• E agora, marcando apenas a</p><p>área permissível por todas as</p><p>três restrições.</p><p>26</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Solução</p><p>• Com isso, temos a região de soluções possíveis delimitada. Todos os pontos</p><p>internos à área vermelha representam soluções possíveis (boas ou ruins) e</p><p>todos os pontos externos representam soluções inviáveis, ou seja, que ferem</p><p>uma ou mais restrições.</p><p>"A solução ótima de um problema está em um dos pontos extremos da</p><p>região permissível“</p><p>• Em outras palavras, a solução ótima está em um dos "cantos" do espaço de</p><p>soluções possíveis.</p><p>27</p><p>Ciência da Computação</p><p>Pesquisa OperacionalSolução Gráfica</p><p>Exemplo 2:</p><p>Com isso, temos a região de soluções possíveis delimitada. Todos os pontos</p><p>internos à área vermelha representam soluções possíveis (boas ou ruins) e</p><p>todos os pontos externos representam soluções inviáveis, ou seja, que ferem</p><p>uma ou mais restrições.</p><p>"A solução ótima de um problema está em um dos pontos extremos da</p><p>região permissível“</p><p>Em outras palavras, a solução ótima está em um dos "cantos" do espaço de</p><p>soluções possíveis.</p><p>28</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>1</p><p>2</p><p>3</p><p>4</p><p>5</p><p>Solução</p><p>29</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Ponto Extremo XA XB Função Objetivo:</p><p>80*XA + 60*XB</p><p>1 0 0 0</p><p>2 4 0 320</p><p>3 3 2 360</p><p>4 1,5 3 300</p><p>5 0 3 180</p><p>Solução</p><p>30</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Ponto Extremo XA XB Função Objetivo:</p><p>80*XA + 60*XB</p><p>1 0 0 0</p><p>2 4 0 320</p><p>3 3 2 360</p><p>4 1,5 3 300</p><p>5 0 3 180</p><p>Solução</p><p>31</p><p>Ciência da Computação</p><p>Pesquisa Operacional</p><p>Referências</p><p>• MOREIRA, D. A.; Pesquisa Operacional: curso introdutório.</p><p>2.ed rev. e atu. São Paulo Cengage Learning, 2010.</p><p>• Introdução à Pesquisa Operacional. Daniel Caetano. Capítulo 1</p><p>• BRONSON, R.; Pesquisa Operacional. 1 ed. São Paulo:</p><p>McGraw-Hill do Brasil, 1985.</p><p>32</p>