|
|
پژوهش های ریاضی، جلد ۱۱، شماره ۲، صفحات ۵۹-۷۴
|
|
|
| عنوان فارسی |
ارائه یک الگوریتم محورگیری برای برنامه‌ریزی خطی با قیدهای مکمل خطی |
|
| چکیده فارسی مقاله |
مساله‌های برنامه‌ریزی خطی با قیدهای مکمل خطی (LPCC) جز مساله‌های پرکاربرد در رشته تحقیق در عملیات هستند و حل آن‌ها به‌دلیل ماهیت غیرخطی و پیچیده قیدهای مکملی، در رده مسائل NP-hard قرار می‌گیرد. در این مقاله، یک حالت خاص از LPCC مورد بررسی قرار گرفته است که در آن قید مکملی از نوع x p x m =0 ![""]("file:///C:/Users/HP/AppData/Local/Temp/msohtmlclip1/01/clip_image001.png") ظاهر می‌شود. این نوع قید در بسیاری از مسائل کاربردی بهینه‌سازی، به‌ویژه در مدل‌هایی که شامل عباراتی نظیر قدرمطلق هستند، دیده می‌شود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روش‌های مرسوم خطی‌سازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی می‌شوند. مزیت روش پیشنهادی در بهره‌گیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روش‌های کلاسیک مانند خطی‌سازی و الگوریتم‌های عمومی شاخه و کران می‌شود. الگوریتم پیشنهادی به‌صورت کامل توسعه داده شده و عملکرد آن از طریق حل مثال‌های عددی و مقایسه با روش‌های مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان می‌دهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روش‌های رایج برتری دارد.
Linear Programming with Linear Complementarity Constraints
|
|
| کلیدواژه‌های فارسی مقاله |
برنامه‌ریزی خطی، قیدهای مکمل خطی، برنامه‌ریزی صفر و یک، الگوریتم شاخه و کران |
|
| عنوان انگلیسی |
A pivoting algorithm for linear programming with linear complementarity constraints |
|
| چکیده انگلیسی مقاله |
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 |
|
| نویسندگان مقاله |
خاطره قربانی مقدم | Khatere Ghorbani-Moghadam
Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran
موسسه تحقیقات ریاضی دکتر مصاحب، دانشگاه خوازمی
رضا قنبری | Reza Ghanbari
Ferdowsi University of Mashhad
دانشکده علوم ریاضی، دانشگاه فردوسی مشهد
جواد محمدنیا | Javad Mohammadnia
Ferdowsi University of Mashhad
دانشکده علوم ریاضی، دانشگاه فردوسی مشهد
|
|
| نشانی اینترنتی |
http://mmr.khu.ac.ir/browse.php?a_code=A-11-1757-1&slc_lang=fa&sid=1 |
| فایل مقاله |
فایلی برای مقاله ذخیره نشده است |
| کد مقاله (doi) |
|
| زبان مقاله منتشر شده |
fa |
| موضوعات مقاله منتشر شده |
ریاضی |
| نوع مقاله منتشر شده |
مقاله مستقل |
|
|
|
برگشت به:
صفحه اول پایگاه |
نسخه مرتبط |
نشریه مرتبط |
فهرست نشریات
|
