Pesquisa Operacional - facom.ufms. ricardo/Courses/OR-2009/Lectures/Lec01_2009... · Pesquisa Operacional

Embed Size (px)

Text of Pesquisa Operacional - facom.ufms. ricardo/Courses/OR-2009/Lectures/Lec01_2009... · Pesquisa...

Pesquisa OperacionalTpicos em Programao Linear e Inteira

Prof. Dr.Ricardo Ribeiro dos Santosricr.santos@gmail.com

Universidade Catlica Dom Bosco - UCDBEngenharia de Computao

Roteiro

Introduo e Histrico

Modelagem Matemtica

Conceitos Bsicos de PL

Soluo Grfica

Programao Linear e o Mtodo Simplex

Pesquisa Operacional e Mercado

Introduo e Histrico

Introduo

Pesquisa Operacional (PO) um conjunto de tcnicas matemticas utilizadas para resolver problemas relacionados com a tomada de decises.

Principais tcnicas: Programao Linear, Programao No Linear,

Programao Dinmica, Programao Geomtrica, Otimizao Combinatria, Teoria de Filas, Teoria de Estoques, Teoria de Deciso, Simulao de Sistemas.

Introduo

Contribuio da Pesquisa Operacional

Resulta na formulao de modelos matemticos para problemas de diversas reas. As tcnicas empregadas envolvem a classificao dos problemas em grupos e a identificao de caractersticas das solues timas, de modo a desenvolver mtodos sistemticos (ou algoritmos) para obteno destas solues.

Aplicaes

Roteirizao de Veculos.

Problemas de Corte.

Problema de Empacotamento.

Problemas de Manufatura.

Escalonamento de Tarefas-Mquinas.

Planejamento de Produo.

Projeto de Circuitos Integrados.

Problema de Engenharias em geral .

Histrico

HistricoO termo Pesquisa Operacional (Operational Research na Inglaterra, Operations Research nos EUA, Investigao Operacional em Portugal e Investigacin Operativa em pases hispnicos) foi usado pela primeira vez em 1938 para designar o estudo sistemtico de problemas estratgicos e tticos decorrentes de operaes militares.

Um grupo de especialistas (Patrick Blackett, Cecil Gordon, C. H. Waddington, Owen Wansbrough-Jones and Frank Yates) foi designado para avaliar e reposicionar os radares do sistema de defesa area da Gr-Bretanha antes e durante a Segunda Guerra Mundial.

Histrico

O desenvolvimento metodolgico mais importante do perodo ps-guerra foi o Mtodo Simplex, por George Dantzig, em 1947, para a resoluo de problemas de Programao Linear.

Histrico

Em 1952, Dantzig comeou a sua pesquisa matemtica, onde comeou a implementar a programao linear.

HistricoAs condies de KKT (William Karush-Harold Kuhn-Albert Tucker), publicadas na dcada de 1950, so condies necessrias e suficientes para a soluo tima de problemas de programao no-lineares

Histrico No Brasil, a PO iniciou na dcada de 1960.

O primeiro Simpsio Brasileiro de Pesquisa Operacional (SBPO) foi realizado em 1968 no ITA e incluia alguns pesquisadores do pas.

Em seguida, foi criada a Sociedade Brasileira de Pesquisa

Operacional (SOBRAPO).

Etapas da PO O processo de aplicao da PO na soluo de um problema:

Estudar o problemater contacto com o problema para compreender e

detalhar as suas caractersticas principais; uma etapa de coleta de dados

Identificar sistema descrever atividades, recursos, restries e objetivos

Construir modelodesenvolver um modelo que represente de modo

simplificado o sistema em estudo

Etapas da POExecutar mtodo

utilizar mtodo matemtico para obter a soluo matemtica para o problema.

Analisar soluo estudar a estabilidade da soluo frente a pequenas

variaes no meio ambiente; transformar a soluo matemtica em uma soluo do problema real.

Tomar deciso implementar a soluo no sistema real.

Realimentarcorrigir ou refazer trabalho anterior com base em erros

detectados, presente em todas as etapas anteriores.

Conceitos Preliminares e

Exemplos de Modelos de PO

Um modelo matemtico para o problema de deciso.

otimizar (funo-objetivo)sujeito a (restries)

Variveis de deciso: x =(x1, x2, ..., xn), possvel expressar tanto a funo-objetivo como as restries em termos de x.

Sejam f : Rn R e gi : Rn R, i = 1, 2,..., p, funes de n variveis, a primeira associada f.o. e as demais s restries do modelo.

Denotando por ~" qualquer das relaes "=",

Uma agroindstria, deve produzir um tipo de rao para determinado animal. A rao produzida pela mistura de farinhas de trs ingredientes bsicos: osso, soja e resto de peixe. Cada ingrediente possui diferentes quantidades de dois nutrientes: protena e clcio. O nutricionista especifica as necessidades mnimas desses nutrientes em 1kg de rao: 30% de protena e 50% de clcio (pelo menos).

Objetivo determinar em que quantidades os ingredientes devem

ser misturados de modo a produzir uma rao que satisfaa s restries nutricionais com o mnimo custo.

Probleminha

