نماذج التخصيص

نموذج التخصيص" مسألة التوظيف أو التعيين( The assignnment problem)

 إن نموذج التخصيص (التعيين) هو احد النماذج الخاصة بمسالة النقل والتي هي إحدى تطبيقات البرمجة الخطية.

حيث أن إشكالية  مسائل التخصيص تتلخص في كيفية توزيع مجموعة من الوظائف على مجموعة من الأشخاص ، أو مجموعة من الآلات على مجموعة من المهام ، بحيث يؤدي ذلك إلى استخدامها بأعلى كفاءة ممكنة ،مما يؤدي إلى تحمل أقل تكاليف أو جني أعلى الأرباح شريطة أن يتم تخصيص لكل وظيفة شخص واحد أو آلة وحيدة فقط

و يمكن استخدام مشكلة التخصيص في المجالات التالية :

1.   تخصيص عدد معين من وسائل الإنتاج ( الآلات) لصناعة مجموعة من أوامر الإنتاج .

2.   توزيع وظائف أو أعمال معينة على عدد من العمال أو الموظفين .

3.   تخصيص وسائل نقل معينة لنقل لسلع من مكان إلى آخر

شروط استخدام مشاكل التخصيص  و التعيين :

1-  تساوي عدد الأشخاص مع عدد العمليات أو الوظائف المطلوب انجازها أي تكون المصفوفة مربعة ( عدد الأسطر يساوي عدد الأعمدة فيها ).

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

3-  كلفة الأداء معروفة و محددة سابقا و شروط عدم السلبية

4-  يجب أن يساوي العرض و الطلب 1 صحيح ( لا يوجد هناك كسر )

5-  في حالة عدم تساوي الصفوف مع الأعمدة يخلق نوع من عدم التوازن  فيتم اضافة سطر أو عمود وهمي يحمل تكاليف أو أرباح صفرية .

استخدام نموذج التخصيص

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

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

طرق حل مسـائل التخصيص :

هناك عدة طرق لحل مشاكل التخصيص منها :

1-  طريقة العد الكامل   complete enumeration method

2-  الطريقة الهنغارية Hungaretion method

3-  طريقة البرمجة الخطية  linear programming method

4-  طريقة النقل transportation method

1-طريقة العد الكامل :

تعتبر هذه الطريقة من أبسط الطرق المستخدمة في حل مشاكل التخصيص و تعتمد على تعداد جميع البدائل المحتملة ثم اختيار أفضلها على حسب الحالة التي نكون بصدد دراستها فنختار أقلها في حالة التكاليف و العكس في حالة الأرباح أي أكبر قيمة . حيث عدد البدائل الممكنة يساوي n و n!= n *(n-1)*...*(n-n)

مع العلم أن :1=! 0

مثال :

3 ! = 3*2*1=^

 5 ! = 5*4*3*2*1=120

6! = 6*5*4*3*2*1 = 720

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

مثال 01:

في مؤسسة مختصة في إنتاج الأجهزة الكهرومنزلية لدينا ثلاثة عمال صيانة  لصيانة ثلاثة آلات و كانت التكاليف  بالدينار الجزائري كما هو موضح في الجدول التالي :

المطلوب : ما هو التخصيص الأمثل باستخدام طريقة العد الكامل لتقليل التكاليف ؟

الحل :

عدد الآلات يساوي عدد العمال و يساوي 3 اذا عدد البدائل الممكنة هو :

3 ! = 3*2*1=6

إذا أفضل تخصيص هو :التخصيص السادس الذي يوافق أدنى تكلفة  أي:

العامل الثالث يقوم بصيانة الآلة الأولىA.

العامل الثاني يقوم بصيانة الآلة الثانيةB.

العامل الأول يقوم بصيانة الثالثة C.

و هذا بمجوع تكاليف مقدرة بــــــ:1050.

و إذا افترضنا أن المصفوفة في المثال هي مصفوفة أرباح فإننا نختار أكبر عائد الذي هو: 1470 دينار و الذي يوافق التخصيص الثاني أي :

العامل الأول يقوم بصيانة الآلة الأولىA.

