Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
1
Restrições Não-Estritas / Variáveis Arbitrárias•Se algumas das variáveis das restrições iniciais 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 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)
2
Restrições Não-Estritas / Variáveis ArbitráriasSe 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 + qi1X1 +...+ qi,sXs
Como as Zi são arbitrárias, uma solução é
Zi = ci para i: 1..m
Zi = 0 para i: m+1..z
Si = 0 para i: 1..s
3
Restrições Não-Estritas / Variáveis Arbitrárias•Havendo mais restrições m do que as z variáveis reais, 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 si, 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 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.
4
Forma Resolvida SF1 (Igualdades)Definição: Um sistema de restrições de igualdade está na forma resolvida SF1 se as suas restrições se dividirem em dois conjuntos Ea e Es definidos como:
•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
sendo as variáveis do lado esquerdo as variáveis básicas-Z, e todas as outras variáveis 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 as variáveis no lado esquerdo são variáveis básicas-S e as outras 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 definidas exclusivamente em função de variáveis não básicas-S.
5
Forma Resolvida SF1 (Igualdades)Exemplo:
X2
X3 = 0
X5 = 0
X4 = 0
Eliminando-se o requisito de não negatividade de X1 e X2 as restrições
admitem como forma resolvida SF1
X1 = 5 - X3 - X4 X2 = -2 + X3 + 2 X4
X5 = 12 - 2 X3 - 3 X4
Ea:
Es:
2 X1 + X2 ≤ 8 X1 + X2 ≥ 3 X1 - X2 ≥ -5
2 X1 + X2 + X3 = 8 X1 + X2 - X4 = 3 X1 - X2 - X5 = -5
6
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. Se fôr satisfazível pode ser colocado na forma SF0, e corresponde ao
conjunto Es.
7
Restrições Estritas / Variáveis ArbitráriasSe 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 indicado 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.
8
Restrições Estritas / Variáveis ArbitráriasAs 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 vários valores.
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 básica.
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.
9
Restrições Estritas / Variáveis ArbitráriasCaso 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 variáveis não básicas-Z (Zi com i: m+1 .. z) e não-negativos das 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.
10
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 variáveis não-negativas. 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.
11
Restrições Estritas / Variáveis ArbitráriasConsideremos 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 além dos valores nulos das variáveis não básicas-S Sj (j: 1.. n), existem outros valores que não tornem negativas as variáveis básicas-S.
Se todos os ci forem positivos, existem vizinhanças εj 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, as disequações existentes são satisfazíveis.
12
Restrições Estritas / Variáveis ArbitráriasSe 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 = -S1+S2 e S4 = S1-S2
com a desigualdade S1-S2≠ 0 escrita em função das variáveis (S1 e S2) não básicas-S,.
13
Restrições Estritas / Variáveis ArbitráriasAparentemente 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 = -S1+S2 e S4 = S1-S2
obteríamos S3 + S4 = 0.
Sendo S3 e S4 variáveis não negativas, ambas devem ser nulas.
14
Restrições Estritas / Variáveis ArbitráriasEscolhendo 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
... o que torna evidente a insatisfazibilidade da restrição de desigualdade.
15
Restrições Estritas / Variáveis ArbitráriasAnalisando 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.
16
Forma Resolvida SF2 (Restrições)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.
17
Forma Resolvida SF2 (Restrições)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.
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.
18
Forma Resolvida SF2 (Restrições)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.
Teorema: A forma resolvida SF2 detecta as variáveis fixas, como variáveis básicas-S.
Demonstração: Basta provar que nenhuma variável não básica-S é fixa (a 0), i.e. dadas as igualdades de Es
Si = ci+qi,1T1 +...+qi,tTt com ci ≥ 0 para i:1..s
existirão, para além da solução Si = ci e Tj = 0, soluções
Si = ci+qi,1ε1 +...+qi,t εt e Tj = εj com εj > 0 para j: 1..t
19
Forma Resolvida SF2 (Restrições)Consideremos a seguinte partição das igualdades de Es
Es = R0 R1 ... Rt
em que a R0 pertencem todas as restrições com ck > 0, e a Rj (para j>0 ) pertencem todas as restrições em que o primeiro coeficiente não nulo (donde, positivo) é rj,k.
Para Es = R0 uma solução Tj > 0 é obtida fazendo Tj = ε, sendo ε qualquer valor que satisfaça as condições
(|qi,1 | +...+|qi,t|) ε ≤ ci para todo o i Indices(R0)
ou seja
0 < ε ≤ mini(ci)/maxi(|qi,1 |+...+|qi,t|)para i Indices(R0)
20
Forma Resolvida SF2 (Restrições)Considere-se agora o caso em que Es = R0 R1. Neste caso pode construir-se uma solução T > 0 da seguinte forma.
Primeiro obtém-se um valor ε1 tal que
(|qi,1 | ε1 < ci para todo o i Indices(R0)
garantindo-se que ck+qk,1ε1 é sempre positivo, qualquer que seja a igualdade de Es.
As outras variáveis Tj (j > 1) podem assim tomar qualquer valor ε, positivo, tal que
0 < ε ≤ mini(ci+qi,1ε)/maxi(|qi,2 |+...+|qi,t|)
para todo o i Indices(R0 R1)
21
Forma Resolvida SF2 (Restrições)A situação em que Es = R0 R1 R2 pode ser tratada de forma semelhante. Primeiro obtem-se um valor ε1
tal que
(|qi,1 | ε1 < ci para todo o i Indices(R0)
Em seguida obtém-se um valor ε2 tal que
|qi,1|ε2 ≤ ci + qi,1ε1 para todo o i Indices(R0 R1)
garantindo-se ck+qk,1ε1 +qk,2ε2> 0 qualquer que seja a igualdade de Es.
As outras variáveis Tj (j > 2) podem tomar qualquer valor ε, tal que
0 < ε ≤ mini(ci+qi,1ε1+qi,2ε2)/maxi(|qi,3 |+...+|qi,t|)
para todo o i Indices(R0 R1 R2)
22
Forma Resolvida SF2 (Restrições)Este procedimento pode generalizar-se até ao caso em que
Es = R0 R1 ... Rk com k < t
em que os valores εj (j k) para as variáveis Tj são obtidas como neste ultimo caso, garantido que
pi = ci+qi,1ε1+...+qi,t-1εt-1 > 0 para todo o iIndices(Es)
As outras variáveis Tl (j > k) podem tomar qualquer valor ε, positivo, tal que
ε ≤ mini (pi)/ maxi(|qi,k+1 |+...+|qi,t|) para iIndices(Es)
o que conclui a demonstração de que a forma resolvida SF2 não “esconde” variáveis fixas, e torna-as explícitas como igualdades si = Ki.
23
Passagem à Forma Resolvida SF2A 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 ≤ 9
R2: X1 + X2 ≤ 11
R3: 2X1 + X2 ≤ 18
R4: 2X1 - X2 ≥ 2
X1 ,X2 ≥ 0
24
Cada restrição é introduzida resolvendo em ordem à variável de desvio.
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.
Passagem à Forma Resolvida SF2
25
No caso de restrições ≥ a origem não pertence à região admissível, pelo que há que fazer uma mudança de base.
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
Donde
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2
Passagem à Forma Resolvida SF2
26
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).
Exemplo:
R5: X1 + 2X2 ≥ 12
Z5 = 12 - X1 - 2X2
Z5 = 11 - 5X2/2 - S4/2
Agora há que minimizar Z5, através de sucessivas mudanças de base.
Passagem à Forma Resolvida SF2
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2
27
Passagem à Forma Resolvida SF2Min Z5
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z5 = 11 - 5X2/2 - S4/2Como 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, como
S1 = 0 = 10 - 5X2/2 => X2 = 4 S2 = 0 = 10 - 3X2/2 => X2 = 20/3 (6.666)S3 = 0 = 16 - 2X2 => X2 = 8X1 = 0 = 1 + X2/2 => X2 = -2Z5 = 0 = 11 - 5X2/2 => X2 = 22/5 (4.400)
a variável S1 sai da base, já que é a primeira variável a anular-se para valores crescentes de X2.
28
Passagem à Forma Resolvida SF2Por entrada na base de X2, por troca com S1,
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z5 = 11 - 5X2/2 - S4/2
converte-se em
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/2Z5 = 1 + S1 - S4
Continuando a minimização de Z5, e pelo raciocínio anterior, S4 entra da base, por troca com Z5.
Passagem à Forma Resolvida SF2
29
Passagem à Forma Resolvida SF2Tendo-se anulado a variável artificial Z5, o sistema pode reescrever-se substituindo essa variável pela variável de desvio S5 = -Z5.
Assim, por entrada na base de S4, por troca com -S5,
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/2Z5 = 1 + S1 - S4
converte-se na forma SF2X2 = 21/5 - S1/5 + S5/5 S2 = 16/5 - S1/5 - 4S5/5 S3 = 33/5 - 3S1/5 - 7S5/5X1 = 18/5 + 2S1/5 + 3S5/5S4 = 1 + S1 + S5
30
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 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + 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.
Variáveis Fixas em SF2
31
Variáveis Fixas em SF2Min Z6
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z6 = 15 - 5X2/2 - S4/2Como anteriormente, Z5/X2 = -5/2 e Z5/S4 = -
1/2,pelo que existe um maior decréscimo de Z5 com X2, e X2 entra na base. Igualmente,
S1 = 0 = 10 - 5X2/2 => X2 = 4 S2 = 0 = 10 - 3X2/2 => X2 = 20/3 (6.666)S3 = 0 = 16 - 2X2 => X2 = 8X1 = 0 = 1 + X2/2 => X2 = -2Z6 = 0 = 15 - 5X2/2 => X2 = 6
Sendo igualmente a variável S1 a sair da base.
32
Por entrada na base de X2, por troca com S1, S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z6 = 15 - 5X2/2 - S4/2
converte-se em
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/5Z6 = 5 + S1 - S4
Na minimização de Z6, agora S4 entra da base, por troca ou com Z6 ou com S2 !
Variáveis Fixas em SF2
33
Variáveis Fixas em SF2
Com efeito, pretendendo-se obter o Min Z6
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/5Z6 = 5 + S1 - S4
S4 entra na base, e portanto deve verificar-se
X2 = 0 = 4 + S4/5 => S4 =-20 S2 = 0 = 4 - 4S4/5 => S4 = 5S3 = 0 = 8 - 7S4/5 => S4 = 40/7 (5.714)X1 = 0 = 3 + 3S4/5 => S4 = -5Z6 = 0 = 5 - S4 => S4 = 5
Pelo que quer Z6 quer S2 se anulam para S4 = 5.
34
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/5X1 = 3 - S1/5 + 3S4/5Z6 = 5 + S1 - S4
converte-se emX2 = 5 - S1/4 - S2/4 S4 = 5 + 3S1/4 - 5S2/4 S3 = 1 - S1/4 - 7S2/4X1 = 6 + S1/4 - 3S2/4Z6 = 0 + S1/4 + 5S2/4
Tendo Z6 o valor 0, pode ser substituído por -S6. Mas a restrição S6 = 0-S1/4-5S2/4 não está na forma SF2!
35
Variáveis Fixas em SF2
Mas reescrevendo a restrição S6 = 0-S1/4-5S2/4
como
S1 + 5S2 + 4 S6 = 0
Verifica-se que deve ser S1 = S2 = S6 = 0
Convertendo-se ...X2 = 5 - S1/4 - S2/4 S4 = 5 + 3S1/4 - 5S2/4 S3 = 1 - S1/4 - 7S2/4X1 = 6 + S1/4 - 3S2/4S6 = 0 - S1/4 - 5S2/4
... na forma SF2, evidenciando-se a fixação de variáveis
S1 = S2 = S6 = 0 X1 = 6 X2 = 5 S4 = 5 S3 = 1
36
Sistemas ImpossíveisSe 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 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2
adicionar a nova restrição:
R7: X1 + 2X2 ≥ 18
Z6 7
Z7 = 17 - 5X2/2 - S4/2
Como anteriormente, há que minimizar Z7.
37
Sistemas ImpossíveisMin Z7
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z7 = 17 - 5X2/2 - S4/2Como 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 = 0 = 10 - 5X2/2 => X2 = 4 S2 = 0 = 10 - 3X2/2 => X2 = 20/3 (6.666)S3 = 0 = 16 - 2X2 => X2 = 8X1 = 0 = 1 + X2/2 => X2 = -2Z7 = 0 = 17 - 5X2/2 => X2 = 34/5 (6.800)
Continuando a ser a variável S1 a sair da base.
38
Por entrada na base de X2, por troca com S1,
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2Z7 = 17 - 5X2/2 - S4/2
converte-se emX2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/5Z7 = 7 + S1 - S4
Na minimização de Z7, agora S4 entra da base, por troca com S2 !
Sistemas Impossíveis
39
Sistemas Impossíveis
Com efeito, pretendendo-se obter o Min Z7
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/5Z7 = 7 + S1 - S4
S4 entra na base, e portanto deve verificar-se
X2 = 0 = 4 + S4/5 => S4 =-20 S2 = 0 = 4 - 4S4/5 => S4 = 5S3 = 0 = 8 - 7S4/5 => S4 = 40/7 (5.714)X1 = 0 = 3 + 3S4/5 => S4 = -5Z7 = 0 = 5 - S4 => S4 = 7
Pelo que quer S2 é o primeiro a anular-se para valores crescentes de S4 (para S4 = 5).
40
Sistemas ImpossíveisSaindo S2 da base, por troca com S4,
X2 = 4 - 2S1/5 + S4/5 S2 = 4 + 3S1/5 - 4S4/5 S3 = 8 + 4S1/5 - 7S4/5X1 = 3 - S1/5 + 3S4/5Z7 = 7 + S1 - S4
converte-se emX2 = 5 - S1/4 - S2/4 S4 = 5 + 3S1/4 - 5S2/4 S3 = 1 - S1/4 - 7S2/4X1 = 6 + S1/4 - 3S2/4Z7 = 2 + S1/4 + 5S2/4
Reescrevendo-a como S1 + 5S2 +4 S7 = -8
esta última restrição, não só mostra que Z7 não pode tomar o valor 0, como que é insatisfazível!
41
Sistemas ImpossíveisA 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 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + S4/2
-X1+2X2 ≥ 10 -X1+2X2 -S8 = 10 X2 = 22/3 + S4/3 +2S8/3
42
Sistemas Impossíveis
Substituindo no sistema abaixo X2 = 22/3 + S4/3 +2S8/3
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + 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.
43
Sistemas ImpossíveisOs conjuntos IIS não são únicos. Substituindo no sistema abaixo X2 = 22/3 + S4/3 +2S8/3
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + 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.
44
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 comoS4 = -25- 3S1- 5S8
que, com as anteriores, X2 = 22/3 + S4/3 +2S8/3 X1 = 1 + X2/2 + S4/2
originaX1 = -12 -2S1 - 3S8
ou X1 + 2S1 + 3S8 = -12, revelando ainda outro conjunto mínimo constituído pelas restrições R1, R8 e X1 (>= 0).
45
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 R1, R8 e X2 >0.
(De notar que a determinação de todos os conjuntos mínimos é um problema NP-hard).
46
Restrições Redundantes
É fácil de mostrar que, dado um conjunto de restrições satisfazíveis, se uma restrição
ai Xi > K ou ai Xi - Si = K
é impossível, então a restrição
ai Xi < K ou ai Xi + Sr = K
é redundante ( a igualdade ai Xi + Sr = K pode ser analisada facilmente)
Das equações anteriores tira-se Sr + Si = 0. Se se obtiver uma condição de impossibilidade Si + pj Vj =
- C então a condição de redundância é Sr = C + pj Vj
47
Restrições RedundantesExemplo: Dadas as restrições
S1 = 10 - 5X2/2 + S4/2 S2 = 10 - 3X2/2 - S4/2 S3 = 16 - 2X2 - S4
X1 = 1 + X2/2 + 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