Motivação Formulações Algoritmo Simplex Dualidade

Análise e Síntese de Algoritmos

Programação Linear [CLRS, Cap. 29]
Motivação Formulações Algoritmo Simplex Dualidade

Contexto

Revisão [CLRS, Cap.1-13]

Fundamentos; notação; exemplos
Algoritmos em Grafos [CLRS, Cap.21-26]
Algoritmos elementares
Caminhos mais curtos
Fluxos máximos
Árvores abrangentes
Técnicas de Síntese de Algoritmos [CLRS, Cap.15-16]
Algoritmos greedy
Programação dinâmica
Programação Linear [CLRS, Cap.29]
Algoritmos e modelação de problemas com restrições lineares
Tópicos Adicionais [CLRS, Cap.32-35]
Emparelhamento de Cadeias de Caracteres
Complexidade Computacional
Algoritmos de Aproximação
Motivação Formulações Algoritmo Simplex Dualidade

Resumo

1 Motivação

2 Formulações
Forma Standard
Forma Slack

3 Algoritmo Simplex
Operação Pivot
Solução Exequível Inicial
Resultados Formais

4 Dualidade
Motivação Formulações Algoritmo Simplex Dualidade

Motivação

Exemplo
Urbanos Suburbanos Rurais
Estradas -2 5 3
Liberalização da Droga 8 2 -5
Subsídios Agricultura 0 0 10
Imposto sobre Gasolina 10 0 -2

Cada entrada representa o número de votos (em milhares) ganhos por

cada 1000 Euros gastos em campanhas
Objectivo a atingir:
Queremos ganhar pelo menos 50% dos votos (100.000 urbanos, 200.000
suburbanos e 50.000 rurais)
minimizar o total a gastar nas campanhas
Motivação Formulações Algoritmo Simplex Dualidade

Motivação

Exemplo
Urbanos Suburbanos Rurais
Estradas -2 5 3
Liberalização da Droga 8 2 -5
Subsídios Agricultura 0 0 10
Imposto sobre Gasolina 10 0 -2

Considere que as seguintes variáveis denotam a quantia a gastar em

campanha para os diferentes temas:
x1 = estradas; x2 = droga; x3 = subsídios; x4 = imposto
4
minimizar ∑ xj
j =1
sujeito a −2x1 + 8x2 + 0x3 + 10x4 ≥ 50
5x1 + 2x2 + 0x3 + 0x4 ≥ 100
3x1 − 5x2 + 10x3 − 2x4 ≥ 25
x1 , x2 , x3 , x4 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Motivação

Outro Exemplo
Uma pessoa tem insuficiências nos nutrientes Na , Nb , Nc . No entanto, estes
nutrientes podem ser encontrados em diferentes tipos de comida. Considere a
seguinte tabela que mostra a quantidade de cada nutriente Na , Nb , Nc por cada dose
unitária de comida C1 , C2 , C3 , C4 .

Na Nb Nc
C1 3 10 5
C2 8 4 7
C3 10 5 2
C4 0 15 10

Para suprimir as suas necessidades, deverá consumir 40 unidades do nutriente Na e

Nc , assim como 50 unidades de Nb . No entanto, o custo por cada dose unitária de
comida varia da seguinte forma: custo(C1 ) = 4, custo(C2 ) = 3, custo(C3 ) = 2, e
custo(C4 ) = 6.
Assumindo que pode comprar doses parciais, qual a quantidade de cada tipo de
comida a consumir para ficar saudável e da forma mais barata possível?
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

Formulação Geral
Programação Linear
Optimizar (minimizar ou maximizar) função linear sujeita a conjunto de
restrições lineares
Função linear (função objectivo):
n
f (x1 , x2 , . . . , xn ) = ∑ cj xj
j =1

Restrições Lineares:

≥
n
g1 (x1 , x2 , . . . , xn ) = ∑ aij xj = bi
j =1
≤
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar

