PESQUISA OPERACIONAL - docs.ufpr.br volmir/PO_I_01_  · PESQUISA OPERACIONAL Ementa Revisão de Álgebra

Embed Size (px)

Text of PESQUISA OPERACIONAL - docs.ufpr.br volmir/PO_I_01_  · PESQUISA OPERACIONAL Ementa Revisão de...

  • PESQUISA OPERACIONAL Introduo

    Professor Volmir Wilhelm Professora Mariana Kleina

  • PESQUISA OPERACIONAL Ementa

    Reviso de lgebra Linear. Modelos de Programao Linear. O Mtodo Simplex. O Problema do Transporte. O Problema da Designao. Dualidade. Anlise de Ps-Otimizao.

    Programa

    Reviso de lgebra linear: Matrizes. Soluo de sistemas de equaes lineares. Espaos Vetoriais. Sistemas de inequaes lineares. Convexidade. Modelos de programao linear: Modelos de Programao Linear. Soluo grfica. Teoremas fundamentais. Limitaes da Programao Linear. Mtodo Simplex: O Mtodo Simplex. Forma padro. Transformao de um problema geral para a forma padro. Casos especiais. Mtodo das duas fases. Problema do transporte: Exemplos de modelos de transporte. Obteno da soluo inicial. Obteno da soluo tima. Casos especiais. Problema da designao: Exemplos de problemas de designao. Algoritmo da designao. Dualidade: Propriedades. Exemplos de formulao do dual. Teorema bsico da dualidade. Teorema da folga complementar. Mtodo Dual-Simplex. Interpretao econmica do problema dual. Anlise de ps-otimizao: Mudanas dos coeficientes de custos. Mudanas nos recursos. Mudanas nas restries. Programao paramtrica.

    Referncias

    Puccini, A.L., Pizzolato, N.D., Programao Linear, LTC, 1990

    Wagner, H.M., Pesquisa Operacional, Prentice Hall do Brasil, 1986

    Taha, Hamdy A., Pesquisa Operacional, 8a. Edio, So Paulo, Pearson, 2008

    Lachtermarcher, Gerson. Pesquisa Operacional na Tomada de Decises, 4a. Edio, So Paulo, Pearson, 2009

    Griffin, Christopher, Linear Programming, 2009-2011

    Sottinen, Tommi, Operations Research with GNU Linear Programming Kit, 2009

    Software Livre

    LpSolve - lp_solve_5.5.2.0_IDE_Setup.exe

    2 2 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

    http://www.personal.psu.edu/cxg286/Math484_V1.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdfhttp://sourceforge.net/projects/lpsolve/
  • A Pesquisa Operacional (PO) consiste no estudo de

    mtodos matemticos, usualmente implementados

    por programas de computador, que podem ser

    utilizados para resolver problemas gerenciais

    relacionados tomada de deciso e controle de

    sistemas.

    PESQUISA OPERACIONAL

    3 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • 1) Problema de Designao: Decidir qual tarefa atribuir a cada mquina de modo a minimizar o

    tempo total de execuo.

    2) Projeto de Rede: Decidir como ligar n cidades atravs de uma coleo de possveis ligaes de

    forma a minimzar o custo total de interligao.

    3) Agendamento de Pessoal: Determinar a programao da semana para o pessoal do hospital,

    de modo a satisfazer as necessidades dirias, minimizando o nmero de pessoas envolvidas.

    4) Teoria da deciso: Decidir qual laptop comprar considerando o preo, o peso e as

    performances.

    Problemas complexos de tomada de decises que so abordados atravs de uma abordagem

    de modelagem matemtica (modelos matemticos, algoritmos e implementaes de

    computador) (http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php)

    PESQUISA OPERACIONAL

    4 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

    http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php
  • 1. Modelagem, Simulao e Otimizao

    2. Programao Matemtica

    3. Processos Decisrios

    4. Processos Estocsticos

    5. Teoria dos Jogos

    6. Anlise de Demanda

    7. Inteligncia Computacional

    http://www.abepro.org.br

    PESQUISA OPERACIONAL

    5 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

    http://www.abepro.org.br/
  • Principais caractersticas de problemas de tomada de deciso

    nmero de tomadores de deciso (quem decide?)

    nmero de objetivos (com base em que critrios?)

    nvel de incerteza nos parmetros (com base em qual informao?)

    Vrios tomadores de deciso Teoria dos Jogos Vrios objetivos Programao Multi-objetivo Nvel de incerteza > 0 Programao Estocstica

    http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php

    PESQUISA OPERACIONAL

    6 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

    http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.phphttp://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php
  • Principais etapas

    definir o problema

    construir um modelo

    conceber ou selecionar um mtodo adequado

    desenvolver ou utilizar uma implementao eficiente

    analisar os resultados

    Um modelo uma representao simplificada da realidade.

    Para definir um modelo precisamos identificar os elementos fundamentais do problema e as principais relaes entre eles.

    PESQUISA OPERACIONAL

    7 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Programao Matemtica

    Um problema de programao matemtica tem por objetivo encontrar os valores para as variveis de deciso que otimizam (maximizam ou minimizam) uma funo objetivo respeitando um conjunto de restries.

    Tipos de modelos de programao matemtica:

    Programao linear

    Programao inteira

    Programao no linear

    Programao dinmica

    Programao binria

    Outros

    PESQUISA OPERACIONAL

    8 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Programao Linear

    uma tcnica de otimizao bastante utilizada na resoluo de problemas que tenham seus modelos representado por expresses lineares. Pela sua simplicidade e a possibilidade de aplicao em uma considervel diversidade de problemas, tornou-se um recurso bastante difundido.

    Tem sido usada com sucesso na soluo de problemas relativos alocao de pessoal, mistura de materiais, distribuio, transporte, carteira de investimento.

    PESQUISA OPERACIONAL

    9 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Programao Linear

    Administrao da produo:

    o Alocao de recursos limitados;

    Anlise de investimentos;

    Logstica:

    o Custo de transporte;

    o Localizao de rede de distribuio;

    Alocao de recursos em marketing

    PESQUISA OPERACIONAL

    10 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Origens

    Pesquisa Operacional: II Guerra Mundial - formulao e soluo de modelos de programao linear em problemas de planejamento de operaes militares

    Dantzig (1947): descoberta do mtodo Simplex para a soluo de problemas de programao linear,

    PROGRAMAO LINEAR

    11 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Origens

    Maximizar ou minimizar uma funo linear

    Sujeito a um conjunto de restries lineares (igualdades ou desigualdades)

    Variveis reais que podem assumir qualquer valor

    PROGRAMAO LINEAR

    12

    0,...0

    ...

    ......

    ...

    ...minmax

    1

    11

    11111

    11

    n

    mnmnm

    nn

    nn

    xx

    bxaxa

    bxaxa

    xcxcZ

    Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Principais etapas

    Definio do problema

    Construo do modelo - modelagem

    Soluo do modelo

    Validao do modelo

    Implementao da soluo

    Avaliao final

    PROGRAMAO LINEAR

    13 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Modelagem

    Variveis de deciso

    Funo objetivo

    Restries

    PROGRAMAO LINEAR

    14 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Exemplo 1

    Num teatro o espectador pode adquirir ingressos que do direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$ 15,00. Sabendo que Ana Carolina gastou R$ 121,00 com 9 ingressos, quantos assentos de cada tipo comprou?

    PS.: sem funo objetivo

    PROGRAMAO LINEAR

    15 Prof. Volmir Eugnio Wilhelm Professora Mariana Kleina

  • Exemplo 1 - variante

    Num teatro o espectador pode adquirir ingressos que do direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$