Trabalho elaborado por: João Rui Nº13
José Teixeira Nº14
Introdução
A programação linear é, actualmente, um instrumento indispensável,
tanto na indústria como noutros sectores de actividade, para a planificação
de estratégias que visem melhores resultados, nos mais variados ramos em
que a sua teoria é aplicável.
A necessidade sentida pelas forças armadas dos EUA na distribuição
de alimentos e material bélico às suas unidades, durante a Segunda Guerra
Mundial, levou ao desenvolvimento de técnicas de programação linear.
Nos séculos XVII e XVIII, Newton Leibniz, Bernoulli e,
principalmente, Lagrange deram a sua contribuição com o cálculo
infinitesimal, onde é possível encontrar a determinação de máximos e
mínimos condicionados de certas funções.
As aplicações desta teoria foram-se multiplicando, 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 perceber 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, uma vez
que, há situações bastante complexas, que envolvem centenas de variáveis,
que só podem ser resolvidas com recursos a estes.
Forma linear
Num problema de programação linear com duas variáveis ( X e Y
), pretende maximizar (lucro) ou minimizar (prejuízo) uma forma linear.
Essa maximização ou minimização diz-se de função objectivo, em
que duas variáveis são sujeitas a varias restrições que serão representadas
por inequações em x e y que irão delimitar o nosso resultado.
A função objectivo será representada por:
L=Ax+By
A, B
R \{0}
, em que L representa o maior lucro (ou menor despesa). A e B são
números reais não nulos e x e y as variáveis da função.
Se igualarmos a função objectivo a uma constante, obtemos equação
duma recta e caso a constante seja zero, a recta passa na origem.
Ex: x+3y=0
y=1/3x
-Em qualquer ponto
P(x,y) desta recta a
expressão x+3y toma o valor de zero.
Diz-se “recta de nível zero” da forma x+3y.
A recta x+3y=k diz-se recta de nível k da forma x+3y, em que
x+3y toma o valor de k. Quanto maior for o valor de k mais para a direita a
recta representativa fica.
Ex:
-y=1/3x
-y=1/3x+2
-y=1/3x+4
-y=1/3x+6
Problema 13
Num minimercado com frutas tropicais, vende-se embalagens de 2 ou 4 frutos.
O comerciante tem 20 mangas e 10 papaias para embalar.
As embalagens com 1 papaia e 1 manga são vendidas a 1€ e as embalagens com
3 mangas e 1 papaia são vendidas a 4€
Como deve o comerciante embalar os frutos para obter o maior volume de
receita?
Para que possa obter o melhor rendimento em relação aos dois tipos
de embalagens deve-se então dar inicio ao método de programação linear.
De forma a simplificar a leitura dos dados do problema deve-se
elaborar uma tabela síntese de maneira que os dados fiquem arrumados.
Essa tabela permitirá de forma mais simples chegar à função
objectivo e ás restrições.
Frutos
Volume de
Emb. Quantidade de emb.
Mangas Papaias
receitas
A
x
x
x
x
B
y
4y
3y
y
x+y
x+4y
x+3y
x+y
total
Denominaremos as emb. A por x e as emb. B por y.
Embalagens A
x
Embalagens B
y
Nº máximo de Mangas
20
Nº máximo de Papaias
10
Sendo o objectivo da função objectivo obter o maior lucro possível
esta deverá ter a seguinte forma:
…, ou seja,
L=x+4y
emb. A – 1 euros
(1x)
emb. B – 4 euros
Sendo,
x – preço por cada emb. A
y – preço por cada emb. B
L – Volume de receitas
As restrições serão determinadas por:
- O nº máximo de mangas
- O nº máximo de papaias
- A quantidade de frutos que cada embalagem pode levar
Sendo assim:
- O nº de papaias que as emb. A e B podem levar é 1. O nº máximo
de papaias é 10, não podendo por isso, a soma do nº de papaias das duas
embalagens ultrapassar as 10 papaias, traduzindo numa inequação:
- x+y≤10
…, em que,
x (1x) – nº de papaias nas emb. A
y (1y) – nº de papaias nas emb. B
10 – nº máximo de papaias
- O nº de mangas que a emb. A leva é 1 e o nº de mangas que a
emb. B leva é 3. No total as mangas são 20, não podendo por isso, a soma
do nº de mangas nas duas embalagens ser superior a 20, traduzindo numa
inequação:
- x+3y≤20
…, em que,
x (1x) – nº de mangas nas emb. A
3y – nº de mangas nas emb. B
20 – nº máximo de mangas
- Como o nº de embalagens quer do tipo A quer do tipo B não poder
ser negativo (porque não existem embalagens negativas):
- x≥0
- y≥0
As restrições irão definir uma região que indicará todas as soluções
possíveis, indicando também a solução óptima!
Estas serão inseridas num sistema de inequações:
x+y≤10
x+3y≤20
x≥0
y≥0
y≤-x+10
3y≤-x+20
x≥0
y≥0
y≤-x+10
y≤-1/3x+20/3
x≥0
y≥0
O sistema é uma forma de organizar melhor as restrições que serão
inseridas num gráfico onde estarão indicadas todas as soluções possíveis,
incluindo a solução óptima.
Recta de maior nível
da forma x+4y que toca no
polígono de soluções.
Vemos que a solução
correspondente ao ponto de intercepção das duas rectas, que pode também
ser obtido pelo sistema de equações:
x+y=10
x=10-y
x=10-y
x=10-y
x+3y=20
10-y+3y=20
2y=10
y=5
x=10-5
x=5
y=5
y=5
Em qualquer ponto P (x,y) desta recta de maior nível a expressão
x+4y toma o valor 25; mas só o ponto (5,5) satisfaz as restrições.
Para que a solução seja óptima será:
L=x+4y
L=5+4x5
L=25€
Maquina gráfica
Se conhecermos as restrições, estas podem ser introduzidas na
máquina gráfica e mostrar a área em que se encontram as soluções
possíveis incluindo, a solução óptima.
Neste caso iremos trabalhar com uma máquina gráfica Casio fx9750G.Este tutorial serve para todas as máquinas gráficas Casio pois estas
têm uma maneira de funcionamento semelhante.
1º - Liga-se a máquina gráfica e no menu
principal escolhe-se a opção GRAPH.
2º - Uma vez que as restrições que
queremos inserir são do tipo Y≤ …,
carregamos na tecla F3 (TYPE), seguido
de F6 e F4 (Y≤).
3º - Inserese todas as restrições (x+y≤10; x+3y≤20;
x≥0; y≥0) sendo que na restrição y≥0 tem
que se alterar o sinal para isso é seguir o 2º
passo, mas em vez de carregar na tecla F4
carrega na tecla F3. A única maneira de
introduzir a função x≥0 é limitando o
monitor. Para isso carrega-se na tecla shift e
F3… (passo seguinte)
4º - …onde diz Xmin é onde devemos
introduzir o valor zero para que no monitor
da máquina gráfica não apareçam valores
inferiores a zero no eixo dos X.
Neste menu pode-se configurar os
limites do monitor, caso este não esteja
adaptado ao gráfico deve ser alterado de
modo a que fique.
5º - Depois de estarem configuradas as
dimensões do gráfico carrega-se em exe e
em seguida F6 (draw).
6º - Quando o gráfico já estiver desenhado,
devemos achar o ponto de intercepção das
duas rectas que nos indicará a solução
óptima.
Premir a tecla shift, F5 (G-solv), F5
(ISCT). De seguida escolhe-se as rectas que
se pretende descobrir o ponto de
intercepção. Para saber qual serão as duas
rectas, vai aparecer um quadrado em cima
delas. Escolha as rectas x+y≤10 e x+3y≤20.
7º - Carregue na tecla exe e em baixo dos gráficos
aparecerá o ponto de intercepção das duas rectas, ou seja,
a solução óptima.
Conclusão
Concluímos que a programação linear é uma maneira diferente de
resolver/optimizar problemas através de cálculos matemáticos. Problemas
com que nos deparamos no dia-a-dia, principalmente se tivermos ligações
com a indústria e comércio (embora esta tenha muitas mais aplicações),
pois é onde a optimização dos recursos é mais rentável sendo por isso mais
utilizada nestas áreas. (apenas referimos aqui estas duas aplicações porque
são as aplicações mais frequentes e mais fáceis de encontrar no dia-a-dia).
Com este trabalho pretendemos mostrar de uma forma simples como
se pode utilizar a programação linear numa fase de introdução a mesma,
onde o nível de complexidade dos problemas é baixo.
Numa perspectiva pessoal não adquirimos conhecimentos novos, o
trabalho apenas nos serviu para nos apercebermos de que passar os
conhecimentos que temos para outras pessoas pode ser complicado, porque
precisamos de ser nos a fazer as ligações todas, mesmo quando se trata de
um assunto que á partida parece simples (pelo menos para aqueles que já o
conhecem).