مسألة التخصيص التربيعي

تُعدّ مسألة التخصيص التربيعي ( QAP ) إحدى مسائل التحسين التوافقي الأساسية في فرع التحسين أو بحوث العمليات في الرياضيات ، وهي من فئة مسائل تحديد مواقع المرافق . وقد اقترحها في الأصل كلٌّ من تجالينج كوبمانز ومارتن ج. بيكمان . ^{[ 1 ]}

تُحاكي هذه المسألة المشكلة الواقعية التالية:

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

يشبه بيان المشكلة بيان مشكلة التخصيص ، باستثناء أن دالة التكلفة يتم التعبير عنها من حيث المتباينات التربيعية، ومن هنا جاء الاسم.

التعريف الرسمي لمسألة التخصيص التربيعي هو كما يلي. ^{[ 2 ]}

بافتراض عدد صحيح موجب${\displaystyle n}$و${\displaystyle n^{4}}$معاملات التكلفة${\displaystyle \{c_{i,j,p,q}\}}$، ابحث عن${\displaystyle n\times n}$مصفوفة${\displaystyle [x_{ij}]}$الذي يقلل دالة الهدف

${\displaystyle \sum _{i,j}\sum _{p,q}c_{i,j,p,q}x_{i,j}x_{p,q}}$

رهناً بالقيود

${\displaystyle \sum _{j}x_{i,j}=\sum _{i}x_{i,j}=1,}$

${\displaystyle x_{ij}\in \{0,1\}}$

تم طرح مسألة التخصيص التربيعي في الأصل من قبل تجالينج كوبمانز ومارتن جيه بيكمان بالشكل التالي.

بفرض وجود مصفوفتين مربعتين D و T ، أوجد مصفوفة التبديل X التي تقلل من حاصل الضرب النقطي المزدوج لـ T مع${\displaystyle A=XDX^{\intercal }}$.

بمعنى آخر، بمعلومية D و T ، أوجد${\displaystyle \{x_{ij}\}_{1\leq i,j\leq n}}$وذلك لكي

$\begin{aligned}{\text{تقليل}}\quad &\sum _{1\leq i,j\leq n}a_{ij}t_{ij}\\{\text{بشرط}}\quad &\sum _{1\leq k\leq n}x_{ik}=\sum _{1\leq k\leq n}x_{jk}=1,\\&x_{ij}\in \{0,1\}.\end{aligned}}$

باستخدام المصطلحات المذكورة أعلاه، تُجدول المصفوفة D المسافة (${\displaystyle d_{ij}}$(يعطي المسافة من الموقع i إلى الموقع j ) و T التدفق (${\displaystyle t_{ij}}$تُحدد كمية الإمدادات المراد نقلها من المنشأة i إلى المنشأة j . تمثل مصفوفة التبديل X تخصيص المنشآت للمواقع.${\displaystyle x_{ij}}$(1 فقط إذا كان المرفق i موجودًا في الموقع j .) ^{[ 2 ]}

وبشكل بديهي، تشجع دالة الهدف على وضع المرافق ذات التدفقات العالية فيما بينها بالقرب من بعضها البعض.

تُعدّ هذه المسألة من المسائل الصعبة حسابيًا (NP-hard )، لذا لا توجد خوارزمية معروفة لحلّها في زمن متعدد الحدود ، بل قد تتطلب حتى الحالات الصغيرة وقتًا طويلًا للحساب. وقد ثبت أيضًا أنه لا توجد خوارزمية تقريبية تعمل في زمن متعدد الحدود لأي عامل (ثابت)، إلا إذا كانت P = NP. ^{[ 3 ]} يمكن اعتبار مسألة البائع المتجول (TSP) حالة خاصة من مسألة التخصيص التربيعي (QAP) إذا افترضنا أن التدفقات تربط جميع المرافق على طول حلقة واحدة فقط، وأن جميع التدفقات لها نفس القيمة غير الصفرية (الثابتة)، وأن جميع المسافات تساوي المسافات المقابلة في حالة مسألة البائع المتجول. ويمكن كتابة العديد من مسائل التحسين التوافقي القياسية الأخرى بهذا الشكل.

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

استُخدم نموذج QAP أيضًا لنمذجة تكلفة وضع الأحرف على لوحة المفاتيح. في هذه الحالة، تمثل المواقع مفاتيح لوحة المفاتيح، وتتوافق المسافات بينها مع الوقت اللازم للضغط على زوج معين من المفاتيح. أما المرافق فتمثل الأحرف، وتتناسب أوزانها مع عدد مرات ظهور زوج الأحرف المحدد في مجموعة النصوص. وقد استُخدم هذا النوع من نماذج QAP في تصميم معيار لوحة المفاتيح الفرنسية (NF Z71-300). ^{[ 4 ]}

• مشكلة تعيين عنق الزجاجة التربيعية

• مايكل ر. غاري وديفيد س. جونسون (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ISBN 0-7167-1045-5.A2.5: ND43، صفحة 218.

• https://doi.org/10.7488/ds/3428 مكتبة QAPLIB - مكتبة مسائل التخصيص التربيعي
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - برنامج لحل مسائل التخصيص التربيعي قائم على لغة جافا
• https://CRAN.R-project.org/package=qap - حزمة R المسماة qap: طرق استدلالية لحل مشكلة التخصيص التربيعي
• https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - برنامج حل مسائل QAP باستخدام خوارزمية Metaheuristic لنظامي التشغيل Windows 10/11