Num problema de optimização procura-se maximizar ou minimizar uma quantidade específica que se designa objectivo, a qual depende de um número finito de variáveis iniciais (ou de input). Estas variáveis podem ser independentes entre si ou podem encontrar-se relacionadas através de uma ou mais restrições.
Exemplo 1: O seguinte é um problema de optimização para o objectivo z. (Obs. s.a. = sujeito a...)
Min z = x2 + 2 x y + y2
s.a.
x + y = 2
x, y >= 0
As variáveis iniciais são x e y, que se encontram restringidas de três formas: x e y devem sempre totalizar 2 e tanto x como y devem ser não negativos. Pretende-se encontrar valores para as variáveis iniciais que minimizem z, o quadrado da sua soma, sujeitos às limitações impostas pelas restrições.
Um Problema de Programação Matemática (PPM) é um problema de optimização no qual o objectivo e as restrições são apresentados como funções matemáticas e relações funcionais. É usual representar um PPM na forma
optimizar: z = f(x1, x2, ..., xn)
s.a.
g1(x1, x2, ..., xn) <=, =, >= b1
g2(x1, x2, ..., xn) <=, =, >= b2
...
gm(x1, x2, ..., xn) <=, =, >= bm
onde cada uma das m restrições envolve um dos três sinais de relação <=, =, >=.
Problema de Programação Linear (PPL)
Um problema de programação matemática diz-se linear se f e todas as gi , i =1, 2, ..., m são funções lineares para todas as variáveis iniciais. Isto é, se
f(x1, x2, ..., xn) = c1 x1 + c2 x2 + ... + cn xn
e
gi(x1, x2, ..., xn) = ai1 x1 + ai2 x2 + ... + ain xn
com ci e aij (i =1, 2, ..., m ; j =1, 2, ..., n) constantes conhecidas.
Qualquer outro problema que não esteja nesta forma diz-se não linear. Então, o exemplo 1 descreve um problema de programação não linear, na função objectivo z.
Programação Linear Inteira (PPLI)
Um problema de programação linear inteira é um PPL com restrições adicionais que obrigam as variáveis iniciais a serem valores inteiros. Não é necessário que os coeficientes ci e aij (i =1, 2, ..., m ; j =1, 2, ..., n) da função objectivo e das restrições sejam inteiros, apesar de muitas vezes o serem.
Programação Quadrática (PQ)
Um problema de programação quadrática é um problema de programação matemática no qual cada restrição gi é uma função linear e a função objectivo é da forma
com cij , di constantes conhecidas.
O Exemplo 1 é um problema de programação quadrática. As três restrições são lineares, e a função objectivo segue a forma quadrática com n=2 e (fazendo x = x1 e y = x2) c11 = c22 = 1 e c12 = c21 = 1 e d1 = d2 = 0.
Formulação de Problemas
Quase sempre os problemas de optimização académicos são apresentados de forma verbal ou escrita, definindo a optimização pretendida e descrevendo as relações entre as variáveis iniciais. A determinação da solução começa por formular o problema em programação matemática e resolvê-lo recorrendo a técnicas e métodos que serão descritos futuramente em outros artigos neste blog. Para transformar um problema verbal em um problema de programação matemática geralmente seguem-se três passos fundamentais:
1. Determinar a quantidade a ser optimizada e expressá-la numa função matemática. Aqui se definem as variáveis iniciais e a função objectivo.
2. Indentificar todos os requisitos, constragimentos e limitações sobre as variáveis iniciais e expressá-los matematicamente. Estes requisitos constituirão as restrições.
3. Expressar todas as condições ocultas. Estas condições não são estipuladas explicitamente no problema na forma verbal mas são aparentes na situação física que se propõe modelar. Geralmente, envolvem requisitos de não negatividade ou de integridade (valores inteiros) sobre as variáveis iniciais.
Solução
Num problema de programação matemática pretende-se encontrar solução, e se forem encontradas várias soluções igualmente optimais então qualquer uma servirá como solução optimal. Cada conjunto de restrições definirá um espaço de soluções admissíveis designado por poliedro de admissibilidade. A solução optimal do PPM estará sempre sobre a fronteira deste espaço que separa as soluções admissíveis das não admissíveis.
Problema 1
Consideremos que num talho onde se fazem diferentes rolos de carne, se pretende optimizar o custo e a quantidade de gordura no rolo de carne tradicional que consiste numa mista de carne de bovino e de porco. As peças de carne de bovino contêm 75% de carne e 25% de gordura e custa 3 €/kg; as peças de porco contêm 65% de carne e 35% de gordura e custa 3,5 €/kg. Quanto de cada tipo de carne deverá o talho usar em cada kg de rolo de carne se pretender minimizar o custo e manter a quantidade de gordura máxima em 30%?
O objectivo será a minimização do custo z (€) de cada kg de rolo de carne, onde z = 3 x peso de carne bovina + 3,5 x peso de carne de porco.
Definindo
x = peso de carne bovina usada em cada kg de rolo de carne
y = peso de carne de porco usada em cada kg de rolo de carne
a função objectivo então será
Min z = 3 x + 3,5 y
Cada kg de rolo de carne conterá 0,25 x de gordura de bovino e 0,35 y de gordura de porco. O total de gordura contida em cada kg de rolo de carne não deverá conter mais de 0,30 kg. Logo,
0,25 x + 0,35 y <= 0,30
As quantidades de carne de vaca e de porco que serão usadas em cada kg de rolo de carne deve portanto somar 1 kg.
x + y =1
Por fim, uma vez não é concebível e portanto não é admissível usar quantidades negativas de carne, ter-se-á as duas restrições escondidas adicionais x >= 0 e y >=0.
Então tem-se a formulação do PPM seguinte:
Min z = 3 x + 3,5 y
s.a.
0,25 x + 0,35 y <= 0,30
x + y =1
x >= 0, y >=0
Como se pode entender este é um problema de programação linear de apenas 2 variáveis pelo que poderá recorrer-se a uma resolução gráfica.
Observando a figura anexa, a região de admissibilidade - conjunto dos pontos (x,y) que satisfazem todas as restrições é o segmento de recta a cheio. Para determinar o valor minimal de z (z*) deve representar-se graficamente as restrições e a função objectivo. Atribuindo os valores arbitrários z = 2,5 e z = 3,5, obtém-se os objectivos respectivamente
2,5 = 3 x + 3,5 y e 3,5 = 3 x + 3,5 y
representados pelas linhas tracejadas.
Assim, pode perceber-se que a solução minimal z* será atingida na extremidade alta do segmento de admissibilidade, e que é o ponto de intersecção das duas linhas
0,25 x + 0,35 y = 0,30 e x + y =1
Logo z* = 3,25€ onde x* = 0,5 kg e y* = 0,5 kg é o ponto solução do sistema linear destas duas equações.
Sem comentários:
Mensagens mais recentes Mensagens antigas Página inicial
Subscrever: Mensagens (Atom)
Autores
Ana Maria Barreto (3)
Ana Silva (2)
Carlos Daniel (2)
Fernando Martins (7)
Francisco Cabral (3)
João Pimentel Ferreira (66)
João Torgal (2)
José Sousa (1)
Marco Tavares Pereira (5)
Nuno Lima (1)
Visitas
Caixa para fórmulas LaTex
Dúvidas a Matemática?
Respondemos gratuitamente no fórum!
As mais lidas de sempre
Milhões, Mil milhões, Biliões ou Triliões? Esclareça a confusão!
Nota : Este artigo aplica-se só a Portugal, pois no Brasil as coisas ficam mais fáceis, devido á similaridade com os EUA da notação. N...
Como encontrar raízes de polinómios de terceiro grau
Este é de facto um tema não debatido ao longo da nossa formação em Matemática, mas definitivamente muito útil nas mais diversas tarefas com...
Exames, testes e exercícios resolvidos de Análise Matemática I do ISEL
Já está disponível na Matemática Viva como acervo pedagógico e de estudo, e para consulta pública dos estudantes, diversos exames resolvido...
Como distinguir Arranjos completos, Arranjos simples e Combinações?
Muitos alunos ficam perplexos e atónitos quando se deparam com a matéria em que é necessário distinguir estes três casos. Quando aplicar os...
IRS mais justo - a eliminação dos escalões
Um dos grandes problemas do atual sistema de Imposto sobre o Rendimento de Pessoas Singulares , é a tabela com os presentes escalões. O fac...
A prova da irracionalidade da raiz de 2 por "redução ao absurdo"
Teoria dos Conjuntos | Notações, Relações e Operações
Já está na Matemática Viva, um pequeno texto de 14 páginas, claro, conciso, com explicações detalhadas de notações, operações e muito mais s...
Calculadoras Autorizadas para os Exames Nacionais de Matemática A e B
Lista exemplificativa, não exaustiva, de máquinas de calcular gráficas passíveis de serem utilizadas nos exames nacionais de Matemática A, M...
Tabela de Primitivas e Integrais
Aqui coloco uma pequena tabela com as derivadas mais comuns A fracção d/dx é uma notação equivalente a f '(x). De salientar que a v...
Média, mediana e moda - exemplo simples
Anda muita confusão na cabeça de muita gente com algo que é muito simples de entender. Imaginemos 5 irmãos que vão à pasterlaria com a ...
As mais lidas nesta semana
Milhões, Mil milhões, Biliões ou Triliões? Esclareça a confusão!
Nota : Este artigo aplica-se só a Portugal, pois no Brasil as coisas ficam mais fáceis, devido á similaridade com os EUA da notação. N...
Como encontrar raízes de polinómios de terceiro grau
Este é de facto um tema não debatido ao longo da nossa formação em Matemática, mas definitivamente muito útil nas mais diversas tarefas com...
A prova da irracionalidade da raiz de 2 por "redução ao absurdo"
Tabela de Primitivas e Integrais
Aqui coloco uma pequena tabela com as derivadas mais comuns A fracção d/dx é uma notação equivalente a f '(x). De salientar que a v...
Será que o gelo depois de derretido faz aumentar o nível da água?
Colocaram-me, em tempos quando fui a uma entrevista de emprego o seguinte problema, imagine um recipiente com água, e no topo do recipiente...
A Física e a Matemática da distância de travagem
A grande maioria dos automobilistas não tem a mínima noção do impacto que a velocidade tem na segurança rodoviária, essencialmente em meios...
Média, mediana e moda - exemplo simples
Anda muita confusão na cabeça de muita gente com algo que é muito simples de entender. Imaginemos 5 irmãos que vão à pasterlaria com a ...
A Matemática nas Escalas Musicais
A matemática e a música têm funções muito diferentes na sociedade. No entanto, estão mais intimamente relacionadas do que geralmente s...
Cálculo da exponencial de uma matriz
Em matemática, a exponencial de uma matriz é uma função matricial definida no conjunto das matrizes quadradas e possui propriedades semelh...
O Explicador e a fiscalidade
Se é explicador de qualquer matéria, e pretende cumprir a lei como é de saudar nos cidadãos que cumprem os seus deveres cívicos, terá de pag...
Comentários recentes
A Matemática Viva
Abstracta, racional, por vezes intuitiva, sempre filosófica a matemática é a ferramenta fundamental desde os tempos primordiais. Desde tempos imemoráveis que o Homem faz uso da matemática para auxílio ao seu quotidiano.
Mas desde quando na evolução humana, começou a nossa espécie a tecer raciocínios abstractos matemáticos? Foi um passo bastante longo, moroso, mas foi um passo deveras importantíssimo na evolução do Homem; muito mais relevante que a invenção do fogo ou da roda. O raciocínio abstracto é o que nos difere das outras espécies, para os crentes é uma dádiva divina que nos diferencia e nos torna superiores, para os incrédulos e laicos é somente um passo evolutivo devido às necessidades dos tempos e talvez mesmo por questões de sobrevivência.
O que é certo é que a Matemática, e posteriormente a Filosofia e as Artes talvez tenham sido as primeiras ferramentas que o Homem concebeu com a sua capacidade de abstracção.
Já na nossa era, os matemáticos tentaram-nos incutir uma Matemática extremamente racional e abstracta, muitas vezes sem quaisquer paralelismos com o mundo terreno. Talvez uma premonição, mas o que é certo é que o número um surgiu para representar um objecto físico.
A matemática surgiu como uma necessidade do Homem no seu trajecto evolutivo, à medida que aumentava o seu volume craniano, foi sendo dotado de raciocínios algébricos. Se o Pensamento foi uma dádiva de Deus ou uma necessidade não o sabemos, mas é este que fez o Homem evoluir, é este que nos diferencia das outras espécies, foi este que nos levou a Marte, que criou a roda, e que nos fornece todas as panóplias quer frívolas, quer de grande utilidade, do nosso mundo moderno.
A Matemática é Viva quando é processada por seres humanos, quando é intuitiva, quando a sentimos útil aos nosso pressupostos. Aliemos então a Matemática, supostamente estritamente pura implicando assim ser apenas racional, à criatividade e sensibilidade humanas. É esta união que torna a Matemática elegante
Sendo elegante,
A Matemática é Viva quando é Humana
Pesquise na Matemática Viva
MatLab - Programa para cálculo Matemático
Álgebra, Equações Diferenciais, Matrizes, Imagem e Visão, Termodinâmica, Fluídos, Cálculo Financeiro, Controlo