Я работаю над проблемой программирования, которая сводится к набору уравнения и неравенства:
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]
ограничены набором неотрицательных целых чисел.
Да, это так. Спасибо за уточняющий вопрос.
Хм, тогда я бы тоже придерживался линейного программирования ...
ЦЕЛОЕ! Тогда это задача целочисленного программирования (намного сложнее), ветвь и граница и все подобное подойдет.
PS - Я не думаю (надеюсь), что вы найдете здесь людей, дающих вам исчерпывающий ответ. Для этого это слишком уж проблема из учебника ...;)
@Barry: Я не искал полного ответа, нет. Просто указатели на то, какая работа была проделана в этом районе.
На первый взгляд кажется, что у этой проблемы есть несколько решений. Можете ли вы дать некоторые реальные данные для ознакомления?
Похоже, это проблема линейное программирование.
Это похоже на проблему линейное программирование. Симплексный алгоритм обычно дает хорошие результаты. По сути, он обходит границы подпространства, ограниченного неравенствами, в поисках оптимума.
Подумайте об этом визуально: каждое неравенство обозначает полупространство, плоскость в n-мерном пространстве, от которой вы должны находиться справа. Ваша функция полезности - это то, что вы пытаетесь оптимизировать. Если пространство закрытое, оптимум будет на одной из вершин закрытого пространства; если он открыт, возможно, что оптимум бесконечен.
Возможно, вы захотите использовать Matlab или Mathematica или посмотрите код из Числовые рецепты на C для идей о том, как реализовать функции минимизации. Приведенная ссылка ведет на версию книги 1992 года. Более новые версии доступны на Amazon.
У этого Компания есть инструмент для подобных вещей.
Взгляните на запись википедия о линейном программировании. Раздел целочисленного программирования - это то, что вы ищете (ограничение x [i] целыми числами не из легких).
Найдите библиотеки python для ветвей и привязок, веток и вырезок и тому подобного (я не думаю, что они еще были реализованы в scipy).
Другие интересные ссылки:
Должно ли x [0] ... x [n] быть больше или равно нулю?