توليد الأعمدة

يُعد توليد الأعمدة أو توليد الأعمدة المؤجل خوارزمية فعالة لحل البرامج الخطية الكبيرة . ^{[ 1 ]}

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

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

تعتمد الخوارزمية على مسألتين: المسألة الرئيسية والمسألة الفرعية. المسألة الرئيسية هي المسألة الأصلية مع مراعاة مجموعة فرعية فقط من المتغيرات. أما المسألة الفرعية فهي مسألة جديدة تُنشأ لتحديد متغير مُحسِّن ( أي متغير يُمكنه تحسين دالة الهدف للمسألة الرئيسية).

ثم تتابع الخوارزمية عملها على النحو التالي:

1. قم بتهيئة المسألة الرئيسية والمسألة الفرعية.
2. حل المسألة الرئيسية
3. ابحث عن متغير مُحسِّن في المسألة الفرعية
4. إذا تم العثور على متغير مُحسِّن: أضفه إلى المسألة الرئيسية ثم انتقل إلى الخطوة 2
5. وإلا: فإن حل المسألة الرئيسية هو الحل الأمثل. توقف.

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

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

سنشرح الآن بالتفصيل كيفية حساب التكلفة المخفضة للمتغيرات وسبب ذلك. لننظر إلى البرنامج الخطي التالي في صورته القياسية:

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x\\&{\text{subject to}}\\&Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

والتي سنسميها المسألة الأولية وكذلك برنامجها الخطي الثنائي :

${\displaystyle {\begin{aligned}&\max _{u}u^{T}b\\&{\text{subject to}}\\&u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}}$

علاوة على ذلك، دع${\displaystyle x^{*}}$و${\displaystyle u^{*}}$تُعتبر هذه الحلول الأمثل لهاتين المسألتين، والتي يمكن لأي برنامج حل خطي توفيرها. تحقق هذه الحلول قيود برنامجها الخطي، وبحسب مبدأ الازدواجية ، فإن لها نفس قيمة دالة الهدف (${\displaystyle c^{T}x^{*}=u^{*T}b}$) والتي سنسميها${\displaystyle z^{*}}$هذه القيمة المثلى هي دالة لمعاملات المسألة الأولية المختلفة:${\displaystyle z^{*}=z^{*}(c,A,b)}$لاحظ أن هناك متغيرًا ثنائيًا${\displaystyle u_{i}^{*}}$لكل قيد من قيود النموذج الخطي الأولي. من الممكن إثبات أن المتغير الثنائي الأمثل${\displaystyle u_{i}^{*}}$يمكن تفسيرها على أنها المشتقة الجزئية للقيمة المثلى${\displaystyle z^{*}}$دالة الهدف بالنسبة للمعامل${\displaystyle b_{i}}$من الجانب الأيمن للقيود:${\displaystyle u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}}$أو غير ذلك${\displaystyle u^{*}={\frac {\partial z^{*}}{\partial b}}}$وبعبارة أبسط،${\displaystyle u_{i}^{*}}$يشير إلى مقدار الزيادة المحلية في القيمة المثلى لدالة الهدف عندما يكون المعامل${\displaystyle b_{i}}$يزيد بمقدار وحدة واحدة.

لنفترض الآن أن المتغير${\displaystyle y}$لم يُؤخذ هذا المتغير في الاعتبار حتى ذلك الحين في المسألة الأصلية. لاحظ أن هذا يُعادل القول بأن المتغير${\displaystyle y}$كان موجودًا في النموذج ولكنه كان يأخذ قيمة صفرية. سنلاحظ الآن تأثير تغيير قيمة على المشكلة الأساسية.${\displaystyle y}$من${\displaystyle 0}$ل${\displaystyle {\hat {y}}}$. لو${\displaystyle c_{y}}$و${\displaystyle A_{y}}$تمثل هذه المعاملات على التوالي المعاملات المرتبطة بالمتغير${\displaystyle y}$في دالة الهدف وفي القيود، يتم تعديل البرنامج الخطي على النحو التالي:

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x+c_{y}{\hat {y}}\\&{\text{subject to}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

لكي تعرف ما إذا كان من المفيد إضافة المتغير${\displaystyle y}$لحل المشكلة ( أي للسماح لها بأخذ قيمة غير صفرية)، نريد أن نعرف ما إذا كانت القيمة${\displaystyle z_{\hat {y}}^{*}}$تتناقص قيمة دالة الهدف لهذه المسألة الجديدة مع ازدياد قيمة${\displaystyle {\hat {y}}}$من المتغير${\displaystyle y}$يزداد. بعبارة أخرى، نريد أن نعرف${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$وللقيام بذلك، لاحظ أن${\displaystyle z_{\hat {y}}^{*}}$يمكن التعبير عنها وفقًا لقيمة دالة الهدف للمسألة الأولية:${\displaystyle z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*}(c,A,b-A_{y}{\hat {y}})}$ثم يمكننا حساب المشتقة التي تهمنا:

${\displaystyle {\begin{aligned}{\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial {\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned}}}$

بمعنى آخر، تأثير تغيير القيمة${\displaystyle {\hat {y}}}$على القيمة${\displaystyle z_{\hat {y}}^{*}}$يترجم ذلك إلى مصطلحين. أولاً، يؤثر هذا التغيير بشكل مباشر على دالة الهدف، وثانياً، يتم تعديل الجانب الأيمن من القيود مما يؤثر على المتغيرات المثلى.${\displaystyle x^{*}}$والتي يتم قياس مقدارها باستخدام المتغيرات الثنائية${\displaystyle u^{*}}$المشتق${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$يُطلق عليه عمومًا التكلفة المخفضة للمتغير${\displaystyle y}$وسيُشار إليه بـ${\displaystyle cr_{y}}$فيما يلي.