Como iniciar o método Simplex a partir de um ponto interno viável?

Eu tenho um algoritmo que gera uma solução viável para um problema de programação linear. No entanto, é muito provável que este não seja um ponto de partida. Isso o torna inadequado para uso direto como solução inicial viável para um solucionador Simplex limitado. Como posso encontrar com eficiência um ponto de vantagem dessa solução que posso usar?

Em resumo, como posso iniciar o método Simplex a partir de um ponto interno viável?

Todo livro sobre otimização linear explica o método simplex como um algoritmo de dois estágios: o primeiro para encontrar um canto viável como ponto de partida e o segundo para encontrar o ideal. O primeiro usa um problema duplo. Veja D. Bertsimas e JN Tsitsiklis: "Introdução à otimização linear" , por exemplo.

A razão pela qual precisamos da abordagem em duas fases é que normalmente é difícil encontrar qualquer ponto viável - em espaços dimensionais altos, o conjunto viável é muito pequeno comparado com, por exemplo, a caixa da unidade. Da sua pergunta, parece que você tem uma maneira diferente de encontrar pelo menos um ponto possível e, nesse caso, pode ser possível gerar um vértice do poliedro possível a partir deste ponto. Uma idéia seria usar a seguinte abordagem: cada restrição de desigualdade representa um meio espaço separado por um hiperplano. Dado um ponto possível , encontre os hiperplanos n + 1 mais próximos de x $x^\ast$$n+1$$x^\ast$e pegue a interseção deles. Intuitivamente, esse vértice deve ser viável, embora eu admita que seria necessário pensar um pouco mais sobre isso.

Infelizmente, a solução de Wolfgang Bangerth não garante que funcione:

$i$$i$$(n-i)$$n$

Na verdade, existem muitas abordagens diferentes para a fase I no método simplex. Em particular, existem algoritmos de fase I que usam iterações simplex simplex primárias e outros algoritmos de fase I que usam iterações simplex duplas. Aqui está uma abordagem muito geral que pode ser facilmente adaptada para usar uma solução viável conhecida. Esta versão usa o método simplex duplo na fase I e o método simplex primal na fase II, mas há uma variante que usa iterações simplex primárias na fase I e iterações simplex duplas na fase II que mencionarei no final. A abordagem que vou descrever aqui é discutida em muitos livros didáticos sobre programação linear. Por exemplo, veja o texto de Robert Vanderbei .

Suponha que estamos resolvendo

$\max cx$

sujeito a

$Ax=b$

$l \leq x \leq u$

onde do tamanho por . Por uma questão de simplicidade, suponha que as linhas de sejam linearmente independentes (isso pode ser conseguido por uma fatoração reveladora da classificação).$A$$m$$n$$A$

1. Escolha uma base inicial. Esta é uma coleção de variáveis ​​para que as colunas correspondentes de formem uma matriz não singular . As demais variáveis ​​não básicas podem ser definidas para seus limites superior ou inferior (ou zero se uma variável não tiver limites). $m$$A$$B$

Uma maneira fácil de fazer isso em sua solução inicial é selecionar como variáveis ​​básicas as variáveis ​​que estão mais distantes de seus limites na solução viável conhecida e, em seguida, verificar se não é singular. Pode ser necessário modificar a base para tornar não singular. O ponto aqui é que existem muitas bases possíveis, mas essa tem como variáveis ​​básicas as variáveis ​​que parecem estar corretas em sua solução viável. $B$$B$

Resolva as equações para obter os valores das variáveis ​​básicas. $Ax=b$

2. A solução básica que você obtém provavelmente será primordial inviável no sentido de que algumas das variáveis ​​primárias estão fora de seus limites. Também é provável que seja duplamente inviável no sentido de que alguns dos custos reduzidos das variáveis ​​não básicas apresentam sinais errados (por exemplo, variáveis ​​não básicas nos limites inferiores com custos reduzidos positivos ou variáveis ​​não básicas nos limites superiores com custos reduzidos negativos).

Superaremos esse problema alterando a função objetivo para uma que seja dupla viável. Para cada variável não básica em seu limite inferior, subtraia uma grande quantidade positiva do coeficiente da função objetivo. Para cada variável não básica em seu limite superior, adicione uma grande quantidade positiva ao coeficiente. Isso garante que o dicionário seja duplo viável. $M$$M$

O objetivo dessa modificação da função objetivo é tentar trabalhar em direção à viabilidade primordial, mas também avançar em direção à otimização em relação à função objetivo original. Você quer que seja grande o suficiente para ter dupla viabilidade, mas deseja manter o máximo de influência possível da função objetivo original. $M$

3. Execute métodos simplex duplos para obter uma solução básica que seja ao mesmo tempo primal viável (todas as variáveis ​​básicas dentro dos boudns) e viável dupla (todos os custos reduzidos têm o sinal desejado.) Essa solução é ideal para o problema da fase I.

4. Substitua a função objetivo modificada da fase I pela função objetivo original. Agora você terá uma solução básica que é primal viável (alterar a função objetivo não afeta isso), mas que é dupla inviável. Execute iterações simplais primárias para voltar à otimização.

Uma alternativa óbvia a essa abordagem seria modificar o lado direito b no início da fase I, usar iterações simplex primárias na fase I para obter a otimização e, em seguida, colocar o lado direito original de volta na fase II e usar iterações simplex duplas na fase II.

Eu estava procurando a solução para uma pergunta semelhante: para um programa linear esparso muito grande, apenas o método simplex testado funciona, mas somente quando a solução 0 padrão é viável. Parece que o algoritmo da fase um (como no linprog do Matlab) é ruim. E o código-fonte da fase um é tão complexo para substituí-lo por outro algoritmo, como o algoritmo genético; portanto, um método para contornar isso é fazer a transformação linear do problema original, de modo que nas novas variáveis ​​a solução viável inicial fornecida seja 0, e isso 0 será usado pela fase um sem usar seu próprio método para encontrar um ponto de partida diferente.

Ao testar esse método, passo a passo através de linprog.m, simplex.m, simplexpresolve.m e simplexphaseone.m, nos casos em que apenas restrições de desigualdade são usadas, confirma-se que o 0 padrão será usado para as variáveis ​​originais, em que as variáveis ​​de folga terão as diferenças. Portanto, a transformação linear pode deslocar x0 para simplex, impedindo intencionalmente o usuário de fornecer x0. Você pode ver a mensagem "O ponto inicial padrão é possível, ignorando a Fase 1". Por outro lado, geralmente o GA pode encontrar uma solução próxima do programa linear para 0,01% usando tempos duplos ou triplos, portanto, pode não merecer os esforços da transformação linear dessas restrições, objetivo e limites, especialmente quando as restrições são criadas artificialmente .