2.4. Задача розподілу потоків

Ця задача відноситься до задач другого і четвертого типів, постановка яких наведена в розділі 3.1. В цьому розділі розглядається задача розподілу потоків, в якій вважається, що пропускні спроможності задані, а потоки потрібно розподілити так, щоб мінімізувати середнє значення часу перебування в мережі – задача другого типу.

В цьому випадку може виникнути ситуація, коли потік по маршруту перевищує пропускну спроможність каналу, тобто . Ця ситуація вимагає розщеплення одного потоку по кількох каналах.

Розв’язок цієї задачі базується на теоремі Форда-Фалкерсона та угорському алгоритмі.

З рівності (3.4) маємо

Звідси видно, що

Отже, можна зробити висновки, що Т – опукла функція потоків і має мінімум.

Не вдаючись в подробиці виводу (тих хто цікавиться відсилаємо до [28, 29]) сформулюємо алгоритм розв’язку задачі методом відхилення потоку.

КРОК 1. Покласти

КРОК 2. Для кожного і = 1, 2, ..., М знайти довжину

КРОК 3. Знайти – добав очний вартісний коефіцієнт для цього потоку

.

КРОК 4. Розв’язати задачу відшукання потоків по найкоротшому маршруту (розділ 2.1.). Позначимо вектор потоків

.

КРОК 5. Знайти – добавлений вартісний коефіцієнт для потоку по найкоротшому маршруту

.

КРОК 6. (Правило зупинки). Якщо , де – допуск, то зупинка. Якщо ні, то перехід на крок 7.

КРОК 7. Знайти таке значення , , для якого потік мінімізує Т. Це можна зробити любим методом пошуку, наприклад методом Фібоначчі.

КРОК 8. Покласти

.

КРОК 9. Покласти . Перейти до кроку 2.

Тих, хто більш детально цікавиться алгоритмами відшукання оптимального розподілу потоків, відсилаємо до / /.

Система масового обслуговування М/М/1

Ця СМО являє собою одноканальну (з одним приладом) систему масового обслуговування з необмеженою чергою. Процедура обслуговування – безпріоритетна FIFO. На вхід у систему поступає пуасонівський потік клієнтів з інтенсивністю Час обслуговування клієнтів є незалежними випадковими величинами, розподіленими по експоненційному закону із середнім значенням 1/ . Рівняння Чепмена-Колмогорова для такої СМО мають вигляд

де імовірність того, що в довільний момент часу t в СМО буде рівно N клієнтів.

Умовно стаціонарного режиму роботи СМО буде

де – завантаження (коефіцієнт використання) системи.

В стаціонарному режимі і розподіл ймовірностей має вигляд

Використовуючи властивості математичних очікувань знайдемо числові характеристики систем М/М/1:

• середня кількість клієнтів у системі

• середня кількість у черзі

• середній час перебування клієнта в СМО

• середній час перебування клієнта в черзі

• формули Літла

Додаток 2

Метод невизначених множників Лагранжа

Метод невизначених множників Лагранжа є основним методом розв’язку задач умовної оптимізації, коли цільова функція і обмеження не є лінійними функціями. Сутність методу полягає в наступному.

Припустимо, нам потрібно знайти екстремум функції n змінних . На цю функцію накладаються m обмежень, виду співпадає з екстремумом функції Лагранжа

(д.1)

В самому ділі, оскільки квадратна дужка в (д. 1) дорівнює нулю, то функція фактично не змінилась. Але тепер кількість змінних збільшилась до n+m, n – кількість змінних в задачі, m – кількість обмежень, які введені у функцію Лагранжа за рахунок m множників Лагранжа , значення яких нам невідомо.

Розв’язком задачі пошуку екстремуму (д. 1) буде розв’язок системи