Formulação de problemas de programação linear e

PROGRAMAÇÃO LINEAR
Formulação de problemas de programação linear e resolução gráfica
A programação linear surge pela primeira vez, nos novos programas de
Matemática A no 11º ano de escolaridade. Contudo também no 12 º ano, na
Matemática B, se podem encontrar questões ligadas a este assunto, embora
com outra formulação.
A programação linear (PL) vai permitir aos alunos aplicar conceitos leccionados
no 10º ano e ampliados no 11º. Os alunos vão ter oportunidade de resolver
problemas, essencialmente da área da Economia, com ferramentas
matemáticas simples.
O que é a PL
A PL é uma técnica da Matemática Aplicada usada no ramo de Investigação
Operacional (IO). A origem da IO como ciência é atribuído à coordenação das
operações militares durante a 2ª Guerra Mundial.
A palavra “programação” refere-se a uma programação de tarefas ou
planificação, não a uma programação no sentido da informática.
A palavra “Linear”, advém do facto de as expressões (condições) que se
utilizam serem lineares.
Objectivo da PL.
O objectivo desta técnica é optimizar problemas de decisão, através da
utilização de modelos, que representem uma realidade. O óptimo na
globalidade é um mínimo ou máximo a ser alcançado, nas condições existentes.
A aplicabilidade da PL é enorme, pode aplicar-se a situações militares, indústria,
agricultura, economia, etc. Contudo, é na área económica que mais se tem
desenvolvido.
Pretende-se que os alunos se familiarizem-se com decisões concretas de
decisão em termos de planeamento, que podem ter a ver com minimizar
consumos, custos ou maximizar lucros.
Um modelo na PL é constituído por:
• Variáveis de decisão (que pretendemos determinar)
• Objectivo (o que se pretende optimizar)
• Restrições (que têm de ser satisfeitas)
Os procedimentos para determinar a solução (de modo a que o objectivo se
cumpra) podem ser variados. O mais antigo é o método Simplex. O método
Simplex consiste de um algoritmo que permite resolver problemas de
Programação Linear.
Netprof
Contudo o método que iremos utilizar baseia-se na representação gráfica.
Foi George Dantzig que, entre 1947 e 1949, desenvolveu os conceitos principais
da PL.
Como curiosidade refira-se que o primeiro problema resolvido por Dantzig –
para desgosto de sua esposa – foi um problema de dieta de custo mínimo. Este
problema necessitava da resolução de um sistema de 9 equações (requisitos de
nutrição) e 77 variáveis de decisão.
Em 1947, George Dantzig e outros cientistas do Departamento da Força Aérea
Americana, apresentaram um método denominado Simplex para a resolução
dos problemas de Programação Linear (PL).
As primeiras e grandes aplicações foram no domínio militar.
.-.-.-.-.-.-.-.-.-.-.-.-.
Exemplo
Uma empresa fabrica dois produtos A e B. Cada um deste produtos requer uma
certa quantidade de tempo na linha de montagem e ainda mais algum para a
sua finalização.
Cada produto do tipo A necessita de 5 horas na linha de montagem e de 2
horas para a finalização. Cada produto de tipo B necessita de 3 horas na linha
de montagem e de 4 horas para a finalização.
Numa semana, a empresa dispõe de 108 horas para a linha de montagem e 60
horas para a finalização. Toda a produção é vendida. O lucro de cada produto é
de 120 € para o produto A e de 210 € para o B.
Quantas unidades, por semana, dos produtos A e B se devem produzir, de
modo a que o lucro seja máximo?
Podemos elaborar uma tabela para melhor esquematizar os dados:
Montagem
A
B
Disponibilidade
Finalização
5
3
108
2
4
60
Lucro
120
210
Seja x o número de unidades que a empresa produz, por semana, do produto A
e y o número de unidades que a empresa produz, por semana, do produto B.
O tempo necessário na linha de montagem para os dois produtos é 5x+3y
horas, no total. Como somente existem 108 horas de disponibilidade, temos a
restrição:
5x+3y ≤ 108
De forma análoga temos a seguinte restrição:
2x+4y ≤ 60
Netprof
Consideremos os lucros:
Cada unidade do produto A origina um lucro de 120 euros assim, com x
unidades produzidas do produto A, obtêm-se 120x euros de lucro.
Cada unidade do produto B origina um lucro de 210 euros assim, com y
unidades de B, obtêm-se 210y euros de lucro.
O lucro semanal é dado por: L= 120x+210y. Pretendemos maximizar o lucro.
Claro que temos que acrescentar duas condições x ≥ 0 e y ≥ 0, pois a
produção é não negativa.
Resumindo:
•
Variáveis de decisão (que pretendemos determinar):
x e y … número de unidades …
•
Objectivo (o que se pretende optimizar)
maximizar o lucro: L= 120x+210y
•
Restrições (que têm de ser satisfeitas)
5x+3y ≤ 108
2x+4y ≤ 60
x≥0
y≥0
Habitualmente escreve-se na seguinte forma:
max. L= 120x+210y
sujeito a 5x+3y ≤ 108
2x+4y ≤ 60
x≥0
y≥0
Resolvamos o problema graficamente (Método Gráfico)
Como x ≥ 0 e y ≥ 0, iremos precisar somente do primeiro quadrante dos eixos
de coordenadas.
As outras duas restrições resolvem-se em ordem a y e considera-se o domínio
plano respectivo.
y ≤- (5/3)x+ 36 e y ≤-0,5x+15
Na figura seguinte estão representados os pontos (área sombreada) que
respeitam as restrições do problema.
Podemos considerar que a solução que procuramos se encontra no polígono
[OABC] .
Netprof
Os pontos que estão nesta região dizem-se pontos admissíveis. E os vértices
O, A, B e C dizem-se vértices da região admissível.
Resta saber quais destes pontos maximizam o lucro.
Ora, L= 120x+210y ⇔ y = -(4/7)x + L/210, representa uma família de
rectas todas com o mesmo declive (-4/7) e cuja ordenada na origem é L/210.
Assim sendo a um maior valor de L/210 corresponde a um maior valor de L e
assim sendo a resolução do nosso problema consiste em encontrar a recta com
declive -4/7 de maior ordenada na origem e que tenha algum contacto com o
polígono.
Netprof
Das várias rectas de declive -4/7 a que tem maior ordenada na origem e tem
pontos de contacto com o domínio, é a que passa no vértice B. Este ponto é a
solução do sistema.
Para encontrar o valor exacto da solução basta resolver o sistema que é
composto pelas rectas que intersectam o ponto B.
5 x + 3 y = 108
 x = 18
