کنفرانس مهندسی برق ایران

صفحه اصلی / سی و یکمین کنفرانس بین المللی مهندسی برق

بهره‌گیری از رویکرد برنامه‌ریزی ریاضیاتی برای حل مسئله‌ی مجموعه رأس بازخورد، تحت شرط مستقل بودن یا همبندی

نویسندگان :

فاطمه سلطانی دزکی¹ حسین فلسفین²

1- دانشگاه صنعتی اصفهان 2- دانشگاه صنعتی اصفهان

کلمات کلیدی :

برنامه‌ریزی خطی،مسئله‌ مجموعه رأس بازخورد کمینه،مسئله‌ مجموعه رأس بازخورد مستقل،مسئله‌ مجموعه رأس بازخورد همبند

چکیده :

مسئله‌ی مجموعه رأس بازخورد کمینه، یک مسئله‌ی NP-سخت است. کاربردهای فراوانی برای این مسئله در دنیای واقعی وجود دارد. گونه‌های مختلفی از مسئله مجموعه رأس بازخورد کمینه وجود دارد. مجموعه رأس بازخورد مستقل و مجموعه رأس بازخورد همبند از گونه‌های این مسئله می‌باشد. برای حل مسئله مجموعه رأس بازخورد، رویکرد‌های دقیق مختلفی ارائه شده است اما برای گونه‌های مجموعه رأس بازخورد مستقل و مجموعه رأس بازخورد همبند، تا آنجا که اطلاع داریم، تاکنون رویکرد‌ی دقیق ارائه نشده است. به همین دلیل، ما در این مقاله با تغییر دو مدل موجود برای مسئله کلاسیک مجموعه رأس بازخورد، مدل‌هایی فشرده و دقیق برای مسئله مجموعه رأس بازخورد مستقل و همبند ارائه می‌دهیم. برای به دست آوردن جواب‌های دقیق، از رویکرد برنامه‌ریزی خطی عدد صحیح، استفاده کرده‌ایم. با استفاده از نتایج حاصل از شبیه‌سازی، دو مدل ارائه‌شده برای مجموعه رأس بازخورد مستقل را مورد مقایسه قرار می‌دهیم.