الدرس الثالث (١)

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

الفكرة الأساسية

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

الشرح

تبدأ صياغة مشكلة التحسين بتمثيل متغيرات القرار التي يتحكم فيها متخذ القرار، ومتغيرات الحالة التي تعبر عن البيئة الخارجية ولا يمكن ضبطها بشكل مباشر مثل توفر المواد الخام أو العمالة. بعد ذلك يتم بناء الدالة الموضوعية لتحديد هدف التحسين إما بالزيادة كما في الأرباح أو النقصان كما في التكاليف. وتتم إضافة القيود لضمان الالتزام بسعة محددة أو شروط معينة. في مشكلة حقيبة الظهر (The Knapsack Problem)، يتم استخدام متغير قرار ثنائي $x$ يأخذ القيمة $1$ إذا تم اختيار العنصر $i$ أو $0$ بخلاف ذلك، بحيث لا يتجاوز مجموع أوزان العناصر المنتقاة السعة القصوى $C$ وتكون الدالة الموضوعية هي تعظيم مجموع قيم العناصر. أما في مشكلة البائع المتجول (Traveling Salesman Problem)، فتتمثل المشكلة في إيجاد مسار متصل يزور كل موقع مرة واحدة ويعود لموقع البداية، وتتطلب صياغتها استخدام مصفوفة مسافات ومتغيرات ثنائية $x_{i,j}$ تشير إلى الانتقال من الموقع $i$ إلى الموقع $j$. نظراً لأن عدد الطرق الممكنة يتزايد بشكل هائل مع زيادة عدد المواقع بحيث يصل عدد الطرق إلى $N!$ أو $(N-1)!$ في حال وجود موقع بداية محدد، يتم اللجوء إلى برمجة الأعداد الصحيحة المختلطة (MIP) عبر مكتبة البايثون mip لحل هذه المشكلات وإضافة قيود الوصول والمغادرة وقيود الاتصال لضمان عدم وجود طرق منفصلة.

مثال محلول خطوة بخطوة

لنأخذ مثال مشكلة حقيبة الظهر المكونة من ستة عناصر بأوزان وقيم محددة، وبسعة ظهر قصوى تساوي $40$ وحدة. أولاً، يتم استيراد الوحدات الضرورية وتثبيت مكتبة البايثون mip. ثانياً، تُعرّف القيم في مصفوفة values = [20, 10, 23, 15, 7, 7] والأوزان في مصفوفة weights = [5, 10, 19, 8, 11, 2] والسعة C = 40. ثالثاً، يتم إنشاء نموذج الحل solver = Model("knapsack") وإضافة متغيرات القرار الثنائية لكل عنصر باستخدام add_var(var_type = BINARY). رابعاً، تُصاغ الدالة الموضوعية لتعظيم القيمة الإجمالية solver.objective = maximize(sum(values[i] * x[i] for i in I)). خامساً، يُضاف قيد السعة solver += sum(weights[i] * x[i] for i in I) <= C. سادساً، يُنفذ الأمر solver.optimize() لحل المشكلة. وأخيراً، عند التحقق من العناصر المختارة عبر الشرط x[i].x == 1، تظهر العناصر المختارة وهي العنصر $0$ و$2$ و$3$ و$5$ بإجمالي وزن قدره $34$ وقيمة إجمالية قدرها $65$.

أخطاء شائعة

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

سؤالان للتدريب مع الإجابة

السؤال الأول: ماذا تمثل الدالة الموضوعية في مشكلات التحسين وكيف يتم التعبير عنها؟ الإجابة: تمثل الهدف من مشكلة التحسين بزيادتها أو تقليلها (مثل زيادة الربح أو تقليل التكاليف) بناءً على المتغيرات المناسبة، وتتم صياغتها كتعبير رياضي باستخدام المتغيرات والمتباينات الرياضية. السؤال الثاني: ما الغرض الأساسي من استخدام متغيرات القرار الثنائية في مشكلة حقيبة الظهر؟ الإجابة: تُستخدم لتتبع تجميعات العناصر التي ستعبأ في حقيبة الظهر، حيث تكون قيمة المتغير $1$ إذا تم اختيار العنصر للإضافة للحقيبة، و$0$ بخلاف ذلك.