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

الموسوعة الحرة
رسم بياني لسطح معطى بالمعادلة z = f( x , y ) = −( x ² + y ²) + 4. يتم الإشارة إلى القيمة العظمى العالمية عند ( x, y, z ) = (0, 0, 4) بنقطة زرقاء.
بحث نيلدر-ميد عن الحد الأدنى لدالة سيميونيسكو . يتم ترتيب رؤوس سيمبلكس حسب قيمها، حيث يمثل الرقم 1 أدنى قيمة (و(x){\displaystyle f(x)}أفضل قيمة.

التحسين الرياضي ( أو البرمجة الرياضية) هو اختيار أفضل عنصر، وفقًا لمعايير محددة ، من بين مجموعة من البدائل المتاحة. [ 1 ] [ 2 ] وينقسم عمومًا إلى فرعين رئيسيين: التحسين المتقطع والتحسين المستمر . تظهر مسائل التحسين في جميع التخصصات الكمية، بدءًا من علوم الحاسوب والهندسة [ 3 ] وصولًا إلى بحوث العمليات والاقتصاد ، وقد حظي تطوير أساليب الحل باهتمام كبير في الرياضيات لقرون. [ 4 ]

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

مشاكل التحسين

يمكن تقسيم مسائل التحسين إلى فئتين، اعتمادًا على ما إذا كانت المتغيرات متصلة أم منفصلة :

يمكن تمثيل مسألة التحسين بالطريقة التالية:

معطى : دالةو:أ→R{\displaystyle f:A\rightarrow \mathbb {R} }من مجموعة ما A إلى الأعداد الحقيقية
المطلوب: عنصر x 0 ∈ A بحيث يكون f ( x 0 ) ≤ f ( x ) لجميع x ∈ A ("التصغير") أو بحيث يكون f ( x 0 ) ≥ f ( x ) لجميع x ∈ A ("التعظيم").

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

بما أن ما يلي صحيح:

و(x0)≥و(x)⇔-و(x0)≤-و(x)،{\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),}

يكفي حل مسائل التصغير فقط. ومع ذلك، فإن المنظور المعاكس المتمثل في النظر فقط في مسائل التعظيم سيكون صحيحًا أيضًا.

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

عادةً، A هي مجموعة جزئية من الفضاء الإقليديRن{\displaystyle \mathbb {R} ^{n}}غالبًا ما يتم تحديد المجال A للدالة f بمجموعة من القيود أو المعادلات أو المتباينات التي يجب أن تستوفيها عناصره . يُطلق على المجال A للدالة f اسم فضاء البحث أو مجموعة الاختيار ، بينما تُسمى عناصر A بالحلول المرشحة أو الحلول الممكنة .

تُسمى الدالة f بأسماء مختلفة، منها دالة الهدف ، ودالة المعيار ، ودالة الخسارة ، ودالة التكلفة (للتقليل)، [ 6 ] ودالة المنفعة أو دالة اللياقة (للتعظيم)، أو في بعض المجالات، دالة الطاقة أو دالة الطاقة الوظيفية . ويُطلق على الحل الممكن الذي يُقلل (أو يُعظم) دالة الهدف اسم الحل الأمثل .

في الرياضيات، عادةً ما تُصاغ مسائل التحسين التقليدية من حيث التصغير.

يُعرَّف الحد الأدنى المحلي x * بأنه عنصر يوجد له δ > 0 بحيث

∀x∈أأين‖x-x*‖≤دلتا،{\displaystyle \forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,}

العبارة f ( x *) ≤ f ( x ) صحيحة؛

بمعنى آخر، في منطقة معينة حول x ، تكون جميع قيم الدالة أكبر من أو تساوي القيمة عند ذلك العنصر. وتُعرَّف القيم العظمى المحلية بطريقة مماثلة.

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

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

الترميز

تُصاغ مسائل التحسين غالبًا باستخدام رموز خاصة. إليك بعض الأمثلة:

القيمة الدنيا والقيمة القصوى للدالة

ضع في اعتبارك الرموز التالية:

مينx∈R(x2+1){\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)}

يشير هذا إلى القيمة الدنيا لدالة الهدف x² + 1 ، عند اختيار x من مجموعة الأعداد الحقيقيةR{\displaystyle \mathbb {R} }القيمة الدنيا في هذه الحالة هي 1، وتحدث عند x = 0 .

وبالمثل، فإن الترميز

الأعلىx∈R2x{\displaystyle \max _{x\in \mathbb {R} }\;2x}