Probleminha

0.460.810.56Custos ($/kg)

0.50.40.40.6Clcio

0.30.40.50.2Protena

RaoPeixeSojaOsso

IngredientesNutrientes

- varivel de deciso xj como a quantidade (em kg) do ingrediente j que deve ser usada em uma unidade (1kg) de rao, j=1 (osso), 2 (soja), 3 (peixe).

- o custo da mistura ser dado por:f(x1, x2, x3)=0.56x1+0.81x2+0.46x3

- as restries so dadas por:0.2x1+0.5x2+0.4x3>=0.30.6x1+0.4x2+0.4x3>=0.5x1+x2+x3=1x1>=0, x2>=0, x3>=0

Construindo o Modelo

Construindo o Modelo

O modelo matemtico resultante :

Minimizar f(x1, x2, x3)=0.56x1+0.81x2+0.46x3 Sujeito a 0.2x1+0.5x2+0.4x3>=0.3

0.6x1+0.4x2+0.4x3>=0.5x1+x2+x3=1x1>=0, x2>=0, x3>=0

Problema do Transporte Centros de produo de produtos so denominados origens

Mercados consumidores so denominados destinos

Supor a existncia de m origens e n destinos e o custo de transporte de uma unidade do produto da origem i para o destino j cij

Oferta do produto na origem i ai e a demanda do produto no destino j bj

1 1

2

nm

2

a1

a2

am

b1

b2

bn

c11

cmn

Problema do Transporte xij quantidade transportada da origem i para o destino j.

cijxij o custo para realizar o transporte de i para j com a quantidade x de produtos com o custo c.

O custo total de transporte a soma dos custos de transporte de todas as quantidades transportadas de todas as origens i a todos os destinos j. Esse custo deve ser minimizado.

Observe que:

O que transportado de cada origem i a todos os destinos j no pode ultrapassar a quantidade ofertada em i.

As quantidades transportadas das diversas origens ao destino j satisfaam a demanda requerida neste destino.

Como seria o modelo de PO para esse problema?

Problema do Transporte Modelo Matemtico de PO

Minimizar f(x11, ..., xmn)=

s.axc ij

n

jij

m

i

== 11

i

n

jij ax

=1

i

m

iij bx =

=1

0ijx

mi ,,1=

nj ,,1=

mi ,,1= nj ,,1=

Problema do TransporteConsidere uma distribuidora de bebidas com 2 centros de distribuio: Paranaba e Sonora e quatro mercados consumidores principais: Campo Grande, Dourados, Corumb e Trs Lagoas. O custo unitrio para transportar uma unidade do produto de cada centro de produo a cada mercado dado na Tabela a seguir:

350

11

4

TLagoas

300500900Demanda1200785Sonora

9501075Paranaba

CorumbDouradosCGrande

Suprimento disponvel

MercadoCentro de distribui

o

Problema do Planejamento de Produo

Esses problemas envolvem decidir quais produtos e quanto fabricar de cada produto em um perodo visando a maximizar lucro da empresa.

Considere xj a quantidade do produto j=1,2,..., n a ser produzida em um perodo de planejamento.

Seja Ci, i=1,2,...m a capacidade do recursos disponvel no perodo.

Para produzir o produto j, so consumidas aij unidades do recurso i.

Uma produo mnima do produto j, digamos dj, precisa ser realizada no perodo.

As vendas do produto no excedem vj unidades no perodo em estudo.

Cada unidade do produto j resulta em uma contribuio ao lucro de lj para a empresa.

Problema do Planejamento de Produo

O problema do Planejamento de Produo

Maximizar f(x1,..., xn)= xl jn

jj

=1

Cxa ijn

jij

=1

vxd jij

mi ,,2,1 =

nj ,,2,1 =

Modelo Matemtico

O modelo matemtico do problema da rao :

Minimizar f(x1, x2, x3)=0.56x1+0.81x2+0.46x3 Sujeito a 0.2x1+0.5x2+0.4x3>=0.3

0.6x1+0.4x2+0.4x3>=0.5x1+x2+x3=1x1>=0, x2>=0, x3>=0

Mtodo Simplex

um procedimento matricial para resolver o modelo de programao linear na forma padro.

O mtodo localiza sucessivamente outra solues bsicas viveis acarretando melhores valores para a funo objetivo at ser obtida a soluo tima encontrada.

um mtodo de direes factveis que pode ser denominado mtodo de pontos extremos, uma vez que cada iterao est associada a um ponto extremo (soluo bsica factvel) do conjunto de solues factveis.

MPI so mtodos de direes factveis, porm cada iterao est associada a um ponto interior do conjunto de solues factveis.

Cada iterao de um MPI requer um nmero maior de operaes computacionais, porm o nmero de iteraes menor, isto se torna uma vantagem na resoluo de problemas de grande porte.

O MPI consegue obter um melhor desempenho computacional para problemas de grande porte em comparao aos mtodos clssicos, por exemplo, o mtodo simplex.

Mtodos de Pontos Interiores

Mtodos heursticos procuram um compromisso entre o desempenho na obteno de uma soluo e a qualidade da soluo.

A qualidade da