x1 ≥ 0
sujeito a

x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar

x1 ≥ 0
sujeito a

x1 , x2 ≥ 0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

2 8
Exemplo

1 x ≤
maximizar

4x −
x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8

x1 , x2 ≥ 0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

2 8
Exemplo

1 x ≤
maximizar

4x −
x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10

2x 1
x1 , x2 ≥ 0

+ x2
≤1
0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

2 −
2
1 −2
x ≥

2 8
Exemplo

1 x ≤
5x
maximizar

4x −
x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
− ≥ −2

2x 1
5x1 2x2
x1 , x2 ≥ 0

+ x2
≤1
0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

2 −
2
1 −2
x ≥

2 8
Exemplo

1 x ≤
5x
maximizar

4x −
x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
− ≥ −2

2x 1
5x1 2x2
x1 , x2 ≥ 0

+ x2
≤1
0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar

x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar x1 + x2

x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar x1 + x2

x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar x1 + x2

x1 ≥ 0
sujeito a
4x1 − x2 ≤ 8
2x1 + x2 ≤ 10
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0

x1
+
x2
=4
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar x1 + x2

x1 ≥ 0
sujeito a
− ≤

x1
4x1 x2 8

+
+ ≤

x2
2x1 x2 10

=8
5x1 − 2x2 ≥ −2
x1 , x2 ≥ 0

x1
+
x2
=4
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

x2

Exemplo
maximizar x1 + x2
sujeito a
Solução
4x1 − x2 ≤ 8

x1 ≥ 0
2x1 + x2 ≤ 10

x1
5x1 − 2x2 ≥ −2

+
x2
x1 , x2 ≥ 0

=8
x1
Solução

+
x2
x1 = 2, x2 = 6

=4
x1

x1
+

x2 ≥ 0
x2
=0
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

Região Exequível
x2
Qualquer solução que satisfaça o conjunto
de restrições designa-se por solução
exequível
A cada solução exequível corresponde um
valor (custo) da função objectivo
O conjunto de soluções exequíveis é
designado por região exequível
A região exequível é um conjunto convexo
no espaço n-dimensional
Conjunto convexo S: qualquer ponto de um
segmento que liga quaisquer dois pontos
em S está também em S x1
S é designado por simplex
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

Região Exequível
Qualquer solução que satisfaça o conjunto
x2
de restrições designa-se por solução
exequível
A cada solução exequível corresponde um
valor (custo) da função objectivo
O conjunto de soluções exequíveis é
designado por região exequível
A região exequível é um conjunto convexo
no espaço n-dimensional
Conjunto convexo S: qualquer ponto de um
segmento que liga quaisquer dois pontos
em S está também em S
S é designado por simplex
x1
A solução óptima encontra-se num vértice
do simplex
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

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
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

Perspectiva sobre Programação Linear

Conceitos a reter:
Solução: exequível ou não exequível
Valor da função objectivo: valor objectivo
Valor máximo/mínimo: valor objectivo óptimo
Se formulação não tem soluções exequíveis diz-se não exequível; caso
contrário diz-se exequível
Se formulação é exequível, mas sem solução óptima, diz-se não
limitado
Motivação Formulações Algoritmo Simplex Dualidade

Formulações

Caminhos Mais Curtos

Caminhos mais curtos entre s e t:

maximizar d [t ]
sujeito a d [v ] ≤ d [u ] + ω(u , v ), ∀(u , v ) ∈ E
d [s] = 0

Fluxo Máximo
maximizar ∑ f (s, v )
v ∈V
sujeito a f (u , v ) ≤ c (u , v ) ∀u , v ∈ V
f (u , v ) = −f (v , u ) ∀u , v ∈ V
∑v ∈V f (u , v ) = 0 ∀u ∈ V − {s, t }
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

