Simplex.html

PES Pesquisa Operacional

Prof. Milton Procópio de Borba

Originais do Prof. Fernando Deeke Sasse

5. Programação Linear: Solução pelo Método Simplex

5.1 Problema da produção de brinquedos: solução manual

Vamos agora estudar os passos do método simplex resolvendo o problema de produção de brinquedos. Tínhamos nesse o seguinte sistema de equações:

> restart:

> with(linalg):

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

> System:=[x[1]+x[3]=90, x[2]+x[4]=60, 5*x[1]+6*x[2]+x[5]=600];

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

> b:=evalm(RHS);

> c:=vector(5,[30,40,0,0,0]);

Vamos agora definir uma matriz básica B a partir de A, usando a últimas três colunas (matriz identidade) :

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

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

A solução básica é então dada por

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

Ou seja, se = = 0, então , e , de modo que se nada é produzido, então haverá uma capacidade ociosa de 90 e 60 unidades nos departamentos de carros e trens, respectivamente. Sem produção as 600 partes também não serão usadas. Isso corresponde à origem do gráfico.

À solução básica xB está associada o vetor cB de preço associado às variáveis básicas. Como as outras variáveis estão zeradas, o valor da função objetivo é dado por . Aqui cB pode ser considerado uma matriz linha e xB uma matriz coluna. No presente caso,

> cB:=vector(3,[c[3],c[4],c[5]]);

> z:=evalm(cB&*xB);

Como a matriz base B consiste de vetores linearmente independentes , ... , , qualquer coluna da matriz de coeficientes pode ser escrita como uma combinação linear das colunas de B. Ou seja,

= ,

onde

= ( , ... , ) '

é uma matriz coluna. Para computar estes coeficientes da combinação linear devemos fazer

> y[1]:=evalm((1/B)&*a[1]);

> y[2]:=evalm((1/B)&*a[2]);

Podemos agora definir um novo escalar:

= = cB .

Esta quantidade é interpretada como o decréscimo no valor da função objetivo que resultará se uma unidade de uma variável não-básica for trazida à solução. No nosso caso temos

> z[1]:=evalm(cB &* y[1]);

> z[2]:=evalm(cB &* y[2]);

Devemos agora decidir como melhorar a presente solução. Para isso definimos como sendo a contribuição resultante da introdução de uma unidade da variável não-básica na solução. O que dá o maior é escolhido como a nova variável básica (os casos de "empate" podem ser decididos arbitrariamente). No presente caso temos

> c[1]-z[1]; c[2]-z[2];

Portanto deve entrar a coluna .

Devemos decidir agora qual a coluna da matriz básica que deve sair. Isso deve ser feito de modo que a nova solução básica seja factível. Já vimos que a coluna da matriz base que deve ser substituída pela coluna é aquela que satisfaz a

No nosso caso,

> if y[2][1]>0 then print(xB[1]/y[2][1]) else print("Não definido") fi;

> if y[2][2]>0 then print(xB[2]/y[2][2]) else print("Não definido") fi;

> if y[2][3]>0 then print(xB[3]/y[2][3]) else print("Não definido") fi;

Note, para evitar confusões, que o primeiro índice de y[i][j] é de colunas e o segundo é de linhas, ao contrário do usual, pois já denota um vetor coluna. Da relação acima vemos que o índice deve ser selecionado. Ou seja, sai a coluna .

A nova matriz básica agora é

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

O processo agora repete-se iterativamente:

> xB:=evalm(inverse(B) &* b);

> cB:=vector(3,[c[3],c[2],c[5]]);

> z:=evalm(cB &* xB);

> y[1]:=evalm(inverse(B) &* a[1]);
y[3]:=evalm(inverse(B) &* a[3]);

> z[1]:=evalm(cB &* y[1]);
z[3]:=evalm(cB &* y[3]);

> c[1]-z[1]; c[3]-z[3];

> # a[1] entra

> if y[1][1]>0 then print(xB[1]/y[1][1]) else print("No Ratio") fi;

> if y[1][2]>0 then print(xB[2]/y[1][2]) else print("No Ratio") fi;

> if y[1][3]>0 then print(xB[3]/y[1][3]) else print("No Ratio") fi;

> # b[3]=a[5] sai

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

> xB:=evalm(inverse(B) &* b);

> cB:=vector(3,[c[3],c[2],c[1]]);

> z:=evalm(cB &* xB);

> y[4]:=evalm(inverse(B) &* a[4]);
y[5]:=evalm(inverse(B) &* a[5]);

> z[4]:=evalm(cB &* y[4]);
z[5]:=evalm(cB &* y[5]);

> c[4]-z[4]; c[5]-z[5];

> # Solução ótima

A solução ótima foi encontrada pois a introdução de qualquer variável não básica na base diminuiria o valor da função objetivo. Portanto

> x[2]:=xB[2];

> x[1]:=xB[3];

e o lucro é

> z:=evalm(cB &* xB);

Ver em Excel ( este problema dos brinquedos e das Duas Minas por SIMPLEX )

5.2 Problema da produção de brinquedos: solução com pacote simplex

> restart:

> with(simplex):

Warning, the protected names maximize and minimize have been redefined and unprotected

> z:=30*x[1]+40*x[2];

> rest[1]:=x[1]<=90; rest[2]:=x[2]<=60; rest[3]:=5*x[1]+6*x[2]<=600;

> Sol:=maximize(z,{seq(rest[i],i=1..3)},NONNEGATIVE);

> assign(Sol); z;

Ver em Excel ( este problema dos brinquedos e das Duas Minas por SIMPLEX )

5.3 Exercício

Resolva o seguinte problem de PL utilizando o método manual e depois confira o resultado usando o pacote simplex.

min

Sugestão: transforme o problema de minimização de em um problema de maximização para .

Solução manual

Introduzindo a variável de folga e as desiguladades acima tornam-se:

A matriz de coeficientes é . Neste ponto não é claro qual é a matriz base que devemos escolher de modo que a primeira solução básica seja factível, com exisgido no método simplex. Introduzimos então duas novas variáveis artificiais e nas últimas equações:

A matrix de coeficientes é agora dada por

Portanto, a primeira matrix básica que vai gerar uma solução básica factível é , de modo que . As variáveis artificiais devem ser eliminadas no final. Para garantir que na solução ótima elas sejam zero, devemos associa-las a um preço muito alto. Para isso reescrevemos a função objetivo como

min + 0 + 0 + ,

onde é um número não-negativo que é assumido ser suficientemente grande de modo a garantir que qualquer preço correspondente a uma variável legítima seja desprezível com relação a . Podemos ainda transformar o problema de minimização em maximização, trocando o sinal da função objetivo: