Restrições Lineares sobre os Reais/Racionais
•
Muitos problemas podem ser modelados através de restrições sobre
variáveis que, para todos os efeitos práticos, podem tomar valores
no domínio dos números reais (ou racionais).
•
Essas variáveis são geralmente denominadas variáveis de decisão.
•
Um caso particularmente importante ocorre quando todas as
restrições sobre essas variáveis são lineares.
•
Em muitos casos, pretendem-se soluções que não só satisfaãm
todas as restrições, mas também que optimizem uma função (linear)
objectivo - optimização condicionada
•
Exemplos:
– gestão da produção
– redes de distribuição
1
Gestão da Produção
Dados:
a)
Um conjunto de itens P1, ..., Pn que se pretende produzir
b)
Um conjunto de recursos R1, ..., Rm disponíveis para os produzir
c)
Uma matriz A, cujos elementos aij representam a quantidade do
recurso i necessário para produzir uma unidade do item j
d)
Um vector C, cujos elementos cj representam o lucro obtido por
cada unidade do item j produzido
e)
Um vector B, cujos elementos bi representam a quantidade máxima
do recurso i que pode ser utilizado
Objectivo:
Determinar a quantidade a produzir de cada item j
2
Gestão da Produção
Gestão 0: Restrições Base
Designando por Xi a quantidade do item Pi produzido, o problema de
não sobre-utilização dos recursos existentes é modelado por
a11 X1 + a12 X2 + ... + a1n Xn =< b1
...
am1 X1 + am2 X2 + ... + amn Xn =< bm
Por exemplo, sendo necessárias 3 minutos de uma máquina para
fabricar 1 sapato e 4 minutos para 1 bota, representando por S e B o
número de sapatos e botas e estando a máquina disponível 4 horas
temos
3 S + 4 B =< 240
3
Gestão da Produção
Gestão 1: Satisfação (de um dado lucro)
Para modelar que um dado lucro L é atingido, adiciona-se ao modelo
anterior a restrição
c1 X1 + c2 X2 + ... + cn Xn >= L
Por exemplo, se se obtem um lucro de 4(5) € por cada sapato (bota)
vendido, pretender que o lucro seja pelo menos de 3000€ é modelada
pela restrição
4 S + 5 B >= 3000
Gestão 2: Optimização (do lucro obtido)
Para modelar a maximização do lucro obtido, adiciona-se ao modelo
inicial a função objectivo L (a maximizar)
Max
L = c1 X1 + c2 X2 + ... + cn Xn
4
Gestão da Produção (Dual)
Dados:
a)
Um conjunto de itens P1, ..., Pn que se pretende produzir
b)
Um conjunto de recursos R1, ..., Rm disponíveis para os produzir
c)
Uma matriz A, cujos elementos aij representam a quantidade do
recurso i necessário para produzir uma unidade do produto j
d)
Um vector C, cujos elementos cj representam o custo mínimo por
cada unidade do item j produzido
e)
Um vector B, cujos elementos bj representam a quantidade do
recurso j a utilizar
Objectivo:
Determinar os custos por recurso adequados
5
Gestão da Produção (Dual)
Gestão 0d:
Restrições Base
Designando por Yj o custo incorrido por cada unidade do recurso j
gasto, as restrições que impõe um custo mínimo por unidade de item i
produzido são modeladas por
a11 Y1 + a21 Y2 + ... + am1 Ym >= c1
a12 Y1 + a22 Y2 + ... + am2 Ym >= c2
...
a1m Y1 + a2m Y2 + ... + amn Ym >= cn
6
Gestão da Produção (Dual)
Gestão 1d: Satisfação (de um dado custo total)
A garantia de que o custo total do plano de produção não excede um
valor V é modelada, por adição ao modelo da restrição
b1 Y1 + b2 Y2 + ... + bm Ym =< V
Gestão 2d: Optimização (do custo total)
Para modelar a minimização dos custo total do plano de produção,
adiciona-se a função objectivo V (a minimizar)
Min
V = b1 Y1 + b2 Y2 + ... + bm Ym
7
Redes de Distribuição
Dados:
a)
Um conjunto de nós P1, ..., Pn , dos quais P1 é emissor e Pn o
receptor
b)
Uma matriz M, cujos elementos mi,j representam a capacidade da
ligação (em bits/seg) entre os nós i e j
c)
Uma matriz C, cujos elementos ci,j representam o custo (em €/bit)
da transmissão entre os nós i e j;
Objectivo:
Avaliar o fluxo de informação que a rede é capaz de transmitir entre
os nós emissor (P1) e receptor (Pn).
8
Redes de Distribuição
Restrições Base:
Designando por Xi,j a quantidade de informação debitada entre os nós i
e j, as restrições de capacidade são
X1,1 =< m1,1
...
Xm,n =< mm,n
% Em geral mi,i = 0
As restrições de igualdade de fluxo de entrada e saída em todos os k
nós (excepto nos nós P1 e Pn) são modeladas por
X1,2+X2,2+X3,2+...+Xn,2 = X2,1+X2,2+ ...+X2,n
X1,3+X2,3+X3,3+...+Xn,3 = X3,1+X3,2+ ...+X3,n
...
X1,k+X2,k+X3,k+...+Xn,k = Xk,1+Xk,2+ ...+Xk,n
9
Redes de Distribuição
Redes 1: Satisfação (de um fluxo F entre P1 e Pn)
A verificação de que é possível transmitir um determinado fluxo de
informação F entre os nós emissor (P1) e receptor (Pn) é modelada pela
adição da restrição
X1,2+X1,3+X1,4+...+X1,n >= F
ou
X1,n+X2,n+X3,n+...+Xn-1,,n >= F )
Redes 2: Optimização (do fluxo total)
Para modelar o máximo fluxo de informação que a rede é capaz de
transmitir entre os nós P1 e Pn, adiciona-se uma função objectivo F (a
maximizar)
Max
F =
X1,2+X1,3+X1,4+...+X1,n
10
Formalização
Os problemas de satisfação de restrições lineares sobre variáveis (de
decisão) Xi reais (ou racionais, se todos os parâmetros aij são números
racionais) têm a forma
a11 X1 + a12 X2 + ... + a1n Xn ρ1 b1
a21 X1 + a22 X2 + ... + a2n Xn ρ2 b2
...
am1 X1 + am2 X2 + ... + amn Xn ρm bm
em que ρ1..ρm são relações do conjunto {≤, =, ≥, <, >, ≠ }
Se se pretender a optimização das variáveis de decisão, inclui-se a
optimização de uma função (linear) objectivo F
Opt F = c1 X1 + c2 X2 + ... + cn Xn
em que Opt pode ser um de {Max, Min, Sup, Inf}.
11
Interpretação Geométrica
Dado um espaço com n dimensões, a restrição
ai1 X1 + ai2 X2 + ... + ain Xn = bi
define uma região admissível, correspondente aos pontos de um
hiper-plano desse espaço.
Como casos particulares temos
•
um espaço tridimensional (n=3), em que o hiper-plano corresponde
ao plano usual, e
•
um espaço bidimensional (ou vulgar plano, n=2) em que o hiperplano se reduz a uma recta.
A restrição ≠ define uma região admissível que corresponde a todos os
pontos do espaço n-dimensional, excepto os pontos do hiper-plano
12
Interpretação Geométrica
As restrições ≤ e ≥ definem regiões admissíveis do tipo semi-hiperespaço limitado pelo correspondente hiper-plano, incluído na região
admissível.
Com n=3 temos um semi-espaço e com n=2 um semi-plano.
As restrições < e > definem regiões admissíveis semelhantes, mas
excluindo a fronteira.
O conjunto de restrições define, num espaço a n dimensões, um hiperpoliedro (poliedro com n=3 e polígono com n=2) correspondente à
intersecção das m regiões admissíveis (m+n com não negatividade).
Algumas faces do hiper-poliedro pertencem (≤, ≥) à região admissível e
outras não (<, >). Devem ainda ser considerados hiper-planos de
exclusão (≠).
13
Interpretação Geométrica
• Com exclusão das restrições ≠, a região admissível é convexa.
• Em problemas de optimização a função
C =
c1
X1 + c2
X2 + ... + cn
Xn
define uma família de hiper-planos paralelos (1 para cada valor de C).
• O supremo e o ínfimo dessa função na região admissível corresponde
a um (hiper-)vértice do hiper-poliedro, o “último” ponto em que um
hiper-plano da função objectivo “toca” a região admissível quando se
desloca para valores crescentes (Sup) ou decrescentes (Inf) de C.
14
Interpretação Geométrica
• Se esse vértice pertencer à região admissível ele corresponde
igualmente ao seu Max ou Min
• Caso contrário (i.e. se foi excluído por alguma restrição >, < ou ≠)
não existem Max/Min mas apenas Sup/Inf.
• No caso em que o vértice de óptimo pertence a uma aresta ou um
lado do hiper-poliedro paralelos à família de hiper-planos de
optimização, haverá em geral mais do que um ponto óptimo, já que a
função objectivo tem o mesmo valor em todos os pontos dessas
arestas e lados.
15
Exemplo (2 dimensões)
X2
max X1 + X2
Suj. 2 X1 + X2 ≤ 8
X1 + X2 ≥ 3
X1 - X2 ≥ -5
X1 - X2 ≥ -5
X1 ≥ 0
2 X1 + X2 ≤ 8
X1 + X2 = k
X1 + X2 ≥ 3
x1
X2 ≥ 0
16
Complexidade Potencial
• Apesar de o espaço de pesquisa ser infinito, o problema de satisfação
reduz-se à verificação de que as restrições definem um hiper-poliedro
não vazio.
• Assim, pelo menos um dos vértice definidos pelos hiper-planos de
fronteira das restrições (excepto restrições ≠) deve pertencer à região
admissível.
• Como n restrições de igualdade (independentes) num espaço ndimensional definem univocamente um ponto (solução de um sistema
de n equações a n incógnitas), no pior caso, ter-se-á de verificar a
pertença à região admissível de Cmn pontos.
• Na prática, o número de vértices a testar é muito inferior.
• No pior caso, a complexidade do problema de satisfação é idêntica a
um problema de optimização.
17
Formas Resolvidas
• Há pois que determinar uma forma expedita de representar os
vértices, e pesquisem eficientemente se pertencem à região
admissível.
• Em particular, estaremos interessados em algoritmos que
•
Associem vértices a uma Forma Resolvida,
•
Implementem a pesquisa
manipulações algébricas.
através
de
um
conjunto
de
• A associação deverá ser possível se e apenas se o conjunto de
restrições inicial fôr satisfazível.
• Vamos abordar estas formas resolvidas para sistemas de restrições
com riqueza de expressão crescente.
18
Restrições Não-Estritas / Variáveis Não-negativas
• As restrições de desigualdade podem ser substituidas por restrições
de igualdade através da adição de variáveis de desvio (slacks),
igualmente não negativas
ai1 X1 +...+ ain Xn ≤ bi  ai1 X1 +...+ ain Xn + Si = bi
ai1 X1 +...+ ain Xn ≥ bi  ai1 X1 +...+ ain Xn - Si = bi
• A existência de uma forma resolvida para estes sistemas de restrições
é justificada pelo seguinte
Lema 1: Todo o sistema de m equações a m+n incógnitas não
negativas, é satisfazível sse admitir uma solução em que n variáveis
são nulas.
Demonstração:
 Se existe uma solução então o sistema é satisfazível.
