الحل الأساسي الممكن

بالنسبة للتعريفات الواردة أدناه، سنقدم أولاً البرنامج الخطي في ما يسمى بالصيغة المعادلة :

أقصى${\textstyle \mathbf {c^{T}} \mathbf {x} }$

رهناً بـ${\displaystyle A\mathbf {x} =\mathbf {b} }$و${\displaystyle \mathbf {x} \geq 0}$

أين:

• ${\displaystyle \mathbf {c^{T}} }$و${\displaystyle \mathbf {x} }$هي متجهات بحجم n (عدد المتغيرات)؛
• ${\displaystyle \mathbf {b} }$هو متجه بحجم m (عدد القيود)؛
• ${\displaystyle A}$هي مصفوفة من الرتبة m × n ؛
• ${\displaystyle \mathbf {x} \geq 0}$هذا يعني أن جميع المتغيرات غير سالبة.

يمكن تحويل أي برنامج خطي إلى شكل معادلة عن طريق إضافة متغيرات الركود .

كخطوة تنظيف أولية، نتحقق مما يلي:

• النظام${\displaystyle A\mathbf {x} =\mathbf {b} }$يوجد حل واحد على الأقل (وإلا فإن البرنامج الخطي بأكمله ليس له حل ولا يوجد شيء آخر يمكن فعله)؛
• جميع صفوف المصفوفة m${\displaystyle A}$مستقلة خطيًا ، أي أن رتبتها هي m (وإلا يمكننا ببساطة حذف الصفوف الزائدة دون تغيير البرمجة الخطية).

الحل الممكن للبرمجة الخطية هو أي متجه${\displaystyle \mathbf {x} \geq 0}$بحيث${\displaystyle A\mathbf {x} =\mathbf {b} }$نفترض وجود حل ممكن واحد على الأقل. إذا كان m = n ، فلا يوجد سوى حل ممكن واحد. عادةً ما يكون m < n ، لذا فإن النظام${\displaystyle A\mathbf {x} =\mathbf {b} }$للمسألة حلول عديدة؛ ويسمى كل حل من هذه الحلول حلاً ممكناً للمسألة الخطية.

أساس البرمجة الخطية هو مصفوفة فرعية غير منفردة من A، تحتوي على جميع الصفوف m و m < n عمود فقط.

أحيانًا، يُستخدم مصطلح الأساس ليس للمصفوفة الفرعية نفسها، بل لمجموعة مؤشرات أعمدتها. ليكن B مجموعة جزئية من m مؤشرًا من المجموعة {1، ...، n }. نرمز بـ${\displaystyle A_{B}}$المصفوفة المربعة m × m المكونة من m عمودًا من${\displaystyle A}$مفهرسة بواسطة B. إذا${\displaystyle A_{B}}$إذا كانت غير منفردة ، فإن الأعمدة المفهرسة بواسطة B تشكل أساسًا لفضاء الأعمدة لـ${\displaystyle A}$في هذه الحالة، نسمي B أساسًا للخط البرمجي.

منذ رتبة${\displaystyle A}$إذا كان m ، فإنه يمتلك أساسًا واحدًا على الأقل؛ بما أن${\displaystyle A}$إذا كان يحتوي على n عمودًا، فإنه يحتوي على الأكثر${\displaystyle {\binom {n}{m}}}$القواعد.

بفرض وجود أساس B ، نقول إن الحل الممكن${\displaystyle \mathbf {x} }$يُعتبر حلاً أساسياً ممكناً ذو أساس B إذا كانت جميع متغيراته غير الصفرية مُفهرسة بواسطة B ، أي لجميع${\displaystyle j\not \in B:~~x_{j}=0}$.

عمليًا، أسهل طريقة لإيجاد حل أمثل للبحث في العرض أولًا (BFS) هي استخدام خوارزمية سيمبلكس . تحتفظ هذه الخوارزمية، في كل مرحلة من مراحل تنفيذها، بـ "أساس حالي" B (مجموعة فرعية من m من أصل n متغيرًا)، و"حل أمثل حالي للبحث في العرض أولًا"، و"جدول حالي". الجدول هو تمثيل للبرنامج الخطي حيث تُعبَّر المتغيرات الأساسية بدلالة المتغيرات غير الأساسية: ^{[ 1 ] : 65}$${\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}$$أين${\displaystyle x_{B}}$هو متجه المتغيرات الأساسية m ،${\displaystyle x_{N}}$هو متجه من n متغير غير أساسي، و${\displaystyle z}$هو هدف التعظيم. بما أن المتغيرات غير الأساسية تساوي صفرًا، فإن البحث في العرض أولاً الحالي هو${\displaystyle p}$والهدف الحالي لتحقيق أقصى قيمة هو${\displaystyle z_{0}}$.

