حل مسائل التحسين الصعبة NP باستخدام بعض تطبيقات الرسم البياني

الباحث

حسين علي حسين جاسم الدلال

المشرف

مشتاق عبد الغني شخير الجنابي

الجامعة

جامعة بابل

الكلية / القسم

كلية التربية للعلوم الصرفة / الرياضيات

الشهادة

دكتوراه

السنة

2024

لغة الرسالة

انكليزي

الكلمات المفتاحية

NP-Hard Problems; Graph Theory; Optimization; Heuristic Algorithms

تعد عملية تحسين الشبكة القائمة على الرسم البياني واحدة من أبرز مسائل تحسين NP-hard في الرياضيات. تتضمن عملية تحسين الشبكة المستندة إلى الرسوم البيانية استخدام الأساليب والتقنيات الرياضياتية التي تقوم بدعم أداء الشبكات وتحسين كفادتها في تحقيق المبتغات الذي من أجلها وجدت تلك الشبكات. ومن الواضح ان استخدام تحسين الشبكات وتطبيقاتها تنتشر بشكل واسع جداً ولها دور فعال في lane المجالات الحيوية والغير حيوية. فهي تحظى بأهمية بالغة. وكان ذلك أحد الأسباب التي دعت إلى تناولها كمشكلة رئيسية في هذه الاطروحة. وبالرغم من أتساع رقعة مشاكل تحسين الشبكات, فقد خصصت الدراسة في هذه الاطروحة حول مشكلتين بارزتين تنطويان تحت مشاكل نتحسين الشبكات من أجل حصر أهداف الدراسة لان هذا يؤدي إلى حصاد أفضل النتائح. وعليه فقد تم إجراء البحث من خلال دراسة كل من مشكلة البائع المتجول (TSP) ومشكلة مقايضات الجودة والتكلفة لانهما من المشاكل البارزة في نظرية التحسين ونظرية الرسم البياني. وكذلك نظراً لأهميتهم الكبيرة والملموسة في عدة مجالات منها خدمات النقل والاتصالات, وشبكات المياه والكهرباء. والتخطيط لإدارة المشاريع. وجدولة العمليات الإنتاجية. وغير ذلك. في الواقع تصنف مشكلة البائع المتجول (TSP) ضمن مشاكل الأمثلية التوافقية التي تنتمي إلى فئة مشاكل NP-hard ويعود سبب هذا التصنيف إلى حدوث الانفجار التوافقي للحلول المجدية في منطقة الحل المجدي عندما يزداد حجم المشكلة. في حين تعد مشكلة مقايضات الجودة والتكلفة من المشاكل التي لها بنية شبكية معقدة, خاصة عندما تنشأ في المشاريع العملاقة والعمليات الانتاجية الضخمة. بشكل عام, ان أهداف إجراء هذه الدراسة تتجسد في دراسة مشكلة البائع المنجول (TSP) والتي تكون وظيفتها الموضوعية بنوعيها التصفير والتعظيم بغرض التوصل إلى بناء خوارزميات فعالة لحل تلك المشاكل. بالإضافة إلى ذلك دراسة مشكلة مقايضات الجودة والتكلفة من أجل وضع نهج فعال لحل هذه المشكلة. بالحقيقة ان ما نم تقديمه في هذه الاطروحة ينسجم مع تحقيق الأهداف الوارد ذكرها Ladi والتي تمثلت بإجراء دراسة شاملة تقريباً لما يخص أهم أساسيات مشاكل تحسين الشبكات. علاوة على EUS تم إنشاد كل من خوارزمية مصفوفة التجاور الأولى (RAMA) وخوارزمية مصفوفة التجاور الثانية SAMA) لحل مشكلة البائع المتجول (TSP) ذو الدالة الموضوعية بنوعيها, على التوالي. الى جانب ذلك, تم تصميم كل من التقنية الأولى لتحسين الجودة (FTQO) والتقنية الثانية لتحسين الجودة (STQO) من أجل حل مشكلة مقايضات الجودة والتكلفة. وفي هذا الصدد فقد تم اختبار كفادة أداء هذه الخوارزميات لتحديد مدى أفضلية وأهمية النتائج المتحصل عليها من خلال استخدامها في حل العديد من القضايا الخاصة بكل واحدة منها. ومن هنا تمثلت النتائج الرئيسية بالحصول على أفضل الحلول المجدية لتلك القضايا. على الرغم من كل التحديات والتعقيدات التي تنطوي عليها تلك المشاكل. ان من أبرز الأسباب التي أدت إلى ننائج فعالة تكمن في تصميم كافة تلك الخوارزميات بأسلوب دقيق يحاكي بيانات المشاكل وطبيعة حلولها. وأخيراً. ان أهمية ما ورد في هذه الدراسة تتجلى في نميز أداء تلك الخوارزميات وكفادة النتائح التي حققتها. كما تنعكس أهمية الدراسة الحالية بشكل عام من خلال مساهمتها في تلبية متطلبات صناع القرار ورفد الباحثون بأهم الأفكار التي تدعمهم لإجراء المزيد من الدراسات البحثية الرائدة ضمن نطاق مشاكل تحسين الشبكات والمشاكل المرتبطة بها.

