CAPÍTULO 2
Introdução à Programação Linear
1. Definição
Um problema de PL consiste em determinar valores não negativos para as variáveis de decisão,
de forma que satisfaçam as restrições impostas e que optimizem (minimizem ou maximizem) uma
função (real) linear dessas variáveis.
2. Formalização e modelação matemática de problemas de PL
Existem 2 formas diferentes de apresentar o modelo, conforme se pretenda maximizar ou
minimizar, que são as seguintes :
Maximizar (Minimizar)
Z = c 1 x 1 + c 2 x 2 +L+ c n x n
(1.1)
Sujeito a
a 11 x 1 + a 12 x 2 +L+ a 1n x n
{ ≤, =, ≥ }
b1
a 21 x 1 + a 22 x 2 +L+ a 2n x n
{ ≤, =, ≥ }
b2
(1.2)
...
a m1 x 1 + a m2 x 2 +L+ a mn x n
{ ≤, =, ≥ }
bm
x 1 , x 2 , L, x n ≥ 0
(1.3)
onde,
aij (i = 1, ...,m; j = 1, ...,n) → coeficientes técnicos ou tecnológicos,
b1, b2, ..., bm → termos independentes (constantes de restrição ou segundos membros),
c1 , c2, . . . , cn → coeficientes da função objectivo (coeficientes de custo),
14
Formalização e modelação matemática de problemas de PL
x1 , x2, . . . , xn → variáveis de decisão (principais ou controláveis),
(1.1) → função objectivo (económica ou critério),
(1.2) → restrições (restrições funcionais), em que apenas se verifica uma das relações,
(1.3) → condições de não negatividade.
No entanto, o modelo é frequentemente apresentado nas seguintes formas típicas :
Maximizar (Minimizar)
Z = c 1 x 1 + c 2 x 2 +L+ c n x n
(2.1)
Sujeito a
a 11 x 1 + a 12 x 2 +L+ a 1n x n ≤ ( ≥ ) b 1
a 21 x 1 + a 22 x 2 +L+ a 2n x n ≤ ( ≥ ) b 2
(2.2)
...
a m1 x 1 + a m2 x 2 +L+ a mn x n ≤ ( ≥ ) b m
x 1 , x 2 ,L, x n ≥ 0
(2.3)
Estas duas formas são tão gerais quanto (1.1), (1.2) e (1.3), pois, mediante operações
convenientes, é sempre possível dar a qualquer problema uma daquelas formas. Com efeito, qualquer
problema pode ser reduzido a uma destas formas, da seguinte maneira :
qualquer problema de minimização pode converter-se num de maximização, pois
Minimizar Z = − Maximizar (− Z)
restrições do tipo (≥) pode ser convertida em restrições do tipo (≤), mediante a multiplicação por (1) de ambos os membros,
a i1 x 1 + a i2 x 2 + L + a in x n ≥ b i ⇔ − a i1 x 1 − a i2 x 2 − L − a in x n ≤ − b i
restrições do tipo (=) pode ser convertida em 2 do tipo (≤) equivalentes, em conjunto, àquela,
a i1 x 1 + a i2 x 2 + L + a in x n = b i
⇔
a i1 x 1 + a i2 x 2 + L + a in x n ≤ b i

a i1 x 1 + a i2 x 2 + L + a in x n ≥ b i
⇔
a i1 x 1 + a i2 x 2 + L + a in x n ≤ b i

