Какой алгоритм оптимизации следует использовать для максимизации прибыли с временными ограничениями?

Question

Я бы хотел найти подходящий алгоритм для решения этой проблемы:

Предположим, у нас есть N проектов, и мы знаем, сколько денег мы заработаем на каждом проекте и сколько времени потребуется для выполнения каждого проекта (расчетное время для каждого проекта). У нас есть определенное количество свободного времени для выполнения всех проектов. Мы хотим выбирать проекты таким образом, чтобы наша прибыль была максимальной, а общее расчетное время не превышало доступное время. Подскажите, пожалуйста, какой алгоритм оптимизации следует использовать? Есть ли уже готовые вещи, которые я мог бы использовать в C #, технологии .NET или Java?

Answer 1

Это звучит просто: Проблема с рюкзаком :

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

В вашем случае, вес - это время, необходимое для проектов, и пределэто ограничение по времени.

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

В случае теоретического интереса, задача о рюкзаке является NP-трудной и активной областью алгоритма.

Answer 2

То, что вы ищете, называется проблемой с рюкзаком .

, в вашем случае пределом «веса» является ограничение по времени, а значением является значение.

Answer 3

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

После того, как вы определились с вашей формулировкой, для решения проблемы имеется пара решений на c #MIP.У Microsoft есть Microsoft Solver Foundation, который вы можете изучить, который способен решать простые MIP, и который имеет приятный C # API

. IBM недавно приобрела пакет оптимизации OPL (считается ведущим в отрасли), который вы можете использовать для разработки своегоMIP формулировка.Как только у вас есть формулировка, OPL предлагает .NET API, которые вы можете вызвать для запуска ваших моделей.

Пройдя сам путь OPL, я бы по возможности избегал использования OPL .NET API, потому что они очень громоздки.Если ваша проблема проста, возможно, вы захотите взглянуть на основу решения, потому что она предлагает современный и чистый API по сравнению с OPL

Answer 4

Упрощенно, это выглядит как взвешенный http://en.wikipedia.org/wiki/Knapsack_problem. Ваше время будет размером проекта, а ваш вес будет ваши расходы