دوره 11، شماره 2 - ( 6-1404 )
دوره 11 شماره 2 صفحات 74-59 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Ghorbani-Moghadam K, Ghanbari R, Mohammadnia J. A pivoting algorithm for linear programming with linear complementarity constraints. mmr 2025; 11 (2) :59-74
URL: http://mmr.khu.ac.ir/article-1-3404-fa.html
URL: http://mmr.khu.ac.ir/article-1-3404-fa.html
قربانی مقدم خاطره، قنبری رضا، محمدنیا جواد. ارائه یک الگوریتم محورگیری برای برنامه‌ریزی خطی با قیدهای مکمل خطی. پژوهش های ریاضی. 1404; 11 (2) :59-74
خاطره قربانی مقدم*1 
، رضا قنبری2 ، جواد محمدنیا2
، رضا قنبری2 ، جواد محمدنیا2
1- موسسه تحقیقات ریاضی دکتر مصاحب، دانشگاه خوازمی ، k.ghorbani@khu.ac.ir
2- دانشکده علوم ریاضی، دانشگاه فردوسی مشهد
2- دانشکده علوم ریاضی، دانشگاه فردوسی مشهد
چکیده: (30 مشاهده)
مساله‌های برنامه‌ریزی خطی با قیدهای مکمل خطی[1] (LPCC) جز مساله‌های پرکاربرد در رشته تحقیق در عملیات هستند و حل آن‌ها به‌دلیل ماهیت غیرخطی و پیچیده قیدهای مکملی، در رده مسائل NP-hard قرار می‌گیرد. در این مقاله، یک حالت خاص از LPCC مورد بررسی قرار گرفته است که در آن قید مکملی از نوع x p x m =0 
ظاهر می‌شود. این نوع قید در بسیاری از مسائل کاربردی بهینه‌سازی، به‌ویژه در مدل‌هایی که شامل عباراتی نظیر قدرمطلق هستند، دیده می‌شود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روش‌های مرسوم خطی‌سازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ[2] ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی می‌شوند. مزیت روش پیشنهادی در بهره‌گیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روش‌های کلاسیک مانند خطی‌سازی و الگوریتم‌های عمومی شاخه و کران می‌شود. الگوریتم پیشنهادی به‌صورت کامل توسعه داده شده و عملکرد آن از طریق حل مثال‌های عددی و مقایسه با روش‌های مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان می‌دهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روش‌های رایج برتری دارد.
ظاهر می‌شود. این نوع قید در بسیاری از مسائل کاربردی بهینه‌سازی، به‌ویژه در مدل‌هایی که شامل عباراتی نظیر قدرمطلق هستند، دیده می‌شود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روش‌های مرسوم خطی‌سازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ[2] ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی می‌شوند. مزیت روش پیشنهادی در بهره‌گیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روش‌های کلاسیک مانند خطی‌سازی و الگوریتم‌های عمومی شاخه و کران می‌شود. الگوریتم پیشنهادی به‌صورت کامل توسعه داده شده و عملکرد آن از طریق حل مثال‌های عددی و مقایسه با روش‌های مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان می‌دهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روش‌های رایج برتری دارد.
نوع مطالعه: مقاله مستقل |
موضوع مقاله:
ریاضی
دریافت: 1403/5/18 | ویرایش نهایی: 1404/8/17 | پذیرش: 1404/5/8 | انتشار: 1404/6/15 | انتشار الکترونیک: 1404/6/15
دریافت: 1403/5/18 | ویرایش نهایی: 1404/8/17 | پذیرش: 1404/5/8 | انتشار: 1404/6/15 | انتشار الکترونیک: 1404/6/15
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
