Mathematical Researches

fa مسئله ممانعت از درخت پوشای کمینه با هدف ثابت نگه داشتن استراتژی پیرو Minimum spanning tree interdiction problem considering follower strategy stability جریان شبکه- تحقیق عملکرد Network Flows- Operation Reseach علمی پژوهشی کاربردی S این مقاله یک مسئله ممانعت در بهینه‌سازی ترکیبیاتی، به نام ممانعت از درخت پوشای کمینه (MSTI) را بررسی می‌کند. از دیدگاه نظریه بازیها، این مسئله شامل دو بازیکن با اهداف متفاوت است. بازیکن اول که پیرو نامیده میشود به دنبال یافتن یک درخت پوشای کمینه است.  از طرف دیگر، بازیکن دیگر که رهبر نامیده میشود، با در نظر گرفتن محدویتهای بودجه و کران، هزینه کمانها را افزایش میدهد که مقدار تابع هدف پیرو را تا حد ممکن بدتر نماید؛ با این امید که پیرو دست از فعالیت بیشتر بردارد. در این مقاله حالت خاصی از مسئله در نظر گرفته شده است که در آن درخت بهینه اولیه حتی با تغییر وزنها بهینه باقی می‌ماند. این فرض تضمین میکند که رهبر میتواند مطمئن باشد که پیرو انگیزهای برای تغییر استراتژی خود ندارد، زیرا استراتژی بهتری برای وی در دسترس نیست. به منظور حل کارای این مسئله با هزینه‌های خطی یک مدل جدید پیشنهاد می‌گردد که شامل تعداد زیادی محدودیت است. به همین دلیل یک الگوریتم حل بر مبنای روش تولید سطر (محدودیت) برای مسئله پیشنهاد می‌شود. سپس یک مثال عددی و نتایج محاسباتی بر نمونه‌های تصادفی برای ارزیابی عملکرد این روش ارائه می‌گردد. نتایج محاسباتی نشان می‌دهد که الگوریتم ارایه شده در تعداد تکرار متناهی و در زمان اجرای منطقی جواب بهینه مسئله را محاسبه می‌کند. <div>  <hr align="left" size="1" width="33%" > <div id="ftn1"></div> </div> 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 99 120 http://mmr.khu.ac.ir/browse.php?a_code=A-10-1774-1&slc_lang=fa&sid=1 Javad Tayyebi جواد طیبی Javadtayyebi@birjandut.ac.ir 10031947532846006832 10031947532846006832 No Birjand University of Technology دانشگاه صنعتی بیرجند Malihe Niksirat ملیحه نیک سیرت niksirat@birjandut.ac.ir 10031947532846006833 10031947532846006833 Yes Birjand University of Technology دانشگاه صنعتی بیرجند