ارلانگ B در پایتون؛ احتمالِ انسداد با مدلِ بی‌صف و حسابِ دقیق

داشتنِ چهار جایگاهِ تماس، به‌تنهایی احتمالِ ردشدنِ تماسِ بعدی را تعیین نمی‌کند. این احتمال به مدلِ ورود و مدتِ اشغال هم وابسته است. در این آموزش، فرمولِ ارلانگ B را برای یک سامانهٔ فرضیِ بی‌صف با حسابِ کسری بررسی می‌کنیم. هدف، روشن‌کردنِ قرارداد و کنترلِ محاسبه است؛ هیچ ترافیکِ واقعی، ظرفیتِ سرور یا کیفیتِ مکالمه اندازه‌گیری نمی‌شود.

۱. بارِ پیشنهادی و فرض‌های مدلِ بی‌صف

در مدلِ انتخاب‌شده، ورودها یک فرایندِ پواسون با نرخِ ثابت‌اند. مدت‌های خدمت، مستقل و نمایی با میانگینِ ثابت فرض می‌شوند؛ هر تماس دقیقاً یک جایگاهِ همسان می‌گیرد. تماسِ واردشده به سامانهٔ پُر، فوراً از مدل خارج می‌شود. صف، تماسِ مجدد، انصرافِ منتظر، اولویت و رزرو نداریم. این‌ها فرض‌های مسئله‌اند و از صرفِ داشتنِ گزارشِ تماس نتیجه نمی‌شوند.

بخشِ ۴٫۶ کتابِ پژوهشِ عملیاتیِ شهریِ MIT فرضِ ورودِ پواسون را بیان می‌کند و دربارهٔ موجِ ورود در رخدادهای بزرگ هشدار می‌دهد. این یادآوری برای تلفنِ سازمانی هم مفید است: یک میانگینِ روزانه، به‌تنهایی خوشه‌ای‌بودنِ ورودها یا تغییرِ نرخ در طولِ روز را حذف نمی‌کند. ما نرخ را تخمین نمی‌زنیم؛ مقدارِ ساختگی را صریح می‌دهیم.

بارِ پیشنهادی را با A برابرِ نرخِ ورود ضرب‌در میانگینِ مدتِ خدمت تعریف می‌کنیم. اگر نرخ، سه‌دوم تماس در دقیقه و مدتِ متوسط، دو دقیقه باشد، A سه ارلانگ است. دقیقه‌ها حذف می‌شوند؛ ارلانگ واحدِ بیانِ بارِ بی‌بُعد است، نه تعدادِ قطعیِ تماس‌های فعال. تغییرِ واحدِ یکی از دو ورودی بدون تبدیلِ دیگری، جواب را خراب می‌کند.

نمادِ M/M/c/c همین انتخابِ ورود و خدمت و ظرفیتِ محدود را خلاصه می‌کند. شرایطِ کافیِ مدلِ ما را نباید شرطِ لازمِ همهٔ تعمیم‌های ارلانگ B معرفی کرد؛ منبعِ MIT به تعمیمِ مدتِ خدمت هم اشاره دارد. این درس آن تعمیم را اثبات یا شبیه‌سازی نمی‌کند و برای بارِ متغیر، منابعِ ناهمسان یا رفتارِ تماسِ مجدد نتیجه نمی‌دهد.

۲. احتمالِ اشغالِ کامل از وزن‌های حالت

حالتِ n یعنی n جایگاهِ مشغول، از صفر تا c. برای این مدلِ ماندگار، وزنِ حالت برابرِ A به توانِ n تقسیم‌بر n فاکتوریل است. وزن‌ها هنوز احتمال نیستند؛ هرکدام را بر مجموعِ وزن‌های صفر تا c تقسیم می‌کنیم. معادلهٔ ۴٫۵۷ و حالتِ بدونِ انتظار در MIT همین توزیعِ محدود و احتمالِ پُربودن را توضیح می‌دهد.

