Programação Matemática. Uma introdução à programação linear - Formulação

Problemas de Optimização

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:

Enviar um comentário