Programação Linear

Prévia do material em texto

C A P Í T U L O 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 : 
 nn2211 xcxcxcZ)(MinimizarMaximizar +++= L (1.1) 
 Sujeito a 
 
{ }
{ }
{ } mnmn2m21m1
2n2n222121
1n1n212111
b,,xaxaxa
. . .
b,,xaxaxa
b,,xaxaxa
≥=≤+++
≥=≤+++
≥=≤+++
L
L
L
 (1.2) 
 (1.3) 0x,,x,x n21 ≥L
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 nn2211 xcxcxcZ)(Minimizar +++= L (2.1) 
 Sujeito a 
 
mnmn2m21m1
2n2n222121
1n1n212111
b)(xaxaxa
. . .
b)(xaxaxa
b)(xaxaxa
≥≤+++
≥≤+++
≥≤+++
L
L
L
 (2.2) 
 (2.3) 0x,,x,x n21 ≥L
 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, 
 ⇔ inin2i21i1 bxaxaxa ≥+++ L inin2i21i1 bxaxaxa −≤−−−− L 
restrições do tipo (=) pode ser convertida em 2 do tipo (≤) equivalentes, em conjunto, àquela, 
 ⇔ ⇔ inin2i21i1 bxaxaxa =+++ L 


≥+++
≤+++
inin2i21i1
inin2i21i1
bxaxaxa
bxaxaxa
L
L
 ⇔ 



−≤−−−−
≤+++
inin2i21i1
inin2i21i1
bxaxaxa
bxaxaxa
L
L
variável livre (sem restrição de sinal) pode ser substituída pela diferença de variáveis não 
negativas1 ( x ), formulando-se de novo o problema em termos 
destas variáveis. 
0x,xcomxx ''j'j''j'jj ≥= −
 
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) 
 x1 ≤ 160 (mercado) 
 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) 
 sujeito a 20 x1 + 50 x2 ≥ 200 (hidratos de carbono) 
 quantidade a fornecer
diariamente 
 quantidade mínima 
necessária por dia 
 
 50 x1 + 10 x2 ≥ 150 (vitaminas) 
 30 x1 + 30 x2 ≥ 210 (proteínas) 
 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 camelosa 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 (capacidade) 
 3 x1 + 4 x2 ≤ 60 (feno) 
 100 x1 + 80 x2 ≤ 1 600 (água) 
 x1, x2 ≥ 0 (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 Z nn2211 xcxcxc +++ L= (3.1) 
 
Sujeito a
 
mnmn2m21m1
2n2n222121
1n1n212111
bxaxaxa
bxaxaxa
bxaxaxa
=+++
=+++
=+++
L
L
L
...
 (3.2) 
 (3.3) 0x,,x,x n21 ≥L
Introdução à Programação Linear 
22 Terminologia associada às soluções do PL 
A redução à forma padrão do problema de PL 
 Maximizar Z nn2211 xcxcxc +++= L 
 
Sujeito a
 
2n2n222121
1n1n212111
bxaxaxa
bxaxaxa
≤+++
≤+++
L
L
 
 . . . 
 mnmn2m21m1 bxaxaxa ≤+++ L 
 0x,,x,x n21 ≥L
conduz ao seguinte problema equivalente : 
 Maximizar Z mn2n1nnn2211 x0x0x0xcxcxc +++ +++++++= LL 
 
Sujeito a
 
22nn2n222121
11nn1n212111
bxxaxaxa
bxxaxaxa
=++++
=++++
+
+
L
L
 
 . . . 
 mmnnmn2m21m1 bxxaxaxa =++++ +L 
 0x,,x,x,x,,x,x mn2n1nn21 ≥+++ LL
 em que, 
  são as variáveis de decisão (principais) n21 x,,x,x L
  são as variáveis folga (“slack”) mn2n1n x,,x,x +++ L
 Também é frequente o modelo de PL ser apresentado em forma matricial : 
 Maximizar Z = C X 
 Sujeito a A X = 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 
O conjunto convexo (politopo ou poliedro) X, tem um nº finitode vértices v(X) ( ≤ . nmC )
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 
	Introdução à Programação Linear
	Definição
	Formalização e modelação matemática de problem
	Formalização e modelação de alguns problemas d�
	Representação e resolução gráfica de problemas
	Forma padrão ou “standard” de um problema de PL
	Terminologia associada às soluções do PL
	Tipos de soluções
	Análise convexa
	Propriedades fundamentais