A bi-level linear programming problem for computing the nadir point in MOLP

Authors

1 1Assistant Professor, Department of Applied Mathematics, University of Tabriz, Tabriz, Iran

2 M.Sc Graduate, Department of Applied Mathematics, University of Tabriz, Tabriz, Iran

Abstract

Computing the exact ideal and nadir criterion values is a very important subject in multi-objective linear programming (MOLP) problems‎‎. In fact, these values define the ideal and nadir points as lower and upper bounds on the nondominated points. Whereas determining the ideal point is an easy work, because it is equivalent to optimize a convex function (linear function) over a convex set which is a convex optimization problem, but the problem of computing the nadir point in MOLP is equivalent to solving a nonconvex optimizationproblem whose solving is very hard in the general case. ‎‎In this paper, a bi-level linear programming problem is presented for obtaining the nadirpoint in MOLP problems which can be used in general to optimize a linear function on the nondominated set, as well. Then, as one of the solution methods of this problem, amixed-integer linear programming problem is presented which obtains the exact nadir values in one stage.

Keywords


Article Title [Persian]

مساله برنامه‌ریزی خطی دوسطحی برای محاسبه نقطه ضدایده‌آل

Authors [Persian]

  • جواد وکیلی 1
  • حلیمه دهقانی 2
1 استادیار، دانشگاه تبریز، گروه ریاضی کاربردی، تبریز، ایران
2 دانش آموخته کارشناسی ارشد، دانشگاه تبریز، گروه ریاضی کاربردی، تبریز، ایران
Abstract [Persian]

محاسبه مقادیر دقیق معیار ایده‌آل و ضدایده‌آل موضوع مهمی در مسائل برنامه‌ریزی خطی چند‌معیاره  (MOLP)است. در واقع این مقادیر به‌عنوان کران‌های پایین و بالا روی مجموعه نقاط نامغلوب تعریف می‌شوند. هرچند تعیین نقطه ایده‌آل یک کار آسانی است، چون آن معادل با بهینه‌سازی یک تابع محدب (تابع خطی) روی یک مجموعه محدب است که یک مساله بهینه‌سازی محدب است، اما محاسبه نقطه ضدایده‌آل در MOLP با یک مساله بهینه‌سازی نامحدب معادل می‌باشد که حل آن در حالت کلی کار خیلی سختی است. در این مقاله یک مساله برنامه‌ریزی خطی دوسطحی برای به‌دست آوردن نقطه ضدایده‌آل در مسائلMOLP ارائه می‌شود که در حالت کلی می‌تواند برای بهینه‌سازی یک تابع خطی روی مجموعه نقاط نامغلوب نیز به‌کار رود. در نهایت، به‌عنوان یک روش حل مسائل برنامه‌ریزی خطی دوسطحی، یک مساله برنامه‌ریزی خطی مختلط- صحیح ارائه می‌شود که مقادیر دقیق ضدایده‌آل را در یک مرحله به‌دست می‌آورد.

Keywords [Persian]

  • مسائل برنامه‌ریزی خطی چندهدفه
  • برنامه‌ریزی خطی دوسطحی
  • نقطه ضدایده‌آل