Restrições Não-Estritas / Variáveis Arbitrárias
• Analisemos agora a situação em que no conjunto de restrições
lineares algumas variáveis podem tomar valores reais/racionais
arbitrários.
• Tal como no caso anterior, substituem-se todas as desigualdades por
igualdades com variáveis de desvio não negativas.
• Desta forma, um sistema de m restrições lineares com n variáveis é
transformado num sistema de m equações a m+n variáveis.
• Algumas das variáveis podem tomar um valor real arbitrário, enquanto
outras (as variáveis de desvio e eventualmente algumas variáveis de
decisão) só podem tomar valores não negativos.
• Para as distinguir, vamos renomear essas variáveis como Z e S, em
número de z e s, respectivamente (z + s = m + n)
1
Restrições Não-Estritas / Variáveis Arbitrárias
Se o número de variáveis reais não fôr inferior ao número de restrições
(z ≥ m), e sendo assumido que os coeficientes das variáveis das
restrições são linearmente independentes (como será sempre
assumido), o sistema é sempre possível.
Com efeito, é sempre possível reescrever as equações isolando m
variáveis arbitrárias (as variáveis básicas-Z; sem perda de generalidade,
consideramos serem Z1 a Zm,)
Zi = ci + pi,m+1Zm+1 +...+ pi,zZz + qi1S1 +...+ qi,sSs
Como as Zi são arbitrárias, uma solução é
Zi = ci
para i: 1..m
Zi = 0
para i: m+1..z
Sj = 0
para j: 1..s
2
Restrições Não-Estritas / Variáveis Arbitrárias
• Havendo mais restrições m do que as z variáveis reais (m > z),
podemos isolar os Zi em z das m restrições, obtendo
Zi =
ci + qi,1S1 + ... + qi,sSs
para i: 1..m
• Quaisquer que sejam os valores, não negativos, atribuídos às
variáveis Si, estas restrições são satisfeitas já que é possível atribuir
valores arbitrários às variáveis Zi.
• As restantes restrições constituem um conjunto de (m – z) equações a
s = m – z + n variáveis não negativas. Como visto anteriormente,
estas restrições são satisfazíveis sse se puderem reescrever na forma
resolvida SF0.
• Assim, quando as restrições não estritas envolvem variáveis
arbitrárias, pode definir-se uma forma resolvida SF1 por extensão de
SF0.
3
Forma Resolvida SF1 (Igualdades)
Definição: Um sistema de m restrições de igualdade envolvendo z
variáveis arbitrárias e s variáveis não negativas está na forma resolvida
SF1 se as suas restrições se dividirem nos conjuntos Ea e Es, sendo:
• Se z ≥ m, Es é vazio e Ea constituído por m equações
Zi = di + pi,m+1Zm+1 +...+ pi,zZz + qi,1S1 + ... + qi,sSs
onde as variáveis do lado esquerdo são as variáveis básicas-Z, e todas
as outras variáveis são não básicas.
• Se z < m o conjunto Es é constituido por m - z equações
Si = ci + ri,m-z+1Sm-z+1 +...+ ri,sSs com ci≥0 para i:1..m-z
em que, no lado esquerdo, as variáveis básicas-S são definidas em
função das variáveis não básicas-S. Ea é constituido por z equações
Zi = di + ri,m-z+1Sm-z+1 + ... + ri,sSs
em que as variáveis básicas-Z são igualmente definidas exclusivamente
em função de variáveis não básicas-S.
4
Forma Resolvida SF1 (Igualdades)
Exemplo:
Eliminando-se o requisito de não negatividade de X1 e X2 as
restrições
X2
2 X1 + X2 ≤ 8
X1 + X2 ≥ 3
X1 - X2 ≥ -5
X5 = 0
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1 - X2 - X5 = -5
admitem como forma resolvida SF1
X3 = 0
X4 =
0
Ea:
X1 = 5 - X3 X4
X2 = -2 + X3 + 2 X4
Es:
X5 = 12 - 2 X3 - 3 X4
5
Forma Resolvida SF1 (Igualdades)
Teorema: Um sistema de m equações a m+n variáveis arbitrárias e/ou
não negativas é satisfazível sse puder rescrever na forma SF1.
Demonstração:
 Se um sistema se pode escrever na forma SF1 então é satisfazível
Trivial. Anulando as variáveis não básicas obtem-se uma solução
 Se um sistema é satisfazível pode escrever-se na forma SF1.
