Ответы пользователя по тегу Алгоритмы
  • А не поможете с прогнозированием продаж?

    vanxant
    @vanxant
    У вас классическая задача на методы оптимизации (man методы оптимизации).

    Сначала введите обозначения:
    Goal — плановая выручка
    для i-того товара
    price[i] — цена
    qty[i] — остаток на складе
    w[i] — сложность продаваемости
    plan[i] — искомый план

    Дальше советую начать со случая двух товаров, так это всё очень наглядно. Как разберетесь с двумя — разберетесь и с любым количеством.
    Берете ручку, рисуете график.
    По оси x у вас plan[1], по оси y — plan[2].
    Рисуете две прямых и помечаете области под ними:
    plan[1]<=qty[1]
    plan[2]<=qty[2]
    Рисуете еще одну прямую и заштриховываете область НАД ней
    plan[1]*price[1] + plan[2]*price[2] >= Goal

    Заштрихованный треугольник, который получился — это ваше пространство потенциальных решений. Если треугольника не получилось, значит при ваших исходных данных решить задачу вообще нельзя (нужно или снижать хотелку, или повышать запасы на складах).

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

    Для случая трёх товаров у вас получится не треугольник, а пирамидка из 4 точек, для 1000 товаров — 1001-мерная «пирамидка» из треугольников.

    Дальше выписываете вашу целевую функцию:
    Ф(plan[]) = plan[1]*w[1] + plan[2]*w[2] (… + plan[i]*w[i] + ....)
    Вам нужно найти точку в пространстве решений, в котором ваша функция будет иметь минимум. Таким образом вы найдете миниальный план продаж, при котором выполняются все ваши ограничения.

    Вы халявщик, потому что ваша целевая функция Ф — линейная. Можно доказать, что её минимум будет лежать в одном (или нескольких) углах треугольника/пирамидки. Поэтому вам нужно просто посчитать значения Ф во всех углах и выбрать среди них те, где значене Ф() будет минимальным.
    Почему возможно несколько минимальных решений — ну если например у вас два товара с одинаковой ценой и одинаковой сложностью, то вам без разницы, продать один или другой.
    Собственно всё, задача решена.
    Ответ написан
    2 комментария
  • Есть ли здесь бывшие олимпиадники? Как олимпиады помогли Вам?

    vanxant
    @vanxant
    В моем случае (Бауманка) дипломами посоветовали подтереться, типа на вас таких мест не хватит. А вот знания пригодятся, если не хотите прожить жизнь тупым быдлокодерам. Нет, ну понятно, что в хорошем вузе вы все это пройдете, но там дают знания под другим углом зрения. Готовят для решения стандартных задач. А олимпиады готовят к нестандартным.
    Ну и вообще, just for fun, есть что вспомнить, и опять же есть чем меряться.
    Ответ написан
    Комментировать