PES Pesquisa Operacional

Prof. Milton Procópio de Borba

Originais do Prof. Fernando Deeke Sasse

4. Programação Linear: Soluções Factíveis e Soluções Básicas Factíveis

4.1 Exemplo 1

Este exemplo ilustra o fato estabelecido pelo teorema que afirma que, se um sistema linear com admite uma solução factível, ele também admite uma solução básica factível.

Consideremos o seguinte conjunto de restrições:

,

,

,

, , , .

Solução : Para transformar a desigualdade em equação devemos introduzir a variável de folga . Temos então

,

,

,

, , , , , , .

Vamos inicialmente gerar a matriz do sistema:

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> sistema:=[3*x[1]-0*x[2]+5*x[3]-6*x[4]+x[5] = 4,2*x[1]-6*x[2]+x[3]+5*x[4] = 1,1/2*x[1]+x[2]+5*x[3]+0*x[4]= 10];

> A:=genmatrix(sistema,[x[1],x[2],x[3],x[4],x[5]],RHS);

> evalm(A);

> b:=evalm(RHS);

>

Vamos associar um vetor a cada coluna de A :

> for j to 5 do a[j]:=col(A,j) od;

Devemos escolher uma matriz base B e obter a primeira solução factível básica. Se escolhermos aleatóriamente as colunas a serem eliminadas podemos obter soluções básicas não-factíveis. Por exemplo,

> B:=augment(a[1],a[2],a[3]);

A solução básica é :

> xB:=evalm(B^(-1)&*b);

que é não-factível, pois nem todas as componentes de xB são não-negativas.

Devemos então usar algum critério que nos permita determinar qual coluna deve ser zerada.

Uma solução factível é

> x[4]:=2;x[5]:=1/2;

> sistema;

> op(sistema);

> ss:=solve({op(sistema)},{x[1],x[2],x[3]});

>

> assign(ss);

> x[2];

Determinemos os coeficientes que fazem a combinação linear das colunas .

> zer:=vector(5,[0,0,0,0,0]);

> eq1:=evalm(add(alpha[i]*a[i],i=1..5));

> set_eqs:={seq(eq1[i]=0,i=1..3)};

> vars:={seq(alpha[j],j=1..5)};

> sol:=solve(set_eqs,vars);

> assign(sol);

> alpha[2]:=1;alpha[3]:=1;

> seq(alpha[k],k=1..5);

A coluna a ser retirada terá índice dado por ,

Ou seja,

> S:=evalf([x[2]/alpha[2],x[3]/alpha[3],x[4]/alpha[4],x[5]/alpha[5]]);

Portanto, será eliminada a coluna . O novo sistema será

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> A := matrix([[3, 0, 5, -6], [2, -6, 1, 5], [1/2, 1, 5, 0]]);

> b := vector([4, 1, 10]);

Vamos associar um vetor a cada coluna de A :

> for j to 4 do a[j]:=col(A,j) od;

>

> X:=vector(4,[x1,x2,x3,x4]);

> eq1:=evalm(A&*X-b);

> eq1[1];

> eqs:={seq(eq1[j]=0,j=1..3)};

> sol1:=solve(eqs,{x1,x2,x3,x4});

>

> assign(sol1);

Escolhendo

> x4:=1;

obtemos uma solução factível:

> seq(X[j],j=1..3);

Determinemos os coeficientes que fazem a combinação linear das colunas .

>

> zer4:=vector(4,[0,0,0,0]);

> eq1:=evalm(add(alpha[i]*a[i],i=1..4));

> set_eqs:={seq(eq1[i]=0,i=1..3)};

> vars:={seq(alpha[j],j=1..4)};

> sol:=solve(set_eqs,vars);

> assign(sol);

> alpha[3]:=1;

> seq(alpha[k],k=1..4);

A coluna a ser retirada terá índice dado por ,

Ou seja,

Portanto, eliminamos a coluna e chegamos a uma matriz básica (3x3):

> restart:

