تحليل مشكلات التحسين والبرمجة الرياضية - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

سؤال 3: قم بتحليل مشكلتين من مشكلات التحسين يُمكن حلهما باستخدام البرمجة الرياضية، ثم حدّد متغيرات الحالة ومتغيرات القرار الخاصة بهما.

الإجابة: س:3: 1) مسألة البائع المتجول: الهدف أقل مسافة. الحالة: S (المدن)، i (الحالية). القرار: المدينة j. 2) مسألة حقيبة الظهر: الهدف تعظيم القيمة. الحالة: i (العنصر)، W (السعة). القرار: xi (أخذ العنصر).

خطوات الحل:

1. **الشرح:** لنفهم هذا السؤال. البرمجة الرياضية هي أداة لحل مشكلات التحسين، حيث نريد إيجاد أفضل قيمة (مثل أقل تكلفة أو أعلى ربح) ضمن قيود معينة. السؤال يطلب تحليل مشكلتين من هذه المشكلات. **المشكلة الأولى: مسألة البائع المتجول (Traveling Salesman Problem - TSP)** الفكرة هنا هي أن بائعاً يريد زيارة مجموعة من المدن ثم العودة إلى مدينته الأصلية، بحيث يقطع أقصر مسافة ممكنة دون زيارة أي مدينة أكثر من مرة. - **متغيرات الحالة:** تمثل الظروف أو المواقف أثناء الحل. هنا، الحالة يمكن أن تكون: مجموعة المدن التي تمت زيارتها (S)، والمدينة الحالية التي يقف فيها البائع (i). - **متغيرات القرار:** هي الخيارات التي نتخذها في كل خطوة. هنا، القرار هو: أي مدينة (j) سنزورها بعد المدينة الحالية (i)؟ **المشكلة الثانية: مسألة حقيبة الظهر (Knapsack Problem)** الفكرة هنا هي أن لدينا حقيبة ظهر بسعة محددة (مثل وزن أقصى) ومجموعة من العناصر، لكل عنصر وزن وقيمة. نريد اختيار مجموعة من العناصر لوضعها في الحقيبة لتعظيم القيمة الإجمالية، دون تجاوز سعة الحقيبة. - **متغيرات الحالة:** تمثل الوضع الحالي. هنا، الحالة يمكن أن تكون: العنصر الحالي الذي نفكر فيه (i)، والسعة المتبقية في الحقيبة (W). - **متغيرات القرار:** هي الخيارات المتاحة لكل عنصر. هنا، القرار هو: هل نأخذ العنصر الحالي (xi = 1) أم نتركه (xi = 0)؟ إذن، بتحليل المشكلتين، نجد أن لكل منهما هدفاً (تقليل المسافة أو تعظيم القيمة) ومتغيرات حالة وقرار تحدد كيفية الوصول للحل الأمثل باستخدام البرمجة الرياضية.

سؤال 4: اذكر ثلاث مشكلات تحسين مُختلفة من عائلة مشكلات تحديد المسار.

الإجابة: س:4: 1) مسألة أقصر مسار (Shortest Path). 2) مسألة البائع المتجول (TSP). 3) مسألة توجيه المركبات (VRP).

خطوات الحل:

1. **الشرح:** لنفهم هذا السؤال. مشكلات تحديد المسار هي نوع من مشكلات التحسين التي تهدف إلى إيجاد أفضل طريق أو مسار بين نقاط معينة، مثل المدن أو المواقع، مع مراعاة قيود مثل المسافة أو الوقت أو التكلفة. السؤال يطلب ذكر ثلاث مشكلات مختلفة من هذه العائلة. **المشكلة الأولى: مسألة أقصر مسار (Shortest Path Problem)** الفكرة هنا هي إيجاد المسار الأقصر بين نقطتين في شبكة (مثل طريق بين مدينتين)، حيث "أقصر" يمكن أن يعني أقل مسافة أو أقل وقت أو أقل تكلفة. مثال: استخدام تطبيق خرائط لإيجاد أسرع طريق للوصول إلى مكان ما. **المشكلة الثانية: مسألة البائع المتجول (Traveling Salesman Problem - TSP)** الفكرة هنا هي إيجاد أقصر مسار يزور مجموعة من المدن كلها مرة واحدة فقط ثم يعود إلى نقطة البداية. هذه المشكلة أكثر تعقيداً من مسألة أقصر مسار لأنها تتطلب زيارة جميع النقاط. مثال: تخطيط route لشاحنة توصيل تزور عدة عملاء في مدينة. **المشكلة الثالثة: مسألة توجيه المركبات (Vehicle Routing Problem - VRP)** الفكرة هنا هي تطوير على مشكلة البائع المتجول، حيث لدينا عدة مركبات (مثل شاحنات) وعدد من العملاء، والهدف هو إيجاد مجموعة من المسارات للمركبات لتلبية طلبات العملاء بأقل تكلفة، مع قيود مثل سعة كل مركبة ومواعيد التسليم. مثال: شركة لوجستية تخطط مسارات لأسطول شاحناتها لتوصيل بضائع إلى عملاء متعددين. إذن، هذه المشكلات الثلاث تندرج تحت عائلة مشكلات تحديد المسار، ولكل منها تطبيقات عملية في مجالات مثل النقل واللوجستيات والتخطيط.

سؤال ٣: قم بتحليل مشكلتين من مشكلات التحسين يمكن حلهما باستخدام البرمجة الرياضية، ثم حدد متغيرات الحالة ومتغيرات القرار الخاصة بهما.

