Introdução a Programação Linear

Prof. Dr. André Bergsten Mendes

Introdução
 Após a etapa de modelagem matemática, surge a
necessidade de encontrar respostas (soluções) para
o modelo matemático construído.
 Em se tratando de um modelo com função objetivo
e restrições lineares, além de variáveis reais não-
negativas, teremos um modelo referente a um
Problema de Programação Linear (PPL).
 É necessário um método de solução do modelo
matemático.
Sistemática de Resolução de Problemas de
Pesquisa Operacional

Modelo
Conceitual

Feedback
Modelo
Problema
Matemá-
Real Validação tico

Solução
Bertrand, Fransoo (2002)
Introdução
 Apesar da diversidade de modelos, quanto à função
objetivo (minimizar ou maximizar) e quanto às
restrições (igualdade e desigualdades), bem como
quanto às variáveis, iremos trabalhar com uma
forma padrão, para o qual o algoritmo de solução
poderá ser aplicado:
 Função objetivo: minimização
 Restrições: igualdade
 Variáveis: não-negativas
 2º membro: não-negativo (critério de viabilidade)
Forma Padrão do Problema de
Programação Linear
min z
z = cx
sujeito a : Ax = b
x≥0
Onde:
c = [c1 c2  cn ] Vetor linha
 x1   b1 
x  b 
x =  2  b =  2  A = [aij ] Matriz m x n (n≥m)
 
   
 xn  bm 
Vetores colunas
Soluções Viáveis & Solução Ótima

{ }
F = x ∈ R n:Ax = b, x ≥ 0 Conjunto de soluções viáveis do
problema de programação linear
(“feasible set”)

x * será solução ótima do problema de programação

linear na forma padrão se x* ∈ F e se, para qualquer
x ∈ F ⇒ cx ≥ cx *
Equivalência - Restrições de
desigualdade
 Uma restrição do tipo:
ai1 x1 + ai 2 x2 +  + ain xn ≤ bi
é equivalente às restrições:
 ai1 x1 + ai 2 x2 +  + ain xn + si = bi

si ≥ 0 Variável residual ou de folga

 Analogamente, uma restrição do tipo:

ai1 x1 + ai 2 x2 +  + ain xn ≥ bi
é equivalente às restrições:
 ai1 x1 + ai 2 x2 +  + ain xn − si = bi

si ≥ 0 Variável residual ou de excesso
Equivalência - Função Objetivo
Maximização
 Seja:
Problema P1 : Problema P2 :
max z min w
z = cx w = −cx
sujeito a : Ax = b sujeito a : Ax = b
x ≥0 x ≥0

Seja x * solução ótima do problema P2. Então:

− cx* ≤ −cx para qualquer x ∈ F .
Logo : cx* ≥ cx e x * é solução ótima de P1.
Equivalência - Variáveis irrestritas em
sinal
 Se uma variável de decisão x i for irrestrita em sinal,
então ela pode ser substituída pelo par de variáveis
x i+ e x i−
 ...tal que:
x i = x i+ - x i−
x i+ ≥ 0, x i− ≥ 0
Exemplo
 Colocar na forma padrão o seguinte PPL:

max z = −4 x1 + 6 x 2 + 6 x3 min w = +4 x1+ − 4 x1− − 6 x 2 − 6 x3

5 5
4 x1 + x 2 − 3x3 ≥ −29 − 4 x + 4 x − x 2 + 3x3 + x 4 = 29
+
1
−
1
6 6
− 2x1 + 4 x 2 + 3x3 ≥ 13 − 2x1+ + 2x1− + 4 x 2 + 3x3 − x5 = 13
7 7 + 7 −
+ x1 + 7 x 2 + 6 x3 ≤ 18 + x1 − x1 + 7 x 2 + 6 x3 + x 6 = 18
2 2 2
x2 , x3 ≥ 0 x1+ , x1− , x 2 , , x 6 ≥ 0
Forma Padrão de um Problema de
Programação Linear
min z
n
z = ∑c j x j
j =1
n
sujeito a : ∑a x
j =1
ij j = bi i = 1,2, , m

xj ≥0 j = 1,2, , n
Resolvendo um PPL
 Considere um problema de programação linear com
n variáveis e m equações independentes.
 As seguintes possibilidades poderão acontecer: n =
m, n < m, n > m.
 O caso de interesse em programação linear é
quando n>m.
 Será desenvolvido um procedimento em o sistema
será resolvido para m variáveis dependentes, em
função de n-m variáveis independentes.
Resolvendo um PPL
 Quantas formas há de escolher n-m variáveis
independentes dentre n variáveis?
 n  n
  =  
 n − m  m
100 
 Exemplo: n = 100; m = 40   = 1,4.10 28
 40 
Exemplo
 Resolver o sistema abaixo para x3 , x4 e x5 em
função de x1 e x2 , aplicando o método de eliminação
de Gauss Jordan.
9
min z = −4 x1 + 6 x 2 + 6 x3 − 4 x 4 + x5
2
5
4 x1 + x 2 + 3x3 + 2x 4 + 4 x5 = 29
6
23
− 2x1 + x 2 + 3x3 − 2x 4 + 4 x5 = 11
6
7
− x1 + 7 x 2 + 6 x3 − 4 x 4 + 6 x5 = 18
2
x1 , , x5 ≥ 0
Método de Eliminação de Gauss-Jordan
 A regra geral para eliminação de uma dada variável
xj é:
1. Sendo i a linha em que a variável x j será mantida
com coeficiente 1, definir aij como elemento pivô e
para s ≠ j :
a'is = ais / aij ; b'i = bi / aij
2. Para as demais linhas r ≠ i :
a) Para a coluna j: a'rj = 0
b) Para as demais colunas j ≠ s
ais arj
a'rs = ars −
aij
bi arj
b'r = br −
aij
Exemplo
 O elemento pivô será o coeficiente de x3 na 1ª linha.
Esta variável será eliminada do sistema,
aparecendo com valor 0 nas demais linhas.

x1 x2 x3 x4 x5 − z0
−z −4 6 6 −4 9/2 0
x3 4 5/6 3 2 4 29
x4 − 2 23 / 6 3 − 2 4 11
x5 − 7 / 2 7 6 −4 6 18
Exemplo
 O elemento pivô será o coeficiente de x4 na 2ª linha.
Esta variável será eliminada do sistema,
aparecendo com valor 0 nas demais linhas.

x1 x2 x3 x4 x5 − z0
−z − 12 13 / 3 0 −8 −7/ 2 − 58
x3 4 / 3 5 / 18 1 2/3 4 / 3 29 / 3
x4 −6 3 0 −4 0 − 18
x5 − 23 / 2 16 / 3 0 −8 − 2 − 40
Exemplo
 O elemento pivô será o coeficiente de x5 na 3ª linha.
Esta variável será eliminada do sistema,
aparecendo com valor 0 nas demais linhas.

x1 x2 x3 x4 x5 − z0
−z 0 −5/3 0 0 −7/2 − 22
x3 1 / 3 7/9 1 0 4 / 3 20 / 3
x4 3 / 2 − 3 / 4 0 1 0 9/2
x5 1 / 2 − 2 / 3 0 0 −2 −4
Exemplo
 Após a aplicação de Gauss-Jordan, o sistema
resultante está resolvido em função de x1 e x2.

x1 x2 x3 x4 x5− z0
− z − 7 / 8 −1/ 2 0 0 0 − 15
x3 2/3 1/ 3 1 0 0 4
x4 3/ 2 −3/ 4 0 1 0 9/2
x5 − 1 / 4 1/ 3 0 0 1 2