Спосіб оптимального планування розподілом задач в системі підтримки прийняття рішень

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