19
Lema 1 (exemplo)
•
Considere-se o sistema de 2 equações a 4 incógnitas (isto é, m = 2
e n = 2). Este exemplo permite perceber melhor os passos da
demonstração (por indução em n) apresentada adiante.
(S1)
3X1–2X2+ X3- X4 = 4
X1+ X2-2X3+ X4 = 2
que admite a solução não negativa <X1,X2,X3,X4> = <2,1,1,1>.
•
Escolhendo arbitrariamente uma das variáveis, por exemplo X4, e
fazendo-se X4 = 1- δ (notar o sinal “-”) obtem-se o sistema S2
(S2)
3X1–2X2+ X3 = 5 - δ
X1+ X2-2X3 = 1 + δ
•
Assuma-se δ = 0. Pela hipótese de indução todo o sistema de m
equações a m+n incógnitas (neste caso, 2 equações a 3 incógnitas)
tem uma solução <s1,s2,s3> com n-1 (1) variáveis nulas.
20
Lema 1 (exemplo)
•
Este é o caso de S2 que admite de facto a solução < 11/7, 0, 2/7>,
podendo colocar-se na forma equivalente S3
(S3)
X1 = 11/7 + 3/7 X2 – 1/7 δ
X3 =
•
Anulando a variável X2 obtem-se o sistema S4
(S4)
X1 = 11/7 – 1/7 δ
X3 =
•
2/7 + 5/7 X2 – 4/7 δ
2/7 – 4/7 δ
Para toda a solução <s1, s3> não negativa deste sistema existe uma
solução <s1, 0, s3, 1-δ > do sistema S1 inicial.
•
Com δ =0, temos obviamente a solução <11/7, 0, 2/7, 1 >.
•
Mas incrementando-se o valor de δ ir-se-á necessariamente obter
uma nova solução de S1 em que uma das variáveis X1, X3 ou X4 terá
o valor 0.
21
Lema 1 (exemplo)
(S4)
X1 = 11/7 – 1/7 δ
X3 =
2/7 – 4/7 δ
Em geral duas situações podem acontecer.
•
Os termos em δ são todos positivos (não é o caso do exemplo):
Relembrando que tinhamos X4 = 1- δ, poderia fazer-se δ=1,
obtendo-se uma solução do sistema S1 com X3 e X4 nulos (sendo
X1 e X3 mais positivos que 11/7 e 2/7, respectivamente).
•
Alguns termos em δ são negativos (caso do exemplo):
Neste caso, incrementando-se δ vão-se decrementando os valores
das variáveis X1 e X3, bem com da variável X4, nas soluções
correspondentes de S1.
Haverá então algum valor mínimo de δ que anulará uma destas
variáveis, e garantirá as n (=2) variáveis nulas numa solução de
S1.
22
Lema 1 (exemplo)
(S4)
X1 = 11/7 – 1/7 δ
X3 =
2/7 – 4/7 δ
Neste exemplo temos
• δ = 1/2 → X3 = 0
• δ = 1 → X4 = 0
• δ = 11 → X1= 0
•
( e X1 = 3/2 ; X4 = 1/2)
( e X1 = 10/7 ; X3 = 2/7)
( e X3 = - 6 ; X4 = -10)
Para o menor destes valores de δ garante.-se pois que uma das
variáveis se anula e nenhuma das outras se torna negartiva
resolvendo-se o sistema inicial. Neste caso, a solução
<21/14, 0, 0, ½>
é de facto uma solução do sistema inicial S1
(S1)
3X1 – 2X2+ X3 - X4 = 4
X1 + X2- 2X3 + X4 = 2
23
Lema 1
 (1)
 A demonstração é feita por indução em n. Sendo o caso n=0 trivial,
