خوارزمية سيمبلكس

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 56 صور
الموسوعة الحرة
يوضح الرسم البياني خوارزمية سيمبلكس لحل مشكلة البرمجة الخطية بمتغيرين.
يوضح الرسم البياني خوارزمية سيمبلكس لحل مشكلة البرمجة الخطية بمتغيرين.

في مجال التحسين الرياضي ، تعتبر خوارزمية سيمبلكس لدانتزيج ( أو طريقة سيمبلكس ) خوارزمية للبرمجة الخطية . [ 1 ]

اسم الخوارزمية مشتق من مفهوم المُجَسَّم البسيط ، وقد اقترحه تي إس موتزكين . [ 2 ] لا تُستخدم المُجَسَّمات البسيطة فعليًا في هذه الطريقة، ولكن أحد تفسيراتها أنها تعمل على المخاريط المُجَسَّمة ، والتي تُصبح مُجَسَّمات بسيطة حقيقية مع قيد إضافي. [ 3 ] [ 4 ] [ 5 ] [ 6 ] المخاريط المُجَسَّمة المقصودة هي زوايا (أي جوارات الرؤوس) شكل هندسي يُسمى مُجَسَّمًا متعدد السطوح . ويُحدد شكل هذا المُجَسَّم بالقيود المُطبقة على دالة الهدف.

تاريخ

عمل جورج دانتزيج على أساليب التخطيط لسلاح الجو الأمريكي خلال الحرب العالمية الثانية باستخدام آلة حاسبة مكتبية . في عام ١٩٤٦، تحدّاه زميله لأتمتة عملية التخطيط لإلهائه عن قبول وظيفة أخرى. صاغ دانتزيج المشكلة على شكل متباينات خطية مستوحاة من أعمال فاسيلي ليونتيف ، إلا أنه لم يُدرج هدفًا ضمن صياغته آنذاك. فبدون هدف، يمكن أن يكون عدد كبير من الحلول ممكنًا، وبالتالي، لإيجاد الحل الأمثل الممكن، يجب استخدام "قواعد أساسية" عسكرية تحدد كيفية تحقيق الأهداف بدلًا من تحديد الهدف نفسه. تمثلت رؤية دانتزيج الأساسية في إدراكه أن معظم هذه القواعد الأساسية يمكن ترجمتها إلى دالة هدف خطية يجب تعظيمها. [ ٧ ] كان تطوير طريقة سيمبلكس تدريجيًا واستغرق حوالي عام. [ ٨ ]

بعد أن أضاف دانتزيغ دالة الهدف إلى صياغته في منتصف عام ١٩٤٧، أصبحت المسألة أسهل من الناحية الرياضية. أدرك دانتزيغ أن إحدى المسائل غير المحلولة التي ظنها واجبًا منزليًا في محاضرة أستاذه جيرزي نيمان (والتي حلّها لاحقًا بالفعل)، قابلة للتطبيق في إيجاد خوارزمية للبرامج الخطية. تضمنت هذه المسألة إيجاد معاملات لاغرانج للبرامج الخطية العامة على نطاق متصل من المتغيرات، كل منها محصور بين الصفر والواحد، ويحقق قيودًا خطية معبر عنها في صورة تكاملات ليبيغ . نشر دانتزيغ لاحقًا "واجبه المنزلي" كأطروحة لنيل درجة الدكتوراه. وقد منحت هندسة الأعمدة المستخدمة في هذه الأطروحة دانتزيغ رؤية ثاقبة جعلته يعتقد أن طريقة سيمبلكس ستكون فعالة للغاية. [ ٩ ]

ملخص

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

تعمل خوارزمية سيمبلكس على البرامج الخطية في شكلها المتعارف عليه

أقصىجتيx{\textstyle \mathbf {c^{T}} \mathbf {x} }
رهناً بـأx≤ب{\displaystyle A\mathbf {x} \leq \mathbf {b} }وx≥0{\displaystyle \mathbf {x} \geq 0}

معج=(ج1،...،جن){\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}معاملات دالة الهدف،(⋅)تي{\displaystyle (\cdot )^{\mathrm {T} }}هي منقولة المصفوفة مع وضع نقطة كعنصر نائب ، وx=(x1،...،xن){\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}هي متغيرات المسألة،أ{\displaystyle A}هي مصفوفة من الرتبة p × n ، وب=(ب1،...،بص){\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}هناك عملية مباشرة لتحويل أي برنامج خطي إلى برنامج في شكل قياسي، لذا فإن استخدام هذا الشكل من البرامج الخطية لا يؤدي إلى فقدان العمومية.

من الناحية الهندسية، المنطقة الممكنة المحددة بجميع قيمx{\displaystyle \mathbf {x} }بحيثأx≤ب{\textstyle A\mathbf {x} \leq \mathbf {b} }و∀أنا،xأنا≥0{\displaystyle \forall i,x_{i}\geq 0}هو متعدد السطوح محدب (ربما غير محدود) . تُعرف النقطة القصوى أو رأس متعدد السطوح هذا باسم الحل الأساسي الممكن (BFS).

يمكن إثبات أنه بالنسبة لبرنامج خطي في صورته القياسية، إذا كانت دالة الهدف لها قيمة عظمى في المنطقة الممكنة، فإنها تمتلك هذه القيمة على (واحدة على الأقل) من النقاط القصوى. [ 10 ] وهذا في حد ذاته يُختزل المسألة إلى عملية حسابية محدودة نظرًا لوجود عدد محدود من النقاط القصوى، إلا أن عدد النقاط القصوى كبير جدًا بحيث يصعب التعامل معه في جميع البرامج الخطية باستثناء أصغرها. [ 11 ]

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