العامل الثالث يقوم بصيانة الآلة الثانيةB.

العامل الثاني يقوم بصيانة الآلة الثالثة. C

2-الطريقة المجرية أو الهنغارية  Hungaretion method :

و ترجع تسميتها بهذا السم نسبة الى العالم المجري د.كوهن .Kuhn H. W. و هي تعتبر من اكثر الطرق كفاءة في ايجاد الحل الأمثل لمشاكل التخصيص .

و لايجاد أفضل تخصيص باستخدام هذه الطريقة نتبع الخطوات التالية:[2]

1-  طرح الصفوف : نأخذ أقل قيمة في كل صف و نطرحها من قيم ذلك الصف و لجميع الصفوف .

2-  طرح الأعمدة: نأخذ أقل قبمة في كل عمود و نطرحها من قيم ذلك العمود و لجميع الأعمدة.

3-  تغطية العناصر الصفرية : نغطي الأصفار في المصفوفة الناتجة من عملية طرح الصفوف و طرح الأعمدة و ذلك بأقل عدد ممكن من الخطوط الأفقية و العمودية .

4-  إذا كان عدد الخطوط التي تغطي الأصفار سواء كانت أفقية أو عمودية مساويا لعدد الصفوف أو الأعمدة فإننا نقوم بعملية التخصيص .

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

6-  الاستمرار في الخطوات 3 و 5 حتى إنهاء عملية التخصيص .

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

مثال 01 :

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

الحل :

الخطوة الأولى : طرح الصفوف : أقل قيمة بالنسبة للسطر الأول 450، الثاني 350 ،   و الثالث 250.

الخطوة الثانية : طرح الأعمدة:

أقل قيمة بالنسبة لكل الأعمدة هو 0 فالجدول يبقى كما هو :

الخطوة الثالثة : تغطية الأصفار

المرحلة  أو الخطوة الرابعة : بما أن عدد الأسطر يساوي عدد الأعمدة فإننا نقوم بعملية التخصيص كما يلي :

العامل الأول يقوم بصيانة الثالثة C.

العامل الثاني يقوم بصيانة الآلة الثانيةB.

العامل الثالث يقوم بصيانة الآلة الأولىA.

بمجموع تكاليف مقدرة ب :

250+350+450=1050

و في حالة اعتبرنا أن المصفوفة هي مصفوفة أرباح فالحل يكون باتباع الخطوات التالية :

 قبل البدأ في الحل نقوم بارجاع المصفوفة الى مصفوفة تكاليف بطرح كل القيم من أكبر قيمة في الجدول كما يلي :

أكبر قيمة في الجدول هي :600 و عليه يصبح الجدول كما يلي :

الخطوةالأولى : : طرح الصفوف : أقل قيمة بالنسبة للسطر الأول 0، الثاني 200 ،   و الثالث 100.

الخطوة الثانية : طرح الأعمدة:

أقل قيمة بالنسبة للعمود الأول 0 ، العمود الثاني 0 ، العمود الثالث 30

و عليه يصبح الجدول كما يلي :

الخطوة الثالثة : تغطية الأصفار

المرحلة  أو الخطوة الرابعة : بما أن عدد الأسطر يساوي عدد الأعمدة فإننا نقوم بعملية التخصيص كما يلي :

العامل الأول يقوم بصيانة الآلة الأولىA.

 العامل الثاني يقوم بصيانة الآلة الثالثة. C

العامل الثالث يقوم بصيانة الآلة الثانيةB.

بمجموع أرباح مقدرة بـ:

600+370+500=1470

مثال 02:

بافتراض أنه لدينا جدول التكاليف التالي :

المطلوب : ايجاد التخصيص الأمثل باستخدام الطريقة الهنغارية ؟

الحل :

الخطوة الأولى : : طرح الصفوف : أقل قيمة بالنسبة للسطر الأول 7، الثاني 2،   و الثالث 1 و الرابع 2. و عليه تصبح المصفوفة كما يلي :

الخطوة الثانية : طرح الأعمدة:

أقل قيمة بالنسبة للعمود الأول 0 ، العمود الثاني 0 ، العمود الثالث 0 و العمود الرابع 2

