Распределение суммы по статьям затрат

[_Ivana]

Это очень легкая задачка, но имхо забавная, не олимпиадная, хотя для школьников средних классов может пойдет Я с ней столкнулся только что по работе (с работы и пишу этот пост ), решая более общую задачу написания блока автоматического планирования/исполнения затрат в одной коммерческой фирме.
Есть сумма $S$, которую мы можем себе позволить потратить на затраты. Есть статьи затрат, у каждой из которых определен показатель - процент от общей суммы, который мы можем отдать на эту статью. Есть набор заявок на затраты от руководителей подразделений, каждая заявка содержит свою требуемую сумму и статью затраты. Каждая заявка имеет уникальный приоритет ее исполнения. В рамках каждой статьи затрат допускается количество частично удовлетворенных заявок в вариантах (в зависимости от заранее выбранной установки):
а) одна
б) ноль
Написать и реализовать алгоритм, наиболее оптимально (хоть в каком-то смысле ) распределяющий имеющуюся сумму $S$ по статьям затрат с детализацией до каждой заявки.

ЗЫ если надо, могу нарисовать тестовые данные в цифрах, для сравнения ответов.

[zer0]

Если задача не олимпиадная, то зачем ее засовывать в раздел олимпиадных задач?

[_Ivana]

Как известно, олимпиада только что закончилась, и вроде как новые задачи уже не к месту. Но скоро начнется паралимпиада, и там тоже будет своя программа. Вот эта задача как раз для паралимпиады по программированию, так что она в своем разделе

[rockclimber]

_Ivana в сообщении #830761 писал(а):

Это очень легкая задачка, но имхо забавная, не олимпиадная, хотя для школьников средних классов может пойдет

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

[_Ivana]

А в этом часть задачи - понять что в итоге должно получиться. Хотя, можно это сказать одной фразой - принять решение, кому сколько денег дать (при любых входящих условиях). А вторая часть - придумать и реализовать алгоритм. Но если не хотите подумать над первой частью, вечером выложу пример исходных данных и мой вариант результата для них.

[whitefox]

1. Распределяем сумму $S$ по всем статьям в соответствии с заданным для каждой статьи процентом.
2. Для каждой стать удовлетворяем заявки в соответствии с их приоритетом пока, либо не закончатся выделенные средства, либо не опустеет очередь заявок.
3. Если для некоторых статей останутся неизрасходованные средства, то аккумулируем их в "резервный фонд".
4. Средствами из "резервного фонда" удовлетворяем заявку принадлежащую статье с максимальной общей суммой неудовлетворённых заявок (ибо нужда в этой статье больше чем в других). Если таких статей несколько, то из всех заявок, принадлежащих этим статьям, удовлетворяем заявку с максимальным приоритетом (такая заявка будет единственной так как приоритеты уникальны).
5. Если "резервный фонд" ещё не исчерпан, то возвращаемся на шаг 4.

[_Ivana]

whitefox, насколько я понял, вы разделяете варианты а) и б) в вашем пункте 2 - если на очередную заявку не хватает остатка средств, распределенных по процентам, то мы в варианте а) оставляем эту заявку частично погашенной, а в варианте б) всю эту сумму выделяем в резервный фонд? Осталось непонятным, как вы реализуете вариант б) в пункте 4 - если на очередную заявку по приоритету суммы не хватает, а допустим хватает на другие, да еще есть варианты?
А так навскидку алгоритм имеет право на жизнь, хотя я не согласен с пунктом 4 и всем что после него. Я предложу другой вариант, имхо более оптимальный. Начнем с простого - распределение в варианте а):
получаем сводную таблицу затребованных сумм по статьям затрат, сумму к распределению считаем равной сумме $S$ В цикле пока сумма к распределению больше $0$ делаем:
1. пробегаем по этой таблице, пропускаем те статьи, по которым выделенная сумма равна затребованной, по остальным строкам считаем суммарный (накопительный) процент статей. Если этот итоговый процент равен 0 (нет непогашенных статей) - выход из внешнего цикла.
2. второй раз пробегаем по этой таблице, также пропускаем те статьи, по которым выделенная сумма равна затребованной, по остальным строкам увеличиваем выделенную сумму на сумму к распределению, умноженную на коэффициент = процент текущей статьи/накопительный процент непогашенных статей (рассчитанный в п 1.). Если при этом выделенная сумма превышает затребованную, то приравниваем выделенную на статью сумму затребованной, а излишек накапливаем в "резервный фонд".
3. сумму к распределению приравниваем "резервному фонду" и идем на шаг 1 в начало цикла.

То есть в отличие от вашего предложения, мы каждый раз распределяем получающийся резервный фонд по назначенным процентам оставшихся непогашенных статей - имхо это справедливее. Этот нехитрый алгоритм распределяет сумму $S$ по статьям затрат. А далее внутри каждой статьи распределяем сумму (распределенную на статью) по заявкам в порядке приоритета, последняя заявка каждой статьи будет в общем случае частично погашена (если статья погашена не полностью). Пункт а) закончен.

Теперь остается пункт б) - имхо, тут тоже есть над чем подумать.

-- 06.03.2014, 21:41 --

Вот этот принцип:

whitefox в сообщении #833477 писал(а):

Средствами из "резервного фонда" удовлетворяем заявку принадлежащую статье с максимальной общей суммой неудовлетворённых заявок (ибо нужда в этой статье больше чем в других).

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

[whitefox]

_Ivana в сообщении #833521 писал(а):

