Математические модели

Из книги "Теоретический минимум по Computer Science Distilled", автор Владстон Феррейра Фило.

Математическое моделирование рассматиривается в этом разделе для полноты картины, хотя формально оно является самостоятельной междисциплинарной областью.

Математическое моделирование — это умение перевести бизнес-задачу на язык цифр.

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

Математические модели имеют большое преимущество: их можно приспособить для компьютеров при помощи четко сформулированных математических методов.

Если ваша модель основана на графах, используйте теорию графов. Если она задействует уравнения, используйте алгебру.

Модель: Выбор лучшего кандидата

Для построения модели отлично подходит «Задача о разборчивой невесте».

Сценарий: Невеста ищет лучшего жениха из $N$ кандидатов.

1. Невеста смотрит кандидатов по одному в случайном порядке.
2. После каждого свидания она должна немедленно решить: станет ли он ей парой или отказать.
3. Если невеста отказала — вернуться к кандидату уже нельзя.
4. Если невеста выбрала кого-то — процесс останавливается, остальных она уже не смотрит.

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

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

Математическое решение

Оптимальная стратегия заключается в разделении процесса на два этапа:

1. Этап обучения: Первые $k$ кандидатов вы просто просматриваете, отказывая всем им, но фиксируете для себя уровень лучшего из них.
2. Этап выбора: Начиная с кандидата $k+1$, вы нанимаете первого же человека, который окажется лучше всех предыдущих.

Вопрос моделирования: чему должно быть равно $k$?

Через вычисление предела вероятностей (используя натуральные логарифмы) математики вывели магическое число: $$k=\frac{N}{e}\approx 0,37N$$

Вывод модели

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

• Если у вас 10 кандидатов — посмотрите троих и берите следующего лучшего.
• Если у вас 100 кандидатов — пропустите 37.

Интересный факт: При такой стратегии вероятность успеха (найма именно самого лучшего из всей сотни) также составляет примерно 37%. Для случайного выбора из 100 человек это очень высокий показатель.

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

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

Модель: Поиск экстремума функции

Загон для скота На ферме содержат два вида домашних животных. У вас есть 100 мотков проволоки для сооружения прямоугольного загона и перегородки внутри него, отделяющей одних животных от других. Как поставить забор, чтобы площадь пастбища была максимальной?

Где:

• $w$ - ширина пастбища
• $l$ - длина пастбища

Сделать площадь максимальной означает использовать всю проволоку, потому мы устанавливаем связь между $w$ и $l$, с одной стороны, и 100 мотками, с другой:

Подберем $w$ и $l$, при которых площадь $A$ будет максимальной.

Из уравнения связи (периметра с перегородкой) выразим $l$:

$$3l=100-2w$$

$$l=\frac{100-2w}{3}$$

Подставим полученное выражение в формулу площади $A=w\times l$:

$$A(w)=w\cdot \left(\frac{100-2w}{3}\right)=\frac{100w-2w^2}{3}$$

Нахождение максимума. Графиком данной функции является парабола, ветви которой направлены вниз. Максимум находится в её вершине. Чтобы найти его, возьмем производную по $w$ и приравняем её к нулю:

$$A^{\prime }(w)=\frac{1}{3}(100-4w)$$

$$100-4w=0$$

$$w=25$$

Нахождение второй стороны. Теперь найдем оптимальное значение $l$, подставив $w=25$ в уравнение связи:

$$l=\frac{100-2\cdot 25}{3}=\frac{50}{3}\approx 16,67$$

Ответ:

Для достижения максимальной площади размеры загона должны быть:

• Ширина ($w$): $25$ единиц.
• Длина ($l$): $16\frac{2}{3}$ (или примерно $16,67$) единиц.

Максимальная площадь при этом составит:

$$A=25\cdot \frac{50}{3}=\frac{1250}{3}\approx 416,67\text{ кв. единиц.}$$

Модель: «Формула Уилсона» (Оптимальный размер заказа)

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

• Издержки на заказ необходимых педалей. Вам выгоднее заказывать редко, но огромными партиями.
• Издержки на хранение: Педали нужно где-то хранить. Склад стоит денег. Вам выгоднее заказывать часто, но крошечными партиями, чтобы склад был почти пустым.

Задача: Найти такой размер одной партии заказа комплектующих ($Q$), при котором суммарные издержки (доставка + хранение) будут минимальными.

Математическое решение

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

Пусть:

• $D$ — годовой спрос (сколько всего педалей нам нужно в год);
• $S$ — стоимость одного заказа педалей (фикс за доставку и оформление);
• $H$ — стоимость хранения одной единицы товара в год;
• $Q$ — объем одной партии (искомая переменная).

Суммарные издержки $TC$ состоят из двух частей:

1. Издержки на заказ: $\frac{D}{Q}\cdot S$ (чем больше партия $Q$, тем меньше трат).
2. Издержки на хранение: $\frac{Q}{2}\cdot H$ (чем больше партия $Q$, тем выше средний запас на складе и траты).

Итоговая функция издержек: $$TC(Q)=\frac{D\cdot S}{Q}+\frac{H\cdot Q}{2}$$

Чтобы найти минимум, мы берем производную и приравниваем её к нулю (как при поиске вершины параболы в Вашем примере с загоном): $$\frac{d(TC)}{dQ}=-\frac{D\cdot S}{Q^2}+\frac{H}{2}=0⟹Q^{\ast }=\sqrt{\frac{2DS}{H}}$$

