Análise e Síntese de Algoritmos Programação Linear CLRS, Cap. 29

Análise e Síntese de Algoritmos

Programação Linear CLRS, Cap. 29

2003/2004 Análise e Síntese de Algoritmos 2

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)


Resumo

• Motivação• Formas Standard e Slack• Formulação de Problemas• O Algoritmo Simplex• Soluções Exequíveis Iniciais• Dualidade


Exemplo

• 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

Urbanos Suburbanos CampoEstradas -2 5 3Liberalização droga 8 2 -5Subsídios agricultura 0 0 10Imposto sobre gasolina 10 0 -2


Exemplo

Urbanos Suburbanos CampoEstradas -2 5 3Liberalização droga 8 2 -5Subsídios agricultura 0 0 10Imposto sobre gasolina 10 0 -2

0,,,252105310000255010082a sujeito

minimizar

4321

4321

4321

4321

4

1i

xxxxxxxxxxxxxxxx

xi

x1 = estradas; x2 = droga; x3 = subsídios; x4 = Imposto


Formulação Geral

• Programação Linear (LP):– Optimizar (minimizar ou maximizar) função linear sujeita a

conjunto de restrições lineares

– Função linear:

– Restrições lineares:

n

jjjn xcxxxf

121 ,,,

i

n

jjijnj bxaxxxg

1

21 ,,,


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 n-dimensional

• Conjunto convexo S: qualquer ponto de segmento que liga dois pontos em S está também em S

• S é designado por simplex

• Exemplo


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


Forma Standard

• Todos os valores cj, aij, bi são valores reais• Representação matricial:

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

njx

mibxa

xc

j

in

j jij

n

j jj

,,2,10

,,2,1a sujeito

maximizar

1

1

função objectivo

restrições

0a sujeito

maximizar T

xbAxxc


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


Conversão para Forma Standard

• Problemas:– Minimização em vez de maximização– Variáveis sem restrição de serem não negativas– Restrições com igualdade– Restricões com


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


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: variável de slack• Conversão de forma standard para forma slack:

• Exemplo

01

sxabs n

j jiji

01

in

n

j jijiin

xxabx


Forma Slack

• 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:

• Exemplo

n

j jijiin xabx1

n

j jjxcz1


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:

• Forma slack descrita por: (N, B, A, b, c, v)– v: constante na função objectivo

mnBN ,,2,1


Formulação de Problemas de LP

• Fluxos de Custo Mínimo:

– Caminhos Mais Curtos – Fluxo Máximo– ...

Ejiux

Viibxx

xcxz

ijij

Ejij Eijjjiij

Ei,jijij

,0

:a sujeito

minimizar

,: ,:


Outras Formulações

• Caminhos Mais Curtos– Entre s e t:

• Fluxo Máximo:

0

,,a sujeito

maximizar

sd

Evuvuwudvd

td

tsVuvufVvuuvfvufVvuvucvuf

vsf

Vv

Vv

,0,,,,,,,a sujeito

,maximizar


O Algoritmo Simplex

• Definições• Pivots

– Exemplo

• O algoritmo simplex• Soluções exequíveis iniciais• Dualidade


Forma Slack

• 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:

• 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

n

j jijiin xabx1

n

j jjxcz1


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– – –

le xxNN ' el xxBB '

vcbABN ,,,,','


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)


O Algoritmo Simplex

• Para valores i em B– Atribuir valor bi – Caso contrário atribuir valor 0

• i.e. variáveis em N

• Exemplos


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



• Seja L um programa linear na forma standard, e seja Laux definido da forma seguinte:

• 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

njx

mibxxa

x

j

n

jijij

,,2,1,00

,,2,1subject to

maximize

10

0



• 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



• Após a primeira aplicação de pivot, a solução básica é exequível para Laux – Prova


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



• 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



• O Simplex está em ciclo se existem formas slack idênticas para duas iterações do algoritmo

• Se o algoritmo Simplex não termina após 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: – Número de formas slack distintas: – Se algoritmo executar mais de 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

mmn

C mnm

mnmC

mnmC

mnmC


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:

• Programa primal: formulação original• Exemplo

miy

njcya

yb

i

jmi iij

mi ii

,,2,10

,,2,1a sujeito

minimizar

1

1


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:

– Prova

n

j

m

iiijj ybxc

1 1


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– e,

• Exemplo

n

j

m

iiijj ybxc

1 1


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


Exemplos Adicionais

• Algoritmo Simplex

• Solução exequível inicial

• Dualidade

• Fluxo máximo com o Simplex


Revisão

• Programação Linear – Algoritmo Simplex

• A seguir:– Fluxos de Custo Mínimo (S, Cap. 22)

Documents

Análise e Síntese de Algoritmos Programação Linear CLRS, Cap. 29