Análise e Síntese de Algoritmos
Programação Linear
CLRS, Cap. 29
Contexto
• Algoritmos em Grafos (CLRS, Cap. 22-26)
– ...
– Fluxos máximos em grafos (CLRS, Cap. 26)
•
•
•
•
•
•
•
Programação Linear (CLRS, Cap. 29)
Fluxos de Custo Mínimo (S, Cap. 22)
Programação Dinâmica (CLRS, Cap. 15)
Algoritmos Greedy (CLRS, Cap. 16)
Emparelhamento de Caracteres (CLRS, Cap. 32)
Completude NP (CLRS, Cap. 34)
Algoritmos de Aproximação (CLRS, Cap. 35)
2003/2004
Análise e Síntese de Algoritmos
2
Resumo
•
•
•
•
•
•
Motivação
Formas Standard e Slack
Formulação de Problemas
O Algoritmo Simplex
Soluções Exequíveis Iniciais
Dualidade
2003/2004
Análise e Síntese de Algoritmos
3
Exemplo
Urbanos Suburbanos Campo
Estradas
-2
5
3
Liberalização droga
8
2
-5
Subsídios agricultura
0
0
10
Imposto sobre gasolina
10
0
-2
• Queremos ganhar pelo menos 50% dos votos (100.000
urbanos, 200.000 suburbanos e 50.000 rurais)
• Entrada representa o número de votos (em milhares)
ganhos por cada 1000 Euros gastos em campanhas
2003/2004
Análise e Síntese de Algoritmos
4
Exemplo
Urbanos Suburbanos Campo
Estradas
-2
5
3
Liberalização droga
8
2
-5
Subsídios agricultura
0
0
10
Imposto sobre gasolina
10
0
-2
x1 = estradas; x2 = droga; x3 = subsídios; x4 = Imposto
minimizar

4
x
i 1 i
sujeito a  2 x1  8 x2  0 x3  10x4
2003/2004
 50
5 x1  2 x2  0 x3  0 x4
 100
3x1  5 x2  10x3  2 x4
x1 , x2 , x3 , x4
 25
 0
Análise e Síntese de Algoritmos
5
Formulação Geral
• Programação Linear (LP):
– Optimizar (minimizar ou maximizar) função linear sujeita a
conjunto de restrições lineares
– Função linear:
n
f x1 , x2 ,, x n    c j x j
j 1
– Restrições lineares:

n
g j x1 , x2 ,, x n    aij x j  bi
j 1
2003/2004
Análise e Síntese de Algoritmos

6
Perspectiva sobre LP
• Qualquer solução do conjunto de restrições designa-se
por solução exequível
– Cada solução exequível corresponde a um valor da função
objectivo (ou de custo)
• O conjunto de soluções exequíveis é designado por
região exequível
• A região exequível é um conjunto convexo no espaço ndimensional
• Conjunto convexo S: qualquer ponto de segmento que liga
dois pontos em S está também em S
• S é designado por simplex
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
7
Perspectiva sobre LP
• Utilização de representações canónicas:
– Formas standard e slack
• Algoritmos:
– Algoritmo Simplex
• Exponencial no pior caso; eficiente na prática e muito
utilizado
– Algoritmo da Elipsóide
• Polinomial; normalmente ineficiente
– Métodos de Ponto Interior
• Polinomiais; eficientes na prática, competitivos com Simplex
2003/2004
Análise e Síntese de Algoritmos
8
Forma Standard
função objectivo
maximizar
sujeit o a
restrições