يطلب السؤال إيجاد القيمة القصوى لدالة الهدف 2x ، حيث x أي عدد حقيقي. في هذه الحالة، لا توجد قيمة قصوى لأن دالة الهدف غير محدودة، لذا فإن الإجابة هي " لانهاية " أو " غير مُعرّفة ".

وسائط الإدخال المثلى

ضع في اعتبارك الرموز التالية:

أرزمأنانx∈(-∞،-1]x2+1،{\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}

أو ما يعادل ذلك

أرزمأنانxx2+1،رهناً بما يلي:x∈(-∞،-1].{\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].}

يمثل هذا قيمة (أو قيم) الوسيط x في الفترة [ −∞,−1] التي تُقلل (أو تُقلل) دالة الهدف x² + 1 (القيمة الدنيا الفعلية لهذه الدالة ليست ما يطلبه السؤال). في هذه الحالة، الإجابة هي x = −1 ، لأن x = 0 غير ممكن، أي أنه لا ينتمي إلى مجموعة الحلول الممكنة .

بصورة مماثلة،

أرزمأxx∈[-5،5]،y∈Rxكوس⁡y،{\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,}

أو ما يعادل ذلك

أرزمأxx،yxكوس⁡y،رهناً بما يلي:x∈[-5،5]،y∈R،{\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}

يمثل الزوج (أو الأزواج) { x , y } الذي يُعظّم (أو يُعظّم) قيمة دالة الهدف x cos y ، مع إضافة شرط أن تقع x في الفترة [−5,5] (مرة أخرى، لا تُؤخذ القيمة القصوى الفعلية للتعبير في الاعتبار). في هذه الحالة، تكون الحلول هي الأزواج من الشكل {5, 2kπ } و {−5, ( 2k + 1) π } ، حيث k عدد صحيح .

تُكتب المعاملات arg min و arg max أحيانًا أيضًا على شكل argmin و argmax ، وهي تعني وسيط الحد الأدنى ووسيط الحد الأقصى .

تاريخ

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

يعود مصطلح " البرمجة الخطية " لبعض حالات التحسين إلى جورج  ب. دانتزيج ، على الرغم من أن ليونيد كانتوروفيتش قدّم جزءًا كبيرًا من النظرية عام 1939. ( لا تشير البرمجة في هذا السياق إلى برمجة الحاسوب ، بل إلى استخدام الجيش الأمريكي لكلمة "برنامج " للإشارة إلى جداول التدريب والإمداد المقترحة ، وهي المشكلات التي درسها دانتزيج آنذاك). نشر دانتزيج خوارزمية سيمبلكس عام 1947، كما عمل جون فون نيومان وباحثون آخرون على الجوانب النظرية للبرمجة الخطية (مثل نظرية الازدواجية ) في نفس الفترة تقريبًا. [ 7 ]

ومن بين الباحثين البارزين الآخرين في مجال التحسين الرياضي ما يلي:

المجالات الفرعية الرئيسية

في عدد من المجالات الفرعية، تم تصميم التقنيات في المقام الأول لتحقيق التحسين في السياقات الديناميكية (أي اتخاذ القرارات بمرور الوقت):

التحسين متعدد الأهداف

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

يُعتبر التصميم "مثاليًا وفقًا لمبدأ باريتو" (أو "فعالًا وفقًا لمبدأ باريتو" أو ضمن مجموعة باريتو) إذا لم يكن متفوقًا عليه أي تصميم آخر: إذا كان أسوأ من تصميم آخر في بعض الجوانب وليس أفضل منه في أي جانب، فإنه يكون متفوقًا عليه وليس مثاليًا وفقًا لمبدأ باريتو.

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

تم تعميم مشاكل التحسين متعددة الأهداف بشكل أكبر إلى مشاكل تحسين المتجهات حيث لم يعد الترتيب (الجزئي) معطى بواسطة ترتيب باريتو.

التحسين متعدد الأنماط أو التحسين العالمي

غالبًا ما تكون مسائل التحسين متعددة الأنماط؛ أي أنها تمتلك حلولًا جيدة متعددة. قد تكون جميعها جيدة عالميًا (بنفس قيمة دالة التكلفة)، أو قد يكون هناك مزيج من الحلول الجيدة عالميًا والمحلية. ويكمن هدف مُحسِّن متعدد الأنماط في الحصول على جميع الحلول المتعددة (أو بعضها على الأقل).

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

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

