برنامج التكوين الخطي

في مسألة تعبئة الصناديق ، يوجد n عنصرًا بأحجام مختلفة. الهدف هو تعبئة العناصر في أقل عدد ممكن من الصناديق، بحيث لا يتجاوز عدد العناصر في كل صندوق B عنصرًا . التكوين الأمثل هو مجموعة من الأحجام التي لا يتجاوز مجموعها B عنصرًا .

• مثال : ^{[ 7 ]} لنفترض أن أحجام العناصر هي 3، 3، 3، 3، 3، 4، 4، 4، 4، و B = 12. عندئذٍ، تكون التكوينات الممكنة هي: 3333؛ 333؛ 33، 334؛ 3، 34، 344؛ 4، 44، 444. إذا كان لدينا ثلاثة عناصر فقط من الحجم 3، فلن نتمكن من استخدام التكوين 3333.

لنرمز بـ S إلى مجموعة الأحجام المختلفة (وعددها). ولنرمز بـ C إلى مجموعة التكوينات المختلفة (وعددها). لكل حجم s في S وتكوين c في C ، نرمز بما يلي:

• n _s - عدد العناصر ذات الحجم s .
• a _{s , c} - عدد مرات ظهور الحجم s في التكوين c .
• x _c - متغير يشير إلى عدد الصناديق ذات التكوين c .

ثم، يكون تكوين LP لتعبئة الصناديق كما يلي:

تقليل${\displaystyle \sum _{c\in C}x_{c}}$رهناً بـ

${\displaystyle \sum _{c\in C}a_{s,c}x_{c}\geq n_{s}}$لكل s في S (جميع n _s من العناصر ذات الحجم s معبأة).

${\displaystyle x_{c}\in \{0,\ldots ,n\}}$ لكل c في C (يوجد على الأكثر n خانة إجمالاً، لذا على الأكثر n من كل تكوين فردي).