با فرضِ ورودِ پواسونِ مستقلِ همین مدل، احتمالِ دیده‌شدنِ سامانهٔ پُر هنگامِ ورود، با احتمالِ زمانیِ حالتِ c برابر است؛ آن را B می‌نامیم. این برابری را برای هر نوعِ ورود تعمیم نمی‌دهیم. همچنین ماندگار یعنی توصیفِ بلندمدتِ مدل؛ احتمالِ وضعیتِ خاصِ یک سامانهٔ تازه‌روشن‌شده یا پیش‌بینیِ قطعیِ تماسِ بعدی نیست.

برای A برابرِ سه و c برابرِ سه، وزن‌ها یک، سه، نه‌دوم و نه‌دوم‌اند و مجموعشان سیزده است. پس احتمال‌های حالت به‌ترتیب یک‌سیزدهم، سه‌سیزدهم، نه‌بیست‌وششم و نه‌بیست‌وششم می‌شوند. احتمالِ انسداد نه‌بیست‌وششم است. مجموعِ احتمال‌ها یک می‌شود؛ یکسان‌بودنِ دو احتمالِ آخر ویژگیِ همین ورودی است، نه قانونِ عمومیِ مدل.

تعدادِ متوسطِ جایگاه‌های مشغول، مجموعِ n ضرب‌در احتمالِ حالتِ n است؛ در مثال پنجاه‌ویک‌بیست‌وششم می‌شود. همین مقدار از A ضرب‌در یک‌منهای B به دست می‌آید و بارِ حمل‌شده است. بارِ پیشنهادیِ سه با بارِ حمل‌شده برابر نیست، چون بخشی رد می‌شود. این متوسط، مصرفِ CPU یا شمارِ کانالِ خریداری‌شده نیست.

۳. رابطهٔ بازگشتی و مرجعِ مستقلِ دقیق

لازم نیست در مسیرِ اصلی، توان‌ها و فاکتوریل‌ها را دوباره بسازیم. از مقدارِ قراردادیِ B برای ظرفیتِ صفر، یعنی یک، آغاز می‌کنیم. برای هر ظرفیتِ k، حاصلِ A ضرب‌در B قبلی را بر مجموعِ همان حاصل و k تقسیم می‌کنیم. این رابطه از جداکردنِ آخرین وزنِ مجموعِ نرمال‌سازی به دست می‌آید؛ پارامترِ تازه‌ای به مدل اضافه نمی‌کند.

برای کنترلِ مستقل، مسیرِ دوم مستقیماً همهٔ وزن‌های فاکتوریلی را می‌سازد و نرمال می‌کند؛ تابعِ بازگشتی را صدا نمی‌زند. علاوه‌بر آخرین احتمال، جمعِ احتمال‌ها و توازنِ دو حالتِ مجاور بررسی می‌شوند: احتمالِ حالتِ n ضرب‌در A باید برابرِ احتمالِ حالتِ بعدی ضرب‌در n به‌علاوهٔ یک باشد. توافقِ این مسیرها جای بررسیِ فرض‌ها را نمی‌گیرد.

مستنداتِ Fraction در پایتون حسابِ عددهای گویا را توضیح می‌دهد. کسر را از صورت و مخرجِ صحیح می‌سازیم؛ تبدیلِ اعشارِ دودویی الزاماً همان کسرِ ده‌دهیِ موردنظر نیست. بنابراین ورودیِ برنامه فقط Fraction دقیق است و مقدارِ اعشاری خودکار تبدیل نمی‌شود. این سخت‌گیری قراردادِ آموزشیِ ماست، نه محدودیتِ عمومیِ کتابخانه.

۴. کدِ کامل و انتخابِ ظرفیت در دامنهٔ محدود

فایلِ کامل با CPython 3.14.5 و کتابخانهٔ استاندارد، یک‌بار اجرا شده است. مستندِ خوانده‌شدهٔ پایتون نسخهٔ 3.14.8 است؛ این دو نسخه را یکسان گزارش نمی‌کنیم. MATLAB، مرکزِ تلفن و شبیه‌سازیِ تصادفی اجرا نشده‌اند. کدِ زیر، محاسبهٔ دقیقِ مدل را همراهِ مرجع، ورودی‌های نامجاز و پاسخِ نمونه نگه می‌دارد.