تصنيف النقاط الحرجة والنقاط القصوى

مشكلة الجدوى

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

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

وجود

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

الشروط اللازمة لتحقيق الأمثلية

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

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

شروط كافية لتحقيق الأمثلية

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

حساسية واستمرارية الأمثلية

تصف نظرية الغلاف كيف تتغير قيمة الحل الأمثل عند تغير أحد المعاملات الأساسية . وتُسمى عملية حساب هذا التغير بالتحليل المقارن .

تصف نظرية الحد الأقصى لكلود بيرج (1963) استمرارية الحل الأمثل كدالة للمعلمات الأساسية.

حساب التفاضل والتكامل الأمثل

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

علاوة على ذلك، يمكن تصنيف النقاط الحرجة باستخدام مدى تحديد مصفوفة هيسيان : إذا كانت مصفوفة هيسيان موجبة التحديد عند نقطة حرجة، فإن النقطة تمثل حدًا أدنى محليًا؛ وإذا كانت مصفوفة هيسيان سالبة التحديد، فإن النقطة تمثل حدًا أقصى محليًا؛ وأخيرًا، إذا كانت غير محددة، فإن النقطة تمثل نوعًا من نقاط السرج .

يمكن تحويل المسائل المقيدة في كثير من الأحيان إلى مسائل غير مقيدة باستخدام معاملات لاغرانج . كما يمكن أن يوفر استرخاء لاغرانج حلولاً تقريبية للمسائل المقيدة الصعبة.

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

التقارب العالمي

بشكل عام، إذا لم تكن دالة الهدف دالة تربيعية، فإن العديد من طرق التحسين تستخدم أساليب أخرى لضمان تقارب سلسلة فرعية من التكرارات نحو الحل الأمثل. تعتمد الطريقة الأولى، والتي لا تزال شائعة، لضمان التقارب على البحث الخطي ، الذي يُحسّن الدالة على طول بُعد واحد. أما الطريقة الثانية، والتي تزداد شعبيتها، فتستخدم مناطق الثقة . يُستخدم كل من البحث الخطي ومناطق الثقة في الطرق الحديثة للتحسين غير التفاضلي . عادةً ما يكون المُحسِّن العالمي أبطأ بكثير من المُحسِّنات المحلية المتقدمة (مثل BFGS )، لذا غالبًا ما يُمكن بناء مُحسِّن عالمي فعال عن طريق بدء المُحسِّن المحلي من نقاط بداية مختلفة.

تقنيات التحسين الحسابي

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

خوارزميات التحسين

الأساليب التكرارية

تختلف الطرق التكرارية المستخدمة لحل مسائل البرمجة غير الخطية باختلاف ما إذا كانت تقيّم مصفوفات هيس ، أو التدرجات، أو قيم الدوال فقط. في حين أن تقييم مصفوفات هيس (H) والتدرجات (G) يُحسّن معدل التقارب، إلا أنه بالنسبة للدوال التي توجد لها هذه الكميات وتتغير بسلاسة كافية، فإن هذه التقييمات تزيد من التعقيد الحسابي (أو التكلفة الحسابية) لكل تكرار. في بعض الحالات، قد يكون التعقيد الحسابي مرتفعًا للغاية.

يُعدّ عدد عمليات تقييم الدوال المطلوبة أحد المعايير الرئيسية للمُحسِّنات، إذ غالبًا ما يُمثّل هذا جهدًا حسابيًا كبيرًا، عادةً ما يكون أكبر بكثير من الجهد المبذول داخل المُحسِّن نفسه، والذي يعمل بشكل أساسي على N متغيرًا. تُوفّر المشتقات معلومات تفصيلية لهذه المُحسِّنات، ولكن حسابها أصعب، فعلى سبيل المثال، يتطلب تقريب التدرج N+1 عملية تقييم للدالة على الأقل. بالنسبة لتقريب المشتقات من الرتبة الثانية (المُجمّعة في مصفوفة هيسيان)، يكون عدد عمليات تقييم الدالة في حدود N². تتطلب طريقة نيوتن المشتقات من الرتبة الثانية، لذا يكون عدد استدعاءات الدالة في كل تكرار في حدود N²، بينما في مُحسِّن التدرج البحت الأبسط، يكون N فقط. مع ذلك، تحتاج مُحسِّنات التدرج عادةً إلى عدد تكرارات أكبر من خوارزمية نيوتن. يعتمد اختيار الأفضل من حيث عدد استدعاءات الدالة على طبيعة المسألة نفسها.

  • الطرق التي تقيّم مصفوفات هيسيان (أو تقارب مصفوفات هيسيان باستخدام الفروق المحدودة ):
    • طريقة نيوتن
    • البرمجة التربيعية المتسلسلة : طريقة تعتمد على نيوتن لحل المسائل المقيدة ذات الحجم الصغير والمتوسط . بعض الإصدارات قادرة على التعامل مع المسائل ذات الأبعاد الكبيرة.
    • طرق النقطة الداخلية : هذه فئة كبيرة من الطرق لتحسين القيود، بعضها يستخدم فقط معلومات التدرج (الفرعي) والبعض الآخر يتطلب تقييم مصفوفات هيسيان.
  • الطرق التي تقيّم التدرجات، أو تقارب التدرجات بطريقة ما (أو حتى التدرجات الفرعية):
  • الطرق التي تقيّم قيم الدالة فقط: إذا كانت المشكلة قابلة للتفاضل بشكل مستمر، فيمكن تقريب التدرجات باستخدام الفروق المحدودة، وفي هذه الحالة يمكن استخدام طريقة تعتمد على التدرج.

