View
224
Download
0
Category
Preview:
Citation preview
1
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
1
Investigação Operacional(Mestrado)
Engenharia Industrial
José António Oliveirahttp://dps.uminho.pt/pessoais/zan
Universidade do Minho - Escola de EngenhariaDepartamento de Produção e Sistemas
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
2
Investigação Operacional – IOOperations Research – OR (USA)
Operational Research – OR (UK)
Management Science - MS
O que é ?
2
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
3
Investigação Operacional – IOA Investigação Operacional é a disciplina que aplica métodos analíticos avançados para ajudar a tomar melhores decisões.
Usando técnicas como modelação matemática para analisar situações complexas, a Investigação Operacional dá aos executivos o poder de tomar decisões mais efectivas e construir sistemas mais produtivos baseado em:
– Dados mais completos– Consideração de todas as opções disponíveis– Predições cuidadosas de resultados e estimativas de risco– Nas mais recentes ferramentas de decisão e técnicas
Em poucas palavras...
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
4
Investigação Operacional – IO
Assim que um modo bom ou melhor modo de proceder for identificado, as pessoas de IO são frequentemente centrais na implementação da mudança proposta.
As Organizações tem em conta uma gama extensiva de melhorias operacionais - por exemplo, maior eficiência, melhor atendimento ao consumidor, qualidade mais elevada ou mais baixo custo.
Em poucas palavras...
3
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
5
Investigação Operacional – IO
Qualquer que seja o ramo da engenharia a IO pode oferecer a flexibilidade e a adaptabilidade para a proporcionar ajuda objectiva.
A maioria dos problemas que a IO enfrenta são confusos e complexos, por vezes implicando incerteza considerável. A IO pode usar métodos quantitativos avançados, modelação, estruturação de problemas, simulação e outras técnicas analíticas para examinar suposições, facilitando um aprofundamento e decidir a acção prática.
Em poucas palavras...
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
6
Investigação Operacional
Ciência aplicada àresolução de problemas
do mundo real
Concluindo...
4
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
7
IO em Portugal• http://www.apdio.pt/
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
8
5
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
9
IO 2006: 9-11 OutubroSala Millennium BCP (Piso 3) / Aud.III (Pi Sala 202 (Piso 2) / UNICRE (Piso 3) Sala Aud. I (Piso 2) Sala 303 (Piso 3) / ctt (Piso 3) Sala CGD (Piso 4) Sala Edifer (Piso 2)
9 Out. 15:10-16:30 SC1: Optimização I SC2: Meta-heurísticas I SC3: Grafos e Redes I SC4: Rotas SC5: Produção I SC6: Transportes I
10 Out. 09:00-10:00 TA1: Optimização II TA2: DEA I TA3: Multicritério I TA4: Multiobjectivo I TA5: Data Mining TA6: Economia e Finanças I
10 Out. 10:10-11:10 TB1: Localização I TB2: DEA II TB3: Grafos e Redes II TB4: Multiobjectivo II TB5: Transportes II TB6: Modelos Estocásticos I
10 Out. 15:10-16:30 TC1: Localização II TC2: Redes Neuronais TC3: Multicritério II TC4: Escalonamento TC5: Produção II TC6: Economia e Finanças II
10 Out. 17:00-18:20 TD1: Modelos Estocásticos II TD2: DEA III TD3: Avaliação de Desempenho TD4: Logística I TD5: Sequenciamento I
11 Out. 09:00-10:00 QA1: Programação Inteira I QA2: DEA IV QA3: Grafos e Redes III QA4: Multiobjectivo III QA5: Produção III QA6: Corte e Empacotamento I
11 Out. 10:10-11:10 QB1: Programação Inteira II QB2: Meta-heurísticas II QB3: Multicritério III QB4: Logística II QB5: Sequenciamento II QB6: Corte e Empacotamento II
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
10
Os problemas do mundo real:• são difíceis de solucionar porque:
– O número de soluções possíveis no espaço de pesquisa é tão grande que impede qualquer pesquisa exaustiva da melhor solução;
– O problema é tão complicado, que para tornar possível uma resposta que seja, temos de usar modelos para o problema de tal modo simplificados que o resultado não se adequa;
– A função de avaliação que descreve a qualidade de qualquer solução proposta tem ruído, ou varia com o tempo, e por isso uma única solução não é suficiente, mas sim uma série inteira de soluções;
– As soluções possíveis são tão restringidas, que construir uma solução possível é uma resposta difícil, quanto mais encontrar a solução óptima;
6
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
11
Não podemos simplificar?
Problema Modeloaprox. Soluçãoexact. (Modeloaprox.)
Problema Modeloexact. Soluçãoaprox. (Modeloexact.)
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
12
Um problema difícil• Até ao momento, todos os algoritmos
conhecidos para solucionar os problemas difíceis (NP-completos) requerem um tempoque é uma função exponencial do tamanho do problema, (é desconhecido se há qualquer algoritmo mais rápido).
• No pior caso, este tipo de algoritmos pode conduzir à enumeração completa das soluções.
• São muitos os problemas difíceis?– Problemas NP-Completos
7
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
13
NP - Completos• Qual a dificuldade?
Não existe um algoritmo eficiente para a solução
• É importante ter um algoritmo eficiente?
Principalmente se queremos resolver problemas de grande dimensão e não dispomos de muito tempo para computação.
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
14
Métodos Heurísticos• Heurístico é a arte e ciência de descoberta. A
palavra vem da mesma raiz grega como "eureka", e que significa “encontrar”.
• Uma heurística não garante a solução óptimado problema, mas frequentemente resolve-o bem, e isto basta para a maioria das práticas, e geralmente é mais rápido que um método de solução exacta.
8
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
15
Métodos Heurísticos• sacrificam a garantia da obtenção da solução óptima
pela obtenção de boas soluções numa significativa redução de tempo de computação.
• Estes métodos têm tido uma atenção crescente ao longo dos últimos 30 anos por parte da comunidade científica.
– MIC’2001 - 4th Metaheuristics International Conference Porto, Portugal, July, 2001
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
16
algoritmos• Porquê tanto estudo?
• O que é um algoritmo perfeito?
Eficácia
Eficiência
9
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
17
Resumo do MIC’2001• Novos algoritmos: Hibridar & Nova estratégia & (+S+E+E)
– (+Simples+Eficaz+Eficiente)
• Telecomunicações ($$) & Saúde ($$) & Alta Finança ($$$$)
• 1ª aplicação da técnica num problema
• Um novo problema (no mundo real) ou modelos mais realistas
• Funções objectivo mais complexas – multi-objectivo/critério
• Paralelizar algoritmos - melhor uso da programação
• Melhor conhecimento específico do problema / vizinhança ...
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
18
Porquê estudar IO?
10
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
19
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
20
11
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
21
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
22
12
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
23
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
24
13
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
25
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
26
Porquê estudar IO?
14
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
27
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
28
Tipo de Aplicações• Ampla variedade de problemas• É possível identificar um pequeno
conjunto de problemas que representam a maioria dos problemas.
• Estes problemas repetem-se com frequência
• Desenvolveram-se técnicas protótipo para modelizar e encontrar as soluções para esses modelos.
15
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
29
Tipo de Aplicações• Previsão:• Análise de séries temporais para
responder a questões típicas:• Como será a procura de produtos?• Quais serão os modelos de venda?• Como afectará os ganhos?
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
30
Tipo de Aplicações• Finanças e investimento:• Quanto capital é necessário?• Onde pode ser obtido?• Quanto custará?
16
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
31
Tipo de Aplicações• Planeamento e afectação de mão-de-
obra:• Quantos empregados são necessários?• Que habilitações / formação devem ter?• Quanto tempo devem trabalhar para
nós?
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
32
Tipo de Aplicações• Sequenciamento e escalonamento:• Que tarefas são mais importantes?• Em que ordem devem ser realizadas?
17
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
33
Tipo de Aplicações• Localização, afectação, distribuição e
transportes:• Qual é a melhor localização para uma
operação?• Que dimensão devem ter as instalações?• Que recursos são necessários?• Existem deficiências?• Como se podem estabelecer
prioridades?
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
34
Tipo de Aplicações• Política de confiabilidade e manutenção:• Como funciona o equipamento?• Quanto é a sua confiabilidade?• Quando deve ser substituído?
18
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
35
Tipo de Aplicações• Controlo de inventário e rupturas de
stock:• Quantas existências deveríamos
manter?• Quando se encomenda?• Quanto devemos pedir?
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
36
Tipo de Aplicações• Planeamento e controlo do projecto:• Quanto tempo requererá o projecto?• Quais são as actividades mais
importantes?• Como devem ser utilizados os recursos?
19
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
37
Tipo de Aplicações• Filas de espera e congestionamento:• Qual é o comprimento das filas de
espera?• Quantos servidores deveríamos utilizar?• Qual é o nível de serviço que estamos a
oferecer?
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
38
Tipo de Aplicações• A ampla gama de potenciais aplicações e
a grande variedade de técnicas para o processo de modelização em Investigação Operacional, que se podem eleger e combinar para se alcançar uma abordagem multidisciplinar, funcionam em conjunto, fazendo com que a profissão seja dinâmica e estimulante.
20
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
39
Porquê estudar IO?
• Que pode esperar o aluno obter como recompensa? – o prazer de fazer coisas. – o prazer de fazer coisas que são úteis. – o fascínio de lidar com objectos complexos tipo quebra-
cabeças.– aprender continuamente.
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
40
Porquê estudar IO?"O que devo aprender em investigação
operacional se pretendo tornar-me um administrador em vez de um especialista?“
" O que devo aprender em investigação operacional se desejar aplicá-la a problemas reais?“
21
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
41
Porquê estudar IO?Um único curso introdutório de
investigação operacional não pode responder completamente a nenhuma das duas perguntas.
Mas um curso assim pode responder melhor à primeira pergunta que àsegunda.
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
42
Porquê estudar IO?Dentro do contexto destas duas
perguntas, os principais objectivos do curso são:
• Apresentar as ideias importantes em investigação operacional que sejam tanto fundamentais como duradouras.
• Demonstrar a coerência da metodologia de investigação operacional.
22
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
43
Porquê estudar IO?• Dar aos alunos suficiente compreensão e
confiança para apreciar as forças e as limitações inerentes da abordagem de investigação operacional.
• Preparar e motivar futuros especialistas a continuarem em seus estudos por terem uma visão geral mais penetrante de investigação operacional.
Universidade do Minho2006
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
44
Porquê estudar IO?Os estudantes que frequentam esta
disciplina aumentam suas habilitações para formular e construir modelos formais para situações de decisão complexas, de perceber as questões críticas a serem resolvidas e de isolar os fenómenos básicos que constituem os elementos mais importantes de situações reais.
1
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
1
Investigação OperacionalModelos de Programação Linear
(Licenciatura)
Tecnologias e Sistemas de Informação http://dps.uminho.pt/pessoais/zan
Universidade do Minho - Escola de EngenhariaDepartamento de Produção e Sistemas
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
2
Modelação MatemáticaAs técnicas e algoritmos abordados neste curso destinam-se a estruturar e a solucionar os modelos quantitativos que podem ser expressos matematicamente.
Os principais modelos de IO são denominados de Programação Matemática e constituem uma das mais importantes variedades dos modelos quantitativos.
Programação é entendida no sentido de planeamento, e não no sentido da "programação" computacional. A Programação Matemática irá implicar programação computacional, uma vez que o número de variáveis de decisão e restrições é enorme na prática.
2
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
3
Modelação MatemáticaO campo da Programação Matemática é enorme e suas técnicas são de grande utilidade na solução de problemas de optimização.
Várias peculiaridades contextos de programação (planeamento), os métodos de solução especializados
O processo de modelagem matemática, em si, pouco varia, contudo as técnicas de solução acabaram agrupadas em várias subáreas como:• Programação Linear• Programação Não-linear• Programação Inteira
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
4
PROGRAMAÇÃO LINEAR - PLCaracterísticas do Modelo de PLModelo básico – serve para a compreensão de todos os outros modelos da Programação Matemática.
Os conceitos de base serão estendidos aos outros modelos, concedendo suporte a estudos mais avançados.
Uma outra vantagem do modelo PL está na extraordinária eficiência dos algoritmos de solução hoje existentes, disponibilizando alta capacidade de cálculo e podendo ser facilmente implementado até mesmo através de folhas de cálculo e com o auxílio de computadores pessoais.
3
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
5
PROGRAMAÇÃO LINEAR - PLCaracterísticas do Modelo de PLOs modelos de Programação Linear são um tipo especial de modelos de optimização. Para que um determinado sistema possa ser representado por meio de um modelo de PL, ele deve possuir as seguintes características:
• Proporcionalidade
• Não Negatividade
• Divisibilidade
• Aditividade
• Separabilidade
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
6
PROGRAMAÇÃO LINEAR - PL
ProporcionalidadeA quantidade de recurso consumido por uma dada actividade deve ser proporcional ao nível dessa actividade na solução final do problema.
O custo de cada actividade é proporcional ao nível de operação da actividade.
Um termo xi2 na função objectivo ou numa restrição
viola este pressuposto.
4
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
7
PROGRAMAÇÃO LINEAR - PL
Não NegatividadeDeve ser sempre possível desenvolver uma dada actividade em qualquer nível não negativo;
DivisibilidadeQualquer proporção de um dado recurso deve poder ser (sempre) utilizado.
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
8
PROGRAMAÇÃO LINEAR - PL
AditividadeO custo total é a soma das parcelas associadas a cada actividade.
Um termo do tipo produto (xi.xj) viola este pressuposto.
SeparabilidadePode-se identificar de forma separada o custo (ou consumo de recursos) específico das operações de cada actividade.
5
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
9
PROGRAMAÇÃO LINEAR - PLFormulação algébrica geral – forma mista
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
10
PROGRAMAÇÃO LINEAR - PLFormulação algébrica geral
Optimizar representa aqui a:
maximização
minimização
6
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
11
PROGRAMAÇÃO LINEAR - PLForma canónica Forma estandardizada/padrão
equivalentes
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
12
PROGRAMAÇÃO LINEAR - PLForma matricial
0
: /
≥
=
IxbAxasujeito
cxzMinMaxVector de sinais. Cada elemento corresponde a: ≥=≤ , ,
Matriz identidade de dimensão n.
7
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
13
PROGRAMAÇÃO LINEAR - PLUm mesmo modelo de PL, composto pelo conjunto de equações anteriormente apresentadas, pode, sem qualquer perda para suas propriedades matemáticas, ser reescrito em cada uma das formas básicas. Esse processo de tradução é realizado através das seguintes operações elementares:
– mudança no critério de optimização
– transformação de uma variável
– transformação de desigualdades em igualdades (vice versa)
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
14
PROGRAMAÇÃO LINEAR - PLOperação 1:mudança no critério de optimização, ou seja, transformação de maximização para minimização e vice versa. Essa mudança pode ser realizada através da seguinte propriedade:
8
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
15
PROGRAMAÇÃO LINEAR - PLOperação 2:transformação de uma variável livre (*• E dl), em variável não negativa. Nesse caso, a mudança exigirá a substituição da variável em transformação por duas variáveis auxiliares, ambas maiores ou iguais a zero, mas cuja soma é igual à variável original, ou seja:
ℜ∈x
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
16
PROGRAMAÇÃO LINEAR - PLOperação 3a:transformação de desigualdades em igualdades e vice-versa. Nessa situação, temos dois casos a examinar:
• Caso de transformação de restrições de menor ou igual em restrições de igualdade
– Para transformá-la numa restrição de igualdade podemos, introduzir uma variável de folga capaz de "completar" a desigualdade, o que permite representar a restrição da seguinte forma:
9
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
17
PROGRAMAÇÃO LINEAR - PLOperação 3b:transformação de desigualdades em igualdades e vice-versa. Nessa situação, temos dois casos a examinar:
• Caso de transformação de restrições de maior ou igual em restrições de igualdade
– Para transformá-la em uma restrição de igualdade podemos introduzir uma variável de folga com valor negativo capaz de "completar" a desigualdade, passando a representar a restrição da seguinte forma:
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
18
PROGRAMAÇÃO LINEAR - PLPassos para a Formulação de um PPL
– Definição das actividades• Após a análise do problema, são definidas as actividades que o
compõem. Associada a cada actividade deve ser adoptada uma unidade de medida.
– Definição dos recursos• Considerando os inputs disponíveis dentro de cada actividade,
determinam-se os recursos que são usados e produzidos.
– Cálculo dos coeficientes de consumo / produção• É indispensável estabelecer claramente como as actividades e
os recursos estão relacionados em termos de recursos necessários por unidade de actividade produzida.
10
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
19
PROGRAMAÇÃO LINEAR - PLPassos para a Formulação de um PPL (cont)
– Determinação das condições externas• Considerando que os recursos são limitados, cumpre determinar
a quantidade de cada recurso disponível para o processo modelado. Essas são as denominadas condições externas do modelo.
– Formalização do Modelo• Consiste em associar quantidades não negativas a cada uma das
actividades, escrever as equações de balanceamento e indicar o uso de cada recurso.
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
20
PROGRAMAÇÃO LINEAR - PLTerminologia
11
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
21
PROGRAMAÇÃO LINEAR - PLUma metalurgia deseja maximizar sua receita bruta. A Tabela ilustra a proporção de cada material na mistura para a obtenção das ligas passíveis de fabricação. O preço está cotado em UM (unidades monetárias) por tonelada da liga fabricada. As restrições de disponibilidade de matéria-prima também estão expressas em toneladas.
* ton. minério aaton. de liga
50003000Preço de venda (UM/ton)
15 ton0,50,25Chumbo
11 ton0,30,25Zinco
16 ton0,20,5Cobre
Disponibilidade de matéria-prima
Liga de altaresistência
Liga de baixaresistência
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
22
PROGRAMAÇÃO LINEAR - PLEscolha da variável de decisão
Esta etapa é simples quando a função objectivo e as restrições estão directamente associadas às variáveis de decisão.
Quais são as incógnitas?
O que queremos decidir?
O que é que o agente de decisão quer saber?
+- cobre? +- zinco? +- chumbo?
Ganhar muito ou pouco?
Que parâmetros são variáveis e quais são fixos?
12
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
23
PROGRAMAÇÃO LINEAR - PLEscolha da variável de decisão
Quais são as incógnitas?
xi?
O que queremos decidir?
Níveis de produção das ligas (em toneladas)
O que é que o agente de decisão quer saber?
O plano óptimo de produção.
? ?LBaixa LAltax x
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
24
PROGRAMAÇÃO LINEAR - PLFunção Objectivoexpressa em função das variáveis decisão
Maximizar ou minimizar?
Cada tonelada de liga baixa resistência contribui para o objectivo com quanto? E a de alta resistência?
z representa a receita bruta em UM em função da quantidade produzida em toneladas de ligas de baixa e alta resistência
z = 3000 5000LBaixa LAltaMaximizar x x+
13
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
25
PROGRAMAÇÃO LINEAR - PLRestrições (tecnológicas)expressa em função das variáveis decisão
Podemos produzir quanto?
O que condiciona a produção?
Matéria prima
Cobre
Zinco
Chumbo
161115
Quanto há (em ton.)?
0.50 0.2LBaixa LAltax x+
0.25 0.3LBaixa LAltax x+0.25 0.5LBaixa LAltax x+
≤≤≤
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
26
PROGRAMAÇÃO LINEAR - PLRestrições de não-negatividade
A quantidade que vamos produzir pode ser negativa?Na maioria dos problemas reais as variáveis só podem assumir valores nulos ou não negativos. São exemplos típicos variáveis que englobam peso, espaço, número de itens, configurações, pessoas etc. Eventualmente podemos dar sentido a valores negativos de tempo, unidades monetárias etc. Contudo, os valores negativos das variáveis podem ser eliminados por convenientes transformações de variáveis.
0,LBaixa LAltax x ≥
14
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
27
PROGRAMAÇÃO LINEAR - PLModelo
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
28
PROGRAMAÇÃO LINEAR - PLProblema da fábrica de móveis
Uma grande fábrica de móveis dispõe em stock 250 metros de tábuas, 600 metros de pranchas e 500 metros de painéis de aglomerado. A fábrica normalmente oferece uma linha de móveis composta por um modelo de escrivaninha, uma mesa de reunião, um armário e uma prateleira. Cada tipo de móvel consome uma certa quantidade de matéria prima, conforme a Tabela. A escrivaninha évendida por 100 unidades monetárias (u.m.), a mesa por 80 u.m., o armário por 120 u.m. e a prateleira por 20 u.m. Pede-se para exibir um modelo de Programação Linear que maximize a receita com a venda dos móveis.
15
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
29
PROGRAMAÇÃO LINEAR - PLProblema da fábrica de móveis
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
30
PROGRAMAÇÃO LINEAR - PLProblema da fábrica de móveis
16
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
31
PROGRAMAÇÃO LINEAR - PLProblema da dieta
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
32
PROGRAMAÇÃO LINEAR - PLProblema da dieta
17
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
33
PROGRAMAÇÃO LINEAR - PLProblema da dieta (geral)
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
34
PROGRAMAÇÃO LINEAR - PLProblema da dieta (geral)
Nota: O problema da dieta foi o primeiro problema de “grande dimensão” de Programação Linear a ser resolvido (1947). O modelo construído tinha 9 (in)equações (nutrientes) e 77 variáveis (alimentos).
Foi dispendido um esforço de 120 homem.dia.
Hoje, um problema de PL de grande dimensão é um problema com centenas de milhares de (in)equações e centenas de milhares de variáveis!
É corrente resolverem-se problemas com milhares de (in)equações e variáveis em poucos segundos. A evolução não se deveu apenas ao desenvolvimento dos computadores, mas também ao notável desenvolvimento da teoria.
18
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
35
PROGRAMAÇÃO LINEAR - PLProblema de transportes
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
36
PROGRAMAÇÃO LINEAR - PLProblema de transportes
19
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
37
PROGRAMAÇÃO LINEAR - PLProblema de transportes
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
38
PROGRAMAÇÃO LINEAR - PLProblema de transportes
20
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
39
PROGRAMAÇÃO LINEAR - PLLeituras aconselhadas
Secções 3.1 a 3.5 de
F. Hillier, G. Lieberman, “Introduction to Operations Research”, 7th
edition, McGraw-Hill, 2001.
Universidade do Minho2007
Investigação OperacionalJosé António Oliveira – zan@dps.uminho.pt
40
PROGRAMAÇÃO LINEAR - PLLinks
Recommended