РОЗВ’ЯЗУВАННЯ ЛІНІЙНОЇ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ НА ПОЛІРОЗМІЩЕННЯХ ПРИ СТАЛОСТІ СУМ КООРДИНАТ У РОЗМІЩЕННЯХ

Анотація

У статті розглядається одна із задач оптимізації, а саме: лінійна умовна повністю комбінаторна задача евклідової оптимізації на полірозміщеннях, у якій сума координат у розміщеннях константна. Ця задача полягає в мінімізації лінійної цільової функції за лінійних обмежень, які виражають умову, що ті координати допустимої точки, які входять в одне розміщення полірозміщення, в сумі дорівнюють сталій, яку можна вважати одиницею. Комбінаторним обмеженням цієї задачі є те, що допустима точка є полірозміщенням. Для розв’язування задачі запропоновано та обґрунтовано метод гілок та меж. Для методу висвітлені правила галуження допустимих підмножин, оцінювання підмножин і відсікання. У роботі запропоновано правило оцінювання допустимих множин та доведено теорему, яка встановлює оцінку допустимої підмножини. Принцип оцінювання, який реалізовано в теоремі, полягає в тому, що в якості оцінки беруть суму двох доданків, один з яких є сумою тих елементів цільової функції, які відповідають визначеним у допустимій множині, що оцінюється, а другий – є мінімумом на комбінаторній множині полірозміщень, яка утворюється спеціальним чином, лінійної цільової функції, що є тією частиною вихідної цільової функції, в яку входять невизначені в допустимій множині, що оцінюється, змінні. Доведені деякі властивості оцінок, а саме: 1) для введеного способу оцінювання та галуження допустимих підмножин оцінка наступної підмножини на гілці дерева галуження від кореня до листа буде не меншого від оцінки попередньої підмножини; 2) на одному рівні глибини від кореня дерева галуження оцінки допустимих підмножин, що є підмножинами однієї і тієї ж допустимої підмножини, при русі від верхніх гілок до нижніх гілок підмножини розташовані нижче підмножини мають більші оцінки. У статті наведено ілюстративний приклад, який поліпшує сприйняття матеріалу.