و عليه يصبح الجدول كما يلي :

الخطوة الثالثة : تغطية الأصفار

المرحلة  أو الخطوة الرابعة : بما أن عدد الأسطر لا يساوي عدد الأعمدة 4≠3 و بالتالي فإننا لا نستطيع القيام بعملية التخصيص و عليه  ننتقل الى:

الخطوة الخامسة : نقوم بإختيار أقل قيمة من القيم غير المغطاة و نطرحها من باقي القيم غير المغطاة و نضيفها إلى نقاط التقاطع و القيم المغطاة تبقى كما هي . أقل قيمة من القيم غير المغطاة هي 3

و عليه يصبح الجدول كما يلي :

الخطوة السادسة : نستمر في الخطوات 3 و5

تغطية الأصفار كما يلي :

بما أنه عدد الأسطر يساوي عدد الأعمدة فإنه يمكننا القيام بعملية التخصيص كما يلي :

العامل الأول يقوم بصيانة الآلة الرابعة D

 العامل الثاني يقوم بصيانة الآلة الأولى A أو الثانية B

العامل الثالث يقوم بصيانة الآلة الثانيةB أو الثالثة C.

العامل الرابع يقوم بصيانة الآلة الأولىA  أو الثالثة C

البديل الأول :

1  (D)

2  (A)

  3 (B)

  4 (C)

 بتكلفة تقدر ب :

9+5+1+2=17

البديل الثاني :

1  (D)

2  (B)

  3 (C)

  4 (A)

 بتكلفة تقدر ب : 17=2+4+2+9

مثال :

نفس المثال السابق و في حالة اعتبرنا أن المصفوفة هي مصفوفة أرباح فالحل يكون باتباع الخطوات التالية :

 قبل البدأ في الحل نقوم بارجاع المصفوفة الى مصفوفة تكاليف بطرح كل القيم من أكبر قيمة في الجدول كما يلي :

أكبر قيمة في الجدول هي :9 و عليه يصبح الجدول كما يلي:

الخطوة الأولى : : طرح الصفوف : أقل قيمة بالنسبة للسطر الأول 0، الثاني 1،   و الثالث 0 و الرابع 3. و عليه تصبح المصفوفة كما يلي :

الخطوة الثانية : طرح الأعمدة:

أقل قيمة بالنسبة للعمود الأول 1 ، العمود الثاني 2 ، العمود الثالث 0 و العمود الرابع 0

و عليه يصبح الجدول كما يلي :

الخطوة الثالثة : تغطية الأصفار

الخطوة الرابعة : بما أن عدد الأسطر لا يساوي عدد الأعمدة 4≠2 و بالتالي فإننا لا نستطيع القيام بعملية التخصيص و عليه  ننتقل الى:

الخطوة الخامسة : نقوم بإختيار أقل قيمة من القيم غير المغطاة و نطرحها من باقي القيم غير المغطاة و نضيفها إلى نقاط التقاطع و القيم المغطاة تبقى كما هي . أقل قيمة من القيم غير المغطاة هي1.

و عليه يصبح الجدول كما يلي :

الخطوة السادسة : نستمر في الخطوات 3 و5

تغطية الأصفار كما يلي :

بما أنه عدد الأسطر يساوي عدد الأعمدة فإنه يمكننا القيام بعملية التخصيص كما يلي :

العامل الأول يقوم بصيانة الآلة الأولى A

 العامل الثاني يقوم بصيانة الآلة الثالثة C

العامل الثالث يقوم بصيانة الآلة الرابعة D .

العامل الرابع يقوم بصيانة الآلة  الثانية B

بأرباح تقدر ب : 27=3+9+7+8

طريقة البرمجة الخطية :

حيث يرجع استخدام نموذج البرمجة الخطية إلى جورج دانتزنج (G.Dantzing) عندما أستخدم أسلوب السمبلكس لحل مشاكل البرمجة الخطية سنة 1947م,و تعرف البرمجة الخطية بأنها :

