A Eng de Processos

1. Introdução

A Pesquisa Operacional consiste no uso de modelos matemáticos, estáticas e algoritmos para auxiliar no processo de tomada de decisão, de forma a analisar problemas complexos e reais, com a finalidade de aperfeiçoar o seu desempenho.  

A modelagem matemática, por sua vez, é o processo de obtenção de um modelo específico para descrever matematicamente uma situação real, fazendo com que seja possível compreendê-lo e aplica-lo em áreas como economia, administração, engenharia e finanças, com o objetivo principal de otimiza-lo.

Um exemplo prático desta aplicação seria uma empresa que, ao fabricar um produto, deve considerar pontos como a quantidade ideal de mão de obra, equipamentos, matéria-prima e fornecedores, de forma que o lucro da produção seja máximo, e o seu custo seja mínimo. Com estas variáveis, o objetivo da pesquisa operacional será montar um modelo matemático que otimize a produção, dentro das especificações da empresa analisada.

Para facilitar a resolução destes problemas, o operador poderá utilizar a função Solver, do programa Excel da Microsoft, onde o cálculo e a solução são rapidamente feitos e demonstrados.

Após a modelagem do processo, onde a equação é escrita e suas restrições são apontadas, existem duas maneiras de demonstrar a resolução do problema: Método Gráfico e Método Simplex. Ambos os métodos serão explicados nos próximos capítulos.

1. Método Simplex

O Método Simplex é o processo que irá viabiliza a otimização da solução da função objetivo em cada etapa, onde o mesmo só será finalizado quando não for mais possível melhorar o valor obtido, de forma que todas as restrições sejam satisfeitas. Ou seja, o processo é encerrado no momento em que a função ótima seja alcançada.

É importante pontuar que o método Simplex só trabalha com restrições de problemas cujas desigualdades sejam do tipo "≤" (menor ou igual) e seus coeficientes independentes sejam maiores ou iguais a 0. Por isso, é necessário padronizar as restrições para atender aos requisitos do método antes de iniciar o processo.

Ainda assim, depois deste processo, caso apareçam restrições do tipo "≥" (maior ou igual) ou "=" (igualdade), e que não seja possível alterá-las, será necessário utilizar outros métodos de resolução como, por exemplo, o método das Duas Fases.

1. Características:

O método simplex só pode ser utilizado na solução de problemas de programação linear se o problema estiver padronizado no formato: max/min z = cx 

Sendo as restrições:

• Ax = b
• x ≥ 0
• b ≥ 0

Para converter a inequação em uma equação é possível utilizar as variáveis de folga (utilizadas para converter uma inequação do tipo “≤” em "=") e as variáveis de excesso (utilizadas para converter uma inequação do tipo “≥” em "=").

Sendo as características para o sistema linear de equações:

• Todas as variáveis são não-negativas:
• Todos os bi’ são não-negativos;
• Todas as equações iniciais do sistema são do tipo " ≤ ".

Dessa forma, quando padronizadas, só serão encontradas as variáveis de folga. Apenas no caso de uma das características apontadas não ocorrer, será necessário considerar o Método Simplex de Duas Fases para solucionar a questão.

1. Metodologia:

Para implementar o Método Simplex é necessária uma solução inicial que seja viável. Assim, o método irá verificar se esta solução é ótima, identificando se algum dos vértices fornecem um valor menor para a função objetivo que a atual (no caso de problemas de minimização). Então, é feita uma mudança na direção do vértice, para que este diminua a função objetivo a fim de obter, enfim, o vértice ótimo. O processo terminará quando todos os pontos extremos adjacentes fornecerem valores maiores para a função objetivo.

Em resumo, o Método Simplex é consistido das seguintes etapas:

1. Encontrar a solução inicial viável;
2. Verificar se a solução é ótima;
3. Caso a solução não seja ótima, determinar a variável não básica que deve entrar na base;
4. Determinar a variável básica que deve sair da base;
5. Atualizar o sistema de forma que a nova solução seja viável;
6. Verificar então se esta é ótima.

1. Tipos de Otimização:

O objetivo do Método Simplex é, sem dúvidas, otimizar o valor da função objetivo. Com isso, é possível analisar que existem duas opções de otimizações, que irão ser aplicadas de acordo com o epicentro do problema, onde podem ser obtidos o maior valor ótimo (maximização), ou o menor valor ótimo (minimização).

No algoritmo criado, existem diferenças a respeito do critério de parada para finalizar as condições de entrada e saída da base, dependendo do objetivo da solução. Estas são:

• Minimização: O critério de parada será quando não aparecer nenhum valor positivo na linha Z. O critério de entrada na base será quando aparecer o maior valor positivo na linha Z, indicando a entrada na base da variável Pj. Por fim, o critério de saída de base, será denominada a variável de saída o menor quociente P0/Pj dos valores negativos.
• Maximização: Por sua vez, o critério de parada será quando não aparecer nenhum valor negativo na linha Z. O critério de entrada de base será quando o menor valor negativo aparecer na linha Z, indicando a entrada na base da variável Pj. Já o critério de saída da base será denominada a variável de saída o menor quociente P0/Pj dos valores positivos.

Tornando assim, um método o oposto do outro.

1. Mudança de Sinal:

Para que seja possível usar o método Simplex, é preciso que todos os termos independentes da equação sejam não negativos.

Para que isso aconteça, caso alguma das restrições possua um termo independente menor que zero, será necessário multiplicar por “-1” os dois lados da equação. Assim, com a mudança de sinais nas restrições, torna-se viável a aplicação do Método na modelagem.

1. Desenvolvimento do Método:

A partir do momento em que o modelo é padronizado, é preciso verificar se a aplicação será pelo Método Simplex, ou pelo Método das Duas Fases.