1 نتیجه برای برنامهریزی صفر و یک
خانم دکتر خاطره قربانی مقدم، آقای دکتر رضا قنبری، آقای جواد محمدنیا،
دوره 11، شماره 2 - ( 6-1404 )
چکیده
مسالههای برنامهریزی خطی با قیدهای مکمل خطی (LPCC) جز مسالههای پرکاربرد در رشته تحقیق در عملیات هستند و حل آنها بهدلیل ماهیت غیرخطی و پیچیده قیدهای مکملی، در رده مسائل NP-hard قرار میگیرد. در این مقاله، یک حالت خاص از LPCC مورد بررسی قرار گرفته است که در آن قید مکملی از نوع x p x m =0 
ظاهر میشود. این نوع قید در بسیاری از مسائل کاربردی بهینهسازی، بهویژه در مدلهایی که شامل عباراتی نظیر قدرمطلق هستند، دیده میشود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روشهای مرسوم خطیسازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی میشوند. مزیت روش پیشنهادی در بهرهگیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روشهای کلاسیک مانند خطیسازی و الگوریتمهای عمومی شاخه و کران میشود. الگوریتم پیشنهادی بهصورت کامل توسعه داده شده و عملکرد آن از طریق حل مثالهای عددی و مقایسه با روشهای مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان میدهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روشهای رایج برتری دارد.
Linear Programming with Linear Complementarity Constraints
