Restrições Lineares sobre os Reais/Racionais
• Muitos problemas podem ser modelados através de
variáveis reais (ou racionais), denominadas variáveis de
decisão.
• Todas as restrições sobre essas variáveis são lineares.
• Geralmente pretendem-se soluções 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 a
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
hiper-plano 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-hiper-espaço limitado pelo correspondente hiperplano, 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 hiper-poliedro (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 (um 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 hiperplanos de fronteira das restrições (excepto restrições ≠)
deve pertencer à região admissível.
• Como n restrições de igualdade num espaço n-dimensional
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
simbólica (algébrica).
uma
Forma
Resolvida,
ou
• implementem a pesquisa através de um conjunto de
manipulações algébricas.
• 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 (Lema 1)
 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 desta demonstração (por indução em n).
(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>.
Fazendo X4 = 1- δ obtemos o sistema S2
(S2)
3X1–2X2+ X3 = 5 - δ
X1+ X2-2X3 = 1 + δ
Para toda a solução <ω1,ω2,ω3> deste sistema existe uma
solução <ω1,ω2,ω3,1-δ> de S1. Pela hipótese de indução todo
o sistema de m equações a m+n incógnitas (isto é, 2
equações a 3 incógnitas) tem uma solução com n-1 (1)
20
variáveis nulas.
Lema 1 (exemplo)
Este é o caso de S2 que admite de facto a solução < 11/7,
0, 2/7>. Assim pode reescrever-se o sistema equivalente
S3, isolando X1 e X3
(S3)
X1 = 11/7 + 3/7 X2 – 1/7 δ
X3 = 2/7 + 5/7 X2 – 4/7 δ
Assumindo X2 = 0, considere-se o sistema S4
(S4)
X1 = 11/7 – 1/7 δ
X3 = 2/7 – 4/7 δ
Para qualquer solução <s1, s3> de S4 existe também uma
solução <s1, 0, s3, 1-δ > do sistema inicial S1.
Para δ =1/2, X3 anula-se, obtendo-se outra solução de S6
(<3/2,0>) a que corresponde a solução, <3/2, 0, 0, 1/2> de
S1 que, como se pretendia, tem n+1=2 variáveis nulas.
21
Lema 1 (exemplo)
(S4)
X1 = 11/7 – 1/7 δ
X3 = 2/7 – 4/7 δ
Para qualquer solução <s1, s3> de S4 existe também uma
solução <s1, 0, s3, 1-δ > do sistema inicial S1.
Para δ =0 a solução <11/7, 0, 2/7, 1 > do sistema inicial S1
tem apenas 1 variável nula. No entanto ao aumentar-se δ
• ou 1- δ se anula
• ou um dos X1 X3 se anula.
Em ambos os casos obtem-se uma solução do problema
inicial S1 com 2 variáveis nulas. Neste caso, X3 anula-se
para δ =1/2, obtendo-se uma solução, <3/2, 0, 0, 1/2> de S1
que, como se pretendia, tem n+1=2 variáveis nulas.
22
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 = ci+ai,m+n+1δ
(ci=bi-ai,m+n+1wm+n+1)
Uma solução deste sistema com δ=0 é uma solução do sistema S1 com
Xm+n+1 = wm+n+1. Assim, o sistema
(S3) ai,1X1+...+ai,m+nXm+n = ci
é satisfazível (admite a solução inicial Xi = wi )
23
Lema 1
 (2)
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δ
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.
24
Lema 1
 (3)
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).
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.
25
Lema 1
Xi
 (4)
= 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 um 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 .
26
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.
27
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
rescrever 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 <s1,s2, ...,sm,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.
28
Interpretação Geométrica
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 pelos conjuntos de restrições
{R3, R4}, {R3, R5} e {R4, R5}.
X2
X1 - X2 - X5 = -5
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1
29
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 e R2: X2 ≥ 0
A região admissível é constituída pela intersecção das
sub-regiões definidas pelos 10 conjuntos de restrições
{R1, R2}, a {R4, R5}.
X2
X1 - X2 = -5
X1 = 0
2 X1 + X2 = 8
X1
X1 + X2 = 3
X2 = 0
30
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
2X1 + X2 ≤ 8
2 X1 + X2 + X3 = 8
X5 = 0
X1 = 0
2 X1 + X2 = 8
X3 = 0
X4 = 0
X1
X1 + X2 = 3
X1 + X2 ≥ 3
X1 + X2 - X4 = 3
X2 = 0
31
Restrições Racionais
A questão que se coloca agora é como garantir a passagem
eficiente de um conjunto de restrições lineares sobre
variáveis não negativas para essa forma resolvida SF0,
sem escolha arbitrária dos vértices.
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á que definir um procedimento para efectuar essa
transformação incremental. Esse procedimento é
esencialmente baseado no algoritmo SIMPLEX.
32
Interpretação Geométrica
Ora como cada restrição é limitada pelo anulamento de
uma das variáveis de desvio, o ponto de intersecção de
rectas correspondentes a duas restrições é obtido pelo
anulamento das respectivas variáveis de desvio.
Por outro lado, as m equações a m+2 variáveis podem ser
reescritas de forma a que m variáveis (as variáveis
básicas) venham definidas em relação às outras duas.
Considerando essas duas (não-básicas) como variáveis de
desvio, o seu anulamento determina o valor das outras
variáveis no ponto de intersecção das rectas
correspondentes a essas variáveis de desvio.
33
Interpretação Geométrica
Por exemplo, dadas as restrições anteriores
R3: 2X1 + X2 ≤ 8 ; R4: X1 + X2 ≥ 3 ; R5: X1 - X2 ≥ -5
e reescrevendo-as como
R3: 2X1 + X2+ X3 = 8 ; R4: X1 + X2 -X4 = 3 ; R5: X1 - X2 -X5 = -5
considerando a base {X1, X2 e X4} elas podem ser
reescritas como
X1 = 1 - X3/3 + X5/3
X2 = 6 - X3/3 - 2 X5/3
X4 = 4 - 2 X3/3 - X5/3
sendo X1 =1, X2 = 6 e X4 =4 o ponto onde se intersectam as
restrições R3 e R5 (isto é, com desvios X3 e X5 nulos).
34
Interpretação Geométrica
Havendo m restrições e m+2 variáveis, o número de
potenciais vértices da região admissível é o número de
combinações de m+2 variáveis 2 a 2, isto é, (m+2)*(m+1)/2.
No caso que temos vindo a exemplificar, m=3 donde o
número de potenciais vértices é 10.
Na realidade, nem todos os pontos resultantes da
intersecção das rectas estão dentro da região admissível.
Um vértice não está na região admissível se no ponto
correspondente, algumas das variáveis tomarem valores
negativos.
35
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
36
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.
37
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
38
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 = 8
ou
X1 + X2 + X4 = 3
X1 - X2 - X5 = -5
39
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
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 ( C m+n ) de possibilidades de escolha da
m
base.
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
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ásica.
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 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
positivos mudar a base escolhendo
coeficientes
• 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 X1 +
X3 =
2X2
9 + X1 - 3X2
X4 = 11 - X1 -
→
9/3
X2
→ 11/1
X5 = 18 - 2X1 - X2
→ 18/1
entra X2, sai X3
50
Interpretação Geométrica
Exemplo.
Max X1 +
X3 =
2X2
9 + X1 - 3X2
X4 = 11 - X1 -
→
9/3
X2
→ 11/1
X5 = 18 - 2X1 - X2
→ 18/1
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, 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
i: 1..m
em que todos os bi são não negativos. Neste caso basta
escolher as variáveis X1 a Xn para variáveis não básicas,
pois o seu anulamento satisfaz as restrições!
53
Passagem para a Forma Resolvida SF0
Podemos ver agora como é que o algoritmo de optimização
pode ser utilizado para colocar o sistema inicial na forma
SFO, quando o anulamento das variáveis de decisão não
constitui uma solução admissivel.
Se essa é a situação, então temos uma (ou mais) restrição
Ri na forma
Xi = di+ ci1 Xm+1 +...+ cin Xm+n
em que o di < 0. Nesta situação, podemos introduzir uma
variável artificial não negativa, Zi, na restrição fazendo
Xi = Zi + di+ ci1 Xm+1 +...+ cin Xm+n
54
Passagem para a Forma Resolvida SF0
Xi = Zi + di+ ci1 Xm+1 +...+ cin Xm+n
Como é óbvio, a restrição assim modificada e a inicial
serão equivalentes sse Zi = 0.
Reescrevendo a restrição modificada como
Zi = - di+ ci1 Xm+1 +...+ cin Xm+n - Xi
Obtem-se uma restrição que já se encontra na forma SF0,
já que -di > 0. Assim sendo, como uma solução admissível
do sistema modificado é uma solução do sistema inicial se
Zi = 0, tudo o que é necessário fazer é, no sistema
modificado, minimizar Zi.
55
Passagem para a Forma Resolvida SF0
Em geral, 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 = di+ ci1 Xm+1 +...+ cin Xm+n
2. Se todos os di 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.
56
Passagem para a Forma Resolvida SF0
Naturalmente, se o mínimo fôr 0, no ponto de mínimo todas
as variáveis artificiais são nulas. Em princípio, as variáveis
artificiais são não-básicas, e o sistema toma a forma
Xi = di+ ci1Xm+1 +...+ cinXm+n +ei1Z1 +...+ eiqZq
Em que os dis são não negativos. O sistema inicial é
equivalente ao modificados com as variáveis artificiais
nulas. Assim o sistema inicial é equivalente ao sistema que
se obtem eliminando no anterior os termos nas variáveis
artificiais, e que já está na forma SF0 porque todos os dis
são não negativos.
Xi = di+ ci1Xm+1 +...+ cinXm+n
57
Passagem para a Forma Resolvida SF0
Na realidade alguma(s) das variáveis artificiais podem não
ser não básicas obtendo-se restrições reescritas como
Zq = 0 + ci1Xm+1 +...+ cinXm+n +ei1Z1 +...+ eiq-1Zq-1
Neste caso, pode simplesmente trocar-se a variável Zi com
um qualquer dos Xs não básicos obtendo-se, por exemplo
Xm+1= 0 + c’i1Xm+2 +...+ c’inXm+n +e’i1Z1 +...+eiqZq
em que c’ij= -cij/ci1, e’il= -eil/ci1 e eik= -1/ci1.
A substituição de Zq por Xm+1 nas outras restrições não
vai afectar os termos livres (dis) nelas existentes que
serão simplesmente somados com 0.
58
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 hiperpoliedro até atingir o espaço inicial (em 2D, o plano X-Y).
59
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
60
Interpretação Geométrica
Exemplo
X3 =
9 + X1 - 3X2
X4 =
11 - X1 -
X2
X5 =
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>
61
Interpretação Geométrica
Exemplo
min Z1 = 12 - X1 - 2X2 +
X6
X3 =
9 + X1 - 3X2
X4 = 11 - X1 -
X2
X5 = 18 -2X1 -
X2
Z1 = 12 - X1 - 2X2 + X6
min 6 - 7X1/3 - 2X3 /3 + X6
X2 =
3 +
X1/3 - X3/3
X4 =
8 - 4X1/3 + X3
X5 = 15 - 7X1/3 +
Z1 = 6 -
X3/3
8X1/3 + 2X3/3 + X6
Projecção no plano X1-X2 do ponto <X1, X2, Z1> = <0, 3, 6>
62
Interpretação Geométrica
Exemplo
min 6 - 7X1/3 - 2X3 /3 + X6
X2 =
3 +
X1/3 - X3/3
X4 =
8 - 4X1/3 + X3
X5 = 15 - 7X1/3 + X3/3
Z1 = 6 -
8X1/3 + 2X3/3 + X6
min Z1
X1 = 18/5 + 2X3/5 + 3X6/6 -3Z1/5
21/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
63
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)
64
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 + 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
65
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.
66
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.
67
Forma Resolvida SF1 (Igualdades)
Exemplo:
X2
Eliminando-se o requisito de não negatividade
de X1 e X2 as restrições
X5 = 0
2 X1 + X2 ≤ 8
X1 + X2 ≥ 3
X1 - X2 ≥ -5
X3 = 0
X4 = 0
2 X1 + X2 + X3 = 8
X1 + X2 - X4 = 3
X1 - X2 - X5 = -5
admitem como forma resolvida SF1
Ea:
X1 = 5 - X3 - X4
X2 = -2 + X3 + 2 X4
Es:
X5 = 12 - 2 X3 - 3 X4
68
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.
69
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
indicado abaixo (em que os si ≥ 0).
ai1 X1 +...+ ain Xn ≤ bi  ai1 X1 +...+ ain Xn + Si = bi
ai1 X1 +...+ ain Xn < bi 
bi
ai1 X1 +...+ ain Xn + Si =
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 todas70as)
variáveis são não negativas.
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 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 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.
71
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 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.
72
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.
73
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 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.
74
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 - S 2 ≠ 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.
75
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 = -S1+S2
e
S4 = S1-S2
obteríamos S3 + S4 = 0.
Sendo S3 e S4 variáveis não negativas, ambas devem ser
nulas.
76
Restrições Estritas / Variáveis Arbitrárias
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
... o que torna evidente a insatisfazibilidade da restrição
de desigualdade.
77
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
e da sua simétrica
-S1 +S2
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.
78
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.
79
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.
80
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
81
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)
82
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)
83
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)
84
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 iIndices(Es)
As outras variáveis Tl (j > k) podem tomar qualquer valor ε,
positivo, tal que
ε ≤ mini (pi)/ maxi(|qi,k+1 |+...+|qi,t|) para
iIndices(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.
85
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
86
Passagem à Forma Resolvida SF2
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.
87
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.
S1 = 9 + X1 - 3X2
S2 = 11 - X1 - X2
S3 = 18 - 2X1 - X2
R4: 2X1 - X2 ≥
 2X1 - X2
 S4 = -2 +
 X1 = 1 +
2
- S4 = 2
2X1 - X2
X2/2 + S4/2
Donde
S1
S2
S3
X1
= 10 - 5X2/2
= 10 - 3X2/2
= 16 - 2X2
= 1 + X2/2
+
+
S4/2
S4/2
S4
S4/2
88
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).
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
 Z5 = 12 - X1 - 2X2
 Z5 = 11 - 5X2/2 - S4/2
