Pesquisa Operacional - Apostila completa + livro 167pg

Embed Size (px)

Text of Pesquisa Operacional - Apostila completa + livro 167pg

Pesquisa Operacional

Engenharia de Produo DEPROT / UFRGS Profs. Flavio Fogliatto, Ph.D.

1. INTRODUO PESQUISA OPERACIONAL A Pesquisa Operacional (PO) trata da modelagem matemtica de fenmenos estticos ou dinmicos. Os problemas estticos so denominados por determinsticos. Nestes problemas, todos os componentes so conhecidos a priori e nenhuma aleatoriedade em sua ocorrncia admitida. Os problemas dinmicos so denominados estocsticos, e seus elementos apresentam uma probabilidade de ocorrncia em uma determinada forma. Este material aborda problemas determinsticos de Pesquisa Operacional. Os problemas de PO existem desde longa data. Somente a partir da 2a Grande Guerra, todavia, passaram a ser tratados a partir de uma abordagem organizada, sendo organizados na forma de uma disciplina ou rea do conhecimento (Ravindran et al., 1987). Os primeiros casos reportados de aplicao da PO foram, em virtude de sua origem, de carter militar. Somente aps o final da Segunda Grande Guerra, problemas civis passaram a ser estudados pela PO. Os primrdios da PO encontram-se descritos no trabalho de Trefethen (1954). Ravindran, A., Phillips, D.T. & Solberg, J.J. (1987). Operations Research, Principles and Practice, 2nd Ed.. New York: John Wiley. Trefethen, F.N. (1954). A History of Operations Research, in Operations Research for Management, J.F. McCloskey & F.N. Trefethen (Eds.). Baltimore: Johns Hopkins Press.

1

EmentaINTRODUO 1. Programao Matemtica 2. Reviso de lgebra Linear 3. Uso de pacotes computacionais na soluo de problemas PROGRAMAO LINEAR 1. Introduo Programao Linear 2. O algoritmo Simplex

Prof. Fogliatto

Pesquisa Operacional

2

Dois eventos motivaram o rpido desenvolvimento da PO. O primeiro foi o desenvolvimento de um algoritmo simples para solucionar problemas de programao linear (isto , problemas determinsticos de PO), denominado algoritmo simplex e proposto por George Dantzig em 1947. Tal algoritmo permitiu a resoluo manual de diversos problemas de PO, especialmente aqueles de baixa complexidade. O segundo foi a proliferao dos microcomputadores e o rpido aumento em sua velocidade de processamento. Problemas de PO so usualmente modelados na forma de uma funo objetivo (por exemplo, maximizar o lucro da empresa) e diversas restries (associadas, por exemplo, disponibilidade de matrias-primas, mo-de-obra, etc.). A chave do algoritmo simplex est no formato da regio limitada pelas restries, comum a todos os problemas de PO, conforme verificado por Dantzig; tal regio denominada simplex. Quaisquer dois pontos selecionados no contorno de um simplex, quando unidos por uma linha, resultam em uma linha interiamente contida dentro do simplex. A partir dessa constatao, a busca pela soluo tima em problemas de PO passou a ser limitada a pontos extremos da regio simplex, o que permitiu o desenvolvimento de um algoritmo de baixa complexidade computacional por Dantzig.

2

EmentaMODELOS DE REDES 1. O problema do transporte 2. O problema da designao 3. O problema do transbordo 4. Modelos de Redes TPICOS AVANADOS 1. Programao Inteira

Prof. Fogliatto

Pesquisa Operacional

3

Os problemas determinsticos de PO podem ser classificados em duas categorias genricas: problemas de programao (i) linear e (ii) no-linear. Somente os problemas de programao linear podem ser resolvidos pelo algoritmo simplex. Um problema qualquer de programao linear um problema de otimizao (isto , busca pela melhor dentre vrias situaes, utilizando um critrio prestabelecido de otimalidade), com as seguintes caractersticas (Bronson & Naadimuthu, 1997): o problema possui um conjunto de variveis manipulveis no procedimento de busca pelo timo; essas so as variveis de deciso do problema. uma funo objetivo compe o critrio de otimalidade, sendo escrita em termos das variveis de deciso do problema. A funo objetivo uma funo linear das variveis de deciso, devendo ser maximizada ou minimizada. os valores assumidos pelas variveis de deciso devem satisfazer um conjunto de restries, que compem a regio de solues viveis do problema. as variveis de deciso podem assumir valores pr-estabelcidos no domnio dos nmeros reais (isto , valores positivos, negativos ou ambos).

3

Referncias BibliogrficasLIVRO-TEXTO: Operations Research, Applications and Algorithms, de Wayne L. Winston, 3a. Ed., Duxburry Press. Adicionais (no mesmo nvel): 1. Pesquisa Operacional, de Harvey Wagner, 2a. Ed., Prentice-Hall do Brasil. 2. Pesquisa Operacional, de Pierre J. Ehrlich, Ed. Atlas.

Prof. Fogliatto

Pesquisa Operacional

4

A soluo de problemas atravs da Pesquisa Operacional pode ser implementada atravs de um procedimento em sete etapas, conforme apresentado na Figura 1.1. As etapas so auto-explicativas para uma descrio completa das etapas, ver Winston, 1994.

Figura 1.1. A metodologia de Pesquisa Operacional (Winston, 1994).

