طريقة السمبلكس

طريقة السمبلكس

الطريقة البيانيّة أو الطريقة بالرسم تستخدم فقط عندما يكون عندنا متغيرين فقط.

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

·       نظام السمبلكس .. يعتمد نظام الصفّ البسيط والمصفوفات وما يسمى بعامود الوحدة.

مثال: البرمجة الخطية الطريقة المبسطة ( السمبلكس )

عظم ر 20س1 + 10س2

(ع.ب):

2س1 + 1س2 ≤ 40

        1س1 + 2س 2 ≤ 44

         س1 ، س2 ≥0   قيد اللاسلبية

الخطوة الأولى هي تحويل المشكلة من الشكل العادي إلى الشكل المثالي أو المعياري ..

  عظم ر 20س1+10س2 + 0ح1 + 0ح2

ويجب تحويل الاقتران أو المتباينة إلى معادلة إلى إشارة يساوي (=) ..

(ع.ب):

2س1 + 1س2 + 1ح1 = 40

1س1 + 2س2 + 1ح2 = 44

س1 ، س2 ، ح1 ، ح2 ≥ 0   

عظّم ر .. إذاً المشكلة مشكلة تعظيم ربح

قاعدة: السمبلكس أو الطريقة المبسّطة يجب أن تبدأ من نقطة الأصل .  سواءً كانت المشكلة تكاليف تعظيم أو تخفيض

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

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

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

يجب أن تضيف إلى الطرف الأقل متغيّر وهمي يحمل رقم القيد المعني .. فنقول ح1 ..

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

بناءً على ذلك :

يصبح القيد الأول./  2 س1+1س2+1ح1=40

القيد الثاني  أصبح الآن 0+0=0 و0+1ح2=44 ..إذاً ح2 =44 ..

* إذا أضفنا ح2 يجب أن نضيف ح2 إلى دالة الهدف فنضيف + 0ح1 .. في دالة الهدف ..  فأي إجراء تتخذه على القيد نعكسه مباشرة في نفس اللحظة على دالة الهدف . فتكون (  عظم ر 20س1+10س2 + 0ح1 + 0ح2 )

* أي إجراء يعمل على القيود عند تحويل المشكلة إلى الشكل المعياري يجب أن ينعكس على شيئين.. وهما :

1/- دالة الهدف.          2/- قيود اللاسلبية.

قيد اللاسلبية يجب أن يتضمن جميع القيود أو جميع المتغيرات التي بالمشكلة س1،س2،ح1،ح2..

·       س1 وس2 متغيرات حقيقية .. كالطاولات والكراسي تستطيع أن تلمسهم وتراهم ..

·       ح1 وح2 متغيرات وهمية ليس لهم على أرض الواقع من وجود إنما هي عملية تحايل رياضي .

بما أن:  2س1 + 1س2 الطرف إشارة أقل من أو يساوي نضيف متغير حر 1ح1=40

ومباشرة نضيف في بداية دالة الهدف عظم ر 20س1 + 10س2 0ح1 ونضع ح1  في قيد اللاسلبية.

القيد الثاني أضفنا ح1 ح2 فيصبح 1س1 +2س2 + 1ح2 = 44

* جميع المتغيرات الحقيقية والوهمية يجب أن تكون اكبر أو تساوي صفر. (   س1،س2، ح1،ح2≥  0  )

ملاحظات:

1/ في الشكل المثالي نضيف إلى دالة الهدف جميع المتغيرات الحرة ويكون معاملها في دالة الهدف صفر..لأنها متغيرات وهميّه .. ولأن الصفر لا يؤثر على حل معادلتنا ..

2/ نضيف إلى كل قيد يحمل إشارة  ≤  في الشكل الأصلي متغير حر (ح) يكون معامله في القيد المعني (1) ويحمل رقم القيد مثلاً ح1 مقصود به المتغير الحر للقيد الأول وهكذا .. وذلك لتحويل المتباينة إلى إشارة مساواة.

3/ نضيف جميع المتغيرات الحرة ح1،ح2 إلى قيود اللاسلبية ويجب أن تكون اكبر أو تساوي صفراً..وذلك لتطبيق مبدأ اللاسلبية

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

5- دائماً نبدأ بتشكيل الحل الأولي من خلال الجدول الأولي عند نقطة الأصل حيث س1 = صفر س2 = صفر ←

جدول الحل الأولي عند نقطة الأصل  س1=0   س2=0 )

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

في السطر الأول لاحظ  س1   س2  ح1   ح2  هذه المتغيرات الحقيقية والغير حقيقية.

( ر  ح ) في السطر الثاني 20 ، 10 ، 0 ، 0  تُمثل معادلات دالة الهدف. وهي إجمالي الربح المتحقق حيث:

·       دخول وحدة واحدة من س1 وهي الطاولات إلى مزيج الحل سوف يزيد الربح بمقدار 20

·       وإدخال وحدة واحدة من س2 إلى مزيج الحل سوف يولد ربح إجمالي بمقدار 10

·       وإدخال وحدة واحدة من ح1 إلى مزيج الحل كـ متغير سوف يزيد الربح الإجمالي بمقدار صفر .

( ر   ح ) تُمثل صف وعمود، الصف وهو 20 - 10 - 0 – 0  وهي المساهمة الربحية         ( الربح الإجمالي )،

