مشكلة التخصيص المعممة

الموسوعة الحرة

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

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

في حالات خاصة

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

شرح التعريف

فيما يلي، لدينا عدد من أنواع العناصر،أ1{\displaystyle a_{1}}خلالأن{\displaystyle a_{n}}وأنواع مختلفة من الصناديقب1{\displaystyle b_{1}}خلالبم{\displaystyle b_{m}}كل صندوقبأنا{\displaystyle b_{i}}يرتبط بالميزانيةتأنا{\displaystyle t_{i}}. لصندوق القمامةبأنا{\displaystyle b_{i}}كل عنصرأج{\displaystyle a_{j}}يحقق ربحاًصأناج{\displaystyle p_{ij}}ووزنwأناج{\displaystyle w_{ij}}الحل هو عملية توزيع العناصر على الصناديق. الحل الممكن هو حل يكون فيه لكل صندوق قيمة معينة.بأنا{\displaystyle b_{i}}الوزن الإجمالي للعناصر المخصصة هو على الأكثرتأنا{\displaystyle t_{i}}يمثل ربح الحل مجموع الأرباح لكل تخصيص للعناصر في الصناديق. والهدف هو إيجاد حل يحقق أقصى ربح ممكن.

رياضياً، يمكن صياغة مسألة التخصيص المعممة كبرنامج عدد صحيح :

أقصى ∑أنا=1م∑ج=1نصأناجxأناج.رهناً بـ ∑ج=1نwأناجxأناج≤تأناأنا=1،...،م؛∑أنا=1مxأناج≤1ج=1،...،ن؛xأناج∈{0،1}أنا=1،...،م،ج=1،...،ن؛{\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}

تعقيد

تُعدّ مسألة التخصيص المعممة مسألة صعبة من نوع NP . [ 1 ] ومع ذلك، توجد استرخاءات برمجة خطية تُعطي(1-1/هـ){\displaystyle (1-1/e)}-تقريب. [ 2 ]

خوارزمية التقريب الجشعة

بالنسبة لنوع المشكلة الذي لا يتطلب فيه تخصيص كل عنصر لصندوق، توجد مجموعة من الخوارزميات لحل مشكلة GAP باستخدام ترجمة توافقية لأي خوارزمية لمشكلة حقيبة الظهر إلى خوارزمية تقريبية لمشكلة GAP. [ 3 ]

استخدام أيα{\displaystyle \alpha }باستخدام خوارزمية التقريب ALG لمسألة حقيبة الظهر ، من الممكن إنشاء (α+1{\displaystyle \alpha +1}تقريب (-) لمسألة التخصيص المعممة بطريقة جشعة باستخدام مفهوم الربح المتبقي. تقوم الخوارزمية بإنشاء جدول زمني في تكرارات، حيث خلال التكرارج{\displaystyle j}مجموعة أولية من العناصر المراد التخلص منهابج{\displaystyle b_{j}}تم تحديد الخيار. تحديد الحاويةبج{\displaystyle b_{j}}قد تتغير هذه القيم حيث قد يتم إعادة تحديد العناصر في تكرار لاحق لصناديق أخرى. الربح المتبقي للعنصرxأنا{\displaystyle x_{i}}لصندوق القمامةبج{\displaystyle b_{j}}يكونصأناج{\displaystyle p_{ij}}لوxأنا{\displaystyle x_{i}}لم يتم اختيارها لأي حاوية أخرى أوصأناج{\displaystyle p_{ij}}–صأناك{\displaystyle p_{ik}}لوxأنا{\displaystyle x_{i}}تم تحديده للصندوقبك{\displaystyle b_{k}}.

بشكل رسمي: نستخدم متجهًاتي{\displaystyle T}للإشارة إلى الجدول الزمني المبدئي أثناء تنفيذ الخوارزمية. تحديداً،تي[أنا]=ج{\displaystyle T[i]=j}يعني العنصرxأنا{\displaystyle x_{i}}مُجدول على سلة المهملاتبج{\displaystyle b_{j}}وتي[أنا]=-1{\displaystyle T[i]=-1}يعني ذلك العنصرxأنا{\displaystyle x_{i}}غير مُجدول. الربح المتبقي في التكرارج{\displaystyle j}يُرمز إليه بـPج{\displaystyle P_{j}}، أينPج[أنا]=صأناج{\displaystyle P_{j}[i]=p_{ij}}إذا كان العنصرxأنا{\displaystyle x_{i}}غير مُجدول (أيتي[أنا]=-1{\displaystyle T[i]=-1}) وPج[أنا]=صأناج-صأناك{\displaystyle P_{j}[i]=p_{ij}-p_{ik}}إذا كان العنصرxأنا{\displaystyle x_{i}}مُجدول على سلة المهملاتبك{\displaystyle b_{k}}(أيتي[أنا]=ك{\displaystyle T[i]=k}).

رسميا:

تعيينتي[أنا]=-1 ل أنا=1...ن{\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}
لج=1،...،م{\displaystyle j=1,\ldots ,m}يفعل:
اتصل بـ ALG لإيجاد حل لمشكلة سلة المهملاتبج{\displaystyle b_{j}}باستخدام دالة الربح المتبقيPج{\displaystyle P_{j}}. أشر إلى العناصر المختارة بـSج{\displaystyle S_{j}}.
تحديثتي{\displaystyle T}استخدامSج{\displaystyle S_{j}}، أي،تي[أنا]=ج{\displaystyle T[i]=j}للجميعأنا∈Sج{\displaystyle i\in S_{j}}.

انظر أيضاً

مراجع

  1. ↑ أوزباكير، لالي؛ بايكاس أوغلو، عادل؛ تابكان، بينار (2010)، خوارزمية النحل لمسألة التخصيص المعممة ، الرياضيات التطبيقية والحساب، المجلد  215، إلسيفير، الصفحات 3782-3795 ، doi : 10.1016/j.amc.2009.11.018 .
  2. ↑ فليشر، ليزا؛ غومانز، ميشيل إكس؛ ميروكني، وهاب إس؛ سفيريدينكو، مكسيم (2006). خوارزميات التقريب الدقيق لمسائل التخصيص العام الأقصى . وقائع الندوة السنوية السابعة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة - SODA '06. الصفحات 611-620 . 
  3. ↑ كوهين، رؤوفين؛ كاتزير، ليران؛ راز، داني (2006). "تقريب فعال لمسألة التخصيص المعمم". رسائل معالجة المعلومات . 100 (4): 162-166 . CiteSeerX 10.1.1.159.1947 . doi : 10.1016/j.ipl.2006.06.003 . 

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

  • كيلير، هانز؛ فرشي، أولريش؛ بيسنجر ، ديفيد (2013/03/19). مشاكل الحقيبة . سبرينغر. رقم ISBN 978-3-540-24777-7.