پژوهش های ریاضی، جلد ۱۱، شماره ۱، صفحات ۹۹-۱۲۰
عنوان فارسی مسئله ممانعت از درخت پوشای کمینه با هدف ثابت نگه داشتن استراتژی پیرو
چکیده فارسی مقاله این مقاله یک مسئله ممانعت در بهینه‌سازی ترکیبیاتی، به نام ممانعت از درخت پوشای کمینه (MSTI) را بررسی می‌کند. از دیدگاه نظریه بازی­ها، این مسئله شامل دو بازیکن با اهداف متفاوت است. بازیکن اول که پیرو نامیده می­شود به دنبال یافتن یک درخت پوشای کمینه است.  از طرف دیگر، بازیکن دیگر که رهبر نامیده می­شود، با در نظر گرفتن محدویت­های بودجه و کران، هزینه کمان­ها را افزایش می­دهد که مقدار تابع هدف پیرو را تا حد ممکن بدتر نماید؛ با این امید که پیرو دست از فعالیت بیشتر بردارد. در این مقاله حالت خاصی از مسئله در نظر گرفته شده است که در آن درخت بهینه اولیه حتی با تغییر وزن­ها بهینه باقی می‌ماند. این فرض تضمین می­کند که رهبر می­تواند مطمئن باشد که پیرو انگیزه­ای برای تغییر استراتژی خود ندارد، زیرا استراتژی بهتری برای وی در دسترس نیست.
به منظور حل کارای این مسئله با هزینه­‌های خطی یک مدل جدید پیشنهاد می‌گردد که شامل تعداد زیادی محدودیت است. به همین دلیل یک الگوریتم حل بر مبنای روش تولید سطر (محدودیت) برای مسئله پیشنهاد می‌شود. سپس یک مثال عددی و نتایج محاسباتی بر نمونه‌های تصادفی برای ارزیابی عملکرد این روش ارائه می‌گردد. نتایج محاسباتی نشان می‌دهد که الگوریتم ارایه شده در تعداد تکرار متناهی و در زمان اجرای منطقی جواب بهینه مسئله را محاسبه می‌کند.
 
کلیدواژه‌های فارسی مقاله درخت پوشای کمینه، مسئله ممانعت، استراتژی ثابت، تابع هزینه خطی.
عنوان انگلیسی Minimum spanning tree interdiction problem considering follower strategy stability
چکیده انگلیسی مقاله Introduction: This paper examines a combinatorial optimization interdiction problem, called minimum spanning tree interdiction. From the point of view of game theory, this problem involves two players with different goals. The first player, called the follower, seeks to find a minimum spanning tree. On the other hand, the other player, who is called the leader, increases the cost of arcs, taking into account the budget and the bound constraints, which will make the value of the follower's objective function worse as much as possible, with the hope that the follower will stop doing more. In this article, a special case of the problem is considered in which the initial optimal tree remains optimal even with the change of weights. This assumption guarantees that the leader can be sure that the follower has no motivation to change his strategy, because a better strategy is not available.
Material and Methods: In order to efficiently solve this problem with linear costs, a new model is proposed, which includes a large number of constraints. For this reason, a solution approach based on the row (constraint) generation method is proposed for the problem. Then a numerical example and calculation results on random samples are presented to evaluate the performance of this method.
Results and discussion: The proposed model addresses this problem by utilizing a row generation approach to enhance solving efficiency. Computational results demonstrate its acceptable performance under various conditions, highlighting its potential for practical applications.  The computational results indicate that the proposed algorithm computes the optimal solution to the problem within a finite number of iterations and a reasonable execution time.
 
کلیدواژه‌های انگلیسی مقاله Minimum spanning tree, Interdiction problem, Fixed strategy, Linear cost function
نویسندگان مقاله جواد طیبی | Javad Tayyebi
Birjand University of Technology
دانشگاه صنعتی بیرجند

ملیحه نیک سیرت | Malihe Niksirat
Birjand University of Technology
دانشگاه صنعتی بیرجند

نشانی اینترنتی http://mmr.khu.ac.ir/browse.php?a_code=A-10-1774-1&slc_lang=fa&sid=1
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده جریان شبکه- تحقیق عملکرد
نوع مقاله منتشر شده علمی پژوهشی کاربردی
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات