método simplex e equações à diferença

Tema: Metódo Simplex e Equações à diferença

Método Simplex

Introdução O Método Simplex é um procedimento geral para resolver um Problema de Programação Linear. Foi desenvolvido em 1947 pelo matemático norte-americano George B. Dantzig e consiste em um método iterativo que percorre os pontos extremos do conjunto de soluções compatíveis do problema. Este método é formado por um grupo de critérios para escolha de soluções básicas que melhorem o desempenho do modelo, e também de um teste de otimalidade.
Para ser iniciado, é necessário se conhecer uma solução compatível básica (chamada solução inicial) do sistema. Posteriormente, é verificado se a presente solução é ótima. Se for, o processo está encerrado. Se não for ótima, é porque um dos pontos extremos adjacentes ao ponto extremo inicialmente adotado fornece para a função objetivo um valor melhor do que o atual. Para melhorar o valor da função objetivo, a mesma deve ser aumentar ou diminuir, conforme o problema seja de maximização ou minimização respectivamente. O Método Simplex faz então a mudança do ponto inicial para o ponto extremo adjacente que melhore o valor da função objetivo. O procedimento adotado para o ponto extremo inicial é repetido para este segundo ponto extremo. O processo finaliza quando, estando num ponto extremo, todos os pontos extremos a ele adjacentes, fornecem valores piores para a função objetivo. Algebricamente, um ponto extremo adjacente é uma solução compatível básica incluindo todas as variáveis básicas anteriores, com exceção de apenas uma delas. Achar, portanto, a próxima solução compatível básica (ponto extremo adjacente) exige a escolha de uma variável não básica para entrar na base em sua substituição. O Método Simplex compreenderá, portanto, os seguintes passos:
1) Achar uma solução compatível básica inicial.