دوره 11، شماره 1 - ( 3-1404 )
دوره 11 شماره 1 صفحات 120-99 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Tayyebi J, Niksirat M. Minimum spanning tree interdiction problem considering follower strategy stability. mmr 2025; 11 (1) :99-120
URL: http://mmr.khu.ac.ir/article-1-3416-fa.html
URL: http://mmr.khu.ac.ir/article-1-3416-fa.html
طیبی جواد، نیک سیرت ملیحه. مسئله ممانعت از درخت پوشای کمینه با هدف ثابت نگه داشتن استراتژی پیرو. پژوهش های ریاضی. 1404; 11 (1) :99-120
جواد طیبی1 
، ملیحه نیک سیرت*2
، ملیحه نیک سیرت*2
1- دانشگاه صنعتی بیرجند
2- دانشگاه صنعتی بیرجند ،niksirat@birjandut.ac.ir
2- دانشگاه صنعتی بیرجند ،
چکیده: (27 مشاهده)
این مقاله یک مسئله ممانعت در بهینه‌سازی ترکیبیاتی، به نام ممانعت از درخت پوشای کمینه (MSTI) را بررسی میکند. از دیدگاه نظریه بازیها، این مسئله شامل دو بازیکن با اهداف متفاوت است. بازیکن اول که پیرو نامیده میشود به دنبال یافتن یک درخت پوشای کمینه است. از طرف دیگر، بازیکن دیگر که رهبر نامیده میشود، با در نظر گرفتن محدویتهای بودجه و کران، هزینه کمانها را افزایش میدهد که مقدار تابع هدف پیرو را تا حد ممکن بدتر نماید؛ با این امید که پیرو دست از فعالیت بیشتر بردارد. در این مقاله حالت خاصی از مسئله در نظر گرفته شده است که در آن درخت بهینه اولیه حتی با تغییر وزنها بهینه باقی می‌ماند. این فرض تضمین میکند که رهبر میتواند مطمئن باشد که پیرو انگیزهای برای تغییر استراتژی خود ندارد، زیرا استراتژی بهتری برای وی در دسترس نیست.
به منظور حل کارای این مسئله با هزینه‌های خطی یک مدل جدید پیشنهاد می‌گردد که شامل تعداد زیادی محدودیت است. به همین دلیل یک الگوریتم حل بر مبنای روش تولید سطر (محدودیت) برای مسئله پیشنهاد میشود. سپس یک مثال عددی و نتایج محاسباتی بر نمونه‌های تصادفی برای ارزیابی عملکرد این روش ارائه می‌گردد. نتایج محاسباتی نشان میدهد که الگوریتم ارایه شده در تعداد تکرار متناهی و در زمان اجرای منطقی جواب بهینه مسئله را محاسبه میکند.
به منظور حل کارای این مسئله با هزینه‌های خطی یک مدل جدید پیشنهاد می‌گردد که شامل تعداد زیادی محدودیت است. به همین دلیل یک الگوریتم حل بر مبنای روش تولید سطر (محدودیت) برای مسئله پیشنهاد میشود. سپس یک مثال عددی و نتایج محاسباتی بر نمونه‌های تصادفی برای ارزیابی عملکرد این روش ارائه می‌گردد. نتایج محاسباتی نشان میدهد که الگوریتم ارایه شده در تعداد تکرار متناهی و در زمان اجرای منطقی جواب بهینه مسئله را محاسبه میکند.
نوع مطالعه: علمی پژوهشی کاربردی |
موضوع مقاله:
جریان شبکه- تحقیق عملکرد
دریافت: 1403/6/6 | ویرایش نهایی: 1404/7/14 | پذیرش: 1404/4/18 | انتشار: 1404/3/10 | انتشار الکترونیک: 1404/3/10
دریافت: 1403/6/6 | ویرایش نهایی: 1404/7/14 | پذیرش: 1404/4/18 | انتشار: 1404/3/10 | انتشار الکترونیک: 1404/3/10
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
