Задачка на подумать из практики

[g.Naukovych]

На прошлой работе в компании Manzanagroup у меня была следующая задача.
Мы делали программу лояльности.
Карты, баллы и прочее.

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

Теперь мы хотим потратить баллы, но определенную группу можно списывать только на определенные товары.


пример.
купили сникерс и воду бонаква

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

Теперь представим промышленный вариант, где групп баллов несколько и в чеке много позиций.
Вопрос, как расчитать, сколько максимально можно списать баллов?
Баллы всегда в целых числах и нельзя списать 1,5 балла или 1,10


или еще пример.

У нас есть матрица

NxM

где N кол-во позиций чека, а M группы баллов

если эту группу баллов нельзя использовать для этой позиции чека в матрице стоит 0.

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


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

[Diman]

Классические задачи дискретного программирования
1. упрощенная задача о назначении целей (кол-во переборов уменьшено информацией о том, какие баллы к какой группе товара принадлежат). Решение в лоб: отсортировать товары по группам применимости баллов, сначала тратим спец баллы, потом обычные. Если речь идет об одном чеке.
2. при условии, что числа целые, это задача о ранце. Только добавятся итерации по подбору значений для каждой ячейки. Минус решения перебором большое кол-во итераций, но можно попробовать прикрутить метод приближения непрерывными задачами множителями Лагранжа, чтобы сократить кол-во итераций.
А как решали вы?

[S.Kuskov]

По сути вопроса Diman уже высказался, а я немного позанудствую

Для чего нужна такая система лояльности при которой свою выгоду клиент не может рассчитать самостоятельно до покупки? Мне казалось что размер скидки должен стимулировать клента на покупку, а не быть, возможно приятной, но неожиданностью при подсчете итоговой суммы. Бедные продавцы-консультанты. Так и вижу их с маркером в руках объясняют клиенту как сформировалась итоговая сумма в чеке и рисуют описанную вами матрицу

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

Не лучше ли сложную математику применять не в момент реализации скидки - траты балов, а в момент их (балов) начисления?
Целью разделения балов на группы является стимулирование клиента к покупке в следующий раз того же товара (группы товаров)? Тогда можно оставить единые универсальные балы, но рассчитывать количество начисляемых балов с учетом прошлых покупок клиента. Этакая накопительная система получения балов в разрезе групп товаров.
Если понадобится, то можно ещё ограничить максимальный процент скидки для каждой категории товаров в отдельности. И даже тогда порядок расчета скидки останется более прозрачным.

[Diman]

Цитата:

Сообщение от S.Kuskov

Не лучше ли сложную математику применять не в момент реализации скидки - траты балов, а в момент их (балов) начисления?
Целью разделения балов на группы является стимулирование клиента к покупке в следующий раз того же товара (группы товаров)? Тогда можно оставить единые универсальные балы, но рассчитывать количество начисляемых балов с учетом прошлых покупок клиента. Этакая накопительная система получения балов в разрезе групп товаров.
Если понадобится, то можно ещё ограничить максимальный процент скидки для каждой категории товаров в отдельности. И даже тогда порядок расчета скидки останется более прозрачным.

Видел описание похожей системы, которая пыталась вывести персональное кол-во баллов по конкретному покупателю, чтобы стимулировать на дальнейшие покупки на основе статистики по каждому покупателю. Довольно сложная софтина и модели, которые в ней применялись, внедрялась отдельно поверх ERP

[macklakov]

Разогнать отдел маркетинга к чертям собачим! Смысл баллов в мотивации покупателя. Если понять тяжело, средний покупатель не поймет. А без понимания это превращается в хаотичную раздачу халяв.
Гораздо ценнее собирать историю покупок. Чтобы можно было делать персональные спец. предложения. Но в таком случае баллы являются своеборазной платой клиенту за то, что он пользуется карточкой, т.е. помогает отделу маркетинга собирать о себе информацию.

[g.Naukovych]

