е бути сформовано або до початку розв'язання задачі, якщо з апріорних міркувань відомо хоча б одне її допустиме рішення, або в процесі пошуку, як тільки таке рішення знайдено. Це обмеження формується на основі запису цільової функції та її значення для кращого знайденого до поточного кроку перебору допустимого рішення Xд:
. (3.31)
Знак строгої нерівності застосовується тоді, коли хочуть знайти лише одне (перше-ліпше) з безлічі можливих оптимальних рішень. Інакше застосовують знак "ВЈ". p> Для скорочення обсягу обчислень, перш ніж перевіряти приналежність деякого рішення допустимої області, перевіряють виконання фільтруючого обмеження. Якщо воно не виконується, то переходять до розгляду наступного рішення. Обгрунтування такого правила полягає в тому, що після знаходження допустимого рішення надалі з точки зору вирішення оптимізаційної задачі має сенс розглядати лише такі x, для яких значення цільової функції менше z (Xд). p> Щоразу при знаходженні кращого допустимого рішення права частина фільтруючого обмеження коригується (зменшується). При цьому фільтруюче обмеження стає більш жорстким. p> Ще однією можливістю, яка в деяких завданнях може забезпечити додаткове скорочення обсягу обчислень, є використання упорядкування змінних по швидкості зміни відповідно до величинами коефіцієнтів цільової функції: сама швидкозмінних мінлива - та, якій відповідає найменше значення коефіцієнта цільової функції. При такому упорядкуванні, як правило, раніше будуть розглянуті рішення з меншими значеннями цільової функції. Якщо серед них знайдеться допустиме, то в більш ранній момент буде введено більш жорстке фільтруюче обмеження, що і має призвести до скорочення обсягу обчислень. p> І ще одна можливість. Перевірка приналежності деякого рішення області допустимих рішень здійснюється послідовно по кожному обмеженню. Як тільки знайдено не виконують обмежене, подальший аналіз рішення закінчується і здійснюється перехід до наступного. На цій основі може бути реалізовано правило впорядкування обмежень задачі "по жорсткості": у першу чергу доцільно перевіряти більш жорсткі обмеження. Більш жорсткими є ті обмеження, які для більшого числа можливих рішень не виконуються. Інформація про жорсткість обмежень може бути отримана або на основі апріорного аналізу оптимізаційної задачі, або може бути реалізована адаптивна процедура впорядкування і переупорядковування обмежень безпосередньо в процесі перебору з реалізованої частотам їх виконання. За аналогією з фільтруючим обмеженням застосування цього правила може дати додаткове скорочення обсягу обчислень. p align="justify"> У лінійних задачах можливим також є проведення аналізу значень окремих коефіцієнтів цільової функції, обмежень і напрямки зміни при переборі відповідних оптимізаційних змінних з метою пропуску деяких послідовностей точок, серед яких або не можна знайти допустимих рішень, або рішень, кращих за значенням цільової функції.
Алгоритм мЛНП
...
