Programação Linear
Método Simplex
Profa. Sandra de Amo
Disciplina: Análise de Algoritmos
Pós-graduação em Ciência da Computação
Programação Linear

Variáveis: x1, …, xn

Restrições: conjunto de inequações lineares em x1, …, x

Função objetivo: função linear nas variáveis x1, …, xn

Objetivo: encontrar os valores de x1,…,xn:
 Verificando todas as restrições
 Maximizando (ou minimizando) a função objetivo
Exemplo


Variáveis: x1, x2
Restrições: m+n inequações
m=3
n=2
Função objetivo:
Espaço das Soluções: n-dimensional
Espaço das soluções



Limitado: polígono convexo
ou Ilimitado
ou Impossível
Problema da Programação Linear Inteira:
NP-completo
Idéia do método simplex




Partir de um vértice
Caminhar para o vértice vizinho que
“melhora” o valor da função objetivo
Caso encontre um vértice onde todos os
vizinhos tem valor igual ou pior para a função
objetivo, páre.
Retorna o valor deste vértice.
Exemplo
Por que o método funciona ?


Espaço das soluções é região convexa no espaço, dilimitada
por hiperplanos n-1 dimensionais.
Os pontos (x1,…,xn,y) tais que y = f(x1,…,xn), f = função
objetivo,
 representam um hiperplano deslocando-se no espaço
 quando este hiperplano deslocante encontra um ponto P
onde onde todos os outros pontos da região ficam abaixo
do hiperplano, este será o valor optimal.
 Se os vértices vizinhos de P ficam abaixo do hiperplano
passando por P, então todos os pontos da região também
ficam abaixo do hiperplano, já que a região é convexa.
Outro exemplo
Variáveis : x1, x2, x3
Restrições : total = 4 + 3
Função objetivo
Questões importantes
1)
Como determinar se um ponto é um vértice ?
1)
Como determinar se dois vértices são vizinhos ?
Vértices


Cada inequação representando uma restrição
corresponde a uma região n-dimensional no
espaço n-dimensional das soluções
A equação correspondente representa a fronteira
desta região, um hiperplano (dimensão n-1).


Chamamos tais equações de “equações fronteira”
Um vértice é o único ponto onde algum
subconjunto de hiperplanos se encontram.
Definição de vértice e vértices vizinhos





Seja n = número de variáveis
Um vértice é a solução de n equações
fronteira.
Dois vértices são vizinhos se têm em comum
n-1 de suas respectivas equações fronteira.
Pergunta: quantos vizinhos pode ter um
vértice (em termos de m e n ?)
Resposta: m.n vizinhos !
Exemplo
Vertice B = 2 + 3 + 4 ou
=2+4+5
Hipóteses



Origem O= (0,0,...0) está no espaço das soluções
Um vértice V é gerado por um único subconjunto de
n inequações.
Sempre podemos supor que o objetivo é maximar a
função objetivo pois:


min {f(x1,...,xn)} = max {– f(x1,...,xn)}
Se O está no espaço das soluções então

O é um vértice pois é solução de n inequações
x1 ≥ 0,..., xn ≥ 0
Algoritmo Simplex
1)
2)
V = (0,0,...0)
Enquanto V não é optimal faça
1)
2)
Determina vértice vizinho V’ para onde se mover
V = V’
Como testar se O é optimal ?


f(x1,...,xn) = c1x1 + ... + cnxn
f(0,...0) = 0
Se f(0,...,0) = max{c1x1 + ... + cnxn}então

ci ≤ 0, para todo i = 1,...,n
Logo, se um dos ci é positivo, O não é otimal.

Se O não é otimal, em quais das direções caminhar para aumentar o
valor de f(0,...0) = 0?


Basta escolher uma direção i onde ci > 0.
Até onde podemos caminhar nesta direção ?



Até que o ponto que se desloca (0,0,...0, c , 0,...0) torna-se solução de uma
das equações “fronteira”. Seja E esta equação.
Este é o próximo vértice V a ser testado.
V é solução de n equações fronteira: xj ≥ 0 (para i ≠ j) e E
Exemplo
Origem (0,0) não é otimal
Escolhemos a direção x2 para caminhar
Os pontos deste “caminho” são do tipo:
(0,x2)
A primeira inequação que é violada com
o crescimento de x2 é (3) já que:
(1) x2 ≥ - 4
(2) x2 ≤ 4.5
(3) x2 ≤ 3
Como transformar um vértice na
origem
Sejam E1,...,En as n inequações que
determinam um vértice u:
Ei: ai1x1 + ai2x2 + ... ain xn ≤ bi (para i =
1,...,n)
yi = a distância de qualquer ponto da
região ao hiperplano Ei
yi = bi – (ai1x1 + ai2x2 + ... ain xn)
yi ≥ 0
Transformar variáveis x1,...,xn nas variáveis y1,..., yn
Escrever x1,...,xn em função de y1,...,yn
A origem deste novo sistema é (y1,...,yn) onde yi=0 para todo i = 1,...,n
= vértice u
Programa transformado




Restrições são transformadas em inequações nas novas
coordenadas
Acrescenta-se as restrições yi ≥ 0, para i = 1,...,n
A origem do novo programa é o vértice u
A nova função objetivo é:

Max(G) onde G é obtida substituindo as antigas coordenadas x1,...,xn
por suas expressões envolvendo as novas y1,...,yn
Exemplo
Programa original
Programa transformado
Complexidade de Simplex


Simplex executa no pior dos casos k iterações, uma para cada vértice
do poliedro fronteira
O número de vértices é

De fato:
n = número de variáveis
n + m = número de inequações (m restrições + as restrições xi >= 0)
Cada vértice corresponde a um conjunto de n inequações
Logo: número de vértices = número de subconjuntos de tamanho n em
um conjunto de tamanho n+m

Existem exemplos de programas onde todos os vértices são testados
Logo: complexidade de Simplex é exponencial

Discussão






Simplex é um método exponencial
Somente em casos raros o pior caso é atingido
Na maioria dos casos, Simplex não verifica
todos os vértices e finaliza rapidamente.
Programação Linear inteira é NP-completo
Será que Programação Linear (real) é
polinomial ?
Por muito tempo pensou-se que não !
Histórico



1979: Leonid Khachiyan propôs o algoritmo Elipsoid que
resolve PL em tempo polinomial.
Paradoxo: Elipsoid, embora polinomial, na prática é menos
eficiente do que Simplex
1984: Narendra Kamarkar propôs o algoritmo de Karmarkar
que resolve PL em tempo polinomial e é eficiente na prática.



Diferente de simplex, o algoritmo alcança o máximo atravessando o
interior do poliedro através de um caminho especial.
Chamado: Método do “ponto interior”
Códigos super rápidos atuais são baseados em simplex
combinado com o método do ponto interior de Karmarkar.