Programação Matemática
Professoras:
Franklina Toledo e Maristela Santos*
Instituto de Ciências Matemáticas e de Computação -
ICMC
Universidade de São Paulo – USP
*Estes slides foram feitos em colaboração com pesquisadores do Laboratório de Otimização.
Ementa:
Definição e formulação de problemas de programação
matemática.
Teoria da programação linear e o método simplex.
Programação inteira e o algoritmo de separação e
avaliação (branch-and-bound).
Heurísticas.
Objetivos do curso:
Modelagem: capacitar o aluno a compreender e escrever
modelos matemáticos para representar problemas simples de
otimização linear (com variáveis contínuas e inteiras).
Resolução de problemas:
capacitar o aluno a resolver problemas pequenos lineares e
lineares inteiros (método simplex e método branch-and-
bound);
capacitar o aluno a resolver problemas maiores por um
software de otimização;
capacitar o aluno a compreender e elaborar heurísticas
simples.
Material do Curso:
ARENALES, M; ARMENTANO, V; MORABITO, R E YANASSE, H Pesquisa operacional . Ed. Campus, 2006.
(Livro Texto)
WINSTON, W.L. – Operations Research – Applications and Algorithms – IE-THOMSON, 2004.
GOLDBARG, M.C. e LUNA, H.P.L – Otimização Combinatória e Programação Linear – Modelos e Algoritmos
– Editora CAMPUS, 2005.
BERTSIMAS, D. E TSITSIKLIS, J.N. – Introduction to Linear Optimization, Athena Scientific, 1997.
HILLIER, F.S.; LIEBERMAN, G.J.- Introdução à Pesquisa Operacional, Rio de Janeiro, RJ, Campus, 1988.
BAZARAA,M.S.; JARVIS,J.J., Linear Programming and Network Flows, John Wiley and Sons, N.Y., 1977.
Material de apoio: aulas no TIDIA
Avaliações:
Provas:
Provas intermediárias (9 provas): 70% nota
Prova Final – 30% nota – (28/11/2016)
Nota: Observem o cronograma disponível no
TIDIA.
Lembrem-se: Possíveis alterações do
cronograma podem ser realizadas.
Avaliação:
NotaFinal = 0,7*MProvas + 0,3*ProvaFinal
MProvas = média aritmética das 70% melhores
provas.
Horário de Atendimento:
Estagiário PAE:
• Confirmar no TIDIA
Professora:
• Confirmar no TIDIA
Vídeo:
[Link]/watch?v=tX6Rw7KJGjE
Um breve histórico de PO
1939-1945: Durante a 2a Guerra Mundial, as gerências militares
britânica e americana empregaram uma abordagem científica
para tratamento de problemas de gerenciamento de recursos
escassos (radares, tropas, munição, remédios etc.), de forma
eficaz.
1936: British military applications: Foi utilizado o termo
"operational research".
Programação Matemática
• O que é otimização?
• Será que vocês já resolveram algum problema de otimização
antes?
• Otimização tem utilizada prática?
Programação Matemática
Um estudante deseja balancear os alimentos que consome no café
da manhã, de modo que minimize o custo. Para isso, ele pretende se
alimentar de modo que consuma no mínimo 130mg de cálcio e no
máximo 480 kcal. O valor nutritivo e o preço por porção dos
alimentos a serem considerados são dados por:
Tipo de Cálcio Energia Preço
alimento Porção (mg) (kcal) (R$)
Leite
achocolatado 100ml 70 83 0,90
Pão de forma 100g 2,5 343 0,10
Quanto de cada alimento ele deve consumir?
Programação Matemática:
"Em matemática, o termo otimização, ou programação matemática, refere-
se ao estudo de problemas em que se busca minimizar ou maximizar uma
função através da escolha sistemática dos valores de variáveis reais ou
inteiras dentro de um conjunto viável.”
Fonte: Wikipedia.
Programação Matemática
Programação Matemática
Recursos escassos:
Minimizar tempo para realizar tarefas
diárias;
Minimizar custos;
Minimizar o espaço utilizado.
Melhorar eficiência de empresas.
Ajudar na organização do planejamento e
da produção.
Grande Área: Pesquisa Operacional (Operations
Research)
"Pesquisa operacional (PO) é um ramo interdisciplinar da matemática
aplicada que faz uso de modelos matemáticos, estatísticos e de algoritmos
na ajuda à tomada de decisões. É usada sobretudo para analisar sistemas
complexos do mundo real, tipicamente com o objetivo de melhorar ou
otimizar a performance.“
Fonte: Wikipedia
Um breve histórico de PO
1939-1945: Durante a 2a Guerra Mundial, as gerências militares
britânica e americana empregaram uma abordagem científica
para tratamento de problemas de gerenciamento de recursos
escassos (radares, tropas, munição, remédios etc.), de forma
eficaz.
1936: British military applications: Foi utilizado o termo
"operational research".
Um breve histórico de PO
1947: Início do interesse das indústrias na utilização das técnicas
desenvolvidas na área militar, para auxiliar no planejamento e
controle da produção.
A maioria desses problemas é formulada por meio de modelos
matemáticos lineares
Um breve histórico de PO
1947:George B. Dantzig propôs um método prático para solução de
modelos lineares (paper: Programming in a Linear Structure).
Em 1979, Leonid Khachiyan desenvolveu um novo algoritmo para
resolver modelos de programação linear: o Algoritmo Elipsóide (tempo
polinomial porém mais lento do que o Simplex).
Em 1984, surge mais um método de se resolver problemas lineares:
Algoritmo dos Pontos Interiores, criado por Narendra Karmarkar
(tempo polinomial e competia com o Simplex).
mais datas( [Link]
02/[Link])
Problema da dieta George Stigler
(Historia)
• Primeiro problema de computação de grande escala com o método simplex de George
B. Dantzig.
• Em 1945, George Stigler apresentou o problema (Stigler, 1945): para um homem
mediano pesando aproximadamente 70 kg, qual quantidade dentre 77 diferentes
alimentos deveria ser ingerida diariamente, de modo que as necessidades mínimas de
nutrientes fossem iguais às recomendadas pelo Conselho Nacional de Pesquisa Norte-
americano e, além disso, a dieta elaborada tivesse o menor custo possível .
• 9 inequações e 77 variáveis não negativas- Heurística de Stigler avaliou 510 diferentes
possibilidades de combinação de alimentos – Solução 39,93 dólares por ano.
• Método Simplex (1947) - apoio de 9 pessoas utilizando calculadoras de mesa de
operação manual e utilização de um recurso estimado de 120 dias-homem- Solução
ótima - 39,69 dólares . Hoje menos de 1s nos computadores atuais.
• (Retirado do artigo: NAMEN, Anderson Amendoeira; BORNSTEIN, Cláudio Thomás.
Uma ferramenta para avaliação de resultados de diversos modelos de otimização de
dietas. Pesqui. Oper., Rio de Janeiro , v. 24, n. 3, p. 445-465).
Associações Científicas
IFORS - International Federation Of Operational Research
Societies ([Link] .
EURO - The Association of European Operational Research
Societes ([Link]
SOBRAPO - Sociedade Brasileira de Pesquisa Operacional
([Link]
SBMAC- Sociedade de Matemática Aplicada e Computacional
([Link]
Resolução de um problema utilizando PO
segue as seguintes fases
Razão para a construção de modelos
Entender melhor o problema;
Analisar diversas soluções;
Propor soluções não aparentes;
Experimentar diversos cenários.
Modelo?
Foto tirada no Museu da TAM.
Construindo um modelo matemático
Passo Fundamental: Ouvir aquele que lida com o problema
real.
Passo 1: Descobrir o que deve ser determinado (variáveis
do problema).
Passo 2: Descobrir o que está disponível (dados do
problema).
Passo 3: Reproduzir os caminhos que levam a uma solução
(equações).
Construindo um modelo matemático
A busca de uma solução mais adequada entre diversas soluções
alternativas traz consigo os elementos de um Problema de
Otimização
Devemos estabelecer um critério de avaliação das soluções
alternativas, o qual nos permite dizer que uma solução é
“melhor” que outra (objetivo ou subjetivo).
A este critério de avaliação chamamos de função objetivo, que
buscamos otimizar, ou seja, maximizar ou minimizar.
Por outro lado, as soluções alternativas devem ser possíveis de
execução indicando a presença de restrições que devem ser
respeitadas
Construindo um modelo matemático
• Formato geral:
Minimize (maximize) função objetivo
Sujeito a: restrições: equações ou
inequações
domínio das variáveis
Construindo um modelo matemático
Construindo um modelo matemático