طريقة سيمبلكس المعدلة

في مجال التحسين الرياضي ، تعتبر طريقة سيمبلكس المعدلة شكلاً مختلفاً من طريقة سيمبلكس لجورج دانتزيج للبرمجة الخطية .

تُعادل طريقة السمبلكس المُعدّلة رياضيًا طريقة السمبلكس القياسية، لكنها تختلف عنها في التطبيق. فبدلًا من الاحتفاظ بجدول يُمثل القيود المُعدّلة لمجموعة من المتغيرات الأساسية، تحتفظ هذه الطريقة بتمثيل أساس المصفوفة التي تُمثل هذه القيود. ويُتيح هذا النهج المُوجّه نحو المصفوفات كفاءة حسابية أكبر من خلال تمكين عمليات المصفوفات المتفرقة. ^{[ 1 ]}

صياغة المشكلة

فيما تبقى من المناقشة، يُفترض أن مسألة البرمجة الخطية قد تم تحويلها إلى الشكل القياسي التالي:

{\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}

حيث $A \in ℝ m \times n$ . وبدون فقدان للعمومية، يُفترض أن مصفوفة القيود $A$ ذات رتبة صفية كاملة وأن المسألة قابلة للحل، أي يوجد على الأقل $x \geq 0$ بحيث يكون $Ax = b$ . إذا كانت $A$ ناقصة الرتبة، فإما أن هناك قيودًا زائدة، أو أن المسألة غير قابلة للحل. ويمكن معالجة كلتا الحالتين بخطوة تمهيدية.

الوصف الخوارزمي

شروط الأمثلية

في البرمجة الخطية، تُعد شروط كاروش-كون-تاكر ضرورية وكافية لتحقيق الحل الأمثل. شروط كاروش-كون-تاكر لمسألة البرمجة الخطية في صورتها القياسية هي:

{\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}

حيث يمثل $λ$ و $s$ معاملات لاغرانج المرتبطة بالقيود $Ax = b$ و $x \geq 0$ على التوالي. ^{[ 2 ]} يُطلق على الشرط الأخير، المكافئ لـ $s i x i = 0$ لجميع $1 < i < n$ ، اسم شرط التراخي التكميلي .

بحسب ما يُعرف أحيانًا بالنظرية الأساسية للبرمجة الخطية ، يُمكن تحديد رأس $x في متعدد السطوح الممكنة من خلال كونه أساسًا$ $B$ للمصفوفة $A$ ، مُختارًا من أعمدة الأخيرة. ^{[ أ ]} بما أن $A$ ذات رتبة كاملة، فإن $B$ غير منفردة. دون فقدان للعمومية، نفترض أن $A = [B \in N]$ . عندئذٍ يُعطى $x بالعلاقة التالية:$

{\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}

حيث $x B \geq 0.$ قسّم $c$ و $s$ وفقًا لذلك إلى

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}

لتحقيق شرط التراخي التكميلي، نفرض أن $s B = 0.$ ويترتب على ذلك أن

{\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}

مما يعني أن

{\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}

إذا كانت قيمة $s N \geq 0$ عند هذه النقطة، فإن شروط KKT تتحقق، وبالتالي فإن $x$ هو الأمثل.

عملية محورية

إذا لم تتحقق شروط كاروش-كون-تاكر، تُجرى عملية محورية تتضمن إضافة عمود من $N$ إلى الأساس على حساب عمود موجود في $B.$ في حال عدم وجود انحلال ، تؤدي العملية المحورية دائمًا إلى انخفاض حاد في $c T x$ . لذلك، إذا كانت المسألة محدودة، يجب أن تنتهي طريقة السمبلكس المُعدّلة عند رأس أمثل بعد عمليات محورية متكررة نظرًا لوجود عدد محدود من الرؤوس. ^{[ 4 ]}

اختر فهرسًا $m < q \leq n$ بحيث يكون $sq < 0$ كفهرس دخول . سيتم نقل العمود المقابل من المصفوفة $A$ $،$ أي $Aq ،$ إلى الأساس، وسيُسمح $لـ$ $xq$ بالزيادة من الصفر. يمكن إثبات أن

{\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},

$أي$ أن كل زيادة بمقدار وحدة واحدة في xq $تؤدي$ $إلى$ ^انخفاض بمقدار $-sq$ $في$ cTx $. [$ $5$ ^{] بما} أن

{\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},

$يجب إنقاص x B$ بمقدار $Δx B = B -1 A q$ $x $ $q$ ، بشرط أن يكون $x B$ $- Δx$ $$ $B$ $ \geq$ $0. لنفترض أن$ $d = B -1 A q$ . إذا كان $d \leq 0$ ، فمهمازادت $قيمة x q$ ، ستبقى $x B - Δx B$ غير سالبة. بالتالي، يمكن إنقاص $c T x$ $كيفما شئنا، ومن ثمّ فإن المسألة غير محدودة. وإلا، نختار فهرسًا p = argmin 1 \leq i \leq m {x i / d i | d i > 0}$ كفهرسمغادرة. يؤدي هذا الاختيار إلى زيادة $x q$ من الصفر حتى $تنخفض x p$ إلى الصفر مع الحفاظ على إمكانية الحل. تُختتم عملية التمحور باستبدال $A p$ بـ $A q$ في الأساس.