import matplotlib.pyplot as plt
import numpy as np

# Параметры модели
D = 1000  # Годовой спрос
S = 50    # Стоимость заказа
H = 2     # Стоимость хранения

# Диапазон объемов заказа
Q = np.linspace(10, 500, 400)

# Функции издержек
ordering_cost = (D * S) / Q
holding_cost = (H * Q) / 2
total_cost = ordering_cost + holding_cost

# Оптимальная точка (EOQ)
q_opt = np.sqrt((2 * D * S) / H)
tc_min = (D * S / q_opt) + (H * q_opt / 2)

# Построение графика
plt.figure(figsize=(10, 6))
plt.plot(Q, ordering_cost, '--', label='Издержки на заказ (S/Q)', color='blue')
plt.plot(Q, holding_cost, '--', label='Издержки на хранение (H*Q/2)', color='green')
plt.plot(Q, total_cost, label='Суммарные издержки (TC)', color='red', linewidth=2)

# Отметка минимума (аналог вершины)
plt.scatter([q_opt], [tc_min], color='black', zorder=5)
plt.annotate(f'Оптимальный заказ Q* ≈ {int(q_opt)}', xy=(q_opt, tc_min), xytext=(q_opt+20, tc_min+100),
             arrowprops=dict(facecolor='black', shrink=0.05))

plt.title('Моделирование оптимального размера заказа (EOQ)')
plt.xlabel('Размер партии (Q)')
plt.ylabel('Суммарные затраты ($)')
plt.grid(True, linestyle=':', alpha=0.6)
plt.legend()
plt.show()

Это именно тот случай, когда квадратное уравнение (или его аналог при поиске экстремума) экономит компании миллионы, а программист, пишущий логику для ERP-системы, должен понимать, откуда этот $Q^{\ast }$ взялся в техническом задании.

Модель: Сравнение сортировки вставками и сортировки слиянием

В теории алгоритмов ($O$-нотация) мы часто отбрасываем константы, но в реальности они имеют решающее значение.

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

1. Сортировка вставками (Insertion Sort): Имеет сложность $O(n^2)$, но она очень «легкая» и быстро выполняется на малых данных.
2. Сортировка слиянием (Merge Sort): Имеет сложность $O(n\log n)$, но она «тяжелая» из-за рекурсии и выделения памяти.

1. Формализация задачи

Представим, что мы замерили время работы на конкретном процессоре и получили следующие функции времени (в микросекундах) от количества элементов $n$:

• $T_1(n)=2n^2$ (Квадратичный алгоритм)
• $T_2(n)=50n{\log }_{2}n$ (Логарифмический алгоритм)

Нам нужно найти точку пересечения — критическое значение $n$, после которого «быстрый» алгоритм действительно станет быстрее.

2. Математическая модель

Чтобы найти эту точку, нам нужно решить уравнение: $$2n^2=50n{\log }_{2}n$$

Разделим обе части на $2n$ (при $n>0$): $$n=25{\log }_{2}n$$

Это трансцендентное уравнение, которое часто сводится к анализу функций, похожих на квадратичные зависимости в определенном диапазоне. Если мы упростим задачу для наглядности (например, сравнивая $n^2$ и $100n+500$), мы получим классическое квадратное уравнение.

import matplotlib.pyplot as plt
import numpy as np

# Количество элементов
n = np.linspace(1, 350, 400)

# Время выполнения (условные единицы)
t_insertion = 2 * n**2              # Квадратичная сложность
t_merge = 50 * n * np.log2(n + 1)    # Сортировка слиянием

# Поиск точки пересечения (приблизительно)
idx = np.argwhere(np.diff(np.sign(t_insertion - t_merge))).flatten()

plt.figure(figsize=(10, 6))
plt.plot(n, t_insertion, label='Сортировка вставками (2n²)', color='red', linewidth=2)
plt.plot(n, t_merge, label='Сортировка слиянием (50n log n)', color='blue', linewidth=2)

if len(idx) > 0:
    plt.scatter(n[idx], t_insertion[idx], color='black', zorder=5)
    plt.annotate(f'Точка эффективности n ≈ {int(n[idx][0])}', 
                 xy=(n[idx], t_insertion[idx]), 
                 xytext=(n[idx]-40, t_insertion[idx]+2000),
                 arrowprops=dict(facecolor='black', shrink=0.05))

plt.title('Сравнение эффективности алгоритмов')
plt.xlabel('Количество элементов (n)')
plt.ylabel('Время выполнения (мкс)')
plt.grid(True, linestyle=':', alpha=0.6)
plt.legend()
plt.ylim(0, 120000)
plt.show()

На графике Вы увидите:

1. Зона до $n\approx 189$: Квадратичный алгоритм (красная линия) находится ниже. Это значит, что для небольших массивов «плохая» сортировка вставками работает быстрее, чем «умная» сортировка слиянием.
2. Точка пересечения: Здесь их эффективность равна.
3. Зона после: Квадратичная функция начинает «взлетать» вверх. Здесь и проявляется важность $O$-нотации.

Практический вывод: Именно поэтому в стандартных библиотеках (например, в Java или Python для Timsort) используется гибрид: массив сначала разбивается на мелкие куски, которые сортируются вставками ($n^2$), а затем они объединяются слиянием ($n\log n$). Программисты рассчитали эту модель и поняли, что на малых $n$ парабола выгоднее логарифма.