Escolham-se arbitrariamente as variáveis básicas-Z. Se z ≥ m, as m
equações constituem o sistema Ea (sendo Es vazio). Se z < m, então
considerem-se z equações para formar Ea. Nas restantes equações
eliminando-se as variáveis arbitrárias (segundo Ea), obtem-se um
sistema apenas em variáveis não-negativas. Sendo o sistema inicial
satisfazível também este sistema apenas em variáveis não negativas o
será, podendo pois ser colocado na forma SF0, e corresponde ao
conjunto Es.
6
Restrições Estritas / Variáveis Arbitrárias
Se o conjunto de restrições envolver restrições estritas (<, > e ≠) é
possível reescrever estas restrições em termos não só de igualdades
mas também de desigualdades como abaixo (em que os si ≥ 0).
ai1 X1 +...+ ain Xn ≤ bi  ai1 X1 +...+ ain Xn + Si = bi
ai1 X1 +...+ ain Xn < bi  ai1 X1 +...+ ain Xn + Si = bi
ai1 X1 +...+ ain Xn
≠ bi
ai1 X1 +...+ ain Xn ≥ bi  ai1 X1 +...+ ain Xn - Si = bi
ai1 X1 +...+ ain Xn > bi  ai1 X1 +...+ ain Xn - Si = bi
ai1 X1 +...+ ain Xn
≠ bi
Obtém-se desta forma um sistema de equações (=) e de disequações
(≠), em que algumas (eventualmente todas as) variáveis são não
negativas.
7
Restrições Estritas / Variáveis Arbitrárias
As disequações são satisfazíveis sempre que as suas variáveis não
sejam fixas (constantes).
A conversão na forma resolvida SF1 permite verificar que o conjunto de
equações é satisfazível, e definir as variáveis básicas em termos das
variáveis não básicas.
Em geral, as variáveis não-básicas aparecem no lado direito das
equações de Ea e Es, e podem tomar, para além do valor 0, vários
valores na sua vizinhança.
Si = ci + ri,m-z+1 Sm-z+1 +...+ ri,s Ss
ci ≥ 0
Escrevendo as disequações exclusivamente em função das variáveis
não básicas, elas serão satisfazíveis se contiverem pelo menos uma
variável não fixa.
Assim, devemos concentrar-nos nas equações, e verificar se elas
impõem ou não a fixação de variáveis não básicas.
8
Restrições Estritas / Variáveis Arbitrárias
• Caso z ≥ m:
Não havendo mais restrições que variáveis arbitrárias, basta
escolher m variáveis arbitrárias para básicas, obtendo-se assim um
conjunto Es vazio e Ea constituído por m equações
Zi = di + pi,m+1Zm+1 +...+ pi,zZz + qi,1S1 + ... + qi,sSs
Quaisquer valores arbitrários das m-n variáveis não básicas-Z (as
variáveis Zi com i: m+1 .. z) e valores não-negativos das s variáveis
não básicas-S (sj com j: 1 .. s), conduzem a valores das variáveis
básicas-Z dentro do seu domínio (arbitrário).
Donde, se z ≥ m, as variáveis não básicas não são fixadas e as
disequações são sempre satisfazíveis.
9
Restrições Estritas / Variáveis Arbitrárias
• Caso z < m:
Neste caso todas as variáveis arbitrárias são básicas, originando um
conjunto Ea é constituido por z equações
Zi = di + ri,m-z+1Sm-z+1 +...+ ri,sSs
Uma vez obtido Ea, continuam a existir m-z equações nas s variáveis
não-negativas (sendo s > m-z). Assim, a análise da fixação de
variáveis é análoga ao caso em que não há variáveis arbitrárias.
Para simplificar a notação, vamos estudar o caso de um sistema de
m equações a m+n variáveis não negativas.
10
Restrições Estritas / Variáveis Arbitrárias
Consideremos pois um conjunto Es constituido por
Si = ci + ri,m+1Sm+1 +...+ ri,m+nSm+n
ci ≥ 0 ( i:1.. m)
No conjunto Es há que verificar-se se, para além dos valores nulos das
variáveis Sm+j (j: 1.. n) não básicas-S, existem outros valores que não
tornem negativas as variáveis básicas-S.
Se todos os ci forem positivos, existem vizinhanças εi de 0 para as
variáveis não básicas-S que mantêm as variáveis básicas-S não
negativas.
Assim se todos os ci forem positivos não há variáveis não básicas-S
(nem básicas-S) fixadas e, se existirem disequações nessas variáveis,
essas disequações são satisfazíveis.
11
Restrições Estritas / Variáveis Arbitrárias
Se alguns ci forem nulos, não há garantia de haver essas vizinhanças.
Um exemplo permite clarificar este ponto.
Exemplo: Verificar que, para S1 e S2 não negativos, são insatisfazíveis
as restrições
S1 - S2 ≤ 0
; S1 - S2 ≥ 0
e S1 - S2 ≠ 0
Reescrevendo as restrições como equações, obtem-se
S1-S2+S3 = 0 ; S1-S2-S4 = 0
e S1 - S2 ≠ 0
Escolhendo variáveis básicas-S, S3 e S4,, a forma SF1 é
S3 = 0-S1+S2
e
S4 = 0+S1-S2
com a desigualdade S1-S2≠ 0 escrita em função das variáveis (S1 e S2)
não básicas-S.
12
Restrições Estritas / Variáveis Arbitrárias
Aparentemente o sistema é satisfazível, pois foi possível escrever as
equações na forma SF1 e colocar a disequação em termos das
variáveis não básicas-S.
No entanto, uma análise mais cuidada permite verificar que as variáveis
S1 e S2 têm um valor fixo de 0, o que torna impossível a disequação.
Com efeito, somando as duas equações de Es,
S3 = 0-S1+S2
e
S4 = 0+S1-S2
obteríamos S3 + S4 = 0.
Sendo S3 e S4 variáveis não negativas, ambas devem ser nulas. Assim
sendo, por qualquer das equações de Es se obteria S1 = S2, pelo que
a disequação
S1 - S2 ≠ 0
não é satisfazível.
13
Restrições Estritas / Variáveis Arbitrárias
S1-S2+S3 = 0 ; S1-S2-S4 = 0
Escolhendo outra combinação de variáveis básicas-S (S1, S3 e S4)
poderíamos ter reescrito a forma SF1 como
S1 = S2 ;
S3 = 0
e
S4 = 0
Eliminando a variável básica S1, da disequação
S1 - S2 ≠ 0
... obtemos
S2 - S2 ≠ 0
... que se simplifica para a desigualdade trivial
0 ≠ 0
... e que torna evidente a insatisfazibilidade da restrição de
desigualdade.
14
Restrições Estritas / Variáveis Arbitrárias
Analisando a razão pela qual a fixação de variáveis não foi detectada
na primeira forma SF1, pode constatar-se que o problema reside na
utilização de uma expressão
-S1 +S2
e da sua simétrica
S1- S2
no lado direito de equações do conjunto Es da forma SF1 em que os
termos independentes eram nulos.
S3 = -S1+S2
e
S4 = S1-S2
É para impedir estas situações que se define a forma SF2 (para o caso
m > z) com uma condição adicional em relação à forma SF1.
15
Forma Resolvida SF2
Definição SF2: Um sistema m restrições = e ≠, com z variáveis
arbitrárias (z < m) e s+t (s = m-z) variáveis não negativas está na forma
resolvida SF2 se as suas restrições se dividirem nos seguintes
conjuntos, Ea ,Es, D:
D: O conjunto D é constituido por desigualdades do tipo
ri,1T1 +...+ri,tTt ≠ ai
sendo um dos termos ri,t não nulo. As t variáveis Tj são as variáveis não
básicas-S.
Ea: O conjunto Ea é constituido por z igualdades
Zi = di + pi,1T1 +...+ pi,tTt
sendo as variáveis arbitrárias Zi ,variáveis básicas-Z.
16
Forma Resolvida SF2
Definição SF2 (cont.):
Es: O conjunto Es é constituido por s = m-z igualdades do tipo
Si = ci+qi,1T1 +...+qi,tTt
com ci ≥ 0
para i:1..s
em que as variáveis Si e Tj, respectivamente básicas-S e não
básicas-S, são variáveis não negativas.
Condição adicional (não existente em SF1):
• Para as variáveis Tj, não básicas-S, define-se uma ordem arbitrária
pela qual elas devem ser escritas nas igualdades.
• Nestas igualdades, ou o termo ci é positivo ou, sendo ci=0, o
primeiro coeficiente ri,j não nulo deve ser positivo.
As condições impostas no conjunto Es garantem que qualquer variável
não negativa que deva tomar valores fixos é considerada como variável
básica-S na forma SF2, permitindo explicitar as variáveis fixas.
17
Forma Resolvida SF2
Teorema: A forma resolvida SF2 detecta as variáveis fixas, como variáveis
básicas-S.
Consideremos para as igualdades de Es
Si = ci + qi,1 T1 +...+ qi,tTt
a seguinte partição
Es = F  R
e
R = R0  R1  ...  Rt
em que
• a F pertencem todas as restrições com qi,t= 0;
• a R0 pertencem as outras restrições com ci > 0;
• a Rk (1  k  t) pertencem todas as outras restrições, com ci = 0,
e em que o primeiro coeficiente não nulo (donde, positivo) é qi,k.
As variáveis básicas Si pertencentes às restrições de F são fixas.
A demonstração de que não há mais variáveis básicas fixas pode ser feita
por indução nos conjuntos Ri, mostrando que em nenhum nível i existem
variáveis (básicas ou não básicas) fixas.
18
Forma Resolvida SF2
Caso Base (j = 0):
Para R = R0, façamos
ε = mini ci/(|qi,1|+...+|qi,t|)
Em cada restrição Si = ci + qi,1 T1 +...+ qi,tTt , se as
variáveis não básicas Tj tomarem valores arbitrários 0 < δ < ε , será
 = |qi,1 δ +...+ qi,t δ| =
