Em suma, o método simplex consiste em uma família de algoritmos de otimização desenvolvidos para resolver problemas de programação linear.
Para conhecer um pouco mais sobre a programação linear, sua relevância e seu vasto campo de aplicação, visite o artigo histórias da programação linear.
O método simplex foi proposto por George B. Dantzig, no ano de 1947, e se tornou uma das técnicas mais utilizadas para resolver problemas de programação linear na indústria e na academia.
Além de ser o primeiro método proposto para resolver problemas de programação linear, o método simplex consiste em um dos mais relevantes algoritmos inventados no século XX.
Neste artigo, discutiremos os três principais algoritmos da família simplex: algoritmo simplex pimal, algoritmo simplex dual e algoritmo simlex primal-dual.
Saber qual algoritmo aplicar na resolução de um problema é algo extremamente importante. Na prática, os problemas são complexos e o tempo de resposta para a tomada de decisão, em muitos casos, necessita ser bastante curto, questão de segundos.
Então, venha conosco para descobrir mais sobre este fascinante tema.
Programação linear
A programação linear é uma área da matemática aplicada que desenvolve técnicas para encontrar a melhor solução para um problema, sujeito a um conjunto de restrições.
Essas restrições são expressas em forma de equações ou desigualdades lineares, e a função objetivo é uma função linear que visa, por exemplo, maximizar lucros ou minimizar custos. Isto é, visa obter a melhor solução possível para o problema.
Modelagem matemática
Sendo assim, para que o método simplex possa ser empregado, o problema a ser resolvido precisa ser representado, formulado, através de um conjunto de equações lineares e uma função objetivo, também linear.
Após esta etapa, conhecida como processo de modelagem, um modelo matemático é gerado para o problema. Veja, no vídeo a seguir, como obter o modelo para um problema.
O modelo é representado por uma matriz A, um vetor b, e um vetor c. Todos eles com coeficientes (números) reais.
No caso do modelo apresentado no vídeo acima, as restrições são representadas por inequações. Mas cada inequação pode ser facilmente convertida para uma equação, adicionando uma nova variável ao problema, chamada de variável de folga.
Então, já considerando as restrições do problema como equações, a matriz A possui uma coluna para cada uma das n variáveis do problema (as originais e as de folga), e uma linha para cada uma das m restrições (equações).
O vetor c possui um valor para cada variável, enquanto que o vetor b é composto pelos termos independentes das m equações.
Na prática, o número de variáveis, n, é muito maior do que o das equações, m. Assim, cada conjunto de m colunas da matriz A é candidato a gerar uma base pela qual uma solução para o problema pode ser obtida.
Ideia geral do simplex
Então, após obter os dados, matriz A e vetores b e c, o método simplex aplica uma série de operações matriciais, como multiplicação de matrizes, resolução de sistemas de equações lineares e cálculo da matriz inversa, até encontrar, se existir, uma solução ótima para o problema.
Estas operações são necessárias para a seleção de uma variável para entrar e uma para sair da base, em cada iteração do método, visando a obtenção de soluções cada vez melhores.
O método simplex também pode ser interpretado geometricamente. O conjunto das soluções, que atentem todas as restrições do problema de programação linear, chamado de conjunto viável, forma um poliedro. Já a função objetivo é representada pelo vetor de custos, c, que aponta para onde o valor da função objetivo aumenta.
Desta forma, cada ponto extremo do poliedro, que pode ser calculado através de uma combinação de m colunas da matriz A, é um candidato a solução ótima do problema.
Logo, a ideia geométrica do simplex consiste em caminhar, de ponto extremo a ponto extremo adjacente, melhorando o valor da função objetivo em cada iteração. Veja esta ideia no vídeo a seguir.
Mesmo tendo sido superado teoricamente pelos métodos de pontos interiores, e também no que tange a resolução de problemas mais complexos, de grande porte, o método simplex ainda é amplamente utilizado, pois na prática, para problemas do mundo real, oferece uma ótima eficiência computacional.
Além disso, o método simplex com sua fundamentação teórica serve como uma base para a teoria da otimização linear e é um exemplo importante de algoritmo de otimização.
Forma padrão
Temos que qualquer problema de programação linear pode ser representado, de modo equivalente, em um formato onde todas as variáveis são não negativas e as demais restrições são de igualdade.
Isto é feito, por exemplo, adicionando variáveis de folga, para transformar restrições de menor ou igual em igualdade, ou variáveis de excesso, para transformar restrições de maior ou igual em igualdade. Assista o vídeo explicativo abaixo.
Os algoritmos da família simplex
Dada a complexidade em resolver problemas reais, de programação linear, devido suas dimensões não serem pequenas, se faz necessário alguns cuidados.
Não basta ter e aplicar um algoritmo, ele deve se comportar bem e fazer o menor número de contas possível para resolver o problema.
Caso contrário, ele pode não obter a solução para o problema, por exemplo, por esgotar a memória do computador antes de finalizar sua execução. Ou, também, poderia levar um tempo inaceitável para resolver o problema.
Logo, é importante avaliar os dados do problema para, então, saber qual é o algoritmo mais adequado a ser aplicado.
Neste sentido, várias variantes do método simplex foram desenvolvidas.
Os três principais algoritmos, que são: algoritmo simplex primal, algoritmo simplex dual e algoritmo simplex primal-dual, serão discutidos nesta seção. Além de uma versão mais eficiente para estes métodos.
Antes, porém, vamos falar sobre duas metodologias possíveis para se efetuar os cálculos durante a aplicação dos algoritmos simplex.
Simplex tabular x Simplex revisado
O simplex tabular (quadro), presente em boa parte dos livros de pesquisa operacional e programação linear, é uma estrutura criada para aplicar o método simplex. O objetivo era ter todas as informações da resolução do problema em um quadro/tabela.
Então, o simplex tabular consiste em colocar todos os dados do problema, isto é, a matriz A e os vetores b e c, em uma única tabela (matriz) e então fazer as contas ao longo das iterações.
Desempenho computacional
Há duas importantes observações (críticas) a serem feitas em torno do simplex tabular. Uma delas diz respeito à ineficiente computacional. O próprio autor do método Simplex, George B. Dantzig, propôs em 1953 (o artigo está citado no final desta página) uma nova versão para o método, mais eficiente.
Como dito acima, os problemas tratados na prática são de dimensões consideráveis e, em cada iteração do simplex, o número de colunas da matriz A para as quais não é necessário fazer contas é grande.
Neste sentido, o simplex tabular faz muito esforço desnecessário, uma vez que ele realiza os cálculos sobre todas as colunas da matriz A.
Considerando ainda que o simplex leva várias iterações para resolver um problema, esta técnica se torna impraticável de ser implementada, por exemplo.
Processo de ensino e aprendizagem
Outra importante observação, em torno do tabular, diz respeito ao processo de aprendizagem. Com ele, as justificativas das decisões durante a aplicação do método simplex são “mascaradas”.
Como todas as informações aparecem automaticamente no quadro simplex, após a redução dele à forma canônica (por meio de operações elementares por linhas), o método se resume basicamente ao processo de pivoteamento.
Desta forma, o aprendizado do funcionamento do método, que é o que realmente importa nas disciplinas que abordam tal tópico, acaba sendo substituído pela memorização de algumas regrinhas.
Logo, como o objetivo de estudar algoritmos é entender bem o seu funcionamento e saber identificar quando aplicá-lo, então, também não recomendamos o uso do tabular para esta finalidade.
A revisão do método simplex
Com o objetivo de definir uma metodologia mais eficiente para os cálculos durante a aplicação do simplex, Dantzig e Orchard-Hays desenvolveram para a RAND Corporation, em 1953, a versão simplex revisado.
Tal versão visava tratar a informação estritamente necessária para o cálculo e, assim, reduzir fatores imprescindíveis, como: o número de operações realizadas em cada iteração, o espaço de memória, e o tempo computacional.
Portanto, no simplex revisado calculamos apenas o que realmente é necessário em cada passo. Neste sentido, antes de realizar qualquer operação, é necessário saber o significado de cada elemento que importa nas tomadas de decisão do método simplex.
O conhecimento e entendimento de elementos como os custos reduzidos, por exemplo, que são capazes de nos dizer se uma solução é (ou não) ótima e, caso não seja, nos indicar pontualmente qual decisão tomar para melhorar a solução atual, é indispensável no que tange ao estudo do método simplex. Veja, no vídeo a seguir, como analisar os custos reduzidos em um exemplo simples.
Então, em cada iteração do simplex revisado, trabalhamos com uma matriz inversa pela qual se pode obter todas as informações relevantes para o método. Isto é feito através de operações matriciais básicas, como a multiplicação e a soma/subtração de matrizes.
Algoritmo simplex primal
O algoritmo simplex primal, desenvolvido para resolver um PPL na forma padrão, isto é, com restrições de igualdade (Ax = b) e variáveis não negativas, requer uma matriz básica B (formada por m colunas de A), que gera uma solução básica viável (SBV). As SBVs de um PPL são os pontos extremos do seu conjunto viável.
Em cada iteração do algoritmo simplex primal, os custos reduzidos das variáveis não básicas são calculados. Caso nenhum deles indique melhoria para a função objetivo, a SBV atual é ótima. Caso contrário, algum custo reduzido que indicando melhoria é escolhido e o vetor direção simplex é calculado, para identificar a variável básica que sairá da base. Se nenhuma delas for candidata, significa que o PPL é ilimitado. Segue-se um vídeo explicando passo-a-passo a resolução de um exemplo com o algoritmo.
Há uma atividade bem prática sobre o simplex primal, utilizando os apps A+Exemplo e A+Prática para este tópico, disponível na versão anterior da APlus Platform. O link para a atividade se encontra no final desta página, em referências.
Cálculo eficiente da inversa
De uma iteração para outra durante a execução do algoritmo simplex, trocamos uma única coluna na base. Isto é, alguma coluna aj da matriz A, que não está em B, entra no lugar de alguma coluna ai que está em B. Vamos chamar de k a posição em B onde esta troca acontece.
Neste sentido, a inversa da matriz básica atual é muito “próxima” da inversa da matriz básica da iteração seguinte, a qual precisamos obter para prosseguir com os cálculos. Quando multiplicamos a inversa anterior na nova matriz básica, teremos todas as colunas da matriz identidade exceto na coluna k. O que teremos na coluna k é o vetor direção simplex, h j = B -1 . aj.
Montando uma matriz M com as colunas da identidade nas posições diferentes de k, e a coluna k com 1 /h jk na posição k e – h jf /h jk nas demais posições (f de 1 a m exceto k), então basta multiplicar M pela inversa anterior para obter a nova inversa. O valor na posição k do vetor h j , dado por h jk é diferente de zero devido as escolhas feitas em cada iteração do simplex.
Deste modo, o cálculo da inversa em cada iteração do simplex, operação mais “pesada” do processo, se resume a uma multiplicação de matrizes, onde uma delas (M) é bastante esparsa (muitos zeros), o que simplifica bastante os cálculos. Isto implica em uma redução considerável no esforço computacional, além de reduzir possíveis erros de arredondamento.
No capítulo 3 do livro intitulado Otimização Linear, de M. Fampa e N. Maculan, citado no final desta página, você encontra mais detalhes sobre este tópico, com demonstração e um exemplo.
Algoritmo simplex dual
No algoritmo simplex dual, é preciso que se tenha como entrada uma matriz básica B, de A, com os custos reduzidos atendendo as condições de otimalidade. Isto é equivalente a dizer que B gera uma solução dual viável (para mais detalhes neste sentido, estude dualidade em PL – Programação Linear).
As soluções de cada iteração do simplex dual são conhecidas como “super ótimas”, por atenderem as condições de otimalidade. Além de manter essa propriedade, as soluções geradas sempre atendem ao sistema Ax = b. Assim, uma das condições de parada do algoritmo é quando todas as variáveis são não negativas. Neste caso, além de viável, a solução atende as condições de otimalidade, logo é ótima para o problema. Durante cada iteração do algoritmo, também podemos identificar que é impossível se ter Ax = b com um vetor x não negativo. Ou seja, neste caso o problema é inviável.
Algoritmo simplex primal-dual
Para um bom entendimento do algoritmo simplex primal-dual também é necessário o estudo da dualidade em PL, com atenção especial para o teorema das folgas complementares.
O requisito para aplicar este algoritmo é de se ter uma solução dual viável inicial. Dual é um outro problema de PL, o qual é associado ao problema que se deseja resolver. A solução dual requertida aqui basta ser viável, não precisa estar relacionada à uma base como no simplex dual.
Com a solução dual, é calculado um vetor com as folgas duais. A partir dele e do PPL original, é gerado e resolvido, através do simplex primal fase 2, um PPL chamado de primal restrito, o qual obedece o teorema das folgas complementares. No algoritmo simplex primal-dual, ao contrário do simplex dual, as soluções geradas em cada iteração são não negativas, mas o Ax = b só é atendido no final, e é a condição de parada do algoritmo encontrando uma solução ótima. Nos casos em que o PPL original é inviável, após a resolução do primal restrito de alguma iteração, isto será detectado e o algoritmo finalizado.
Método das duas fases do simplex
Na resolução de problemas de PL para os quais não temos uma entrada para aplicar o primal fase 2, nem para o dual e nem para o primal-dual, podemos utilizar o método das duas fases do simplex, onde na primeira fase é realizada uma busca por um ponto de partida e, na segunda, é realizada a resolução do problema a partir do ponto obtido na fase 1.
No simplex primal, esta primeira fase é chamada de fase de viabilidade e a segunda de fase de otimalidade. Assista o vídeo abaixo para acompanhar, passo-a-passo, a aplicação do simplex fases 1 e 2 na resolução de um exemplo.
Para este tópico, também te oferecemos uma atividade bem prática, disponível na versão anterior da APlus Platform. O link para a atividade se encontra no final desta página, em referências.
Simplex com variáveis canalizadas
As versões mais eficientes dos algoritmos da família simplex são as que fazem tratamento implícito de variáveis canalizadas. Em muitos casos, as variáveis do problema estão restritas a ser maiores do que um limite inferior, não nulo, e menores do que um limite superior.
Caso estas restrições sejam tratadas como as demais, para cada variável deste tipo, outras duas, uma de folga e outra de excesso, devem ser adicionadas ao modelo. Com isso, o número de variáveis e restrições do PPL, quando convertido para a forma padrão, pode triplicar. Isto implica diretamente no custo computacional.
O tratamento implícito de variáveis canalizadas, feito nesta versão do simplex, é similar ao que é feito para garantir a não negatividade das variáveis em cada iteração do algoritmo simplex tradicional.
Veja o capítulo 8 de M. Fampa e N. Maculan, Otimização Linear, para mais detalhes e exemplos. O link está no final desta página.
Conclusão
Como discutimos neste texto, a decisão de qual método aplicar na resolução de problemas é fundamental, pois na prática a dimensão dos problemas é considerável. Isto pode implicar em um elevado esforço computacional e, dependendo da escolhida, o problema sequer será resolvido.
Vimos também que, dos algoritmos da família simplex, as versões revisadas e com tratamento implícito de variáveis canalizadas são as mais eficientes. Para escolher entre o primal, o dual e o primal-dual, precisamos saber se temos algum dado de entrada. Como uma base que gera uma SBV, neste caso aplicamos o simplex primal, ou uma base que gera uma solução dual viável, neste caso aplicamos o simplex dual, ou apenas uma solução dual viável, caso para o simplex primal-dual. Caso contrário, utilizamos o simplex fases 1 e 2.
Referências
SIAM – George B. Dantzig Prize
Atividade algoritmo Simplex primal fase 2 – uso do par de aplicativos A+Exemplo e A+Prática
Otimização Linear – Márcia Fampa e Nelson Maculan
Atividade Simplex fases 1 e 2 – uso do par de aplicativos A+Exemplo e A+Prática
