Спосіб розподілу та кодування інформаційного ресурсу в мультисервісних мережах

Реферат: Спосіб розподілу та кодування інформаційного ресурсу в мультисервісних мережах, вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. UA 92960 U (12) UA 92960 U UA 92960 U 5 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відомий "Спосіб послідовного призначення одиниць для наближеного рішення задачі про одномірний ранець" [1], який вирішує задачу цілочисельного лінійного програмування з булевими змінними:  f (x)  n  c j x j  max , (1) j 1 при виконанні умов: n  aij x j  b1 , (2) x j  0,1 i  1 j  (1, n) , , , (3) j 1 a1j  0, cj  0 . (4) В даному способі як початковий розглядається нульовий вектор, в якому змінним присвоюються одиничні значення за умови, що при побудові допустимого цілочисельного 10 рішення призначаються одиничні значення у відповідності з послідовністю z0  j1   j2  ...   jn , починаючи з найбільшого значення. Якщо для деякого  jk таке призначення виконати неможливо, тоді z0  0 і переходять до номеру jk 1 . Процес завершується після jk перегляду всіх змінних, або при порушенні умови (2). Призначення одиничних значень виконується у відповідності з послідовністю c j1  c j2  ...  c jn . 15 20 Недоліком відомого способу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибраним як прототип, є "Способ решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода" [2], який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та полягає у тому, що з вершини s графа ΔD будується множина шляхів mr 1, j  (1, n) першого рангу r, що задовольняє sj  *r  властивості, і в множинах mr 1 визначаються шляхи максимальної довжини   за вагою   sj  sj    функціонала cj. Для кожної вершини j визначається вага  j за правилом:  j  c j 1  c j  2  ...  c n ,  n  0; j  (1, n  1) .(5)   Виключаються шляхи r , p  (r, n) у множині mr поточного рангу r, довжини якої dc (r ) sj sp sp задовольняють нерівності:     * r   dc (r )   p  max dc  sp   sp  , (6)      cj де  p  c p 1  c p  2  ...  c n та для вершини j  n вага  j - дорівнює нулю;  25 dc (r ) - довжина шляху від вершини s до вершини p рангу r за вагою функціоналу. sp Формується множина шляхів mr r 1 , p  (1 n) наступного рангу, що задовольняє властивості , sp (5), на базі множини шляхів mr попереднього рангу на основі рекурентного співвідношення: sj   r r 1  max r  ( j, p) p  r  1, n j  r, n j  p , (7) sp sj c  j де r  ( j, p) - шлях з вершини s графа ΔD у вершину p, що проходить через проміжну sj 30 вершину j і який одержується за рахунок приєднання до шляху r ребра ( j, p) , якщо таке sj з'єднання не суперечить правилу відсікання неперспективних варіантів рішень. 1 UA 92960 U 5 10 15 20 25 30 * r  r  1 У визначених множинах mr r 1 виділяються щонайдовші шляхи  . sp   sp  Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з меншим значенням довжини за вагою обмежень a1j. Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-7). Недоліком способу-прототипу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити "Спосіб динамічного кодування та захисту інформаційного ресурсу в інфокомунікаційних системах", який дозволить зменшити відносну похибку алгоритму до 3 %. Поставлена задача вирішується за рахунок того, що у спосіб-прототип додатково введено правило відсікання неперспективних варіантів рішень на основі вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по убуванню значень коефіцієнтів в функціоналі. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком до 3 %. На фіг. 1 представлено граф ΔD. На фіг. 2 наведено приклад рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Запропонований "Спосіб динамічного кодування та захисту інформаційного ресурсу в інфокомунікаційних системах" ґрунтується на правилі відсікання неперспективних варіантів рішень на основі вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортуванні даних по убуванню значень коефіцієнтів в функціоналі. Суть способу полягає у наступному. Виконується сортування даних по убуванню значень коефіцієнтів в функціоналі: c1 c 2 c   ...  n (8) 1  2 n . З вершини s графа ΔD будується множина шляхів 35 mr 1 , j  (1, n) першого рангу r, що sj  *r  задовольняє властивості, і визначаються в множинах mr 1 шляхи максимальної довжини   sj    sj    за вагою функціонала cj. Для кожної вершини j визначається вага  j за правилом (5).   Виключаються шляхи r , p  (r, n) у множині mr поточного рангу r, довжини якої dc (r ) sj sp sp задовольняють нерівності (6). Формується множина шляхів mr r 1 , p  (1 n) наступного рангу, що задовольняє властивості , sp (5), на базі множини шляхів 40 mr попереднього рангу на основі правила відсікання sj неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком:     r r 1  max r  ( j, p) ; sj  sp cj L3 :  r r 1 p  r  1 n j  r, n j  p .(9) ,  sp  min r  ( j, p) .  sj j  2 UA 92960 U У визначених множинах 5 10 15 mr r 1 sp виділяються щонайдовші шляхи * r  r  1   . Якщо   sp  визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з найбільшим значенням довжини за вагою функціонала c1j, та шлях з меншим значенням довжини за вагою обмежень a1j. Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу, інакше збільшується r на 1 і виконується обчислення у відповідності до формул (5-8). Джерела інформації: 1. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - Изд. 2-е, испр. - М.: ФИЗМАТЛИТ, 2003. -240 с. 2. Третьяк В.Ф., Голубничий Д.Ю., Огурцов В.В. Метод решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода //Системи обробки інформації. Збірник наукових прань, 2009. - випуск 4 (78). - С. 152-155. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 Спосіб розподілу та кодування інформаційного ресурсу в мультисервісних мережах, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком, який відрізняється тим, що введено правило відсікання неперспективних варіантів рішень по вибору максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. 3 UA 92960 U 4 UA 92960 U Комп’ютерна верстка Л. Литвиненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5