• أ) مشكلة النقل: متغيرات الحالة: الطلب والعرض، متغيرات القرار: كميات النقل بين المصادر والأهداف.
• ب) مشكلة الجدولة: متغيرات الحالة: الوقت المتاح، متغيرات القرار: توقيت المهام.
• ج) مشكلة التخزين: متغيرات الحالة: سعة التخزين، متغيرات القرار: كميات المخزون.
• د) مشكلة التوزيع: متغيرات الحالة: مواقع التوزيع، متغيرات القرار: مسارات التوزيع.

الإجابة الصحيحة: مثال 1: مشكلة تخصيص الموارد - متغيرات الحالة: الموارد المتاحة، متغيرات القرار: كمية الموارد المخصصة لكل نشاط. مثال 2: مشكلة جدولة الإنتاج - متغيرات الحالة: الطاقة الإنتاجية، متغيرات القرار: كميات الإنتاج لكل منتج.

الشرح: البرمجة الرياضية تستخدم لحل مشكلات التحسين من خلال تحديد متغيرات القرار التي تؤثر على متغيرات الحالة لتحقيق هدف معين مثل تعظيم الربح أو تقليل التكلفة.

تلميح: فكر في مشكلات واقعية تتضمن موارد محدودة وأهداف قابلة للقياس.

سؤال ٤: اذكر ثلاث مشكلات تحسين مختلفة من عائلة مشكلات تحديد المسار.

• أ) مشكلة البائع المتجول، مشكلة أقصر مسار، مشكلة تحديد مسار المركبات.
• ب) مشكلة تخصيص الموارد، مشكلة الجدولة، مشكلة التخزين.
• ج) مشكلة البرمجة الخطية، مشكلة البرمجة غير الخطية، مشكلة البرمجة الصحيحة.
• د) مشكلة التحكم الأمثل، مشكلة التحسين الديناميكي، مشكلة التحسين العشوائي.

الإجابة الصحيحة: 1. مشكلة البائع المتجول (TSP). 2. مشكلة أقصر مسار (Shortest Path). 3. مشكلة تحديد مسار المركبات (VRP).

الشرح: مشكلات تحديد المسار تتضمن إيجاد المسار الأمثل بين نقاط معينة، وتستخدم في مجالات مثل النقل والخدمات اللوجستية.

تلميح: تذكر المشكلات الكلاسيكية في نظرية الشبكات والتحسين.

اذكر مشكلتين من مشكلات التحسين التي يمكن حلها باستخدام البرمجة الرياضية، مع تحديد متغيرات الحالة ومتغيرات القرار لكل منهما.

الإجابة: يمكن حل العديد من مشكلات التحسين باستخدام البرمجة الرياضية. مثالان هما: 1. **مشكلة تخصيص الموارد (Resource Allocation Problem):** * **مشكلة التحسين:** تعظيم الأرباح أو تقليل التكاليف عند تخصيص موارد محدودة (مثل العمالة، الآلات، المواد الخام) لإنتاج منتجات مختلفة. * **متغيرات الحالة:** الكميات المتوفرة من كل مورد، تكلفة كل مورد، الربح أو التكلفة المرتبطة بإنتاج وحدة واحدة من كل منتج. * **متغيرات القرار:** كمية كل منتج سيتم إنتاجه. 2. **مشكلة الجدول الزمني للإنتاج (Production Scheduling Problem):** * **مشكلة التحسين:** تحديد أفضل تسلسل لإنتاج مجموعة من المنتجات على خط إنتاج واحد لتقليل وقت التوقف أو زيادة الإنتاجية. * **متغيرات الحالة:** أوقات الإعداد بين المنتجات المختلفة، أوقات الإنتاج لكل منتج، الكمية المطلوبة من كل منتج. * **متغيرات القرار:** ترتيب إنتاج المنتجات.

الشرح: البرمجة الرياضية هي أداة قوية تستخدم لوصف وتحسين النظم المعقدة. تتطلب هذه المشكلات تحديد المتغيرات التي يمكن التحكم فيها (متغيرات القرار) والمقيدات والعوامل الثابتة (متغيرات الحالة).

تلميح: فكر في سيناريوهات واقعية تتطلب اتخاذ قرارات تتعلق بالكميات أو التسلسل لتعظيم منفعة أو تقليل خسارة.

ما هي عائلة مشكلات تحديد المسار؟ اذكر ثلاث مشكلات مختلفة منها.

الإجابة: عائلة مشكلات تحديد المسار (Pathfinding Problems) تتعلق بإيجاد المسار الأمثل بين نقطتين أو أكثر في شبكة أو رسم بياني. ثلاث مشكلات مختلفة منها هي: 1. **مشكلة أقصر مسار (Shortest Path Problem):** إيجاد المسار ذي أقل وزن (مثل المسافة، الوقت، التكلفة) بين عقدتين في رسم بياني. 2. **مشكلة المسار الأطول (Longest Path Problem):** إيجاد المسار ذي أكبر وزن بين عقدتين في رسم بياني (تكون مفيدة في بعض التطبيقات مثل تحليل المسارات الحرجة). 3. **مشكلة دورة البائع المتجول (Traveling Salesperson Problem - TSP):** إيجاد أقصر مسار يمر بكل عقدة في الرسم البياني مرة واحدة ويعود إلى نقطة البداية.

الشرح: تحديد المسار هو مفهوم أساسي في علوم الحاسوب والشبكات، ويشمل العديد من الخوارزميات والتطبيقات العملية مثل التوجيه في شبكات الاتصالات، تخطيط المسارات اللوجستية، وإيجاد أفضل طريق للمركبات الذاتية.

تلميح: تخيل خرائط جوجل وكيف تحدد المسارات. ما هي أنواع المسارات المختلفة التي يمكن البحث عنها؟