"""Original bounded exact Erlang B lesson; no calls, random simulation or PBX."""
from enum import IntEnum
from fractions import Fraction
from math import factorial
import json
import platform


def _load(value):
    if type(value) is not Fraction:
        raise TypeError('load must be an exact Fraction, not a coerced number')
    if not 0 <= value <= 20 or value.denominator > 1000:
        raise ValueError('load outside 0..20 Erlangs or denominator above 1000')
    return value


def _channels(value):
    if type(value) is not int:
        raise TypeError('channels must be an exact int; bool and enums excluded')
    if not 0 <= value <= 20:
        raise ValueError('channels outside 0..20')
    return value


def offered_load(arrivals_per_minute, mean_holding_minutes):
    """Exact declared units only; this function does not estimate either input."""
    for value in (arrivals_per_minute, mean_holding_minutes):
        if type(value) is not Fraction:
            raise TypeError('rate and mean holding time must be exact Fractions')
        if not 0 <= value <= 20 or value.denominator > 1000:
            raise ValueError('declared parameter outside bounded contract')
    if mean_holding_minutes == 0:
        raise ValueError('positive mean holding time required')
    return _load(arrivals_per_minute * mean_holding_minutes)


def erlang_b(load, channels):
    """B(0,A)=1; A=0 with positive capacity gives zero by convention."""
    _load(load)
    _channels(channels)
    blocked = Fraction(1)
    for count in range(1, channels + 1):
        numerator = load * blocked
        blocked = numerator / (count + numerator)
    return blocked


def factorial_state_oracle(load, channels):
    """Separate direct state weights; never calls the Erlang B recurrence."""
    _load(load)
    _channels(channels)
    weights = tuple(load ** n / factorial(n) for n in range(channels + 1))
    total = sum(weights, Fraction(0))
    return tuple(weight / total for weight in weights)


def minimum_channels(load, target, maximum=20):
    """First c in the actually checked 0..maximum set with B(c,A)<=target."""
    _load(load)
    _channels(maximum)
    if load == 0:
        raise ValueError('dimensioning requires positive assumed arrival load')
    if type(target) is not Fraction:
        raise TypeError('target must be an exact Fraction')
    if not 0 < target < 1 or target.denominator > 1000000:
        raise ValueError('target must be in (0,1), denominator at most 1000000')
    for channels in range(maximum + 1):
        if erlang_b(load, channels) <= target:
            return channels
    return None


def rejects(function, expected):
    try:
        function()
    except expected:
        return True
    return False


