Пошук академічних текстів

Інформація × Реєстраційний номер 2124U009197, Матеріали видань та локальних репозитаріїв Категорія Опубліковано, Стаття Назва роботи ІННОВАЦІЙНИЙ ВДОСКОНАЛЕНИЙ МЕТОД НАБЛИЖЕНОГО РІШЕННЯ ДЛЯ ЗАДАЧІ ЦІЛОЧИСЕЛЬНОГО РАНЦЯ, СТИСНЕННЯ ПОМИЛОК ТА ОБЧИСЛЮВАЛЬНІ ЕКСПЕРИМЕНТИ Автор Мамедов К. Ш.Ніязова Р. Р.Mamedov K. Sh.Niyazova R. R. Дата публікації 26-12-2024 Постачальник інформації Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") Першоджерело https://ric.zp.edu.ua/article/view/315998 Видання National University "Zaporizhzhia Polytechnic" Опис Актуальність. Математичні моделі багатьох задач оптимізації, що зустрічаються в економіці та техніці, розглядаються у формі задачі про цілочисельний рюкзак. Оскільки ця задача належить до класу «NP-повних», тобто «важко розв’язуваних», кількість операцій, необхідних відомим методам для знаходження її оптимального розв’язку, експоненціальна. Це не дозволяє вирішувати масштабні завдання в режимі реального часу. Тому розроблено різноманітні та швидкопрацюючі методи наближеного розв’язання цієї задачі. Однак відомо, що наближене рішення, отримане цими методами, у більшості випадків може суттєво відрізнятися від оптимального. Тому після прийняття будь-якого наближеного рішення за вихідну точку виникає потреба розробити методи його подальшого вдосконалення. Розробка таких методів має як теоретичне, так і велике практичне значення. Мета роботи. Основна мета вирішення цього питання полягає в наступному. Основна мета виконання даної роботи полягає в тому, щоб будь-яким відомим методом спочатку знайти вихідний наближений розв’язок задачі, а потім розробити алгоритм для послідовного подальшого вдосконалення цього розв’язку. Для цього необхідно визначити набір чисел, якими можуть відрізнятися координати оптимального і знайденого наближеного розв’язку. Після цього слід побудувати нові розв’язки шляхом присвоєння можливих значень невідомим, що відповідають числам цього набору, і вибрати найкраще з цих розв’язків. Але алгоритм побудови такого рішення повинен бути простим, вимагати невеликої кількості операцій, не викликати труднощів з точки зору програмування, бути новим і застосовним до практичних завдань. Метод. Суть запропонованого способу полягає в наступному. Спочатку за відомим правилом знаходять початковий наближений розв’язок задачі, що розглядається, і відповідне йому значення цільової функції. Після цього оптимальний розв’язок задачі легко знаходить відомим методом без урахування умови цілості невідомих. Очевидно, що цей розв’язок може приймати не більше одного дробового значення координати. Передбачається, що координати оптимального розв’язку цілочисельної задачі про ранець і початкового наближеного розв’язку можуть відрізнятися навколо певної дробової координати оптимального розв’язку неперервної задачі. Потім знайдено мінімальну кількість ненульових координат і нульових координат в оптимальному розв’язку. Для цього доведено відповідні теореми. Передбачається, що різні координати оптимального розв’язку та початкового наближеного розв’язку знаходяться між цими мінімальними числами. Таким чином, найкраще рішення можна вибрати шляхом послідовної зміни координат між цими мінімальними числами один за одним. Результати. Із застосуванням запропонованого методу були проведені численні розрахункові експерименти. Висока якість цього методу ще раз підтверджена експериментально. Висновки. Запропонований метод є новим, простим за своєю суттю, легким для програмування та має важливе практичне значення. Таким чином, ми називаємо це рішення інноваційним покращеним наближеним рішенням. Додано в НРАТ 2026-02-15 Закрити