= δ (|qi,1 +...+ qi,t|)
≤ δ (|qi,1| +...+ |qi,t|)
≤ δ
ci / ε
= ci (δ /ε )
Mas sendo δ < ε então  tem valor absoluto inferior a Ci. Assim,
para o valor δ > 0 das variáveis não básicas as variáveis não básicas
mantêm-se positivas, pelo que nenhuma das variáveis é fixa!
19
Forma Resolvida SF2
Caso de Indução (k ~> k + 1):
Assumindo que nenhum sistema R0  ...  Rk fixa variáveis, provemos
que nenhum sistema R = (R0  ...  Rk)  Rk+1 as fixa.
Considere-se para o sistema R a partição R = RK  Rk+1.
hipótese de indução, o sistema RK não fixa variáveis pelo que
Pela
• todas as variáveis não básicas Ti (i  K ) não são fixas.
Para analizar as restantes variáveis (tanto as básicas Si como as não
básicas Tj, com j > k) notemos que as restrições (pertencentes a
Rk+1), têm a forma
Si = qi,k+1Tk+1 + qi,k+2Tk+2 +... + qi,tTt (com qi,k+1> 0 )
e façamos, como anteriormente,
 = mini qi,k+1/(|qi,k+2|+...+|qi,t|).
20
Forma Resolvida SF2
Caso de Indução (k ~> k + 1):
Sendo Si = qi,k+1Tk+1 + qi,k+2Tk+2 +... + qi,tTt (com qi,k+1>0),
se escolhermos valores b e g, tais que 0 < b < g <  para as variáveis
não básicas Tj , teremos
Si = qi,k+1 g + qi,k+2 b ... + qi,k+1 b
= qi,k+1 g + b (qi,k+2 + ... + qi,t)
≤ qi,k+1 g + b (| qi,k+2 + ... + qi,t|)
≤ qi,k+1 g + b (| qi,k+2| + ... + | qi,t|)
≤ qi,k+1 (g - b )
pois  = mini qi,k+1 /(|qi,k+2|+...+|qi,t|)
Portanto, nem as variáveis básicas nem as não básicas são fixadas,
pois as básicas podem tomar valores positivos quando as variáveis
não básicas tomam valores positivos arbitrários, b < g < .
21
Passagem à Forma Resolvida SF2
A conversão de um conjunto de restrições lineares na forma SF2, de
uma forma incremental, é explicada através de um exemplo.
R1: -X1 + 3X2 ≤
R2:
9
X1 +
X2 ≤ 11
R3: 2X1 +
X2 ≤ 18
R4: 2X1 -
X2 ≥
2
X1 ,X2 ≥ 0
22
Passagem à Forma Resolvida SF2
Cada restrição é introduzida resolvendo em ordem à variável de desvio.
Assume-se a ordem X1 < X2 < S1 < S2 .. < Sn.
No caso de restrições ≤ nada mais é necessário fazer.
R1: -X1 + 3X2 ≤ 9
 -X1 + 3X2 + S1 = 9