الأساليب الاستدلالية

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

التطبيقات

الميكانيكا

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

يمكن التعبير عن العديد من مشاكل التصميم كبرامج تحسين. يُطلق على هذا التطبيق اسم تحسين التصميم. ومن فروعه تحسين الهندسة ، وفرع آخر حديث ومتنامٍ في هذا المجال هو تحسين التصميم متعدد التخصصات ، والذي، على الرغم من فائدته في العديد من المشاكل، فقد طُبِّق بشكل خاص على مشاكل هندسة الطيران والفضاء .

يمكن تطبيق هذا النهج في علم الكونيات والفيزياء الفلكية. [ 10 ]

الاقتصاد والتمويل

يرتبط علم الاقتصاد ارتباطًا وثيقًا بتحسين سلوك الفاعلين الاقتصاديين ، لدرجة أن أحد التعريفات المؤثرة يصف علم الاقتصاد ، بوصفه علمًا، بأنه "دراسة السلوك البشري كعلاقة بين الغايات والوسائل النادرة "، مع وجود استخدامات بديلة. [ 11 ] تشمل نظرية التحسين الحديثة نظرية التحسين التقليدية، ولكنها تتداخل أيضًا مع نظرية الألعاب ودراسة التوازنات الاقتصادية . تصنف رموز مجلة الأدب الاقتصادي البرمجة الرياضية وتقنيات التحسين والمواضيع ذات الصلة تحت تصنيف JEL:C61-C63 .

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

منذ سبعينيات القرن الماضي، دأب الاقتصاديون على نمذجة القرارات الديناميكية عبر الزمن باستخدام نظرية التحكم . [ 12 ] فعلى سبيل المثال، تُستخدم نماذج البحث الديناميكية لدراسة سلوك سوق العمل . [ 13 ] ويكمن أحد الفروق الجوهرية بين النماذج الحتمية والنماذج العشوائية. [ 14 ] إذ يبني خبراء الاقتصاد الكلي نماذج التوازن العام الديناميكي العشوائي (DSGE) التي تصف ديناميكيات الاقتصاد ككل كنتيجة لقرارات التحسين المترابطة بين العمال والمستهلكين والمستثمرين والحكومات. [ 15 ] [ 16 ]

الهندسة الكهربائية

تشمل بعض التطبيقات الشائعة لتقنيات التحسين في الهندسة الكهربائية تصميم المرشحات النشطة ، [ 17 ] والحد من المجال الشارد في أنظمة تخزين الطاقة المغناطيسية فائقة التوصيل، وتصميم هياكل الميكروويف باستخدام رسم الخرائط المكانية ، [ 18 ] وهوائيات الهواتف المحمولة، [ 19 ] [ 20 ] [ 21 ] والتصميم القائم على الكهرومغناطيسية. وقد استفاد تحسين تصميم مكونات وهوائيات الميكروويف، الذي تم التحقق من صحته كهرومغناطيسيًا، على نطاق واسع من نموذج بديل مناسب قائم على الفيزياء أو تجريبي، ومنهجيات رسم الخرائط المكانية منذ اكتشاف رسم الخرائط المكانية في عام 1993. [ 22 ] [ 23 ] كما تُستخدم تقنيات التحسين في تحليل تدفق الطاقة . [ 24 ]

الهندسة المدنية

