• HISTÓRIA DA PROGRAMAÇÃO LINEAR

Tem as suas raízes na antiguidade clássica

1759 – Quesnay (1ª tentativa de modelizar a economia)

1936 – Leontief (2º marco para a economia americana )

1937 – Von Neumann (modelo de programação linear dinâmico)

1939 – Kantorovich (forma rigorosa de um problema de PL)

1947 – Dantzig (forma sistemática da resolução dos problemas de PL)

- “Método Simplex”-

•O que é a Programação Linear?

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.

•Utilização da Programação Linear

Planos de produção e armazenamento

Obtenção de misturas óptimas

Composição de medicamentos

Rentabilização de aeroportos

Optimização do tráfego interno

Programação de rádio ou televisão

Estratégias militares

•A formulação do problema deve consistir em :

•Identificação das variáveis de decisão

•Identificação da função objectivo

•Identificação das restrições

•Verificação dos axiomas de linearidade

•Formulação matemática

•Igualando-a a uma constante obtemos a equação duma recta;

ALGORITMO

P (x, y)

•Uma expressão como ax+by define uma função linear a duas variáveis também chamada «forma linear».

ax + by = 0 y = - (a/b)x

cujo gráfico será

- se a constante for zero, temos uma recta que passa na origem:

•Concretizando os valores a e b (a = 3 , b = 1) e fazendo variar o k obtém-se o gráfico seguinte:

- em qualquer ponto P (x, y) desta recta, a expressão ax + by toma o valor 0;

- diz-se «recta de nível 0» da forma ax + by.

•Igualando a expressão ax + by a uma constante diferente de 0, obtemos outra recta que não passa na origem, mas é paralela à anterior visto que tem o mesmo declive:

ax + by = c by = -ax + c y = - (a/b)x + (c/b)(c/b) = k (constante)

•A recta de equação 3x + y = k diz-se recta de nível k da forma linear 3x + y e em qualquer dos seus pontos a expressão 3x + y toma o valor k.

Num problema de maximização:

- procura-se a recta de maior nível que toque pelo menos num ponto do polígono de soluções.

Num problema de minimização:

- procura-se a recta de menor nível que toque pelo menos num ponto do polígono de soluções.

As restrições do problema originam um polígono – polígono de soluções.

PROBLEMA DE MAXIMIZAÇÃO

Uma empresa de telecomunicações pretende lançar no mercado uma rede móvel. Precisa, para o efeito de definir o tarifário das suas chamadas. A tarifação será efectuada ao minuto e as chamadas vão ser cobradas de acordo com o seu destino, havendo uma tarifa para as chamadas efectuadas para a mesma rede e outra para as chamadas efectuadas para as outras redes.

O instituto responsável pelas comunicações definiu que a soma do preço de um minuto de chamada para a mesma rede com o preço de um minuto de chamada para outra rede não pode ser superior a 0,40 €.

Estudos efectuados em operadoras já existentes mostram que em média cada cliente fala para a mesma rede 100 minutos por mês, e para as outras redes 30 minutos por mês. Cada cliente terá que efectuar um pagamento de 15€ mensais, sendo esse o saldo disponível para efectuar as chamadas, podendo no entanto pagar um valor mais elevado no caso de querer dispor de um saldo maior.

Sobre tarifa cobrada a empresa obtém 70% de lucro nas chamadas efectuadas para a mesma rede e 40% nas chamadas efectuadas para as outras redes.

Como deverá a empresa cobrar as tarifas de forma a obter o maior lucro possível?

Tarifa das chamadas por

minuto

Média mensal dos minutos

de conversação

Percentagem de lucro ( % )

Mesma rede x 100 70

Outras redes y 30 40

RESOLUÇÃO

A função linear a maximizar é o preço total por minuto das chamadas em euros:

0,7x + 0,4y

Restrições: •Tem que se definir os preços para as duas tarifas:

x ≥ 0 e y ≥ 0•A soma por minuto das duas tarifas tem que ser inferior a

0,40€: x + y ≤ 0,40•O dinheiro gasto por mês não pode exceder 15€:

100x + 30y ≤ 15

GÁFICO DA REGIÃO ADMISSÍVEL

Qualquer ponto da região a verde satisfaz as várias restrições, logo é uma solução possível.

 0,7 x + 0,4 y = 0 <=> y = - 1,75 x

(0,07 ; 0,20) é uma solução para a qual o lucro seria

0,7 ×0,07 + 0,4 × 0,20 = 0,129€ por minuto

(0,09 ; 0,18) é mais lucrativo, visto que