Forma Standard
n
maximizar ∑ cj xj
j =1
n
sujeito a ∑ aij xj ≤ bi i = 1, 2, . . . , m
j =1
xj ≥ 0 j = 1, 2, . . . , n

Todos os valores cj , aij , bi são valores reais

Representação Matricial

maximizar cT x
sujeito a Ax ≤ b
x≥0

Em que A = (aij ), b = (bi ), c = (cj ) e x = (xj )

Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

Problemas na Conversão para a Forma Standard

Minimização em vez de maximização
Variáveis sem restrição de serem não negativas
Restrições com igualdade
Restricões com ≥
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

Problemas na Conversão para a Forma Standard

Minimização vs. Maximização:
Multiplicar coeficientes por -1
Variáveis sem restrição de serem não negativas:
Substituir cada ocorrência de xi por (xi1 − xi2 ), em que xi1 e xi2 são novas
variáveis
Restrições com igualdade:
Introduzir duas restrições, uma com ≤ e outra com ≥
Restrições com ≥ :
Multiplicar restrição por –1
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

minimizar −2x1 + 3x2

sujeito a
x1 + x2 = 7
x1 − 2x2 ≤ 4
x1 ≥ 0

maximizar 2x1 − 3x2

sujeito a
x1 + x2 = 7
x1 − 2x2 ≤ 4
x1 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

maximizar 2x1 − 3x2

sujeito a
x1 + x2 = 7
x1 − 2x2 ≤ 4
x1 ≥ 0

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 = 7
x1 − 2x20 + 2x200 ≤ 4
x1 , x20 , x200 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 = 7
x1 − 2x2 + 2x200
0 ≤ 4
x1 , x20 , x200 ≥ 0

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 ≤ 7
x1 + x20 − x200 ≥ 7
x1 − 2x20 + 2x200 ≤ 4
x1 , x20 , x200 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 ≤ 7
x1 + 0
x2 − x200 ≥ 7
x1 − 2x2 + 2x200
0 ≤ 4
x1 , x20 , x200 ≥ 0

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 ≤ 7
−x1 − x2 + 0 x200 ≤ −7
x1 − 2x2 + 2x200
0 ≤ 4
x1 , x20 , x200 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Standard

Formulações

maximizar 2x1 − 3x20 + 3x200

sujeito a
x1 + x20 − x200 ≤ 7
−x1 − x2 + 0 x200 ≤ −7
x1 − 2x2 + 2x200
0 ≤ 4
x1 , x20 , x200 ≥ 0

maximizar 2x1 − 3x2 + 3x3

sujeito a
x1 + x2 − x3 ≤ 7
−x1 − x2 + x3 ≤ −7
x1 − 2x2 + 2x3 ≤ 4
x1 , x2 , x3 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Slack

Formulações

Conversão para a 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 si (variável de slack)
n
si = bi − ∑ aij xj
j =1
si ≥ 0

Conversão de forma standard para forma slack:

n
xn+i = bi − ∑ aij xj
j =1
xn+i ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Forma Slack

Formulações

Conversão para a Forma Slack

n
Nas expressões: xn+i = bi − ∑ aij xj
j =1
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
A solução básica é obtida quando se colocam as variáveis não-básicas
com valor 0
Na forma slack, a função objectivo é definida como:
n
z= ∑ cj xj
j =1
Motivação Formulações Algoritmo Simplex Dualidade

Forma Slack

Formulações

Conversão para a 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
N ∪ B = {1, 2, . . . , n + m}
Forma slack descrita por: (N , B , A, b, c , v )
v : constante na função objectivo
n
z = v + ∑ cj xj
j =1
n
xn+i = bi − ∑ aij xj i = 1, 2, . . . , m
j =1
Motivação Formulações Algoritmo Simplex Dualidade

Forma Slack

Formulações

maximizar 2x1 − 3x2 + 3x3

sujeito a
x1 + x2 − x3 ≤ 7
−x1 − x2 + x3 ≤ −7
x1 − 2x2 + 2x3 ≤ 4
x1 , x2 , x3 ≥ 0

