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.
Navegue entre tópicos
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 na prática para problemas de programação linear de tamanho moderado.
Além disso, o método simplex 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..
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.
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.
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 ao processo de pivoteamento.
Desta forma, o aprendizado do funcionamento do método, que é o que realmente importa, 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.
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
texto..
Algoritmo simplex dual
texto..
Algoritmo simplex primal-dual
texto..