S1 = 9 + X1 - 3X2
R2: X1 + X2 ≤ 11
 X1 + X2 + S2 = 11
 S2 = 11 - X1 - X2
R3: 2X1 + X2 ≤ 18
 2X1 + X2 + S3 = 18
 S3 = 18 - 2X1 - X2
O vértice definido implicitamente é a origem.
23
Passagem à Forma Resolvida SF2
No caso de restrições ≥ a origem não pertence à região admissível,
pelo que há que fazer uma mudança de base (troca de X1 com S4).
S1 = 9 + X1 - 3X2
S2 = 11 - X1 - X2
S3 = 18 - 2X1 - X2
R4: 2X1 - X2 ≥ 2
 2X1 - X2 - S4 = 2
 S4 = -2 + 2X1 - X2
 X1 = 1 + X2/2 + S4/2
Substituindo X1 obtem-se
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
Por “sorte” o termo independente da equação em X1 é positivo e não
acarretou nenhum termo negativo em S1, S2 ou S3.
24
Passagem à Forma Resolvida SF2
Em geral a mudança de base pode fazer-se de uma forma sistemática
por minimização de uma variável artificial (1ª fase do método de 2 fases
do SIMPLEX), que é considerada para além da variávels de desvio.
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
Exemplo:
R5: X1 + 2X2 ≥ 12
 X1 + 2X2 –S5 + Z5 = 12
 Z5 = 12 - X1 - 2X2 + S5
 Z5 = 11 - 5X2/2 - S4/2 + S5