насколько я понял, вы разделяете варианты а) и б) в вашем пункте 2 - если на очередную заявку не хватает остатка средств, распределенных по процентам, то мы в варианте а) оставляем эту заявку частично погашенной, а в варианте б) всю эту сумму выделяем в резервный фонд?

Да.

_Ivana в сообщении #833521 писал(а):

Осталось непонятным, как вы реализуете вариант б) в пункте 4 - если на очередную заявку по приоритету суммы не хватает, а допустим хватает на другие

В этом случае удовлетворим подходящую заявку с наибольшим приоритетом и перейдём к шагу 5. На котором сравним "резервный фонд" с минимальной суммой ещё не удовлетворённой заявки. Если "резервный фонд" больше или равен минимальной сумме, то вернёмся на шаг 4.

_Ivana в сообщении #833521 писал(а):

Вот этот принцип:

whitefox в сообщении #833477 писал(а):

Средствами из "резервного фонда" удовлетворяем заявку принадлежащую статье с максимальной общей суммой неудовлетворённых заявок (ибо нужда в этой статье больше чем в других).

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

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

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

_Ivana в сообщении #833521 писал(а):

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

Но сами эти проценты взяты ведь не с потолка. Они отражают ожидания степени важности той или иной статьи затрат. Редко когда реальность совпадает с ожиданием. Имхо, справедливее динамически подкорректировать эти проценты, что и происходит в предложенном методе.

[_Ivana]

Оказывается есть что обсудить в этой задачке, несмотря на скепсис первого взгляда.
whitefox, если брать за основу ваши идеи, тогда надо вообще сразу скорректировать проценты с учетом затребованных сумм по каждой статье и распределять уже по этим скорректированным процентам. Система будет "гибко подстраиваться под нужды момента", читай - "отрабатывать не установку руководителя, а жадность просящих". Почему вы вспоминаете про приоритет и величину неудовлетворенности статьи только для "резервного фонда", может сразу для стартовой суммы тогда, будет логичнее? Это уже третий алгоритм распределения получается. Вот такая неоднозначная задачка.
А если следовать логике - начальник назначает приоритет и подтверждает обоснованность заявки - тогда можно вообще забыть про проценты статей и распределять всю сумму в порядке приоритета заявок. Но такой подход еще менее красив,чем предложенные 3.
В моей системе статья, которой хватило меньше, чем назначено процентом, "отдает" излишек на другие статьи, и с этого момента можно рассматривать эту ситуацию как стартовую задачу - есть сумма (излишка), надо распределить по непогашенным статьям. И красиво, если мы при этом распределении придерживаемся того же алгоритма, что и для стартовой суммы.

[master]

whitefox в сообщении #833477 писал(а):

Средствами из "резервного фонда" удовлетворяем заявку принадлежащую статье с максимальной общей суммой неудовлетворённых заявок

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

_Ivana в сообщении #830761 писал(а):

Каждая заявка имеет уникальный приоритет ее исполнения.

В реальности даже заявки из одной статьи могут иметь одинаковый приоритет.
Надо плавающие процент на статью.

[whitefox]

_Ivana
Согласен с Вами, что вариантов решения можно придумать великое множество. И все они будут правильными, ибо не указана функция значение которой нужно оптимизировать. А понятие красоты субъективно (имхо, мой покрасивше будет ).
По этому спор о том чей алгоритм лучше — беспредметен.

_Ivana в сообщении #833576 писал(а):

"отрабатывать не установку руководителя, а жадность просящих"

Давайте, всё же, считать все заявки обоснованными. Кстати, Ваш метод при необоснованных заявках тоже даст искажённый оптимум.

master

master в сообщении #833645 писал(а):

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

Вы не учитываете, что задача паралимпийская

В реальности вариант б) абсолютно не применим, и вариант а) не намного лучше.

В самом деле, какой смысл удовлетворить заявку на кирпич полностью, а на раствор отклонить? Стройка-то остановится.

Не многим лучше вариант: удовлетворить заявку на кирпич на 10%, а заявку на раствор на 100%. Большая часть средств будет выброшена на ветер (90% раствора застынет).

[_Ivana]

master в сообщении #833645 писал(а):

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

Да, это правда. Но я сознательно упростил задачу для большей легкости и понятности.

whitefox в сообщении #833697 писал(а):

В реальности вариант б) абсолютно не применим, и вариант а) не намного лучше.

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

ЗЫ насчет учета обоснованности заявок - придумал имхо неплохое решение (напоминает альфа-бета фильтр или Калмана). Получаем таблицу затребованных сумм по статьям, и удовлетворяем их по каким-то процентам, получающиеся резервные фонды распределяем тоже по ним. А для расчета этих каких-то процентов вводим (и даем руководителю менять) коэффициент $K$ - если он равен нулю, то проценты берутся назначенные для статей, если единице - то игнорируются проценты статей, а берутся относительные доли затребованных сумм. При промежуточных значения коэффициента считаются средние значения процентов между указанными в статьях и долями затребованных сумм - надо придумать математику их получения, она должна быть несложная. Таким образом, коэффициент $K$ будет определять степень учета долей затребованных сумм при распределении суммы затрат, точнее баланс между заложенными процентами и получившимися по затребованным суммам.

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

[whitefox]

_Ivana в сообщении #833758 писал(а):

если вас смущают мои варианты а) и б), то можно реализовать третий вариант с)

А где варианты в) г) д) . . . о) п) р) ?

[_Ivana]

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