النسخة الأصلية ل هذه القصة ظهرت في مجلة كوانتا.
في عام 1939، عند وصوله متأخرًا إلى دورة الإحصاء في جامعة كاليفورنيا في بيركلي، قام جورج دانتزيج – وهو طالب دراسات عليا في السنة الأولى – بنسخ مسألتين من السبورة، معتقدًا أنهما واجب منزلي. لقد وجد الواجب المنزلي “أصعب من المعتاد”، كما روى لاحقًا، واعتذر للأستاذ لأنه استغرق بعض الأيام الإضافية لإنجازه. وبعد بضعة أسابيع، أخبره أستاذه أنه قام بحل مسألتين مفتوحتين مشهورتين في الإحصاء. سيوفر عمل دانتزيج الأساس لأطروحة الدكتوراه الخاصة به، وبعد عقود من الزمن، سيكون مصدر إلهام للفيلم حسن النية الصيد.
حصل دانتزيج على درجة الدكتوراه في عام 1946، بعد الحرب العالمية الثانية مباشرة، وسرعان ما أصبح مستشارًا رياضيًا للقوات الجوية الأمريكية المشكلة حديثًا. كما هي الحال مع كل الحروب الحديثة، اعتمدت نتيجة الحرب العالمية الثانية على التخصيص الحكيم للموارد المحدودة. ولكن على عكس الحروب السابقة، كان هذا الصراع عالمي النطاق حقًا، وتم الفوز به إلى حد كبير من خلال القوة الصناعية المطلقة. وبوسع الولايات المتحدة ببساطة أن تنتج المزيد من الدبابات، وحاملات الطائرات، وقاذفات القنابل مقارنة بأعدائها. وإدراكًا لذلك، كان الجيش مهتمًا بشدة بمشاكل التحسين، أي كيفية تخصيص الموارد المحدودة بشكل استراتيجي في المواقف التي يمكن أن تتضمن مئات أو آلاف المتغيرات.
كلفت القوات الجوية Dantzig باكتشاف طرق جديدة لحل مشكلات التحسين مثل هذه. ردًا على ذلك، اخترع الطريقة البسيطة، وهي خوارزمية تعتمد على بعض التقنيات الرياضية التي طورها أثناء حل مشكلات السبورة قبل عقد من الزمن تقريبًا.
وبعد مرور ما يقرب من 80 عامًا، لا تزال الطريقة البسيطة من بين الأدوات الأكثر استخدامًا على نطاق واسع عندما يلزم اتخاذ قرار لوجستي أو قرار يتعلق بسلسلة التوريد في ظل قيود معقدة. إنها فعالة وتعمل. وقالت صوفي هويبرتس من المركز الوطني الفرنسي للبحث العلمي (CNRS): “لقد كانت تسير بسرعة دائمًا، ولم يرَ أحد أنها ليست بهذه السرعة”.
وفي الوقت نفسه، هناك خاصية غريبة ألقت بظلالها لفترة طويلة على طريقة دانتزيج. في عام 1972، أثبت علماء الرياضيات أن الوقت الذي يستغرقه إكمال مهمة ما يمكن أن يرتفع بشكل كبير مع زيادة عدد القيود. لذا، بغض النظر عن مدى سرعة هذه الطريقة في الممارسة العملية، فإن التحليلات النظرية قدمت باستمرار سيناريوهات أسوأ الحالات التي تشير ضمنا إلى أن الأمر قد يستغرق وقتا أطول بشكل كبير. وقال هويبرتس: “بالنسبة للطريقة البسيطة، فإن أدواتنا التقليدية لدراسة الخوارزميات لا تعمل”.
ولكن في ورقة بحثية جديدة سيتم تقديمها في ديسمبر في مؤتمر أسس علوم الكمبيوتر، يبدو أن هيبرتس وإليون باخ، وهو طالب دكتوراه في جامعة ميونيخ التقنية، قد تغلبوا على هذه المشكلة. لقد جعلوا الخوارزمية أسرع، وقدموا أيضًا أسبابًا نظرية لعدم تحقق أوقات التشغيل الأسية التي طالما كان يُخشى منها في الممارسة العملية. العمل، الذي يعتمد على نتيجة تاريخية من عام 2001 لدانييل سبيلمان وشانغ هوا تينغ، هو “رائع (و) جميل”، وفقًا لتنغ.
وقال لازلو فيج، عالم الرياضيات في جامعة بون، الذي لم يشارك في هذا الجهد: “إنه عمل تقني مثير للإعجاب للغاية، فهو يجمع ببراعة العديد من الأفكار التي تم تطويرها في خطوط البحث السابقة، (مع إضافة) بعض الأفكار التقنية الجديدة الرائعة حقًا”.
الهندسة المثلى
تم تصميم الطريقة البسيطة لمعالجة فئة من المشكلات مثل هذا: لنفترض أن شركة أثاث تصنع الخزائن والأسرة والكراسي. من قبيل الصدفة، كل خزانة مربحة ثلاث مرات مثل كل كرسي، في حين أن كل سرير مربح مرتين. إذا أردنا أن نكتب هذا كتعبير، باستخدام أ, ب، و ج لتمثيل كمية الأثاث المنتج، يمكننا القول أن إجمالي الربح يتناسب مع 3أ + 2ب + ج.
لتعظيم الأرباح، ما هو عدد المنتجات التي يجب على الشركة إنتاجها من كل منتج؟ الجواب يعتمد على القيود التي يواجهها. لنفترض أن الشركة يمكنها إنتاج 50 عنصرًا شهريًا على الأكثر، لذلك أ + ب + ج أقل من أو يساوي 50. من الصعب صنع الدولاب – لا يمكن إنتاج أكثر من 20 – لذلك أ أقل من أو يساوي 20. تتطلب الكراسي خشبًا خاصًا، وهو متوفر بشكل محدود، لذا ج يجب أن يكون أقل من 24.
تحول الطريقة البسيطة مثل هذه المواقف – على الرغم من أنها تتضمن غالبًا العديد من المتغيرات – إلى مشكلة هندسية. تخيل رسم بياني للقيود لدينا ل أ, ب و ج في ثلاثة أبعاد. لو أ أقل من أو يساوي 20، يمكننا أن نتخيل مستوى على رسم بياني ثلاثي الأبعاد متعامد مع أ المحور، وقطع من خلاله في أ = 20. سنشترط أن الحل يجب أن يقع في مكان ما على هذا المستوى أو أسفله. وبالمثل، يمكننا إنشاء حدود مرتبطة بالقيود الأخرى. مجتمعة، يمكن لهذه الحدود أن تقسم الفضاء إلى شكل معقد ثلاثي الأبعاد يسمى متعدد السطوح.
