متفرقات

التحسين | الرياضيات

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

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

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

تُعرف فئة مهمة من التحسين بالبرمجة الخطية. يشير الخطي إلى أنه لا توجد متغيرات مرفوعة لقوى أعلى ، مثل المربعات. بالنسبة لهذه الفئة ، تتضمن المشكلات تصغير (أو تعظيم) دالة هدف خطية تكون متغيراتها أرقامًا حقيقيةالتي يتم تقييدها لتلبية نظام من المساواة الخطية وعدم المساواة. تُعرف فئة مهمة أخرى من التحسين بالبرمجة غير الخطية. في البرمجة غير الخطية ، المتغيرات هي أرقام حقيقية ، والهدف أو بعض القيود هي وظائف غير خطية (ربما تتضمن مربعات أو جذور تربيعية أو دوال مثلثية أو منتجات المتغيرات). تمت مناقشة كل من البرمجة الخطية وغير الخطية في هذه المقالة. تشتمل الفئات المهمة الأخرى من مشكلات التحسين التي لم يتم تناولها في هذه المقالة على البرمجة العشوائية ، حيث يكون ملفتعتمد الوظيفة الموضوعية أو القيود على المتغيرات العشوائية ، بحيث يتم العثور على الأمثل في بعض المعاني "المتوقعة" أو الاحتمالية ؛ تحسين الشبكة ، والذي يتضمن تحسين بعض خصائص التدفق عبر الشبكة ، مثل تعظيم كمية المواد التي يمكن نقلها بين موقعين معينين في الشبكة ؛ والتحسين التوافقي ، حيث يجب إيجاد الحل ضمن مجموعة محدودة ولكن كبيرة جدًا من القيم الممكنة ، مثل الطرق العديدة الممكنة لتعيين 20 مصنعًا في 20 موقعًا.

احصل على اشتراك Britannica Premium وتمتع بالوصول إلى محتوى حصري إشترك الآن

البرمجة الخطية

الأصول والتأثيرات

على الرغم من أنها تستخدم الآن على نطاق واسع لحل مشاكل القرار اليومية ، إلا أن البرمجة الخطية كانت غير معروفة نسبيًا قبل عام 1947. لم يتم تنفيذ أي عمل ذي أهمية قبل هذا التاريخ ، على الرغم من أن عالم الرياضيات الفرنسي جوزيف فورييه بدا على دراية بإمكانيات هذا الموضوع في وقت مبكر من عام 1823. في عام 1939 ، نشر عالم الرياضيات الروسي ليونيد فيتاليفيتش كانتوروفيتش دراسة موسعة بعنوان Matematicheskie metody Organizatsi i planirovaniya proizvodstva ("الطرق الرياضية لتنظيم وتخطيط الإنتاج") ، والتي يُنسب إليها الآن كونها أول أطروحةلإدراك أن بعض الفئات الواسعة الهامة من مسائل الجدولة لها هياكل رياضية محددة جيدًا. لسوء الحظ ، ظلت مقترحات كانتوروفيتش غير معروفة في الغالب في كل من الاتحاد السوفيتي وأماكن أخرى لما يقرب من عقدين من الزمن. في غضون ذلك ، تطورت البرمجة الخطية بشكل كبير في الولايات المتحدة وأوروبا الغربية. في الفترة التي أعقبت الحرب العالمية الثانية ، توصل المسؤولون في حكومة الولايات المتحدة إلى الاعتقاد بأن التنسيق الفعال لطاقات وموارد أمة بأكملها في حالة نشوب حرب نووية يتطلب استخدام تقنيات التخطيط العلمي. جعل ظهور الكمبيوتر مثل هذا النهج ممكنًا .