def run_example():
    arrival_rate = Fraction(3, 2)
    mean_holding = Fraction(2)
    load = offered_load(arrival_rate, mean_holding)
    states = factorial_state_oracle(load, 3)
    loads = tuple(Fraction(n, 4) for n in range(81))
    oracle_comparisons = []
    balanced = []
    conservation = []
    for a in loads:
        for capacity in range(21):
            distribution = factorial_state_oracle(a, capacity)
            blocking = erlang_b(a, capacity)
            oracle_comparisons.append(distribution[-1] == blocking)
            balanced.append(sum(distribution, Fraction(0)) == 1
                and all(p >= 0 for p in distribution)
                and all(distribution[n] * a == distribution[n + 1] * (n + 1)
                        for n in range(capacity)))
            mean_busy = sum((n * p for n, p in enumerate(distribution)), Fraction(0))
            carried = a * (1 - blocking)
            conservation.append(mean_busy == carried and 0 <= carried <= capacity
                                and carried + a * blocking == a)

    class Number(IntEnum):
        ONE = 1

    class Ratio(Fraction):
        pass

    bad_load_types = (True, 3, 3.0, '3', None, Number.ONE, Ratio(3))
    bad_cap_types = (True, 3.0, '3', None, Number.ONE)
    checks = {
        'literal_three_erlang_state_distribution': load == 3 and states ==
            (Fraction(1, 13), Fraction(3, 13), Fraction(9, 26), Fraction(9, 26)),
        'literal_recurrence_values_zero_through_five_channels':
            tuple(erlang_b(load, c) for c in range(6)) ==
            (Fraction(1), Fraction(3, 4), Fraction(9, 17), Fraction(9, 26),
             Fraction(27, 131), Fraction(81, 736)),
        'independent_factorial_oracle_1701_finite_pairs':
            len(oracle_comparisons) == 1701 and all(oracle_comparisons),
        'normalized_nonnegative_states_and_adjacent_balance': all(balanced),
        'mean_busy_equals_carried_load_and_total_load_conserved':
            all(conservation) and sum(n * p for n, p in enumerate(states)) == Fraction(51, 26),
        'blocking_strictly_decreases_with_channels_for_positive_grid_loads':
            all(erlang_b(a, c + 1) < erlang_b(a, c)
                for a in loads[1:] for c in range(20)),
        'blocking_strictly_increases_with_grid_load_for_positive_channels':
            all(erlang_b(a, c) < erlang_b(b, c)
                for a, b in zip(loads, loads[1:]) for c in range(1, 21)),
        'zero_load_and_zero_capacity_conventions_are_explicit':
            all(erlang_b(Fraction(0), c) == 0 for c in range(1, 21))
            and all(erlang_b(a, 0) == 1 for a in loads),
        'minimum_capacity_and_inclusive_exact_threshold':
            minimum_channels(load, Fraction(1, 5)) == 5
            and minimum_channels(load, Fraction(27, 131)) == 4
            and minimum_channels(load, Fraction(9, 26)) == 3,
        'bounded_search_reports_no_solution_without_fabricated_capacity':
            minimum_channels(load, Fraction(1, 5), 4) is None
            and minimum_channels(load, Fraction(1, 5), 0) is None,
        'declared_rate_time_units_and_scale_preserve_offered_load':
            offered_load(Fraction(3), Fraction(1)) == load
            and offered_load(Fraction(1, 2), Fraction(6)) == load
            and offered_load(Fraction(0), Fraction(2)) == 0,
        'one_channel_closed_form_and_maximum_boundary':
            all(erlang_b(a, 1) == a / (1 + a) for a in loads)
            and type(erlang_b(Fraction(20), 20)) is Fraction,
        'strict_input_types_ranges_and_positive_dimensioning_contract':
            all(rejects(lambda a=a: erlang_b(a, 3), TypeError) for a in bad_load_types)
            and all(rejects(lambda c=c: erlang_b(load, c), TypeError) for c in bad_cap_types)
            and all(rejects(lambda a=a: erlang_b(a, 3), ValueError)
                    for a in (Fraction(-1), Fraction(21), Fraction(1, 1001)))
            and all(rejects(lambda c=c: erlang_b(load, c), ValueError) for c in (-1, 21))
            and rejects(lambda: offered_load(Fraction(1), Fraction(0)), ValueError)
            and rejects(lambda: offered_load(Fraction(20), Fraction(20)), ValueError)
            and rejects(lambda: offered_load(Fraction(1, 999), Fraction(1, 998)), ValueError)
            and rejects(lambda: offered_load(1, Fraction(2)), TypeError)
            and rejects(lambda: minimum_channels(Fraction(0), Fraction(1, 5)), ValueError)
            and rejects(lambda: minimum_channels(load, 0.2), TypeError)
            and all(rejects(lambda t=t: minimum_channels(load, t), ValueError)
                    for t in (Fraction(0), Fraction(1), Fraction(-1), Fraction(1, 1000001)))
            and rejects(lambda: minimum_channels(load, Fraction(1, 5), True), TypeError),
    }
    assert all(type(value) is bool for value in checks.values())
    assert all(checks.values()), checks
    return {
        'python': platform.python_version(),
        'dependencies': 'Python standard library only',
        'scope': 'Original exact stationary M/M/c/c loss-model arithmetic; no real traffic, PBX or SLA',
        'assumptions': ['stationary independent Poisson arrivals',
                        'independent exponential holding times',
                        'identical single-slot servers; no waiting or retries'],
        'fixture': {'arrivals_per_minute': str(arrival_rate),
                    'mean_holding_minutes': str(mean_holding), 'offered_erlangs': str(load),
                    'three_channel_states': [str(x) for x in states],
                    'blocking_three_channels': str(erlang_b(load, 3)),
                    'mean_busy_three_channels': str(load * (1 - erlang_b(load, 3))),
                    'blocking_four_channels': str(erlang_b(load, 4)),
                    'blocking_five_channels': str(erlang_b(load, 5)),
                    'target': '1/5', 'minimum_checked_capacity': minimum_channels(load, Fraction(1, 5))},
        'finite_pairs_inside_one_oracle_group': len(oracle_comparisons),
        'zero_load_note': 'B(c=0,A=0)=1 is an algebraic convention, not an observed arrival blocking rate',
        'checks': checks,
    }


