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

نویسنده

استادیار دانشکده مهندسی صنایع، دانشگاه صنعتی ارومیه، ارومیه، ایران

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

An Algorithm Genetic Approach for solving Bi-level Linear Programming

نویسنده [English]

  • Hashem Omrani
Department of Industrial Engineering, Urmia University of Technology, Urmia, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Bi-level programming
  • Genetic Algorithm
  • Decision theory