يُستخدم التحسين على نطاق واسع في الهندسة المدنية. وتُعد إدارة الإنشاءات وهندسة النقل من بين الفروع الرئيسية للهندسة المدنية التي تعتمد بشكل كبير على التحسين. ومن أكثر مشاكل الهندسة المدنية شيوعًا التي تُحل باستخدام التحسين: حفر وردم الطرق، وتحليل دورة حياة المنشآت والبنى التحتية، [ 25 ] وتسوية الموارد ، [ 26 ] [ 27 ] وتخصيص موارد المياه ، وإدارة حركة المرور ، [ 28 ] وتحسين الجداول الزمنية.

بحوث العمليات

يُعدّ مجال بحوث العمليات مجالًا آخر يستخدم تقنيات التحسين على نطاق واسع . [ 29 ] كما يستخدم بحوث العمليات النمذجة والمحاكاة العشوائية لدعم تحسين عملية اتخاذ القرارات. ويتزايد استخدام البرمجة العشوائية في بحوث العمليات لنمذجة القرارات الديناميكية التي تتكيف مع الأحداث؛ ويمكن حل هذه المشكلات باستخدام أساليب التحسين واسعة النطاق وأساليب التحسين العشوائي .

هندسة التحكم

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

الجيوفيزياء

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

النمذجة الجزيئية

تُستخدم أساليب التحسين غير الخطي على نطاق واسع في تحليل التشكيل .

علم الأحياء النظمي الحاسوبي

تُستخدم تقنيات التحسين في العديد من جوانب بيولوجيا الأنظمة الحاسوبية، مثل بناء النماذج، والتصميم الأمثل للتجارب، والهندسة الأيضية، والبيولوجيا التركيبية. [ 30 ] وقد طُبقت البرمجة الخطية لحساب أقصى إنتاجية ممكنة لمنتجات التخمر، [ 30 ] ولاستنتاج شبكات تنظيم الجينات من مجموعات بيانات المصفوفات الدقيقة المتعددة [ 31 ] ، بالإضافة إلى شبكات تنظيم النسخ من بيانات الإنتاجية العالية. [ 32 ] كما استُخدمت البرمجة غير الخطية لتحليل استقلاب الطاقة [ 33 ] وطُبقت في الهندسة الأيضية وتقدير المعلمات في المسارات الكيميائية الحيوية. [ 34 ]

التعلم الآلي

حلول

انظر أيضاً

