Оптимизационная задача - делим пирог

[квит]

Для желающих отдохнуть от гуманитарной составляющей форума - поразмять мозги.

Прилетела недавно задача - ее постановка:

Есть N предприятий.

Каждое из них может проводить ряд мероприятий, с затратами на них по i-му предприятию R(i) - расход, и ожидаемым экономическим эффектом D(i) - доход.

Суммарные затраты составляют SR=R(1)+R(2)+...+R(N), и равны, допустим, 2 млн. тугриков

Есть центр, который выделяет финансирование, и который говорит, хрен вам, ребята, на все выделяю 1 млн. тугриков.

Задача - как распределить выделенное финансирование между предприятиями, чтобы максимизировать суммарный доход?

Формальная постановка.
SD -> max
SR <= const

SD=D(1)+D(2)+...
SR=R(1)+R(2)+...

[квит]

Мат. модель

Если ввести переменную х(i) - "выделяем бапки i-му предприятию", ее значения
0 - не даем,
1 - даем.

тогда задача сводится к задаче целочисленного линейного программирования на N-мерном кубе

R'*X -> max
D'*X <= const



Спешл фор рассудок - [0,1]^N - N-кратное декартово произведение множества {0,1}

[Zab]

Как влияет на отдачу недофинансирование?
Возможный сценарий:
- при 10% недофинансинровании результат не меняется (финансирование было избыточным),
- при 20% недрфинансировании результат уменьшается вдвое, да еще и сроки непредсказуемо передвигаются,
- при 40% недофинансировании результата не будет вообще, вместо продукта получим отчет о ходе работ, и только,
- при 70% недофинансировании не получим даже отчета, деньги возьмут, да еще и обругают, работать никто даже пытаться не будет.

[квит]

Сначала самое простое - конкретному предприятию либо есть, либо нету.

Т.е если фонд уменьшили в два раза, это значит, кто то получит 100%, а кто то 0%

[Afa]

квит, поправь. эт вроде на задачу коммивояжера похоже. можно посмотреть на эмпирики от нее.

[Afa]

квит, а тестовая задачка - сколько предприятий? я прикинуть ресурсоемкость хочу

[квит]

В одной структуре порядка 200

В другой 4000

Полный перебор - 2 в степени N вариантов

[Тома]

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

Зачем такой огород городить с н мерными кубами?
Или я чего то не догоняю?

э

т вроде на задачу коммивояжера похоже.

Предприятия между собой не связаны никак. Графы вроде не причем.....

[квит]

Тома, я ж рассудку эту задачу подсовывал, а ты ответ подсказала... )))

Я так и делаю, только вместо показателя д/р использую нпв = д - р дисконтированные

[Afa]

Сообщение от квит

В одной структуре порядка 200

В другой 4000

Полный перебор - 2 в степени N вариантов

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