Mathematical Researches

fa ارائه یک الگوریتم محورگیری برای برنامه‌ریزی خطی با قیدهای مکمل خطی A pivoting algorithm for linear programming with linear complementarity constraints ریاضی Mat مقاله مستقل Original Manuscript مساله‌های برنامه‌ریزی خطی با قیدهای مکمل خطی<a href="#_ftn1" name="_ftnref1" title="">[1]</a> &lrm;&lrm;&lrm;&lrm;(LPCC) &lrm; جز مساله‌های پرکاربرد در رشته تحقیق در عملیات هستند و حل آن‌ها به‌دلیل ماهیت غیرخطی و پیچیده قیدهای مکملی، در رده مسائل NP-hard قرار می‌گیرد. در این مقاله، یک حالت خاص از LPCC مورد بررسی قرار گرفته است که در آن قید مکملی از نوع <m:ctrlpr></m:ctrlpr> <m:r>x</m:r> <m:r>p</m:r> <m:r> </m:r> <m:ctrlpr></m:ctrlpr> <m:r>x</m:r> <m:r>m</m:r> <m:r>=0</m:r> <img alt="" id="_x0000_i1025" src="file:///C:/Users/HP/AppData/Local/Temp/msohtmlclip1/01/clip_image001.png" style="width:48pt; height:15pt" >  ظاهر می‌شود. این نوع قید در بسیاری از مسائل کاربردی بهینه‌سازی، به‌ویژه در مدل‌هایی که شامل عباراتی نظیر قدرمطلق هستند، دیده می‌شود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روش‌های مرسوم خطی‌سازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ<a href="#_ftn2" name="_ftnref2" title="">[2]</a> ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی می‌شوند. مزیت روش پیشنهادی در بهره‌گیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روش‌های کلاسیک مانند خطی‌سازی و الگوریتم‌های عمومی شاخه و کران می‌شود.   الگوریتم پیشنهادی به‌صورت کامل توسعه داده شده و عملکرد آن از طریق حل مثال‌های عددی و مقایسه با روش‌های مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان می‌دهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روش‌های رایج برتری دارد. <div>  <hr align="left" size="1" width="33%" > <div id="ftn1"><a href="#_ftnref1" name="_ftn1" title="">[1]</a> Linear Programming &lrm;with &lrm;Linear&lrm; Complementarity Constraints</div> <div id="ftn2"><a href="#_ftnref2" name="_ftn2" title="">[2]</a> Big-M</div> </div>   <div>  <hr align="left" size="1" width="33%" ></div> Linear programming problems with complementary linear constraints (LPCC) are widely studied in operations research and are known to be NP-hard. This paper explores a specific case of LPCC where the product of two variables must be zero, i.e., xp xm=0. This scenario frequently arises in optimization problems, particularly those involving absolute values that cannot be expressed as linear or integer programming problems. To tackle this, we will present a branch-and-bound algorithm, and we will implement the algorithm on numerical examples and compare its performance with existing methods. برنامه‌ریزی خطی, قیدهای مکمل خطی, برنامه‌ریزی صفر و یک, الگوریتم شاخه و کران Linear Programming Problems, Linear‎ Complementarity Constraints, Zero-one constraint, Branch and Bound Algorithm 59 74 http://mmr.khu.ac.ir/browse.php?a_code=A-11-1757-1&slc_lang=fa&sid=1 Khatere Ghorbani-Moghadam خاطره قربانی مقدم k.ghorbani@khu.ac.ir 10031947532846006861 10031947532846006861 Yes Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran موسسه تحقیقات ریاضی دکتر مصاحب، دانشگاه خوازمی Reza Ghanbari رضا قنبری rghanbari@um.ac.ir 10031947532846006862 10031947532846006862 No Ferdowsi University of Mashhad دانشکده علوم ریاضی، دانشگاه فردوسی مشهد Javad Mohammadnia جواد محمدنیا khatere.moghadam67@gmail.com 10031947532846006863 10031947532846006863 No Ferdowsi University of Mashhad دانشکده علوم ریاضی، دانشگاه فردوسی مشهد