يتم حل البرنامج الخطي على مرحلتين. في المرحلة الأولى، المعروفة بالمرحلة الأولى، يتم إيجاد نقطة بداية قصوى. قد يكون هذا الأمر بسيطًا، اعتمادًا على طبيعة البرنامج، ولكن بشكل عام، يمكن حله بتطبيق خوارزمية السمبلكس على نسخة معدلة من البرنامج الأصلي. النتائج المحتملة للمرحلة الأولى هي إما إيجاد حل أساسي ممكن، أو أن تكون المنطقة الممكنة فارغة. في الحالة الأخيرة، يُسمى البرنامج الخطي غير قابل للحل . في المرحلة الثانية، المعروفة بالمرحلة الثانية، تُطبق خوارزمية السمبلكس باستخدام الحل الأساسي الممكن الذي تم إيجاده في المرحلة الأولى كنقطة بداية. النتائج المحتملة للمرحلة الثانية هي إما إيجاد حل أساسي ممكن أمثل، أو حافة لانهائية تكون دالة الهدف غير محدودة فوقها. [ 13 ] [ 14 ] [ 15 ]

النموذج القياسي

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

x1≥5{\displaystyle x_{1}\geq 5}

متغير جديد،y1{\displaystyle y_{1}}، يتم تقديمه مع

y1=x1-5x1=y1+5{\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}

يمكن استخدام المعادلة الثانية للتخلص منx1{\displaystyle x_{1}}من البرنامج الخطي. وبهذه الطريقة، يمكن تغيير جميع قيود الحد الأدنى إلى قيود عدم السلبية.

ثانيًا، لكل قيد متباينة متبقٍ، يُضاف متغير جديد يُسمى متغير الركود ، لتحويل القيد إلى قيد مساواة. يُمثل هذا المتغير الفرق بين طرفي المتباينة، ويُفترض أن يكون غير سالب. على سبيل المثال، المتباينات

x2+2x3≤3-x4+3x5≥2{\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}

يتم استبدالها بـ

x2+2x3+s1=3-x4+3x5-s2=2s1،s2≥0{\displaystyle {\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}}

يسهل إجراء العمليات الجبرية على المتباينات بهذا الشكل. في المتباينات التي يظهر فيها الرمز ≥، مثل المتباينة الثانية، يشير بعض المؤلفين إلى المتغير المُدخل بـمتغير فائض .

ثالثًا، يتم حذف كل متغير غير مقيد من البرنامج الخطي. يمكن القيام بذلك بطريقتين، الأولى هي حل إحدى المعادلات التي يظهر فيها المتغير ثم حذفه بالتعويض. أما الثانية فهي استبدال المتغير بفرق بين متغيرين مقيدين. على سبيل المثال، إذاz1{\displaystyle z_{1}}إذا كان غير مقيد، فاكتب

z1=z1+-z1-z1+،z1-≥0{\displaystyle {\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{محاذاة}}}

يمكن استخدام المعادلة للتخلص منz1{\displaystyle z_{1}}من البرنامج الخطي.

عند اكتمال هذه العملية، ستكون المنطقة الممكنة على الشكل التالي:

أx=ب،∀ xأنا≥0{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}

من المفيد أيضاً افتراض أن رتبةأ{\displaystyle \mathbf {A} }يمثل عدد الصفوف. وهذا لا يؤدي إلى فقدان العمومية، لأنه بخلاف ذلك، إما أن النظامأx=ب{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }يحتوي على معادلات زائدة يمكن حذفها، أو أن النظام غير متسق ولا يوجد حل للبرنامج الخطي. [ 17 ]

جدول سيمبلكس

يمكن تمثيل البرنامج الخطي في شكله القياسي كجدول من الشكل التالي:

[1-جتي00أب]{\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {A} &\mathbf {b} \end{bmatrix}}}