falta demonstrar o passo de indução, ou seja,
se qualquer sistema de m equações a n variáveis não negativas tem
uma solução com n variáveis nulas, então qualquer sistema de m
equações a n+1 variáveis não negativas tem uma solução com n+1
variáveis nulas.
Consideremos um sistema satisfazível com m+n+1 variáveis
(S1) ai,1X1+..+ai,m+nXm+n+ai,m+n+1Xm+n+1 = bi i: 1..m
Se o sistema é satisfazível, existe uma solução Xi = wi (≥ 0 para i:
1..m+n+1). Substituindo Xm+n+1 por Xm+n+1= wm+n+1-δ
(S2)
ai,1X1+...+ai,m+nXm+n
ai,m+n+1wm+n+1)
=
ci+ai,m+n+1δ
(ci=bi-
Uma solução deste sistema com δ=0 é uma solução do sistema S1 com
Xm+n+1 = wm+n+1.
24
Lema 1
 (2)
Assim, o sistema S3 é satisfazível (admite a solução inicial Xi = wi )
(S3) ai,1X1+...+ai,m+nXm+n = ci
Ora tendo este sistema, satisfazível, m equações e m+n variáveis, pela
hipótese de indução, deve ter uma solução com n variáveis nulas. Sem
perda de generalidade, considere-se que são as últimas n variáveis
que se anulam, nessa solução, isto é, que existe uma solução
Xi = di ≥ 0 para i: 1..m
e
Xm+j = 0 para j : 1, n
Desta forma, o sistema S3 pode reescrever-se na forma
(S4) Xi = di + ci,m+1 Xm+1+ ... + ci,m+n Xm+n
Algebricamente, S4 é obtido de S3 por combinação linear das suas
linhas. Aplicando a mesma combinação linear, não a S3 mas a S2,
obtemos o sistema
(S5) Xi = di + ci,m+1Xm+1+...+ ci,m+nXm+n + ci,m+n+1δ
25
Lema 1
 (3)
Sendo obtido por uma combinação linear de S2, S5 é equivalente a S2.
Assim, qualquer solução de S5 com δ=0 é uma solução do sistema
inicial (S1), com Xm+n+1 = wm+n+1.
Se considerarmos apenas as soluções com as n variáveis Xm+j (j: 1..n)
nulas o sistema S5 pode ser reescrito como
(S6) Xi = di + ci,m+n+1 δ
Assim, qualquer solução deste sistema S5, corresponde a uma solução
do sistema S1 em que
Xi
= di + ci,m+n+1 δ
i : 1..m;
Xm+j
= 0
j : 1..n; e
Xm+n+1 = wi-δ
Desta forma o sistema S1 inicial de m equações a m+n+1 variáveis tem
uma solução com n variáveis nulas (todas as variáveis Xm+j com j: 1..n).
26
Lema 1
 (4)
Se algum dos dis ou se wi fôr nulo, então basta fazer δ=0 para obter
uma solução de S1 com n+1 variáveis nulas: as anteriores mais Xi (i:
1..m) ou Xm+n+1.
Xi
= di + ci,m+n+1 δ
i : 1..m;
Xm+n+1
= wi-δ
No caso mais geral, em que os dis e wi são estritamente positivos, pode
obter-se uma nova solução para um valor de δ > 0 e que garanta
di + ci,m+n+1 δi = 0
para algum i : 1..m; ou
δm+n+1 = wi
No menor destes valores δi, S6 tem uma solução com uma variável
nula.
Mas então o sistema S1 tem uma solução com n+1 variáveis nulas:
para além da variável correspondente de S6, todas as variáveis Xm+j (j:
1..n) são nulas, o que prova o teorema .
27
Forma Resolvida SF0
Definição: Dado um sistema de equações de m equações a m+n
incógnitas
(S1)
ai,1 X1+...+ai,m+n Xm+n = bi
(i: 1..m)
a sua forma resolvida SF0 tem a forma
(SF0) Xi = di + ci,m+1 Xm+1+...+ ci,m+n Xm+n
sendo di ≥ 0 i: 1..m
As variáveis no lado esquerdo são as variáveis básicas, sendo as outras
as não básicas (as variáveis básicas podem ser quaisquer e não as
primeiras m variáveis como são apresentadas para simplificar a
notação).
O lema anterior permite justificar o seguinte teorema.
28
Forma Resolvida SF0
Teorema: Um sistema de equações de m equações a m+n variáveis
não-negativas é satisfazível sse se puder reescrever na forma SF0.
Demonstração
 Se se pode reescrever na forma resolvida SF0, então o sistema
admite a solução não negativa, <d1, d2, ..., dm,0,..,0>.
 Dado o sistema satisfazível
(S1)
ai,1 X1+...+ai,m+n Xm+n = bi
(i: 1..m)
o lema anterior garante uma solução <d1,d2, ...,dm,0,..,0>, que permite a
forma SF0
(SF0) Xi = di + ci,m+1 Xm+1+ ... + ci,m+n Xm+n
com di ≥ 0 para i: 1..m
através de uma combinação linear das suas equações.
29
Interpretação Geométrica
Exemplo:
Dadas R3: 2X1 + X2 ≤ 8 ; R4: X1 + X2 ≥ 3 ; R5: X1 - X2 ≥ -5, a região
admissível é constituída pela intersecção das sub-regiões definidas por
cada uma das restrições.
X2
X1 - X2 - X5 = -5
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1
30
Interpretação Geométrica
Na realidade, pretendendo-se a não-negatividade de X1 e X2, deverão
ser consideradas mais 2 restrições
R1: X1 ≥ 0
R2: X2 ≥ 0
e
A região admissível é constituída pela intersecção das sub-regiões
definidas pelas 5 restrições {R1, R2, R3, R4, R5}.
X2
X1 - X2 = -5
X1 = 0
2 X1 + X2 = 8
X1
X1 + X2 = 3
X2 = 0
31
Interpretação Geométrica
Cada uma das rectas correspondentes a uma restrição pode ser
identificada pelo anulamento da correspondente variável de desvio.
X1 - X2 ≥ -5
X1 - X2 - X5 = -5
X2
X1 - X2 = -5
X5 = 0
X1 = 0
2X1 + X2 ≤ 8
2 X1 + X2 + X3 = 8
2 X1 + X2 = 8
X3 = 0
X4 = 0
X1
X1 + X2 = 3
X1 + X2 ≥ 3
X1 + X2 - X4 = 3
X2 = 0
32
Interpretação Geométrica
A intersecção de quaisquer duas rectas, define um potencial vértice da
região admissível, e é obtida pelo anulamento de 2 (das 5 variáveis).
X2
X1 = 0
X5 = 0
X4 = 0
X5 = 0
X2 = 0
X5 = 0
X1 = 0
X3 = 0
X3 = 0
X5 = 0
X5 = 0
X1 = 0
X3 = 0
X1 = 0
X4 = 0
X4 = 0
X2 = 0
X1 = 0
X2 = 0
X2 = 0
X4 = 0
X2 = 0
X3 = 0
X1
X3 = 0
X4 = 0
33
Interpretação Geométrica
Neste caso temos um sistema de 3 igualdades a 5 variáveis (2 variáveis
de decisão, X1 e X2, e 3 variáveis de desvio (X3 , X4 e X5 e ).
2 X1 + X2 ≤ 8
X1 + X2 ≥ 3
X1 - X2 ≥ -5
X1 , X2 ≥ 0
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1 - X2 - X5 = -5
Existem naturalmente 10 combinações de variáveis 2 a 2. O anulamento
de quaisquer 2 variáveis, corresponde a um vértice potencial da região
admissível.
Esse anulamento corresponde igualmente a uma escolha de variáveis
não básicas, e a uma potencial forma SF0 do sistema inicial.
Apenas as formas SF0 potenciais em que os coeficientes livres são não
negativos correspondem a formas SF0 reais (e reais vértices da região
admissível).
34
Interpretação Geométrica
X2 = 8 - 2 X1 - X3
X4 = 5 - X1 - X3
X5 = -3 + 3 X1 + X3
X2 = 5 + X1 - X5
X3 = 3 - 3 X1 + X5
X4 = 2 + 2 X1 - X5
X2
x1 = 1 - x3/3 + x5/3
x2 = 6 - x3/3 - 2 x5/3
x4 = 4 - 2 x3/3 - X5/3
2 X1 + X2 ≤ 8
X1 + X2 ≥ 3
X1 - X2 ≥ -5
X1 , X2 ≥ 0
X5 = 0
X1 = 0
X3 = 0
X1 =-1 + X4/2 + X5/2
X2 = 4 + X4/2 - X5/2
X3 = 6 - 3 X4/2 - X5/2
X3 = 8 - 2 X1 - X2
X4 = -3 + X1 + X2
X5 = 5 + X1 - X2
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1 - X2 - X5 = -5
X4 = 0
X1
X2 = 0
X1 = 3 - X2 + X4
X3 = 2 + X2 - 2 X4
X5 = 2 - 2 X2 + X4
X1 = 5 - X3 - X4
X2 = -2 + X3 + 2 X4
X5 = 12 - 2 X3 - 3 X4
35
Interpretação Geométrica
A existência de soluções para o conjunto de restrições equivale a que a
região admissível seja não vazia. Um problema em que nenhum vértice
seja admissível é um problema sem solução.
Por exemplo, se nas restrições anteriores se trocarem o sinal das
restrições R3 e R4, o novo sistema
R3’: 2X1 + X2 ≥ 8
R4’: X1 + X2 ≤ 3
R5: X1 - X2 ≥ -5
R3’: 2X1 + X2 -X3 = 8
ou
R4’: X1 + X2 +X4 = 3
R5: X1 - X2 -X5 = -5
corresponde a um problema que é impossível e não tem qualquer
solução.
36
Interpretação Geométrica
X2 = 8 - 2 X1 + X3
X4 = -5 + X1 - X3
X5 = -3 + 3 X1 - X3
X2 = 5 + X1 - X5
X3 = -3 + 3 X1 - X5
X4 = -2 - 2 X1 + X5
X2
x1 = 1 + x3/3 + x5/3
x2 = 6 + x3/3 - 2 x5/3
x4 = -4 - 2 x3/3 + x5/3
2 X1 + X2 ≥ 8
X1 + X2 ≤ 3
X1 - X2 ≥ -5
X1 , X2 ≥ 0
X5 = 0
X1 = 0
X3 = 0
X1 = -1 - X4/2 + X5/2
X2 = 4 - X4/2 - X5/2
X3 = -6 - 3 X4/2 + X5/2
X3 = - 8 + 2 X1 + X2
X4 = 3 - X1 - X2
X5 = 5 + X1 - X2
2 X1 + X2 - X3 = 8
X1 + X2 + X4 = 3
X1 - X2 - X5 = -5
X4 = 0
X1
X2 = 0
X1 = 3 - X2 - X4
X3 = -2 - X2 - 2 X4
X5 = 2 - 2 X2 - X4
X1 = 5 + X3 + X4
X2 = -2 - X3 - 2 X4
X5 = 12 + 2 X3 + 3 X4
37
Passagem para a Forma Resolvida SF0
Para avaliar a satisfazibilidade de um problema basta pois verificar que
pelo menos um dos potenciais vértices corresponde a uma solução.
Mas isso corresponde a colocar o sistema de restrições na forma SF0.
Por exemplo, o vértice admissível
X1 = 1 -
X3/3 +
X2 = 6 -
X3/3 - 2 X5/3
X4 = 4 - 2 X3/3 -
X5/3
X5/3
Corresponde à reescrita na forma SF0 do sistema inicial
2 X1 + X2 ≥ 8
X1 + X2 ≤ 3
X1 - X2 ≥ -5
2 X1 + X2 - X3 =
ou
X1 + X2 + X4 =
8
3
X1 - X2 - X5 = -5
38
Passagem para a Forma Resolvida SF0
Para colocar um sistema de m restrições de igualdade a m+n variáveis
(possivelmente proveniente de um sistema de m restrições de
desigualdade ≤ ou ≥ ) na forma SF0, basta pois
1. Escolher m variáveis como variáveis básicas
2. Reescrever o sistema nessa base
3. Verificar se os coeficentes livres (valor das variáveis básicas
quando as não básicas se anulam) são não negativos
O problema desta abordagem é a existência de um número muito
elevado (combinações de m+n, n a n,
) de possibilidades de
m+n
escolha da base.
C
m
A escolha é trivial no caso em que todas as restrições são do tipo
ai1 X1 +...+ ain Xn ≤ bi
com bi >= 0
em que as variáveis não básicas são as de decisão (X1 a Xn) já que a
solução Xi = 0 ( 1  i  n) é admissível (pois 0  bi).
39
Conversão em SF0 - Simplex
No caso mais geral em que as restrições são do tipo  ou  coloca-se
aquestão de garantir a passagem eficiente de um conjunto de restrições
lineares sobre variáveis não negativas para uma forma resolvida SF0,
se existir, sem escolha arbitrária dos vértices (variáveis básicas).
Por outro lado, se se pretender a integração dum resolvedor de
restrições simbólicos num sistema de programação em lógica (CLP)
esse resolvedor deve ser incremental.
Há pois que definir um procedimento eficiente e incremental para
efectuar essa transformação.
Na prática, há que definir uma estratégia para escolher eficientemente
as variáveis básicas e as não básicas.
Uma solução possível, geralmente utilizada, é esencialmente baseada
no algoritmo SIMPLEX.
40
Optimização em SF0
Há pois que definir uma estratégia para determinar quais as variáveis
que devem entrar na base.
Essa estratégia é fácil de entender se se pretender não apenas verificar
a satisfação de um conjunto de restrições, mas ainda a optimização de
uma função objectivo, que tal como as restrições seja linear.
Assim, assumamos que, dado um conjunto de m restrições de igualdade
nas variáveis X1 a Xm+n,, já colocado na forma SF0, se pretende
adicionalmente maximizar (o caso da minimização é semelhante) uma
função
max F = c1 X1 + c2 X2 + ... + Cm+n Xm+n
41
Optimização em SF0
max F = c1 X1 + c2 X2 + ... + Cm+n Xm+n
Sem perda de generalidade, consideremos que as primeiras m variáveis
X1 a Xm são as variáveis básicas, isto é, que as restrições foram
reescritas na forma SF0
X1 = d1+ c11 Xm+1 +...+ c1n Xm+n
...
Xm = dm+ cm1 Xm+1 +...+ cmn Xm+n
Substituindo na função F as variáveis básicas pelas suas expressões
nas não básicas obtemos
max F = k + k1 Xm+1 + k2 Xm+2 + ... + kn Xm+n
42
Optimização em SF0
max F = k + k1 Xm+1 + k2 Xm+2 + ... + kn Xm+n
Esta expressão mostra que no vértice definido pelas variáveis básicas
(com as não-básicas nulas) a função a maximizar tem o valor k.
Mostra ainda que, se todos os coeficientes ki forem negativos, não se
pode obter maiores valores de F.
No caso de haver coeficientes ki positivos, um aumento da variável
correspondente aumenta o valor da função F.
Quanto maior o coeficiente, maior o aumento da função objectivo por
aumento unitário da variável.
43
Optimização em SF0
max F = k + k1 Xm+1 + k2 Xm+2 + ... + kn Xm+n
Numa perspectiva de optimização, dada uma certa base admissível,
para a qual existam valores ki positivos, o valor da função objectivo pode
ser melhorado (ser maior que k) tornando positiva as correspondentes
variáveis não básicas.
Mas para mantermos o sistema na forma SF0, se se “desanula” uma
variável não-básica, essa situação deverá ser compensada anulando
uma das variáveis básicas.
Assim, a estratégia de optimização a seguir é a de, partindo de uma
base admissível, proceder a um conjunto de mudanças de base até se
poder reescrever a função objectivo com coeficientes exclusivamente
não negativos.
44
Optimização em SF0
Obviamente, uma mudança de base, envolve a escolha de
a)
uma variável não básica para entrar na base, e
b)
uma variável básica para sair da base,
A escolha da variável de entrada pode seguir a heurística delineada
atrás:
A variável de entrada é aquela a que corresponde na função objectivo o
coeficiente mais positivo (maximização) ou mais negativo (minimização).
Uma vez escolhida a variável de entrada, ela deverá aumentar tanto
quanto possível. No entanto, na forma SF0 corrente, um aumento dessa
variável poderá conduzir à diminuição das variáveis básicas.
45
Optimização em SF0
Com efeito, tome-se a forma SF0 abaixo e, sem perda de generalidade,
considere-se Xm+1 como variável de entrada.
max
F = k + k1 Xm+1 + k2 Xm+2 + ... + kn Xm+n
suj.
Xi = di + ci1 Xm+1 +...+ cin Xm+n
i:1..m
Mantendo as outras variáveis não básicas nulas, as equações
reescrevem-se como
Xi = di + ci1 Xm+1
i:1..m
Assim, sendo di ≥ 0, um aumento de Xm+1 anula as variáveis básicas
(em que ci1< 0), quando tomar o valor di/|ci1|.
Como se pretende anular uma variável básica, mantendo as outras não
negativas, a escolha da variável de saída recai na variável básica Xi
para a qual seja menor o valor di/|ci1|.
46
Optimização em SF0
Resumindo, a maximização da função objectivo de um sistema de m
igualdades a m+n variáveis envolve a escrita do sistema e da função
objectivo na forma SF0
max
F = k + k1 Xm+1 + k2 Xm+2 + ... + kn Xm+n
suj.
Xi = di+ ci1 Xm+1 +...+ cin Xm+n
i:1..m
e a execução do seguinte algoritmo:
 Enquanto a função objectivo tiver coeficientes positivos mudar