n
j 1
n
j 1
cjxj
aij x j  bi
xj  0
i  1,2,  , m
j  1,2,  , n
• Todos os valores cj, aij, bi são valores reais
• Representação matricial:
maximizar c T x
sujeit o a Ax  b
x0
– Em que A = (aij), b = (bi) e c = (cj) e x = (xj)
2003/2004
Análise e Síntese de Algoritmos
9
Forma Standard
• Noções a reter:
–
–
–
–
–
Solução exequível
Solução não exequível
Valor da função objectivo: valor objectivo
Valor máximo/mínimo: valor objectivo óptimo
LP sem soluções exequíveis diz-se não exequível; caso
contrário diz-se exequível
– LP exequível, mas sem solução óptima, diz-se não limitado
2003/2004
Análise e Síntese de Algoritmos
10
Conversão para Forma Standard
• Problemas:
–
–
–
–
2003/2004
Minimização em vez de maximização
Variáveis sem restrição de serem não negativas
Restrições com igualdade
Restricões com 
Análise e Síntese de Algoritmos
11
Conversão para Forma Standard
• Soluções:
– Minimização vs. Maximização:
• Multiplicar coeficientes por -1
– Variáveis sem restrição de serem não negativas:
• Substituir xi por duas variáveis xi1 e por xi2, e multiplicar
coeficientes de xi2 por –1
– Restrições com igualdade:
• Introduzir duas restrições, uma com  e outra com 
– Restrições com  :
• Multiplicar restrição por –1
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
12
Conversão para Forma Slack
• Objectivo é trabalhar apenas com igualdades
– Todas as restrições, excepto as restrições das variáveis
serem não negativas, são igualdades
• Para cada restrição introduzir uma nova variável s
s  bi   j 1 aij x j
n
s0
– s: variável de slack
• Conversão de forma standard para forma slack:
xn i  bi   j 1 aij x j
xn  i  0
n
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
13
Forma Slack
xni  bi   j 1 aij x j
n
• Nas expressões:
– Variáveis expressas em função de outras variáveis
designam-se por variáveis básicas
– As variáveis que definem as variáveis básicas designam-se
por variáveis não-básicas
• Definir:
z   j 1 c j x j
n
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
14
Forma Slack
• N:
– Conjunto de índices das variáveis não básicas, |N| = n
• B:
– Conjunto de índices das variáveis básicas, |B| = m
• Obs:
N  B  1,2,, n  m
• Forma slack descrita por: (N, B, A, b, c, v)
– v: constante na função objectivo
2003/2004
Análise e Síntese de Algoritmos
15
Formulação de Problemas de LP
• Fluxos de Custo Mínimo:
minimizar z  x  
c x

 
i,j E
sujeit o a :

  
j: i , j E 
xij 
ij ij
x

   
j: j ,i E
ji
 bi  i  V
0  xij  uij
i, j   E
– Caminhos Mais Curtos
– Fluxo Máximo
– ...
2003/2004
Análise e Síntese de Algoritmos
16
Outras Formulações
• Caminhos Mais Curtos
– Entre s e t:
maximizar d t 
sujeito a d v  d u   wu, v 
u, v  E
d s   0
• Fluxo Máximo:
 f s, v 
maximizar
vV
sujeito a
f u, v   cu, v 
f u, v    f v, u 
 f u, v   0
u , v V
u , v V
u V  s, t
vV
2003/2004
Análise e Síntese de Algoritmos
17
O Algoritmo Simplex
• Definições
• Pivots
– Exemplo
• O algoritmo simplex
• Soluções exequíveis iniciais
• Dualidade
2003/2004
Análise e Síntese de Algoritmos
18
Forma Slack
xni  bi   j 1 aij x j
n
• Nas expressões:
– Variáveis expressas em função de outras variáveis
designam-se por variáveis básicas
– As variáveis que definem as variáveis básicas designam-se
por variáveis não-básicas
• Definir:
z   j 1 c j x j
n
• Forma slack descrita por: (N, B, A, b, c, v)
– N: varáveis não básicas; |N| = n
– B: variáveis básicas; |B| = m
– v: constante na função objectivo
2003/2004
Análise e Síntese de Algoritmos
19
Pivots
• Exemplo
• Escolher variável não básica xe para passar a básica
– Variável de entrada
• Escolher variável básica xl para passar a não básica
– Variável de saída
• Calcular nova forma slack do problema
– N '  N  xe   xl 
– B'  B  xl   xe 
–  N ' , B' , A, b, c, v 
2003/2004
Análise e Síntese de Algoritmos
20
O Algoritmo Simplex
• Calcular forma slack inicial
– Para a qual solução básica inicial é exequível
– Caso contrário reporta problema não exequível (retorna
“unfeasible”) e termina
• Enquanto existir ce > 0 (i.e. valor de z pode aumentar)
– xe define variável de entrada (i.e. nova variável básica)
– Seleccionar xl
• xl corresponde a linha i que minimiza bi / aie, para aie > 0
• Se aie < 0 para todo o i, retornar ‘ unbounded’
– Aplicar pivoting com (N, B, A, b, c, v, l, e)
2003/2004
Análise e Síntese de Algoritmos
21
O Algoritmo Simplex
• Para valores i em B
– Atribuir valor bi
– Caso contrário atribuir valor 0
• i.e. variáveis em N
• Exemplos
2003/2004
Análise e Síntese de Algoritmos
22
Solução Exequível Inicial
• Um programa linear pode ser exequível, mas solução
básica inicial pode não ser exequível
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
23
Solução Exequível Inicial
• Seja L um programa linear na forma standard, e seja
Laux definido da forma seguinte:
 x0
maximize
subject to
n
 aij x j  x0  bi