يُحدد الصف الأول دالة الهدف، بينما تُحدد الصفوف المتبقية القيود. يُمثل الصفر في العمود الأول متجه الصفر الذي له نفس بُعد المتجه.ب{\displaystyle \mathbf {b} }(يستخدم المؤلفون المختلفون اصطلاحات مختلفة فيما يتعلق بالتصميم الدقيق). إذا كانت أعمدةأ{\displaystyle \mathbf {A} }يمكن إعادة ترتيبها بحيث تحتوي على مصفوفة الوحدة من الرتبةص{\displaystyle p}(عدد الصفوف فيأ{\displaystyle \mathbf {A} }إذا كانت قيم المتغيرات في الجدول تساوي صفرًا، يُقال إن الجدول في شكله القانوني . [ 18 ] تُسمى المتغيرات المقابلة لأعمدة مصفوفة الوحدة بالمتغيرات الأساسية، بينما تُسمى المتغيرات المتبقية بالمتغيرات غير الأساسية أو الحرة . إذا تم تعيين قيم المتغيرات غير الأساسية إلى صفر، فإنه يُمكن الحصول بسهولة على قيم المتغيرات الأساسية كمدخلات في الجدول.ب{\displaystyle \mathbf {b} }وهذا الحل هو حل أساسي ممكن. التفسير الجبري هنا هو أن معاملات المعادلة الخطية الممثلة بكل صف إما0{\displaystyle 0}،1{\displaystyle 1}أو أي رقم آخر. سيحتوي كل صف على1{\displaystyle 1}عمود ذو قيمة1{\displaystyle 1}،ص-1{\displaystyle p-1}أعمدة ذات معاملات0{\displaystyle 0}والأعمدة المتبقية بمعاملات أخرى (تمثل هذه المتغيرات الأخرى متغيراتنا غير الأساسية). من خلال ضبط قيم المتغيرات غير الأساسية على الصفر، نضمن في كل صف أن قيمة المتغير الذي يمثله a1{\displaystyle 1}يساوي في عمودهب{\displaystyle b}القيمة في ذلك الصف.

وعلى العكس من ذلك، إذا توفر حل أساسي ممكن، يمكن توسيع الأعمدة المقابلة للمتغيرات غير الصفرية إلى مصفوفة غير منفردةب{\displaystyle B}إذا ضُرب الجدول المقابل في معكوسب{\displaystyle B}ثم تكون النتيجة عبارة عن لوحة في شكلها المتعارف عليه. [ 19 ]

يترك

[1-جبتي-جدتي00أنادب^]{\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}

أن يكون لوحة في شكلها المتعارف عليه، حيثب^=ب-1ب{\displaystyle {\widehat {\mathbf {b} }}=B^{-1}\mathbf {b} }يمكن تطبيق تحويلات إضافية لإضافة الصفوف لإزالة المعاملات c T B  من دالة الهدف. تُسمى هذه العملية "التسعير" وتنتج عنها جدول معياري.

[10-ج¯دتيzب0أنادب^]{\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}

حيث تمثل z<sub> B</sub> قيمة دالة الهدف عند الحل الأساسي الممكن المقابل. أما المعاملات المُحدَّثة، والمعروفة أيضًا بمعاملات التكلفة النسبية ، فهي معدلات تغير دالة الهدف بالنسبة للمتغيرات غير الأساسية. [ 14 ]

عمليات التمحور

تُنفَّذ العملية الهندسية للانتقال من حل أساسي ممكن إلى حل أساسي ممكن مجاور كعملية محورية . أولًا، يُختار عنصر محوري غير صفري في عمود غير أساسي. يُضرب الصف الذي يحتوي على هذا العنصر في مقلوبه لتغيير قيمته إلى 1، ثم تُضاف مضاعفات هذا الصف إلى الصفوف الأخرى لتغيير باقي عناصر العمود إلى 0. والنتيجة هي أنه إذا كان العنصر المحوري في الصف r ، فإن هذا العمود يصبح العمود r من مصفوفة الوحدة. يصبح المتغير الخاص بهذا العمود الآن متغيرًا أساسيًا، ليحل محل المتغير الذي كان يُقابل العمود r من مصفوفة الوحدة قبل العملية. في الواقع، يدخل المتغير المُقابل للعمود المحوري إلى مجموعة المتغيرات الأساسية ويُسمى المتغير الداخل ، بينما يخرج المتغير الذي يتم استبداله من مجموعة المتغيرات الأساسية ويُسمى المتغير الخارج . يبقى الجدول في شكله المتعارف عليه، ولكن مع تغيير مجموعة المتغيرات الأساسية بعنصر واحد. [ 13 ] [ 14 ]

الخوارزمية

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

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

إدخال اختيار المتغير

بما أن المتغير المُدخل سيزداد عمومًا من 0 إلى عدد موجب، فإن قيمة دالة الهدف ستزداد (وتقترب من القيمة القصوى) إذا كانت المشتقة (أي المعاملات)ج¯تي{\displaystyle {\bar {\mathbf {c} }}^{\mathrm {T} }}تكون قيمة ) دالة الهدف بالنسبة لهذا المتغير موجبة. وبالتالي، ينبغي اختيار عمود محوري تكون قيمته المقابلة في صف دالة الهدف (-ج¯تي{\displaystyle -{\bar {\mathbf {c} }}^{\mathrm {T} }}) من الجدول سالب. (إذا كان المطلوب تقليل دالة الهدف، فسيتم اختيار عمود تكون فيه القيمة في صف الهدف موجبة.)

عادة ما يكون هناك أكثر من عمود واحد يحتوي على إدخال سلبي في صف الهدف، ويتم توجيه اختيار أي منها لإضافته إلى مجموعة المتغيرات الأساسية من خلال إحدى قواعد اختيار المتغيرات الداخلة العديدة [ 20 ] مثل خوارزمية Devex [ 21 ] .

إذا لم تكن أي من القيم في صف الهدف سالبة، فلن يكون بالإمكان اختيار أي متغير، وبالتالي يكون الحل في الواقع عند القيمة القصوى. ومن السهل ملاحظة أنه حل أقصى، لأن صف الهدف الآن يُقابل معادلة من الشكل التالي:

z(x)=zب+الحدود غير الموجبة المقابلة للمتغيرات غير الأساسية{\displaystyle z(\mathbf {x} )=z_{B}+{\text{الحدود غير الموجبة المقابلة للمتغيرات غير الأساسية}}}

اختيار المتغيرات المتبقية

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

بعد ذلك، يجب اختيار صف المحور بحيث تكون قيمة المتغير المُدخل (وبالتالي التحسن في الهدف) في أعلى قيمة لها، مع مراعاة أن تظل جميع المتغيرات الأساسية الأخرى غير سالبة. إذا كان عمود المحور هو c ، فسيتم تحقيق ذلك إذا تم اختيار صف المحور r بحيث

