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

[квит]

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

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

Есть 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к элементов.
террабайтник на временную таблицу под декартово. ну нормально чо. решить можно за обозримое время - но стоит таки брать более оптимальные алгоритмы

[Afa]

Сообщение от Тома

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

неоптимальное заполнение. а неизрасходованный бюджет урезают. оно надо?
больше скажу. самый прибыльный - вполне может вылететь из конкурса. а выиграет десяток менее прибыльных - но выбравших весь бюджет.

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

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

я лишь про оптимизации. и откидывание непроходящих вариантов. в коммивояжере были пакости^Wрасширения.

[квит]

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

Ограничения кроме всего фонда могут еще быть по группам

[Afa]

та непринципиально. добавка вычислимых параметров по одному для ограничения. выбор кста упростится.

[Тома]

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

такой параметр может не дать оптимальный в смысле максимальной отдачи результат кстати.
Большое малоприбыльное предприятие будет приоритетней малого высокоприбыльного.

[Samirat]

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

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

Я бы применила ABCD-анализ и далее распределение ресурсов (выделенное финансирование) по формуле: 17=10+4+2+1 по группам предприятий.

[квит]

Договорились с клиентом, что делаем возможность выбора показателя оптимизации

По д-р
По д/р
По сроку окупаемости

Сюда же можно и вас анализ включить

[квит]

Договорились с клиентом, что делаем возможность выбора показателя оптимизации

По д-р
По д/р
По сроку окупаемости

Сюда же можно и вас анализ включить

[Samirat]

а что такое вас анализ?

[квит]

Это у меня режим т9 включен

Авс анализ

[Samirat]

понятно))

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

[квит]

Приятно, что эта модель тиражируема

Венчурный фонд и инвест проекты
Корпорация и дочки
ГРБС и БУ
Портфельный инвестор и бумаги

[квит]

Сообщение от Тома

такой параметр может не дать оптимальный в смысле максимальной отдачи результат кстати.
Большое малоприбыльное предприятие будет приоритетней малого высокоприбыльного.

надо делать сразу по двум показателям (д-р и д/р) и выбирать попавшие в парето-оптимальное множество...