Agora há que minimizar Z5, através de sucessivas mudanças de base.
25
Passagem à Forma Resolvida SF2
Min Z5
S1
S2
S3
X1
Z5
(= 11 - 5X2/2 - S4/2 + S5)
= 10 - 5X2/2 + S4/2
= 10 - 3X2/2 - S4/2
= 16 - 2X2
- S4
= 1 + X2/2 + S4/2
= 11 - 5X2/2 - S4/2 + S5
Como Z5/X2 = -5/2 e Z5/S4 = -1/2 existe um maior
decréscimo de Z5 com X2, pelo que X2 entra na base. Por outro lado,
mantendo-se S4 = S5 = 0,
S1
S2
S3
X1
Z5
=
=
=
=
=
0
0
0
0
0
=
=
=
=
=
10
10
16
1
11
+
–
5X2/2
3X2/2
2X2
X2/2
5X2/2
=>
=>
=>
=>
=>
X2
X2
X2
X2
X2
=
=
=
=
=
4
20/3 (6.666)
8
-2
22/5 (4.4)
pelo que a variável S1 sai da base, já que é a primeira variável a anularse para valores crescentes de X2.
26
Passagem à Forma Resolvida SF2
Por entrada na base de X2, por troca com S1,
Min Z5
S1
S2
S3
X1
Z5
=
=
=
=
=
=
11
10
10
16
1
11
-5X2/2
- 5X2/2
- 3X2/2
- 2X2
+ X2/2
- 5X2/2
+
+
-
S4/2 + S5
S4/2
S4/2
S4
S4/2
S4/2 + S5
+
+
+
+
S4
+
+
-
+ S5
S4/5
4S4/5
7S4/5
3S4/2
S4 + S5
converte-se em
Min Z5
(-)
X2
(5)
S2
(40/7) S
3
(-)
X1
(1)
Z5
=
=
=
=
=
=
1
4
4
8
3
1
S1 2S1/5
3S1/5
4S1/5
S1/5
S1
Continuando a minimização de Z5, e pelo raciocínio anterior, S4 entra da
base, por troca com Z5.
27
Passagem à Forma Resolvida SF2
Por entrada na base de S4, por troca com Z5, obtem-se
Min Z5
X2
S2
S3
X1
Z5
=
=
=
=
=
=
1
4
4
8
3
1
+ S1 - S4 + S5
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/2
+ S1
- S4 + S5
converte-se em
Min Z5
(-)
X2
(5)
S2
(40/7) S
3
(-)
X1
(1)
S4
= 0
= 21/5- S1/5+ S5/5- Z5/5
= 16/5- S1/5– 4S5/5- Z5/5
=
1 - 4S1/5- 7S5/5+ 7Z5/5
= 18/5+ 2S1/5+ 3S5/5– 3Z5/5
=
1 + S1 + S5 - Z5
Tendo-se pois anulado a variável artificial Z5, como pretendido.
28
Passagem à Forma Resolvida SF2
Tendo-se anulado a variável artificial Z5, o sistema pode reescrever-se
eliminando simplesmente esta variável. Assim,
Min Z5 = 0
(-)
X2 = 21/5- S1/5+ S5/5- Z5/5
(5)
S2 = 16/5- S1/5– 4S5/5- Z5/5
(40/7) S3 =
1 - 4S1/5- 7S5/5+ 7Z5/5
(-)
X1 = 18/5+ 2S1/5+ 3S5/5– 3Z5/5
S4 =
1 + S1 + S5 – Z5
(1)
converte-se em
X2
S2
S3
X1
S4
=
=
=
=
=
21/5
16/5
33/5
18/5
1
- S1/5 + S5/5
- S1/5 - 4S5/5
- 3S1/5 - 7S5/5
+ 2S1/5 + 3S5/5
+ S1
+ S5
que se encontra na forma SF2, já que os termos independentes são
positivos (SF1) e não há inequações.
29
Variáveis Fixas em SF2
Se houver lugar à fixação de variáveis, esta é detectada na conversão
para a forma SF2. Esta fixação é ilustrada no seguinte exemplo. Dadas
as 4 primeiras restrições
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
Adicionar a nova restrição:
R6: X1 + 2X2 ≥ 16
 Z6 = 16 - X1 - 2X2
 Z6 = 15 - 5X2/2 - S4/2
Tal como anteriormente, há que minimizar Z6, através de sucessivas
mudanças de base.
30
Variáveis Fixas em SF2
Min Z6
S1
S2
S3
X1
Z6
=
=
=
=
=
=
15
10
10
16
1
15
+
-
5X2/2
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2 + S6
S4/2
S4/2
S4
S4/2
S4/2 + S6
Como anteriormente, Z5/X2 = -5/2 e
existe um maior decréscimo de Z5 com
Igualmente,
S1 = 0 = 10 - 5X2/2 => X2 =
S2 = 0 = 10 - 3X2/2 => X2 =
S3 = 0 = 16 - 2X2
=> X2 =
X1 = 0 = 1 + X2/2 => X2 =
Z6 = 0 = 15 - 5X2/2 => X2 =
Z5/S4 = -1/2, pelo que
X2, e X2 entra na base.
4
20/3 (6.666)
8
-2
6
Sendo igualmente a variável S1 a sair da base.
31
Variáveis Fixas em SF2
Por entrada na base de X2, por troca com S1,
S1
S2
S3
X1
Z6
=
=
=
=
=
10
10
16
1
15
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2
S4/2
S4
S4/2
S4/2 +S6
converte-se em
X2
S2
S3
X1
Z6
=
=
=
=
=
4
4
8
3
5
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/5
+ S1
- S4
+S6
Na minimização de Z6, agora S4 entra da base, por troca ou com Z6 ou
com S2!
32
Variáveis Fixas em SF2
Com efeito, pretendendo-se obter o Min Z6
X2
S2
S3
X1
Z6
=
=
=
=
=
4
4
8
3
5
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/5
+ S1
- S4 + S6
S4 entra na base, e portanto deve verificar-se
X2
S2
S3
X1
Z6
=
=
=
=
=
0
0
0
0
0
=
=
=
=
=
4
4
8
3
5
+ S4/5 => S4
- 4S4/5 => S4
- 7S4/5 => S4
+ 3S4/5 => S4
- S4
=> S4
= -20
=
5
= 40/7 (5.714)
= -5
=
5
Pelo que quer Z6 quer S2 se anulam para S4 = 5.
33
Variáveis Fixas em SF2
Escolhendo S2 para sair da base, por troca com S4,
X2 = 4 - 2S1/5 + S4/5
S2 = 4 + 3S1/5 - 4S4/5
S3 = 8 + 4S1/5 - 7S4/5
X1 = 3 - S1/5 + 3S4/5
Z6 = 5 + S1
- S4 +S6
converte-se em
X2 = 5 S4 = 5 +
S3 = 1 X1 = 6 +
Z6 = 0 +
S1/4
3S1/4
S1/4
S1/4
S1/4
+
S2/4
5S2/4
7S2/4
3S2/4
5S2/4 +S6
Eliminando-se Z6, reescreve-se a equção como
S6 = 0-S1/4-5S2/4
que não está na forma SF2!
34
Variáveis Fixas em SF2
Analisando-se a igualdade S6 = 0-S1/4-5S2/4 e reescrevendo-a
como
S1 + 5S2 + 4 S6 = 0
verifica-se que deve ser
S1 = S2 = S6 = 0
Convertendo-se ...
X2 = 5 - S1/4
S4 = 5 + 3S1/4
S3 = 1 - S1/4
X1 = 6 + S1/4
S6 = 0 - S1/4
-
S2/4
5S2/4
7S2/4
3S2/4
5S2/4
... na forma SF2, evidenciando-se adicionalmente a fixação das
variáveis X1, X2, S3 e S4
S1 = S2 = S6 = 0
X1 = 6
X2 = 5
S4 = 5
S3 = 1
35
Sistemas Impossíveis
Se o conjunto de restrições fôr insatisfazível, esta situação é igualmente
detectada na conversão para a forma SF2, sendo esta feita de uma
forma incremental, como ilustrado no seguinte exemplo. Dadas as 4
primeiras restrições,
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
adicionar a nova restrição:
R7: X1 + 2X2 ≥ 18
 Z6 = 18 - X1 - 2X2
 Z6 = 17 - 5X2/2 - S4/2
