حل مسأله برنامه ريزي دو سطحي خطي با استفاده از الگوريتم ژنتيك

An Algorithm Genetic Approach for solving Bi-level Linear Programming

مسأله برنامه ريزي دو سطحي (BLP) يكي از مسائل مهم در تئوري تصميم گيري مي باشد كه زير مجموعه مسائل برنامه ريزي چند سطحي به شمار مي رود. اين مسأله داراي دو سطح بيروني و داخلي مي باشد كه فضاي جواب مسأله بيروني يا سطح اول توسط مسأله داخلي يا سطح دوم معين مي شود. با توجه به اينكه BLP يك مسأله NP-hard مي باشد، حل آن توسط روشهاي سنتي به راحتي امكان پذير نيست. در اين مقاله ابتدا مسأله BLP و كاربردهاي آن بررسي و سپس براي يافتن نقطه بهينه مسأله از روش شمارش نقاط رأسي استفاده مي شود. در اين مقاله براي جستجوي فضاي اطراف نقاط رأسي و يافتن جواب بهينه از الگوريتم ژنتيك استفاده مي گردد. همچنين با استفاده از يك پارامتر كنترلي، شعاع فضايي را كه بايد جستجو شود كنترل مي شود تا از افزايش زمان حل مسأله اجتناب گردد. نتايج خروجي نشان مي دهد كه جواب بدست آمده از الگوريتم ژنتيك پيشنهادي در مقايسه با مطالعات قبلي قابل قبول مي باشد.

Bi-level programming (BLP), is one of the important problems in the decision-making 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 NP-hard, 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.