ناحیه جواب مدل برنامه ریزی خطی بازه ای با رویکرد جدید

نوع مقاله: مقاله پژوهشی

نویسندگان

1 گروه ریاضی، دانشکده ریاضی، دانشگاه سیستان و بلوچستان، زاهدان،ایران

2 ریاضی، دانشکده ریاضی، دانشگاه سیستان و بلوچستان، زاهدان، ایران

چکیده

 در این مقاله تعیین ناحیه­ی جواب مدل­های برنامه­ریزی خطی بازه­ای  (ILP)که در حالت کلی یک مسئله­ی NP سخت است، در نظر گرفته‌شده است. در تمامی روش­های حل مدل­های ILP تنها شرط شدنی بودن (یعنی جلوگیری از نقض قیود) مدنظر قرارگرفته است. روش حالات بهترین - بدترین (BWC) یکی از روش­های حل مدل ILP هست. گرچه این روش بهترین و بدترین مقادیر تابع هدف را تعیین می­کند اما برخی از جواب­های حاصل، نشدنی می­باشند. برای تضمین شدنی بودن جواب­ها روش دو گامی بهبودیافته (ITSM)، روش برنامه­ریزی خطی اصلاح‌شده (MILP) پیشنهادشده است. هرچند در این روش­ها، تمام جواب­ها شدنی­اند اما برخی از آن‌ها بهینه نمی­باشند. با استفاده از یک رویکرد جدید، ناحیه جوابی برای حل مدل ILP معرفی می­شود که با استفاده از دو آزمون، شدنی بودن و بهینگی فضای حاصل تضمین می‌گردد.

کلیدواژه‌ها

موضوعات

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

Solution space of interval linear programming model by new approach

نویسندگان [English]

  • Mehdi Allahdadi 1
  • Hasan Mishmast Nehi 2
1 Mathematics Department, University of Sistan and Baluchestan, Zahedan, Iran
2 Mathematics Department, University of Sistan and Baluchestan, Zahedan, Iran
چکیده [English]

In this paper, solution space of interval linear programming (ILP) models that is a NP-hard problem, has been considered. In all of the solving methods of the ILP, feasibility condition has been only considered. Best-worst case (BWC) is one of the methods for solving the ILP models. Some of the solutions obtained by the BWC may result in an infeasible space. To guarantee that solution is completely feasible, improved two-step method (ITSM) is proposed. By using a new approach, we introduce a space for solving ILP models in which by two tests, feasibility and optimality of the obtained space has been guaranteed.

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

  • Interval linear programming
  • BWC
  • ITSM
  • MILP
  • Uncertainty

مراجع

Alefeld, G., & Herzberger, J. (2012). Introduction to interval computation. Academic press.

Allahdadi, M., Nehi, H. M., Ashayerinasab, H. A., & Javanmard, M. (2016). Improving the modified interval linear programming method by new techniques. Information sciences, 339, 224-236.

Allahdadi, M., & Nehi, H. M. (2013). The optimal solution set of the interval linear programming problems. Optimization letters, 7(8), 1893-1911.

Fiedler, M., Nedoma, J., Ramik, J., Rohn, J., & Zimmermann, K. (2006). Linear optimization problems with inexact data. Springer Science & Business Media.

Chinneck, J. W., & Ramadan, K. (2000). Linear programming with interval coefficients. Journal of the operational research society, 209-220.

Hladík, M. (2014). How to determine basis stability in interval linear programming. Optimization letters, 8(1), 375-389.

Huang, G., & Dan Moore, R. (1993). Grey linear programming, its solving approach, and its application. International journal of systems science, 24(1), 159-172.

Koníckocá, J. (2001). Sufficient condition of basis stability of an interval linear programming problem. ZAMM‐Journal of applied mathematics and mechanics/zeitschrift für angewandte mathematik und mechanik, 81(S3), 677-678.

Rohn, J. (1993). Cheap and tight bounds: The recent result by E. Hansen can be made more efficient. Interval computations, 4(13-21), 2.

Rohn, J. (2009). Forty necessary and sufficient conditions for regularity of interval matrices: A survey. Electronic journal of linear algebra, 18(500-512), 86.

Rohn, J. (1993). Stability of the optimal basis of a linear program under uncertainty. Operations research letters, 13(1), 9-12. Shaocheng, T. (1994). Interval number and fuzzy number linear programmings. Fuzzy sets and systems, 66(3), 301-306.

Wang, X., & Huang, G. (2014). Violation analysis on two-step method for interval linear programming. Information sciences, 281, 85-96.

Zhou, F., Huang, G. H., Chen, G. X., & Guo, H. C. (2009). Enhanced-interval linear programming. European journal of operational research, 199(2), 323-333.

تصمیم گیری و تحقیق در عملیات

دوره 2، شماره 3
زمستان 1396
صفحه 228-235

فایل ها

سابقه مقاله

  • تاریخ دریافت: 06 شهریور 1396
  • تاریخ بازنگری: 11 دی 1396
  • تاریخ پذیرش: 12 دی 1396

اشتراک گذاری

ارجاع به این مقاله

آمار