Como anteriormente, há que minimizar Z7.
36
Sistemas Impossíveis
Min Z7
S1 =
S2 =
S3 =
X1 =
Z7 =
10
10
16
1
17
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2
S4/2
S4
S4/2
S4/2 + S7
Como anteriormente, Z7/X2 = -5/2 e Z7/S4 = -1/2, pelo que
existe um maior decréscimo de Z7 com X2, e X2 entra na base.
Igualmente,
S1
S2
S3
X1
Z7
=
=
=
=
=
0
0
0
0
0
=
=
=
=
=
10
10
16
1
17
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
=>
=>
=>
=>
=>
X2
X2
X2
X2
X2
=
=
=
=
=
4
20/3 (6.666)
8
-2
34/5 (6.800)
Continuando a ser a variável S1 a sair da base.
37
Sistemas Impossíveis
Por entrada na base de X2, por troca com S1,
S1
S2
S3
X1
Z7
=
=
=
=
=
10
10
16
1
17
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2
S4/2
S4
S4/2
S4/2 + S7
converte-se em
X2
S2
S3
X1
Z7
=
=
=
=
=
4
4
8
3
7
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/5
+ S1
- S4
Na minimização de Z7, agora S4 entra da base, por troca com S2 !
38
Sistemas Impossíveis
Com efeito, pretendendo-se obter o Min Z7
X2
S2
S3
X1
Z7
=
=
=
=
=
4
4
8
3
7
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/5
+ S1
- S4 + S7
S4 entra na base, e portanto deve verificar-se
X2
S2
S3
X1
Z7
=
=
=
=
=
0
0
0
0
0
=
=
=
=
=
4
4
8
3
5
+ S4/5 => S4
- 4S4/5 => S4
- 7S4/5 => S4
+ 3S4/5 => S4
- S4
=> S4
=-20
= 5
= 40/7 (5.714)
= -5
= 7
Pelo que S2 é o primeiro a anular-se para valores crescentes de S4
(para S4 = 5).
39
Sistemas Impossíveis
Saindo S2 da base, por troca com S4,
X2
S2
S3
X1
Z7
=
=
=
=
=
4
4
8
3
7
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/5
+ S1
- S4 + S7
converte-se em
X2
S4
S3
X1
Z7
=
=
=
=
=
5
5
1
6
2
- S1/4 - S2/4
+ 3S1/4 - 5S2/4
- S1/4 - 7S2/4
+ S1/4 - 3S2/4
+ S1/4 + 5S2/4 + S7
Mas esta última restrição, mostra que Z7 tem um valor mínimo de 2, e
portanto não não pode tomar o valor 0. Assim o sistema não se pode
colocar na forma SF2 e é portanto insatisfazível.
40
Sistemas Impossíveis
A conversão na forma SF2 permite ainda detectar Conjuntos Mínimos
de Restrições Insatisfazíveis (Irreducible Impossible Sets).
Estes conjuntos são identificados
pelas suas variáveis de desvio
que podem ser vistas como
“testemunhas”.
Exemplo:
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
-X1 + 2X2 ≥ 10  -X1 + 2X2 -S8 = 10
 X2 = 22/3 + S4/3 +2S8/3
