مرحباً بك في إجابة - موسوعة الأسئلة والإجابات الحرة
اطرح سؤالاً:


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

من إجابة
اذهب إلى: تصفح, البحث
Question red.png

سـؤال

ما هي هذه الطريقة ومتى نلجأ إليها وكيف يمكن برمجتها؟

محتويات

[عدل]

رد

طريقة السمبلكس أو طريقة التبسيط هي خوارزمية قابلة للبرمجة طورها جورج دانتزغ George Dantzig عام 1948 وتعد من أعظم تطبيقات البرمجة الخطية في القرن العشرين لحل مسائل البرمجة الخطية التي تتعدى المتغيرين أو الثلاثة والتي يصبع إن لم يكن مستحيلاً حلها في رسومات بيانية. معلوم أن من الممكن حل مسائل البرمجة الخطية ذات المتغيرين بشكل رسومات ثنائية البعد وكذلك مسائل المتغيرات الثلاثة في ثلاثة أبعاد أو في بعدين مؤلفين من ثلاثة أبعاد افتراضية (رسم على الورق). عند محاولة دراسة نظم خطية من 3 متغيرات أو أكثر فإن الرسم البياني يصبح أمراً غير تطبيقي ويلزم تغيير مفهوم الرسومات جذرياً والاعتماد على طرق أخرى أسهل.

[عدل] البرمجة الخطية

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

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

فمثلاً في متغيرين \(x_1,x_2\)، إذا أردنا أن نجد أصغر قيمة للمقدار \(c_1x_1 + c_2 x_2\) بشرط أن يحقق الحل المتباينات التالية (انظر على البرمجة الخطيةموقع الرياضيات رمز): \[\begin{array}{l}a_{11}x_1+a_{12}x_2 \leq b_1 \\a_{21}x_1+a_{22}x_2 \leq b_2 \\a_{31}x_1+a_{32}x_2 \leq b_3\end{array}\]

في حالة متغيرين في مجموعة حل نظام المتراجحات تكون عادة محددة بمضلع ما. والمبرهنة الرئيسة للبرمجة الخطية هي أن النقطة المثلى (إن وجدت) هي أحد رؤوس هذا المضلع. يمكن تعميم المثال السابق لـ n من المتغيرات بـ m من المتراجحات.

تكون مجموعة حل نظام المتباينات عبارة فوق-مسطح polytope في الفضاء \(\mathbb R^n\)، وتكون النقطة المثلى إن وجدت أحد رؤوس فوق-المسطح. وتسمى هذه المنطقة المحصورة بالمسطح بالمجموعة الممكنة feasible set، وإن كانت المجموعة خالية فإن المسألة غير ممكنة infeasible.

[عدل] خوارزم الحل بطريقة سمبلكس

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

  • يتم أولاً صياغة المشكلة في نموذج رياضياتي بحيث نضع دالة الهدف،

[عدل] مثال

لتكن لدينا دالة الهدف،

<m>Minimize Z = 1.5 x_1 + 1.8 x_2 ~~~ (1)</m>

خاضعة للشروط التالية:

<m>3 x1 + 2 x_2 <= 15000 ~~~ (2)</m>
<m>x1 + 2 x_2 <= 1000 ~~~ (3)</m>
<m>0 <= x_1 <= 4000 ~~~ (4)</m>
<m>0 <= x_2 <= 4500 ~~~ (5)</m>
  • بعدها يتم تحويل المتباينات إلى معادلات عبر إضافة أو طرح متغيرات بحسب نوع المتباينة (هل هي اصغر من أو تساوي أم أكبر أو تساوي). تعرف هذه المتغيرات بالمتغيرات الخاملة أو الراكدة Slack Variables. في المثال السابق نحصل على
<m>3 x_1 + 2 x_2 + x_3 ~~~~~~~~~~= 15000 ~~~ (6)</m>
<m>x1 + 2 x_2 + ~~~~~~ x_4~~~~~~ = 1000 ~~~ (7)</m>
<m>x_1 + ~~~~~~~~~~~~~~~x_5~~~= 4000 ~~~ (8)</m>
<m>x_2 + ~~~~~~~~~~~~~~~~~x_6= 4500 ~~~ (9)</m>

