A Introdução a Management Sciences

...

Conceito de modelos Programação Linear (PL)

Um modelo é uma representação simplificada da realidade, sendo assim é tem extrema importância para o estuda da pesquisa operacional.

Para que um modelo seja criado é necessário identificar o problema e qual a função objetivo, as restrições e tipo de otimização que se deseja.

Abaixo segue um modelo de Programação Linear, juntamente com sua resolução e representação gráfica (Exemplo retirado no site http://www.ufjf.br):

Suponha que para construir uma casa popular por mês uma construtora necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 serventes. A construtora possui um efetivo total de 30 pedreiros e 70 serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda de cada casa popular e de R$5.000,00 na venda de cada apartamento e toda "produção" da construtora é vendida. Qual é a quantidade ótima de casas populares e apartamentos que a construtora deve construir para que está obtenha lucro máximo

Solução Vamos inicialmente representar este problema em forma de tabela:

Asa popular

APART.

Disponibilidade de mão de obra

Pedreiro

2

3

30

Servente

4

8

70

Lucro (em mil R$)

3

5

A Função Objetivo (que deve expressar o lucro total) é dada por:

F(x1, x2) = 3x1 + 5 x2

Onde: x1 é a quantidade de casas populares construídas; x2 é a quantidade de apartamentos construídos. A modelagem matemática da Função Objetivo neste exemplo é muito simples, pois o lucro total vai ser dado pela soma do lucro obtido com casas populares e apartamentos multiplicados por suas respectivas quantidades produzidos (x1 e x2). Por exemplo, se a construtora construir 2 casas populares (x1=2) e 3 apartamentos (x2=3) o lucro total vai ser:

f(x1, x2) = 3 x 2 + 5 x 3 = 21

Como o lucro está dado em milhares de Reais, a construtora terá um lucro de R$21.000,00.

No entanto, será que este lucro de R$21.000,00 é o melhor resultado que está construtora pode obter?

2x1 + 3 x2 ≤ 30 (inequação de injunção de pedreiros) (3)

4 x1 + 8x2 ≤ 70 (inequação de injunção de serventes) (4)

Além das inequações 3 e 4, podemos escrever mais duas inequações de injunção apenas para limitar as quantidades construídas de casas e apartamentos para valores positivos por motivos óbvios (não se pode construir -1 (menos um) apartamento ou -2 (menos duas) casas!). Estas inequações são:

X1 ≥ 0 (5)

X2 ≥ 0 (6)

As inequações 3, 4, 5 e 6 definem um quadrilátero no plano (x1,x2) onde qualquer ponto que esteja "dentro" (contido) deste é uma solução possível (viável) para este problema. Cabe então a nós descobrirmos qual destes pontos é a solução ótima.

[pic 1]

O gráfico da figura 1 mostra, por exemplo, se a construtora construir 15 casas, esta não poderá construir nenhum apartamento, ou seja, x1=15 e x2=0. Esta é uma solução possível, pois satisfaz as 4 inequações de injunção citadas, porém não é a ótima.

As inequações 5 e 6 "forçam" que a solução esteja no primeiro quadrante, a inequação 3 "força" a solução estar sobre ou abaixo da reta 2x1 + 3 x2 = 30 (linha vermelha) e a inequação 4 "força" a solução estar sobre ou abaixo da reta 4 x1 + 8 x2 = 70 (linha verde).

Se fizermos f (x1, x2) constante estaremos determinando as "curvas de nível" da Função Objetivo:

[pic 2]

Fig. 2 - Quadrilátero representando a região de soluções viáveis e curvas de nível.

As curvas de nível estão indicando que os valores da Função Objetivo estão aumentando à medida que estas se aproximam das retas delimitadoras referente às injunções do pedreiro e do servente (linhas vermelhas e verdes). Todos os pontos (x1, x2) que estão sobre uma mesma curva de nível caracterizam um mesmo valor para Função Objetivo (mesmo lucro no caso), porém combinações diferentes de quantidades de casas populares e apartamentos construídos. A figura 3 mostra a Função Objetivo e as suas respectivas curvas de nível projetadas sobre o plano (x1, x2).

[pic 3]Fig. 3 - Quadrilátero representando a região de soluções viáveis, curvas de nível e Função Objetivo.

[pic 4]Fig. 4 - Quadrilátero representando as soluções viáveis, curvas de nível e Função Objetivo de outro ponto de vista.

Neste exemplo a solução ótima será a interseção da "equação da reta do pedreiro" (linha vermelha) e a "equação da reta do servente" (linha verde), ou seja, x1=7.5 e x2=5.0.

Utilização de programação linear no mundo real.

Existem vários momentos no mundo real em que podemos utilizar a Programação Linear na resolução dos problemas, levando em consideração que os mesmos envolvam a idéia de otimização. Alguns exemplos claros seriam: na Nutrição se procura em suprir as nutrientes essências diários com menor custo possível, considerando a capacidade financeira do individuo; Na