реби), і набору позитивних чисел {c1, ..., cm}, які задають пріоритети запитів, знайти відрізки [xj, Xj] (xj 0, Xj> 0, j = 1 ... m), відповідні шуканого розподілу.
Залежно від величини дефіциту ресурсу по лівим і правим кордонів запитів має місце один з чотирьох випадків.
b1 + ... + bm> a, B1 + ... + Bm> A. Спочатку вирішується завдання для лівих кордонів, а потім завдання для правих кордонів. p> b1 + ... + bma, B1 + ... + Bm> A. Вважаємо xj = bj (j = 1 ... m), потім вирішуємо завдання для правих кордонів. p> b1 + ... + bm> a, B1 + ... + Bm A. Вважаємо Xj = Bj (j = 1 ... m), потім вирішуємо завдання для лівих кордонів. p> b1 + ... + bma, B1 + ... + Bm A. У цьому випадку вважаємо xj = bj, Xj = Bj (j = 1 ... m), і завдання вважається виродженої. br/>
Завдання для лівих кордонів
Потрібно знайти набір позитивних чисел xj (j = 1 ... m), які відповідають умовам xjbj, x1 + ... + xm = a.
Ліві кордону обчислюються итеративно. Спочатку безліч I індексів Незнайдений xj покладається рівним {1, ..., m}. Далі в кожній ітерації присвоюємо ще знайденим Xj значення pjа. Потім вважаємо = {j I | xj bj} =. Для всіх j xj вважається знайденим і рівним bj. Якщо ж = (порожньо), вважаємо = I. Далі змінюємо I і a: I: = I , a: = a-. Якщо I =, ітерації прекращаются.В іншому випадку перераховуємо пріоритети і продовжуємо ітерації. p> Завдання для правих кордонів
Потрібно знайти набір позитивних чисел Xj (j = 1 ... m), які відповідають умовам XjBj, X1 + ... + Xm = A.
Схема обчислень аналогічна схемі для лівих кордонів. Значення A перед початком обчислень приймається рівним A - (x1 + ... + xm). Безліч I покладається рівним {1, ..., m}. У кожній ітерації присвоюємо ще знайденим Xj значення xj + pjА. Потім вважаємо = {j I | Xj Bj}. Для всіх j Xj вважається знайденим і рівним Bj. Якщо ж = (порожньо), вважаємо = I. Далі I: = I ,. Якщо I =, ітерації припиняються, інакше перераховуємо пріоритети і продовжуємо ітерації. br/>
Програмна реалізація
У ході виконання курсового проекту була задіяна програмна реалізація рішення задачі одноресурсного розподілу методом інтервального аналізу створена Ткаченко Микитою за алгоритмом, створеному д.т.н., професором Ільїним Володимиром Дмитровичем та к.т.н. Ільїним Олександром Володимировичем. Дана програмна реалізація створена в середовищі VisulStudio 2010 як додаток WindowsForms і написана на мові C #. Програма дозволяє вирішувати як завдання безпріорітетна розподілу, так і завдання пріоритетного розподілу. Користувач має можливість введення практично будь-якої структури ієрархії і будь-якого типу числових даних. Після вибору типу задачі одноресурсного розподілу і введення структури ієрархії, на екрані відображається таблиця запитів відповідної структури. При цьому для кожної зі статей таблиці користувач може ввести власну назву. По натискання кнопки В«ОбчислитиВ» з'являється таб...
