Como resolver um sistema de desigualdades?

Question

Reduzi meu problema (algoritmo de layout de tabela) ao seguinte problema:

Imagine que tenho N variáveis ​​X₁, X₂, ...,X_N.Também tenho um número (indeterminado) de desigualdades, como:

X₁ >= 2
x₂ +X₃ >= 13
etc.

Cada desigualdade é uma soma de uma ou mais variáveis ​​e é sempre comparada a uma constante usando o operador >=.Não posso dizer antecipadamente quantas desigualdades terei de cada vez, mas todas as variáveis ​​têm que ser não negativas, então já é uma para cada variável.

Como resolver este sistema de forma que os valores das variáveis ​​sejam os menores possíveis?

Adicionado: Leia o artigo da Wikipedia e percebi que esqueci de mencionar que as variáveis ​​​​têm que ser números inteiros.Acho que isso torna tudo NP-difícil, hein?

Answer 1

Minimizando x1 + x2 + ...onde xi satisfaz restrições lineares é chamado de Programação Linear.É abordado com alguns detalhes em Wikipédia

Answer 2

O que você tem aí é bastante básico Programação linear problema.Você quer maximizar a equação X_1 + ... + X_n sujeito a

X_1 >= 2
X_2 + X_3 >= 13
etc.

Existem inúmeros algoritmos para resolver esse tipo de problema.O mais conhecido é o Algoritmo simples que resolverá sua equação (com certas ressalvas) com bastante eficiência no caso médio, embora existam problemas de LP para os quais o algoritmo Simplex exigirá muitas etapas exponencialmente para resolver (no tamanho do problema).

Existem várias implementações de solucionadores LP.Por exemplo LP_Resolver deve satisfazer a maioria dos seus requisitos

Answer 3

Você também pode postar diretamente seu modelo linear na plataforma NEOS (http://neos.mcs.anl.gov/neos/solvers/index.html).O que você precisa fazer primeiro é escrever seu modelo em uma linguagem algébrica como AMPL.Então o NEOS resolverá o modelo e retornará os resultados por e-mail.

Answer 4

Programação linear