Складання оптимального розкладу за наявності заданих обмежень на основі теорії графів

Запропоновано новий алгоритм розв’язання прикладної задачі складання розкладу приймання лікувальних процедур пацієнтами санаторію як розширеної математичної задачі пошуку максимального паросполучення у дводольному графі зі зникаючими дугами. На відміну від відомих, алго- ритм дає змогу врахувати обмеження сумісності лікувальних процедур і має меншу обчислювальну складність порівняно з методом повного перебору за рахунок скорочення кількості паросполучень, що аналізуються. Алгоритм гарантує знаходження розв’язку задачі складання розкладу приймання процедур пацієнтами санаторію, якщо він існує. Проведено порівняльний обчислювальний експеримент на серії випадкових умов задачі, отриманих від реальних пацієнтів санаторію за часовою вибіркою. Він засвідчив, що запропонований оптимальний алгоритм забезпечує зменшення часу складання розкладу від 4,48 до 8,87 разу порівняно з методом повного перебору і що час складання розкладу прямо пропорційно залежить від кількості вершин дводольного графа.

Рік видання: 
2012
Номер: 
6
УДК: 
519.161
С. 46—53. Іл. 3. Табл.. 3. Бібліогр.: 8 назв.
Література: 

1. Данильченко О.М., Данильченко А.О., Ібрагім С.А. Розв’язання одного класу задач складання розкладів генетичними алгоритмами на кластерних системах // Вісник ЖІТІ, 2004. – № 4. – С. 130–135.
2. Панішев А.В., Данильченко А.М., Данильченко А.А. Задача про паросполучення зі “зникаючими” дугами” // Моделювання та інформ. технол.: Зб. наук. пр. – К., 2012 – С. 75–81.
3. Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд-во МГУ, 1985. – 312 с.
4. Ope О. Теория графов. – М.: Наука, Гл. ред. физ.- мат. лит., 1980. – 336 с.
5. Майника Э. Алгоритмы оптимизации в сетях и графах: Пер. с англ. – М.: Мир, 1981. – 324 с.
6. Харари Ф. Теория графов / Пер. с англ. и предисл. В.П. Козырева; под ред. Г.П. Гаврилова. – 2-е изд. – М.: Едиториал УРСС, 2003. – 296 с.
7. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. – 512 с.
8. Данильченко О.М., Данильченко А.О. Інтелектуальний аналіз даних (Data Mining): Навч. посібник. – Жито- мир: ЖДТУ, 2009. – 406 с.

Текст статтіРозмір
2012-6-6.pdf210.58 КБ