تويت
البرمجة الخطية هي أسلوب رياضي يستخدم في اختيار الحل الأمثل من بين عشرات أو مئات او آلاف الحلول، ولذلك فإن تطبيقات البرمجة الخطية كثيرة ومتنوعة ومن بينها اختيار أفضل تكوين للخلايا. هذه المقالة يستفيد منها من له دراية بمبادئ البرمجة الخطية، وإن شاء الله سوف أكتب عن أساسيات البرمجة الخطية عدة مقالات في المستقبل.
معامل الاختلاف (عدم التماثل):
لكي نستخدم البرمجة الخطية فإننا نحسب معامل عدم التماثل dissimilarity بدلا من معامل التماثل، ويتم تعريف معامل عدم التماثل (الاختلاف) كالآتي:
معامل عدم التماثل (م أب) = مجموع القيمة المطلقة (أ ك– ب ك)
والمعادلة السابقة تعني أننا لو أردنا حساب معامل عدم التماثل لمنتجين أ و ب فإننا نستخدم مصفوفة المنتج الماكينة -التي تعرفنا عليها من قبل- ثم نمر على كل ماكينة ك فإن كان أ يحتاج ماكينة ك بينما ب لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (1-0) =1 ثم نمر على الماكينة التالية فلو كان ب يحتاجها بينما أ لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (0-1) = 1 ثم نمر على الماكينة التالية فإن كان كلا من أ و ب يحتاجها فإننا نحسب: القيمة المطلقة لـ ( 1 -1) = 0 ثم نمر على الماكينة التالية فإن كان كلا من المنتجين لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (0-0) = 0 وهكذا، ثم نجمع كل هذه الأرقام لتشكل معامل عدم التماثل للمنتجين. عملية تبدو معقدة ولكنها غاية في البساطة إذا جربتها.
فلكي نستعد لاستخدام البرمجة الخطية نحسب معامل عدم التماثل بين كل منتجين. لاحظ أن هذا يختلف عن معامل التماثل حيث أننا نحسبه لكل ماكينتين او خليتين بينما هنا نحسب معامل عدم التماثل لكل منتجين.
مثال:
افترض أننا سبع منتجات ونستخدم لذلك أربع ماكينات، وكانت مصفوفة المنتج الماكينة كالتالي:
احسب مصفوفة معامل الاختلاف (عدم التماثل).
باستخدام المعادلة أعلاه نحصل على المصفوفة كالتالي:
حاول التحقق من نتيجة الحسابات بنفسك. على سبيل المثال معامل الاختلاف بين منتج 2 ومنتج 6 = القيمة المطلقة (1-1) + القيمة المطلقة (0-0) + القيمة المطلقة (1-0) + القيمة المطلقة (0-1)= 0 + 1 +1 = 2. ومعامل الاختلاف بين منتج 1 ومنتج 5 = القيمة المطلقة (1-0) + القيمة المطلقة (1-0) + القيمة المطلقة (0-1) + القيمة المطلقة (1-1)= 1+1+1+0= 3.
نموذج البرمجة الخطية:
تعتمد هذه الطريقة على تكوين مجموعات (عائلات) من الأجزاء المتشابهة من حيث طريقة التصنيع. ويتكون نموذج البرمجة الخطية من:
دالة الهدف: تقليل قيمة Minimize:
مجموع حاصل ضرب (معامل عدم التماثل x متغيرات القرار)
المتغيرات الرئيسية سأ بهي متغيرات تأخذ إحدى قيمتين: إما صفر إذا لم يكن المنتج أ ينتمي للعائلة ب، أو واحد إذا كان منتج أ ينتمي للعائلة ب. وهذه المتغيرات يمكن وضعها في شكل مصفوفة كما في الجدول التالي:
والحل في النهاية يحدد قيم هذه المتغيرات كما بالشكل التالي:
جميع المتغيرات في المنطقة ذات اللون الأزرق الفاتح هي متغيرات القرار Decision Variables فعلى سبيل المثال منتج 1 ينتمي لعائلة 3 ومنتج 5 ينتمي لعائلة 2 ومنتج 2 ينتمي لعائلة 2. هذه المتغيرات لا يكون لها قيمة معروفة مسبقا وإنما نحصل على قيمتها من حل نموذج البرمجة الخطية. كما ترى فنحن نفترض عددا من العائلات يساوي عدد المنتجات ونطلب من البرمجة الخطية أن تختار العائلة المناسبة لكل منتج، وسوف يتضح لك أننا سنحدد أيضا عدد العائلات المسموح بتكوينها.
تقليل حاصل ضرب معامل عدم التماثل في متغيرات القرار يعني اختيار انتساب كل منتج لعائلة بحيث يقل المجموع الكلي لعدم التماثل (الاختلاف) أي تقليل الاختلاف بين مكونات عائلة المنتجات (الخلية) الواحدة وهذا هو ما يضمن لنا تقليل النقل بين الخلايا وهو ما يعني أيضا استقلالية الخلايا بأقصى قدر ممكن. هذه هي الفكرة الأساسية للنموذج.
حاصل ضرب معامل عدم التماثل في متغيرات القرار يأخذ الصورة الآتية في حالة خمس منتجات:
س11 x م11 + س21 x م21 + س31 x م31 + س41 x م41 + س51 x م51
+ س12 x م12 + س22 x م22 + س32 x م32 + س42 x م42 + س52 x م52
+ س13 x م13 + س23 x م23 + س33 x م33 + س43 x م43 + س53 x م53
+ س14 x م14 + س24 x م24 + س34 x م34 + س44 x م44 + س54 x م54
+ س15 x م15 + س25 x م25 + س35 x م35 + س45 x م45 + س55 x م55
هناك قيود (شروط) للحل Constraints وهي:
الشرط الأول: أن كل منتج ينتمي لعائلة واحدة فقط أي أن مجموع متغيرات القرار في الصف الواحد يساوي واحدا كما هو مبين بالشكل أعلاه، فلكي نضمن أن منتج 1 ينتمي لعائلة واحدة فقط فلابد أن يكون مجموع س11+س21+س31+س41+س51=1 أي أن أحدهم سيأخذ قيمة 1 والباقي صفرا، وهكذا بالنسبة لكل المنتجات.
الشرط الثاني أن متغيرات القرار س أ ب هي متغيرات ثنائية Binary أي أنها لا تقبل سوى صفرا أو واحدا. مثال: س11= صفر أو واحد، س12 = صفر أو واحد وهكذا.
الشرط الثالث والرابع مبنيان على أساس أن عائلة ب لو تكونت فلابد أن يكون فيها منتج رقم ب أي أن عائلة 3 لو تكونت فلابد أن يكون فيها منتج 3 وكذلك عائلة 5 لو تكونت فلابد أن يكون فيها منتج 5. لاحظ أن هذه طريقة مبتكرة لكي نستطيع التحكم في عدد العائلات. وتقع متغيرات القرار هذه في الخلايا الملونة باللون البني أدناه للتوضيح، فلو كانت قيمة المتغير في الخلية البنية لأحد الأعمدة تساوي صفرا فهذا يعني أن هذه العائلة ليس لها وجود أي لن يتم تكوينها.
الشرط الثالث هو أن متغيرات القرار لكل عائلة لابد أن تقل أو تساوي المتغير سب ب أي أن أي متغير في العمود لا يمكن أن يساوي واحد ما لم يكن المتغير الذي يتساوى فيه رقم المنتج مع رقم العائلة يساوي واحدا، أي أن س31 و س32 وس34 و س35 لا يمكن أن يساوي أيا منها واحدا ما لم يكن س33 = 1 وهكذا الحال في كل الأعمدة. وبما أن هذه المتغيرات ثنائية فإنه يمكننا صياغة هذا الشرط بأن نقول أن كل المتغيرات في العمود الواحد لابد ألا تكون قيمة أي منها أصغر من أو تساوي قيمة المتغير الذي يتساوى فيه رقم المنتج مع رقم العمود. مثال:
س52≤ س55 ، س51≤ س55 ، س53≤ س55 ، س54≤ س55
س12≤ س22 ، س32≤ س22 ، س42≤ س22 ، س52≤ س22
وهكذا ……
الشرط الرابع أن مجموع متغيرات القرار التي يتساوى فيها رقم المنتج مع رقم العائلة تساوي عدد العائلات التي نريدها، فنحن نحدد عددا من العائلات حسبما نريد. مثال:
س11+س22+س33+س44+س55 = عدد العائلات المطلوب
قد تتساءل ولماذا نفترض عددا للعائلات يساوي عدد المنتجات؟ إننا نسمح بذلك بتكوين أي عائلة ولكن هذا لا يعني أننا نريد تكوين عائلات بعدد المنتجات فبعض هذه العائلات لن يحتوي أي منتج أي أن كل متغيرات القرار في ذلك العمود تساوي صفرا في الحل النهائي وهو ما يعني أن هذه العائلة ليس لها وجود.
مثال:
افترض أننا ننتج أحد عشر جزءا باستخدام ثمان ماكينات وأن مصفوفة المنتج الماكينة كالتالي:
نريد استخدام البرمجة الخطية لتكوين خلايا التصنيع.
نبدأ بحساب معامل الاختلاف (عدم التماثل) لكل الأجزاء كالتالي:
نستخدم برنامج إكسل والذي يحتوي على Solver الذي يقوم بحل مسائل البرمجة الخطية.
نحدد الهدف والقيود في نافذة Solver
الهدف: هو تقليل الخلية C186 – بالطبع يمكنك أن تستخدم أي خلية لهذا الغرض.- والتي تساوي حاصل ضرب متغيرات القرار في معامل الاختلاف، وقد استخدمت لذلك الدالة Sumproduct.
القيود:
1- جميع متغيرات القرار في نفس العمود تساوي أو تقل عن متغير القرار في نفس العمود الذي يتساوى فيه رقم العائلة مع رقم المنتج
2- جميع متغيرات القرار ثنائية.
3- مجموع متغيرات القرار في نفس الصف تساوي واحدا لأن كل منتج سينتمي لعائلة واحدة فقط.
4- مجموع متغيرات القرار التي يتساوى فيها رقم المنتج مع رقم العائلة يساوي عدد العائلات الذي نحدده وقد وضعت رقم 3 في هذا المثال أي أننا نريد تكوين 3 عائلات فقط.
في البداية حصلتُ على هذا الحل
ولكن هذا الحل لم يعجبني لأنه خصص خلية خاصة للمنتج رقم 2 فقط فقلت ربما يكون حجم الطلب على هذا المنتج لا يكفي لتخصيص خلية فأضفت شرطا يمنع من تكوين العائلة رقم 2 وهو ان س22 =0 ثم حصلت على الحل التالي:
لاحظ أن العائلات 1 و 2 و3 و4 و 6 و7 و 8 و 9 لم تتكون، وأن العائلة رقم 5 تتكون من المنتجات أرقام 2، 5، 9، وأما العائلة رقم 10 فتتكون من المنتجات أرقام 1، 3، 8، 10، وأما العائلة رقم 11 فتتكون من باقي المنتجات، أي أننا قسمنا المنتجات إلى ثلاث عائلات أي ثلاث خلايا. ويمكننا تصور شكل الخلايا كالتالي:
البرمجة الخطية تتميز بالمرنة العالية فيمكنك وضع قيود أخرى مثلما وضعنا شرطا يمنع تكون العائلة رقم 2، فمثلا يمكنك وضع شرط يمنع وضع منتجين محددين في عائلة واحدة أو العكس، ويمكنك وضع شرط يمنع وضع أكثر من عدد محدد من المنتجات في نفس العائلة وهكذا. ويمكنك كذلك إضافة معامل آخر لمعامل الاختلاف مثل معامل اختلاف الضبط أو معامل اختلاف تسلسل عملية التصنيع وغير ذلك.
بهذا نكون قد استعرضنا بعض طرق تكوين الخلايا وسوف نناقش في المقالات التالية إن شاء الله كيفية تنظيم العمل في مخطط المنتج او مخطط الورشة.
معامل الاختلاف (عدم التماثل):
لكي نستخدم البرمجة الخطية فإننا نحسب معامل عدم التماثل dissimilarity بدلا من معامل التماثل، ويتم تعريف معامل عدم التماثل (الاختلاف) كالآتي:
معامل عدم التماثل (م أب) = مجموع القيمة المطلقة (أ ك– ب ك)
والمعادلة السابقة تعني أننا لو أردنا حساب معامل عدم التماثل لمنتجين أ و ب فإننا نستخدم مصفوفة المنتج الماكينة -التي تعرفنا عليها من قبل- ثم نمر على كل ماكينة ك فإن كان أ يحتاج ماكينة ك بينما ب لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (1-0) =1 ثم نمر على الماكينة التالية فلو كان ب يحتاجها بينما أ لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (0-1) = 1 ثم نمر على الماكينة التالية فإن كان كلا من أ و ب يحتاجها فإننا نحسب: القيمة المطلقة لـ ( 1 -1) = 0 ثم نمر على الماكينة التالية فإن كان كلا من المنتجين لا يحتاجها فإننا نحسب: القيمة المطلقة لـ (0-0) = 0 وهكذا، ثم نجمع كل هذه الأرقام لتشكل معامل عدم التماثل للمنتجين. عملية تبدو معقدة ولكنها غاية في البساطة إذا جربتها.
فلكي نستعد لاستخدام البرمجة الخطية نحسب معامل عدم التماثل بين كل منتجين. لاحظ أن هذا يختلف عن معامل التماثل حيث أننا نحسبه لكل ماكينتين او خليتين بينما هنا نحسب معامل عدم التماثل لكل منتجين.
مثال:
افترض أننا سبع منتجات ونستخدم لذلك أربع ماكينات، وكانت مصفوفة المنتج الماكينة كالتالي:
احسب مصفوفة معامل الاختلاف (عدم التماثل).
باستخدام المعادلة أعلاه نحصل على المصفوفة كالتالي:
حاول التحقق من نتيجة الحسابات بنفسك. على سبيل المثال معامل الاختلاف بين منتج 2 ومنتج 6 = القيمة المطلقة (1-1) + القيمة المطلقة (0-0) + القيمة المطلقة (1-0) + القيمة المطلقة (0-1)= 0 + 1 +1 = 2. ومعامل الاختلاف بين منتج 1 ومنتج 5 = القيمة المطلقة (1-0) + القيمة المطلقة (1-0) + القيمة المطلقة (0-1) + القيمة المطلقة (1-1)= 1+1+1+0= 3.
نموذج البرمجة الخطية:
تعتمد هذه الطريقة على تكوين مجموعات (عائلات) من الأجزاء المتشابهة من حيث طريقة التصنيع. ويتكون نموذج البرمجة الخطية من:
دالة الهدف: تقليل قيمة Minimize:
مجموع حاصل ضرب (معامل عدم التماثل x متغيرات القرار)
المتغيرات الرئيسية سأ بهي متغيرات تأخذ إحدى قيمتين: إما صفر إذا لم يكن المنتج أ ينتمي للعائلة ب، أو واحد إذا كان منتج أ ينتمي للعائلة ب. وهذه المتغيرات يمكن وضعها في شكل مصفوفة كما في الجدول التالي:
والحل في النهاية يحدد قيم هذه المتغيرات كما بالشكل التالي:
جميع المتغيرات في المنطقة ذات اللون الأزرق الفاتح هي متغيرات القرار Decision Variables فعلى سبيل المثال منتج 1 ينتمي لعائلة 3 ومنتج 5 ينتمي لعائلة 2 ومنتج 2 ينتمي لعائلة 2. هذه المتغيرات لا يكون لها قيمة معروفة مسبقا وإنما نحصل على قيمتها من حل نموذج البرمجة الخطية. كما ترى فنحن نفترض عددا من العائلات يساوي عدد المنتجات ونطلب من البرمجة الخطية أن تختار العائلة المناسبة لكل منتج، وسوف يتضح لك أننا سنحدد أيضا عدد العائلات المسموح بتكوينها.
تقليل حاصل ضرب معامل عدم التماثل في متغيرات القرار يعني اختيار انتساب كل منتج لعائلة بحيث يقل المجموع الكلي لعدم التماثل (الاختلاف) أي تقليل الاختلاف بين مكونات عائلة المنتجات (الخلية) الواحدة وهذا هو ما يضمن لنا تقليل النقل بين الخلايا وهو ما يعني أيضا استقلالية الخلايا بأقصى قدر ممكن. هذه هي الفكرة الأساسية للنموذج.
حاصل ضرب معامل عدم التماثل في متغيرات القرار يأخذ الصورة الآتية في حالة خمس منتجات:
س11 x م11 + س21 x م21 + س31 x م31 + س41 x م41 + س51 x م51
+ س12 x م12 + س22 x م22 + س32 x م32 + س42 x م42 + س52 x م52
+ س13 x م13 + س23 x م23 + س33 x م33 + س43 x م43 + س53 x م53
+ س14 x م14 + س24 x م24 + س34 x م34 + س44 x م44 + س54 x م54
+ س15 x م15 + س25 x م25 + س35 x م35 + س45 x م45 + س55 x م55
هناك قيود (شروط) للحل Constraints وهي:
الشرط الأول: أن كل منتج ينتمي لعائلة واحدة فقط أي أن مجموع متغيرات القرار في الصف الواحد يساوي واحدا كما هو مبين بالشكل أعلاه، فلكي نضمن أن منتج 1 ينتمي لعائلة واحدة فقط فلابد أن يكون مجموع س11+س21+س31+س41+س51=1 أي أن أحدهم سيأخذ قيمة 1 والباقي صفرا، وهكذا بالنسبة لكل المنتجات.
الشرط الثاني أن متغيرات القرار س أ ب هي متغيرات ثنائية Binary أي أنها لا تقبل سوى صفرا أو واحدا. مثال: س11= صفر أو واحد، س12 = صفر أو واحد وهكذا.
الشرط الثالث والرابع مبنيان على أساس أن عائلة ب لو تكونت فلابد أن يكون فيها منتج رقم ب أي أن عائلة 3 لو تكونت فلابد أن يكون فيها منتج 3 وكذلك عائلة 5 لو تكونت فلابد أن يكون فيها منتج 5. لاحظ أن هذه طريقة مبتكرة لكي نستطيع التحكم في عدد العائلات. وتقع متغيرات القرار هذه في الخلايا الملونة باللون البني أدناه للتوضيح، فلو كانت قيمة المتغير في الخلية البنية لأحد الأعمدة تساوي صفرا فهذا يعني أن هذه العائلة ليس لها وجود أي لن يتم تكوينها.
الشرط الثالث هو أن متغيرات القرار لكل عائلة لابد أن تقل أو تساوي المتغير سب ب أي أن أي متغير في العمود لا يمكن أن يساوي واحد ما لم يكن المتغير الذي يتساوى فيه رقم المنتج مع رقم العائلة يساوي واحدا، أي أن س31 و س32 وس34 و س35 لا يمكن أن يساوي أيا منها واحدا ما لم يكن س33 = 1 وهكذا الحال في كل الأعمدة. وبما أن هذه المتغيرات ثنائية فإنه يمكننا صياغة هذا الشرط بأن نقول أن كل المتغيرات في العمود الواحد لابد ألا تكون قيمة أي منها أصغر من أو تساوي قيمة المتغير الذي يتساوى فيه رقم المنتج مع رقم العمود. مثال:
س52≤ س55 ، س51≤ س55 ، س53≤ س55 ، س54≤ س55
س12≤ س22 ، س32≤ س22 ، س42≤ س22 ، س52≤ س22
وهكذا ……
الشرط الرابع أن مجموع متغيرات القرار التي يتساوى فيها رقم المنتج مع رقم العائلة تساوي عدد العائلات التي نريدها، فنحن نحدد عددا من العائلات حسبما نريد. مثال:
س11+س22+س33+س44+س55 = عدد العائلات المطلوب
قد تتساءل ولماذا نفترض عددا للعائلات يساوي عدد المنتجات؟ إننا نسمح بذلك بتكوين أي عائلة ولكن هذا لا يعني أننا نريد تكوين عائلات بعدد المنتجات فبعض هذه العائلات لن يحتوي أي منتج أي أن كل متغيرات القرار في ذلك العمود تساوي صفرا في الحل النهائي وهو ما يعني أن هذه العائلة ليس لها وجود.
مثال:
افترض أننا ننتج أحد عشر جزءا باستخدام ثمان ماكينات وأن مصفوفة المنتج الماكينة كالتالي:
نريد استخدام البرمجة الخطية لتكوين خلايا التصنيع.
نبدأ بحساب معامل الاختلاف (عدم التماثل) لكل الأجزاء كالتالي:
نستخدم برنامج إكسل والذي يحتوي على Solver الذي يقوم بحل مسائل البرمجة الخطية.
نحدد الهدف والقيود في نافذة Solver
الهدف: هو تقليل الخلية C186 – بالطبع يمكنك أن تستخدم أي خلية لهذا الغرض.- والتي تساوي حاصل ضرب متغيرات القرار في معامل الاختلاف، وقد استخدمت لذلك الدالة Sumproduct.
القيود:
1- جميع متغيرات القرار في نفس العمود تساوي أو تقل عن متغير القرار في نفس العمود الذي يتساوى فيه رقم العائلة مع رقم المنتج
2- جميع متغيرات القرار ثنائية.
3- مجموع متغيرات القرار في نفس الصف تساوي واحدا لأن كل منتج سينتمي لعائلة واحدة فقط.
4- مجموع متغيرات القرار التي يتساوى فيها رقم المنتج مع رقم العائلة يساوي عدد العائلات الذي نحدده وقد وضعت رقم 3 في هذا المثال أي أننا نريد تكوين 3 عائلات فقط.
في البداية حصلتُ على هذا الحل
ولكن هذا الحل لم يعجبني لأنه خصص خلية خاصة للمنتج رقم 2 فقط فقلت ربما يكون حجم الطلب على هذا المنتج لا يكفي لتخصيص خلية فأضفت شرطا يمنع من تكوين العائلة رقم 2 وهو ان س22 =0 ثم حصلت على الحل التالي:
لاحظ أن العائلات 1 و 2 و3 و4 و 6 و7 و 8 و 9 لم تتكون، وأن العائلة رقم 5 تتكون من المنتجات أرقام 2، 5، 9، وأما العائلة رقم 10 فتتكون من المنتجات أرقام 1، 3، 8، 10، وأما العائلة رقم 11 فتتكون من باقي المنتجات، أي أننا قسمنا المنتجات إلى ثلاث عائلات أي ثلاث خلايا. ويمكننا تصور شكل الخلايا كالتالي:
البرمجة الخطية تتميز بالمرنة العالية فيمكنك وضع قيود أخرى مثلما وضعنا شرطا يمنع تكون العائلة رقم 2، فمثلا يمكنك وضع شرط يمنع وضع منتجين محددين في عائلة واحدة أو العكس، ويمكنك وضع شرط يمنع وضع أكثر من عدد محدد من المنتجات في نفس العائلة وهكذا. ويمكنك كذلك إضافة معامل آخر لمعامل الاختلاف مثل معامل اختلاف الضبط أو معامل اختلاف تسلسل عملية التصنيع وغير ذلك.
بهذا نكون قد استعرضنا بعض طرق تكوين الخلايا وسوف نناقش في المقالات التالية إن شاء الله كيفية تنظيم العمل في مخطط المنتج او مخطط الورشة.
الملفات المرفقة