Bronson, R. & Naadimuthu, G. (1997). Operations Research, 2nd Ed.. New York: McGraw-Hill. Winston, W.L. (1994). Operations Research, Applications and Algorithm, 3rd Ed.. Belmont (CA): Duxburry Press.

4

INTRODUO PROGRAMAO LINEAR Programao Linear uma ferramenta para soluo de problemas de otimizao. Em 1947, George Dantzig desenvolveu o algoritmo SIMPLEX, extremamente eficiente na soluo de problemas de PL. A partir de ento, PL passou a ser utilizada em diversos segmentos da atividade produtiva: Bancos Instituies Financeiras Empresas de Transportes, etc. Vamos introduzir a PL a partir de um exemplo.Prof. Fogliatto Pesquisa Operacional 5

2. PROGRAMAO LINEAR Problemas de programao so modelados tal que o melhor uso de recursos escassos possa ser determinado, conhecidos os objetivos e necessidades do analista. Problemas de programao linear compem uma sub-classe de problemas nos quais a modelagem interiamente expressa em termos de equaes lineares. Parece intuitivo que para ser possvel a soluo de um dado problema atravs da programao linear, o problema deve ser, incialmente, formulado em termos matemticos. A construo de um modelo de programao linear seguetrs passos bsicos (Ravindran et al., 1987): Passo I. Identifique as variveis desconhecidas a serem determinadas (elas so denominadas variveis de deciso) e represente-as atravs de smbolos algbricos (por exemplo, x e y ou x1 e x2). Passo II. Liste todas as restries do problema e expresse-as como equaes (=) ou inequaes (, ) lineares em termos das variveis de deciso definidas no passo anterior. Passo III. Identifique o objetivo ou critrio de otimizao do problema, representando-o como uma funo linear das variveis de deciso. O objetivo pode ser do tipo maximizar ou minimizar.

5

EXEMPLO: O caso PolitoyA Politoy S/A fabrica soldados e trens de madeira. Cada soldado vendido por $27 e utiliza $10 de matria-prima e $14 de mo-de-obra. Duas horas de acabamento e 1 hora de carpintaria so demandadas para produo de um soldado. Cada trem vendido por $21 e utiliza $9 de matria-prima e $10 de mo-de-obra. Uma hora de acabamento e 1 h de carpintaria so demandadas para produo de um trem.

Prof. Fogliatto

Pesquisa Operacional

6

Na sequncia, os passos acima so ilustrados atravs de dois exemplos. Os exemplos foram adaptados de Ravindran et al. (1987). Exemplo 1 - O problema do mix de produo A empresa Dalai-Lama deseja planejar a produo de incensos. Os incensos requerem dois tipos de recursos: mo-de-obra e materiais. A empresa fabrica trs tipos de incenso, cada qual com diferentes necessidades de mo-de-obra e materiais, conforme tabela abaixo:Modelo B 3 4 2

Mo-de-obra (horas por unidade) Materiais (g / unidade produzida) Lucro ($ / unidade)

A 7 4 4

C 6 5 3

A disponibilidade de materiais de 200 g/dia. A mo-de-obra disponvel por dia de 150 horas. Formule um problema de programao linear para determinar quanto deve ser produzido de cada tipo de incenso, tal que o lucro total seja maximizado. Para resolver o problema acima, aplicam-se os passos para a construo de um modelo de programao linear. Passo I - Identifique as variveis de deciso. As atividades a serem determinadas dizem respeito s quantidades de produo dos trs tipos de incenso. Representando essas quantidades em termos algbricos, tem-se:

6

EXEMPLO: O caso PolitoyA Politoy no tem problemas no fornecimento de matria-primas, mas s pode contar com 100 h de acabamento e 80 h de carpintaria. A demanda semanal de trens ilimitada, mas no mximo 40 soldados so comprados a cada semana. A Politoy deseja maximizar seus ganhos semanais. Formule um modelo matemtico a ser utilizado nessa otimizao.

Prof. Fogliatto

Pesquisa Operacional

7

xA = produo diria do incenso tipo A xB = produo diria do incenso tipo B xC = produo diria do incenso tipo C Passo II - Identifique as restries. Neste problema, as restries dizem respeito disponibilidade limitada dos recursos de mo-de-obra e materiais. O tipo A requer 7 horas de mo-de-obra por unidade, e sua quantidade produzida xA. Assim, a demanda por mo-de-obra para o incenso tipo A ser 7xA horas (se considerarmos uma relao linear). Analogamente, os tipos B e C vo requerer 3xB e 6xC horas, respectivamente. Assim, a quantidade total de horas de trabalho demandadas na produo dos trs tipos de incenso ser 7xA + 3xB + 6xC. Sabese que esta quantidade no deve axceder o total de horas disponveis na empresa, isto , 150 horas. Assim, a restrio relacionada a mo-de-obra ser: 7xA + 3xB + 6xC 150 Para obter a restrio relacionada aos materiais, utiliza-se raciocnio similar. A restrio resultante ser: 4xA + 4xB + 5xC 200 Para finalizar, deseja-se restringir as variveis de deciso no domnio dos reais no-negativos (isto , x 0). Essas restries, uma para cada varivel de deciso, so denominadas restries de no-negatividade. Apesar de serem comuns em muitas aplicaes de programao lin