حل مساله برنامه ریزی دو سطحی خطی با استفاده از الگوریتم ژنتیک

مساله برنامه ریزی دو سطحی  (blp) یکی از مسائل مهم در تئوری تصمیم گیری می باشد که زیر مجموعه مسائل برنامه ریزی چند سطحی به شمار می رود. این مساله دارای دو سطح بیرونی و داخلی می باشد که فضای جواب مساله بیرونی یا سطح اول توسط مساله داخلی یا سطح دوم معین می شود. با توجه به اینکه blp یک مساله nphard می باشد، حل آن توسط روشهای سنتی به راحتی امکان پذیر نیست. در این مقاله ابتدا مساله blp و کاربردهای آن بررسی و سپس برای یافتن نقطه بهینه مساله از روش شمارش نقاط راسی استفاده می شود. در این مقاله برای جستجوی فضای اطراف نقاط راسی و یافتن جواب بهینه از الگوریتم ژنتیک استفاده می گردد. همچنین با استفاده از یک پارامتر کنترلی، شعاع فضایی را که باید جستجو شود کنترل می شود تا از افزایش زمان حل مساله اجتناب گردد. نتایج خروجی نشان می دهد که جواب بدست آمده از الگوریتم ژنتیک پیشنهادی در مقایسه با مطالعات قبلی قابل قبول می باشد.

An Algorithm Genetic Approach for solving Bi-level Linear Programming

Bilevel programming (BLP), is one of the important problems in the decisionmaking theory, is multilevel programming with two levels. It involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. Since the BLP problem is NPhard, it is impossible solving it by traditional methods. This paper reviews the BLP problem and applies enumeration techniques for finding extreme points. It uses the genetic algorithm for the searching region and finding the optimum solution. Also, the search region is controlled by a parameter in order to avoid the increased time. The results show that the solutions are acceptable in comparison with previous studies.