Pesquisa Operacional Simplex: Métodos quando não há base viável inicial

Pesquisa Operacional Simplex Parte 3 14112023 Outline O que fazer quando não há uma base viável inicial Continuação Degenerescência ciclagem convergência e complexidade computacional O que fazer quando não há uma base viável inicial Há duas variações do método Simplex para resolver problemas com variáveis artificiais O método do Big M ou Penalidades e O método das Duas Fases O método do Big M problemas de arredondamento numérico No método Big M as variáveis artificiais são fortemente penalizadas na função objetivo de modo a provocar rapidamente a sua anulação Neste caso o método Simplex tende naturalmente a eliminar da base as variáveis artificiais como se pretende dado que aquelas estão penalizadas com coeficientes arbitrariamente grandes M na maximização e M na minimização Este método porém sofre com problemas de arredondamento numérico M geralmente é muito grande em relação aos demais coeficientes O método do Big M Repare que os coeficientes de custo da função objetivo associados às variáveis artificiais são não nulos no slide anterior cjM onde j é índice de variável artificial o que não pode acontecer Logo a primeira atitude neste novo método consiste em determinar uma nova função objetivo que seja equivalente à anterior mas em que os coeficientes de custo das variáveis artificiais sejam nulos A nova função objetivo é calculada em função da anterior e das restrições onde existam variáveis artificiais O método do BigM O método do BigM O método do BigM O método do BigM O método do BigM O método do Big M quando não há solução O método do Big M quando não há solução O método do Big M quando não há solução O método das Duas Fases No método das Duas Fases o PPL é resolvido em duas fases distintas Na primeira fase procurase determinar se existem soluções viáveis para o problema original Caso existam obtémse uma solução básica viável que será a solução de partida inicial da fase seguinte A segunda fase consiste simplesmente na aplicação do método Simplex tal como foi descrito anteriormente O método das Duas Fases O método das Duas Fases Obtida uma solução para o problema auxiliar com as variáveis artificiais nulas fica determinada a solução básica de partida para o problema original Repare que uma solução nestas condições só se verifica quando o valor da FO artificial é igual a zero Portanto ao final da 1ª Fase tendose obtido a solução ótima do problema auxiliar estáse em uma das seguintes três situações O método das Duas Fases 1 z A 0 neste caso existe pelo menos uma variável artificial básica com valor estritamente positivo o problema original é inviável 2 z A 0 com todas as variáveis artificiais nãobásicas neste caso a solução do problema auxiliar é uma solução básica de partida para a 2ª Fase zA 0 com pelo menos uma variável artificial básica e nula neste caso a solução do problema auxiliar é uma solução viável para o problema original e temos dois casos a Se na linha referente à variável artificial que é VB existir coeficiente não nulo para alguma coluna nãobásica k yjk0 para qualquer que seja o valor do coeficiente de custo ck podemos fazer com que xk entre na base em lugar da variável artificial com o valor xk0 fazendo yjk0 sem que o valor da função objetivo se altere pois ckxk0 tratandose portanto de uma solução básica viável degenerada b Se na linha referente à variável artificial que é VB todos os coeficientes são nulos para todas as colunas nãobásicas k yjk0 então conseguimos anular uma equação do sistema Axb utilizando apenas transformações elementares sobre as equações do sistema Tratase portanto de uma restrição redundante que pode ser eliminada na verdade devemos eliminar a linha a e a coluna a ela associadas Nos casos 2 e 3 acima passar à 2ª Fase O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 2 z A 0 O método das Duas Fases exemplo do caso 1 z A 0 O método das Duas Fases exemplo do caso 1 z A 0 O método das Duas Fases exemplo do caso 1 z A 0 O método das Duas Fases exemplo do caso 1 z A 0 O método das Duas Fases exemplo do caso 3a sobra variável artificial na base com custo nulo mudança de base O método das Duas Fases exemplo do caso 3a sobra variável artificial na base com custo nulo mudança de base O método das Duas Fases exemplo do caso 3a sobra variável artificial na base com custo nulo mudança de base O método das Duas Fases exemplo do caso 3a sobra variável artificial na base com custo nulo mudança de base O método das Duas Fases exemplo do caso 3a sobra variável artificial na base com custo nulo mudança de base Simplex degenerescência ou degeneração Simplex degenerescência ou degeneração Simplex degenerescência ou degeneração Simplex degenerescência ou degeneração Simplex degenerescência ou degeneração Simplex degenerescência e suas consequências Degenerescência ou degeneração em PL Um PPL é dito degenerado quando há pelo menos uma solução básica viável com uma variável básica com valor zero ie uma solução básica degenerada A degeneração ocorre quando há empate no critério para determinação da variável que sai da base teste da razão Consequências da degeneração Quando um PPL possui muitas soluções básicas viáveis degeneradas o Simplex costuma ser ineficiente Quando um PPL é degenerado pode haver ciclagem o que pode interferir na convergência do algoritmo Simplex degenerescência e ineficiência Simplex degenerescência e ineficiência Simplex degenerescência e ineficiência Simplex degenerescência e ciclagem Exemplo de ciclagem de Beale FO MIN 34 x1 20x2 12 x3 6x4 sa 14 x1 8x2 x3 9x4 0 12 x1 12x2 12 x3 3x4 0 x3 1 x1 x2 x3 x4 0 Simplex degenerescência e ciclagem Z 34 20 12 6 0 0 0 0 Z 1 9 1 0 0 0 0 0 0 0 1 0 0 0 1 x 00000001 0 4 72 33 3 0 0 0 0 0 0 0 x 00000001 Simplex degenerescência e ciclagem Simplex degenerescência e ciclagem Simplex degenerescência e ciclagem Simplex degenerescência e ciclagem Simplex degenerescência e ciclagem O que muda é que ora consideramos uma variável nula como sendo VB ora a consideramos VNB A interpretação geométrica é que mudamos de base permanecendo no entanto no mesmo vértice Cada solução básica viável do PPL dado inclui três VB Como temos sete variáveis teremos sempre quatro VNB as quais devem assumir o valor zero Como para o vértice deste exemplo x0000001 temos seis variáveis nulas temos combinação de 6 4 a 4 ou seja 15 conjuntos compostos de quatro VNB Isto significa que existem quinze bases correspondendo ao mesmo vértice e resultando na mesma solução básica viável Solução do problema de ciclagem de Beale Simplex degenerescência e ciclagem Cabe mencionar que a ciclagem é um fenômeno raro na degeneração Na maioria das vezes uma regra simples como a que foi utilizada neste exemplo e que será vista em detalhes em seguida para o caso de indeterminação na escolha do pivô ou seja na escolha da variável que deixa a base é suficiente para evitar a ciclagem A indeterminação na escolha do pivô ou da variável que deixa a base está como já vimos relacionada à degeneração ou degenerescência FO MIN 34 x1 20 x2 12 x3 6 x4 sa Simplex degenerescência ciclagem e convergência Isso é importante pois na ausência de degeneração a convergência finita do método Simplex é garantida pelo fato de sempre gerarmos bases que implicam em um valor decrescente para a função objetivo Na presença de degeneração essa convergência deixa de ser garantida pelo fato de gerarmos bases que resultam no mesmo valor para a função objetivo De fato no caso da ciclagem é possível a repetição periódica das bases utilizadas pelo algoritmo 14 x1 8 x2 x3 9 x4 0 x1 4 folgada Simplex degenerescência ciclagem e convergência Regra para prevenir a ciclagem pivoteamento de Bland para problemas de minimização Dentre todas as variáveis xk candidatas a entrar na base ou seja dentre aquelas variáveis com custo reduzido negativo selecione aquela de menor índice k Dentre todas as variáveis candidatas a sair da base ou seja dentre aquelas variáveis que primeiro se anulam com o incremento de xk ou ainda para as quais há empate no teste da razão selecione aquela de menor índice 12 x1 12 x2 12 x3 3 x4 0 x1 1 ativa Simplex complexidade computacional A implementação do método Simplex é simples mas requer muitos cuidados para ser eficiente Solução inicial Degeneração Tratamento de matrizes esparsas Determinantes próximos de zero Atualização rápida da base e de sua inversa x3 1 x3 1 ativa Simplex complexidade computacional A complexidade do método Simplex depende Da complexidade computacional em cada iteração Do número de iterações ou operações de pivoteamento Na prática Observouse ao longo dos anos que o método geralmente executa Om operações de pivoteamento na média No pior caso Esta observação que ocorre na prática não é verdadeira para qualquer PPL e qualquer regra de pivoteamento Há exemplos de problemas não degenerados para os quais o método percorre todos os vértices do poliedro até encontrar a solução ótima como será visto a seguir x1 x2 x3 x4 0 Simplex complexidade de pior caso exponencial x 1010 FO 075 05 125 Simplex complexidade de pior caso exponencial Simplex complexidade de pior caso exponencial Simplex complexidade de pior caso exponencial Na figura b do slide anterior vêse a sequência com os 8 vértices percorridos pelo Simplex Portanto o Simplex é um algoritmo de complexidade de pior caso exponencial Mesmo assim para muitos problemas reais o método Simplex é bastante rápido o que faz dele um dos raros exemplos conhecidos de algoritmo teoricamente exponencial de comportamento eficiente na prática Simplex existe regra de pivoteamento imune a essa patologia Para várias regras populares de pivoteamento há exemplos como o indicado anteriormente que fazem o método Simplex percorrer todos os vértices da região viável até chegar ao ótimo Entretanto estes exemplos não excluem a possibilidade de existir uma regra de pivoteamento que não apresente o comportamento de pior caso exponencial Esta é uma das questões mais importantes em Teoria de Programação Linear ainda em aberto O fato é que não se conhece uma regra de pivoteamento imune a esta patologia Simplex existe regra de pivoteamento imune a essa patologia Para várias regras populares de pivoteamento há exemplos como o indicado anteriormente que fazem o método Simplex percorrer todos os vértices da região viável até chegar ao ótimo Entretanto estes exemplos não excluem a possibilidade de existir uma regra de pivoteamento que não apresente o comportamento de pior caso exponencial Esta é uma das questões mais importantes em Teoria de Programação Linear ainda em aberto O fato é que não se conhece uma regra de pivoteamento imune a esta patologia