ب^ر/أ^رج{\displaystyle {\hat {b}}_{r}/{\hat {a}}_{rc}\,}

هو الحد الأدنى على جميع قيم r بحيثأ^رج{\displaystyle {\hat {a}}_{rc}}> 0. يُطلق على هذا اختبار النسبة الدنيا . [ 20 ] إذا كان هناك أكثر من صف واحد يتم فيه تحقيق الحد الأدنى، فيمكن استخدام قاعدة اختيار المتغير المتساقط [ 22 ] لإجراء التحديد.

مثال

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

تحقيق أقصى استفادة
Z=2x+3y+4z{\displaystyle Z=2x+3y+4z}
رهناً بـ
3x+2y+z≤102x+5y+3z≤15x،y،z≥0{\displaystyle {\begin{aligned}3x+2y+z&\leq 10\\2x+5y+3z&\leq 15\\x,\,y,\,z&\geq 0\end{aligned}}}

بإضافة متغيرات الركود s و t ، يتم تمثيل ذلك بواسطة الجدول المتعارف عليه

[1-2-3-40000321101002530115]{\displaystyle {\begin{bmatrix}1&-2&-3&-4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}}

حيث يمثل العمودان 5 و6 المتغيرين الأساسيين s و t ، والحل الأساسي الممكن المقابل هو

x=y=z=0،s=10،ت=15.{\displaystyle x=y=z=0,\,s=10,\,t=15.}

يمكن اختيار الأعمدة 2 و3 و4 كأعمدة محورية. في هذا المثال، لنفترض اختيار العمود 4. قيم z الناتجة عن اختيار الصفين 2 و3 كصفوف محورية هي 10/1  =  10 و15/3  =  5 على التوالي. من بين هذه القيم، القيمة الأصغر هي 5، لذا يجب أن يكون الصف 3 هو الصف المحوري. ينتج عن إجراء عملية المحور ما يلي:

[1231130043200731301-1350235310135]{\displaystyle {\begin{bmatrix}1&{\frac {2}{3}}&{\frac {11}{3}}&0&0&{\frac {4}{3}}&20\\0&{\frac {7}{3}}&{\frac {1}{3}}&0&1&-{\frac {1}{3}}&5\\0&{\frac {2}{3}}&{\frac {5}{3}}&1&0&{\frac {1}{3}}&5\end{bmatrix}}}

يمثل العمودان 4 و5 المتغيرين الأساسيين z و s ، والحل الأساسي الممكن المقابل لهما هو

x=y=ت=0،z=5،s=5.{\displaystyle x=y=t=0,\,z=5,\,s=5.}

في الخطوة التالية، لا توجد قيم سالبة في صف الهدف، وفي الواقع

Z=20-23x-113y-43ت{\displaystyle Z=20-{\frac {2}{3}}x-{\frac {11}{3}}y-{\frac {4}{3}}t}

إذن، القيمة القصوى لـ Z هي 20.

إيجاد جدول أساسي أولي

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

يجب أن تنتهي خوارزمية السمبلكس المطبقة على مسألة المرحلة الأولى بقيمة دنيا للدالة الهدف الجديدة، لأن قيمتها، كونها مجموع متغيرات غير سالبة، محدودة من الأسفل بالصفر. إذا كانت القيمة الدنيا صفرًا، فيمكن حذف المتغيرات الاصطناعية من الجدول المعياري الناتج، مما ينتج عنه جدول معياري مكافئ للمسألة الأصلية. بعد ذلك، يمكن تطبيق خوارزمية السمبلكس لإيجاد الحل؛ وتُسمى هذه الخطوة بالمرحلة  الثانية . إذا كانت القيمة الدنيا موجبة، فلا يوجد حل ممكن لمسألة المرحلة الأولى حيث تكون جميع المتغيرات الاصطناعية أصفارًا. هذا يعني أن المنطقة الممكنة للمسألة الأصلية فارغة، وبالتالي لا يوجد حل للمسألة الأصلية. [ 13 ] [ 14 ] [ 24 ]

مثال

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

تحقيق أقصى استفادة
Z=2x+3y+4z{\displaystyle Z=2x+3y+4z}
رهناً بـ
3x+2y+z=102x+5y+3z=15x،y،z≥0{\displaystyle {\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}}

يختلف هذا المثال عن المثال السابق في أنه يستخدم قيود المساواة بدلاً من قيود عدم المساواة. الحل السابقx=y=0،z=5{\displaystyle x=y=0\,,z=5}ينتهك القيد الأول. يتم تمثيل هذه المشكلة الجديدة بواسطة الجدول (غير القياسي).

[1-2-3-40032110025315]{\displaystyle {\begin{bmatrix}1&-2&-3&-4&0\\0&3&2&1&10\\0&2&5&3&15\end{bmatrix}}}

أدخل متغيرين اصطناعيين u و v ودالة الهدف W  = u + v ، مما ينتج عنه جدول جديد   

