Slide - Seção 1 Origem 2020-2

Programa¸c˜ao Linear - ENP153 Prof. Dr. Alexandre Xavier Martins LASOS - DEENP - ICEA Origem Seção 1 Origem 2 / 25 Origem Guerra × Ciência EUREKA! 3 / 25 Origem Guerra × Ciência 4 / 25 Contexto 13 / 25 Origem Opera¸c˜oes Militares O termo Pesquisa Operacional foi usado pela primeira vez para designar o estudo sistem´atico de problemas estrat´egicos e t´aticos decorrentes de opera¸c˜oes militares ▶ Operational Research na Inglaterra ▶ Operations Research nos EUA ▶ Investiga¸c˜ao Operacional em Portugal ▶ Investigaci´on Operativa em pa´ıses hispˆanicos 6 / 25 Origem Opera¸c˜oes Militares ▶ Segunda Guerra Mundial ▶ Estudo de Radares ▶ Comitˆe de Estudos de Defesa A´erea Britˆanico -¿ Se¸c˜ao de Pesquisa Operacional ▶ Equipes multidisciplinares ▶ Problemas de Planejamento, log´ıstica e transporte ▶ 1945 ▶ Grandes ind´ustrias, governos, universidades ▶ Uso do Computador 7 / 25 Origem Origem ▶ Primeiros problemas estudados ▶ Teoria das Filas - Agner Krarup Erlang estudando o problema de redimensionamento de centrais telefˆonicas (1908) ▶ Problema da Dieta - Stigler (1945): O problema foi resolvido em 1947 por 9 pessoas em aproximadamente 13 dias ▶ Simula¸c˜ao de Integrais 8 / 25 Origem Origem O desenvolvimento metodol´ogico mais importante do per´ıodo p´os-guerra foi o M´etodo Simplex, por George Dantzig, em 1947, para a resolu¸c˜ao de problemas de Programa¸c˜ao Linear, isto ´e, de problemas de planejamento nos quais s˜ao utilizados modelos de otimiza¸c˜ao lineares 9 / 25 Origem Origem No Brasil ▶ O primeiro Simp´osio Brasileiro de Pesquisa Operacional (SBPO) foi realizado em 1968 no ITA ▶ Em seguida, foi criada a Sociedade Brasileira de Pesquisa Operacional (SOBRAPO - https://www.sobrapo.org.br/) 10 / 25 Contexto Se¸c˜ao 2 Contexto 11 / 25 Origem Guerra ✕ Ciência 5 / 25 Contexto INDÚSTRIA 1.0 Mecanização, tear e força à vapor INDÚSTRIA 2.0 Produção em escala, linha de montagem, eletricidade e combustão INDÚSTRIA 3.0 Automação, robótica computadores, internet e eletrônicos INDÚSTRIA 4.0 Sistemas cibernéticos, internet das coisas, redes e inteligência artificial 1784 1870 1969 HOJE 12 / 25 Ferramentas Se¸c˜ao 3 Ferramentas 14 / 25 Ferramentas Ferramentas ▶ Experimenta¸c˜ao com modelos ▶ Modelos de otimiza¸c˜ao ▶ Programa¸c˜ao Linear − ENP153 ▶ Otimiza¸c˜ao Combinat´oria − ENP160 ▶ Otimiza¸c˜ao de Sistemas de Grande Porte − ENP576 ▶ Otimiza¸c˜ao em redes − ENP560 ▶ Heur´ısticas e Metaheur´ısticas − ENP557 ▶ Modelos de Simula¸c˜ao ▶ Simula¸c˜ao a Eventos Discretos − ENP161 15 / 25 Otimiza¸c˜ao Se¸c˜ao 4 Otimiza¸c˜ao 16 / 25 Otimiza¸c˜ao Otimiza¸c˜ao ▶ ´Area da Pesquisa Operacional que trata da melhor utiliza¸c˜ao de recursos (escassos), de acordo com uma certa fun¸c˜ao de avalia¸c˜ao, chamada fun¸c˜ao objetivo ▶ Trabalha com modelos determin´ısticos: As informa¸c˜oes relevantes s˜ao assumidas como conhecidas (sem incertezas) ▶ Aplica¸c˜oes t´ıpicas ▶ Mistura de min´erios, Roteiriza¸c˜ao de ve´ıculos, Programa¸c˜ao de hor´arios ▶ Escala de motoristas, Sequenciamento da produ¸c˜ao, Tabela de jogos ▶ Balanceamento de fluxo, etc... 17 / 25 Otimiza¸c˜ao Otimiza¸c˜ao ▶ ´Area da Pesquisa Operacional que trata da melhor utiliza¸c˜ao de recursos (escassos), de acordo com uma certa fun¸c˜ao de avalia¸c˜ao, chamada fun¸c˜ao objetivo ▶ Trabalha com modelos determin´ısticos: As informa¸c˜oes relevantes s˜ao assumidas como conhecidas (sem incertezas) ▶ Aplica¸c˜oes t´ıpicas ▶ Mistura de min´erios, Roteiriza¸c˜ao de ve´ıculos, Programa¸c˜ao de hor´arios ▶ Escala de motoristas, Sequenciamento da produ¸c˜ao, Tabela de jogos ▶ Balanceamento de fluxo, etc... 17 / 25 Otimiza¸c˜ao Otimiza¸c˜ao ▶ ´Area da Pesquisa Operacional que trata da melhor utiliza¸c˜ao de recursos (escassos), de acordo com uma certa fun¸c˜ao de avalia¸c˜ao, chamada fun¸c˜ao objetivo ▶ Trabalha com modelos determin´ısticos: As informa¸c˜oes relevantes s˜ao assumidas como conhecidas (sem incertezas) ▶ Aplica¸c˜oes t´ıpicas ▶ Mistura de min´erios, Roteiriza¸c˜ao de ve´ıculos, Programa¸c˜ao de hor´arios ▶ Escala de motoristas, Sequenciamento da produ¸c˜ao, Tabela de jogos ▶ Balanceamento de fluxo, etc... 17 / 25 Programa¸c˜ao Linear Se¸c˜ao 5 Programa¸c˜ao Linear 18 / 25 Programação Linear Formulação Algébrica Otimizar f(x) = \sum_{j=1}^{n} c_j x_j Sujeito a: \sum_{j=1}^{n} a_{ij} x_j \begin{cases} \ge \ \le \ = \end{cases} b_i \ \forall \ i = 1,\ldots,m x_j \ge 0 \ \forall \ j = 1,\ldots,n Programa¸c˜ao Linear Programa¸c˜ao Linear 1. As restri¸c˜oes representam limita¸c˜oes de recursos dispon´ıveis (m˜ao-de-obra, capital, recursos minerais ou fatores de produ¸c˜ao) ou ent˜ao, exigˆencias e condi¸c˜oes que devem ser cumpridas 2. xj ´e uma vari´avel de decis˜ao, que quantifica o n´ıvel de opera¸c˜ao da atividade j 3. bi representa a quantidade do i-´esimo recurso dispon´ıvel ou a exigˆencia que deve ser cumprida 4. cj representa o custo associado `a j-´esima atividade 5. aij ´e a quantidade do recurso i (exigido ou dispon´ıvel) em uma unidade da atividade j 6. otimizar = maximizar ou minimizar 20 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Terminologia ▶ Solu¸c˜ao ▶ Qualquer especifica¸c˜ao de valores para as vari´aveis de decis˜ao ▶ Solu¸c˜ao vi´avel ▶ Solu¸c˜ao que satisfaz a todas as restri¸c˜oes ▶ Solu¸c˜ao ´otima ▶ Solu¸c˜ao vi´avel que tem o valor mais favor´avel da fun¸c˜ao objetivo 21 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Proporcionalidade Proporcionalidade ▶ Aplic´avel `a fun¸c˜ao objetivo e `as restri¸c˜oes funcionais ▶ A contribui¸c˜ao de cada atividade j para o valor da equa¸c˜ao ´e proporcional ao n´ıvel da atividade j 22 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Proporcionalidade Proporcionalidade ▶ Aplic´avel `a fun¸c˜ao objetivo e `as restri¸c˜oes funcionais ▶ A contribui¸c˜ao de cada atividade j para o valor da equa¸c˜ao ´e proporcional ao n´ıvel da atividade j 22 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Aditividade Aditividade ▶ As fun¸c˜oes do modelo de programa¸c˜ao linear s˜ao a soma das contribui¸c˜oes individuais das respectivas atividades. ▶ N˜ao ´e poss´ıvel o aparecimento de termos do tipo xi × xj 23 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Aditividade Aditividade ▶ As fun¸c˜oes do modelo de programa¸c˜ao linear s˜ao a soma das contribui¸c˜oes individuais das respectivas atividades. ▶ N˜ao ´e poss´ıvel o aparecimento de termos do tipo xi × xj 23 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Divisibilidade Divisibilidade ▶ As vari´aveis de decis˜ao num modelo de programa¸c˜ao linear podem ter quaisquer valores incluindo valores n˜ao inteiros, desde que satisfa¸cam as restri¸c˜oes funcionais e as condi¸c˜oes de n˜ao negatividade. ▶ Se as vari´aveis assumem apenas valores inteiros → Programa¸c˜ao Linear Inteira 24 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Divisibilidade Divisibilidade ▶ As vari´aveis de decis˜ao num modelo de programa¸c˜ao linear podem ter quaisquer valores incluindo valores n˜ao inteiros, desde que satisfa¸cam as restri¸c˜oes funcionais e as condi¸c˜oes de n˜ao negatividade. ▶ Se as vari´aveis assumem apenas valores inteiros → Programa¸c˜ao Linear Inteira 24 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Certeza Certeza ▶ Os valores atribu´ıdos a cada parˆametro do modelo de programa¸c˜ao linear ´e suposto ser um valor constante e previamente conhecido 25 / 25 Programa¸c˜ao Linear Programa¸c˜ao Linear Hip´oteses da PL ▶ Certeza Certeza ▶ Os valores atribu´ıdos a cada parˆametro do modelo de programa¸c˜ao linear ´e suposto ser um valor constante e previamente conhecido 25 / 25