بدأ العمل المكثف في عام 1947 في سلاح الجو الأمريكي. تم اقتراح نموذج البرمجة الخطية لأنه كان بسيطًا نسبيًا من وجهة نظر رياضية ، ومع ذلك فقد قدم إطارًا عامًا وعمليًا بدرجة كافية لتمثيل الأنشطة المترابطة التي تشترك في الموارد النادرة. في نموذج البرمجة الخطية ، يرى المصمم النظام المطلوب تحسينه على أنه مكون من أنشطة مختلفة يفترض أنها تتطلب تدفق المدخلات (على سبيل المثال ، العمالة والمواد الخام) والمخرجات (على سبيل المثال ، السلع الجاهزة والخدمات) من مختلف أنواع تتناسب مع مستوى النشاط. يُفترض أن تكون مستويات النشاط قابلة للتمثيل بأرقام غير سالبة. تكمن السمة الثورية للنهج في التعبير عن الهدف من عملية اتخاذ القرار من حيث تقليل أو تعظيم وظيفة موضوعية خطية - على سبيل المثال ،القوة الجوية ، أو تعظيم الأرباح في الصناعة. قبل عام 1947 ، تميز كل التخطيط العملي بسلسلة من القواعد الإجرائية والأولويات المفروضة بشكل رسمي. لم يتم تحديد الأهداف العامة مطلقًا ، ربما بسبب استحالة إجراء الحسابات اللازمة لتقليل وظيفة موضوعية في ظل قيود. في عام 1947 ، تم تقديم طريقة (موصوفة في القسم طريقة simplex ) تبين أنها تحل المشكلات العملية بكفاءة. نما الاهتمام بالبرمجة الخطية بسرعة ، وبحلول عام 1951 انتشر استخدامها في الصناعة. يكاد يكون من المستحيل اليوم تسمية صناعة لا تستخدم البرمجة الرياضية في شكل ما ، على الرغم من اختلاف التطبيقات ومدى استخدامها بشكل كبير ، حتى داخل نفس الصناعة.

امتد الاهتمام بالبرمجة الخطية أيضًا ليشمل الاقتصاد. في عام 1937 عالم الرياضيات المجري المولدقام جون فون نيومان بتحليل الاقتصاد المتوسع باطراد بناءً على طرق الإنتاج البديلة والمعاملات التكنولوجية الثابتة. بقدر ما يتعلق الأمر بالتاريخ الرياضي ، فإن دراسة أنظمة عدم المساواة الخطية لم تثير أي اهتمام تقريبًا قبل عام 1936. في عام 1911 ، تم اقتراح حركة من قمة إلى قمة على طول حواف متعدد السطوح (كما هو الحال في الطريقة البسيطة) كطريقة حل مشكلة تضمنت التحسين ، وفي عام 1941 تم اقتراح الحركة على طول الحواف لمشكلة تتعلق بالنقل. من المحتمل أن يعود الفضل في وضع الكثير من الأسس الرياضية إلى فون نيومان. في عام 1928 نشر ورقته البحثية الشهيرة علىتوجت نظرية الألعاب وعمله في عام 1944 بنشر النظرية الكلاسيكية للألعاب والسلوك الاقتصادي بالتعاون مع الاقتصادي النمساوي أوسكار مورجنسترن . في عام 1947 ، توقع فون نيومان تكافؤ البرامج الخطية وألعاب المصفوفة ، وقدم المفهوم المهم لـالازدواجية ، وقدمت عدة مقترحات للحل العددي للبرمجة الخطية ومشاكل اللعبة. بدأ الاهتمام الجاد من قبل علماء الرياضيات الآخرين في عام 1948 مع التطور الصارم للازدواجية والمسائل ذات الصلة.

تمت برمجة طريقة simplex العامة لأول مرة في عام 1951 لحساب مكتب الولايات المتحدة للمعايير SEAC. بدءًا من عام 1952 ، تمت برمجة طريقة simplex لاستخدامها على أجهزة كمبيوتر IBM المختلفة ولاحقًا لتلك الخاصة بشركات أخرى. نتيجة لذلك ، نمت التطبيقات التجارية للبرامج الخطية في الصناعة والحكومة بسرعة. استمر تطوير تقنيات حسابية جديدة وتنوعات من التقنيات القديمة.

More recently there has been much interest in solving large linear problems with special structures—for example, corporate models and national planning models that are multistaged, are dynamic, and exhibit a hierarchical structure. It is estimated that certain developing countries will have the potential of increasing their gross national product (GNP) by 10 to 15 percent per year if detailed growth models of the economy can be constructed, optimized, and implemented.