دوره 11، شماره 1 - ( 3-1404 )                   دوره 11 شماره 1 صفحات 120-99 | برگشت به فهرست نسخه ها

XML English Abstract Print

مسئله ممانعت از درخت پوشای کمینه با هدف ثابت نگه داشتن استراتژی پیرو
جواد طیبی1 ، ملیحه نیک سیرت*2
1- دانشگاه صنعتی بیرجند
2- دانشگاه صنعتی بیرجند ، niksirat@birjandut.ac.ir
چکیده:   (201 مشاهده)
این مقاله یک مسئله ممانعت در بهینه‌سازی ترکیبیاتی، به نام ممانعت از درخت پوشای کمینه (MSTI) را بررسی می‌کند. از دیدگاه نظریه بازی­ها، این مسئله شامل دو بازیکن با اهداف متفاوت است. بازیکن اول که پیرو نامیده می­شود به دنبال یافتن یک درخت پوشای کمینه است.  از طرف دیگر، بازیکن دیگر که رهبر نامیده می­شود، با در نظر گرفتن محدویت­های بودجه و کران، هزینه کمان­ها را افزایش می­دهد که مقدار تابع هدف پیرو را تا حد ممکن بدتر نماید؛ با این امید که پیرو دست از فعالیت بیشتر بردارد. در این مقاله حالت خاصی از مسئله در نظر گرفته شده است که در آن درخت بهینه اولیه حتی با تغییر وزن­ها بهینه باقی می‌ماند. این فرض تضمین می­کند که رهبر می­تواند مطمئن باشد که پیرو انگیزه­ای برای تغییر استراتژی خود ندارد، زیرا استراتژی بهتری برای وی در دسترس نیست.
به منظور حل کارای این مسئله با هزینه­‌های خطی یک مدل جدید پیشنهاد می‌گردد که شامل تعداد زیادی محدودیت است. به همین دلیل یک الگوریتم حل بر مبنای روش تولید سطر (محدودیت) برای مسئله پیشنهاد می‌شود. سپس یک مثال عددی و نتایج محاسباتی بر نمونه‌های تصادفی برای ارزیابی عملکرد این روش ارائه می‌گردد. نتایج محاسباتی نشان می‌دهد که الگوریتم ارایه شده در تعداد تکرار متناهی و در زمان اجرای منطقی جواب بهینه مسئله را محاسبه می‌کند.
 
واژه‌های کلیدی: درخت پوشای کمینه، مسئله ممانعت، استراتژی ثابت، تابع هزینه خطی.
متن کامل [PDF 974 kb]   (160 دریافت)    
نوع مطالعه: علمی پژوهشی کاربردی | موضوع مقاله: جریان شبکه- تحقیق عملکرد
دریافت: 1403/6/6 | ویرایش نهایی: 1404/7/14 | پذیرش: 1404/4/18 | انتشار: 1404/3/10 | انتشار الکترونیک: 1404/3/10
بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.