Я решал иначе, чего то мне кажется, что рюкзак тут не подойдет. и алгоритм с сортировкой баллов не сработает.
Эти варианты я продумывал.
Еще есть другие варианты решения?
здесь может так случиться, что могут быть доп ограничения какие-нибудь и Вы не сможете представить это в виде матрицы.
Мне лично дали задачу решить матрицу, потом пояснили суть, и мне без матрицы было проще решать.

За каждую покупку товара у Вас есть некие доп. баллы.
И Вы стимулируете человека эти сделать следуюшую покупку, чтобы эти баллы потратить.
Логично, что необходимо сначала тратить те баллы, которые для него уникальны и только ему походят, но что делать если нельзя такие однозначно найти.
3 товара, 3 группы, при этом каждая группа срабатывает на 2 товара и все пары товаров различны.
Здесь не решить жадностью и полный перебор не подойдет из-за скорости.

[S.Kuskov]

Цитата:

Сообщение от g.Naukovych

что делать если нельзя такие однозначно найти.

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

[Diman]

Цитата:

Сообщение от g.Naukovych

Я решал иначе, чего то мне кажется, что рюкзак тут не подойдет. и алгоритм с сортировкой баллов не сработает.
Эти варианты я продумывал.
Еще есть другие варианты решения?
здесь может так случиться, что могут быть доп ограничения какие-нибудь и Вы не сможете представить это в виде матрицы.
Мне лично дали задачу решить матрицу, потом пояснили суть, и мне без матрицы было проще решать.

Почему не подойдет?
Матрица тут вообще не причем. Значения матрицы есть аргументы целевой функции и ограничений. Составляете систему уравнений и вперед.

Цитата:

Сообщение от g.Naukovych

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

Нет разницы, значит они одинаковые и можно выбирать любой.
Про жадность речи не было. Про экономию времени курить множители Лагранжа, как и предлагал.
Решение в лоб было на тех условиях, которые вы представили. Общее решение - задача о выборе целей.
Конечно, вышепредложенные задачи общие и к ним придется прикрутить ваши ограничения.
Можете попробовать на любом мат пакете либо Excel + Solver

Интересно все таки увидеть ваше решение. Хотя бы в общем виде. Потому что вопрос "Как решать?", ни разу не вопрос. Хочется от вас увидеть ответ на вопрос "Что решать?"

[Raven Melancholic]

Посмотрел клиентов Manzana Group. Из знакомых только Кораблик, Киа, Тойота и Лукойл.
Жаль что нет кого-то к кому можно было бы завтра зайти и и попросить рассчитать бонусы при помощи:

Цитата:

баланс баллов, который разбит на сегменты

Цитата:

задача о назначении целей

Цитата:

решить матрицу

Цитата:

Составляете систему уравнений и вперед

Кстати, когда я учился в институте (более 20 лет назад), в нашем ВУЗе при решении оптимизационных задач приняты были подходы не на основ матриц (созданных на целевой функции и ограничениях), а на основе преобразований Лапласа, решения задачи в комплексной области и преобразовании ответа назад в область реальных чисел.
Есть большое желание подойти к консультанту в торговом зале и попросить его решить задачу при помощи перехода в область комплексных переменных.

[Diman]

Цитата:

Сообщение от Raven Melancholic

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

Имеете ввиду дискретное преобразование Z/D? Так в чем же дело, предлагайте функцию и может быть такое решение устроит ТС.

Цитата:

Сообщение от Raven Melancholic

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

Попробуйте, расскажете

[Serge Kotov]

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

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

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

Правило номер один (для маркетолога) может звучать так: "Точность прогнозирования реакции покупателя обратно пропорциональна степени сложности схемы расчета баллов "программы лояльности."

[g.Naukovych]

Я решил эту задачу алгоритмом поиска максимального потока.

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

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

[S.Kuskov]

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

[Diman]

Цитата:

Сообщение от g.Naukovych

Я решил эту задачу алгоритмом поиска максимального потока.
.

Тоже вариант.