Как решить систему неравенств?

Question

Я свел свою проблему (алгоритм разметки таблицы) к следующей проблеме:

Представьте, что у меня есть N переменных X ₁ , X ₂ , ..., X _N . У меня также есть некоторое (неопределенное) количество неравенств, например:

X ₁ > = 2
x ₂ + X ₃ > = 13
и др.

Каждое неравенство представляет собой сумму одной или нескольких переменных и всегда сравнивается с константой с помощью оператора > =. Я не могу заранее сказать, сколько неравенств у меня будет каждый раз, но все переменные должны быть неотрицательными, так что это уже одно для каждой переменной.

Как решить эту систему таким образом, чтобы значения переменных были как можно меньше?

Добавлено: . Прочитав статью в Википедии, я понял, что забыл упомянуть, что переменные должны быть целыми числами. Думаю, это делает его NP-сложным, а?

Answer 1

Минимизация x1 + x2 + ..., где xi удовлетворяют линейным ограничениям, называется линейным программированием. Это подробно описано в Википедии

Answer 2

У вас есть довольно простая линейное программирование . Вы хотите максимизировать уравнение X_1 + ... + X_n при условии

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

Существует множество алгоритмов для решения этой проблемы. Наиболее известным является симплексный алгоритм , который достаточно эффективно решит ваше уравнение (с некоторыми оговорками) в средний случай, хотя существуют проблемы ЛП, для которых алгоритм Simplex потребует экспоненциально много шагов для решения (в размере задачи).

Существуют различные реализации решателей LP. Например, LP_Solve должен удовлетворять большинству ваших требований

Answer 3

Вы также можете напрямую публиковать свою линейную модель на платформе NEOS ( http: / /neos.mcs.anl.gov/neos/solvers/index.html ). Сначала вам нужно написать свою модель на алгебраическом языке, таком как AMPL. Затем NEOS решит модель и вернет результаты по электронной почте.

Answer 4

Линейное программирование