Programação
Linear
Autores:
Gonçalo Sobral Martins
Luís Filipe Gomes
11º β
Índice
Pág.
3»
História da Programação Linear
Introdução à Programação Linear
4»
Áreas/Vertentes em que
a Programação Linear está inserida
5»
Resolução de um problema de Programação Linear
12»
Bibliografia
2|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
História da Programação Linear
O desenvolvimento (ainda que elementar) dos denominados ”problemas
de optimização” iniciou-se a partir do séc. XVII, revelando-se essencial ao
progresso das ciências experimentais.
Apesar de já muito estudados, estes mereceram pouca atenção até meados do
séc. XX.
Os principais desenvolvimentos teóricos da programação linear são
devidos a Kantorovich (que mais tarde, em 1975, viria a ganhar o prémio Nobel
da economia) e a um grande grupo de cientistas americanos.
Os primeiros conceitos da programação linear foram desenvolvidos durante a
segunda guerra mundial, por George Dantzig, para serem aplicados a
programas militares (impulsionado para encontrar formas eficientes de
desenvolver esta metodologia, desde a área da logística até à estratégia). Foi
Dantzig o primeiro a reconhecer que um programa de planeamento poderia ser
expresso por um sistema de inequações lineares, assim como foi o primeiro a
apresentar, na forma de uma expressão matemática explícita, um critério para
selecção do “melhor plano” ao que hoje chamamos “função objectivo”.
O pós-guerra foi considerado, pelo matemático Nemhauser, como uma
“Segunda Renascença”, na medida em que, as ciências experimentais
proporcionaram desafios decisivos à matemática, dando lugar às ciências
organizacionais do planeamento e da gestão que mais contribuíram para o seu
sucesso.
Introdução à Programação Linear
O desenvolvimento tecnológico e o incremento da competitividade faz
com que a tomada de decisões, na maioria das vezes, se alicerce na análise das
diversas situações, tendo como finalidade, por exemplo, obter o lucro máximo
ou então minimizar as despesas e desperdícios.
A complexidade destes processos de optimização, muitas das vezes é
grande, atendendo ao elevado modo de variáveis e às limitações/restrições das
mesmas. Em termos matemáticos, a resolução destes problemas conduz
obrigatoriamente a sistemas de equações e inequações com elevado número
3|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
de variáveis, sendo “imprescindível” o recurso a sistemas informáticos e
processos computacionais (inúmeras vezes).
O desenvolvimento tecnológico faz com que estes processos se tornem
mais rápidos e com mais capacidades, proporcionando um aprofundamento e
ampliação do conhecimento matemático nesta área.
Do ponto de vista escolar, a programação linear consiste em optimizar
(maximizar ou minimizar) uma dada função linear, que se chama “função
objectivo”, definida num dado conjunto convexo, tendo em conta que as
variáveis estão sujeitas a restrições.
Áreas/Vertentes em que a Programação Linear está inserida
As
aplicações
desta
teoria
foram-se
ampliando,
passando
por
investigações em estratégias militares, meios de transporte, planeamento
agrícola, gestão de horários e sistemas de treinos, distribuição de operários
pelos diversos sectores de uma empresa, entre outros.
Assim, não é difícil compreender a vasta aplicação da programação
linear, quer no desenvolvimento, quer na simplificação dos problemas, devido
às técnicas modernas potenciadas pelos computadores.
Conclui-se deste modo, que a programação linear encontra-se
“incorporada” em “tudo” à nossa volta e é um ramo matemático essencial à boa
gestão dos mais variados recursos.
4|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
Resolução de um problema de Programação Linear
Enunciado:
A “Rufos” (fábrica de lacticínios) dispõe de 120 iogurtes com sabor a
amora e 180 com sabor a pêssego. Os iogurtes vendem-se em embalagens de 4
iogurtes de dois tipos diferentes. O “tipo A” contém 2 iogurtes com sabor a
amora e 2 com sabor a pêssego. O “tipo B” contém 1 iogurte com sabor a
amora e 3 com sabor a pêssego. A “Rufos” ganha 0,40€ por cada embalagem
vendida de iogurtes do “tipo A” e ganha 0,30€ por cada embalagem vendida de
iogurtes do “tipo B”.
Calcule o número de embalagens que se terá de vender para obter um lucro
máximo, indicando o valor do referido lucro.
Resolução:
Os passos a seguir na resolução de um problema de Programação Linear são os
seguintes:
1. Descrever as Variáveis
2. Descrever a Função Objectivo
3. Descrever as Restrições (analítica e graficamente)
4. Apresentação da Região Admissível (e dos vértices da mesma)
5. Descrever a Solução Óptima (analítica e graficamente)
6. Conclusão da “Situação-Problema”
5|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
Agora passo a passo:
1. - Descrever as Variáveis
x - nr. de embalagens do “tipo A”
y - nr. de embalagens do “tipo B”
Para facilitar a resolução do problema, convém esquematizar o
mesmo através de uma tabela.
Amora
Pêssego
Ganho
2x
2x
0,40€
Y
3y
0,30€
120
180
Nº de iogurtes
por embalagem
do “tipo A”
Nº de iogurtes
por embalagem
do “tipo B”
Nº máximo de
iogurtes
disponíveis
2. - Descrever a Função Objectivo
O lucro (L) pode ser expresso por uma função de duas variáveis:
L = 0,4x + 0,3y
» Esta é a chamada “função objectivo”!
Como o objectivo do problema proposto é o “cálculo do número de
embalagens que se terá de vender para obter um lucro máximo e indicar o
valor do referido lucro”, é o mesmo que, determinar “x” e “y”, de modo que esta
função atinja o máximo.
6|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
3. - Descrever as Restrições (analítica e graficamente)
O problema possui condições, condições essas que têm a designação de
restrições (chama-se “restrições” às condições impostas pela natureza do
próprio problema e pelos dados do mesmo): o número de embalagens de cada
tipo é sempre um número não negativo (e, neste caso, inteiro), isto é, x≥0 e
y≥0.
Por outro lado, há a existência de mais duas funções (expressas no enunciado):
Sendo estas:
2x+y ≤ 120
2x+y=120
y=-2x+120
⇔
Quando x=0, y=120
Quando x=60, y=0
Restrição referente ao número máximo de iogurtes disponíveis com sabor a Amora:
7|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
E também, 2x+3y ≤ 180
2x+3y=180
y= -2/3x + 60
⇔
Quando x=0, y=60
Quando x=90, y=0
Restrição referente ao número máximo de iogurtes disponíveis com sabor a Pêssego:
Optou-se por mostrar uma restrição de cada vez para uma melhor interpretação do problema!
8|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
4. - Apresentação da Região Admissível (e dos vértices da mesma)
Junção gráfica das funções:
x≥0
y≥0
2x + y ≤ 120
2x + 3y ≤ 180
Uma região poligonal corresponde à representação geométrica das restrições, que se
designa “região admissível” do problema.
Vértices da região admissível:
O (0;0)
B (60;0)
I (45,30) - ponto de intersecção das rectas de equação: y=-2/3x+60 e y=-2x+120
C (0;60)
9|Página
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
5. - Descrever a Solução Óptima (analítica e graficamente)
Para saber qual a melhor condição para um lucro máximo substituem-se as
incógnitas da função objectivo pelas respectivas coordenadas dos “vértices” da
região admissível.
Analiticamente,
Função objectivo:
L = 0,4 x + 0,3y
1. Em relação ao vértice B (60;0):
L= 0,4x60 + 0,3x0
⇔ L= 24€
⇔
2. Em relação ao vértice C (0, 60):
L= 0,4x0 + 0,3x60
⇔ L= 18€
⇔
3. Em relação ao vértice I (45;30);
L= 0,4x45 + 0,3x30
⇔ L= 27€
⇔
Abcissa dos
Ordenada dos
L = 0,4 x + 0,3y
Vértices
Vértices
(Lucro)
B
60
0
24€
C
0
60
18€
I
45
30
27€
Vértices
SOLUÇÃO ÓPTIMA
10 | P á g i n a
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
Agora graficamente,
Função objectivo:
L = 0,4 x + 0,3y
⇔ y = -4/3x +10/3L
Interessa encontrar o maior valor possível de “L” de modo que a recta correspondente
contenha algum dos pontos representados.
Se L>27, verifica-se que as rectas correspondentes não contêm qualquer ponto
assinalado na representação gráfica.
O maior valor possível para “L” é 27 e contém o ponto de coordenadas (45;30).
O problema encontra-se assim resolvido graficamente.
6. - Conclusão da “Situação-Problema”
Após estes cálculos concluímos que a melhor condição para obter um lucro máximo é
a do vértice I, em que se venderá 45 embalagens do “tipo A” e 30 embalagens do “tipo
B” e obter-se-á o lucro máximo de 27€.
11 | P á g i n a
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β
Bibliografia
- Manual Escolar “Espaço 11”
- Manual Escolar “Infinito 11A”
- Manual Escolar “Xequemat 11”
- Livro “Programação Linear Hoje!”
- www.GeoGebra.org
- www.mat.ua.pt
12 | P á g i n a
Gonçalo Sobral Martins e Luís Filipe Gomes - 11º β