Оптимизация инвентаризации с помощью науки о данных Практическое руководство с использованием Python

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

Простой пример управления запасами веломагазина

Вернемся к примеру веломагазина: Представьте, что у вас есть веломагазин с запасами, которые могут вместить только определенное количество велосипедов (ограниченная вместимость). Например, предположим, что ваш магазин может вместить максимум 5 велосипедов.

Каждый день в ваш магазин приходят покупатели, чтобы купить велосипеды. Предположим, что сегодня (среда) у вас в магазине есть три велосипеда. Однако вы также знаете, что завтра (четверг) будет спрос на ваш магазин, то есть некоторые из ваших велосипедов будут проданы. Вы не знаете, сколько покупателей будет завтра, что означает, что точный спрос на велосипеды завтра неизвестен. Нам нужно более точно смоделировать этот процесс, смоделировать, как меняется состояние запасов и как он развивается. ¹

Описание проблемы

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

Состояние (внутреннее представление процесса) можно описать двумя компонентами:

• α : количество велосипедов, которые уже есть в магазине
• β : количество велосипедов, которые были заказаны в предыдущий день и прибудут завтра утром (эти велосипеды находятся на грузовике)

Последовательность цикла 24 часа

Последовательность событий в цикле 24 часа для этого веломагазина выглядит следующим образом:

1. В 18:00: вы наблюдаете состояние S_t:(α,β)
2. В 18:00: вы заказываете новые велосипеды, равные max(C−(α+β),0)
3. В 6:00: Вы получаете велосипеды, которые вы заказали 36 часов назад
4. В 8:00: Вы открываете магазин
5. С 8:00 до 18:00 вы испытываете спрос i в течение дня (моделируется с использованием распределения Пуассона) подробнее ниже.
6. В 18:00 вы закрываете магазин

Диаграмма ниже визуализирует эту последовательность:

Аналогично объяснению выше, St=(αt+βt) является внутренним представлением этого стохастического процесса, и в Марковском процессе мы хотим моделировать, как этот стохастический процесс развивается.

Пример, демонстрирующий 24-часовую последовательность запасов.

Давайте приведу пример. Допустим, Дэвид является владельцем веломагазина. В среду (18:00) у него в магазине есть 2 велосипеда, и один велосипед он заказал в понедельник в 18:00. Его состояние будет:

Таким образом, состояние в момент времени среда 20:00 составляет S=(α=2,β=1). Затем каждый день есть случайный (неотрицательный целый) спрос на велосипеды, спрос моделируется с помощью распределения Пуассона (с параметром λ∈R>). Спрос на i велосипедов для каждого i=0,1,2⋯ происходит с вероятностью:

Мы можем визуализировать это распределение, чтобы увидеть вероятность различных спросов при выборе λ=2

# import matplotlib and some desired stylingimport matplotlib.pyplot as plt%matplotlib inlineplt.style.use("ggplot")plt.rcParams["figure.figsize"] = [10, 6]# need numpy to do some numeric calculationimport numpy as np# poisson is used to find pdf of Poisson distribution from scipy.stats import poisson

x_values = np.arange(0,10)# pdf Poisson distri with lambda = 1pdf_x_values = poisson.pmf(k=x_values,mu=2)plt.bar(x_values, pdf_x_values, edgecolor='black')plt.xticks(np.arange(0, 10, step=1))plt.xlabel("Спрос покупателей")plt.ylabel("Вероятность спроса покупателей")plt.title("Распределение вероятности спроса покупателей с $\lambda = 1$ ")plt.savefig("fig/poisson_lambda_2.png", dpi=300)plt.show()

Построение вероятностного перехода Марковского процесса:

Теперь, когда у нас есть начальное понимание того, что такое состояние, St=(α,β), неопределенность, которую вводит понятие стохастического процесса, является спросом покупателей (i). Мы можем продолжить развитие вероятностного перехода в этой задаче. Я сделаю кодирование для этого, но сначала объясним это более простыми словами.

Вероятностный переход этой задачи имеет два случая, случай 1 и 2.

• Случай 1)

Если спрос i меньше общего имеющегося запаса в этот день, начальный запас = α+β

• Случай 2)

Если спрос i больше общего имеющегося запаса в этот день, начальный запас = α+β

Где F(α+β−1) – это функция распределения Пуассона.

Поняв фоновую информацию по этой проблеме, мы можем написать некоторый код на Python, чтобы лучше ее понять. Основной аспект этого кода на Python – разработка структуры данных для хранения переходов процесса Маркова. Для этого я разрабатываю структуру данных в виде Словаря, который я называю “MarkovProcessDict”. Ключи этого словаря соответствуют текущему состоянию, а значения (представленные в виде словаря) – следующим состояниям, вместе с вероятностями, связанными с каждым следующим состоянием. Вот пример того, как выглядит структура данных MarkovProcessDict:

from typing import DictMarkovProcessDict = {"Текущее состояние A":{"Следующее состояние 1, от A": "Вероятность следующего состояния 1, от A",                                        "Следующее состояние 2, от A": "Вероятность следующего состояния 2, от A"},                                         "Текущее состояние B":{"Следующее состояние 1, от B": "Вероятность следующего состояния 1, от B",                                        "Следующее состояние 2, от B": "Вероятность следующего состояния 2, от B" }}MarkovProcessDict

