Решение неравенства для минимального значения

Question

Я работаю над проблемой программирования, которая сводится к уравнению и неравенству:

x[0]*a[0] + x[1]*a[1] + ... x[n]*a[n] >= D
x[0]*b[0] + x[1]*b[1] + ... x[n]*b[n] =  C

Я хочу найти значения X, которые дадут абсолютный минимум C, учитывая входные данные D и списки, а также A и B, состоящие из a[0 - n] и b[0 - n ] .

Я сейчас решаю проблему в Python, но в целом проблема не зависит от языка.

ОБНОВЛЕНИЕ РАЗЪЯСНЕНИЯ: коэффициенты x[0 - n] ограничены набором неотрицательных целых чисел.

Answer 1

Это похоже на проблему линейного программирования . Симплексный алгоритм обычно дает хорошие результаты. Он в основном пересекает границы подпространства, ограниченного неравенствами, в поисках оптимума.

Подумайте об этом визуально: каждое неравенство обозначает полупространство, плоскость в n-мерном пространстве, в которой вы должны находиться справа. Ваша служебная функция - это то, что вы пытаетесь оптимизировать. Если пространство закрыто, оптимум будет на одной из вершин закрытого пространства; если он открыт, возможно, что оптимум бесконечен.

Answer 2

Посмотрите на запись wikipedia о линейном программировании. Раздел целочисленного программирования - это то, что вы ищете (ограничение x [i], являющегося целыми числами, нелегко).

Поиск в библиотеках Python ветвей и границ, ветвей и сечений и т. П. (Я не думаю, что они были реализованы в Scipy)

Другие интересные ссылки:

• Комплект линейного программирования GNU
• Статья IBM о GLPK

Answer 3

Похоже, что это линейное программирование проблема.

Answer 4

Возможно, вы захотите использовать Matlab или Mathematica или взглянуть на код из Числовые рецепты в C , чтобы узнать, как реализовать функции минимизации. Предоставленная ссылка на версию книги 1992 года. Более новые версии доступны на Amazon.

Answer 5

Эта компания имеет инструмент для подобных вещей.