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

الكتاب: كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 | المادة: الذكاء الإصطناعي | المرحلة: الصف 12 | الفصل الدراسي: 1

الدولة: المملكة العربية السعودية | المنهج: المنهج السعودي - وزارة التعليم

الدرس: برمجة الأعداد الصحيحة المختلطة ومشكلة البائع المتجول

📚 معلومات الصفحة

الكتاب: كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 | المادة: الذكاء الإصطناعي | المرحلة: الصف 12 | الفصل الدراسي: 1

الدولة: المملكة العربية السعودية | المنهج: المنهج السعودي - وزارة التعليم

نوع المحتوى: درس تعليمي

مستوى الصعوبة: متوسط

📝 ملخص الصفحة

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

يتم شرح كيفية استخدام أداة numpy.full لإنشاء مصفوفة لتخزين المتغيرات الثنائية، ثم صياغة الدالة الموضوعية للمشكلة التي تحسب المسافة الكلية للرحلة من خلال ضرب مسافة كل انتقال في متغير القرار المناسب.

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

📄 النص الكامل للصفحة

{i}) == 1 # exactly 1 arrival solver += xsum(x[j,i] for j in location_ids - {i}) == 1 # exactly 1 departure ``` * **Section 8 (Page Number)**: * Type: `metadata` * Content Classification: `METADATA` * Content: "290" * **Section 9 (Ministry of Education Logo)**: This is a visual element, not a text section. I will put it in `visual_elements`. **Revisiting Visual Elements:** The "Ministry of Education" logo is present. I should include it in `visual_elements`. **Final Check:** * Language: `ar` * Direction: `rtl` * Page Context: Inferred title, type, topics. No questions/formulas/examples in *chemistry* sense. * Sections: All text and code blocks extracted. Classified correctly. Question indicators are false. * Visual Elements: Ministry of Education logo. The user explicitly mentioned "chemistry textbook page" and "questions 93-106", "Table 9-1", "Figure 26-1". Since the image is clearly *not* a chemistry page, I must address this discrepancy. I will proceed with extracting the content as it appears, which is programming-related, and set `has_questions`, `has_formulas`, `has_examples` (in the chemistry context) to `false` or `true` based on the *actual* content. The `page_title` and `main_topics` will reflect the programming content. I will set `has_examples` to `true` because the Python code blocks serve as programming examples. `has_formulas` will be `false` as there are no chemical formulas. `has_questions` will be `false` as there are no explicit questions like 93-106. `has_visual_elements` will be `true` due to the Ministry of Education logo. Let's refine the `page_context` and `sections` based on the actual content. **Page Context Refinement:** * `page_title`: "برمجة وحل مشكلات التحسين باستخدام مكتبة MIP" (Programming and Solving Optimization Problems using MIP Library) - This is a good fit for the content. * `page_type`: `lesson_content` * `main_topics`: ["برمجة الأعداد الصحيحة المختلطة", "مشكلة البائع المتجول", "مكتبة MIP في بايثون", "صياغة الدوال الموضوعية", "قيود البرمجة"] (Mixed-Integer Programming, Traveling Salesperson Problem, Python MIP Library, Objective Function Formulation, Programming Constraints). * `headers`: No explicit headers, but the introductory sentences serve as context. I will leave this empty or infer from the first sentence. Given the instruction "all headers found", and no explicit headers like "Chapter 1" or "Introduction", I will leave it as an empty array. * `has_questions`: `false` * `has_formulas`: `false` (no chemistry formulas, only programming logic/expressions) * `has_examples`: `true` (the code blocks are examples) * `has_visual_elements`: `true` (due to the logo) **Sections Refinement:** * **Section 1**: * `order`: 1 * `type`: `main_content` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: "يستخدم المقطع البرمجي التالي مكتبة البايثون mip لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة، ثم يضيف متغير قرار ثنائي لكل انتقال ممكن في نسخة مشكلة البائع المتجول التي تم إنشاؤها سابقًا." * **Section 2 (Code Block 1)**: * `order`: 2 * `type`: `example` (as it's a code example) * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: (The Python code block) * **Section 3**: * `order`: 3 * `type`: `main_content` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: "يستخدم المقطع البرمجي السابق أداة ()numpy.full لإنشاء مصفوفة NxN بحجم لتخزين المتغيرات الثنائية x." * **Section 4**: * `order`: 4 * `type`: `main_content` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: "بعد إضافة متغيرات القرار x، يمكن استخدام المقطع البرمجي التالي لصياغة وحساب الدالة الموضوعية لمشكلة البائع المتجول. حيث تقوم الدالة بالتكرار على كل انتقال ممكن i ← j وتضرب مسافتها dist_matrix[i,j] مع متغير قرارها x[i,j]. وإذا تم إدراج الانتقال في الحل سيؤخذ 1=x[i,j] و dist_matrix[i,j] بعين الاعتبار، وبخلاف ذلك ستضرب dist_matrix[i,j] في صفر ليتم تجاهلها." * **Section 5 (Code Block 2)**: * `order`: 5 * `type`: `example` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: (The Python code block) * **Section 6**: * `order`: 6 * `type`: `main_content` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: "تهدف الخطوة التالية إلى التأكد بأن الخوارزمية تُظهر الحلول التي تتضمن زيارة كل المواقع لمرة واحدة فقط، باستثناء موقع startstop (الانطلاق والتوقف) حسب ما تتطلبه مشكلة البائع المتجول، وزيارة كل موقع مرة واحدة تعني أن الطريق الصحيح يمكن أن:\n• يصل إلى كل موقع مرة واحدة فقط.\n• يغادر من كل موقع مرة واحدة فقط.\nويمكن إضافة قيود الوصول والمغادرة هذه بسهولة كما يلي:" * **Section 7 (Code Block 3)**: * `order`: 7 * `type`: `example` * `content_classification`: `EDUCATIONAL_CONTENT` * `content`: (The Python code block) * **Section 8 (Page Number)**: * `order`: 8 * `type`: `metadata` * `content_classification`: `METADATA` * `content`: "290" **Visual Elements Refinement:** * **Ministry of Education Logo**: * `type`: `image` * `title`: "شعار وزارة التعليم" (Ministry of Education Logo) * `description`: "شعار وزارة التعليم السعودية، يتضمن نص 'وزارة التعليم' باللغة العربية وتاريخ '2025 - 1447' بال{ "language": "ar", "direction": "rtl", "page_context": { "page_title": "برمجة وحل مشكلات التحسين باستخدام مكتبة MIP", "page_type": "lesson_content", "main_topics": [ "برمجة الأعداد الصحيحة المختلطة", "مشكلة البائع المتجول", "مكتبة MIP في بايثون", "صياغة الدوال الموضوعية", "قيود البرمجة" ], "headers": [], "has_questions": false, "has_formulas": false, "has_examples": true, "has_visual_elements": true }, "sections": [ { "order": 1, "type": "main_content", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "يستخدم المقطع البرمجي التالي مكتبة البايثون mip لإنشاء خوارزمية حل برمجة الأعداد الصحيحة المختلطة، ثم يضيف متغير قرار ثنائي لكل انتقال ممكن في نسخة مشكلة البائع المتجول التي تم إنشاؤها سابقًا." }, { "order": 2, "type": "example", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "from itertools import product # used to generate all possible transition\nfrom mip import BINARY\nfrom mip import Model, INTEGER\n\nsolver = Model() # creates a solver\nsolver.verbose = 0 # setting this to 1 will print info on the progress of the solver\n\n# 'product' creates every transition from every location to every other location\ntransitions = list(product(location_ids, location_ids))\n\nN = len(location_ids) # number of locations\n\n# creates a square numpy array full of 'None' values\nx = numpy.full((N, N), None)\n\n# adds binary variables indicating if transition (i->j) is included in the route\nfor i, j in transitions:\n x[i, j] = solver.add_var(var_type = BINARY)" }, { "order": 3, "type": "main_content", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "يستخدم المقطع البرمجي السابق أداة ()numpy.full لإنشاء مصفوفة NxN بحجم لتخزين المتغيرات الثنائية x." }, { "order": 4, "type": "main_content", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "بعد إضافة متغيرات القرار x، يمكن استخدام المقطع البرمجي التالي لصياغة وحساب الدالة الموضوعية لمشكلة البائع المتجول. حيث تقوم الدالة بالتكرار على كل انتقال ممكن i ← j وتضرب مسافتها dist_matrix[i,j] مع متغير قرارها x[i,j]. وإذا تم إدراج الانتقال في الحل سيؤخذ 1=x[i,j] و dist_matrix[i,j] بعين الاعتبار، وبخلاف ذلك ستضرب dist_matrix[i,j] في صفر ليتم تجاهلها." }, { "order": 5, "type": "example", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "# the minimize tool is used then the objective function has to be minimized\nfrom mip import xsum, minimize\n\n# objective function: minimizes the distance\nsolver.objective = minimize(xsum(dist_matrix[i,j]*x[i][j] for i,j in transitions))" }, { "order": 6, "type": "main_content", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "تهدف الخطوة التالية إلى التأكد بأن الخوارزمية تُظهر الحلول التي تتضمن زيارة كل المواقع لمرة واحدة فقط، باستثناء موقع startstop (الانطلاق والتوقف) حسب ما تتطلبه مشكلة البائع المتجول، وزيارة كل موقع مرة واحدة تعني أن الطريق الصحيح يمكن أن:\n• يصل إلى كل موقع مرة واحدة فقط.\n• يغادر من كل موقع مرة واحدة فقط.\nويمكن إضافة قيود الوصول والمغادرة هذه بسهولة كما يلي:" }, { "order": 7, "type": "example", "content_classification": "EDUCATIONAL_CONTENT", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "# for each location id\nfor i in location_ids:\n solver += xsum(x[i,j] for j in location_ids - {i}) == 1 # exactly 1 arrival\n solver += xsum(x[j,i] for j in location_ids - {i}) == 1 # exactly 1 departure" }, { "order": 8, "type": "metadata", "content_classification": "METADATA", "question_indicators": { "has_question_words": false, "has_numbering": false, "has_multiple_choice": false, "has_instruction_words": false }, "title": null, "content": "290" } ], "visual_elements": [ { "type": "image", "title": "شعار وزارة التعليم", "description": "شعار وزارة التعليم السعودية، يتضمن نص 'وزارة التعليم' باللغة العربية وتاريخ '2025 - 1447' بالتقويم الميلادي والهجري على التوالي، مع تصميم رسومي يمثل نقاطًا متصلة.", "axes_labels": null, "data_description": null, "key_values": [], "numeric_data": null, "table_structure": null, "educational_context": "شعار الجهة الناشرة أو المعتمدة للمحتوى التعليمي.", "estimated": false } ] }