ملحوظات

  1. ↑ " طبيعة البرمجة الرياضية مؤرشفة في 2014-03-05 على Wayback Machine "، مسرد البرمجة الرياضية ، جمعية الحوسبة INFORMS.
  2. ↑ "البرمجة الرياضية: نظرة عامة" (ملف PDF) . تم الاطلاع عليه بتاريخ 26 أبريل 2024 .
  3. ↑ مارتينز، جواكيم آر آر إيه؛ نينغ، أندرو (2021-10-01). تحسين التصميم الهندسي . مطبعة جامعة كامبريدج. ISBN 978-1108833417.
  4. ↑ دو، د.ز.؛ باردالوس، ب.م.؛ وو، و. (2008). "تاريخ التحسين". في فلوداس، س .؛ باردالوس، ب. (محرران). موسوعة التحسين . بوسطن: سبرينغر. ص 1538-1542 . 
  5. ^ هارتمان ، ألكسندر ك. ريجر، هيكو (2002). خوارزميات التحسين في الفيزياء . سيتيسير.
  6. ↑ إروين ديويرت، دبليو. (2017)، "دوال التكلفة" ، قاموس بالغراف الجديد للاقتصاد ، لندن: بالغراف ماكميلان المملكة المتحدة، ص 1-12 ، doi : 10.1057/978-1-349-95121-5_659-2 ، ISBN  978-1-349-95121-5تم الاطلاع عليه بتاريخ 18 أغسطس 2024
  7. ↑ بيكسبي، روبرت إي (2012). "تاريخ موجز لحسابات البرمجة الخطية والبرمجة المختلطة" . دوكيومنتا ماثيماتيكا . سلسلة دوكيومنتا ماثيماتيكا. 2012 : 107-121 . doi : 10.4171/dms/6/16 . ISBN 978-3-936609-58-5.
  8. ↑ عبد القادر، ر.؛ لياخوف، ب.؛ بيرجرمان، م.؛ ريزنيكوف، د. (فبراير 2024). "التعرف على صور الأقمار الصناعية باستخدام الشبكات العصبية الجماعية وزخم التدرج التفاضلي الموجب-السالب" . الفوضى، السوليتونات والكسور . 179 114432. Bibcode : 2024CSF...17914432A . doi : 10.1016/j.chaos.2023.114432 .
  9. ↑ فيريشاجين، أ.ف. (1989). "نمذجة والتحكم في حركة روبوتات المناولة". المجلة السوفيتية لعلوم الحاسوب والأنظمة . 27 (5): 29-38 .
  10. ↑ حجاج، س.؛ ديسوكي، ف.؛ رمضان، م. (2017). "نموذج تضخمي كوني باستخدام التحكم الأمثل". الجاذبية وعلم الكونيات . 23 (3): 236-239 . Bibcode : 2017GrCo...23..236H . doi : 10.1134/S0202289317030069 . ISSN 1995-0721 . S2CID 125980981 .  
  11. ↑ ليونيل روبنز (1935، الطبعة الثانية) مقال عن طبيعة وأهمية العلوم الاقتصادية ، ماكميلان، ص 16.
  12. ↑ دورفمان، روبرت (1969). "تفسير اقتصادي لنظرية التحكم الأمثل". المجلة الاقتصادية الأمريكية . 59 (5): 817-831 . JSTOR 1810679 . 
  13. ↑ سارجنت، توماس ج. (1987). "البحث" . نظرية الاقتصاد الكلي الديناميكي . مطبعة جامعة هارفارد. ص 57-91 . ISBN  9780674043084.
  14. ↑ أ. ج. مالياريس (2008). "التحكم الأمثل العشوائي"، قاموس بالغراف الجديد للاقتصاد ، الطبعة الثانية. ملخص مؤرشف بتاريخ 18-10-2017 في أرشيف الإنترنت .
  15. ↑ روتمبرغ، خوليو ؛ وودفورد، مايكل (1997). "إطار اقتصادي قياسي قائم على التحسين لتقييم السياسة النقدية" (ملف PDF) . حولية الاقتصاد الكلي للمكتب الوطني للبحوث الاقتصادية . 12 : 297-346 . doi : 10.2307/3585236 . JSTOR 3585236 . 
  16. ↑ من قاموس بالغراف الجديد للاقتصاد (2008)، الطبعة الثانية مع روابط الملخص:• " أساليب التحسين العددي في الاقتصاد " بقلم كارل شميدرز• " البرمجة المحدبة " بقلم لورانس إي. بلوم • " نموذج آرو-ديبرو للتوازن العام " بقلم جون جياناكوبولوس .
  17. ↑ دي، بيشنو براساد؛ كار، ر.؛ ماندال، د.؛ غوشال، س.ب. (27-09-2014). "الاختيار الأمثل لقيم المكونات لتصميم مرشح نشط تناظري باستخدام خوارزمية تحسين سرب الجسيمات البسيطة". المجلة الدولية للتعلم الآلي وعلم التحكم الآلي . 6 (4): 621-636 . doi : 10.1007/s13042-014-0299-0 . ISSN 1868-8071 . S2CID 13071135 .  
  18. ↑ كوزيل، سلاومير؛ باندلر، جون دبليو. (يناير 2008). "رسم الخرائط المكانية باستخدام نماذج تقريبية متعددة لتحسين مكونات الميكروويف". رسائل مكونات الميكروويف واللاسلكية IEEE . 18 (1): 1-3 . Bibcode : 2008IMWCL..18L1969K . CiteSeerX 10.1.1.147.5407 . doi : 10.1109/LMWC.2007.911969 . S2CID 11086218 .  
  19. ↑ تو، شينغ؛ تشنغ، تشينغشا س.؛ تشانغ، ييفان؛ باندلر، جون و.؛ نيكولوفا، ناتاليا ك. (يوليو 2013). "تحسين رسم الخرائط المكانية لهوائيات الهواتف المحمولة باستخدام نماذج الأسلاك الرقيقة" . معاملات IEEE في مجال الهوائيات والانتشار . 61 (7): 3797-3807 . Bibcode : 2013ITAP...61.3797T . doi : 10.1109/TAP.2013.2254695 .
  20. ↑ N. Friedrich, “Space mapping outpasse EM optimization in handset-antenna design,” microwaves&rf, August 30, 2013.
  21. ^ سرفانتس غونزاليس، خوان سي. راياس سانشيز، خوسيه إي؛ لوبيز، كارلوس أ. كاماتشو بيريز، خوسيه ر. بريتو بريتو، زابديل؛ شافيز هورتادو، خوسيه إل. (فبراير 2016). "تحسين رسم الخرائط الفضائية لهوائيات الهاتف مع الأخذ في الاعتبار تأثيرات EM لمكونات الهاتف المحمول وجسم الإنسان" . المجلة الدولية لهندسة الترددات اللاسلكية والميكروويف بمساعدة الكمبيوتر . 26 (2): 121-128 . دوى : 10.1002/mmce.20945 . اتش دي ال : 11117/4485 . S2CID 110195165 . 
  22. ↑ باندلر، جيه دبليو؛ بيرناكي، آر إم؛ تشين، شاو هوا؛ جروبلني، بي إيه؛ هيمرز، آر إتش (1994). "تقنية رسم الخرائط المكانية لتحسين الكهرومغناطيسية". معاملات IEEE في نظرية وتقنيات الميكروويف . 42 (12): 2536-2544 . Bibcode : 1994ITMTT..42.2536B . doi : 10.1109/22.339794 .
  23. ↑ باندلر، جيه دبليو؛ بيرناكي، آر إم؛ شاو هوا تشين؛ هيمرز، آر إتش؛ مادسن، ك. (1995). "التحسين الكهرومغناطيسي باستخدام رسم الخرائط المكانية المكثفة". معاملات IEEE في نظرية وتقنيات الميكروويف . 43 (12): 2874-2882 . Bibcode : 1995ITMTT..43.2874B . doi : 10.1109/22.475649 .
  24. ↑ الاسترخاء المحدب لتدفق الطاقة الأمثل: دليل تعليمي . ندوة iREP لعام 2013 حول ديناميكيات أنظمة الطاقة الكبيرة والتحكم فيها. doi : 10.1109/IREP.2013.6629391 .
  25. ↑ بيريونيسي، سيد مدح؛ توكولان، مهدي (9 يناير 2017). "نموذج برمجة رياضية لحل مسائل تحسين التكلفة والسلامة في صيانة المنشآت" . مجلة الجمعية الكورية للهندسة المدنية . 21 (6): 2226-2234 . Bibcode : 2017KSJCE..21.2226P . doi : 10.1007/s12205-017-0531-z . S2CID 113616284 . 
  26. ↑ حجازي، طارق (يونيو 1999). "تحسين تخصيص الموارد وتسويتها باستخدام الخوارزميات الجينية". مجلة هندسة وإدارة الإنشاءات . 125 (3): 167-175 . doi : 10.1061/(ASCE)0733-9364(1999)125:3(167) .
  27. ↑ بيريونيسي، إس. ماده؛ ناصري، مهران؛ رمضاني، عبد الله (9 يوليو 2018). "بيريونيسي، إس. إم.، ناصري، م.، ورمضاني، أ. (2018). تسوية الموارد في مشاريع البناء مع تقسيم الأنشطة وقيود الموارد: تحسين التلدين المحاكي". المجلة الكندية للهندسة المدنية . 46 : 81-86 . doi : 10.1139/cjce-2017-0670 . hdl : 1807/93364 . S2CID 116480238 . 
  28. ↑ هيرتي، م.؛ كلار، أ. (1 يناير 2003). "نمذجة ومحاكاة وتحسين شبكات تدفق حركة المرور" . مجلة SIAM للحوسبة العلمية . 25 (3): 1066-1087 . Bibcode : 2003SJSC...25.1066H . doi : 10.1137/S106482750241459X . ISSN 1064-8275 . 
  29. ↑ "قوة جديدة على الساحة السياسية: حزب سيوفونيست" . مؤرشف من الأصل بتاريخ 18 ديسمبر 2014. تم الاطلاع عليه بتاريخ 14 سبتمبر 2013 .
  30. 1 2 بابوتساكيس، إليفثيريوس تيري (فبراير 1984). "معادلات وحسابات لتخمرات بكتيريا حمض الزبدة". التكنولوجيا الحيوية والهندسة الحيوية . 26 (2): 174-187 . Bibcode : 1984BiotB..26..174P . doi : 10.1002 / bit.260260210 . ISSN 0006-3592 . PMID 18551704. S2CID 25023799 .   
  31. ↑ وانغ، يونغ؛ جوشي، تروبتي؛ تشانغ، شيانغ-سون؛ شو، دونغ؛ تشين، لوانان (24 يوليو/تموز 2006). "استنتاج شبكات تنظيم الجينات من مجموعات بيانات متعددة للمصفوفات الدقيقة". المعلوماتية الحيوية . 22 (19): 2413-2420 . doi : 10.1093/bioinformatics/btl396 . ISSN 1460-2059 . PMID 16864593 .  
  32. ↑ وانغ، روي-شنغ؛ وانغ، يونغ؛ تشانغ، شيانغ-سون؛ تشن، لوانان (22-09-2007). "استنتاج شبكات تنظيم النسخ من بيانات الإنتاجية العالية" . المعلوماتية الحيوية . 23 (22): 3056-3064 . doi : 10.1093/bioinformatics/btm465 . ISSN 1460-2059 . PMID 17890736 .  
  33. ↑ فو، ثوي د.؛ بول لي، دبليو إن؛ بالسون، برنارد أو. (مايو 2007). "تحليل أنظمة استقلاب الطاقة يوضح معقد سلسلة التنفس المتأثر في متلازمة لي". علم الوراثة الجزيئية والاستقلاب . 91 (1): 15-22 . doi : 10.1016/j.ymgme.2007.01.012 . ISSN 1096-7192 . PMID 17336115 .  
  34. ↑ مينديز، ب .؛ كيل، د. (1998). "التحسين غير الخطي للمسارات الكيميائية الحيوية: تطبيقات في الهندسة الأيضية وتقدير المعلمات" . المعلوماتية الحيوية . 14 (10): 869-883 . doi : 10.1093/bioinformatics/14.10.869 . ISSN 1367-4803 . PMID 9927716 .  