تُعدّ مسألة البرمجة الخطية للتكوينات مسألة برمجة خطية عددية صحيحة ، لذا فهي عمومًا مسألة صعبة الحل (NP-hard). علاوة على ذلك، فإن المسألة نفسها كبيرة جدًا في الغالب: إذ تحتوي على C متغيرًا و S قيدًا. إذا كان أصغر حجم للعنصر هو eB (لجزء كسري e في (0,1))، فيمكن أن يصل عدد العناصر في كل خانة إلى 1/ e ، وبالتالي فإن عدد التكوينات C ~ S ^{1/ e} ، والذي قد يكون كبيرًا جدًا إذا كانت e صغيرة (إذا اعتُبرت e ثابتة، فيمكن حل مسألة البرمجة الخطية العددية الصحيحة بالبحث الشامل: يوجد على الأكثر S ^1/e تكوينًا، ولكل تكوين يوجد على الأكثر n قيمة ممكنة، وبالتالي يوجد على الأكثر${\displaystyle n^{S^{1/e}}}$يجب فحص التوليفات. لكل توليفة، علينا فحص قيود S ، لذا فإن وقت التشغيل هو${\displaystyle S\cdot n^{S^{1/e}}}$(وهي دالة متعددة الحدود في n عندما تكون S و e ثابتتين). ^{[ 7 ]}

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

يُعدّ نموذج البرمجة الخطية الجزئية لتعبئة الصناديق بمثابة استرخاء للبرمجة الخطية الصحيحة المذكورة أعلاه، وهو يحلّ محلّ القيد الأخير.${\displaystyle x_{c}\in \{0,\ldots ,n\}}$مع مراعاة القيد${\displaystyle x_{c}\geq 0}$بمعنى آخر، يمكن استخدام كل تكوين عددًا جزئيًا من المرات. وقد قُدِّم هذا الأسلوب لأول مرة من قِبَل جيلمور وجوموري، ^{[ 2 ]} ويُطلق عليه غالبًا اسم برنامج جيلمور-جوموري الخطي . ^{[ 8 ]}

• مثال : لنفترض وجود 31 عنصرًا بحجم 3 و7 عناصر بحجم 4، وحجم كل صندوق 10. التكوينات هي: 4، 44، 34، 334، 3، 33، 333. القيود هي: [0,0,1,2,1,2,3] × x = 31 و[1,2,1,1,0,0,0] × x = 7. الحل الأمثل للبرمجة الخطية الكسرية هو [0,0,0,7,0,0,17/3]. أي: يوجد 7 صناديق بتكوين 334 و17/3 صندوقًا بتكوين 333. لاحظ أنه يلزم تكوينان مختلفان فقط.

باختصار، يمكن كتابة برنامج البرمجة الخطية الكسرية على النحو التالي:

تقليل${\displaystyle ~\mathbf {1} \cdot \mathbf {x} ~}$شارع${\displaystyle ~\mathbf {A} \mathbf {x} \geq \mathbf {n} ~}$و${\displaystyle ~\mathbf {x} \geq 0~}$

حيث 1 هو المتجه (1، ...، 1) بحجم C ، و A هي مصفوفة S × C حيث يمثل كل عمود تكوينًا واحدًا، و n هو المتجه ( n ₁ ، ...، n _S ).

يمكن حل برنامج خطي بدون قيود على التكامل في وقت متعدد الحدود بالنسبة لعدد المتغيرات والقيود. تكمن المشكلة في أن عدد المتغيرات في البرنامج الخطي ذي التكوين الكسري يساوي عدد التكوينات الممكنة، وهو عدد قد يكون هائلاً. يقدم كارماركار وكارب ^{[ 9 ]} خوارزمية تتغلب على هذه المشكلة.

أولاً، يقومون بإنشاء البرنامج الخطي المزدوج للبرنامج الخطي الكسري:

أقصى${\displaystyle ~\mathbf {n} \cdot \mathbf {y} ~}$شارع${\displaystyle ~A^{T}\mathbf {y} \leq \mathbf {1} ~}$و${\displaystyle ~\mathbf {y} \geq 0}$.

يحتوي على S متغيرات y ₁ ,..., y _S ، و C قيود: لكل تكوين c ، يوجد قيد${\displaystyle A^{c}\cdot y\leq 1}$، أين${\displaystyle A^{c}}$يمثل العمود s في المصفوفة A التكوين c . وله التفسير الاقتصادي التالي: ^{[ 9 ]} لكل حجم s، يجب تحديد سعر غير سالب y s. ربحنا هو السعر الإجمالي لجميع الأصناف. نريد تعظيم الربح ny مع مراعاة أن _السعر الإجمالي للأصناف في كل تكوين لا يتجاوز 1.

ثانيًا، يطبقون صيغة معدلة من طريقة القطع الناقص ، لا تتطلب سرد جميع القيود، بل تحتاج فقط إلى مُوَصِّل فصل . مُوَصِّل الفصل هو خوارزمية، عند إعطائها متجهًا y ، إما أن تُؤكد أنه حل ممكن، أو تجد قيدًا يُخالفه. يمكن تطبيق مُوَصِّل الفصل للبرمجة الخطية الثنائية بحل مسألة حقيبة الظهر بأحجام s وقيم y : إذا كانت القيمة الإجمالية للحل الأمثل لمسألة حقيبة الظهر لا تتجاوز 1، فإن y حل ممكن؛ وإذا كانت أكبر من 1، فإن y غير ممكن ، ويُحدد الحل الأمثل لمسألة حقيبة الظهر تكوينًا يُخالف فيه القيد.

ثالثًا، يوضحون أنه من خلال حل تقريبي لمسألة حقيبة الظهر، يمكن للمرء الحصول على حل تقريبي للبرمجة الخطية الثنائية، ومن هذا، حل تقريبي للبرمجة الخطية الأولية؛ انظر خوارزميات تعبئة الصناديق Karmarkar-Karp .

بشكل عام، بالنسبة لأي عامل تسامح h ، يجد حلاً أساسياً ممكناً بتكلفة لا تتجاوز LOPT(I) + h ، ويعمل في الوقت:

${\displaystyle O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)}$،

حيث S هو عدد الأحجام المختلفة، و n هو عدد العناصر المختلفة، وحجم أصغر عنصر هو eB . على وجه الخصوص، إذا كان e ≥ 1/ n و h = 1، فإن الخوارزمية تجد حلاً في وقت لا يتجاوز LOPT+1 خانة.${\displaystyle O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)}$يعمل متغير عشوائي من هذه الخوارزمية في الوقت المتوقع التالي:

${\displaystyle O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)}$.

قام كارماركار وكارب بتطوير طريقة لتقريب برنامج البرمجة الخطية الكسري إلى حل تقريبي لبرنامج البرمجة الخطية التكاملي؛ انظر خوارزميات تعبئة الصناديق لكارماركار وكارب . يُظهر برهانهما أن فجوة التكامل الجمعي لهذا البرنامج تقع في O(log₂ ⁽ n ) ). لاحقًا، حسّن هوبرغ وروثفوس ^{[ 10 ]} نتيجتهما وأثبتا أن فجوة التكامل تقع في O(log( n )). أفضل حد أدنى معروف لفجوة التكامل هو ثابت Ω(1). إيجاد فجوة التكامل الدقيقة لا يزال مسألة مفتوحة .

فجوة التكامل لـ Configure-LP لجدولة الآلات غير المرتبطة هي 2. ^{[ 5 ]}