Давайте разберем, что означает структура данных MarkovProcessDict. Например, начальное состояние – “Текущее состояние A”, которое может перейти к двум новым состояниям:

• 1) “Следующее состояние 1, от A”, с вероятностью “Вероятность следующего состояния 1, от A“
• 2) “Следующее состояние 2, от A”, с вероятностью “Вероятность следующего состояния 2, от A“.

Практическое программирование

Давайте напишем код для создания структуры данных MarkovProcessDict, с учетом двух различных случаев этого процесса, объясненных ранее.

MarkovProcessDict: Dict[tuple, Dict[tuple, float]] = {}user_capacity = 2user_poisson_lambda = 2.0

# Мы рассматриваем все возможные состояния# С которыми мы можем столкнуться в работе этого веломагазинаfor alpha in range(user_capacity+1):                                                                                               for beta in range(user_capacity + 1 - alpha):                # Это St, текущее состояние        state = (alpha, beta)                                           # Это начальный инвентарь, общее количество велосипедов у вас в 8 утра         initial_inventory = alpha + beta                                         # beta1 - это beta в следующем состоянии, независимо от         #текущего состояния (поскольку политика принятия решений постоянна)        beta1 = user_capacity - initial_inventory                # Список всех возможных спросов, с которыми вы можете столкнуться        for i in range(initial_inventory +1):            # если начальный спрос может удовлетворить спрос            if i <= (initial_inventory-1):                                # вероятность того, что возникнет конкретный спрос                transition_prob = poisson.pmf(i,user_poisson_lambda)                                # Если мы уже определили состояние в наших данных                 # (MarkovProcessDict)                if state in MarkovProcessDict:                                        MarkovProcessDict[state][(initial_inventory - i, beta1)]= transition_prob                                else:                                        MarkovProcessDict[state] = {(initial_inventory - i, beta1):transition_prob }                                     # если начальный спрос не может удовлетворить спрос            else:                                # вероятность того, что не будет удовлетворен спрос                transition_prob = 1- poisson.cdf(initial_inventory -1, user_poisson_lambda)                if state in MarkovProcessDict:                                        MarkovProcessDict[state][(0, beta1)]= transition_prob                                    else:                    MarkovProcessDict[state] = {(0, beta1 ):transition_prob }

В приведенном выше коде цикл for перебирает все возможные комбинации состояний, и каждое состояние (St) переходит в следующее состояние (S_{t+1}) с вероятностью “transition_prob”. Мы можем вывести динамику системы с помощью следующего кода:

or (state, value) in MarkovProcessDict.items():        print("Текущее состояние: {}".format(state))        for (next_state, trans_prob) in value.items():        print("Следующее состояние: {} с вероятностью {:.2f}".format(next_state, trans_prob))

Визуализация конечной структуры данных

Один из способов понять эти динамики — использовать пакет graphviz для Python, где каждый узел представляет собой текущее состояние, а ребра показывают вероятность перехода из одного состояния в другое.

# импорт пакетаimport graphviz  # определение начальной структуры графа визуализации d = graphviz.Digraph(node_attr={'color': 'lightblue2', 'style': 'filled'},                     )d.attr(size='10,10')d.attr(layout = "circo")for s, v in MarkovProcessDict.items():        for s1, p in v.items():                        # представление альфы и беты с помощью s[0] и s[1]            d.edge("(\u03B1={}, \u03B2={})".format(s[0],s[1]),                    # представление p как вероятности перехода из текущего состояния в новое состояние                    "(\u03B1={}, \u03B2={})".format(s1[0],s1[1]), label=str(round(p,2)), color="red")            print(d)

На нижеприведенном графике я визуализировал графики этого перехода. Например, если мы находимся в состоянии St = (α=1,β=0) (круг в верхнем левом углу), то существует 86% вероятность, что следующее состояние будет S(t+1):(α=0,β=1), и 14% вероятность, что следующее состояние будет S(t+1):(α=1,β=1).

Заключительные заметки

• Оптимизация запасов — это не статическая оптимизационная задача; скорее, это последовательное принятие решений, требующее адаптивной политики для принятия наилучшего решения с учетом неопределенности на каждом временном этапе.
• В этой статье я попытался построить математическую модель для отслеживания процесса управления запасами (с использованием состояний и процесса Маркова) и визуализировал динамику процесса с помощью практического программирования на Python.
• Эта статья является основой для работы с проблемами оптимизации запасов, где на следующих этапах мы будем работать с Марковским вознаграждением и Марковским процессом принятия решений.

[1] Вы можете прочитать этот пример более подробно в книге «Основы обучения с подкреплением с применением в финансах». Однако я переписал коды Python в этой статье, чтобы его было проще понять.

Спасибо за чтение до конца!

Я надеюсь, что этот материал предоставил понятное руководство по оптимизации запасов с помощью Python.

Если вы считаете, что этот материал помог вам узнать больше о оптимизации запасов и процессе Маркова, пожалуйста, поставьте 👏 и подпишитесь!