if __name__ == '__main__':
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

بار، کسرِ دقیقِ صفر تا بیست با مخرجِ حداکثرِ هزار است؛ ظرفیت، int دقیقِ صفر تا بیست است. نرخ و مدتِ تابعِ تبدیل نیز کسرهای همین دامنه‌اند، مدت باید مثبت باشد و حاصل هم باید شرطِ بار را پاس کند. bool و زیرنوع‌های عددی پذیرفته نیستند. هدفِ انسداد، کسرِ مثبتِ کوچک‌تر از یک با مخرجِ حداکثرِ یک‌میلیون است.

جست‌وجوی ظرفیت فقط برای بارِ مثبت انجام می‌شود و نخستین نامزدِ بررسی‌شده با B کوچک‌تر یا مساویِ هدف را برمی‌گرداند. برای بارِ سه و هدفِ یک‌پنجم، ظرفیتِ چهار با احتمالِ بیست‌وهفت‌صدوسی‌ویکم کافی نیست؛ ظرفیتِ پنج با احتمالِ هشتادویک‌هفتصدوسی‌وششم شرط را پاس می‌کند. تساوی پذیرفته می‌شود و نتیجه فقط در محدودهٔ نامزدهای مجاز معنا دارد.

{
  "python": "3.14.5",
  "dependencies": "Python standard library only",
  "scope": "Original exact stationary M/M/c/c loss-model arithmetic; no real traffic, PBX or SLA",
  "assumptions": [
    "stationary independent Poisson arrivals",
    "independent exponential holding times",
    "identical single-slot servers; no waiting or retries"
  ],
  "fixture": {
    "arrivals_per_minute": "3/2",
    "mean_holding_minutes": "2",
    "offered_erlangs": "3",
    "three_channel_states": [
      "1/13",
      "3/13",
      "9/26",
      "9/26"
    ],
    "blocking_three_channels": "9/26",
    "mean_busy_three_channels": "51/26",
    "blocking_four_channels": "27/131",
    "blocking_five_channels": "81/736",
    "target": "1/5",
    "minimum_checked_capacity": 5
  },
  "finite_pairs_inside_one_oracle_group": 1701,
  "zero_load_note": "B(c=0,A=0)=1 is an algebraic convention, not an observed arrival blocking rate",
  "checks": {
    "literal_three_erlang_state_distribution": true,
    "literal_recurrence_values_zero_through_five_channels": true,
    "independent_factorial_oracle_1701_finite_pairs": true,
    "normalized_nonnegative_states_and_adjacent_balance": true,
    "mean_busy_equals_carried_load_and_total_load_conserved": true,
    "blocking_strictly_decreases_with_channels_for_positive_grid_loads": true,
    "blocking_strictly_increases_with_grid_load_for_positive_channels": true,
    "zero_load_and_zero_capacity_conventions_are_explicit": true,
    "minimum_capacity_and_inclusive_exact_threshold": true,
    "bounded_search_reports_no_solution_without_fabricated_capacity": true,
    "declared_rate_time_units_and_scale_preserve_offered_load": true,
    "one_channel_closed_form_and_maximum_boundary": true,
    "strict_input_types_ranges_and_positive_dimensioning_contract": true
  }
}