مثال عددي

لنفترض برنامجًا خطيًا حيث

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}

يترك

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}

في البداية، وهو ما يتوافق مع رأس ممكن $x = [0 0 0 10 15] T.$ في هذه اللحظة،

{\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

اختر $q = 3$ كمؤشر دخول. عندئذٍ $،$ $d = [1 3]$ $T، مما يعني أن زيادة x3 بمقدار وحدة واحدة تؤدي إلى انخفاض x4 و x5 بمقدار 1 و 3$ $على$ التوالي $.$ لذلك ، $تزداد$ قيمة $x3$ $إلى$ 5 $،$ وعندها تنخفض $قيمة$ $x5$ $إلى$ $الصفر$ ، ويصبح $p$ $=$ $5$ $مؤشر$ الخروج.

بعد عملية التمحور،

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}

وبالمثل،

{\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

تشير قيمة $s N$ $الموجبة إلى أن x$ هو الأمثل الآن.

قضايا عملية

الانحطاط

نظرًا لأن طريقة السمبلكس المعدلة مكافئة رياضيًا لطريقة السمبلكس، فإنها تعاني أيضًا من الانحلال، حيث لا تؤدي عملية المحور إلى انخفاض في $c T x$ ، وتتسبب سلسلة من عمليات المحور في تكرار الأساس. يمكن استخدام استراتيجية الاضطراب أو الترتيب المعجمي لمنع التكرار وضمان الإنهاء. ^{[ 6 ]}

التمثيل الأساسي

يوجد نوعان من الأنظمة الخطية التي تتضمن $B في طريقة سيمبلكس المعدلة:$

{\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}

بدلاً من إعادة تحليل المصفوفة $B$ ، عادةً ما يتم تحديث تحليل LU مباشرةً بعد كل عملية محورية، ولهذا الغرض توجد عدة استراتيجيات مثل طريقتي فورست-توملين وبارتلز-جولوب. مع ذلك، تتراكم كمية البيانات التي تمثل التحديثات والأخطاء العددية بمرور الوقت، مما يجعل إعادة التحليل الدورية ضرورية. ^{[ 1 ]}^{[ 7 ]}

ملاحظات ومراجع

ملحوظات

↑ تنص النظرية نفسها أيضًا على أن متعدد السطوح الممكن يحتوي على رأس واحد على الأقل، وأن هناك رأسًا واحدًا على الأقل هو الأمثل.^{[ 3 ]}

مراجع

1 2 مورغان 1997 ، §2.
↑ Nocedal & Wright 2006 ، ص 358 ، المعادلة 13.4.
↑ Nocedal & Wright 2006 ، ص 363 ، النظرية 13.2.
↑ Nocedal & Wright 2006 ، ص 370 ، النظرية 13.4.
↑ Nocedal & Wright 2006 ، ص. 369 ، المعادلة 13.24.
↑ Nocedal & Wright 2006 ، ص 381 ، §13.5.
↑ Nocedal & Wright 2006 ، ص 372 ، §13.4.

فهرس

مورغان، إس إس (1997). مقارنة بين خوارزميات طريقة سيمبلكس (رسالة ماجستير). جامعة فلوريدا . مؤرشف من الأصل في 7 أغسطس 2011.
نوسيدال، ج.؛ رايت، إس. جيه. (2006). ميكوش، تي. في.؛ ريسنيك، إس. آي.؛ روبنسون، إس. إم. (محررون). التحسين العددي . سلسلة سبرينغر في بحوث العمليات والهندسة المالية ( الطبعة الثانية). نيويورك، نيويورك، الولايات المتحدة الأمريكية: سبرينغر . ISBN 978-0-387-30303-1.

[4] تنص النظرية نفسها أيضًا على أن متعدد السطوح الممكن يحتوي على رأس واحد على الأقل، وأن هناك رأسًا واحدًا على الأقل هو الأمثل.^{[ 3 ]}

[FOOTNOTEMorgan1997§2-1] 1 2 مورغان 1997 ، §2.

[FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2] Nocedal & Wright 2006 ، ص 358 ، المعادلة 13.4.

[FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3] Nocedal & Wright 2006 ، ص 363 ، النظرية 13.2.

[FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5] Nocedal & Wright 2006 ، ص 370 ، النظرية 13.4.

[FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6] Nocedal & Wright 2006 ، ص. 369 ، المعادلة 13.24.

[FOOTNOTENocedalWright2006381§13.5-7] Nocedal & Wright 2006 ، ص 381 ، §13.5.

[FOOTNOTENocedalWright2006372§13.4-8] Nocedal & Wright 2006 ، ص 372 ، §13.4.

[ 1 ]

[ 2 ]

[ أ ]

[ 4 ]

انخفاض

[ 6 ]

[ 7 ]

[ 3 ]