مقدمة للحلول الأساسية الممكنة في الهندسة

أنت تعرف ما يعنيه تحسين النظام للحصول على أفضل نتيجة ممكنة إذا كنت طالب هندسة أو مهندسًا.

يعد تحسين الحل هو مفتاح النجاح في كل شيء بدءًا من بناء الجسور وحتى صناعة البرامج.

تأتي فكرة الحل الأساسي الممكن في هذه المرحلة.

إنها فكرة أساسية في البرمجة الخطية تتيح لك معرفة أي مجموعة من الحلول الممكنة هي الأفضل.

لكن لماذا هو مهم جدا؟ في هذه المقالة ، سأتحدث عن الحلول الأساسية الممكنة وكيف يمكن استخدامها لحل المشكلات الهندسية في العالم الحقيقي.

سأتحدث عن كيفية العثور عليهم ، ومن هم مصنوعون ، ولماذا هم مهمون.

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

فهم الحل الأساسي المجدي

تعريف رسمي:

حل أساسي لنموذج برنامج خطي تكون فيه جميع المتغيرات غير سالبة.

الحل الأساسي المجدي (BFS) هو فكرة أساسية في البرمجة الخطية التي تساعد في إيجاد أفضل الحلول.

BFS هو حل بأقل عدد ممكن من المتغيرات غير الصفرية.

إنه ركن من المجسمات المتعددة السطوح للحلول الممكنة.

بمعنى آخر ، BFS هو حل أساسي يلبي القيود غير السلبية ويقع في المنطقة المجدية أو منطقة المشكلة.

إيجاد حل عملي أساسي أمثل

للعثور على أفضل BFS ، نحتاج إلى القيام بما يلي:

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

هذا المتغير هو الآن متغير أساسي ، ولم يعد أحد المتغيرات الأساسية الأخرى متغيرًا أساسيًا.

إذا كان هناك حل أمثل ، فيجب أن يكون عند أحد أطراف أو رؤوس المنطقة التي يمكن إيجاد الحلول فيها.

لذلك ، إذا كان LP لديه الحل الأمثل ، فلديه الحل الأمثل عند نقطة قصوى من المجموعة الممكنة.

أيضًا ، هناك دائمًا BFS مثالي إذا كان هناك حل مثالي.

استخدام طريقة Simplex لإيجاد BFS الأمثل

طريقة Simplex هي خوارزمية لحل المشكلات في البرمجة الخطية.

ينتقل من BFS إلى BFS "مجاور" باستخدام الإجراء المحوري.

في الإجراء المحوري ، يتم اختيار متغير غير أساسي ليصبح متغيرًا أساسيًا ، ثم يتم استخدام BFS الحالي لحل المتغيرات الأساسية الجديدة.

عندما لا يمكن تغيير متغير غير أساسي لتحسين وظيفة الهدف ، يتم إجراء الخوارزمية.

لماذا تعتبر الحلول الأساسية القابلة للتنفيذ ضرورية لحل المشكلات الهندسية المعقدة

لا يزال من الصعب فهمها؟ اسمحوا لي أن أغير وجهة النظر قليلاً:

من الذي يحتاج إلى إجابات بسيطة وعملية على أي حال؟ فقط ارمي كل شيء معًا وأتمنى الأفضل.

بعد كل شيء ، من يحتاج إلى التحسين عندما تكون الفوضى أكثر متعة؟ مرحبًا بكم في عالم المتغيرات غير السلبية ، حيث كل شيء مجرد اقتراح والفشل شبه مؤكد.

أو هو؟

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

حسنًا ، كانت هذه مجرد مزحة لتبدو وكأنها إعلان تلفزيوني.

الآن دعنا نعود إلى الشرح.

إيجاد حل عملي أساسي

الحل الأساسي المجدي (BFS) هو حل لمشكلة التحسين الخطية التي تلبي جميع القيود ولديها أقل عدد من المتغيرات غير الصفرية.

كل BFS هو ركن من متعدد الوجوه للحلول الممكنة من وجهة نظر هندسية.

إذا كان هناك أفضل حل ، فيجب أن يكون هناك أيضًا أفضل خطوة أولى.

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

إيجاد حل عملي أساسي مبدئي