حيث ان:

    • عدد الساعات الغير مستغلة في قسم التصنيع = x3
    • عدد الساعات الغير مستغلة في قسم التجميع = x4
    • عدد الوحدات الغير منتجة من النوع الأول برغم حاجة السوق لها. = x5
    • عدد الوحدات الغير منتجة من النوع الثاني برغم حاجة السوق لها. = x6
  • ثالثا : - إظهار دالة الهدف وكذلك معادلات القيود بدلالة كافة المتغيرات الأصلية والخاملة وبنفس ترتيب متغيرات دالة الهدف ، ويتم ذلك بوضع المعامل الحسابي (صفر) للمتغير الغير موجود بالأساس في المعادلة وكما يلي : -

$$\text{Maximize } 1.5 x_1 + 1.8 x_2 + 0x_3 + 0x_4 + 0x_5 + 0x_6 ~ ~ ...(1)$$ $$\text{Subject } 3x_1 + 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 = 15000 ~ ~ ...(2)$$ $$~ ~ ~~ ~ ~ x_1 + 2x_2 + 0x_3 + x_4 + 0x_5 + 0x_6 = 10000 ~ ~ ...(3)$$ $$~ ~ ~~ ~ ~ x_1 + 0x_2 + 0x_3 + 0x_4 + x_5 + 0x_6 = 4000 ~ ~ ...(4)$$ $$~ ~ ~~ ~ ~ 0x_1 + x_2 + 0x_3 + 0x_4 + 0x_5 + x_6 = 4500 ~ ~ ...(5)$$

  • رابعا : إنشاء جدول السمبلكس، وهو الجدول الذي سيتم في داخله حل المشكلة المدروسة . ويتكون الجدول وكما هو مبين

بالجدول التالي

الكمية المتاحة 1.5 1.8 0 0 0 0 →صف ربح الوحدة للمتغير
x1 x2 x3 x4 x5 x6 →صف التغيرات الأصلية والخاملة
15000 3 2 1 0 0 0 →صف قيد قسم التصنيع
10000 1 2 0 1 0 0 →صف قيد قسم التجميع
4000 1 0 0 0 1 0 →صف قيد الطلب على النوع الأول
4500 0 1 0 0 0 1 →صف قيد الطلب على النوع الثاني

لمزيد من المعلومات حول هذا المثال يمكن الرجوع للمصدر http://www.startimes.com/f.aspx?t=22582509

[عدل] انظر أيضاً

[عدل] وصلات خارجية للاستزادة

يمكن زيارة http://www.zweigmedia.com/RealWorld/tutorialsf4/framesSimplex.html لمعرفة المزيد عن طريقة السمبلكس والإفادة أيضاً من بعض البرامج الموجودة في الموقع مثل Simplex Method Tool وPivot and Gauss-Jordan Tool والمكتوبان بلغة جافا سكربت (سيتم شرحهما وكتابة الشفرة المصدرية على موقع إجابة لاحقاً) وكذلك ملف تطبيق اكسل Excel pivot and Gauss-Jordan tool للمهتمين بذلك.

[عدل] أسئلة ذات صلة

  • رسم شكل خماسي بواسطة الفرجار
  • أوجد نهاية الدالة lim tan(4x) / sqrt(1-cos(6x)) عندما x تؤول إلى 0
  • ما هو أكبر عدد من الزوايا القائمة في أي مضلع؟
  • حساب طول منحنى
  • طريقة نيوتن
  • ما هي نتيجة قسمة عدد غير صفري على الصفر مثل 1\0؟
  • ثلاثة أعداد مجموعها 6، مجموع مربعاتها 8، مجموع مكعباتها 5 فما مجموع قواها الرابعة
  • إثبات متطابقة جيب مجموع زاويتين المثلثية
  • ما هي جذور المعادلة 2x + 10/(x^3+1) - 4 وهل هي كثيرة حدود؟
  • ما هى قوانين مساحة المثلث؟
  • أدوات شخصية

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