i  1,2,, m
xj  0
j  0,1,2,, n
j 1
• Então L é exequível se e só o valor objectivo óptimo
de Laux é 0
– Se L tem solução, então Laux tem solução com x0 = 0, o valor
óptimo
– Se o valor óptimo de x0 é 0, então solução é solução para L
2003/2004
Análise e Síntese de Algoritmos
24
Solução Exequível Inicial
• A partir de L construir Laux se solução básica inicial
não for exequível
• Determinar indíce l com menor bi
– Aplicar pivot com e = 0
• A solução básica calculada é exequível para Laux
• Aplicar passos do Simplex para calcular solução
óptima
– Se solução óptima verifica x0 = 0 retornar solução calculada,
sem x0
– Caso contrário L não é exequível
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
25
Solução Exequível Inicial
• Após a primeira aplicação de pivot, a solução básica
é exequível para Laux
– Prova
2003/2004
Análise e Síntese de Algoritmos
26
Simplex: Resultados Formais
• Dado um programa linear (A, b, c):
– Se o algoritmo Simplex retorna uma solução, a solução é
exequível
– Se o algoritmo Simplex retorna ‘unbounded’, o programa é
não limitado
• Dado um programa linear (A, b, c) na forma
standard, e B um conjunto de variáveis básicas, a
forma slack é única
2003/2004
Análise e Síntese de Algoritmos
27
Simplex: Resultados Formais
• Variação do valor da função objectivo após pivoting:
– Valor da função objectivo não pode diminuir
• Variável escolhida tem coeficiente positivo
• Valor da variável é não negativo, pelo que novo valor da
função de custo não pode diminuir
– Valor da função objectivo pode não aumentar
• Degenerescência
– Mas é sempre possível assegurar que algoritmo termina
2003/2004
Análise e Síntese de Algoritmos
28
Simplex: Resultados Formais
• O Simplex está em ciclo se existem formas slack
idênticas para duas iterações do algoritmo
n  m

• Se o algoritmo Simplex não termina após Cmnm  
m


iterações, então o algoritmo está em ciclo
– Cada conjunto B determina unicamente a forma slack
– Existem n+m variáveis e |B| = m
• Número de modos de escolher B: Cmnm
– Número de formas slack distintas: Cmnm
– Se algoritmo executar mais de Cmnm iterações, então está em
ciclo
• Eliminar ciclos:
– Regra de Bland: desempates na escolha de variáveis
através da escolha da variável com o menor indíce
2003/2004
Análise e Síntese de Algoritmos
29
Dualidade
• Conceito essencial em optimização
– Normalmente associado com existência de algoritmos
polinomiais
– E.g., fluxo máximo corte mínimo
• Programa linear dual:
minimizar
sujeito a

m
by
i 1 i i

m
a y
i 1 ij i
 cj
yi  0
j  1,2,, n
i  1,2,, m
• Programa primal: formulação original
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
30
Dualidade Fraca em
Programação Linear
• Seja x uma qualquer solução exequível do programa
primal e seja y uma qualquer solução exequível do
programa dual. Nestas condições:
n
m
j 1
i 1
 c j x j   bi yi
– Prova
2003/2004
Análise e Síntese de Algoritmos
31
Dualidade em Programação Linear
• Seja x uma qualquer solução pelo algoritmo Simplex, e
sejam N e B os conjuntos de variáveis para a forma slack
final. Seja c’ o vector dos coeficientes da forma slack final
e seja yi = -cn+i para (n+i)N; 0 caso contrário. Nestas
condições:
– x é solução óptima para o programa primal
– y é a solução óptima para o programa dual
n
m
– e,
 c j x j   bi yi
j 1
i 1
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
32
Teorema Fundamental da
Programação Linear
• Qualquer programa linear na forma standard:
– Ou tem solução óptima com valor finito,
– Ou não é exequível,
– Ou não é limitado.
Se L não é exequível, o algoritmo Simplex retorna “infeasible”
Se L não é limitado, o algoritmo Simplex retorna “unbounded”
Caso contrário, o algoritmo Simplex retorna uma solução
óptima com um valor objectivo finito
2003/2004
Análise e Síntese de Algoritmos
33
Exemplos Adicionais
• Algoritmo Simplex
• Solução exequível inicial
• Dualidade
• Fluxo máximo com o Simplex
2003/2004
Análise e Síntese de Algoritmos
34
Revisão
• Programação Linear
– Algoritmo Simplex
• A seguir:
– Fluxos de Custo Mínimo
2003/2004
Análise e Síntese de Algoritmos
(S, Cap. 22)
35