سیزده گروهِ نام‌دار واقعاً اجرا شده‌اند. ۱۷۰۱ زوجِ بار و ظرفیت در یک گروه با مرجعِ فاکتوریلی مقایسه می‌شوند؛ این‌ها ۱۷۰۱ گروهِ جدا نیستند. توازن، بقای بار، تغییرِ یکنواخت، مرزِ صفر، آستانهٔ دقیق و ردِ نوع‌های نامجاز نیز بررسی شده‌اند. سقفِ جست‌وجوی چهار برای هدفِ یک‌پنجم، None می‌دهد؛ برنامه ظرفیتِ خارج از جست‌وجو جعل نمی‌کند.

۵. چهار پرسش دربارهٔ واحد، مرز و تفسیر

پرسشِ اول: مدتِ متوسطِ ۱۲۰ ثانیه و نرخِ سه‌دوم تماس در دقیقه چه باری دارند؟ پاسخ: ابتدا ۱۲۰ ثانیه را به دو دقیقه تبدیل می‌کنیم؛ حاصل سه ارلانگ است. واردکردنِ عددِ ۱۲۰ به‌عنوانِ دقیقه، خطای واحد است؛ تابعِ ما از روی عدد، واحدِ اشتباه را تشخیص نمی‌دهد.

پرسشِ دوم: آیا بارِ سه با ظرفیتِ سه حتماً همهٔ جایگاه‌ها را پُر می‌کند؟ پاسخ: خیر؛ احتمالِ پُربودن نه‌بیست‌وششم و متوسطِ اشغال پنجاه‌ویک‌بیست‌وششم است. بارِ پیشنهادی، حالتِ قطعی نیست. محدودبودنِ سامانهٔ بی‌صف نیز با شرطِ پایداریِ یک صفِ نامحدود اشتباه گرفته نمی‌شود.

پرسشِ سوم: با بارِ صفر و ظرفیتِ صفر، عددِ یک چه معنایی دارد؟ پاسخ: مقدارِ جبریِ آغازِ رابطه است. وقتی هیچ ورودی نداریم، نسبتِ مشاهده‌شدهٔ تماس‌های مسدود به کلِ ورودها از این عدد نتیجه نمی‌شود. برای ظرفیتِ مثبت و بارِ صفر، فرمول صفر می‌دهد؛ تابعِ ظرفیت‌گذاری بارِ صفر را صریحاً رد می‌کند.

پرسشِ چهارم: آیا جوابِ پنج، توصیهٔ خریدِ پنج کانال است؟ پاسخ: خیر؛ تنها پاسخِ ورودی و هدفِ فرضیِ همین مدل است. شبیه‌سازیِ پذیرشِ بازه‌های تماس دربارهٔ زمان‌بندیِ محدود است و صفِ FCFS و انصراف انتظار را مدل می‌کند. برای سامانهٔ واقعی، اعتبارِ داده، فرض‌های ترافیک و محدودیت‌های شبکه جدا بررسی می‌شوند؛ این احتمال، تضمینِ خدمت نیست.

منابع و مطالعهٔ بیشتر

• MIT؛ بخشِ ۴٫۶، فرضِ ورودِ پواسون و محدودیتِ موجِ تماس
• MIT؛ بخشِ ۴٫۶٫۴ و معادلهٔ ۴٫۵۷، سامانهٔ بی‌صف و احتمالِ انسداد
• Python3.14.8؛ Fraction و تفاوتِ کسرِ دقیق با تبدیلِ اعشاری

بررسی منابع: ۲۸ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.