тетному розподілі для кожної пари змінних xj, Xjзадаются кінцеві позитивні пріоритети запитів сj, які беруть участь в обчисленнях у нормалізованому вигляді: (j = 1 ... m).
орієнтуюся правилами пріоритетного розподілу є
В
.
безпріорітетна розподілення
Залежно від величини дефіциту ресурсу по лівим і правим кордонів запитів має місце один з чотирьох випадків.
1. b1 + ... + bm> a, B1 + ... + Bm> A. Спочатку вирішується завдання для лівих кордонів, а потім - завдання для правих кордонів.
2.b1 + ... + bm a, B1 + ... + Bm> A. Вважаємо xj = bj (j = 1 ... m) і вирішуємо завдання для правих кордонів. p> 3.b1 + ... + bm> a, B1 + ... + Bm A. Вважаємо Xj = Bj (j = 1 ... m) і вирішуємо завдання для лівих кордонів. p> 4.b1 + ... + bm a, B1 + ... + Bm A. У цьому випадку вважаємо xj = bj, Xj = Bj (j = 1 ... m), і завдання вважається виродженої. br/>
Завдання для лівих кордонів
Потрібно знайти набір невід'ємних чіселxj (j = 1 ... m), які відповідають умовам xjbj; x1 + ... + xm = a. Розподіл проводиться пропорційно запитам. Тут алгоритм дійсно гранично прост.Еслі некоториеbj = 0, вважаємо відповідні xj = 0, після чого вважаємо їх знайденими і виключаємо з розгляду. Нехай після цього залишилося sненайденних лівих кордонів. Якщо s = 0, завдання для лівих кордонів вирішена. Якщо s = 1, вважаємо єдину Незнайдений змінну рівною a, і завдання для лівих кордонів вирішена. Інакше здійснюються такі розрахунки. p> Нехай не знайдені ліві кордони для j = 1 ... s (1
В
(j = 1 ... s).
Завдання для правих кордонів
Шукаються позитивні Xj (j = 1 ... m), що задовольняють умовам XjBj, X1 + ... + Xm = A.
Введемо безліч індексів K = {j | Bj = bj, 1jm}. Для покладемо Xj = xj. Введемо також безліч індексів I = {1, ..., m} kи покладемо. У кожній ітерації для всіх вважаємо
.
Тепер вважаємо = {}. Для всехXjсчітается знайденим і рівним Bj. Якщо ж = (пусте безліч), вважаємо = I. Далі змінюємо A і I таким чином:
, I: = I
Якщо I =, ітерації припиняються. Після закінчення ітерацій може виявитися, що A> 0 (тобто не весь ресурс розподілений). Це може статися, тільки якщо для всіх j, де Bj> bj, Xj = Bj. В іншому випадку сталася б ще одна ітерація, і залишок A пішов би на збільшення цих Xj. У такому випадку A итеративно розподіляється між тими запитами, для которихBj = bj. p> У кожній ітерації вважаємо.
Тепер вважаємо = {}. Для всіх значення Xjсчітается знайденим і рівним Bj. Якщо ж = (пусте безліч), вважаємо = K. Далі змінюємо A і Kследующім чином:
, K: = K
Якщо K =, ітерації припиняються.
Пріоритетне розподіл
Для числового відрізка [a, A] (a 0, А> 0), що задає величину распределяемого ресурсу, відрізків [bj, Bj] (bj 0, Bj> 0), які задають запити (пот...
