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

Question

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

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

X ₁ > = 2
х ₂ + Х ₃ > = 13
и т.д.

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

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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