إذا كانت جميع المعاملات في${\displaystyle r}$إذا كانت النتائج سلبية، فـ${\displaystyle z_{0}}$يُعد هذا حلاً أمثل، حيث يجب أن تكون جميع المتغيرات (بما في ذلك جميع المتغيرات غير الأساسية) على الأقل صفرًا، لذا فإن السطر الثاني يعني${\displaystyle z\leq z_{0}}$.

إذا كانت بعض المعاملات في${\displaystyle r}$إذا كانت القيم موجبة، فقد يكون من الممكن زيادة هدف التعظيم. على سبيل المثال، إذا${\displaystyle x_{5}}$غير أساسي ومعامله في ${\displaystyle r}$إذا كانت القيمة موجبة، فإن زيادتها فوق الصفر قد تجعل${\displaystyle z}$أكبر. إذا كان من الممكن القيام بذلك دون انتهاك قيود أخرى، فإن المتغير المتزايد يصبح أساسيًا (يدخل الأساس)، بينما يتم تقليل بعض المتغيرات الأساسية إلى 0 للحفاظ على قيود المساواة وبالتالي يصبح غير أساسي (يخرج من الأساس).

إذا تمت هذه العملية بعناية، فمن الممكن ضمان ذلك.${\displaystyle z}$يزداد حتى يصل إلى أفضل قيمة BFS.

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

مع ذلك، فإنه من السهل إيجاد حل أمثل ممكن لأي برنامج خطي، ويكون في الوقت نفسه أساسيًا ، وذلك عند وجود أي حل أمثل . ^{[ 2 ] : انظر أيضًا "الروابط الخارجية" أدناه.}

يُطلق على الأساس B للبرمجة الخطية اسم الأساس الأمثل المزدوج إذا كان الحل${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$ يمثل حلاً أمثل للبرنامج الخطي المزدوج، أي أنه يقلل من${\textstyle \mathbf {b^{T}} \mathbf {y} }$بشكل عام، الأساس الأمثل الأولي ليس بالضرورة الأمثل الثنائي، والأساس الأمثل الثنائي ليس بالضرورة الأمثل الأولي (في الواقع، قد يكون حل الأساس الأمثل الأولي غير ممكن بالنسبة للثنائي، والعكس صحيح).

إذا كان كلاهما${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$هي حل أمثل للبحث في العرض أولاً للمسألة الخطية الأولية، و${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$إذا كان البحث في العرض أولاً (BFS) هو الحل الأمثل للبرمجة الخطية الثنائية، فإن الأساس B يُسمى أساس PD الأمثل . كل برنامج خطي له حل أمثل يمتلك أساس PD الأمثل، ويتم إيجاده بواسطة خوارزمية سيمبلكس . مع ذلك، فإن وقت تشغيلها أُسّي في أسوأ الحالات. أثبت نمرود مجدو النظريات التالية: ^{[ 2 ]}

• توجد خوارزمية ذات وقت متعدد الحدود بشكل قوي تقوم بإدخال حل أمثل للبرمجة الخطية الأولية وحل أمثل للبرمجة الخطية الثنائية، وتعيد أساسًا أمثلًا.
• إذا كان هناك خوارزمية ذات وقت متعدد الحدود قوي تقوم بإدخال حل أمثل فقط للبرمجة الخطية الأولية (أو البرمجة الخطية الثنائية فقط) وتعيد أساسًا أمثل، فإنه يوجد خوارزمية ذات وقت متعدد الحدود قوي لحل أي برنامج خطي (وهذه الأخيرة مشكلة مفتوحة مشهورة ).

يمكن تنفيذ خوارزميات ميغيدو باستخدام جدول، تمامًا مثل خوارزمية سيمبلكس. كما اقترح ميغيدو، بالتعاون مع بيلينغ، خوارزمية سريعة تستخدم خوارزميات ضرب المصفوفات السريعة . ^{[ 3 ]}