Доброе время суток.
Есть реальная задача, которую я не могу свести к какой-то конкретной математической.
Задача состоит в определении оптимального тарифного плана у сотового оператора(ов).
Входные данные (для упрощения): кол-во исходящих минут, входящих минут, смс, данных, и т.д.
Тарифный план: набор услуг со своими ценами, возможно с ограничениями.
Если выбирать только из тарифных планов, то задача нетрудная: можно представить каждый план как функцию от входных параметров (кусочно-непрерывную), вычислять ее значение для данного набора входных данных и дальше выбирать минимальную (либо просто линейное программирование).
Но есть такое понятие как пакеты. Это наборы типа 1000 смс за ХХ денег, либо 500 смс за YY денег, либо 100 смс + 100 минут и т.д. В общем случае — комбинация услуг за фиксированную плату. Пакеты эти доступны для определенных планов (в общем случае — для всех, но могут быть ограничения). Практически всегда пакет выгоднее просто тарифа в плане, но имеет ограничение по объему, после которого включается сам план. (Для упрощения можно считать, что пакет можно выбрать только раз в месяц, все планы месячные).
Т.о. задача по сути превращается в комбинаторную — найти оптимальную комбинацию "пакеты (как правило несколько) + тарифный план", которая даст минимальную общую стоимость при заданном наборе входных данных.
Задача может быть решена прямым перебором, но мне кажется должны существовать методы либо для решения не комбинаторного, либо для сокращения кол-ва вариантов перебора (например, после сортировки стоимостей пакетов можно отбрасывать дорогие пакеты и т.д.).
Подскажите, пожалуйста, в какую сторону копать?
> Задача может быть решена прямым перебором, но мне кажется должны существовать методы либо для решения не комбинаторного, либо для сокращения кол-ва вариантов перебора (например, после сортировки стоимостей пакетов можно отбрасывать дорогие пакеты и т.д.). > Подскажите, пожалуйста, в какую сторону копать?
Есть тарифные планы с N кол-вом бесплатных минут в день. Если не
израсходовал, то они сгорают. Вообще, опсосы специально вносят сложность
в определение реальной стоимости их услуг.
Я думаю будет слишком сложно найти аналитическое решение данной задачи,
точнее его придется искать снова и снова каждый раз при смене тарифных
планов, доп. услуг и всяческих акций.
Победить эту проблему можно только двумя путями (на мой взгляд).
Первый подход — определить исходные данные как можно более детально, на
математическом языке (например в виде графов, матриц, векторов). Затем
закинуть эти данные на растерзание какому-нибудь математическому пакету
(я бы рассматривал mathematica от wolfram research). А вот все
вычисления, которые будут проводиться этим пакетом над данными
определять на "языке" этого математического пакета, и при этом сами
вычисления будут производными от тарифных планов операторов. Разумеется
каждый раз при смене тарифных планов придется переписывать алгоритм
вычисления (тот, что задан на "языке" мат. пакета).
Второй подход — запустить "эмулятор биллинга" и скоримить ему
вымышленные звонки во всех комбинациях тарифных планов, доп. услуг и
каких-нибудь бонусов. Фактически перебор. При этом "эмулятор биллинга"
придется писать самому, и дописывать его по мере изменения условий у
опсосов.
Оба подхода требуют много затрат на разработку, и мало затрат на
вычисление. При этом первый подход требует более высокой квалификации
разработчика (точнее математика), но и находить решения он будет за
несколько секунд. Второй подход может осилить средний программист, но
вычисления могут занимать несколько дней.
И в том и в другом случае придется подбирать несколько типовых историй
звонков например за месяц.
А, вот еще что. Во втором подходе можно отсортировать комбинации
например по стоимости, и тогда с большой вероятностью самые выгодные
условия будут просчитаны в начале работы алгоритма. Т.е. можно запустить
тотальный пересчет, но приделать возможность отображать промежуточный
вариант. Н-р:
просчитано 12%
результаты:
— немногословный — "план А" + "10 SMS"
— студент — "план А" + "100 SMS" + "интернет"
— тусовщик — "план Б"
— планктон — "план С" + "10 минут в день за 10 рублей"
— комивояжер — "план А" + "безлимитные местные"
Через некоторое время алгоритм дойдет до дорогих планов и может поменять
что-нибудь (например — комивояжеру может оказаться выгоднее какой-нибудь
безлимитный тариф)
Здравствуйте, Other Sam, Вы писали:
OS>Вообще, опсосы специально вносят сложность OS>в определение реальной стоимости их услуг.
Это уж точно ....
OS>Я думаю будет слишком сложно найти аналитическое решение данной задачи, OS>точнее его придется искать снова и снова каждый раз при смене тарифных OS>планов, доп. услуг и всяческих акций.
Да правильно. Обновлять информацию по планам придется постоянно.
Я может не совсем точно описал задачу, но задача состоит не в нахождении лучшего плана вообще
(такой вряд ли будет), а нахождение лучшего при заданном уровне расходов услуг.
Т.е. представляя каждый план в виде кусочно-непрерывной функции, я могу вычислить его стоимость для заданных входных данных (уровня потребления), а потом отобрать минимальный.
Но такой план может быть не оптимальным, если попытаться учесть пакеты, а вариантов план+пакеты будет очень много.
Вот такая комбинаторная задача и представляет для меня основную трудность. Надеялся, что кто-то сможет ее описать математически...
OS>Разумеется OS>каждый раз при смене тарифных планов придется переписывать алгоритм OS>вычисления (тот, что задан на "языке" мат. пакета).
Вот этого и не хочется, хотелось описать алгоритм один раз и получать результат независимо от изменения планов. Для этого, конечно, нужно учесть в алгоритме все возможные варианты тарификации планов и пакетов, для чего сначала спроектировать адекватную модель данных для хранения плана.
OS>Второй подход — запустить "эмулятор биллинга" и скоримить ему OS>вымышленные звонки во всех комбинациях тарифных планов, доп. услуг и OS>каких-нибудь бонусов. Фактически перебор. При этом "эмулятор биллинга" OS>придется писать самому, и дописывать его по мере изменения условий у OS>опсосов.
Скорее всего будет комбинация двух подходов (через биллинг получаем стоимость плана, а дальше аналитически подбираем пакеты к нему для удешевления).
Напрашивается алгоритм оптимизации типа спуска по координатам или метод ветвей и границ, но пока что я в этом плаваю...
Была также мысль сделать нейронную сеть (вход — уровень потребления услуг, выход — тарифный план), но это будет примерное решение, а я думаю, что реально получить точное...
... > Да правильно. Обновлять информацию по планам придется постоянно. > Я может не совсем точно описал задачу, но задача состоит не в нахождении лучшего плана вообще > (такой вряд ли будет), а нахождение лучшего при заданном уровне расходов услуг. > Т.е. представляя каждый план в виде кусочно-непрерывной функции, я могу вычислить его стоимость для заданных входных данных (уровня потребления), а потом отобрать минимальный. > Но такой план может быть не оптимальным, если попытаться учесть пакеты, а вариантов план+пакеты будет очень много. > Вот такая комбинаторная задача и представляет для меня основную трудность. Надеялся, что кто-то сможет ее описать математически...
... > Напрашивается алгоритм оптимизации типа спуска по координатам или метод ветвей и границ, но пока что я в этом плаваю... > > Была также мысль сделать нейронную сеть (вход — уровень потребления услуг, выход — тарифный план), но это будет примерное решение, а я думаю, что реально получить точное...
Можно исходить из предположений общего плана. Например программисты у
обсосов такие же как мы. Поэтому они как-то будут описывать планы,
скорее всего функциями от каких-то исходных данных. Значит и мы можем
описать примерно так же (только тогда это будет не аналитическим
решением, а перебором, но и такое решение вполне подходит).
Я бы просто забил. Дешевле если пару сотен абонентов будут пользоваться
неоптимальными планами, чем платить мне зарплату. Если кто-то готов
платить мне зарплату в этих условиях, значит он может платить и за
что-нибудь другое, более интересное.
И еще, выбор оптимального плана — это искуственная задача, ее придумали
опсосы ради денег (точнее ради обмана). Нужно просто забить на таких
обсосов и перейти к другим. Когда им станет нечего есть, они перестанут
создавать искуственные сложности.
Перед человечеством стоят более важные задачи. Солнце через несколько
миллионов лет взорвется, а человечество либо сможет свалить из солнечной
системы, либо изчезнет.
Им, и только им, такие задачи и следует решать. Причина простая: единомоментно у оператора действует не более 30 тарифов, и к каждому предлагается не более 30 пакетов. Ну что такое 900 тестов для современной техники
Здравствуйте, SkyDance, Вы писали:
A>>Задача может быть решена прямым перебором SD>Им, и только им, такие задачи и следует решать. Причина простая: единомоментно у оператора действует не более 30 тарифов, и к каждому предлагается не более 30 пакетов. Ну что такое 900 тестов для современной техники
В принципе да, для одного раза можно и самом посчитать, но у такого решения нет масштабируемости.
Например, возьмем не одного оператора а несколько (10, 20...), планов суммарно может быть около 1000, пакетов — 1000-100000.
Итого имеем порядка нескольких миллионов комбинаций. Такое будет считаться ощутимое время... Нужна какая-то оптимизация.
Здравствуйте, alextop, Вы писали:
A>Задача состоит в определении оптимального тарифного плана у сотового оператора(ов). A>Входные данные (для упрощения): кол-во исходящих минут, входящих минут, смс, данных, и т.д. A>Тарифный план: набор услуг со своими ценами, возможно с ограничениями.
не очень понятна задача? — найти оптимального оператора и оптимальный план для сферического абонента в вакууме?
Абонент у нас всегда конкретный, со своей статистикой звонков. Так что нам надо всего-навсего формализовать все параметры, заложенные оператором в тарифный план и удобно для пользователя ввести его данные (ввод средних значений, импорт из pdf, htmp и т.п.)
Дальше программа выдаст сводную таблицу планов всех операторов со значением затрат, отсортировав по убыванию месячного платежа.
Этого вполне достаточно. Полезна бы была еще возможность поиграться с параметрами.
Но таких программ воз и маленькая тележка, начиная от калькуляторов на сайте оператора и заканчивая поделками таких же энтузиастов.
A>В принципе да, для одного раза можно и самом посчитать, но у такого решения нет масштабируемости.
Оно обычно и не требуется.
A>Например, возьмем не одного оператора а несколько (10, 20...), планов суммарно может быть около 1000, пакетов — 1000-100000.
Я с трудом себе представляю больше 5 операторов, присутствующих в одном регионе. Ну даже если пусть и так, что такое миллион комбинаций для современных CPU? Раз плюнуть и растереть.
Но даже если и так, то время, потребующееся на банальный ввод бизнес-правил (тех самых тарифных планов, пакетов и т.п.) займет заведомо больше, чем расчет.
Тем более что расчет фантастически легко параллелится на любое количество вычислительных нитей. Возьмите Core2 Quad с гипертредингом — там можно будет считать за доли секунды.
Спасибо за ответ.
A>>Задача состоит в определении оптимального тарифного плана у сотового оператора(ов). A>>Входные данные (для упрощения): кол-во исходящих минут, входящих минут, смс, данных, и т.д. A>>Тарифный план: набор услуг со своими ценами, возможно с ограничениями.
J>не очень понятна задача? — найти оптимального оператора и оптимальный план для сферического абонента в вакууме?
В общем, все правильно, задача ставится именно так. Только абонент не сферический, а вполне конкретный, я описал его в качестве входных данных.
J>Абонент у нас всегда конкретный, со своей статистикой звонков. Так что нам надо всего-навсего формализовать все параметры, заложенные оператором в тарифный план и удобно для пользователя ввести его данные (ввод средних значений, импорт из pdf, htmp и т.п.)
Как "всего-навсего" формализовать и является частью вопроса (при обилии вариантов ценообразования). Калькуляторы есть но я не видел ни одного, который учитывает пакеты услуг изначально. Без них задача тривиальна и решение, в общем-то, бесполезное.
Т.е. как подсчитать, что выгоднее при данном уровне потребления — план Х или план Y с каким-то доп. пакетом, а может план Z с двумя пакетами? Пакетов на каждый план много, включают разные наборы услуг и т.д., задача сводится к подбору варианта сочетания, а не просто посчитать затраты по каждому плану и отсортировать их. Вариантов этих получится много,
Можно пойти еще немного дальше и ввести некоторый процент точности в определении пользователем своих данных, тогда картина может в корне поменяться. Например мы выбрали план, а пользователь потратил на 5% больше минут, и из-за этого оплатился следующий интервал тарификации и получился большой перерасход. При выборе другого плана такого могло не случится. Хотя эта задача уже совсем другая...
Здравствуйте, alextop, Вы писали:
A>Т.е. как подсчитать, что выгоднее при данном уровне потребления — план Х или план Y с каким-то доп. пакетом, а может план Z с двумя пакетами? Пакетов на каждый план много, включают разные наборы услуг и т.д., задача сводится к подбору варианта сочетания, а не просто посчитать затраты по каждому плану и отсортировать их. Вариантов этих получится много,
в чем подбор-то? Если человек звонит на "домашние", значит "любимые" ему включать бессмысленно. Если человек мало пользуется СМС, значет пакет 1000 СМС всего за Х рублей ему то же не подходит
A>Можно пойти еще немного дальше и ввести некоторый процент точности в определении пользователем своих данных, тогда картина может в корне поменяться. Например мы выбрали план, а пользователь потратил на 5% больше минут, и из-за этого оплатился следующий интервал тарификации и получился большой перерасход. При выборе другого плана такого могло не случится. Хотя эта задача уже совсем другая...
имно это как раз самый правильный подход — проанализировать данные пользователя и выдать ему картинку по абсолютно всем сочетаниям тарифов +/- полезных для него пакеты. И позволить ему варьировать данные, на автомате подключая пакеты и добавляя точку на график.
Я бы копал в сторону упрощения ввода пользователем своих данных и удобства выдачи результата и варьирования параметров, нежели в сторону поиска навороченных алгоритмов оптимизации. Один фиг придумать абсолютные критерии не получится — кому-то может нравиться сидеть на МТС потому что логотип нравиться
Здравствуйте, alextop, Вы писали:
A>Здравствуйте, SkyDance, Вы писали:
A>>>Задача может быть решена прямым перебором SD>>Им, и только им, такие задачи и следует решать. Причина простая: единомоментно у оператора действует не более 30 тарифов, и к каждому предлагается не более 30 пакетов. Ну что такое 900 тестов для современной техники
A>В принципе да, для одного раза можно и самом посчитать, но у такого решения нет масштабируемости. A>Например, возьмем не одного оператора а несколько (10, 20...), планов суммарно может быть около 1000, пакетов — 1000-100000. A>Итого имеем порядка нескольких миллионов комбинаций. Такое будет считаться ощутимое время... Нужна какая-то оптимизация.
Отнюдь. У тебя есть 900 вариантов для одного оператора. Пакеты услуг от разных операторов не подходят друг к другу. Так что в итоге останется М*900 операций, где М — кол-во операторов связи, 900 — условное кол-во варинаторв подключения к одному из них.
Здравствуйте, Au1, Вы писали:
A>>В принципе да, для одного раза можно и самом посчитать, но у такого решения нет масштабируемости. A>>Например, возьмем не одного оператора а несколько (10, 20...), планов суммарно может быть около 1000, пакетов — 1000-100000. A>>Итого имеем порядка нескольких миллионов комбинаций. Такое будет считаться ощутимое время... Нужна какая-то оптимизация.
Au1>Отнюдь. У тебя есть 900 вариантов для одного оператора. Пакеты услуг от разных операторов не подходят друг к другу. Так что в итоге останется М*900 операций, где М — кол-во операторов связи, 900 — условное кол-во варинаторв подключения к одному из них.
Au1>Так что все вполне масштабируемо.
Если принять условие один план — один пакет, то наверное да, но на самом деле кол-во планов на пакет больше одного (порядка 5 кажется, точно пока не скажу, есть планы, которые просто состоят из пакетов, которые произвольно набираются). Т.е. фактически это сочетания. Посчитать можно перебором, вопросов нет, но если есть возможность сократить расчеты, то почему бы это не сделать. Осталось эту возможность найти... Еще неплохо было бы как-то аналитически описать ограничения сочетаний план-пакет, такие тоже есть (и само собой, исключить их сразу, или оставить только возможные).
A>Если принять условие один план — один пакет, то наверное да, но на самом деле кол-во планов на пакет больше одного (порядка 5 кажется, точно пока не скажу, есть планы, которые просто состоят из пакетов, которые произвольно набираются). Т.е. фактически это сочетания. Посчитать можно перебором, вопросов нет, но если есть возможность сократить расчеты, то почему бы это не сделать.
Потому что нет смысла. Вы дольше будете вбивать эти планы и пакеты, чем считать. Миллион-другой комбинаций любой сколь-нибудь современный процессор (даже тормозные Atom'ы) считают почти мгновенно.
Здравствуйте, alextop, Вы писали:
A>Т.о. задача по сути превращается в комбинаторную — найти оптимальную комбинацию "пакеты (как правило несколько) + тарифный план", которая даст минимальную общую стоимость при заданном наборе входных данных.
A>Задача может быть решена прямым перебором, но мне кажется должны существовать методы либо для решения не комбинаторного, либо для сокращения кол-ва вариантов перебора (например, после сортировки стоимостей пакетов можно отбрасывать дорогие пакеты и т.д.). A>Подскажите, пожалуйста, в какую сторону копать?
Имитационное моделирование — берешь историю звонков за прошлый месяц из истории телефона, и считаешь, во сколько бы они тебе вышли на каждом тарифном плане. Никакого перебора, совершенно линейные вычисления. Это если не шашечки, а ехать.
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, alextop, Вы писали:
A>>Т.о. задача по сути превращается в комбинаторную — найти оптимальную комбинацию "пакеты (как правило несколько) + тарифный план", которая даст минимальную общую стоимость при заданном наборе входных данных.
Кё>Имитационное моделирование — берешь историю звонков за прошлый месяц из истории телефона, и считаешь, во сколько бы они тебе вышли на каждом тарифном плане. Никакого перебора, совершенно линейные вычисления. Это если не шашечки, а ехать.
Ехать — да, но недалеко Я ж написал, сам по себе оптимальный план вычисляется довольно просто, именно так, как вы написали (хотя опять же, надо будет пересчитывать все планы у всех операторов).
Но любой план сам по себе заранее менее выгоден, чем план в сочетании с какими-то (какими? вот вопрос) пакетами. Перебирать комбинации план + пакет(ы) — это и есть задача, которую пытаюсь оптимально решить.