− a i1 x 1 − a i2 x 2 − L − a in x n ≤ − b i
⇔
variável livre (sem restrição de sinal) pode ser substituída pela diferença de variáveis não
negativas1 ( x j = x 'j − x 'j'
com x 'j , x 'j' ≥ 0 ), formulando-se de novo o problema em termos
destas variáveis.
1
Qualquer número pode ser obtido como a diferença de dois números não negativos.
Introdução à Programação Linear
Formalização e modelação de alguns problemas de PL
15
3. Formalização e modelação de alguns problemas de PL
Problema 1 :
Uma empresa de mobiliário de escritório pretende lançar um modelo de secretárias e estantes.
Pensa-se que o mercado pode absorver toda a produção de estantes, mas aconselha-se que a
produção mensal de secretárias não ultrapasse as 160 unidades.
Ambos os produtos são processados nas unidades de estampagem (UE) e de montagem e
acabamento (UMA).
A disponibilidade mensal em cada uma destas unidades é de 720 horas−máquina (h−m) na UE
e 880 horas−homem (h−h) na UMA.
Cada secretária necessita de 2h−m na UE e de 4 h−h na UMA.
Cada estante necessita de 4 h−m na UE e de 4 h−h na UMA.
As margens de lucro unitárias estimadas são de 6 contos para as secretárias e de 3 contos para
as estantes.
Qual o plano de produção mensal para as secretárias e estantes que maximiza a margem de
lucro.
Formalização do problema :
Variáveis de decisão :
• quantidade de secretárias a produzir por mês (x1)
• quantidade de estantes a produzir por mês (x2)
Função objectivo :
• maximizar a margem bruta total por mês (Z = 6 x1 + 3 x2)
Restrições :
• disponibilidade mensal na unidade de estampagem
• disponibilidade mensal na unidade de montagem e acabamento
• produção mensal de secretárias
Secretárias
Estantes
Capacidade disponível
UE
2
4
720
UMA
4
4
880
Mercado
1
0
160
Lucro
6
3
Introdução à Programação Linear
16
Formalização e modelação de alguns problemas de PL
Modelação matemática :
Relativamente ao Departamento de Estampagem, sabe-se que :
• cada secretária necessita de 2 h−m, pelo que o nº total de h−m necessárias à produção de
x1 secretárias é de 2 x1;
• cada estante necessita de 4 h−m, pelo que o nº total de h−m necessárias à produção de x2
secretárias é de 4 x2;
• a disponibilidade mensal é de 720 h−m.
Logo, a restrição relativa a este Departamento é :
Total de h−m gasto nas
secretárias
+
Total de h−m gasto nas
estantes
≤
Disponibilidade
em h−m
que se traduz algebricamente na desigualdade linear : 2 x1 + 4 x2 ≤ 720
Da mesma forma se determinam as restantes restrições.
Resumindo, o problema consiste em determinar x1 e x2 por forma a
Maximizar
Z = 6 x1 + 3 x2
(lucro mensal em contos)
sujeito a
2 x1
+
4 x2
≤
720
(UE)
4 x1
+
4 x2
≤
880
(UMA)
≤
160
(mercado)
x1
x1, x2 ≥ 0
(não negatividade)
Problema 2 :
Um criador de porcos, pretende determinar a quantidade de cada tipo de ração a dar
diariamente a cada animal, para conseguir uma dada qualidade nutritiva a custo mínimo.
Os dados relativos ao custo de cada tipo de ração, às quantidades mínimas diárias de
ingredientes nutritivos básicos a fornecer a cada animal, bem como às quantidades destes existentes
em cada tipo de ração (g/kg) constam do quadro em baixo.
Granulado
(gr/Kg)
Farinha
(gr/Kg)
Quantidade mínima
requerida
Hidratos de carbono
20
50
200
Vitaminas
50
10
150
Proteínas
30
30
210
Custo (esc./Kg)
10
5
Introdução à Programação Linear
Formalização e modelação de alguns problemas de PL
17
Formalização do problema :
Variáveis de decisão :
• quantidade (Kg) de granulado existente na ração diária (x1)
• quantidade (Kg) de farinha existente na ração diária (x2)
Função objectivo :
• minimizar o custo da ração diária (Z = 10 x1 + 5 x2)
Restrições :
• quantidade mínima diária de hidratos de carbono
• quantidade mínima diária de vitaminas
• quantidade mínima diária de proteínas
Modelação matemática :
Pretende-se determinar x1 e x2 de modo a
minimizar
Z = 10 x1 + 5 x2
(custo diário)
20 x1 + 50 x2
quantidade a fornecer
diariamente
≥
50 x1 + 10 x2
≥
150
(vitaminas)
30 x1 + 30 x2
≥
210
(proteínas)
sujeito a
200
(hidratos de carbono)
quantidade mínima
necessária por dia
x1, x2 ≥ 0
(não negatividade)
Problema 3 :
As Caravanas Marco Polo L.da. usam dromedários (1 bossa) e camelos (2 bossas) para
transportar figos secos de Bagdade para Meca. Um camelo pode levar no máximo 1000 lbs e um
dromedário 500 lbs. Durante a viagem um camelo consome 3 fardos de feno e 100 galões de água. Um
dromedário consome 4 fardos de feno e 80 galões de água. As estações da Marco Polo, situadas em
vários oásis ao longo do caminho, apenas têm disponíveis 1600 galões de água e 60 fardos de feno.
Os camelos e os dromedários são alugados a um pastor perto de Bagdade a 11 pazuzas por
camelo e 5 pazuzas por dromedário. Se as Caravanas Marco Polo L.da. tiverem uma carga de 10000
lbs de figos para transportar, quantos camelos e dromedários devem ser usados para minimizar a
renda a pagar ao pastor ?
Formalização do problema :
Variáveis de decisão :
• quantidade de camelos a usar (x1)
• quantidade de dromedários a usar (x2)
Função objectivo :
Introdução à Programação Linear
18
Representação e resolução gráfica de problemas de PL
• minimizar a renda a pagar ao pastor (Z = 11 x1 + 5 x2)
Restrições :
• capacidade da caravana
• disponibilidade de feno
• disponibilidade de água
Camelos
Dromedários
Capacidade disponível
Capacidade
1 000
500
10 000
Feno
3
4
60
Água
100
80
1 600
Renda a pagar
11
5
Modelação matemática :
Pretende-se determinar x1 e x2 de modo a
Minimizar
Z = 11 x1 + 5 x2
(renda)
sujeito a
1 000 x1
+
500 x2
≥
10 000
3 x1
+
4 x2
≤
60
(feno)
100 x1
+
80 x2
≤
1 600
(água)
x1, x2 ≥ 0
(capacidade)
(não negatividade)
4. Representação e resolução gráfica de problemas de PL
A representação gráfica de problemas de PL só é possível, quando os problemas têm 2 ou 3
variáveis de decisão. No entanto, aqui, apenas serão analisados os problemas com 2 variáveis, os
quais são representados através de um gráfico a 2D.
Para representar graficamente um problema de PL, começa-se por construir um sistema de
eixos cartesianos x1 e x2.
O passo seguinte consiste em identificar os valores de x1 e x2 que satisfaçam todas as restrições
 construção do espaço das soluções.
Por último, procuram-se os pontos situados nesta região que maximizem (minimizem) o valor
de Z. Esta fase vai proceder-se por tentativas (mais adiante será enunciada uma regra prática que
permite resolver esta questão de uma forma quase automática).
O processo baseia-se na representação gráfica da recta Z = F (x1, x2) = constante para um
conjunto de valores. A ideia é traçar rectas Z = constante, até que contenha pelo menos um ponto da
Introdução à Programação Linear
Representação e resolução gráfica de problemas de PL
19
região admissível e esteja o mais distante possível da recta Z = 0 (maximizar) ou o mais perto possível
(minimizar).
Resolução gráfica do Problema 1 :
Solução óptima do problema : xopt = (160, 60) ⇔ Zopt = 1140.
Introdução à Programação Linear
20
Representação e resolução gráfica de problemas de PL
Resolução gráfica do Problema 2 :
Solução óptima do problema : xopt = (2, 5) ⇔ Zopt = 45
Introdução à Programação Linear
Forma padrão ou “standard” de um problema de PL
21
Resolução gráfica do Problema 3 :
Solução óptima do problema : xopt = (4, 12) ⇔ Zopt = 104.
5. Forma padrão ou “standard” de um problema de PL
Um PL diz-se estar na forma padrão, se todas as restrições propriamente ditas (não incluindo as
de não negatividade) são equações. Todo o PL pode escrever-se na sua forma padrão, por introdução
de variáveis folga (“slack”) nas restrições que são inequações, da seguinte forma :
f(x) ≤ b
⇒
f(x) + x = b, x ≥ 0 (x variável “slack”)
f(x) ≥ b
⇒
f(x) − x = b, x ≥ 0 (x variável “slack”)
A forma padrão apresenta a seguinte estrutura :
Maximizar
Sujeito a
Z = c 1 x 1 + c 2 x 2 +L+ c n x n
(3.1)
a 11 x 1 + a 12 x 2 + L + a 1n x n
= b1
a 21 x 1 + a 22 x 2 + L + a 2n x n
= b2
...
(3.2)
a m1 x 1 + a m2 x 2 + L + a mn x n = b m
x1 , x2 , L , xn ≥ 0
Introdução à Programação Linear
(3.3)
22
Terminologia associada às soluções do PL
A redução à forma padrão do problema de PL
Maximizar
Sujeito a
Z = c1x1 + c2 x 2 + L + cn xn
a 11 x 1 + a 12 x 2 + L + a 1n x n ≤ b 1
a 21 x 1 + a 22 x 2 + L + a 2n x n ≤ b 2
...
a m1 x 1 + a m2 x 2 + L + a mn x n ≤ b m
x 1 , x 2 , L, x n ≥ 0
conduz ao seguinte problema equivalente :
Maximizar
Sujeito a
Z = c 1 x 1 + c 2 x 2 + L + c n x n + 0 x n +1 + 0 x n + 2 + L + 0 x n +m
a 11 x 1 + a 12 x 2 + L + a 1n x n + x n +1
a 21 x 1 + a 22 x 2 + L + a 2n x n
= b1
+ x n+2
= b2
...
a m1 x 1 + a m2 x 2 + L + a mn x n
+ x n +m = b m
x 1 , x 2 , L , x n , x n +1 , x n + 2 , L , x n +m ≥ 0
em que,
x 1 , x 2 , L , x n  são as variáveis de decisão (principais)
x n + 1 , x n + 2 , L , x n +m  são as variáveis folga (“slack”)
Também é frequente o modelo de PL ser apresentado em forma matricial :
Maximizar
Z=CX
Sujeito a
AX=b
X≥0
em que,
C = [ c1 c2 . . . cn ] é a matriz dos custos
A = [ aij ] (m×n) é a matriz das restrições
X = [ x1 x2 . . . xn ]T é a matriz das variáveis
b = [ b1 b2 . . . bm ]T é a matriz dos termos independentes
0 = [ 0 0 . . . 0 ]T (1×m) é a matriz nula
6. Terminologia associada às soluções do PL
Solução  qualquer conjunto de valores assumidos pelas variáveis de decisão satisfazendo as
restrições funcionais (3.2).
Solução admissível  solução que satisfaz as condições de não negatividade (3.3).
Região admissível  é o conjunto de todas as soluções admissíveis.
Introdução à Programação Linear
Tipos de soluções
23
Solução óptima  é a solução admissível que tem o melhor valor da função objectivo.
Solução não limitada  não existe um valor máximo (mínimo) para a função objectivo.
7. Tipos de soluções
óptima única : problema tem apenas uma solução (Problemas 1, 2 e 3).
óptimas alternativas : o valor óptimo da função objectivo pode ser obtido através de
infinitas combinações de recursos.
não limitada : não existe um valor máximo finito para a função objectivo (Z → ∞).
Introdução à Programação Linear
24
Tipos de soluções
óptima (com região admissível não limitada) : facto do conjunto das soluções admissíveis ser não
limitado, não implica necessariamente que a solução seja não limitada (Z → ∞).
valor óptimo da FO finito (variáveis podem assumir valores arbitrariamente grandes) : conjunto
das soluções é não limitado e o valor óptimo de Z é finito, com as variáveis de decisão a
poderem assumir valores arbitrariamente grandes na solução óptima.
Introdução à Programação Linear
Análise convexa
25
inexistente (problema impossível) : esta situação, normalmente deriva de erros de formalização.
Isto pode acontece por não existirem valores das variáveis a satisfazerem as restrições do
problema ou as condições de não negatividade, ou ambas simultaneamente.
8. Análise convexa
Chama-se combinação linear convexa de um nº finito de pontos x1, ..., xn ao ponto
λ1 x1 + λ2 x2 + . . . + λn xn
com os escalares λi ≥ 0 e λ1 + λ2 + . . . + λn = 1.
O segmento de recta que une 2 pontos do espaço, é o conjunto de todas as combinações
convexas desses pontos.
Conjunto convexo X, é um conjunto tal que o segmento de recta que une dois quaisquer dos
seus pontos, está contido no conjunto. Por outras palavras, X é um conjunto convexo, se quaisquer
que sejam x1 e x2, ∈ X e 0 ≤ λ ≤ 1, se tem
λ x1 + (1 - λ) x2 ∈ X
Um conjunto convexo é fechado se compreende a sua fronteira.
Conjunto convexo
Conjunto não convexo
Resultado : A intersecção finita de conjuntos convexos é um conjunto convexo.
Introdução à Programação Linear
26
Propriedades fundamentais
Ponto extremo de um conjunto convexo X, é um ponto que não pertence ao segmento de recta a
unir dois outros pontos quaisquer de X. Por outras palavras, um ponto extremo de X não pode ser
obtido por combinação linear convexa positiva de pontos de X.
Algebricamente : x = λ x1 + (1-λ) x2 , com λ ∈ ]0, 1[ e x1, x2 ∈ X ⇒ x = x1 = x2
Um conjunto convexo da forma
X = { x : A x = b, x ≥ 0 } (X é o conjunto de soluções admissíveis do PL)
chama-se um politopo convexo.
Um politopo convexo limitado, chama-se poliedro convexo. Em R2, um poliedro convexo
chama-se polígono convexo.
Chama-se vértice (ou ponto extremo) dum politopo ou poliedro convexo X, a um qualquer
ponto x ∈ X que não possa ser expresso como combinação linear de outros pontos y ∈ X (y ≠ x).
9. Propriedades fundamentais
n
O conjunto convexo (politopo ou poliedro) X, tem um nº finito de vértices v(X) ( ≤ C m
).
Todo o ponto dum poliedro convexo X ⊂ Rn é combinação convexa dos vértices de X.
O conjunto das soluções admissíveis, X, de um problema de PL é um conjunto convexo fechado
(compreende a sua fronteira).
Optimalidade num vértice :
• O óptimo duma função linear num poliedro convexo X ⊂ Rn é obtido em, pelo menos, um
vértice de X;
• Se ele for obtido em mais que um vértice, então será obtido em todo o ponto que é uma
combinação linear convexa desses vértices.
• Se X é um politopo convexo, então existe pelo menos um ponto extremo de X que
optimiza a função objectivo.
Introdução à Programação Linear