برمجة الأعداد الصحيحة المختلطة: دليل لصنع القرار الحسابي

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

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

خوارزميات بحوث العمليات

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

خوارزميات البرمجة الخطية

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

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

في مثالنا البسيط للغاية ، يمكننا أن نرى أن النتيجة المثلى هي 5 ، مع a = 2 و b = 3. في حين أن هذا مثال تافه إلى حد ما ، يمكنك على الأرجح تخيل نموذج برمجة خطي يستخدم آلاف المتغيرات ومئات القيود .

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

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

والتي ستكون معقدة نوعًا ما ويصعب حلها يدويًا أو التجربة والخطأ. سوف تستخدم برامج أبحاث العمليات عدة خوارزميات لحل هذه المشكلات بسرعة. إذا كنت مهتمًا بالخوارزميات الأساسية ، فإنني أوصي بالتعرف على طريقة simplex هنا وطريقة النقطة الداخلية هنا.

خوارزميات البرمجة الصحيحة

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

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

مثال على مشكلة حقيبة الظهر قد تحتوي على المعلمات التالية:

وسيبدو نموذج MIP كما يلي:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

الحل الأمثل ، في هذه الحالة ، هو أ = 0 ، ب = 1 ، ج = 0 ، د = 1 ، مع قيمة إجمالي العنصر 17.

ستتطلب المشكلة التي سنحلها اليوم أيضًا برمجة عدد صحيح حيث يمكن جدولة موظف في مصنع ما لمناوبة أو لا - من أجل البساطة ، لا يمكنك جدولة موظف لثلثي نوبة عمل في هذا المصنع.

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

مثال مشكلة: الجدولة

وصف المشكلة

اليوم ، سوف نستكشف مشكلة التوظيف في المصنع. بصفتنا إدارة المصنع ، سنرغب في تقليل تكاليف العمالة ، لكننا نريد ضمان تغطية كافية لكل وردية لتلبية طلب الإنتاج.

لنفترض أن لدينا خمس نوبات مع متطلبات التوظيف التالية:

ولنفترض أن لدينا العمال التالية أسماؤهم:

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

أدواتنا

بالنسبة لمشكلة اليوم ، سنستخدم برنامجًا مفتوح المصدر للقطع والتفرع يسمى CBC. سنتفاعل مع هذا البرنامج باستخدام PuLP ، وهي مكتبة نماذج أبحاث عمليات شائعة في Python. يمكنك العثور على معلومات عنها هنا.

يتيح لنا PuLP إنشاء نماذج MIP بأسلوب Pythonic للغاية ويتكامل بشكل جيد مع كود Python الحالي. يعد هذا مفيدًا جدًا نظرًا لأن بعض أدوات معالجة البيانات وتحليلها الأكثر شيوعًا مكتوبة بلغة Python ، وتتطلب معظم أنظمة أبحاث العمليات التجارية معالجة بيانات مكثفة قبل التحسين وبعده.

لإثبات بساطة وأناقة PuLP ، إليك مشكلة الحقيبة التي تم حلها سابقًا والتي تم حلها في PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

قم بتشغيل هذا ، ويجب أن تحصل على الإخراج:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

الآن في مشكلة الجدولة لدينا!

ترميز الحل لدينا

تشفير الحل واضح ومباشر. أولاً ، نريد تحديد بياناتنا:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

بعد ذلك ، نريد تحديد النموذج:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

والآن نطلبه فقط لحل وطباعة النتائج!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

بمجرد تشغيل الكود ، سترى المخرجات التالية:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

ارفع مستوى الصعوبة قليلاً: قيود إضافية

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

قيود إضافية

لنفترض أنه بسبب لوائح العمل الجديدة ، لا يمكن تكليف أي عامل بأكثر من نوبتين. لحساب زيادة العمل ، قمنا بتوظيف مساعدة Dothraki Staffing Group ، التي ستوفر ما يصل إلى 10 عمال Dothraki لكل وردية بمعدل 40 دولارًا لكل وردية.

بالإضافة إلى ذلك ، افترض أنه بسبب بعض النزاعات الشخصية المستمرة خارج مصنعنا ، فإن Cersei و Jaime غير قادرين على العمل في أي نوبات إلى جانب Daenerys أو Jon. بالإضافة إلى ذلك ، لا يستطيع خايمي وسيرسي العمل معًا في أي نوبات عمل. أخيرًا ، آريا ، التي لديها علاقات شخصية معقدة بشكل خاص ، غير قادرة على العمل في نفس التحول مع Jaime أو Cersei أو Melisandre.

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

المحلول

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

حدد قائمة الحظر وبعض القيود:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

تعبئة المتغيرات لتنفيذ قيود الحظر و max shift:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

أضف متغيرات Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

سنحتاج أيضًا إلى حلقة معدلة قليلاً لمتطلبات التحول والحظر الحاسوبي:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

وأخيرًا ، لطباعة النتائج:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

ويجب أن نكون على ما يرام. قم بتشغيل الكود وسترى الإخراج على النحو التالي:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

وإليكم الأمر ، نتيجة تحترم قائمة العمال المحظورين ، وتتبع لوائح العمل ، وتستخدم عمال الدوثراكيين بحكمة.

خاتمة

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

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

يمكنك العثور على جميع الأكواد المتعلقة بهذه المقالة على GitHub. إذا كنت ترغب في مناقشة المزيد ، شارك بتعليقاتك أدناه!