0,7 × 0,09 + 0,4 × 0,18 = 0,135€ por minuto.

Qual é então o ponto que dá maior lucro?

Para o calcular, representa-se a recta de nível 0 da função objectivo, que é o “ lucro” a maximizar

GRÁFICO DA RECTA DE NÍVEL ZERO

Procura-se a recta de maior nível (isto é, a paralela mais para a direita) que toque pelo menos num ponto da região admissível.

GRÁFICO DAS RECTAS DE NÍVEL K

GRÁFICO DA SOLUÇÃO ÓPTIMA

Vemos que a solução óptima corresponde ao ponto de intersecção de duas rectas, o qual se obtém resolvendo o sistema:

x + y = 0,40 x = 0,043

Para esta solução o lucro será de

0,7 × 0,043 + 0,4 × 0,357 = 0,173€

100x + 30y = 15 y = 0,357

Problema de Minimização

Uma empresa de refrigerantes pretende produzir um novo sumo. Esse novo sumo será uma mistura de sumo de laranja, sumo de maracujá e água. Cada litro de sumo de laranja contém um grama de carbonatos, três gramas de proteínas e três gramas de vitaminas; cada litro de sumo de maracujá contém três gramas de carbonatos, uma de proteínas e quatro de vitaminas. O preço por litro de sumo de laranja é 1€ e de sumo de maracujá é 0,75€ (o preço da água é desprezável).

Cada litro do novo sumo deverá conter a quantidade mínima de uma grama e meia de carbonatos, uma e meia de proteínas e três de vitaminas.

Qual a forma mais económica da empresa misturar os dois sumos, garantindo os mínimos exigidos?

Tipo de sumo

Quanti-dade de

sumo (litros)

Carbona-tos

Vitaminas Proteínas Preço/ litro( €)

Laranja x 1 3 3 1,00

Maracujá y 3 4 1 0,75

RESOLUÇÃO

A função linear a minimizar é a despesa de fabrico do sumo:

x + 0,75 y

Restrições: •Carbonatos: x + 3y 1,5•Vitaminas : 3x + 4y 3•Proteínas : 3x + y 1,5

Para usar laranja e maracujá: x 0 e y 0

GRÁFICO DA REGIÃO ADMISSÍVEL

GRÁFICO DA SOLUÇÃO ÓPTIMA

Vemos que a solução óptima corresponde ao ponto de intersecção de duas rectas, o qual se obtém resolvendo o sistema:

3x + y = 1,5

3x + 4y = 3

y = 0,5

Para esta solução a despesa por litro de sumo é de:

0,33 + 0,75 × 0,5 = 0,71€

x = 0,33

Casos particulares

1º Caso: solução não limitadaMaximizar z = 2x + 3ySujeito a: 2x + 2y ≥ 6

- x + y ≤ 1 y ≤ 3

x, y ≥ 0

2º Caso: solução óptima com conjunto das soluções admissíveis não limitado.

Maximizar z = -x + 3ySujeito a: 2x + 2y ≥ 6

- x + y≤ 1 y ≤ 3 x, y ≥ 0

3º Caso: valor óptimo da FO finito com variáveis podendo assumir valores arbitrariamente grandesMaximizar z = -2x + 4ySujeito a: x - 2y ≥ -4

- x+ y ≤ 1 x, y ≥ 0

4º Caso: problema impossível

Maximizar z = x + 2ySujeito a: x + y ≥ 3

2 x + y ≤ 2 x, y ≥ 0

MÉTODO SIMPLEX

O Método Simplex é um processo algébrico que permite resolver problemas de programação linear, isto é, determina uma solução óptima finita quando esta existe ou conclui que o problema de optimização é impossível ou ilimitado. Caso a solução óptima exista, o Método Simplex localiza-a após pesquisar um número finito de soluções.

max z = c1 x1 + c2 x2 + … + cn xn

a11 x1 + a12 x2 + ... +a1n xn + xn+1 = b1a21 x1 + a22 x2 + ... + a2n xn + xn+2 = b2am1 x1+ am2 x2+ ... +amn xn + xn+m = bm xj ≥ 0; j = 1, 2, ..., n+m

X1 Xi Xn Xn+1 Xn+m b

Xn+1 a11 a1i a1n 1 0 b1

… … … … … … …

Xn+m am1 ami amn 0 1 bm

z -c1 -cm -cn 0 0 0

Quadro simplex

O problema escrito na forma padrão

PROBLEMA