🎴 بطاقات تعليمية للمراجعة

عدد البطاقات: 4 بطاقة لهذه الصفحة

ما هو دور مكتبة `mip` في سياق برمجة الأعداد الصحيحة المختلطة (MIP) لمشكلة البائع المتجول؟

الإجابة: تُستخدم مكتبة `mip` في بايثون لإنشاء خوارزمية حل لمشكلة برمجة الأعداد الصحيحة المختلطة. تسمح بإنشاء متغيرات القرار الثنائية (مثل `x[i, j]` للإشارة إلى تضمين انتقال ما) وصياغة الدالة الموضوعية (مثل تقليل المسافة الإجمالية) وإضافة القيود (مثل ضمان زيارة كل موقع مرة واحدة).

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

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

كيف يتم تمثيل متغيرات القرار الثنائية للانتقالات في مشكلة البائع المتجول باستخدام مكتبة `mip`؟

الإجابة: يتم تمثيل متغيرات القرار الثنائية باستخدام `solver.add_var(var_type = BINARY)`. كل متغير، مثل `x[i, j]`، يشير إلى ما إذا كان الانتقال من الموقع `i` إلى الموقع `j` سيتم تضمينه في المسار النهائي (إذا كانت قيمته 1) أو لا (إذا كانت قيمته 0).