Solving NP-Hard Optimization Problems by Using some Graph Applications I One of the most prominent NP-hard optimization problems in mathematics is graph- based network optimization. The process of network optimization that is based on graphs involves the use of mathematical approaches and techniques that support the performance of networks and optimize their efficiency in achieving goals for which those networks were found. It is clear that the use of networks optimization and its applications is very widespread and has an effective role in most vital and non-vital fields. It's great importance, and that was one of reasons that necessitated addressing it as a major problem in this dissertation. Despite the wide scope of networks optimization problems, the study in this dissertation was devoted to two prominent problems that fall under networks optimization problems in order to limit objectives of the study because this leads to harvest the best results. Accordingly, the research was conducted by studying both the traveling salesman problem (TSP) and the problem of quality-cost trade-offs because they are among prominent problems in optimization theory and graph theory. Also, due to their great and tangible importance in several areas, including transportation and communications services, water and electricity networks, planning for project management, scheduling production operations, and so on. In fact, TSP is classified among the combinatorial optimization problems that belong to the category of NP-hard problems, and the reason for this classification is due to occurrence of the combinatorial explosion of feasible solutions in the feasible solution region when the problem size increases. While the problem of quality-cost trade-offs is one of problems that has a complex network structure, especially when it arises in mega projects and huge production operations. In general, objectives of conducting this study are embodied in studying TSP which its objective function of both to minimize and maximize for the purpose of arriving at building effective algorithms to solve those problems. In addition, studying the problem of quality-cost trade-offs in order to set an effective approach to solve this problem. Actually, what was presented in this dissertation is consistent with achieving goals mentioned above, which was represented by conducting an almost comprehensive study of the most important basics of networks optimization problems. Moreover, the first adjacency matrix algorithm (FAMA) and the second adjacency matrix algorithm (SAMA) were created to solve TSP with its two types of objective functions, respectively. Besides, both first technique for quality optimization (FTQO) and second technique for quality optimization (STQO) are designed to solve the problem of quality- cost trade-offs. In this regard, the performance efficiency of these algorithms was tested to determine the extent of the superiority and importance of results obtained by using them in solving many issues specific to each. Hence, main results were obtaining the best feasible solutions to those issues, although of all challenges and complexities involved in those problems. One of the most prominent reasons that led to effective results lies in the design of all those algorithms in a precise manner that simulates problems data and the nature of their solutions. Finally, the importance of what was stated in this study is manifested in the performance excellence of those algorithms and the efficiency of results they achieved. The importance of the current study in general is also reflected in its contribution to meet requirements of decision makers and providing researchers with the most important ideas that support them to conduct more pioneering research studies within the scope of networks optimization problems and problems associated with them.

طلب نسخة من الملف

الملفات غير منشورة على الموقع. اترك بياناتك وسيتواصل معك موظفو قسم الشؤون الثقافية والفنون لإرسال النسخة مجاناً.

الاسم

رقم الهاتف

البريد الإلكتروني

الغرض من الطلب (اختياري)

إرسال الطلب