Uma empresa de telecomunicações pretende lançar no mercado uma rede móvel. Precisa, para o efeito de definir o tarifário das suas chamadas. A tarifação será efectuada ao minuto e as chamadas vão ser cobradas de acordo com o seu destino, havendo uma tarifa para as chamadas efectuadas para a mesma rede, outra para as chamadas efectuadas para as outras redes móveis e rede fixa.

Ao exemplo dado de maximização separa-se a rede fixa das outras redes.

Reestruturando o problema vem:

O instituto responsável pelas comunicações definiu que a soma do preço de um minuto de chamada para a mesma rede com o preço de um minuto de chamada para outras redes móveis não pode ser superior a 0,40€, e que a soma do preço de um minuto de chamada para a mesma rede com o preço de um minuto de chamada para outras redes móveis e com o preço de um minuto de chamadas para a rede fixa não pode ser superior a 0,55€.

Estudos efectuados em operadoras já existentes mostram que em média cada cliente fala para a mesma rede 100 minutos por mês, para as outras redes móveis 30 minutos por mês, e para a rede fixa 20 minutos por mês. Cada cliente terá que efectuar um pagamento de 15€ mensais, sendo esse o saldo disponível para efectuar as chamadas, podendo no entanto pagar um valor mais elevado no caso de querer dispor de um saldo maior.

Agora a função a maximizar é Z=0,7X1+0,4X2+0,45X3X1: chamadas para a mesma rede.X2: chamadas para outras redes móveis.X3: chamadas para a rede fixa.

s.a: X1 + X2 ≤ 0,4X1 + X2 + X3 ≤ 0,55100X1 + 30X2 + 20X3 ≤ 15Xj ≥ 0 , j = 1, 2, 3

Preço/minTempo em média de

conversação % de lucro

Mesma rede X1 100 70

Outras redes móveis X2 30 40

Rede fixa X3 20 45

1º Quadro simplex

X1 X2 X3 X4 X5 X6 b

X4 1 1 1 1 0 0 0,55

X5 100 * 30 20 0 1 0 15

X6 1 1 0 0 0 1 0,4

Z -0,7 -0,4 -0,45 0 0 0 0

A primeira solução básica admissível é X1 = 0, X2 = 0, X3 = 0, X4 = 0,55, X5 = 15, X6 = 0,4 onde X1, X2, X3 são as variáveis não básicas e X4, X5, X6 são as variáveis básicas. Verificamos que esta solução não é óptima, visto que existem custos reduzidos negativos, -0,7; -0,4 e -0,45.

A variável a entrar na base é X1, porque entre as variáveis não básicas com custo reduzido negativo, X1 é a que tem menor valor.

A variável de saída é X5, o min {0,55/1; 15/100; 0,4/1} corresponde à linha definida pela variável básica X5. O pivot neste caso é 100.

1ª actualização do quadro simplex

L1 → L1 – (1/100) L2L2 → (1/100) L2L3 → L3 – (1/100) L2L4 → L4 + (7/1000) L2

X1 X2 X3 X4 X5 X6 b

X4 0 0,7 0,8 * 1 0 0 0,4

X1 1 0,3 0,2 0 0,01 0 0,15

X6 0 0,7 -0,2 0 -0,01 1 0,25

Z 0 -0,19 -0,31 0 0,007 0 0,105

Obtemos uma nova solução básica admissível, X1 = 0,15; X2 = 0; X3 = 0; X4 = 0,4; X5 = 0; X6 = 0,25, esta solução não é óptima porque existem custos reduzidos negativos. A variável a entrar na nova base é X3. A variável de saída é X4, porque o min {0,4/0,8; 0,15/0,2} corresponde à linha definida pela variável X4. O novo pivot é 0,8.

Nova actualização do quadro simplex

L1 → (5/4) L1L2 → L2 – (1/4) L1L3 → L3 + (1/4) L1L4 → L4 + (31/80) L1

X1 X2 X3 X4 X5 X6 b

X3 0 0,875 1 1,25 -0,0125 0 0,5

X1 1 0,125 0 -0,25 0,0125 0 0,05

X6 0 0,875 0 0,25 -0,0125 1 0,35

Z 0 0,08125 0 0,3875 0,003125 0 0,26

A nova solução básica admissível é X1 = 0,05; X2 = 0; X3 = 0,5; X4 = 0; X5 = 0; X6 = 0,35, uma vez que neste último quadro não existem custos reduzidos negativos, esta solução é óptima. Sendo o valor máximo da função objectivo 0,26€.

FIM

Este trabalho foi elaborado por:

Ana Cristina Gomes

Filipe Marques Oliveira

Pedro Nuno Silva

Nuno Fortunato Santos