[10000-1-1001-2-3-4000003211010002530115]{\displaystyle {\begin{bmatrix}1&0&0&0&0&-1&-1&0\\0&1&-2&-3&-4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}

يتم الاحتفاظ بالمعادلة التي تحدد دالة الهدف الأصلية تحسباً للمرحلة الثانية.

بحسب التصميم، يُعتبر كل من u و v متغيرين أساسيين لأنهما جزء من مصفوفة الوحدة الأولية. مع ذلك، تفترض دالة الهدف W حاليًا أن u و v يساويان  صفرًا. لتعديل دالة الهدف لتكون قيمتها الصحيحة حيث u  =  10 و v  =  15، أضف الصفين الثالث والرابع إلى الصف الأول، ما يُعطي

[10574002501-2-3-4000003211010002530115]{\displaystyle {\begin{bmatrix}1&0&5&7&4&0&0&25\\0&1&-2&-3&-4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}

حدد العمود 5 كعمود محوري، لذا يجب أن يكون صف المحور هو الصف 4، ويكون الجدول المحدث هو

[307100-4150321100460007103-115002530115]{\displaystyle {\begin{bmatrix}3&0&7&1&0&0&-4&15\\0&3&2&11&0&0&4&60\\0&0&7&1&0&3&-1&15\\0&0&2&5&3&0&1&15\end{bmatrix}}}

الآن حدد العمود 3 كعمود محوري، والذي يجب أن يكون الصف 3 هو صف المحور الخاص به، للحصول على

[70000-7-70070250-210130007103-115000117-2325]{\displaystyle {\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&25&0&-2&10&130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}}

أصبحت المتغيرات الاصطناعية الآن تساوي صفرًا، ويمكن حذفها مما يعطي جدولًا معياريًا مكافئًا للمشكلة الأصلية:

[702501300710150011725]{\displaystyle {\begin{bmatrix}7&0&25&0&130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}

لحسن الحظ، هذا هو الحل الأمثل بالفعل، وبالتالي فإن القيمة المثلى للبرنامج الخطي الأصلي هي 130/7. هذه القيمة "أسوأ" من 20، وهو أمر متوقع لمسألة ذات قيود أكثر.

مواضيع متقدمة

تطبيق

يُتيح شكل الجدول المستخدم أعلاه لوصف الخوارزمية إمكانية تنفيذه مباشرةً، حيث يُحفظ الجدول كمصفوفة مستطيلة بأبعاد ( m  +  1) × ( m  + n + 1). ومن السهل تجنب تخزين الأعمدة m الصريحة لمصفوفة الوحدة التي ستظهر داخل الجدول، وذلك لأن B مجموعة جزئية من أعمدة [ A , I ]. يُشار إلى هذا التنفيذ باسم " خوارزمية السمبلكس القياسية ". إلا أن عبء التخزين والحساب يجعل طريقة السمبلكس القياسية مكلفة للغاية لحل مسائل البرمجة الخطية الكبيرة.    

في كل تكرار لخوارزمية السمبلكس، البيانات المطلوبة هي الصف الأول من الجدول، والعمود المحوري (المحوري) من الجدول الذي يُمثل المتغير الداخل، والطرف الأيمن. يُمكن تحديث الطرف الأيمن باستخدام العمود المحوري، بينما يُمكن تحديث الصف الأول من الجدول باستخدام الصف المحوري (المحوري) الذي يُمثل المتغير الخارج. يُمكن حساب كل من العمود المحوري والصف المحوري مباشرةً باستخدام حلول أنظمة المعادلات الخطية التي تتضمن المصفوفة B وضرب المصفوفة في المتجه باستخدام A. هذه الملاحظات هي التي تُحفز " خوارزمية السمبلكس المُعدلة "، والتي تتميز تطبيقاتها بتمثيلها العكسي للمصفوفة B. [ 25 ] 

في مسائل البرمجة الخطية الكبيرة، تكون المصفوفة A عادةً مصفوفة متفرقة ، وعند استغلال خاصية التفرق الناتجة في المصفوفة B للحفاظ على تمثيلها القابل للعكس، تصبح خوارزمية السمبلكس المعدلة أكثر كفاءة من طريقة السمبلكس القياسية. وتعتمد برامج حل السمبلكس التجارية على خوارزمية السمبلكس المعدلة. [ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ]

الانحطاط: التوقف والدوران

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

تحاول قواعد المحور القائمة على التاريخ مثل قاعدة زاده وقاعدة كانينغهام أيضًا تجنب مشكلة التوقف والتكرار من خلال تتبع عدد مرات استخدام متغيرات معينة ثم تفضيل هذه المتغيرات التي تم استخدامها بشكل أقل.

الكفاءة في أسوأ الأحوال

تُعدّ طريقة السمبلكس فعّالة للغاية عمليًا، وقد مثّلت تحسّنًا كبيرًا مقارنةً بالطرق السابقة مثل طريقة فورييه-موتزكين للحذف . مع ذلك، في عام ١٩٧٢، قدّم كلي ومينتي [ ٣٢ ] مثالًا، وهو مكعب كلي-مينتي ، يُبيّن أن تعقيد أسوأ حالة لطريقة السمبلكس، كما صاغها دانتزيج، هو زمن أُسّي . ومنذ ذلك الحين، تبيّن أنه بالنسبة لكلّ تنويع تقريبًا لهذه الطريقة، توجد مجموعة من البرامج الخطية التي يكون أداؤها ضعيفًا فيها. ويبقى السؤال مطروحًا حول ما إذا كان هناك تنويع ذو زمن متعدد الحدود ، على الرغم من وجود قواعد محورية شبه أُسّية معروفة. [ ٣٣ ]

في عام ٢٠١٤، ثبت [ ٣٤ ] أن أحد أشكال طريقة السمبلكس يتميز بقدرته على حل أي مسألة في فئة NP ضمنيًا أثناء تنفيذ الخوارزمية، مع تكلفة إضافية متعددة الحدود. علاوة على ذلك، يُعد كل من تحديد ما إذا كان متغير معين يدخل في الأساس أثناء تنفيذ الخوارزمية على مدخلات معينة، وتحديد عدد التكرارات اللازمة لحل مسألة معينة، من المسائل الصعبة من فئة NP . [ ٣٤ ] في نفس الوقت تقريبًا، تم إثبات وجود قاعدة محورية اصطناعية يكون حساب مخرجاتها مسألة كاملة من فئة PSPACE . [ ٣٥ ] في عام ٢٠١٥، تم تعزيز هذا الإثبات لإظهار أن حساب مخرجات قاعدة دانتزيج المحورية مسألة كاملة من فئة PSPACE . [ ٣٦ ]

الكفاءة في الممارسة

أدى تحليل وتحديد كمية الملاحظة التي تُشير إلى كفاءة خوارزمية السمبلكس عمليًا، على الرغم من تعقيدها الأسي في أسوأ الحالات، إلى تطوير مقاييس أخرى للتعقيد. تتميز خوارزمية السمبلكس بتعقيد زمني متعدد الحدود في الحالة المتوسطة في ظل توزيعات احتمالية مختلفة ، حيث يعتمد الأداء الدقيق للخوارزمية في الحالة المتوسطة على اختيار التوزيع الاحتمالي للمصفوفات العشوائية . [ 37 ] [ 38 ] يستخدم نهج آخر لدراسة " الظواهر النموذجية " نظرية فئات باير من الطوبولوجيا العامة ، لإثبات أن "معظم" المصفوفات (طوبولوجيًا) يُمكن حلها بواسطة خوارزمية السمبلكس في عدد متعدد الحدود من الخطوات.

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

خوارزميات أخرى

تُشرح خوارزميات أخرى لحل مسائل البرمجة الخطية في مقال البرمجة الخطية . ومن خوارزميات التمحور الأخرى لتبادل الأساس خوارزمية التقاطع . [ 41 ] [ 42 ] توجد خوارزميات للبرمجة الخطية تعمل في زمن متعدد الحدود وتستخدم طرق النقطة الداخلية، ومنها خوارزمية خاتشيان الإهليلجية ، وخوارزمية كارماركار الإسقاطية ، وخوارزميات تتبع المسار . [ 15 ] تُعد طريقة Big -M استراتيجية بديلة لحل البرمجة الخطية، باستخدام مُركب سيمبلكس أحادي الطور. ويُمثل كوهين وآخرون [ 43 ] فرعًا من الخوارزميات التي تُطبق خوارزميات ضرب المصفوفات السريعة على البرامج الخطية.

البرمجة الخطية الكسرية

البرمجة الخطية الكسرية (LFP) هي تعميم للبرمجة الخطية (LP). في البرمجة الخطية، تكون دالة الهدف دالة خطية ، بينما في البرمجة الخطية الكسرية، تكون دالة الهدف نسبةً بين دالتين خطيتين. بعبارة أخرى، البرمجة الخطية هي برمجة خطية كسرية يكون مقامها دالة ثابتة قيمتها واحد في كل مكان. يمكن حل البرمجة الخطية الكسرية باستخدام أحد أشكال خوارزمية السمبلكس [ 44 ] [ 45 ] [ 46 ] [ 47 ] أو باستخدام خوارزمية التقاطع [ 48 ] .

انظر أيضاً

مراجع

  1. ↑ مورتي (1983 ، ص 52-53، القسم 2.1) 
  2. ↑ مورتي (1983 ، التعليق 2.2)
  3. ↑ مورتي (1983 ، ملاحظة 3.9)
  4. ↑ ستون، ريتشارد إي.؛ توفي، كريج أ. (1991). "خوارزميات التبسيط والتحجيم الإسقاطي كطرق للمربعات الصغرى المعاد ترجيحها تكراريًا". مجلة SIAM Review . 33 (2): 220-237 . doi : 10.1137/1033049 . JSTOR 2031142. MR 1124362 .  
  5. ↑ ستون، ريتشارد إي.؛ توفي، كريج أ. (1991). "تصحيح: خوارزميات التبسيط والتحجيم الإسقاطي كطرق مربعات دنيا مُعاد ترجيحها تكراريًا". مجلة SIAM Review . 33 (3): 461. doi : 10.1137/1033100 . JSTOR 2031443. MR 1124362 .  
  6. ↑ سترانج، جيلبرت (1 يونيو 1987). " خوارزمية كارماركار ومكانتها في الرياضيات التطبيقية". مجلة الرياضيات الذكية . 9 (2): 4-10 . doi : 10.1007/BF03025891 . ISSN 0343-6993 . MR 0883185. S2CID 123541868 .   
  7. ↑ دانتزيغ، جورج ب. (أبريل 1982). "ذكريات عن أصول البرمجة الخطية" (ملف PDF) . رسائل بحوث العمليات . 1 (2): 43-48 . doi : 10.1016/0167-6377(82)90043-8 . مؤرشف من الأصل في 20 مايو 2015.
  8. ↑ ألبرز وريد (1986). "مقابلة مع جورج ب. دانتزيج: أبو البرمجة الخطية" . مجلة الرياضيات الجامعية . 17 (4): 292-314 . doi : 10.1080/07468342.1986.11972971 .
  9. ↑ دانتزيغ، جورج (مايو 1987). "أصول طريقة السمبلكس" (ملف PDF) . في: ناش، ستيفن ج. (محرر). تاريخ الحوسبة العلمية . رابطة آلات الحوسبة. الصفحات 141-151 . doi : 10.1145/87252.88081 . ISBN  978-0-201-50814-7تمت أرشفة الملف (PDF) من النسخة الأصلية في 29 مايو 2015.
  10. ↑ مورتي (1983 ، النظرية 3.3)
  11. ↑ مورتي (1983 ، ص 143، القسم 3.13) 
  12. 1 2 مورتي (1983 ، ص 137، القسم 3.8) 
  13. 1 2 3 جورج ب. دانتزيج وموكند ن. ثابا. 1997. البرمجة الخطية 1: مقدمة . سبرينغر-فيرلاغ.
  14. 1 2 3 4 إيفار د. نيرينج وألبرت و. تاكر ، 1993، البرامج الخطية والمسائل ذات الصلة ، دار النشر الأكاديمية. (ابتدائي)
  15. 1 2 روبرت ج. فاندرباي، البرمجة الخطية: الأسس والتوسعات ، الطبعة الثالثة، السلسلة الدولية في بحوث العمليات وعلوم الإدارة، المجلد 114، سبرينغر فيرلاغ، 2008. ISBN 978-0-387-74387-5.
  16. ↑ مورتي (1983 ، القسم 2.2)
  17. ↑ مورتي (1983 ، ص 173) 
  18. ↑ مورتي (1983 ، القسم 2.3.2)
  19. ↑ مورتي (1983 ، القسم 3.12)
  20. 1 2 مورتي (1983 ، ص 66) 
  21. ↑ هاريس، باولا إم جيه. "طرق اختيار المحور في كود Devex LP." البرمجة الرياضية 5.1 (1973): 1-28
  22. ↑ مورتي (1983 ، ص 67) 
  23. ↑ مورتي (1983 ، ص 60) 
  24. 1 2 3 4 بادبيرج، م. (1999). التحسين الخطي والإضافات ( الطبعة الثانية). سبرينغر-فيرلاغ. رقم ISBN  3-540-65833-5.
  25. 1 2 دانتزيج، جورج ب .؛ ثابا، موكوند ن. (2003). البرمجة الخطية 2: النظرية والتوسعات . سبرينغر-فيرلاغ.
  26. ^ اليفراس، دميتريس. بادبيرج، مانفريد دبليو (2001). التحسين الخطي والإضافات: المشاكل والحلول . نص عالمي. سبرينغر-فيرلاغ. رقم ISBN 3-540-41744-3.(مسائل من بادبيرج مع حلولها.)
  27. ↑ ماروس، إستفان؛ ميترا، غوتام (1996). "خوارزميات سيمبلكس". في جيه إي بيزلي (محرر). التطورات في البرمجة الخطية والبرمجة العددية . أكسفورد ساينس. ص 1-46 . MR 1438309 .  
  28. ↑ ماروس، إستفان (2003). التقنيات الحسابية لطريقة سيمبلكس . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد 61. بوسطن، ماساتشوستس: دار نشر كلوير الأكاديمية. الصفحات: xx+325. ISBN   978-1-4020-7332-8MR 1960274 .​ 
  29. ↑ بلاند، روبرت ج. ( مايو 1977). "قواعد محورية محدودة جديدة لطريقة السمبلكس". رياضيات بحوث العمليات . 2 (2): 103-107 . doi : 10.1287/moor.2.2.103 . JSTOR 3689647. MR 0459599. S2CID 18493293 .   
  30. ↑ مورتي (1983 ، ص 79) 
  31. ↑ هناك مسائل تحسين مجردة، تسمى برامج الماترويد الموجهة ، والتي تدور فيها قاعدة بلاند (بشكل غير صحيح) بينماتنتهي خوارزمية التقاطع بشكل صحيح.
  32. ↑ كلي، فيكتور ؛ مينتي، جورج ج. (1972). "ما مدى جودة خوارزمية سيمبلكس؟". في شيشا، عوفيد (محرر). المتباينات III (وقائع الندوة الثالثة حول المتباينات التي عُقدت في جامعة كاليفورنيا، لوس أنجلوس، كاليفورنيا، 1-9 سبتمبر 1969، والمُهداة إلى ذكرى ثيودور س. موتزكين) . نيويورك-لندن: أكاديميك برس. ص 159-175 . MR 0332165 .  
  33. ↑ هانسن، توماس؛ زويك، أوري (2015)، "نسخة محسّنة من قاعدة التمحور العشوائي للوجه لخوارزمية سيمبلكس"، وقائع الندوة السنوية السابعة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 209-218 ، CiteSeerX 10.1.1.697.2526 ، doi : 10.1145/2746539.2746557 ، ISBN   9781450335362، S2CID 1980659 
  34. 1 2 ديسر، يان؛ سكوتيلا ، مارتن (2018/11/01). “خوارزمية Simplex هي NP-Mighty”. ايه سي ام ترانس. الخوارزميات . ١٥ (١): ٥: ١-٥: ١٩. أرخايف : 1311.5935 . دوى : 10.1145/3280847 . ردمك 1549-6325 . S2CID 54445546 .  
  35. ↑ أدلر، إيلان ؛ كريستوس، باباديميتريو ؛ روبنشتاين، أفياد (2014)، "حول قواعد التمحور في سيمبلكس ونظرية التعقيد"، البرمجة العددية والتحسين التوافقي ، سلسلة محاضرات في علوم الحاسوب، المجلد 17، الصفحات 13-24 ، arXiv : 1404.3320 ، doi : 10.1007/978-3-319-07557-0_2 ، ISBN   978-3-319-07556-3، S2CID 891022 
  36. ↑ فيرنلي، جون؛ سافاني، راهول (2015)، "تعقيد طريقة سيمبلكس"، وقائع الندوة السنوية السابعة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 201-208 ، arXiv : 1404.0605 ، doi : 10.1145/2746539.2746558 ، ISBN  9781450335362، S2CID 2116116 
  37. ^ ألكسندر شريفر ، نظرية البرمجة الخطية والأعداد الصحيحة . جون وايلي وأولاده، 1998، ISBN 0-471-98232-6(رياضي)
  38. ↑ تستغرق خوارزمية السمبلكس في المتوسط ​​D خطوة للمكعب. بورغواردت (1987) : بورغواردت، كارل-هاينز (1987). طريقة السمبلكس: تحليل احتمالي . الخوارزميات والتوافقية (نصوص دراسية وبحثية). المجلد 1. برلين: سبرينغر-فيرلاغ. الصفحات xii+268. ISBN   978-3-540-17096-9MR 0868467 .​ 
  39. ↑ سبيلمان، دانيال؛ تينغ، شانغ هوا (2001). "تحليل مُبسّط للخوارزميات: لماذا تستغرق خوارزمية سيمبلكس عادةً وقتًا متعدد الحدود". وقائع الندوة السنوية الثالثة والثلاثين لجمعية ACM حول نظرية الحوسبة . ACM. الصفحات 296-305 . arXiv : cs/0111050 . doi : 10.1145/380752.380813 . ISBN  978-1-58113-349-3. S2CID 1471 . 
  40. ↑ دادوش، دانيال؛ هويبرتس، صوفي (2020-01-01). "تحليل مبسط وسهل لطريقة سيمبلكس" . مجلة SIAM للحوسبة . 49 (5): STOC18–449. arXiv : 1711.05667 . doi : 10.1137/18M1197205 . ISSN 0097-5397 . S2CID 226351624 .  
  41. ↑ تيرلاكي، تاماس؛ تشانغ، شو تشونغ (1993). "قواعد المحور للبرمجة الخطية: دراسة استقصائية للتطورات النظرية الحديثة". حوليات بحوث العمليات . 46-47 (1): 203-233 . CiteSeerX 10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN 0254-5330 . MR 1260019. S2CID 6058077 .    
  42. ↑ فوكودا، كومي ؛ تيرلاكي، تاماس (1997). توماس م. ليبلينغ؛ دومينيك دي ويرا (محرران). "طرق التقاطع: نظرة جديدة على خوارزميات المحور" . البرمجة الرياضية، السلسلة ب . 79 ( 1-3 ). أمستردام: دار نشر نورث هولاند: 369-395 . doi : 10.1007/BF02614325 . MR 1464775. S2CID 2794181 .  
  43. ↑ كوهين، مايكل ب.؛ لي، ين-تات؛ سونغ، تشاو (2018). حل البرامج الخطية في زمن ضرب المصفوفات الحالي . المؤتمر السنوي الحادي والخمسون لجمعية آلات الحوسبة حول نظرية الحوسبة. STOC'19. arXiv : 1810.07896 .
  44. ↑ مورتي (1983 ، الفصل 3.20 (الصفحات 160-164) والصفحات 168 و179)
  45. ↑ الفصل الخامس: كرافن، ب. د. (1988). البرمجة الكسرية . سلسلة سيجما في الرياضيات التطبيقية. المجلد 4. برلين: دار نشر هيلدرمان. ص 145. ISBN   978-3-88538-404-5MR 0949209 .​ 
  46. ↑ كروك، سيرج؛ وولكوفيتش، هنري (1999). "البرمجة شبه الخطية". مجلة SIAM . 41 (4): 795-805 . Bibcode : 1999SIAMR..41..795K . CiteSeerX 10.1.1.53.7355 . doi : 10.1137/S0036144598335259 . JSTOR 2653207. MR 1723002 .   
  47. ↑ ماثيس، فرانك هـ.؛ ماثيس، لينورا جين (1995). " خوارزمية برمجة غير خطية لإدارة المستشفيات". مجلة SIAM Review . 37 (2): 230-234 . doi : 10.1137/1037046 . JSTOR 2132826. MR 1343214. S2CID 120626738 .   
  48. ^ إليس، تيبور. سزيرماي، أكوس؛ ترلاكي، تاماس (1999). "طريقة التقاطع المحدود للبرمجة الزائدية" . المجلة الأوروبية للبحوث التشغيلية . 114 (1): 198–214 . سيتيسيركس 10.1.1.36.7090 . دوى : 10.1016/S0377-2217(98)00049-6 . ردمك 0377-2217 .  

المراجع

مورتي، كاتا ج. (1983). البرمجة الخطية . نيويورك: جون وايلي وأولاده، رقم ISBN 978-0471097259MR 0720547 .​ 

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

هذه المقدمات مكتوبة لطلاب علوم الحاسوب وبحوث العمليات :

  • توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 29.3: خوارزمية سيمبلكس، الصفحات  790-804 .
  • فريدريك إس. هيلير وجيرالد جيه. ليبرمان: مقدمة في بحوث العمليات ، الطبعة الثامنة. ماكجرو هيل. ISBN 0-07-123828-X
  • راردين، رونالد ل. (1997). التحسين في بحوث العمليات . برنتيس هول. ص  919. ISBN 978-0-02-398415-0.