المتغيرات التي تحت مزيج الحل ح1   ح2 معاملاتهم عمودياً  ( ر  ح ) مدى مساهمتهم في الربح الكلي  صفر ، صفر ،

سؤال : عند نقطة الأصل كم تساوي ح1 ؟  الجواب:    ح1 = 40  لماذا ؟ لأن س1=0     و س2=0 

في المنطقة المحصورة ما بين ح1 و ح2 :

الأرقام الموجودة في السطر الثاني مقابل ح1: 2 ، 1 ، 1 ، صفر ، 40   ←  هذه هي معاملات المتغيرات في القيد الأول

أضفنا ح2 واعتبرناها صفر حتى لا نترك خانة فاضيه وضعنا فيها صفر،

 ( 2س1 + 1س2 + 1ح1 )  1ح1 لأننا نتكلم عن القيد الأول، ويجب أن يكون في المصفوفة رقم1 تعكس رقم القيد المعني، و ح1 هنا يسمى الصف المرتبط بالقيد.

لماذا 1ح2؟ لأن المتغير الحُر يجب أن يكون معامله في القيد المعني ح2 هو ( 1 ) وفي دالة الهدف ( صفر ) وأيضاً ( 44 ) .

ما هي :      ( ز  ح ) : هي تُمثل الأشياء التي يُمكن أن أخسرها أو يجب عليّ أن أدفعها وبالتالي هي تُقلل هامش الربح من أجل أن أتم صناعة الشيء، إذاً هي تكاليف،

لو أردت أن أدخل س1 إلى مزيج الحل كم سأخسر ؟ سأخسر بمقدار ( ز   ح ) الرقم الذي تحت س1،

ولو أردت أن أُدخِل س2 كم سأخسر ؟ سأخسر الرقم الذي في صف ( ز   ح ) .

من أين أتينا بــ ( صفر ، صفر ، صفر ، صفر  ز   ح ) ولماذا لا يوجد أرقام أخرى ؟ الجواب : لأنني عند نقطة الأصل حيث س1= صفر و س2= صفر وبالتالي أنا لم أبدأ الإنتاج أصلاً، لأنه لا يوجد عندي تكلفة.

وبالتالي التكاليف (صفر)، والربح أيضا (صفر).

كيف نحسب الربح ؟

المتغيرات الحقيقية س1 و س2 هل دخلت إلى مزيج الحل ؟ لااا لم تدخل إلى مزيج  الحل.

·       (جميع المتغيرات التي لم تدخل إلى مزيج الحل تُسمى متغيرات غير أساسية )،

·       ( المتغيرات التي تدخل إلى مزيج الحل نسميها متغيرات أساسية ) .

إذاً:  س1 و س2 متغيرات غير أساسية لأنهما غير موجودان في عمود مزيج الحل.

 بينما ح1 و ح2 موجودان في مزيج الحل.

مساهمة ح1 لو أدخلناها إلى مزيج الحل، فسوف تساهم في زيادة الربح الإجمالي بمقدار (صفر).

و ح2 = صفر.   إذا الربح = صفر.

إذاً ( ز     ح ) تُمثل التكاليف .

ر    ح  -ز  ح  يعني : إجمالي الربح – التكاليف هذا نسميه؟ صافي الربح .

كيف نحسب صافي الربح ؟ عن طريق المعادلة :  ر  ح  -  ز  ح

الأرقام الموجودة في ر  ح تطرح منها الأرقام الموجودة في صف  ز  ح

·       ر  ح  كم تحت س1 = 20 و ز  ح = صفر إذا  ( 20-0=20 )

·       ر  ح  في الصف الثاني لـ س2 = 10  و ز  ح لـ س2 = صفر إذاً ( 10- صفر =10)

·       ، نذهب إلى ح1 كم ألــ ر  ح التي تتبعها ؟ صفر وكم ألـ ز  ح التي تتبعها ؟ صفر إذً  (صفر – صفر =صفر).

·       ثم نذهب لـ ح2 كم معاملها في صف ر  ح ؟ صفر, وكم قيمتها في    ز  ح ؟ صفر، إذاً (صفر – صفر =صفر).

ر  ح  -  ز  ح  له تسمية أخرى وهي (صف صافي التقييم ) ومعنى صف صافي التقييم: أي أننا نقيم نتيجة الحل ولا نحسب الربح فقط عند تلك النقطة.

وبما أن  ر  ح  -  ز  ح  هي تعظيم الأرباح، إذاً أنا عند نقطة الأصل (صفر) أمامي خيارين، إما أذهب إلى س1 أو س2

يهمني أن أحصل على صافي ربح أكبر ما يمكن، إذا يجب أن أختار الرقم الأكثر موجب وهو الرقم (20) في أخر صف، إذاً هنا أنا أُقيم بناءً على آخر صف وهو صافي الربح، أكبر رقم موجب 20،

إذاً من الأفضل أخذ ألــ 20 لأن المتغير الذي يُقابل أعلى رقم موجب وهو س1،

جدول رقم ( 1)  :

جدول الحل الأولي عند نقطة الأصل س1=0 ، س2 =0

                      الرقم المحوري

مزيج الحل		س1	س2	ح1	ح2	الكمية	النسبة	صف الارتكاز
	ر ح	20	10	0	0
ح1	0	2	1	1	0	40	20
ح2	0	1	2	0	0	44	44
ز ح		0	0	0	0	الربح 0
ر ح – ز ح		20	10	0	0