Programação Linear
ADSA
António Câmara
Programação linear
• Formulação de modelos de
programação linear
• Resolução gráfica
• Método simplex
• Análises de sensibilidade e
paramétrica
• Problemas na aula
Formulação de modelos
• Problemas de programação linear
– Pretende-se maximizar (lucros) ou minimizar
(custos)
– Variáveis de decisão que assumem valores
maiores do que zero
– Critério para seleccionar os melhores valores
das variáveis de decisão é uma função linear
(função objectivo)
– Regras operacionais que governam o processo
podem ser expressas como um conjunto de
equações ou inequações linears (conjunto de
restrições)
Formulação de modelos
• Formalmente:
MAX (ou MIN):
fobj(X1, X2, …, Xn)
sujeito a:
f1(X1, X2, …, Xn)  b1
…
fk(X1, X2, …, Xn)  bk
…
fm(X1, X2, …, Xn)  bm
Resolução gráfica
• Exemplo:
Z= Min (40 X1 + 36 X2)
s. às r.
X1< 8
X2 < 10
5 X1 + 3 X2 > 45
X1, X2 > 0
Resolução gráfica
• Identificar todos os valores das variáveis
de decisão que satisfazem as restrições. O
conjunto de todas as soluções exequíveis
constitui a região exequível.
• Encontrar a melhor solução exequível
(solução óptima)
• Quando a função objectivo é igualada a um
valor fixo a priori representa uma linha
recta
Resolução gráfica
• Podemos fazer Z= 600 por exemplo e
mudando os valores de Z até atingir
região exequível e definir a solução
óptima (um vértice)
• Neste caso obtemos X1= 8, X2= 5/3
com um valor de Z igual a 380.
Resolução gráfica
X2
15
10
X2=10
(3.10)
Z=600
5
X1=8
5X1+3X2=45
(8,5/3)
5
10
15
x1
Resolução gráfica
• Soluções óptimas alternativas- função
objectivo paralela a uma das
restrições
• Soluções ilimitadas- a região
exequível não é limitada
Método Simplex
• Princípios básicos:
– soluções óptimas podem ser encontradas
nos vértices da região exequível
– método de busca convergente
– critério de paragem
Análises de sensibilidade e
paramétrica
• Análise de sensibilidade- variar
coeficientes da função objectivo de forma
a estabelecer os seus limites sem que se
altere a solução final (cost ranging). Análise
util para fixar os custos unitários de
produtos e actividades
• Análise paramétrica- alterar as constantes
do lado direito das restrições nos valores
da função objectivo
Problemas na aula
• Formule e resolva gráficamente um
dos três problemas seguintes
Problema 1
Admitamos que existe um predador com o ninho no
lugar A e com duas presas potenciais X1 e X2 em
áreas B e C, respectivamente.
Em cada viagem a cada um das áreas captura apenas
uma unidade de cada presa. Os tempos de viagem
de ida e volta às áreas B e C estão estimados em 2
e 3 minutos respectivamente. Na área B, o
predador leva 2 minutos a capturar uma unidade de
X1, enquanto que na área C, leva apenas 1 minuto
para capturar uma unidade de X2.
O valor energético de uma unidade de X1 está
estimado em 25 calorias e o valor energético de
uma unidade de X2 é de 30 calorias.
Problema 1 (cont.)
O objectivo do predador consiste em maximizar o
numero de calorias obtidas por dia, sabendo que
que não pode dispender mais de 120 minutos por
dia em viagens de ida e volta entre o ninho e
qualquer um dos locais B e C, e que não pode gastar
mais do que 80 minutos por dia à procura da presa.
Problema 2
Admitamos que temos uma área de 50 hectares de
terra que vai ser utilizada por uma Câmara
Municipal para construção de um bairro residencial
com dois tipos de habitações (A e B) possíveis. A
densidade prevista para as habitações do tipo A é
de 10 unidades por hectare e do tipo B de 5
unidades por hectare. Cada unidade do tipo A
custa 2000 contos à Camara Municipal; cada
unidade do tipo B custa 6000 contos. O orçamento
da Câmara para a construção deste bairro é de
120.000 contos. As rendas das casas tipo A e tipo
B irão ser de 190 e de 470 contos por ano,
respectivamente.
O problema consiste em determinar a combinação de
casas tipo A e tipo B, por forma a obter a máxima
renda annual para a Câmara.
Problema 3
Em 1000 ha de terra nas margens de um reservatório
pretendem-se desenvolver duas culturas agrícolas.
Cada hectare da cultura 1 perde 0.9 kg/ano de
pesticida para o lago. Cada hectare da cultura 2
perde 0.5 kg/ano. As perdas totais de pesticida,
devido aos seus impactes desfavoráveis no lago, não
podem exceder 632.5 kg/ano.
Os rendimentos provenientes das culturas 1 e 2 são de
300 c/ha e 150c/ha para as culturas 1 e 2
respectivamente. Os custos destas culturas são de
160 c/ha para a cultura 1 e 50 c/ha para a cultura 2.
O problema consiste em determinar a combinação de
culturas que maximiza os lucros do agricultor tendo
em conta a restrição das perdas de pesticida para o
lago.