(Parte 1 de 3)

Métodos Quantitativos

Aula_10 Método Simplex

Denilson C. Resende http://buscatextual.cnpq.br/buscatextual/visualizacv.jsp?id=K4761097J7&tipo=completo&idiomaExibicao=2 resendedc@gmail.com

Nem todos os problemas de programação linear estão no formato padrão, isto é, problemas de maximização com todas as restrições do tipo menor ou igual.

Quando o formato é não padrão, devemos utilizar diversos métodos antes de podermos utilizar o simplex.

Que formas não padrão são essas?

Problemas para minimizar com restrições do tipo menor ou igual;

Restrições do tipo maior ou igual;

Restrições com igualdades.

2.5-Problema na forma não padrão

Problemas para minimizar com restrições do tipo menor ou igual

Quando tivermos um problema em que todas as restrições são do tipo menor ou igual e a função-objetivo for de minimização, devemos alterar o problema como mostra:

2.5-Problema na forma não padrão

x Sujeito xxZMin x Sujeito xxZwMax

Esta modificação se baseia no fato de a igualdade

Min Z = Max –Z

Ser sempre válida (quando a solução ótima existir). Mas nem sempre as modificações são tão simples. considere o problema o problema

2.5-Problema na forma não padrão x Sujeito xxZMax

Vamos introduzir as variáveis de folga 2.5-Problema na forma não padrão x x x Sujeito xxZMin

x x

Esta restrição é diferente das primeiras por causa do sinal da restrição. Se utilizássemos o mesmo artifício utilizado anteriormente, isto é, definíssemos uma variável como a diferença entre RHS e LHS e a considerássemos a variável criada maior ou igual a zero, esta não corresponderia ao desejado

O valor de x5 seria, portanto, obrigatoriamente positiva. Isto resolveria o problema de que todas as variáveis de um problema a ser resolvida pelo problema simplex devem ser positivas.

Contudo, um outro problema apareceria: Encontrar a solução inicial. O dicionário inicial e a solução (óbvia) associada a ele

Sabemos que

2.5-Problema na forma não padrão x x x x

A maneira de resolver este problema e outros que virão em que encontrar a solução trivial não é trivial envolve a utilização de tais métodos como “M Grande” e “Função Objetiva artificial”.

Ambos se baseiam na introdução de uma variáveis artificiais (que não existem no problema) para facilitar o descobrimento da solução inicial

2.5-Problema na forma não padrão x xxZ

Axxxxx

Axxx x xxZ

Dicionário modificado inicialDicionário Artificial

Com isso a nova solução inicial (com a variável artificial) é: fazendo x1=0 e x2=0, temos Z=0.

O problema atende todos os requisitos do método simplex, porém não é o problema que queremos resolver, já que existe a variávelA1, que não está presente no problema original. Para este problema ser igual ao problema ser igual ao problema inicial, A1=0, com isso estaremos encontrar a solução para o nosso problema original.

O método da “Função-objetivo-artificial” se baseia no fato de encontrar a primeira solução para o problema original (o que queremos resolver).

2.5-Problema na forma não padrão

Axx

A seguir veremos como utilizar o método para solucionar o problema.

Problemas com restrições de Maior ou igual

Nos casos de restrições de maior ou igual o procedimento para o método da “Função-objetivo-artificial” consiste em introduzir uma variável de excesso (com sinal negativo), no lado esquerdo da igualdade, como mostrado anteriormente (slide 7), criando um dicionário artificial e encontrando a solução óbvia.

O segundo passo do método seria o de se resolver o problema alterado, representado pelo dicionário artificial, solução ótima temos A1=0,se A1diferente de 0, o problema não tem solução viável

2.5-Problema na forma não padrão

No caso do problema alterado nosso objetivo de levarmos a(s) variável(is) artificial(is) introduzida(s) no problema para zero.

O nosso objetivo é equivalente ao de minimizar o somatório destas variáveis.

Se as variáveis forem simultaneamente para zero na solução ótima nossa função objetivo artificial (daí o nome do método) terá valor zerado na solução ótima. Este método é também denominado de método de duas fases, já que está divido em duas partes.

1- Na primeira ao resolver o problema alterado, apenas encontramos uma solução viável para o problema original

2- Na segunda é que efetivamente resolvemos o problema.

2.5-Problema na forma não padrão

Vamos trabalhar no problema passo-a-passo, para que possa ser compreendido.Temos que

2.5-Problema na forma não padrão x Sujeito xxZMax

Axxxxx

(Parte 1 de 3)

Comentários