طريقة رياضية فعالة  لاختيار الخطة المثلى , فهي إجراء للبحث عن الحل الأفضل لمشاكل الأعمال التي تتضمن تفاعل متغيرات متعددة, و التي تشمل اختيار أفضل مزيج للموارد التي تؤدي إلى أقصى الأرباح أو أقل التكاليف و يمكن تعريفها أيضا :

هي عبارة عن طريقة أو أسلوب رياضي يستخدم للمساعدة في التخطيط و إتخاذ القرارات المتعلقة بالتوزيع الأمثل للموارد المتاحة, و ذلك بهدف زيادة الأرباح أو تخفيض التكاليف.

و تجدر الإشارة هنا إلى أن كلمة برمجة (Programming) ليست لها علاقة ببرمجة الحاسوب, و لكنها تعنيي وضع المشكلة بصيغة رياضية أو نموذج رياضي وحلها و التخطيط لها.

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

من التعريفات السابقة نستخلص أن النماذج الخطية هي :

تقنية وطريقة رياضية .

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

تستخدم في حل مشاكل الإدارة التي تتمثل في توزيع الموارد المحدودة على عدد  من الاستخدامات المتباينة

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

فعلى سبيل المثال هناك ثلاث عمال  يقومون بصيانة ثلاث آلات كل واحد من هؤلاء العمال يقوم بصيانة آلة واحدة و لنفرض أن cij هو الزمن اللازم للعامل  كي يقوم بصيانة الآلة  j  وفقا للجدول التالي :

و السؤال المطروح هو كيف يجب أن تنظم عملية الصيانة هذه حتى يكون زمن الصيانة الكلي أقل ما يمكن :

فإن الصياغة الرياضية لهذه المسألة تأخذ الشكل التالي :

Min 6X₁₁+4X₁₂+8X₁₃+9X₂₁+3X₂₂+6X₂₃+5X₃₁+2X₃₂+7X₃₃

S .C

X₁₁+X₁₂+_X13=1

X₂₁+X₂₂+X₂₃=1

X₃₁+X₃₂+X₃₃=1

X₁₁+X₂₁+X₃₁=1

X₁₂+X₂₂+X₃₂=1

X₁₃+X₂₃+X₃₃=1

X₁₁ ,X₁₂ ,X₁₃,X₂₁,X₂₂,X₂₃ ;X₃₁,X₃₂,X₃₃≥ 0

طرق حل مسائل البرمجة الخطية :

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

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

الطريقة الجبرية[3] : The Algebraic Method

تعد الطريقة الجبرية من الطرق الرياضية البحتة التي تعتمد على أسلوب التعويض الجبري للقيم المتوقعة للمتغيرات الداخلة في النموذج الرياضي وفقا الى عدد الطرائق الممكنة لهذه القيم ,و تستخدم هذه الطريقة عندما يحتوي النموذج على متغيرين فقط هما x1,x2 و لحل نموذج البرمجة الخطية بموجبها نتبع الخطوات التالية :

تقسيم متغيرات النموذج الرياضي الى قسمين هما

أ- المتغيرات الأساسية Basic variables: و هي تلك المتغيرات التي لها دور مهم في المشكلة و تكون قيم هذه المتغيرات أكبر من الصفر أي انّ xj≥0,si≥0 .

ب- المتغيرات غير الأساسية :non basic variables  و هي تلك المتغيرات التي ليس لها دور مهم في المشكلة و تكون هذه المتغيرات مساوية للصفر دائما أي أنّ xj=0,si=0

تحويل النموذج الرياضي من الصيغة القانونية  canonical form الى الصيغة المستقرة ( الصيغة القياسية standard form و ذلك باستخدام المتغيرات الراكدة slack variables في دالة الهدف و قيود النموذج كالاتي :

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

3 الطريقة المبسطة simplex method

إن الطريقة المبسطة هي وسيلة رياضية ذات كفاءة عالية في استخراج الحـلول المثـلى لمشكلات البرمجة الخطية بصورة عامة , و بسبب إمكانية برمجة المعلومات لمشكلات البرمجة الخطية على الحاسبة الالكترونية بهذه الطريقة أدى ذلك الى انتشار اســتخدام هذه الطريقة على مدى واسـع و بصورة كبيرة^[4].