Постановка задачи:
Есть n альтернатив (X1, X2, ... ,Xn) — ну например проекты, на которые планируется потратить бюджет организации.
Каждая альтернатива имеет свою стоимость — c (cost) и вес (приоритет, прибыльность) — b (benefit).
Есть бюджет — Sum — который и пойдет на финансирование этих альтернатив. Но он как правило меньше суммарной стоимости всех альтернатив. Отсюда и задача:

c1X1 + c2X2 + ... + ciXi + ... + cnXn <= Sum
b1X1 + b2X2 + ... + biXi + ... + bnXn -> Max
Xi = 0 или Xi = 1

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

1. Xi — обязательно должна быть профинансирована.
2. Xi, Xj, ... , Xk — обязательно должны быть профинансированы.
3. Xm — обязательно должна быть НЕ профинансирована.
4. Xm, Xs, ... , Xf — обязательно должны быть НЕ профинансированы.
5. Скажем 2 и 4 сразу.

6. И условия группирования альтернатив — скажем объединяем альтернативы Xm, Xs, ... , Xf в группу и говорим, что только одна из альтернатив этой группы должна быть профинансирована.

Как решить? Можт кто подскажет?

M>Как решить? Можт кто подскажет?

Напиши программку которая будет справляться. Это легче чем написать комбинаторную формулу в общем виде. И считать быстро будет < 1 сек. Если конечно I не ~ 10e9. С таким кол-вом инициатив можно губозакатыватель покупать. Если хощ сам настругаю такую программку за ~1500руб.

Здравствуйте, Mikola, Вы писали:

M>Но нужно предусмотреть такие ограничения еще:

M>1. Xi — обязательно должна быть профинансирована.
M>2. Xi, Xj, ... , Xk — обязательно должны быть профинансированы.
M>3. Xm — обязательно должна быть НЕ профинансирована.
M>4. Xm, Xs, ... , Xf — обязательно должны быть НЕ профинансированы.
M>5. Скажем 2 и 4 сразу.

А в чем проблема? Полагаете Xi, Xj, ..., Xk равными 1, Xm,..., Xf равными 0, получаете задачу с меньшим количеством переменных:

d1Y1 + d2X2 + ... + dmYm <= Sum' (= Sum — ciXi — ... ckXk)
a1Y1 + a2Y2 + ... + amYm -> Max
Yi из {0,1}

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

M>6. И условия группирования альтернатив — скажем объединяем альтернативы Xm, Xs, ... , Xf в группу и говорим, что только одна из альтернатив этой группы должна быть профинансирована.

Добавляем еще условие

Xm + Xs + ... + Xf <= 1 (или =1, если ровно одна альтернатива должна быть профинансирована обязательно)

M>А в чем проблема? Полагаете Xi, Xj, ..., Xk равными 1, Xm,..., Xf равными 0, получаете задачу с меньшим количеством переменных:

M>d1Y1 + d2X2 + ... + dmYm <= Sum' (= Sum — ciXi — ... ckXk)
M>a1Y1 + a2Y2 + ... + amYm -> Max
M>Yi из {0,1}

M>Т.е. просто уменьшится размерность задачи, решать станет легче.

M>>6. И условия группирования альтернатив — скажем объединяем альтернативы Xm, Xs, ... , Xf в группу и говорим, что только одна из альтернатив этой группы должна быть профинансирована.

M>Добавляем еще условие

M>Xm + Xs + ... + Xf <= 1 (или =1, если ровно одна альтернатива должна быть профинансирована обязательно)

Только подскажите пожалуйста — каким методом эту задачу лучше решать. Я сначала думал комбинаторикой или полным перебором (Я так понял, что это задача о рюкзаке, с некоторыми наворотами), но при каждом увеличении альтернатив время работы алгоритма при этом возрастает в разы.
Потом еще прочитал, что такую задачу решают методами динамического программирования — при этом количество альтернатив может быть достаточно большим. Не подскажите, какие материалы (книги) стоит почитать для решения такой задачи. Вот собираюсь идти в библиотеку. А можт есть уже готовые компоненты или библиотеки для решения подобных задач. Если что, то я пишу эту прогу на Object Pascal (Delphi6)

Здравствуйте, Mikola, Вы писали:

M> Только подскажите пожалуйста — каким методом эту задачу лучше решать. Я сначала думал комбинаторикой или полным перебором (Я так понял, что это задача о рюкзаке, с некоторыми наворотами), но при каждом увеличении альтернатив время работы алгоритма при этом возрастает в разы.
M> Потом еще прочитал, что такую задачу решают методами динамического программирования — при этом количество альтернатив может быть достаточно большим. Не подскажите, какие материалы (книги) стоит почитать для решения такой задачи. Вот собираюсь идти в библиотеку. А можт есть уже готовые компоненты или библиотеки для решения подобных задач. Если что, то я пишу эту прогу на Object Pascal (Delphi6)

Вообще это выглядит как типичная задача целочисленного (линейного) программирования. Задача NP-трудная (как и задача о рюкзаке), решать можно разными способами, в т.ч. и динамическим программированием. Поищите в Яндексе по "целочисленное программирование". Например: http://www.karelia.ru/psu/Faculties/Forest/courses/decision/chap4_a.htm

По "бумажным" книгам подсказать не могу — их очень много, лучше посмотрите на месте по теме "целочисленное программирование".

Насчет готовых компонент, к сожалению, не знаю.