41
Sistemas Impossíveis
Substituindo X2 = 22/3 + S4/3 +2S8/3 na 1ª equação do sistema
abaixo
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
obtemos,
S1 = -25/3 - S4/3 - 5S8/3
que pode ser reescrito como
3S1 + S4 + 5S8 = -25
O que mostra que não só o sistema inicial é impossível, mas que existe
um conjunto mínimo de restrições incompatíveis constituído pelas
restrições R1, R4 e R8.
42
Sistemas Impossíveis
Os conjuntos IIS não são únicos. Substituindo X2 = 22/3+ S4/3 + 2S8/3
na 2ª equação do sistema abaixo,
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
obteríamos igualmente,
S2 = -1 - S4 - S8
que pode ser reescrito como
S2 + S4 + S8 = -1
o que identifica outro conjunto mínimo de restrições incompatíveis
constituído pelas restrições R2, R4 e R8.
43
Sistemas Impossíveis
Outros conjuntos IIS podem permanecer “escondidos” na conversão
para a forma SF2. A restrição obtida anteriormente
S1 = -25/3 - S4/3 - 5S8/3
pode reescrever-se como
S4 = -25- 3S1- 5S8
que, com as anteriores,
X2 = 22/3 + S4/3 +2S8/3
X1 = 1 + X2/2 + S4/2
origina
X1 = -12 -2S1 - 3S8
ou X1 + 2S1 + 3S8 = -12, revelando ainda outro conjunto mínimo
constituído pelas restrições R1, R8 e X1 (>= 0).
44
Sistemas Impossíveis
Igualmente das restrições
X2 = 22/3 + S4/3 +2S8/3
S4 = -25- 3S1- 5S8
obtem-se, com as anteriores,
X2 = 1 - S1 - S8
ou seja
X2 + S1 + S8 = 1,
revelando outro conjunto mínimo constituído pelas restrições explicitas
R1, R8 e pela implícita X2 >= 0.
(De notar que a determinação de todos os conjuntos mínimos é um
problema NP-hard).
45
Restrições Redundantes
É fácil de mostrar que, dado um conjunto de restrições satisfazíveis, se
uma restrição
 ai Xi > K
(  ai Xi - Sc = K)
é impossível, então a restrição
 ai Xi < K
é redundante.
(  ai Xi + Sr = K)
A igualdade
 ai Xi + Sr = K
pode ser analisada igualmente.
Das equações anteriores tira-se Sr + Sc = 0. Se se obtiver uma
condição de impossibilidade Sc +  pj Vj = - C (com C, pj>0) entre a
1ª restrição e as identificadas pelas variáveis Vj, então a 2ª restrição é
redundante face a essas restrições, pois Sr = C +  pj Vj.
46
Restrições Redundantes
Exemplo: Dadas as restrições
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
a restrição
-X1+2X2 ≤ 10
 -X1+2X2 +S9 = 10
é redundante.
Das equações acima tira-se
S1 = -25/3 - S4/3 + 5S9/3