> with(linalg):

> A := matrix([[3, 0, -6], [2, -6, 5], [1/2, 1, 0]]);

> b := vector([4, 1, 10]);

A solução básica é :

> xB:=evalm(A^(-1)&*b);

que é factível, por construção.

4.2 Exemplo 2

Seja o sistema onde

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> A := matrix([[2, 0, 1, -6, 1, 11], [6, 2, 1, 7, 0, 3], [1, 2, 5, 0, 5, 1],[2,4,-2,3,0,1]]);

> b:=matrix([[45], [32], [34], [11]]);

Podemos verificar que uma solução factível para este problema é dada por

> X:= vector(6,[1, 2, 3, 1, 2, 4]);

> evalm(A&*X);

Note que que podemos uma solução básica factível por tentativa e erro.

> for j to 6 do a[j]:=col(A,j) od;

Eliminando as linhas 4 e 5 temos

> B:=augment(a[4],a[2],a[3],a[6]);

> linsolve(B,b);

o que mostra que a solução básica é factível.

Utilize o critério empregado no exemplo anterior para determinar uma solução básica factível.

> evalm(a[1]);

>

> for j to 6 do a[j]:=col(A,j) od;

> zer:=vector(6,[0,0,0,0,0,0]);

> eq1:=evalm(add(alpha[i]*a[i],i=1..6));

> set_eqs:={seq(eq1[i]=0,i=1..4)};

> vars:={seq(alpha[j],j=1..6)};

> sol:=solve(set_eqs,vars);

> assign(sol);

> alpha[2]:=1;alpha[5]:=1;

> seq(alpha[k],k=1..6);

> S:=evalf([X[1]/alpha[1],X[2]/alpha[2],X[5]/alpha[5]]);

Portanto devemos eliminar a coluna a[1]

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> A := matrix([[ 0, 1, -6, 1, 11], [ 2, 1, 7, 0, 3], [ 2, 5, 0, 5, 1],[4,-2,3,0,1]]);

> b:=matrix([[45], [32], [34], [11]]);

> X:=vector(5,[x1,x2,x3,x4,x5]);

> eq1:=evalm(A&*X-b);

> eq1[3,1];

> eqs:=[seq(eq1[j,1]=0,j=1..4)];

> sol1:=solve({op(eqs)},{x1,x2,x3,x5});

>

> assign(sol1);

Escolhendo

> x4:=1;

obtemos uma solução factível:

> seq(X[j],j=1..5);

>

> for j to 5 do a[j]:=col(A,j) od;

> zer:=vector(5,[0,0,0,0,0]);

> eq1:=evalm(add(alpha[i]*a[i],i=1..5));

> set_eqs:={seq(eq1[i]=0,i=1..4)};

> vars:={seq(alpha[j],j=1..5)};

> sol:=solve(set_eqs,vars);

> assign(sol);

> alpha[1]:=1;

> seq(alpha[k],k=1..5);

> S:=evalf([X[1]/alpha[1],X[2]/alpha[2]]);

Eliminamos a coluna a1:

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> A := matrix([[ 1, -6, 1, 11], [ 1, 7, 0, 3], [ 5, 0, 5, 1],[-2,3,0,1]]);

> b:=matrix([[45], [32], [34], [11]]);

Por contrução, tal solução básica deve ser factível. De fato,

> linsolve(A,b);

>

4.3 Exercício

Defina um sistema Ax = b, com 3 equações e 5 incógnitas, de modo que ele admita uma solução factível. Determine então ao menos uma solução básica factível usando (i) tentativa e erro e (ii) a redução mostrada nos exemplos anteriores. A solução poderia ser iniciada da seguinte forma:

> restart;

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> m:=3;n:=5;

> A:=randmatrix(m,n,entries=rand(0..150));

> b:=randvector(m,entries=rand(0..100));

> x:=vector(n);

> LHS:=multiply(A,x);

> sistema:={seq(LHS[i]=b[i],i=1..m)};

>