z = 2x1 − 3x2 + 3x3

x4 = 7 − x1 − x2 + x3
x5 = −7 + x1 + x2 − x3
x6 = 4 − x1 + 2x2 − 2x3
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

Operação Pivot
Operação central do algoritmo Simplex
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 0 = N − { x e } ∪ {x l }
B 0 = B − {xl } ∪ {xe }
(N 0 , B 0 , A , b , c , v )
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

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 (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)

No final, retornar solução básica
x i ← bi , se i ∈ B (variáveis básicas)
x i ← 0, se i ∈ N (variáveis não-básicas)
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

maximizar 3x1 + x2 + 2x3

sujeito a
x1 + x2 + 3x3 ≤ 30
2x1 + 2x2 + 5x3 ≤ 24
4x1 + x2 + 2x3 ≤ 36
x1 , x2 , x3 ≥ 0

Forma Slack

z = 3x1 + x2 + 2x3
x4 = 30 − x1 − x2 − 3x3
x5 = 24 − 2x1 − 2x2 − 5x3
x6 = 36 − 4x1 − x2 − 2x3
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

z = 3x1 + x2 + 2x3
x4 = 30 − x1 − x2 − 3x3
x5 = 24 − 2x1 − 2x2 − 5x3
x6 = 36 − 4x1 − x2 − 2x3

Operação pivot entre x1 e x6

x2 x3 3x6
z = 27 + 4
+ 2
− 4
x2 x3 x6
x1 = 9 − 4
− 2
− 4
3x2 5x3 x6
x4 = 21 − 4
− 2
+ 4
3x2 x6
x5 = 6 − 2
− 4x3 + 2
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

x2 x3 3x6
z = 27 + 4
+ 2
− 4
x2 x3 x6
x1 = 9 − 4
− 2
− 4
3x2 5x3 x6
x4 = 21 − 4
− 2
+ 4
3x2 x6
x5 = 6 − 2
− 4x3 + 2

Operação pivot entre x3 e x5

111 x2 x5 11x6
z = 4
+ 16
− 8
− 16
33 x2 x5 5x6
x1 = 4
− 16
+ 8
− 16
3 3x2 x5 x6
x3 = 2
− 8
− 4
+ 8
69 3x2 5x5 x6
x4 = 4
+ 16
+ 8
− 16
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

111 x2 x5 11x6
z = 4
+ 16
− 8
− 16
33 x2 x5 5x6
x1 = 4
− 16
+ 8
− 16
3 3x2 x5 x6
x3 = 2
− 8
− 4
+ 8
69 3x2 5x5 x6
x4 = 4
+ 16
+ 8
− 16

Operação pivot entre x2 e x3

x3 x5 2x6
z = 28 − 6
− 6
− 3
x3 x5 x6
x1 = 8 + 6
+ 6
− 3
8x3 2x5 x6
x2 = 4 − 3
− 3
+ 3
x3 x5
x4 = 18 − 2
+ 2
Motivação Formulações Algoritmo Simplex Dualidade

Operação Pivot

Algoritmo Simplex

x3 x5 2x6
z = 28 − 6
− 6
− 3
x3 x5 x6
x1 = 8 + 6
+ 6
− 3
8x3 2x5 x6
x2 = 4 − 3
− 3
+ 3
x3 x5
x4 = 18 − 2
+ 2

Não há coeficientes positivos na função objectivo. Simplex termina.

Solução: x1 = 8, x2 = 4 e x3 = 0. Valor função objectivo: 28.

maximizar 3x1 + x2 + 2x3

sujeito a x1 + x2 + 3x3 ≤ 30
2x1 + 2x2 + 5x3 ≤ 24
4x1 + x2 + 2x3 ≤ 36
x1 , x2 , x3 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

Solução Exequível Inicial

