یافتن مجموعه پایدار وزن‌دار یک گراف با وزن‌های غیر قطعی

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

نویسنده

گروه ریاضی، دانشکده علوم پایه، دانشگاه مراغه، مراغه، ایران

چکیده

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

کلیدواژه‌ها


[1] I. M. Bomze , M. Budinich, P. M. Pardalos and M. Pelillo, The maximum clique problem, Handbook of combi-natorial optimization, Supplement, Kluwer Acad. Publ., Dordrecht, A (1999) 1–74.
 [2] S. Burer, R. D. C. Monteiro and Y. Zhang, Maximum stable set formulations and heuristics based on continuous optimization, Math. Program., 94 (2002) 137–166.
[3] L. Chen, J. Peng, B. Zhang and S. Li, Uncertain programming model for uncertain minimum weight vertex covering problem, J. Intell. Manuf., 28 2017 625-632.
[4] M. Djahangiri and A. Ghaffari-Hadigheh, Uncertain weighted dominating set: a prototype application on natural disaster relief management, Soft Comput., 22 (2018) 1003–1012.
[5] Y. Gao, Shortest path problem with uncertain arc lengths,Comput. Math. Appl., 62 (2011) 2591–2600.
[6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979.
[7] A. Ghaffari-Hadigheh, Roman domination problem with uncertain positioning and deployment costs, Soft Com-put., 24 (2020) 2637-2645.
[8] Sh. Han, Z. Peng and S. Wang, The maximum flow problem of uncertain network, Inform. Sci., 265 (2014) 167–175.
[9] B. Liu and Y. K. Liuand, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst., 10 (2002) 445–450.
[10] B. Liu, Uncertainty theory, Second edition. Studies in Fuzziness and Soft Computing, 154, Springer, Berlin, 2007.
[11] B. Liu, Some research problems in uncertainty theory, J. Uncertain Syst., 3 (2009) 3–10.
[12] B. Liu, Uncertain risk analysis and uncertain reliability analysis, J. Uncertain Syst., 4 (2010) 163–170.
[13] B. Liu, Toward uncertain finance theory, J. Uncertain. Anal. Appl., 1 (2013) 1–5.
[14] B. Liu, Uncertainty theory, 24, Springer, Berlin, 2015.
[15] E. Maslov, M. Batsyn and P. M. Pardalos, Speeding up branch and bound algorithms for solving the maximum clique problem, J. Global Optim., 59 (2014) 1–21.
[16] S. Rebennack, M. Oswald, D. O. Theis, H. Seitz, G. Reinelt and P. M. Pardalos, A branch and cut solver for the maximum stable set problem, J. Comb. Optim., 21 (2011) 434–457.
[17] F. Rossi and S. Smriglio, A branch-and-cut algorithm for the maximum cardinality stable set problem, Oper. Res. Lett., 28(2) (2001) 63–74.
[18] P. San Segundo, D. Rodríguez-Losada and A. Jiménez, An exact bit-parallel algorithm for the maximum clique problem, Comput. Oper. Res., 38 (2011) 571–581.
[19] E. Tomita and T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with com-putational experiments, J. Global Optim., 37 (2007) 95–111.
[20] Y. Zhu, Uncertain optimal control with application to a portfolio selection model, Cybern. Syst. Int. J., 41 (2010) 535–547.