Dúvida no simplex duas fases

Dúvida no simplex duas fases

por Felipe Carvalho Perestrelo -
Número de respostas: 2
Oi, professor. Minha dúvida é sobre a recomputação dos dados entre a fase I e II. Pelo que eu entendi:
1) Ao fim da execução temos uma base viável, então poderíamos simplesmente ignorar toda a construção da matriz T até o momento e começar o problema do zero utilizando os índices da base obtidos a partir do problema auxiliar.
2) Podemos utilizar a porção esquerda (das colunas 1 a n) da matriz T pois ela foi obtida a partir de operações elementares de linhas em cima da matriz A original, e assim os problemas original e o obtido são equivalentes.
3) Com isto, a única atualização que devemos fazer é na linha 0, pois no problema auxiliar utilizamos uma função objetivo diferente. Na aula você escreveu que devemos recomputar os dados necessários para a fase II (B^-1, cBarra, T, etc) usando a função objetivo original, e por causa do T, e do etc não ficou totalmente claro pra mim.

É isso?
 
Obrigado.
 
Abs.
 
Felipe
Em resposta à Felipe Carvalho Perestrelo

Re: Dúvida no simplex duas fases

por Marcelo Queiroz -

Olá, Felipe!

Acho que você entendeu certo, e eu posso ter me expressado de forma confusa. O que podemos aproveitar da fase I para a fase II depende fundamentalmente da variante de implementação do simplex que estamos usando:

- Se for o ingênuo, então só os índices da base são aproveitados.

- Se for o revisado, aproveitam-se os índices e também a matriz inversa de base (nesse caso deve-se ter atenção especial para linhas e colunas que tenham sido eliminadas no final da fase 1). Custos reduzidos são recomputados como normalmente é feito no revisado, ou seja, primeiro computa-se a sub-expressão que corresponde aos multiplicadores p'=cB'B-1, e depois usa-se as expressões cbarraj=cj-p'Aj.

- Se for o tabular, aproveita-se toda a parte do tableau que se refere ao problema original, que é tudo excluindo-se a linha 0. Note que para recalcular os custos reduzidos no tabular, dado que a matriz B-1 pode não estar imediatamente disponível, a expressão mais conveniente é calcular os custos como cbarraj=cj-cB'Tj, onde Tj é a coluna j do "miolo" do tableau, que por definição contém a expressão (B-1Aj).

Nos 3 casos, o fundamental é estar atento à parte que *não* se refere ao problema original, como a função objetivo auxiliar y1+y2+...+ym, as colunas do tableau relacionadas a estas variáveis artificiais, e também as restrições que tenham sido eliminadas no final da fase I (com as correspondentes linhas do tableau ou linhas e colunas de B-1 no revisado, conforme o caso).

Talvez a confusão tenha acontecido porque falamos na última aula de alguns casos *particulares* onde dava para identificar a matriz B-1 (ou uma versão levemente modificada dela) nas últimas colunas do tableau, quando o problema possuia uma identidade (ou algo próximo disso) no início. Vale ressaltar que para um problema em geral isso não é verdade.

Bom estudo!

Marcelo