للمزيد من القراءة

  • بويد، ستيفن ب.؛ فاندنبيرغ، ليفين (2004). التحسين المحدب . كامبريدج: مطبعة جامعة كامبريدج. ISBN 0-521-83378-7.
  • جيل، بي إي؛ موراي، دبليو؛ رايت، إم إتش (1982). التحسين العملي . لندن: أكاديميك برس. ISBN 0-12-283952-8.
  • لي، جون (2004). مدخل إلى التحسين التوافقي . مطبعة جامعة كامبريدج. ISBN 0-521-01012-8.
  • نوسيدال، خورخي ؛ رايت، ستيفن جيه. (2006). التحسين العددي (  الطبعة الثانية). برلين: سبرينغر. ISBN 0-387-30303-0.
  • GL Nemhauser، AHG Rinnooy Kan و MJ Todd (محررون): التحسين ، Elsevier، (1989).
  • ستانيسلاف والوكيفيتش: البرمجة العددية الصحيحة ، سبرينغر، ISBN 978-9048140688، (1990).
  • آر. فليتشر: الأساليب العملية للتحسين ، الطبعة الثانية، وايلي، (2000).
  • بانوس م. باردالوس: التقريب والتعقيد في التحسين العددي: المسائل المستمرة والمتقطعة ، سبرينغر، ISBN 978-1-44194829-8، (2000).
  • Xiaoqi Yang, KL Teo, Lou Caccetta (Eds.): Optimization Methods and Applications , Springer, ISBN 978-0-79236866-3, (2001).
  • Panos M. Pardalos و Mauricio GC Resende (محرران): كتيب التحسين التطبيقي ، مطبعة جامعة أكسفورد عند الطلب، ISBN 978-0-19512594-8، (2002).
  • ويل ميشيلز، إميل آرتس، وجان كورست: الجوانب النظرية للبحث المحلي ، سبرينغر، ISBN 978-3-64207148-5، (2006).
  • Der-San Chen, Robert G. Batson, and Yu Dang：Applied Integer Programming: Modeling and Solution , Wiley, ISBN 978-0-47037306-4, (2010).
  • مايكل ج. كوشندرفر وتيم أ. ويلر: خوارزميات للتحسين ، مطبعة معهد ماساتشوستس للتكنولوجيا، ISBN 978-0-26203942-0، (2019).
  • فلاديسلاف بوكشتينوف: التحسين: النجاح في الممارسة ، مطبعة سي آر سي (تايلور وفرانسيس)، ISBN 978-1-03222947-8، (2023).
  • روزاريو توسكانو: حل مسائل التحسين باستخدام خوارزمية كالمان الاستدلالية: طرق عشوائية جديدة ، سبرينغر، ISBN 978-3-031-52458-5 (2024).
  • إيمانويل إم. بومزي، تيبور سينديس، راينر هورست وبانوس إم. باردالوس: التطورات في التحسين العالمي ، كلوير أكاديميك، ISBN 978-1-4419-4768-0 (2010).