القيد (الرياضيات)

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 8 صور
الموسوعة الحرة

في الرياضيات ، القيد هو شرطٌ في مسألة التحسين يجب أن يحققه الحل. توجد أنواعٌ عديدة من القيود ، أهمها قيود المساواة ، وقيود المتباينات ، وقيود الأعداد الصحيحة . تُسمى مجموعة الحلول المرشحة التي تحقق جميع القيود بالمجموعة الممكنة . [ 1 ]

مثال

فيما يلي مسألة تحسين بسيطة:

مينو(x)=x12+x24{\displaystyle \min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}}

رهناً بـ

x1≥1{\displaystyle x_{1}\geq 1}

و

x2=1،{\displaystyle x_{2}=1,}

أينx{\displaystyle \mathbf {x} }يشير إلى المتجه ( x 1 , x 2 ).

في هذا المثال، يُحدد السطر الأول الدالة المراد تقليلها (وتُسمى دالة الهدف ، أو دالة الخسارة، أو دالة التكلفة). أما السطران الثاني والثالث فيُحددان قيدين، الأول قيد متباينة والثاني قيد مساواة. هذان القيدان قيدان حاسمان ، أي أنه يجب تحقيقهما؛ وهما يُحددان مجموعة الحلول الممكنة.

بدون القيود، سيكون الحل هو (0,0)، حيثو(x){\displaystyle f(\mathbf {x} )}يمتلك هذا الحل أدنى قيمة. لكنه لا يفي بالقيود. حل مسألة التحسين المقيد المذكورة أعلاه هوx=(1،1){\displaystyle \mathbf {x} =(1,1)}وهي النقطة التي لها أصغر قيمة لـو(x){\displaystyle f(\mathbf {x} )}الذي يفي بالقيدين.

مصطلحات

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

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

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

القيود العالمية

القيود العامة [ 2 ] هي قيود تمثل علاقة محددة بين عدد من المتغيرات مجتمعة. يمكن إعادة كتابة بعضها، مثل alldifferentالقيد، على شكل اقتران للقيود الذرية بلغة أبسط: alldifferentينطبق القيد على n متغيرًا.x1...xن{\displaystyle x_{1}...x_{n}}ويتحقق هذا الشرط إذا كانت المتغيرات تأخذ قيمًا مختلفة عن بعضها البعض. وهو مكافئ دلاليًا لربط المتباينات.x1≠x2،x1≠x3...،x2≠x3،x2≠x4...xن-1≠xن{\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}تُوسّع القيود العالمية الأخرى نطاق التعبير في إطار القيود. وفي هذه الحالة، فإنها عادةً ما تُجسّد بنية نموذجية للمسائل التوافقية. على سبيل المثال، regularيُعبّر القيد عن قبول سلسلة من المتغيرات بواسطة آلة حتمية محدودة .

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

انظر أيضاً

مراجع

  1. ↑ تاكاياما، أكيرا (1985). الاقتصاد الرياضي (  الطبعة الثانية). نيويورك: مطبعة جامعة كامبريدج. ص 61. ISBN  0-521-31498-4.
  2. ↑ روسي، فرانشيسكا؛ فان بيك، بيتر؛ والش، توبي (2006). "7". دليل برمجة القيود ( الطبعة الأولى). أمستردام: إلسيفير. ISBN  9780080463643. OCLC 162587579 . 
  3. ↑ روسي، فرانشيسكا (2003). مبادئ وممارسات البرمجة المقيدة CP 2003 00 : المؤتمر الدولي التاسع، CP 2003، كينسال، أيرلندا، 29 سبتمبر - 3 أكتوبر 2003. وقائع المؤتمر . برلين: سبرينغر-فيرلاغ برلين هايدلبرغ. ISBN  9783540451938. OCLC 771185146 . 

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