مسئله کوله پشتی با ارزش های فازی مردد بازه‌ای مقدار

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

نویسندگان

1 گروه مهندسی برق، دانشگاه صنعتی شهدای هویزه، دشت آزادگان، خوزستان، ایران

2 گروه ریاضی، دانشگاه صنعتی خاتم الانبیاء بهبهان، خوزستان

20.1001.1.27174409.1399.3.1.12.7/DOR

چکیده

‏در این مطالعه قصد داریم مسئله کوله پشتی صفر و یک که در آن ارزش هریک از آیتم‌ها به صورت مجموعه فازی مردد بازه ای مقدار بیان می‌شود را بررسی نماییم. به این معنا که بیش از یک تصمیم گیرنده در ارزیابی ارزش هر یک از اشیایی که در کوله پشتی قرار گرفته‌اند مشارکت داشته‌اند و علاوه بر این، تصمیم گیرندگان نظرهای خود را به صورت بازه ­ای بین صفر و یک ثبت نموده‌اند. البته وزن هریک از آیتم‌ها و همین طور وزن کل، برای کوله پشتی به صورت قطعی در نظر گرفته شده است. برای این منظور چارچوب مناسبی را جهت رسیدن به پاسخ مناسب مسئله طراحی کردیم. با تحلیل مناسب ساختار مسئله و شناسائی عوامل موثر در حل آن، روش رتبه بندی و عملگر تجمعی مناسبی برای یافتن پاسخ مسئله انتخاب شد. در نهایت مثالی عددی برای بررسی مدل و روش حل ارائه شده مطرح گردید. نتایج از دیدگاه تصمیم گیرنده خوشبین، بدبین و متعادل به دست آمده است. لذا تنوع مناسبی در انتخاب پاسخ برای تصمیم گیرنده فراهم آمده است.

کلیدواژه‌ها


[1] Wascher, G., Schumann, H., An improved typology of cutting and packing problems, Eur. J. Oper. Res. 183 (3) (2007) 1109–1130.
 
[2] Nawrocki, J., Complak, W., Błazewicz, J., Kopczyn-' ska, S., Mac' kowiaki, M., The knapsack-lightening problem and its application to scheduling HRT tasks,Bull. Polish Acad. Sci.: Tech. Sci. 57 (1) (2009) 71–77.
 
[3] Kong, M., Tian, P., Kao, Y., A new ant colony optimization algorithm for the multidimensional knapsack problem, Comput. Oper. Res. 35 (8) (2008) 2672–2683.
 
[4] Granmo, O., Oommen, B,. Myrer, S., Olsen, M., Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation, IEEE Trans Syst. Man Cybern. Part B Cybern. 37 (1) (2007) 166–175.
 
[5] Vanderster, D., Dimopoulos, N., Parra-Hernandez, R., Sobie, R., Resource allocation on computational grids using a utility model and the knapsack problem, Future Gener. Comput. Syst. 25 (1) (2009) 35–50.
 
[6] Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S., Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Appl. Soft Comput. 12 (2011) 1231-1237.
 
[7] Mavrotas, G., Diakoulaki, D., Kourentzis, A., Selection among ranked projects under segmentation, policy and logical constraints, Eur. J. Oper. Res. 187 (1) (2008) 177-192.
 
[8] Bas, E., A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model, Expert Syst. Appl. 38 (10) (2011) 12415-12422.
 
[9] Wilbaut, C., Hanafi, S., Salhi, S., A survey of effective heuristics and their application to a variety of knapsack problems, IMA J. Manage. Math. 19 (3)(2008) 227.
 
[10] Dudzinski, K., "A Dynamic Programming Approach to Solving the Multiple Choice Knapsack Problem”, Bull. Polish Acad. Sci., Tech. Sci., No. 32, 1984, PP. 325-332.
 
[11] Dyer, M.E., Kayal, N., Walker, J., "A Branch and Bound Algorithm for Solving the Multiple Choice Knapsack Problem”, Journal of Computational and Applied Mathematics, No. 11, 1984, PP. 231-249.
 
[12] Dyer, M.E., Riha, W.O., Walker, J., "A Hybrid Dynamic Programming/Branch and Bound Algorithm For The Multiple-Choice Knapsack Problem", Journal of Computational and Applied Mathematics, No. 58, 1995, PP. 43-54.
 
[13] Abdel-Basset, M., El-Shahat, D., and El-Henawy, I., "Solving 0-1 knapsack problem by binary flower pollination algorithm,” Neural Computing and Applications, vol. 31, no. 9, pp. 5477–5495, 2019.
 
[14] Olivas, F., Amaya, I., Ortiz-Bayliss, J.C., Conant-Pablos, S.E., and Terashima-Marin, H., "A Fuzzy Hyper-Heuristic Approach for the 0-1 Knapsack Problem," 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, United Kingdom, 2020, pp. 1-8, doi: 10.1109/CEC48606.2020.9185710.
 
[15] L. A. Zadeh et al., "Fuzzy sets," Information and control, vol. 8, no. 3,pp. 338–353, 1965.
 
[16] Okada, S., Gen, M., "Fuzzy Multiple Choice Knapsack Problem", Fuzzy Sets and Systems, No. 67, 1994, PP. 71-80.
 
[17] Okada, S., Gen, M., "A Method for Solving Fuzzy Multi-Dimensional 0-1 Knapsack Problems", Japanese Journal Fuzzy Theory Systems, No. 6, 1995, PP. 687-702.
 
[18] Torra, V., Narukawa, Y., On hesitant fuzzy sets and decision. The 18-thIEEE International Conference on Fuzzy Systems, Jeju Island, Korea(2009) 1378-1382.
 
[19] Torra, V., Hesitant Fuzzy Sets, Int. J. Intell. Syst. 25 (2010) 529–539.
 
[20] Xia MM, Xu ZS, Chen N (2013) Some hesitant fuzzy aggregation operators with their application in group decision making. Group DecisNegot 22:259–279.
 
[21] Sengupta A, Pal TK (2000) On comparing interval numbers. Eur J Oper Res 127:28-43.
 
[22] Wei GW, Zhao XF, Li R (2013) Some hesitant interval-valued fuzzy aggregation operators and their applications to multiple attribute decision making. Knowl Based Syst 46:43–53.
 
[23] Zeng, W., Li, D. Gu, Y. Note on the aggregation operators and ranking of hesitant interval-valued fuzzy elements. Soft Comput23, 8075-8083 (2019). https://doi.org/10.1007/s00500-018-3445-x.