202183_152013_Programação+Matemática+-+Parte+I+-+Introdução

Prévia do material em texto

Ciência da Computação
Programação Matemática
Prof. Malomar Alex Seminotti
Ciência da Computação – URI
malomar@uricer.edu.br
Ciência da Computação
Introdução
• A Programação Matemática (PO) é um ramo da 
matemática aplicada que faz uso de modelos 
matemáticos, estatísticos e de algoritmos na 
ajuda à tomada de decisão
• Segundo a SOBRAPO, a Programação 
Matemática (PO) é uma ciência aplicada voltada 
para a resolução de problemas reais
• Tem como foco a tomada de decisões, 
aplicando conceitos e métodos de várias áreas 
científicas na concepção, planejamento ou 
operação de sistemas
Programação Matemática - Prof. Malomar Alex Seminotti 2
Ciência da Computação
Introdução
• A PO busca projetar, planejar e operar sistemas 
em situações que requerem alocações 
eficientes de recursos escassos, utilizando 
modelos matemáticos estruturados em fases
• É a aplicação do método científico, por equipes 
multidisciplinares, a problemas envolvendo o 
controle de sistemas organizados de forma a 
fornecer soluções que melhor interessam a 
determinada organização
Programação Matemática - Prof. Malomar Alex Seminotti 3
Ciência da Computação
Histórico
• O termo Programação Matemática parece ter 
surgido no início da década de 1940, 
coincidindo com a Segunda Guerra Mundial, 
que geralmente é citada como a responsável 
pelo surgimento da PO
• Em agosto de 1940, o Chefe do comando 
Antiaéreo da Grã-Bretanha solicitou a 
colaboração do professor P.M.S. Blackett da 
Universidade de Manchester, prêmio Nobel de 
Física
Programação Matemática - Prof. Malomar Alex Seminotti 4
Ciência da Computação
Histórico
• Seu objetivo era estudar a coordenação dos 
equipamentos de radar com um novo aparelho, 
que indicava a elevação e rumo dos canhões, 
tendo por objetivo abater aviões nazistas que 
bombardeavam Londres
• Para realizar seu trabalho, Blackett reuniu uma 
equipe com treino científico, mas não 
necessariamente especialista em eletrônica
Programação Matemática - Prof. Malomar Alex Seminotti 5
Ciência da Computação
Histórico
• Essa equipe foi batizada pelos contemporâneos 
como “o Circo de Blackett”, que, apesar do 
nome depreciativo, demonstrou ser altamente 
eficiente na tarefa para a qual foi criada
• O sucesso de Blackett e de seu “circo” 
estimulou a formação de equipes mistas de 
especialistas nos diversos campos do 
conhecimento vinculados aos problemas 
relativos às operações militares, táticas ou 
estratégicas
Programação Matemática - Prof. Malomar Alex Seminotti 6
Ciência da Computação
Histórico
• Assim foram resolvidos, com sucesso, 
problemas referentes à detecção de navios e 
submarinos inimigos por meio do uso de radar 
em aeroplanos, e a determinação da melhor 
profundidade para explodir as bombas lançadas 
dos aviões contra os submarinos, entre outros.
• As equipes de “analistas operacionais”, como 
eles foram chamados naquela época, 
começaram a se expandir na Grã-Bretanha e 
logo, no Canadá, na Austrália e nos Estados 
Unidos
Programação Matemática - Prof. Malomar Alex Seminotti 7
Ciência da Computação
Histórico
• Terminada a guerra, o sucesso da PO nos 
aspectos bélicos motivou interesse no mundo 
dos negócios que passava a apresentar 
crescente complexidade e especialização
• A explosão econômica, a partir da reconstrução 
mundial, contribui de maneira particularmente 
importante para a crescente convicção de 
muitos executivos, de que as técnicas de PO 
aplicavam-se não só aos aspectos bélicos, 
como também aos de contexto organizacional
Programação Matemática - Prof. Malomar Alex Seminotti 8
Ciência da Computação
Histórico
• O rápido crescimento da PO, primeiramente, foi 
devido o desenvolvimento rápido das técnicas 
gestadas durante a guerra
• O Método Simplex, por exemplo, já havia sido 
desenvolvido por Dantzig em 1947
• No final da década de 1950, já estavam bem 
desenvolvidas as ferramentas padrão da PO, 
como programação linear, teoria das filas e 
teoria do inventário
Programação Matemática - Prof. Malomar Alex Seminotti 9
Ciência da Computação
Sociedades Profissionais
• Há várias sociedades profissionais no mundo 
ligadas à PO, bem como são publicados muitos 
periódicos, onde se tornam públicos os 
trabalhos associados à Programação 
Matemática
• Para conhecimento e referências, a seguir 
algumas sociedades e periódicos mais 
relevantes:
Programação Matemática - Prof. Malomar Alex Seminotti 10
Ciência da Computação
Sociedades Profissionais
• INFORMS – The Institute for Operations Research
and the Management Sciences (www.informs.org)
• EURO - European Operational Research Society
(www.euro-online.org)
• IFORS – The International Federation of Operational
Research Societies (www.ifors.org )
• SOBRAPO - Sociedade Brasileira de Pesquisa
Operacional (www.sobrapo.org.br)
• ABEPRO – Associação Brasileira de Engenharia de
Produção (www.abepro.org.br)
Programação Matemática - Prof. Malomar Alex Seminotti 11
Ciência da Computação
Periódicos
• Operations Research (or.pubs.informs.org)
• European Journal of Operational Research
(www.elsevier.com/locate/ejor)
• Interfaces (interfaces.journal.informs.org)
• Management Sciences
(mansci.pubs.informs.org)
• Revista da SOBRAPO (www.sobrapo.org.br)
Programação Matemática - Prof. Malomar Alex Seminotti 12
Ciência da Computação
Periódicos
• Gestão & Produção (www.scielo.br/gp)
• Produção (www.abepro.org.br)
• Brazilian Journal of Operations and Production
Management (www.abepro.org.br)
Programação Matemática - Prof. Malomar Alex Seminotti 13
Ciência da Computação
Exemplos Reais
• O desenvolvimento e o uso da PO provocou um 
impressionante aumento na eficiência das 
organizações, resultando em contribuição 
notável para o aumento da produtividade da 
economia de diversos países
• O quadro a seguir mostra o impacto financeiro 
do uso de técnicas da PO em algumas 
organizações:
Programação Matemática - Prof. Malomar Alex Seminotti 14
Ciência da Computação
Exemplos Reais
Organização Natureza da Aplicação Economia Anual 
(US$)
Samsung Eletronics Desenvolver métodos de redução de tempo 
de fabricação e níveis de estoque
200 milhões mais 
receitas
Procter & Gamble Redesenho do sistema de produção e 
distribuição
200 milhões
PSA Peugeot Citroen Orientar o processo de projeto para plantas 
de montagem de veículos eficientes
130 milhões mais 
lucros
AT&T Projeto e operação de call centers 750 milhões mais 
lucros
Time Inc. Gerenciamento dos canais de distribuição 
para revistas
3,5 milhões mais 
lucros
Taco Bell Programar a escala de funcionários nas lojas 
da rede
13 milhões
Programação Matemática - Prof. Malomar Alex Seminotti 15
Ciência da Computação
Exemplos Reais
Organização Natureza da Aplicação Economia Anual 
(US$)
Merrill Lynch Gestão de riscos de liquidez parra as linhas 
de crédito rotativo
4 bilhões mais 
liquidez
General Motors Aumentar a eficiência das linhas de 
produção
90 milhões
KeyCorp Aumentar a eficiência do serviço dos caixas 
de banco
20 milhões
Sears Programação e rotas de veículos para as 
frotas de entrega e atendimento domiciliar
42 milhões
Pacific Lumber
Company
Gestão de ecossistemas florestais a longo 
prazo
398 milhões
Workers
Compensation
Gestão de pedidos de benefícios por 
invalidez e reabilitação de alto risco
4 milhões
Programação Matemática - Prof. Malomar Alex Seminotti 16
Ciência da Computação
Problemas Solucionados com PO
• Dentre os tipos de problemas em que a PO 
pode ser utilizada para ajudar no processo de 
decisão, encontram-se:
– Problemas de Otimização de Recursos
– Problemas de Localização
– Problemas de Roteirização
– Problemas de Carteiras de Investimento
– Problemas de Alocação de Pessoas
– Problemas de Previsão e Planejamento
Programação Matemática - Prof. Malomar Alex Seminotti 17
Ciência da Computação
Técnicas da PO
• Programação linear: mix de produção, mistura 
de matérias-primas, modelosde equilíbrio 
econômico, carteiras de investimentos, 
roteamento de veículos, jogos entre empresas
• Modelos em redes: rotas econômicas de 
transporte, distribuição e transporte de bens, 
alocação de pessoal, monitoramento de projetos
• Teoria de filas: congestionamento de tráfego, 
operações de hospitais, dimensionamento de 
equipes de serviço
Programação Matemática - Prof. Malomar Alex Seminotti 18
Ciência da Computação
Técnicas da PO
• Outras técnicas de PO: programação 
dinâmica, simulação, programação inteira, 
programação não-linear, teoria de estoques,
programação por metas, programação 
multiobjetivo, ...
Programação Matemática - Prof. Malomar Alex Seminotti 19
Ciência da Computação
Aplicações da PO – Exemplos
• Alimentação: que alimentos as pessoas (ou 
animais) devem utilizar de modo que o custo 
seja mínimo e os mesmos possuam nutrientes 
nas quantidades adequadas?
• Rotas de Transporte: qual deve ser o roteiro de 
transporte de veículos de carga de modo que 
entreguem toda a carga no menor tempo e no 
menor custo total?
Programação Matemática - Prof. Malomar Alex Seminotti 20
Ciência da Computação
Aplicações da PO – Exemplos
• Manufatura: qual deve ser a composição de 
produtos a serem fabricados por uma empresa 
de modo que se atinja o lucro máximo, sendo 
respeitadas as limitações ou exigências do 
mercado comprador e a capacidade de 
produção da fábrica?
• Petróleo: qual deve ser a mistura de petróleo a 
ser enviada para uma torre de craqueamento
para produzir seus derivados (gasolina, óleo, 
etc.) a um custo mínimo?
Programação Matemática - Prof. Malomar Alex Seminotti 21
Ciência da Computação
Aplicações da PO – Exemplos
• Agricultura: que alimentos devem ser 
plantados de modo que o lucro seja máximo e 
sejam respeitadas as características do solo?
• Carteira de Investimentos: quais ações devem 
compor uma carteira de investimentos de modo 
que o lucro seja máximo e sejam respeitadas as 
previsões de lucratividade e as restrições 
governamentais?
Programação Matemática - Prof. Malomar Alex Seminotti 22
Ciência da Computação
Fases de um Estudo em PO
• Um estudo em Programação Matemática 
costuma envolver seis fases:
– Definição do problema
– Construção do modelo do sistema
– Cálculo da solução através do modelo
– Teste do modelo e da solução
– Estabelecimento de controles da solução
– Implantação e acompanhamento
Programação Matemática - Prof. Malomar Alex Seminotti 23
Ciência da Computação
Definição do Problema
• Nesta fase, o administrador do sistema e o 
responsável pelo estudo em P.O. deverão 
discutir, no sentido de colocar o problema de 
maneira clara e coerente
• Devem definir os objetivos a alcançar e quais os 
possíveis caminhos alternativos para que isso 
ocorra
Programação Matemática - Prof. Malomar Alex Seminotti 24
Ciência da Computação
Definição do Problema
• Além disso, serão levantadas as limitações 
técnicas do sistema e as relações desse 
sistema com outros da empresa ou do ambiente 
externo, com a finalidade de criticar a validade 
de possíveis soluções em face destes 
obstáculos
• Deverá ainda ser acordada uma medida de 
eficiência para o sistema, que permita ao 
administrador ordenar as soluções encontradas, 
concluindo o processo decisório
Programação Matemática - Prof. Malomar Alex Seminotti 25
Ciência da Computação
Construção do Modelo do Sistema
• Os modelos que interessam em Programação 
Matemática são os modelos matemáticos, isto é, 
modelos formados por um conjunto de 
equações e inequações
• Uma das equações do conjunto serve para 
medir a eficiência do sistema para cada solução 
proposta
• É a função objetivo ou função de eficiência
Programação Matemática - Prof. Malomar Alex Seminotti 26
Ciência da Computação
Construção do Modelo do Sistema
• As outras equações geralmente descrevem as 
limitações ou restrições técnicas do sistema
• As variáveis que compõem as equações
são de dois tipos:
– Variáveis controladas ou de decisão
– Variáveis não controladas
Programação Matemática - Prof. Malomar Alex Seminotti 27
Ciência da Computação
Construção do Modelo do Sistema
• Variáveis controladas ou de decisão: são 
variáveis cujo valor está sob controle do 
administrador. Decidir, neste caso, é atribuir um 
particular valor a cada uma dessas variáveis. Numa 
programação de produção, por exemplo, a variável 
de decisão é a quantidade a ser produzida num 
período, o que compete ao administrador controlar
• Variáveis não controladas: são as variáveis cujos 
valores são arbitrados por sistemas fora do controle 
do administrador. Custos de produção, demanda de 
produtos, preço de mercado são variáveis não
controladas
Programação Matemática - Prof. Malomar Alex Seminotti 28
Ciência da Computação
Construção do Modelo do Sistema
• Um bom modelo é aquele que tem desempenho 
suficientemente próximo do desempenho da 
realidade e é de fácil experimentação
• Essa proximidade desejada é variável, 
dependendo do objetivo proposto
• Um bom modelo para um objetivo pode ser 
péssimo para outro
Programação Matemática - Prof. Malomar Alex Seminotti 29
Ciência da Computação
Construção do Modelo do Sistema
• A fidelidade de um modelo é aumentada à 
medida que ele incorpora características da 
realidade, com a adição de novas variáveis
• Isso aumenta sua complexidade, dificultando a 
experimentação, o que se leva a considerar o 
fator custo-benefício quando se pensa em 
melhorar o desempenho de um modelo
Programação Matemática - Prof. Malomar Alex Seminotti 30
Ciência da Computação
Cálculo da Solução Através do Modelo 
• É feito através de técnicas matemáticas 
específicas
• A construção do modelo deve levar em
consideração a disponibilidade de uma técnica 
para o cálculo da solução
Programação Matemática - Prof. Malomar Alex Seminotti 31
Ciência da Computação
Teste do Modelo e da Solução
• Esse teste é realizado com dados empíricos do 
sistema
• Se houver dados históricos, eles serão 
aplicados no modelo, gerando um desempenho 
que pode ser comparado ao desempenho 
observado no sistema
• Se o desvio verificado não for aceitável, a 
reformulação ou mesmo o abandono do modelo 
será inevitável
Programação Matemática - Prof. Malomar Alex Seminotti 32
Ciência da Computação
Estabelecimento de Controles da Solução
• A construção e experimentação com o modelo 
identificam parâmetros fundamentais para
solução do problema
• Qualquer mudança nesses parâmetros deverá 
ser controlada para garantir a validade da 
solução adotada
• Caso alguns desses parâmetros sofra desvio 
além do permitido, o cálculo de nova solução ou 
mesmo a reformulação do modelo poderá ser 
necessária
Programação Matemática - Prof. Malomar Alex Seminotti 33
Ciência da Computação
Implementação e Acompanhamento
• Nesta fase, a solução será apresentada ao 
administrador
• Essa implantação deve ser acompanhada para 
se observar o comportamento do sistema com a 
solução adotada
• Algum ajuste pode ser requerido
Programação Matemática - Prof. Malomar Alex Seminotti 34