Індекс рубрикатора НБУВ: В173.112.1 + В173.14

Рубрики:

Комбінаторне програмування

Багатокритеріальна оптимізація

Шифр НБУВ: ДС50398 Пошук видання у каталогах НБУВ 

Запропоновано алгоритми, які дозволяють підвищити точність розв'язання задачі 0,1-рюкзак, і паралельні обчислювальні структури для їхньої реалізації в масштабі реального часу.

У поданій статті запропонована нова методика статистичного дослідження ПДС-алгоритмів для важковирішуваних комбінаторних задач, на підставі якої визначається статистична значимість поліноміальних підкласів, що виділяються поліноміальною складовою ПДС-алгоритмів, та галузь їх ефективного застосування. Визначаються статистичні параметри, що дозволяють знаходити умови застосування ПДС-алгоритму, який був побудований для однієї важковирішуваної комбінаторної задачі, як ефективний засіб розв'язання інших задач з класу NP.

Запропоновано модель для аналізу помилок синхронізації на підставі межових умов задачі математичного програмування. Описано алгоритми та умови побудови моделі, лінійні критерії оптимізації, приклади розрахунку.

Індекс рубрикатора НБУВ: В173.112

Рубрики:

Дискретне програмування

Шифр НБУВ: Ж14024 Пошук видання у каталогах НБУВ 

Запропоновано новий метод генерування комбінаторних конфігурацій різних типів (перестановок, розбиття множини на підмножини, розбиття числа), який базується на властивості періодичності цього процесу. Застосування методу показано на прикладі упорядкування перестановок та розбиття числа.

Работа посвящена актуальной проблеме нахождения и обоснования полиномиальной оптимизации, которая является труднорешаемой. Выявлен нетривиальный полиномиально разрешимый класс двукритериальной задачи о сочетаниях. Осуществлено конструктивное доказательство теоремы, т.е. построен соответствующий алгоритм, который гарантирует нахождение искомого множества альтернатив с полиномиальной вычислительной сложностью.

Розглядається новий клас задач цілочислового програмування з неоднозначно заданими даними. Для їх розв'язування пропонується та досліджується декомпозиційний метод.

Розглянуто метод побудови точних і наближених рішень задачі (0,1)-рюкзак на основі рангового підходу та оптимізації за напрямком у дискретному просторі станів. Показано, що цей метод дозволяє будувати точні рішення задачі (0,1)-рюкзак протягом поліноміального часу з довірчою вірогідністю 0,95.

Розглянуто задачу визначення ряду домінантності для заданої множини властивостей у двох аспектах: встановлення допустимої множини розв'язків (рядів домінантності) та визначення оптимального з них. Формально задачі представлені як розмиті оптимізаційні задачі на просторі виборок. Розглянуто один клас комбінаторних оптимізаційних задач для формалізації, розв'язку і дослідження яких застосовуються поняття теорії нечітких множин Заде.

Дисертацію присвячено побудуванню умов оптимальності у рамках схеми Дубовицького - Мілютина, а також співвідношень та оцінок розриву двоїстості для неперервних задач оптимального розбиття множин. Для неперервної задачі оптимального розбиття множини на підмножини з заданими координатами їх центрів з обмеженнями у формі рівностей та нерівностей отримано необхідні та достатні умови оптимальності у диференційній та двоїстій формах, а також у термінах сідлової точки, доведено сильну теорему двоїстості. Для неперервної задачі оптимального розбиття множини на підмножини з невідомими координатами їх центрів з обмеженнями у формі рівностей та нерівностей отримано необхідні диференційні та субдиференційні умови оптимальності, досліджено деякі умови виконання сильної теореми двоїстості, доведено існування розв'язків прямої та двоїстої задач, а також побудовано декілька оцінок розриву двоїстості. Проведено ряд узагальнень викладених результатів, зокрема, для динамічних задач розбиття.

Узагальнено класичну задачу про призначення. Для розв'язання цієї нової комбінаторної оптимізаційної задачі запропоновано оригінальну модифікацію угорського методу.

Дисертацію присвячено дослідженню потоків у мережах для узагальненого закону Кірхгофа. Розглядається випадок, в якому різниця між сумарним потоком, котрий витікає в вершину, і умарним потоком котрий стікає з вершини, належить до деякого відрізку. Дано незалежне обгрунтування методу виключення невідомих. Побудовані методи знаходження припущених стаціонарних та динамічних потоків, котрі базуються на алгоритмах виключення невідомих.

Досліджуються області визначення задач евклідової комбінаторної оптимізації на переставних множинах, зокрема, розглядаються системи обмежень загального переставного, загального поліпереставного многогранників і многогранника - області допустимих розв'язків задачі з лінійною функцією цілі, до якої зводиться задача з дробово-лінійною функцією цілі на загальній множині переставлень. Встановлено незвідні системи лінійних обмежень зазначених многогранників та викладено деякі їх нові властивості. а також новий метод знаходження точного розв'язку задачі мінімізації зваженої довжини зв'язучої сітки при лінійному розташуванні прямокутних елементів.

На основі аналізу встановлено, що класичний метод критичного шляху не є адекватним, коли оцінки тривалості робіт виражені нечіткими величинами. Метод нечіткого критичного шляху сформовано на основі розрахунку нечітких множин критичних робіт та шляхів виявлення нечітких резервів та аналізу ризикозмісту проекту.

Розроблено загальний підхід для отримання ефективно обчислювальних оцінок номіналів надійності задач покриття для гіперграфів. Він показаний на прикладі канонічних гіперграфів, що використовуються для оцінки надійності надійних задач покриття.

Індекс рубрикатора НБУВ: В173.112

Рубрики:

Дискретне програмування

Шифр НБУВ: Ж22412/а Пошук видання у каталогах НБУВ 

Досліджено опуклі оболонки областей визначення оптимізаційних задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Визначено незвідні системи лінійних обмежень загального переставного і загального поліпереставного багатогранників та їх нові властивості. Одержано нові властивості переставного багатогранника. Викладено новий метод точного розв'язування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів, розроблено алгоритм його реалізації на ПЕОМ.

Отримано критерій стійкості векторної цілочисельної лінійної задачі лексикографічної оптимізації. Запропоновано метод регуляризації, що дозволяє перейти від можливо нестійкої вихідної задачі до серії збурених стійких еквівалентних задач.

  Скачати повний текст