الشرح: المتغيرات الثنائية (Binary Variables) هي أساسية في نمذجة القرارات التي تعتمد على الاختيار بين خيارين. في هذه المشكلة، كل انتقال إما أن يكون جزءاً من المسار أو لا يكون.

تلميح: ما هي نوعية القيم التي يمكن أن يأخذها المتغير إذا كان يمثل مجرد اختيار بين شيئين (تضمين أو عدم تضمين)؟

ما هو الهدف من صياغة الدالة الموضوعية في مشكلة البائع المتجول؟

الإجابة: الهدف من صياغة الدالة الموضوعية هو تقليل إجمالي المسافة التي يقطعها البائع. يتم تحقيق ذلك بضرب مسافة كل انتقال ممكن (`dist_matrix[i,j]`) مع متغير القرار المقابل له (`x[i,j]`). إذا كان الانتقال مضمناً (`x[i,j]=1`)، تُضاف مسافته إلى الإجمالي؛ وإلا، يُضرب في صفر ويُهمل.

الشرح: الدالة الموضوعية هي التعبير الرياضي الذي نريد تعظيمه أو تقليله. في مشكلة البائع المتجول الكلاسيكية، نريد تقليل إجمالي تكلفة (المسافة) المسار.

تلميح: ما الذي تسعى مشكلة البائع المتجول إلى تحسينه؟

اشرح القيود التي تضمن زيارة كل موقع مرة واحدة فقط في مشكلة البائع المتجول.

الإجابة: لضمان زيارة كل موقع مرة واحدة فقط، يتم فرض قيدين لكل موقع `i`: 1. **قيد الوصول (Exactly 1 arrival):** يجب أن يكون هناك انتقال واحد فقط يدخل إلى الموقع `i`. رياضيًا: `sum(x[j,i] for j in location_ids - {i}) == 1`. 2. **قيد المغادرة (Exactly 1 departure):** يجب أن يكون هناك انتقال واحد فقط يغادر من الموقع `i`. رياضيًا: `sum(x[i,j] for j in location_ids - {i}) == 1`.

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

تلميح: كيف يمكن منع البائع من الوصول إلى موقع مرتين أو المغادرة منه أكثر من مرة؟