يمكننا استخدام طرق مختلفة ، اعتمادًا على كيفية إعداد المشكلة ، للعثور على حل أساسي أولي يعمل مع مشكلة التحسين الخطي.

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

تصبح متغيرات الركود المتغيرات الأساسية ، والباقي متغيرات غير أساسية.

طريقة Simplex ثنائية الطور هي طريقة أخرى لحل المشكلة.

تتضمن هذه الطريقة حل مشكلة برمجة خطية إضافية لإيجاد حل أساسي أولي يكون ممكنًا.

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

إيجاد جميع الحلول الأساسية المجدية

يمكن أن يكون هناك أكثر من حل أساسي يعمل مع برنامج خطي.

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

بعد ذلك ، يتم استخدام هذه الحلول الأساسية الممكنة لإيجاد الحلول الأساسية الممكنة للمشكلة الأصلية.

إيجاد حل عملي أساسي بدون متغيرات Slack

نحتاج إلى استخدام متغيرات الركود للتخلص من قيود أقل من حتى نتمكن من إيجاد حل أساسي يعمل بدون متغيرات الركود.

متغير الركود هو الفرق بين الجانب الأيمن من القيد والجانب الأيسر.

على سبيل المثال ، للقيد الأول ، نحدد متغير الركود x4 = 14 - 2x1 - x2 - x3. من حيث هذا المتغير الجديد ، فإن القيد الأول يعادل ببساطة x4 ≥ 0 ، وهو قيد إيجابي لـ x4.

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

تسمى مجموعة المتغيرات الأساسية ، التي لها قيم غير الصفر في الحل الأساسي ، الأساس.

المتغيرات التي لها قيمة صفر في الحل الأساسي ليست متغيرات أساسية.

للعثور على أفضل حل ، نحتاج إلى إيجاد المتجه x الذي يلبي جميع القواعد ويحصل على أكبر أو أصغر قيمة للهدف.

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

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

للعثور على حل عملي أساسي ، تحتاج إلى استخدام طريقة simplex أو خوارزمية برمجة خطية أخرى للبحث عن حل يلبي جميع القيود ويحتوي على أقل عدد من المتغيرات غير الصفرية.

خصائص وأهمية الحل الأساسي المجدي

خصائص الحل الأساسي المجدي

يحتوي الحل الأساسي المجدي على معظم المتغيرات m التي ليست صفرية ومتغيرات nm على الأقل التي تكون صفرًا ، حيث n هو عدد متغيرات القرار و m هو عدد القيود.

A BFS هو ركن من متعدد الوجوه للحلول الممكنة ، ولكل BFS قيود نشطة مستقلة خطيًا.

إذا كان هناك أفضل حل ، فيجب أن يكون هناك أيضًا أفضل خطوة أولى.

أهم شيء في الحلول الأساسية الممكنة هو أنها نهايات مجموعة الحلول المحدبة لمشكلة البرمجة الخطية.

للعثور على أفضل إجابة ، تمر الخوارزمية البسيطة عبر سلسلة من BFSs.

تبحث خوارزمية Simplex في جميع الحلول الأساسية الممكنة بطريقة منظمة للعثور على أفضل الحلول.

أهمية الحل الأساسي المجدي

يعد العثور على حل أساسي ممكن أمرًا مهمًا لأنه يساعد في العثور على أفضل إجابة لمشاكل البرمجة الخطية.

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

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

بعد ذلك ، يتم استخدام هذه الحلول الأساسية الممكنة لإيجاد الحلول الأساسية الممكنة للمشكلة الأصلية.

فيديو: الحلول الأساسية المجدية

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

استخدم حالات

خاتمة

مع اقتراب هذه النظرة إلى الحلول الأساسية المجدية من نهايتها ، من الواضح أنها أداة مهمة لأي مهندس أو طالب هندسة.

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

ولكن أكثر من كونها مفيدة ، فهي تظهر كيف يمكن أن تكون الرياضيات أنيقة وجميلة.

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

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

لذلك ، عندما تتعلم المزيد عن الهندسة ، ضع في اعتبارك ما تعلمته عن الحلول البسيطة التي تعمل واستخدمها لجعل العالم مكانًا أفضل وأكثر كفاءة.

الروابط والمراجع

الكتب:

• البرمجة الخطية: الأسس والتوسعات
• البرمجة الخطية: النظرية والتطبيقات