a base escolhendo
• como variável de entrada a variável não básica Xj com
coeficiente kj mais positivo na função objectivo
• como variável de saída a variável básica i com cij < 0 e menor
valor di/|cij| na respectiva restrição
47
Interpretação Geométrica
Do ponto de vista geométrico, e como visto atrás, cada forma SF0
corresponde a um vértice da região admissível.
Assim, ao trocar uma variável básica por outra não básica este
algoritmo vai percorrendo vários vértices da região admissível, com
valores crescentes da função objectivo.
Por apenas trocarem uma variável, dois vértices consecutivos estão
unidos por uma aresta do hiper-poliedro que representa a região
admissível.
48
Interpretação Geométrica
Exemplo:
Max X1 +
2X2
R1: -X1 + 3X2 ≤
R2:
9
X1 +
X2 ≤ 11
R3: 2X1 +
X2 ≤ 18
X1 ,X2 ≥ 0
49
Interpretação Geométrica
Exemplo:
Max X1 +
2X2
-X1 + 3X2 + X3 =
9
X1 +
X2 + X4 = 11
2X1 +
X2 + X5 = 18
X1 ,X2 ≥ 0
Max
X3 =
X1 + 2X2
9 + X1 - 3X2
→
9/3
X2
→ 11/1
X5 = 18 - 2X1 - X2
→ 18/1
X4 = 11 - X1 -
entra X2, sai X3
50
Interpretação Geométrica
Max X1 +
Exemplo.
X3 =
2X2
9 + X1 - 3X2
→
9/3
X2
→ 11/1
X5 = 18 - 2X1 - X2
→ 18/1
X4 = 11 - X1 -
entra X2, sai X3
Max
6 + 5X1/3 - 2X3/3
X2 =
3 +
X1/3 - X3/3 →
9
X4 =
8 - 4X1/3 + X3/3 →
6
X5 = 15 - 7X1/3 + X3/3 → 45/7
entra X1, sai X4
51
Interpretação Geométrica
Exemplo.
Max
6 + 5X1/3 - 2X3/3
X2 =
3 +
X4 =
8 - 4X1/3 + X3/3
X1/3 - X3/3
X5 = 15 - 7X1/3 + X3/3
entra X1, sai X4
Max 16 - X3/4 - 5X4/4
X1 = 6 + X3/4 - 3X4/4
X2 = 5 + X3/12-
X4/4
X5 = 1 -7X3/12+ 7X4/4
óptimo encontrado
52
Optimização em SF0
Este algoritmo de optimização pressupõe que, no início, o conjunto de
restrições foi reescrito na forma SFO, que era exactamente o objectivo
que nos levou a abordar o problema da optimização!
Na realidade, como vimos, a colocação na forma SF0 não levanta
qualquer problema quando as m restrições de igualdade a m+n
variáveis provêm de um conjunto de m restrições de desigualdade
ai1 X1 + ai2 X2 + ... + ain Xn =< bi , bi ≥ 0 para i: 1..m
em que todos os bi são não negativos (basta escolher as variáveis X1 a
Xn para variáveis não básicas, pois o seu anulamento satisfaz as
restrições!).
A questão coloca-se pois numa situação em que, para algum i, existe
uma restrição do tipo
ai1 X1 + ai2 X2 + ... + ain Xn >= bi , bi ≥ 0
53
Passagem para a Forma Resolvida SF0
Nestas condições, a restrição Ri pode colocar-se na forma
ai1 X1 + ai2 X2 + ... + ain Xn - Si = bi , bi ≥ 0
ou, equivalentemente
Si = -bi + ai1 X1 +...+ ain Xn
Pode agora introduzir-se uma variável artificial não negativa, Zi, na
restrição, obtendo-se
Si - Zi = -bi + ai1 X1 +...+ ain Xn
O que permite escrever a equação na forma
Zi = bi + Si - ai1 X1 -...- ain Xn
54
Passagem para a Forma Resolvida SF0
Zi = bi + Si - ai1 X1 -...- ain Xn
Esta equação tem duas propriedades importantes
1.
É equivalente à restrição inicial se fôr Zi = 0.
2.
É satisfeita quando as variáveis de decisão, e a variável de
desvio, são nulas.
Desta forma, se uma solução admissível do sistema modificado é uma
solução do sistema inicial se Zi = 0, tudo o que é necessário fazer é,
converter o sistema modificado, num outro equivalente, mas com Zi = 0.
Na prática, sendo Zi não negativo, este objectivo corresponde a
minimizar Zi, ou, equivalentemente, maximizar – Zi.
Este procedimento pode naturalmente ser generalizado.
55
Passagem para a Forma Resolvida SF0
Dado um conjunto m de restrições de igualdade a m+n variáveis, a
passagem à forma SF0 pode fazer-se nos seguintes passos
1.
Escolhem-se m variáveis para variáveis básicas, e reescreve-se o
sistema isolando as variáveis básicas
Xi = bi+ ci1 Xm+1 +...+ cin Xm+n
2.
Se todos os bi forem não negativos, o sistema está na forma SFO.
Caso contrário, introduzem-se variáveis artificiais nas restrições
adequadas, reescrevendo-as em
Zi = - di+ ci1 Xm+1 +...+ cin Xm+n - Xi
3.
Finalmente minimiza-se a soma das variáveis artificiais.
Naturalmente, se o mínimo fôr 0, no ponto de mínimo todas as variáveis
artificiais são nulas. Neste caso, e em princípio, estas variáveis serão
não básicas no sistema obtido e poderão ser simplesmente eliminadas
do sistema.
56
Interpretação Geométrica
Ao introduzir-se uma variável artificial introduz-se uma nova dimensão
no problema.
– Por exemplo, se o problema inicial tinha duas dimensões, X e Y,
pode considerar-se a nova variável como a 3ª dimensão, Z.
O problema inicial, pode considerar-se a intersecção do problema
estendido com o espaço inicial.
– Por exemplo, em 2D, o problema inicial é a intersecção do
problema estendido (3D) com o plano X-Y.
Embora para o problema inicial Xi=0 não seja solução, no problema
estendido, o ponto Xi=0 , Z > 0 é uma solução.
A minimização de Z vai induzir um percurso no hiper-poliedro até atingir
o espaço inicial (em 2D, o plano X-Y).
57
Interpretação Geométrica
Exemplo.
-X1 + 3X2 ≤ 9
-X1 + 3X2 + X3 =
9
X1 +
X2 ≤ 11
X1 +
X2 + X4 = 11
2X1 +
X2 ≤ 18
2X1 +
X2 + X5 = 18
X1 + 2X2 ≥ 12
X1 + 2X2 - X6 = 12
Xi ≥ 0
X3 =
9 + X1 - 3X2
X4 =
11 - X1 -
X2
X5 =
18 -2X1 -
X2
X6 = -12 + X1 + 2X2
58
Interpretação Geométrica
Exemplo
X3 =
X4 =
X5 =
9 + X1 - 3X2
11 - X1 - X2
18 -2X1 - X2
X6 = -12 + X1 + 2X2 + Z1
min Z1 = 12 - X1 - 2X2 + X6
X3 = 9 + X1 - 3X2
X4 = 11 - X1 - X2
X5 = 18 -2X1 - X2
Z1 = 12 - X1 - 2X2 + X6
Projecção no plano X1-X2 do ponto <X1, X2, Z1> = <0, 0, 12>
59
Interpretação Geométrica
Exemplo
min
X6
X3 =
X4 =
X5 =
Z1 =
Z1 = 12 - X1 - 2X2 +
9
11
18
12
+ X1
- X1
-2X1
- X1
- 3X2
- X2
- X2
- 2X2 + X6
min 6 - 7X1/3 X2 = 3 + X1/3
X4 = 8 - 4X1/3
X5 = 15 - 7X1/3
Z1 = 6 - 8X1/3
2X3 /3 + X6
- X3/3
+ X3
+ X3/3
+ 2X3/3 + X6
Projecção no plano X1-X2 do ponto <X1, X2, Z1> = <0, 3, 6>
60
Interpretação Geométrica
Exemplo
min 6 - 7X1/3 X2 = 3 + X1/3
X4 = 8 - 4X1/3
X5 = 15 - 7X1/3
Z1 = 6 - 8X1/3
2X3 /3 + X6
- X3/3
+ X3
+ X3/3
+ 2X3/3 + X6
min Z1
21/5
X1 = 18/5 + 2X3/5 + 3X6/6 -3Z1/5
X2 = 21/5 -
X3/5 +
X6/5 - Z1/5
X4 = 16/5 -
X3/5 - 4X6/5 +4Z1/5
X5 = 33/5 - 3X3/5 - 7X6/5 +7Z1/5
18/5
O ponto <18/5, 21/5, 0> já está no plano X1-X2
61