طريقة البسيط هي واحدة من الطرق الرئيسية للبرمجة الخطية ، والذي يسمح لك لإيجاد الحل الأمثل لمشكلة في وجود قيود. بالنسبة للمبتدئين ، قد يبدو الأمر معقدا ومربكا. ومع ذلك ، بمساعدة دليل مفصل ، يمكنك فهم أساسياته وتعلم كيفية تطبيقه في الممارسة العملية.
بادئ ذي بدء ، من الضروري أن نفهم أن الطريقة البسيطة تعتمد على مبدأ إيجاد أقصى الحدود في مجال قيود مشكلة البرمجة الخطية. تعتمد الطريقة على فكرة الانتقال من قمة إلى أخرى وفقا لقيود المشكلة. تتكرر هذه الحركة حتى يتم العثور على الحل الأمثل.
لتطبيق طريقة البسيط ، يجب عليك أولا إنشاء نموذج رياضي لمشكلة البرمجة الخطية. هذا يعني أنك بحاجة إلى تحديد الوظيفة المستهدفة ، وكذلك جميع القيود المفروضة على حل المشكلة. ثم ، يتم صياغة المشكلة في شكل جدول يسمى الجدول البسيط.
تبدأ عملية الطريقة البسيطة نفسها باختيار العنصر المرجعي للجدول البسيط ، والذي سيتم من خلاله تنفيذ الحركة من رأس إلى آخر. بعد ذلك ، يتم تحويل الجدول البسيط للعثور على قمة مثالية جديدة والمضي قدما في خطوة جديدة في الطريقة. تستمر العملية حتى يتم العثور على حل للمشكلة.
- المفاهيم الأساسية لطريقة البسيط
- تطبيق طريقة البسيط في التحسين
- خطوات حل طريقة البسيط
- الخطوة 1: إنشاء جدول الأسلوب البسيط الأولي
- الخطوة 2: حدد العمود الأساسي والصف
- الخطوة 3: إعادة حساب جدول الأسلوب البسيط
- طريقة التحسين البسيط
- كيفية تحديد الحل الأمثل
- سؤال وجواب
المفاهيم الأساسية لطريقة البسيط
الطريقة البسيطة هي خوارزمية لحل البرمجة الخطية. يعتمد على التكرار فوق نقاط الزاوية لمتعدد السطوح المحدد بواسطة نظام قيود المشكلة. في هذه العملية ، تقلل الطريقة البسيطة المهمة لإيجاد النقطة الزاوية المثلى التي يتم عندها تحقيق الحد الأقصى أو الحد الأدنى من الوظيفة الموضوعية.
يتم استخدام المفاهيم الأساسية التالية في طريقة البسيط:
- المتغير الأساسي: هذا متغير يساوي 0 في جميع معادلات النظام باستثناء واحد. يعد اختيار المتغيرات الأساسية جزءا مهما من طريقة البسيط.
- الخطة الأساسية: هذه مجموعة من قيم المتغيرات الأساسية التي تفي بنظام المعادلات. الخطة الأساسية هي واحدة من الحلول الممكنة للمشكلة.
- الطريقة البسيطة الأساسية: هذا إجراء للانتقال من خطة أساسية إلى أخرى مع تحسين قيمة الوظيفة الموضوعية. يتضمن خطوتين رئيسيتين: اختيار متغير الإدخال واختيار متغير الإخراج.
- المتغير الذي يتم إدخاله: هذا متغير يدخل الأساس في خطة أساسية جديدة ، مما يزيد من الوظيفة المستهدفة.
- متغير الإخراج: هذا متغير يخرج عن خط الأساس في خطة أساسية جديدة ، مما يقلل من الوظيفة المستهدفة.
تستخدم طريقة البسيط على نطاق واسع لحل مشاكل التحسين في مختلف المجالات ، بما في ذلك الاقتصاد والهندسة واللوجستيات وغيرها. يعد تحديد وفهم المفاهيم الأساسية لطريقة البسيط خطوة أساسية نحو التطبيق الناجح لهذه الخوارزمية في الممارسة العملية.
تطبيق طريقة البسيط في التحسين
تعد طريقة البسيط واحدة من أكثر الخوارزميات شيوعا لحل مشكلات التحسين ، خاصة في البرمجة الخطية. يسمح لك بإيجاد الحل الأمثل للمشكلة من خلال تلبية القيود التي وضعتها المعادلات الخطية وعدم المساواة.
التحسين هو عملية إيجاد أفضل حل لمهمة معينة. يمكن أن يكون هذا تصغيرا أو تعظيم لوظيفة الهدف ، والتي تعتمد على مجموعة معينة من المتغيرات الخاضعة لقيود معينة. تنشأ مشاكل التحسين في العديد من المجالات ، بما في ذلك الاقتصاد والهندسة والفيزياء والبيولوجيا وغيرها.
تستخدم طريقة البسيط لحل مشاكل التحسين الخطي عندما يتم تعيين جميع القيود بواسطة المعادلات الخطية وعدم المساواة. يعتمد على فكرة الانتقال خطوة بخطوة من حل أساسي إلى آخر ، حتى يتم العثور على الحل الأمثل. الحل الأساسي هو حل نظام المعادلات التي تكون فيها قيم بعض المتغيرات صفرا ، والمتغيرات المتبقية غير صفرية.
تتطلب طريقة البسيط التحضير الأولي للمشكلة. يجب تقديم المشكلة الأصلية في شكل أساسي ، حيث تكون جميع المتغيرات غير سلبية بشكل حصري. ثم يتم تجميع جدول للطريقة البسيطة ، حيث يتم حساب معاملات الوظيفة الموضوعية والقيود ، ويتم إعطاء قيود على نوع المساواة. تتبع خطوات خوارزمية طريقة البسيط: اختيار الحل الأساسي الأولي ، وحساب العلاقات البسيطة ، والانتقال من خلال الجدول البسيط ، وتحديث الحل الأساسي والتحقق من شروط التوقف.
الطريقة البسيطة هي أداة فعالة لحل مشاكل التحسين ، خاصة في البرمجة الخطية. انها تسمح لك لإيجاد الحلول المثلى مع الأخذ بعين الاعتبار القيود وظيفة التحسين. ومع ذلك ، عند حل مشاكل كبيرة مع عدد كبير من المتغيرات والقيود ، يمكن أن تصبح طريقة البسيط معقدة حسابيا وتتطلب الكثير من الموارد. في مثل هذه الحالات ، يمكن تطبيق خوارزميات أكثر كفاءة مثل طريقة النقطة الداخلية.
خطوات حل طريقة البسيط
الطريقة البسيطة هي واحدة من خوارزميات البرمجة الخطية الرئيسية وتستخدم لحل مشاكل التحسين مع القيود. تتضمن خطوات حل طريقة البسيط ما يلي:
- تحديد المهمة
- بناء جدول بسيط
- اختيار عنصر مرجعي
- إعادة حساب صف مع عنصر مرجعي
- إعادة حساب الصفوف المتبقية من الجدول
- التحقق من حالة الأمثل
- الحصول على الحل الأمثل
دعونا ننظر في كل خطوة بمزيد من التفصيل:
- تحديد المهمة: في هذه الخطوة ، تحتاج إلى تحديد الوظيفة الموضوعية وقيود المهمة. تتم صياغة الوظيفة والقيود الموضوعية في شكل معادلات خطية وعدم مساواة. على سبيل المثال ، يمكن تمثيل الوظيفة الموضوعية على النحو التالي: ض = ج1س1 + ج2س2 + ... + نكسن ، حيث سي هي معاملات ، الحادي عشر هي متغيرات الحل.
- بناء جدول بسيط: في هذه الخطوة ، تحتاج إلى إنشاء جدول بسيط بناء على المهمة. يتكون الجدول البسيط من صفوف وأعمدة ، حيث يمثل كل صف نفسه كقيد ، والعمود الأخير هو معاملات الدالة الموضوعية والمصطلحات الحرة.
- اختيار عنصر مرجعي: في هذه الخطوة ، تحتاج إلى تحديد عنصر مرجعي من الجدول البسيط. يتم تحديد العنصر المرجعي وفقا للقاعدة: يتم تحديد العمود الذي يحتوي على أكبر قيمة سالبة في الصف الأخير من الجدول البسيط.
- إعادة حساب صف مع عنصر مرجعي: في هذه الخطوة ، تحتاج إلى إعادة حساب الصف مع العنصر المرجعي في الجدول البسيط. يتم إجراء إعادة الحساب وفقا لخوارزمية طريقة البسيط.
- إعادة حساب الصفوف المتبقية من الجدول: في هذه الخطوة ، من الضروري إعادة حساب الصفوف المتبقية من الجدول البسيط وفقا لخوارزمية طريقة البسيط.
- التحقق من حالة الأمثل: في هذه الخطوة ، من الضروري التحقق من حالة الأمثل. إذا كانت جميع القيم في الصف الأخير من الجدول البسيط غير سالبة ، فإن الحل الحالي هو الأمثل. خلاف ذلك ، من الضروري المتابعة إلى خطوة تحديد العنصر المرجعي.
- الحصول على الحل الأمثل: في هذه الخطوة ، تحتاج إلى الحصول على الحل الأمثل. يمكن الحصول على الحل الأمثل عن طريق تحديد المتغيرات الأساسية والقيم المقابلة لها.
بعد المرور بجميع الخطوات ، يمكنك الحصول على الحل الأمثل للمشكلة باستخدام طريقة البسيط.
الخطوة 1: إنشاء جدول الأسلوب البسيط الأولي
قبل البدء في حل المشكلة باستخدام طريقة البسيط ، من الضروري إنشاء جدول أولي سيتم استخدامه في عملية التكرار. يتضمن الجدول الأولي العناصر التالية:
- وظيفة الهدف.
- القيود.
- متغيرات إضافية.
- المتغيرات الأساسية وقيمها.
الوظيفة الموضوعية هي وظيفة تحتاج إلى تصغيرها أو تكبيرها. يتم تعريفه على أنه مجموعة خطية من المتغيرات ذات المعاملات ، والتي تسمى معاملات الوظيفة الموضوعية.
القيود هي الشروط التي يجب أن تفي بها المهام المتغيرة. يمكن تعريفها على أنها عدم مساواة خطية أو مساواة.
المتغيرات الإضافية هي المتغيرات التي تتم إضافتها لجعل القيود تبدو مثل المساواة. هذه المتغيرات هي جزء من الأساس.
المتغيرات الأساسية هي متغيرات لها قيم غير صفرية عند نقطة البداية وتؤثر على الوظيفة المستهدفة. عادة ما توجد قيمها ومعاملاتها في العملية التكرارية للحل بطريقة البسيط.
الخطوة 2: حدد العمود الأساسي والصف
في الخطوة الثانية من طريقة البسيط ، تحتاج إلى تحديد العمود الأساسي والصف الأساسي للتكرار التالي.
1. اختيار العمود الأساسي:
- نقوم بالتحقيق في قيم معاملات الدالة الموضوعية في صف عدم المساواة (جدول طريقة البسيط).
- نجد أصغر معامل بين القيم الموجبة. سيكون هذا العمود هو العمود الأساسي.
2. اختيار خط الأساس:
- احسب نسبة الجانب الأيمن والقيمة المقابلة للعمود الأساسي المحدد لكل صف.
- نجد أصغر نسبة موجبة. سيكون هذا الخط هو الخط الأساسي.
بعد تحديد العمود الأساسي والصف ، يتم إعادة حساب عناصر الجدول باستخدام الصيغ البسيطة والعلاقات البسيطة. هذا يسمح لك لإيجاد حل جديد ومواصلة التكرار مع الخطوات اللاحقة من طريقة البسيط.
الخطوة 3: إعادة حساب جدول الأسلوب البسيط
بعد تحديد عنصر الحل في الخطوة السابقة ، تأتي اللحظة لإعادة حساب المعلومات في جدول طريقة البسيط.
الخطوة الأولى في إعادة حساب الجدول هي قسمة الصف المسموح به على قيمة العنصر المسموح به. يتيح لك ذلك إحضار العنصر المسموح به إلى القيمة 1 ، والعناصر المتبقية في الصف المسموح به إلى القيم المقابلة.
بعد ذلك ، يجب إجراء عمليات لتقليل العناصر المتبقية في الجدول إلى الصفر. يمكن القيام بذلك عن طريق طرح ناتج الصف المسموح به بقيمة العنصر في نفس العمود مثل العنصر المسموح به من العناصر المقابلة للصفوف الأخرى.
بعد إجراء هذه العمليات ، سيتم استلام جدول جديد بقيم محدثة.
بعد ذلك ، تحقق من الجدول الناتج للقيم السالبة في صف الدقة. إذا كانت هناك مثل هذه القيم ، فإننا نعود إلى الخطوة الثانية لتحديد عنصر حل جديد وتكرار عملية إعادة حساب الجدول.
إذا لم تكن هناك قيم سالبة في سلسلة الدقة ، فقد حصلنا على الحل الأمثل للمشكلة.
في حالة الحد الأقصى للمهمة ، يمكن العثور على قيمة وظيفة الهدف في الخلية مع "ض" ، في حالة الحد الأدنى للمهمة — مع علامة سلبية.
وبالتالي ، فإن إعادة حساب جدول طريقة البسيط هو جزء لا يتجزأ من عملية حل مشكلة التحسين البسيط. بعد إعادة حساب الجدول ، نحصل على قيم متغيرة جديدة والقيمة المثلى لوظيفة الهدف.
طريقة التحسين البسيط
الطريقة البسيطة هي خوارزمية عددية فعالة لحل مشاكل البرمجة الخطية. يستخدم على نطاق واسع للتحسين في مختلف المجالات مثل الاقتصاد والهندسة والخدمات اللوجستية ، إلخ.
يعتمد التحسين البسيط على مفهوم متعدد السطوح البسيط في ن-الفضاء الأبعاد. البسيط هو مجموعة من النقاط (الرؤوس) التي تشكل مثلث ن الأبعاد. في مشكلة البرمجة الخطية ، يتم استخدام البسيط لإيجاد الحل الأمثل الذي يلبي القيود.
تتكون طريقة البسيط من عدة تكرارات ، كل منها يأخذ خطوة على طول حافة البسيط في اتجاه أكبر زيادة في الوظيفة المستهدفة. وبالتالي ، يتم تحسين قيمة وظيفة الهدف في كل تكرار ، بشرط استيفاء قيود المهمة. تستمر العملية حتى يتم الوصول إلى الحل الأمثل ، عندما لا يكون من الممكن تحسين قيمة وظيفة الهدف.
المراحل الرئيسية لطريقة البسيط:
- عرض المشكلة في شكل قانوني.
- تعريف البسيط الأولي.
- البحث عن الحل الأمثل.
- التحقق من الأمثل وإنهاء الخوارزمية.
يمكن تمثيل خطوات طريقة البسيط كجدول بسيط ، حيث يمثل كل صف حالة البسيط في كل تكرار. يوضح الجدول قيم المتغيرات والمتغيرات الأساسية وقيم الوظيفة المستهدفة والقيود وما إلى ذلك. يساعد هذا في تقديم الخوارزمية بطريقة مرئية أكثر وتتبع التغييرات في كل خطوة.
تحتوي طريقة البسيط على العديد من الاختلافات ، مثل طريقة البسيط على مرحلتين ، وطريقة الأساس الاصطناعي ، وما إلى ذلك. يمكن تطبيق كل طريقة من هذه الطرق اعتمادا على تفاصيل المهمة ودقة التحسين المطلوبة.
من المهم أن تضع في اعتبارك أن طريقة البسيط هي طريقة تحسين تقريبية وقد تكون غير فعالة لبعض فئات المشاكل. في مثل هذه الحالات ، يمكن استخدام خوارزميات تحسين أكثر تعقيدا ، مثل طرق النقاط الداخلية أو طرق البرمجة الجينية.
كيفية تحديد الحل الأمثل
بعد تكرار طريقة البسيط وإيجاد حل أساسي ، من الضروري التحقق مما إذا كان الحل الذي تم العثور عليه هو الأمثل. الحالة المثلى هي الحالة التي تصل فيها قيمة دالة الهدف إلى الحد الأدنى أو الحد الأقصى للقيمة ، اعتمادا على مهمة البرمجة الخطية.
يتم استخدام المعايير التالية لتحديد أمثل الحل: إذا كانت جميع المعاملات في الصف الأخير من الجدول البسيط غير سالبة أو غير صفرية ، فإن الحل الموجود هو الأمثل.
باستخدام الجدول البسيط الناتج ، نتحقق من جميع القيم في الصف الأخير. إذا كانت جميع القيم غير سالبة أو غير صفرية ، فلدينا الحل الأمثل الذي يمكن اعتباره نهائيا. في هذه الحالة ، فإن القيم الموجودة للمتغيرات المقابلة للأساس الأمثل هي الحل الأمثل المطلوب للمشكلة.
إذا كانت هناك قيم سالبة في السطر الأخير ، فيجب إجراء تكرار ثان لطريقة البسيط لإيجاد حل جديد. في التكرار الثاني ، يتم تحديد العمود المرجعي والصف المرجعي ، وبعد ذلك يتم تنفيذ نفس الخطوات كما في التكرار الأول لطريقة البسيط. تتكرر العملية حتى يتم العثور على الحل الأمثل.