صور من ويكيبيديا
لمن هم أكثر دراية بالموضوع ، ربما تعلمون أن أصول البرمجة الخطية بدأت تقريبًا في منتصف الخمسينيات من القرن الماضي ، وعالم الرياضيات باسم جورج دانتزيغ كان متورطا. إذا كان هذا هو تخمينك ، فستكون على حق في معظم الأحيان ، لكننا نعلم جميعًا أن عزو الفضل للعديد (إن لم يكن كل) الاكتشافات العلمية والرياضية ليس بهذه البساطة - غالبًا ما يكون هناك أكثر من فرد ساهم في تطوير مجال البحث ، وهذا بالتأكيد هو الحال بالنسبة للبرمجة الخطية. تم إحراز تقدم أولي بالتوازي من قبل عالمين رياضيين يعملان بشكل مستقل في منتصف القرن العشرين ، وبالتالي كان الائتمان بالتأكيد يرجع إلى أكثر من شخص واحد.
دون الدخول في التاريخ كثيرًا ، دعنا نحاول الحصول على إحساس تقريبي بالجدول الزمني للتطورات الرئيسية في البرمجة الخطية. تشعبت الفكرة الأولى للبرمجة الخطية من ليونيد كانتوروفيتشنية لخفض التكاليف لجيشه مع زيادة جيش العدو. بُذلت جهوده خلال الحرب العالمية الثانية في عام 2 لكن الاتحاد السوفيتي أهملها في ذلك الوقت. في أثناء، تي سي كوبمانز كان لديه فكرة مماثلة لـ Kantorovich ولكنه كان يعمل عليها بشكل مستقل وتم تصميمها لتناسب تطبيقاته الاقتصادية الخاصة. بعد بضع سنوات ، في عام 1941 ، بدأ فرانك لورين هيتشكوك في العمل على أفكار مماثلة ، والتي تم تصميمها مرة أخرى وفقًا لمشاكل النقل الخاصة به ، لكنه طور حلاً مشابهًا لما يُعرف الآن بالطريقة البسيطة. لاختصار الأمر ، كان الرجال الثلاثة يسيرون على الطريق الصحيح ، ولكن بحلول الوقت الذي يستحق فيه الاكتشاف جائزة نوبل في الاقتصاد ، توفي هيتشكوك ، وهكذا حصل كانتوروفيتش وكوبمانز على الفضل في ذلك.
بين عامي 1946 و 1947 ، طور جورج ب. دانتزيغ خوارزمية لطريقة Simplex التي بكفاءة معالجة مشاكل البرمجة الخطية في معظم الحالات - كان هذا إنجازًا رائعًا. بعد ذلك بوقت قصير ، قدم Dantzig نظرية الازدواجية في البرمجة الخطية إلى John Von Neumann ، الذي كان يطور نظرية الألعاب ، وكان مندهشًا عندما اكتشف أن Dantzig قد أحرز تقدمًا في مشكلة لم يتم حلها في البرمجة الخطية. كان هذا مثيرًا للغاية. (Good Will Hunting ، أي شخص؟ كان إنجاز Dantzig في الواقع مصدر إلهام لقصة ذلك الفيلم!).
تمت الآن دراسة هذه المناطق جيدًا واستخدامها بكثافة في تطبيقات الحياة الواقعية المهمة. بعد الحرب العالمية الثانية ، تم تطبيق عمل Dantzig على تطبيقات التخطيط اليومية في العديد من الصناعات ، وسرعان ما أحرز علماء الرياضيات تقدمًا في جعل البرمجة الخطية قابلة للحل في وقت متعدد الحدود. كانت هذه بعض المعلومات الأساسية عن أصولها (ويمكنك قراءة كل شيء عنها هنا، على سبيل المثال) ، ولكن في الوقت الحالي ، دعونا ندخل بإيجاز إلى التطورات الحديثة.
في الآونة الأخيرة ، ركز البحث في البرمجة الخطية على تطوير الخوارزميات التي تعمل على تحسين التعقيد الحسابي. هذه الورقة، على سبيل المثال ، يناقش انعكاسات المصفوفة الديناميكية الأسرع للحصول على LPs أسرع. (ومع ذلك ، فهو ثقيل في علوم الكمبيوتر ، ولسنا بحاجة إلى الدخول فيه). إجمالي، هناك الكثير من البحث الخوض في التحسين الرياضي اليوم ككل ، سواء كان ذلك لتسريع العمليات الحسابية أو تقليل أوجه القصور أو تقديم تطبيقات جديدة في التعلم الآلي.
هناك حزم برامج لا حصر لها لدعم البرمجة الخطية التطبيقية في الصناعة. لديك آي بي إم CPLEX, جوروبي برنامج تحسين مملوك ، حزم Python مفتوحة المصدر (مثل SciPy, بيومو, PuLP, جيكو) وربما أكثر من ذلك بكثير. حقيقة مثيرة للاهتمام هي أن كل هذه الحزم تستخدم ما نسميه لغة النمذجة الجبرية (AML)، نموذج حاسم تم تطويره في أواخر السبعينيات. كل هذه الحزم رائعة فيما تفعله لأسباب مختلفة وهناك العديد من منشورات المدونة التي يمكنك قراءتها للحصول على مقارنة جيدة بين كل منها - تحقق من هذا آخر، فمثلا.
لن ندخل في التفاصيل ، لكن دعنا نتحدث عما يجب أن تعرفه كمستخدم لنظرية ومنهجية البرمجة الخطية. تعتبر نظرية البرمجة الخطية جميلة من تلقاء نفسها ولكنها أكثر من ذلك عندما يمكنك رسم الروابط بين البرمجة الخطية والجبر الخطي. سواء كنت قد التقطت ملف الكتاب المدرسي، تولى دورة تمهيدية عبر الإنترنتالطرق أو تعلمت هذا رسميا في المدرسة، ليس هناك شك في أنك ستصل إلى نفس النتيجة التي مفادها أن البرمجة الخطية هي حالة خاصة من الجبر الخطي ، وربما أحد أهم الامتدادات ذات الصلة بالجبر الخطي الأولي.
بغض النظر عن المسار الذي اخترت أن تسلكه لتعلم البرمجة الخطية ، فمن المحتمل أنك واجهت التسلسل التالي (أو ما شابه) من الموضوعات:
- مكونات البرنامج الخطي
- أشكال البرامج الخطية
- مشاكل البرمجة الخطية الشائعة
- نظرية الازدواجية وتحليل الحساسية
- أنواع متخصصة من البرامج الخطية
- البرمجة الخطية التطبيقية
(هل يبدو هذا صحيحًا؟ إذا فاتني أي شيء ، فالرجاء ترك تعليق أدناه.) إذا كان هذا هو الحال وقلت أنك على دراية بكل هذه الموضوعات ، فأعتقد أنه يجب عليك التوقف عن القراءة هنا وتسميتها بـ اليوم (وتهنئ نفسك لأنك تعاملت للتو مع تاريخ قصير من البرمجة الخطية!). ومع ذلك ، إذا كان أحد الموضوعات المذكورة أعلاه على الأقل يبدو جديدًا بالنسبة لك ، فسأقول إنه يجب عليك مواصلة قراءة هذه المقالة لأنني أعتقد أنها تستحق وقتك.
من أجل الحفاظ على الأشياء قصيرة وقابلة للاستهلاك ، سنقوم بتخطي أول موضوعين في التسلسل ، ولكن هنا مورد جيد حيث يمكنك معرفة المزيد عن مكونات البرنامج الخطي وأشكال البرامج الخطية. وبالمثل ، سوف نحذف مناقشة نظرية الازدواجية وتحليل الحساسية ولكن بعض الموارد العظيمة كذلك هنا و هنا.
الآن ، إذا كنت تحاول تطبيق مبادئ البرمجة الخطية لحل مشكلة ما ، فمن المحتمل أن تكون هناك فئات أخرى متنوعة من النماذج التي فكرت فيها لمشكلتك ، وقد توصلت (على الأرجح بشكل معقول) إلى استنتاج مفاده أن نموذج البرمجة الخطية من شأنه أن يحل مشكلتك. إذا كان الأمر كذلك ، فقد يكون السبب هو أنك فكرت أيضًا في بعض المشكلات الكلاسيكية التي تستخدم البرمجة الخطية: مشكلة المزج, مشكلة التخصيص, مشكلة النقل, مشكلة البائع المتجول، وأكثر من ذلك بكثير.
إذا كانت مشكلتك تبدو تقريبًا مثل أي من هذه المشكلات ، فنحن نعرف بالفعل كيفية حل مشكلتك وأنت على ما يرام. إذا لم يكن الأمر كذلك ، فستحتاج إلى التفكير بشكل أعمق في مشكلتك واكتشاف طريقة لترجمتها بذكاء إلى مشكلة برمجة خطية. ضع في اعتبارك بعض الأسئلة مثل:
- هل حاجة LP لحل هذه المشكلة ، أو هل هناك احتمال أن تكون هذه مشكلة تافهة؟
- ما هو هدفك الرئيسي؟
- هل لديك هدف واحد فقط أم هناك الكثير؟
- هل هي مشكلة تعظيم أم مشكلة تصغير؟
- ما هي كل القيود الممكنة التي يمكنك التفكير فيها؟
- هل متغيرات قرارك كلها غير سلبية ، أم أنك بحاجة إلى نوع خاص من المواصفات؟
لقد قمت بالكثير من الشرح في الوقت الحالي ، لذا بدلاً من التحدث أكثر ، سأريكم فقط ما قد تبدو عليه مشكلة البرمجة الخطية المطبقة "غير القياسية" ، في الكود. إذا كنت تتذكر ، قلنا أن هناك العديد من حزم Python مفتوحة المصدر المتاحة والتي تستخدم نموذج AML. PuLP هو واحد منهم ، لذلك سنستخدم PuLP في الوقت الحالي.
هذا مثال شبه افتراضي يحتوي على 12 مأوى للمشردين من واقع الحياة الواقعية في مدينة تورنتو - عناوين واقعية ومباني واقعية وعدد وهمي للغرف / الأسرة المتاحة (أي العرض / السعة) ، وعدد وهمي من جديد. طلبات الأسرّة (أي حسب الطلب) ، "مجموعة" مزيفة ينتمي إليها المأوى. موضوع قاتم ، وأنا أعلم. تم الحصول على البيانات من المدينة افتح كتالوج البيانات.
كود المؤلف
لنفترض أننا ننظر إلى أي لقطة عشوائية يومية للعرض والطلب على الأسرة في ملاجئ المشردين في تورنتو. تم اختيار ملاجئ المشردين التي ننظر إليها بشكل استراتيجي بحيث ننظر إلى التجمعات المنتشرة في جميع أنحاء المدينة - بعض الملاجئ قريبة من البعض الآخر ، في حين أن بعضها بعيد عن متناول البعض الآخر. ضع ذلك في اعتبارك لأن هذا وثيق الصلة بمشكلة التحسين التي سنحددها. لاحظ أن الطلب على مستوى الكتلة وليس على مستوى المأوى.
علاوة على ذلك ، هناك تكاليف (مالية وزمنية) مرتبطة بكل سرير إضافي يتم توفيره في الملجأ ، وتختلف التكاليف - أحيانًا حسب المأوى وأحيانًا حسب المجموعة. سنقوم بتعريف المجموعة على أنها مجموعة من الملاجئ القريبة نسبيًا من بعضها البعض - صورة "خريطة" تقريبية للمواقع المرتبطة ببعضها البعض أدناه.
بالإضافة إلى التكلفة المالية ، دعنا نقول أن هناك أيضًا تكلفة زمنية مرتبطة بفتح كل سرير إضافي - أحيانًا عن طريق المأوى وأحيانًا حسب المجموعة. السبب وراء هذه التكلفة الزمنية هو أنه قد يكون هناك طلب على سرير داخل الحي / المجموعة ، ولكن تم تقديم الطلب في موقع كامل السعة ويحتاج مستخدم الخدمة إلى الانتقال.
سنقوم بإعداد هذا كملف مشكلة التحسين متعددة الأهداف لذلك يجب أن تكون مواصفاتنا (في الكود) قادرة على استيعاب ذلك. أولاً ، نقوم بتقليل التكلفة المالية ، ثم نقوم بتقليل تكاليف الوقت. المعامِلات في دالة الهدف الثانية تتوافق مع الزيادة الزمنية النسبية ضمن مجموعة مأوى معينة (أي تكلفة الوقت لنقل المستخدمين الجدد من المأوى X إلى المأوى Y). لاحظ أن مواصفات مشكلة التحسين ليست فريدة وقد يكون هناك أكثر من مواصفة تؤدي إلى نفس النتائج.
هذا هو كل الكود كبرنامج نصي طويل. يمكن تكثيف / تبسيط كود مواصفات النموذج ، لكننا سنحتفظ به على هذا النحو حتى تتمكن من رؤية جميع التفاصيل بشكل أكثر وضوحًا. نعلق على دالة الهدف الأولية لأننا أضفناها كقيود تكلفة نقدية في الخطوة رقم 5.
كود المؤلف
إذا قمت بتشغيل هذا الرمز محليًا ، فسترى الإخراج على النحو التالي:
A:2671Islington: 1 additional bed(s). B1:26Vaughan: 0 additional bed(s). B2:14Vaughan: 5 additional bed(s). C:850Bloor: 1 additional bed(s). D1:38Bathurst: 2 additional bed(s). D2:38Bathurst: 1 additional bed(s). E1:135Sherbourne: 6 additional bed(s). E2:339George: 5 additional bed(s). E3:339George: 4 additional bed(s). E4:339George: 0 additional bed(s). E5:339George: 0 additional bed(s). E6:339George: 4 additional bed(s). Optimal Value of Objective Function: 36.9
قد يكون سؤالك الأول: أليست هذه مشكلة تافهة؟ وإذا لم يحدث ذلك ، فكيف يحدث ذلك؟ هذا سؤال مهم ، وقد يبرر عدم تحديد مشكلة البرمجة الخطية على الإطلاق! ومع ذلك ، في هذه الحالة ، إنها مشكلة غير بسيطة ونحتاج إلى مواصفات LP ، فكر في السبب.
ملحوظة: أولاً ، نقوم بتقليل التكاليف المالية ، ثم نقوم بتقليل تكاليف الوقت. هل يمكنك التفكير في طريقة لحل هذه المشكلة يدويًا؟
مراجع حسابات
[1] بي كولمان وري بيك ، البرمجة الخطية الابتدائية مع التطبيقات (1995) ، ScienceDirect
[2] GB Dantzig ، ذكريات حول أصول البرمجة الخطية (1982) قسم بحوث العمليات - جامعة ستانفورد
[3] R. Fourer، DM Gay، BW Kenighan، لغة نمذجة للبرمجة الرياضية 1990
مريم ولاء تخصص في الرياضيات مع أكثر من 3 سنوات من الخبرة كعالم بيانات في الهندسة وتجارة التجزئة والأوساط الأكاديمية تعمل على مجموعة متنوعة من المشكلات التي تتراوح من معالجة اللغة الطبيعية وأنظمة التوصية إلى البرمجة الخطية والتحسين.
- محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
- بلاتوبلوكشين. Web3 Metaverse Intelligence. تضخيم المعرفة. الوصول هنا.
- المصدر https://www.kdnuggets.com/2023/02/linear-programming-101-data-scientists.html?utm_source=rss&utm_medium=rss&utm_campaign=linear-programming-101-for-data-scientists