⇔

2 x + 4 y = 60
y = 6
Assim para que a empresa, que produz o produtos A e B, tenha o maior lucro
possível, deve produzir semanalmente 18 unidades do produto A e 6 unidades
do produto B.
Podemos saber qual é esse lucro:
L= 120x18+210x6= 3420 euros semanais.
Nota:
Considere o seguinte teorema:
Dado um problema de programação linear, se S for a região admissível e
for limitada então existe um máximo e mínimo em S e cada um destes ocorre
pelo menos num dos vértices da região.
Se S não for limitada, então pode não existir nem máximo nem mínimo.
Mas se existir ele encontra-se num vértice de S.
Este teorema permite-nos conciliar estes resultados com o método gráfico.
Netprof
Assim no exemplo anterior, como a região admissível é limitada então a solução
que procuramos encontra-se num dos vértices da área.
Temos 4 vértices para a solução óptima. Façamos uma tabela para procurar o
valor máximo.
O
A
B
C
x
y
0
23,5
18
0
0
0
6
15
L= 120x+210y
0
2820
3420
3150
Observando o quadro, rapidamente se obtém o valor que pretendíamos
determinar.
Observações:
Ao resolver um problema de PL pode ocorrer uma das seguintes situações:
1. O problema tem uma única solução óptima.
2. O problema tem várias soluções óptimas (uma infinidade).
Netprof
3. O problema não tem um valor óptimo finito.
A região de admissibilidade não é limitada e o valor da função objectivo
cresce indefinidamente no sentido favorável (positivo ou negativo).
4. O problema é impossível, não tem nenhuma solução.
Acontece quando não existem soluções admissíveis, isto é, o conjunto de
soluções admissíveis é vazio.
Netprof