Um programa linear pode ser exequível, mas solução básica inicial pode não
ser exequível
Seja L um programa linear na forma standard, e seja Laux definido da
seguinte forma:

maximizar −x0
n
sujeito a ∑ aij xj − x0 ≤ bi i = 1, 2, . . . , m
j =1
xj ≥ 0 j = 0, 1, 2, . . . , n

Então L é exequível se e só se 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
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

Solução Exequível Inicial

Se solução básica inicial for não exequível:
A partir de L construir Laux
Determinar índice l com menor bi
Aplicar operação pivot entre xl e x0
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
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

Solução Exequível Inicial

Após a primeira aplicação de pivot, a solução básica é exequível para
Laux
e=0
l tal que bl < bi , i = 1, . . . , m
bl < 0, pois solução inicial exequível se bi ≥ 0
Após aplicar operação pivot tem-se:
x0 = bl /al0
xi = bi − ai0 (bl /al0 ), i 6= 0
Como ai0 = −1 para todo o i,
x0 = −bl > 0
xi = bi − bl > 0
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

maximizar 2x1 − x2
sujeito a
2x1 − x2 ≤ 2
x1 − 5x2 ≤ −4
x1 , x2 ≥ 0

Solução básica inicial não é exequível.

Construção de Programa Linear Auxiliar.

maximizar −x0
sujeito a
2x1 − x2 − x0 ≤ 2
x1 − 5x2 − x0 ≤ −4
x1 , x2 , x0 ≥ 0
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

maximizar −x0
sujeito a
2x1 − x2 − x0 ≤ 2
x1 − 5x2 − x0 ≤ −4
x1 , x2 , x0 ≥ 0

Forma slack do Programa Linear Auxiliar.

z = − x0
x3 = 2 − 2x1 + x2 + x0
x4 = −4 − x1 + 5x2 + x0
Motivação Formulações Algoritmo Simplex Dualidade

Solução Exequível Inicial

Algoritmo Simplex

z = − x0
x3 = 2 − 2x1 + x2 + x0
x4 = −4 − x1 + 5x2 + x0

Operação pivot entre x0 e x4 .

z = −4 − x1 + 5x2 − x4
x3 = 6 − x1 − 4x2 + x4
x0 = 4 + x1 − 5x2 + x4

Solução básica inicial passou a ser exequível para o programa auxiliar.

Resolver programa auxiliar usando Simplex.
Motivação Formulações Algoritmo Simplex Dualidade

Resultados Formais

Algoritmo 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
Motivação Formulações Algoritmo Simplex Dualidade

Resultados Formais

Algoritmo 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
Motivação Formulações Algoritmo Simplex Dualidade

Resultados Formais

Algoritmo 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 Cm 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+m
Número de modos de escolher B: Cm
n+m
Número de formas slack distintas: Cm
n+m
Se algoritmo executar mais de Cm 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
Motivação Formulações Algoritmo Simplex Dualidade

Dualidade

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:
m
minimizar ∑ bi yi
i =1
m
sujeito a ∑ aij yi ≥ cj j = 1, 2, . . . , n
i =1
yi ≥ 0 i = 1, 2, . . . , m
A formulação original é conhecida como o programa primal
Motivação Formulações Algoritmo Simplex Dualidade

Dualidade

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
∑ cj xj ≤ ∑ bi yi
j =1 i =1

Prova:
n n m
∑ cj xj ≤ ∑ ( ∑ aij yi )xj
j =1 j =1 i =1
m n
= ∑ ( ∑ aij xj )yi
i =1 j =1
m
≤ ∑ bi yi
i =1
Motivação Formulações Algoritmo Simplex Dualidade

Dualidade

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 0 o vector dos coeficientes da forma slack final e seja yi = −cn0 +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, ∑ cj xj = ∑ bi yi
j =1 i =1
Motivação Formulações Algoritmo Simplex Dualidade

Dualidade

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