Agora há que minimizar Z5, através de sucessivas mudanças
89
de base.
Passagem à Forma Resolvida SF2
Min Z5
S1 =
S2 =
S3 =
X1 =
Z5 =
10
10
16
1
11
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2
S4/2
S4
S4/2
S4/2
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, como
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.400)
a variável S1 sai da base, já que é a primeira variável a
anular-se para valores crescentes de X2.
90
Passagem à Forma Resolvida SF2
Por entrada na base de X2, por troca com S1,
S1
S2
S3
X1
Z5
=
=
=
=
=
10
10
16
1
11
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
+
+
-
S4/2
S4/2
S4
S4/2
S4/2
converte-se em
X2
S2
S3
X1
Z5
=
=
=
=
=
4
4
8
3
1
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/2
+ S1
- S4
Continuando a minimização de Z5, e pelo raciocínio
anterior, S4 entra da base, por troca com Z5.
91
Passagem à Forma Resolvida SF2
Tendo-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
S2
S3
X1
Z5
=
=
=
=
=
4
4
8
3
1
- 2S1/5 + S4/5
+ 3S1/5 - 4S4/5
+ 4S1/5 - 7S4/5
- S1/5 + 3S4/2
+ S1
- S4
converte-se na forma SF2
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
92
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.
93
Variáveis Fixas em SF2
Min Z6
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
Como 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
S2
S3
X1
Z6
=
=
=
=
=
0
0
0
0
0
=
=
=
=
=
10
10
16
1
15
+
-
5X2/2
3X2/2
2X2
X2/2
5X2/2
=>
=>
=>
=>
=>
X2
X2
X2
X2
X2
=
=
=
=
=
4
20/3 (6.666)
8
-2
6
Sendo igualmente a variável S1 a sair da base.
94
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
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
Na minimização de Z6, agora S4 entra da base, por troca
ou com Z6 ou com S2 ou com S3!
95
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
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.
96
Variáveis Fixas em SF2
Escolhendo S2 para sair da base, por troca com S4,
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
converte-se em
X2
S4
S3
X1
Z6
=
=
=
=
=
5
5
1
6
0
- S1/4 - S2/4
+ 3S1/4 - 5S2/4
- S1/4 - 7S2/4
+ S1/4 - 3S2/4
+ 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!
97
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
S4
S3
X1
S6
=
=
=
=
=
5
5
1
6
0
- S1/4 - S2/4
+ 3S1/4 - 5S2/4
- S1/4 - 7S2/4
+ S1/4 - 3S2/4
- 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
98
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 7
 Z7 = 17 - 5X2/2 - S4/2
Como anteriormente, há que minimizar Z7.
99
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
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.
100
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
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 !
101
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
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 quer S2 é o primeiro a anular-se para valores
crescentes de S4 (para S4 = 5).
102
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
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
Reescrevendo-a como
S1 + 5S2 +4 S7 = -8
esta última restrição, não só mostra que Z7 não pode
103
tomar o valor 0, como que é insatisfazível!
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
-X1+2X2 ≥ 10
+
+
S4/2
S4/2
S4
S4/2
 -X1+2X2 -S8 = 10  X2 = 22/3 + S4/3 +2S8/3
104
Sistemas Impossíveis
Substituindo no sistema abaixo X2 = 22/3 + S4/3 +2S8/3
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.
105
Sistemas Impossíveis
Os conjuntos IIS não são únicos. Substituindo no sistema
abaixo X2 = 22/3 + S4/3 +2S8/3
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.
106
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). 107
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
restrições R1, R8 e X2 >0.
mínimo
constituído
pelas
(De notar que a determinação de todos os conjuntos
mínimos é um problema NP-hard).
108
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
109
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
110