S9 = 5 + 3S1/5 + S4/5
Pelo que a última restrição é redundante face a R1 e R4.
47
Restrições Lineares no SICStus
• As restrições anteriormente referidas podem ser especificadas em
SICStus através de predicados com a sintaxe adaptada
:- use_module(user:library(clpq)).
r0(X1,X2):- {X1 >= 0, X2 >= 0}.
r1(X1,X2):- {-X1 + 3*X2 =< 9}.
r2(X1,X2):- {X1 + X2
=< 11}.
r3(X1,X2):- {2*X1 + X2 =< 18}.
r4(X1,X2):- {2*X1 - X2 >= 2}.
r5(X1,X2):- {X1 + 2*X2 >= 12}.
r6(X1,X2):- {X1 + 2*X2 >= 16}.
r7(X1,X2):- {X1 + 2*X2 >= 18}.
• Os exemplos anteriores podem ser introduzidos para validação.
|?- r0(X,Y), r1(X,Y), r2(X,Y), r3(X,Y).
{X+Y=<11},
{X+1/2*Y=<9},
{X>=0},{Y>=0},
{X-3*Y>= -9} ? ;no
48
Restrições Lineares no SICStus
• A projecção das variáveis não permite apreender a forma SF2 da
resposta. Essa forma será mais facilmente apreendida se se
explicitarem as variáveis de desvio, em restrições equivalentes
s1(X1,X2,S1):s2(X1,X2,S2):s3(X1,X2,S3):s4(X1,X2,S4):s5(X1,X2,S5):s6(X1,X2,S6):s7(X1,X2,S7):•
{-X1 + 3*X2
{X1 + X2
{2*X1 + X2
{2*X1 - X2
{X1 + 2*X2
{X1 + 2*X2
{X1 + 2*X2
+
+
+
-
S1
S2
S3
S4
S5
S6
S7
=
=
=
=
=
=
=
9,
11,
18,
2,
12,
16,
18,
S1
S2
S3
S4
S5
S6
S7
>=
>=
>=
>=
>=
>=
>=
0}.
0}.
0}.
0}.
0}.
0}.
0}.
Agora a questão equivalente tem a resposta “esperada”
|?- s0(X,Y), s1(X,Y,S1), s2(X,Y,S2), s3(X,Y,S3).
{S1=9+X-3*Y},{S2=11-X-Y},{S3=18-2*X-Y},
{X+Y=<11},{X+1/2*Y=<9},{X>=0},{Y>=0},{X-3*Y>= -9}
?
; no
49
Restrições Lineares no SICStus
Outras questões exemplificadas.
• Mudança de base:
| ?- s0(X,Y),s1(X,Y,S1),s2(X,Y,S2),
s3(X,Y,S3),s4(X,Y,S4).
{S4= 16- 2*Y S3},
{S2= 2-1/2*Y +1/2*S3},
{S1= 18-7/2*Y -1/2*S3},
{X=
9-1/2*Y -1/2*S3},
{Y+1/2*S3=<8},{Y+1/7*S3=<36/7},{Y-S3=<4},
{Y>=0}, {S3>=0} ?
; no.
• Neste caso, o SICStus “optou” pelo ponto (X1=9, X2=0), sobre a
restrição R3 (S3 = 0).
• Na explicação atrás, X1 tinha sido arbitrariamente trocado por S4, pelo
que o ponto encontrado foi (X1=9,X2=0), sobre a restrição R4 (S3 = 0).
50
Restrições Lineares no SICStus
Outras questões exemplificadas.
• Optimização de Variáveis:
| ?- s0(X,Y),s1(X,Y,S1),s2(X,Y,S2),
s3(X,Y,S3),s4(X,Y,S4),
s5(X,Y,S5), maximize(Y).
X = 6, Y = 5,
S1 = 0,S2 = 0,S3 = 1,
S4 = 5, S6 = 0 ? ; no.
| ?- s0(X,Y),s1(X,Y,S1),s2(X,Y,S2),
s3(X,Y,S3),s4(X,Y,S4),
s5(X,Y,S5), maximize(X).
X = 8, Y = 2,
S1 = 0, S2 = 0, S3 = 1,
S4 = 5, S6 = 0 ? ; no.
51
Restrições Lineares no SICStus
• Optimização de Expressões:
| ?- s0(X,Y),s1(X,Y,S1),s2(X,Y,S2),
s3(X,Y,S3),s4(X,Y,S4),
s5(X,Y,S5), minimize(3*X+Y).
X = 18/5,
Y = 21/5,
S1 = 0,
S2 = 16/5,
S3 = 33/5,
S4 = 1,
S5 = 0 ? ;
no.
52
Restrições Lineares no SICStus
• A colocação na forma SF2 pode ser obtida por minimização de
S5+Z5 que determina um ponto na restrição R5.
• | ?- s0(X,Y),s1(X,Y,S1),s2(X,Y,S2),
s3(X,Y,S3),s4(X,Y,S4),
z5(X,Y,S5,Z5), minimize(S5+Z5).
X = 18/5, Y = 21/5,
S1 = 0,
S2 = 16/5,
S3 = 33/5,
S4 = 1,
S5 = 0 ? ; no.
onde a restrição R5 é codificada como
z5(X1,X2,S5,Z5):{X1 + 2*X2 + Z5 - S5 = 12, Z5 >= 0,S5 >= 0}.
53
Restrições Lineares no SICStus
• A fixação de variáveis é igualmente detectada.
|?- s0(X,Y), s1(X,Y,S1), s2(X,Y,S2), s3(X,Y,S3),
s4(X,Y,S4), s6(X,Y,S6).
X = 6, Y = 5,
S1 = 0,S2 = 0,
S3 = 1,S4 = 5,
S6 = 0 ? ; no
... ou mais directamente
|?- r0(X,Y),r1(X,Y),r2(X,Y),r3(X,Y),r4(X,Y),r6(X,Y).
X = 6,
Y = 5 ? ; no
54
Restrições Lineares no SICStus
• Naturalmente, a insatisfação é detectada
|?- s0(X,Y), s1(X,Y,S1), s2(X,Y,S2), s3(X,Y,S3),
s4(X,Y,S4), s7(X,Y,S7).
no
... ou equivalentemente
|?- r0(X,Y),r1(X,Y),r2(X,Y),r3(X,Y),r4(X,Y),r7(X,Y).
no
55
Restrições Lineares no SICStus
• No SICSTus é ainda possível obter como termo (utilizável em
posterior “meta-programação”, as restrições avaliadas, através do
predicado pre-definido dump/3.
|?- r0(X,Y), r1(X,Y), r2(X,Y), r3(X,Y),
dump([X,Y],[A,B],C).
C = [A+1/2*B=<9, A+B=<11, B>=0, A-3*B>= -9, A>=0],
{X+Y=<11},
{X+1/2*Y=<9},
{X>=0},
{Y>=0},
{X-3*Y>= -9} ? ;no
• C é uma lista com as restrições definidas em termos das novas
variáveis A e B, que tomam a vez de X e Y. Testes sobre A e B não
afectam os valores de X e Y.
56