هندسة خوارزمية التحسين مع HorusLP في بایثون| الجزء الثاني

خوارزمية التحسين مع HorusLP

لمتابعة موضوع هندسة خوارزمية التحسين مع HorusLP، يجب عليك قراءة الجزء الأول من هذه المقالة.

البحث عن قيود غير متوافقة

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

لنفترض أننا أضفنا قيودًا وانتهى بنا الأمر بمجموعة القيود التالية:

class SizeConstraint(Constraint):
    def define(self, camera, figurine, cider, horn):
        return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15


class SizeConstraint2(Constraint):
    def define(self, camera, figurine, cider, horn):
        return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20


class MustHaveItemConstraint(Constraint):
    def define(self, cider):
        return cider >= 1

class IncompatibleConstraint1(Constraint):
    def define(self, camera):
        return camera >= 1


class IncompatibleConstraint2(Constraint):
    def define(self, camera):
        return camera <= 0

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

افترض أيضًا أن القيود مجمعة بالطريقة التالية مما قد يجعل عملية الكشف أكثر صعوبة:

class CombinedConstraints1(Constraint):
    dependent_constraints = [SizeConstraint2, IncompatibleConstraint1]


class CombinedConstraints2(Constraint):
    dependent_constraints = [SizeConstraint, IncompatibleConstraint2]

# MustHaveItemConstraint will be included in the problem definition independently

هنا تعريف المشكلة:

class KnapsackProblem(Problem):
    variables = KnapsackVariables
    objective = ValueObjective
    constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint]
    sense = MAXIMIZE

قم بتشغيل المشكلة وسترى النتيجة التالية:

KnapsackProblem: Infeasible

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

prob.print_results(find_infeasible=True)

سهل هكذا! قم بتشغيل الكود والآن يجب أن ترى ما يلي كإخراج:

KnapsackProblem: Infeasible
Finding incompatible constraints...
Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

رائعة! لقد أثبتنا الآن أن MustHaveItemConstraint ليس سبب عدم الجدوى وأن المشكلة ترجع إلى CombinedConstraints1 و CombinedConstraints2.

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

prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

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

KnapsackProblem: Infeasible
Finding incompatible constraints...
Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

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

بناء الخوارزميات من ملفات البيانات

عند بناء النماذج نادرًا ما نمتلك رفاهية كتابة التعليمات البرمجية لكل قيد ومتغير. في كثير من الأحيان يجب أن يكون برنامجنا مرنًا بدرجة كافية لتغيير النموذج اعتمادًا على بيانات الإدخال. لنفترض أنه بدلاً من الإدخال ذي الترميز الثابت أردنا إنشاء مشكلة حقيبة الظهر من JSON التالي:

{
  "items": [
    {"name": "camera", "value": 5, "weight": 2},
    {"name": "figurine", "value": 7, "weight": 4},
    {"name": "apple", "value": 2, "weight": 7},
    {"name": "horn", "value": 10, "weight": 10},
    {"name": "banana", "value": 9, "weight": 2}
  ],
  "capacity": 15
}

يمكننا القيام بذلك من خلال الاعتماد على دعم kwargs لدالة “define” التي ننفذها للقيود والأهداف.

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

JSON = '''
{
  "items": [
    {"name": "camera", "value": 5, "weight": 2},
    {"name": "figurine", "value": 7, "weight": 4},
    {"name": "apple", "value": 2, "weight": 7},
    {"name": "horn", "value": 10, "weight": 10},
    {"name": "banana", "value": 9, "weight": 2}
  ],
  "capacity": 15
}
'''

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

Import json

الآن دعنا نعدل رمز الإعداد المتغير لدينا بالتالي:

mip_cfg = json.loads(JSON)

class KnapsackVariables(VariableManager):
    vars = [
        BinaryVariable(i['name']) for i in mip_cfg['items']
    ]

سيحدد هذا متغيرًا لكل عنصر من العناصر في JSON ويطلق عليه اسمًا مناسبًا.

دعونا نغير القيد والتعريفات الموضوعية مثل:

class CapacityConstraint(Constraint):
    def define(self, **kwargs):
        item_dict = {i['name']: i['weight'] for i in mip_cfg['items']}
        return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity']


class ValueObjective(ObjectiveComponent):
    def define(self, **kwargs):
        item_dict = {i['name']: i['value'] for i in mip_cfg['items']}
        return sum(kwargs[name] * item_dict[name] for name in kwargs)

من خلال طلب **kwargs بدلاً من المتغيرات المحددة تحصل دالة define على قاموس يحتوي على جميع المتغيرات بالاسم. يمكن لوظيفة تعريف القيد الوصول إلى المتغيرات من القاموس.

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

الباقي واضح ومباشر:

class KnapsackProblem(Problem):
    variables = KnapsackVariables
    constraints = [CapacityConstraint]
    objective = ValueObjective
    sense = MAXIMIZE


prob = KnapsackProblem()
prob.solve()
prob.print_results()

قم بتشغيل هذا البرنامج وسترى الإخراج التالي:

KnapsackProblem: Optimal
camera 1.0
figurine 0.0
apple 0.0
horn 1.0
banana 1.0
ValueObjective: 24.00
CapacityConstraint: 14.00

تحديد المقاييس المخصصة في HorusLP

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

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

From horuslp.core import Metric

دعونا الآن نحدد المقياس المخصص:

class NumFruits(Metric):
    name = "Number of Fruits"

    def define(self, apple, banana):
        return apple + banana

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

نحتاج الآن إلى إضافة المقياس إلى تعريف المشكلة. الواجهة هنا مرة أخرى مشابهة جدًا لتعريف القيد:

class KnapsackProblem(Problem):
    variables = KnapsackVariables
    constraints = [CapacityConstraint]
    objective = ValueObjective
    metrics = [NumFruits]
    sense = MAXIMIZE

قم بتشغيل هذا وسترى الإخراج التالي:

KnapsackProblem: Optimal
camera 1.0
figurine 0.0
apple 0.0
horn 1.0
banana 1.0
ValueObjective: 24.00
CapacityConstraint: 14.00
Number of Fruits: 1.00

يمكنك رؤية عدد الثمار المطبوعة في الأسفل.

التعامل مع مشكلة أكثر تعقيدًا: حقيبتان

دعونا نعمل من خلال مثال أكثر تعقيدًا بعض الشيء. افترض أنه بدلاً من حقيبة واحدة لدينا حقيبة وحقيبة سفر. لدينا أيضًا فئتان من الأشياء متينة وهشة. الحقيبة كونها أكثر حماية يمكن أن تحتوي على سلع هشة ودائمة. من ناحية أخرى لا يمكن للحقيبة أن تحتوي إلا على السلع المعمرة. افترض أيضًا أن البيانات الخاصة بالعناصر معطاة في JSON التالي:

{
  "fragile": [
    {"name": "camera", "value": 5, "weight": 2},
    {"name": "glasses", "value": 3, "weight": 4},
    {"name": "apple", "value": 2, "weight": 7},
    {"name": "pear", "value": 5, "weight": 3},
    {"name": "banana", "value": 9, "weight": 2}
  ],
  "durable": [
    {"name": "figurine", "value": 7, "weight": 4},
    {"name": "horn", "value": 10, "weight": 10},
    {"name": "leatherman", "value": 10, "weight": 3}
  ],
  "suitcase_capacity": 15,
  "bag_capacity": 20
}

دعونا نرى كيف يغير هذا النموذج. لنبدأ بسجل فارغ لأن النموذج سيكون مختلفًا تمامًا. ابدأ بإعداد المشكلة:

import json
from horuslp.core.Variables import BinaryVariableGroup
from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent
from horuslp.core.constants import MAXIMIZE

JSON = '''
{
  "fragile": [
    {"name": "camera", "value": 5, "weight": 2},
    {"name": "glasses", "value": 3, "weight": 4},
    {"name": "apple", "value": 2, "weight": 7},
    {"name": "pear", "value": 5, "weight": 3},
    {"name": "banana", "value": 9, "weight": 2}
  ],
  "durable": [
    {"name": "figurine", "value": 7, "weight": 4},
    {"name": "horn", "value": 10, "weight": 10},
    {"name": "leatherman", "value": 10, "weight": 3}
  ],
  "suitcase_capacity": 15,
  "bag_capacity": 20
}
'''
mip_cfg = json.loads(JSON)

لنقم الآن بإعداد المتغيرات. سنقوم بإعداد متغير ثنائي لكل مجموعة عناصر / حاوية محتملة.

class KnapsackVariables(VariableManager):
    vars = [
        # suitcase can hold both fragile and durable goods 
        BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]),
        BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]),
        # bag can only hold durable goods.
        BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']])
    ]

نريد الآن تطبيق قيود الوزن لكل من الحقيبة والحقيبة.

class SuitcaseCapacityConstraint(Constraint):
    def define(self, suitcase_d, suitcase_f):
        fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']])
        durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']])
        return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity']


class BagCapacityConstraint(Constraint):
    def define(self, bag_d):
        durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])
        return durable_weight <= mip_cfg['bag_capacity']

نحتاج الآن إلى تنفيذ قيد أكثر تعقيدًا بعض الشيء – القيد الذي يضمن عدم دخول أي عنصر في كل من الحقيبة والحقيبة – أي إذا كان متغير ” in the suitcase ” هو 1 فإن ” in the bag” يجب أن يكون المتغير صفرًا والعكس صحيح. بالطبع نريد التأكد من السماح بالحالات التي ينتهي فيها العنصر في أي من الحاوية أيضًا.

لإضافة هذا القيد نحتاج إلى تكرار جميع العناصر المتينة والعثور على متغير “in the suitcase” ومتغير “in the bag” والتأكيد على أن مجموع هذه المتغيرات أقل من 1.

يمكننا تحديد القيود التابعة ديناميكيًا بسهولة تامة في HorusLP:

class UniquenessConstraints(Constraint):
    def __init__(self):
        super(UniquenessConstraints, self).__init__()
        # call the dependent constraint builder function for every durable item, and push them into dependent constraints. 
        dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']]
        self.dependent_constraints = dependent_constraints

    def define_uniqueness_constraint(self, item):
        # classes are first-class objects in python, so we can define a class within this function and return it
        class UQConstraint(Constraint):
            # we name the constraint based on the item this is for, so that debugging is easier.
            name = "Uniqueness_%s" % item['name']

            def define(self, suitcase_d, bag_d):
                # the define function can access the variables much in the same way as other functions
                return suitcase_d[item['name']] + bag_d[item['name']] <= 1

        return UQConstraint

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

class TotalValueObjective(ObjectiveComponent):
    def define(self, suitcase_f, suitcase_d, bag_d):
        fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']])
        durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']])
        durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])
        return fragile_value + durable_value_s + durable_value_d

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

class SuitcaseFragileWeightMetric(Metric):
    def define(self, suitcase_f):
        return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']])


class SuitcaseDurableWeightMetric(Metric):
    def define(self, suitcase_d):
        return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']])


class BagWeightMetric(Metric):
    def define(self, bag_d):
        return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

الآن انتهينا من جميع الأجزاء فلنقم بإنشاء مثيل للمشكلة وتشغيل النموذج:

class KnapsackProblem(Problem):
    variables = KnapsackVariables
    constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints]
    objective = TotalValueObjective
    metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric]
    sense = MAXIMIZE

prob = KnapsackProblem()
prob.solve()
prob.print_results()

قم بتشغيل هذا وسترى الإخراج التالي في stdout الخاص بك:

KnapsackProblem: Optimal
suitcase_f[camera] 1.0
suitcase_f[glasses] 1.0
suitcase_f[apple] 1.0
suitcase_f[pear] 0.0
suitcase_f[banana] 1.0
suitcase_d[figurine] 0.0
suitcase_d[horn] 0.0
suitcase_d[leatherman] 0.0
bag_d[figurine] 1.0
bag_d[horn] 1.0
bag_d[leatherman] 1.0
TotalValueObjective: 32.00
SuitcaseCapacityConstraint: 15.00
BagCapacityConstraint: 17.00
Uniqueness_figurine: 1.00
Uniqueness_horn: 1.00
Uniqueness_leatherman: 1.00
SuitcaseDurableWeightMetric: 0.00
SuitcaseFragileWeightMetric: 15.00
BagWeightMetric: 17.00

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

سيناريو أكبر وأكثر واقعية: مشكلة التوظيف (staffing)

تهانينا إذا كنت قد وصلت إلى هذا الحد في برنامجنا التعليمي HorusLP! لديك الآن فكرة جيدة عن كيفية استخدام HorusLP.

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

هندسة خوارزمية التحسين مع HorusLP في بایثون| الجزء الثاني

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

فلنبدأ بإعداد المشكلة:

from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup
from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective
from horuslp.core.constants import MINIMIZE

shift_requirements = [1, 4, 3, 5, 2]  # the number of workers we need to staff for each shift
# the availability and pay rates of each of the employees
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
    }
}

# the following people can't work together, sadly.
ban_list = {
    ("Daenerys", "Jaime"),
    ("Daenerys", "Cersei"),
    ("Jon", "Jaime"),
    ("Jon", "Cersei"),
    ("Arya", "Jaime"),
    ("Arya", "Cersei"),
    ("Arya", "Melisandre"),
    ("Jaime", "Cersei")
}

# Dothraki Staffing Corp will provide us with expensive temp workers
DOTHRAKI_MAX = 10
DOTHRAKI_COST = 45

دعنا الآن نحدد المتغيرات والتي ستكون في هذه الحالة متغيرات ثنائية تحدد ما إذا كان يجب على العامل أن يعمل نوبته ومتغيرات الأعداد الصحيحة التي تحدد عدد dothrakis الذي نوظفه لكل نوبة:

class StaffingVariables(VariableManager):
    vars = []

    def __init__(self):
        # like dependent constraints, we can dynamically define variables in the init function
        super(StaffingVariables, self).__init__()
        # regular workers
        varkeys = []
        for employee, availability_info in workers.items():
            for shift in availability_info['availability']:
                varkeys.append((employee, shift))
        self.vars.append(BinaryVariableGroup('employee_shifts', varkeys))
        # dothrakis
        dothraki_keys = [i for i in range(len(shift_requirements))]
        self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

الآن دعونا ننفذ القيد الذي يتطلب منا توفير موظفين كافيين لكل وردية:

class SufficientStaffingConstraint(Constraint):
    # we need to staff people sufficiently
    dependent_constraints = []

    def __init__(self):
        super(SufficientStaffingConstraint, self).__init__()
        for shift_num, shift_req in enumerate(shift_requirements):
            self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req))

    def build_shift_constraint(self, sn, sr):
        class ShiftConstraint(Constraint):
            name = "shift_requirement_%d" % sn

            def define(self, employee_shifts, dothraki_workers):
                variables = [val for key, val in employee_shifts.items() if key[1] == sn]
                variables.append(dothraki_workers[sn])
                return sum(variables) >= sr
        return ShiftConstraint

الآن نحن بحاجة إلى تنفيذ القيود التي تمنع أشخاصًا معينين من العمل مع بعضهم البعض:

class PersonalConflictsConstraint(Constraint):
    # some people can't work together
    dependent_constraints = []

    def __init__(self):
        super(PersonalConflictsConstraint, self).__init__()
        for person_1, person_2 in ban_list:
            for shift in range(len(shift_requirements)):
                self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift))

    def build_conflict_constraint(self, p1, p2, s):
        class ConflictConstraint(Constraint):
            name = "Conflict_%s_%s_%d" % (p1, p2, s)

            def define(self, employee_shifts):
                if (p1, s) in employee_shifts and (p2, s) in employee_shifts:
                    return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1
                return True # returning true will make the constraint do nothing
        return ConflictConstraint

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

class LaborStandardsConstraint(Constraint):
    # we can make someone work more than two shifts a day.
    dependent_constraints = []

    def __init__(self):
        super(LaborStandardsConstraint, self).__init__()
        for worker in workers.keys():
            # we don't need a constraint builder function, but in those circumstances
            # we need to set the needed values as class variables and refer to them
            # via the self keyword due to how python's closure system works
            class LaborConstraint(Constraint):
                # we can't use worker directly!
                wk = worker
                name = "labor_standard_%s" % worker

                def define(self, employee_shifts):
                    # we need to access the worker using self. Change self.wk to worker to see
                    # why we need to do this
                    worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk]
                    return sum(worker_vars) <= 2
            self.dependent_constraints.append(LaborConstraint)

والآن دعونا نحدد الأهداف. يتم حساب تكلفة الدوثراكي وتكاليف الموظفين العادية بشكل مختلف تمامًا لذلك سنضعها في مكونات موضوعية منفصلة:

class CostObjective(ObjectiveComponent):
    # this is the cost function for all the named workers
    def define(self, employee_shifts, dothraki_workers):
        costs = [
            workers[key[0]]['cost'] * var for key, var in employee_shifts.items()
        ]
        return sum(costs)


class DothrakiCostObjective(ObjectiveComponent):
    # don't forget the Dothrakis
    def define(self, dothraki_workers):
        dothraki_costs = [
            dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers
        ]
        return sum(dothraki_costs)


class TotalCostObjective(CombinedObjective):
    objectives = [
        (CostObjective, 1),
        (DothrakiCostObjective, 1)
    ]

والآن يمكننا تحديد المشكلة وتشغيلها:

class StaffingProblem(Problem):
    variables = StaffingVariables
    objective = TotalCostObjective
    constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint]
    sense = MINIMIZE # we're minimizing this time, not maximizing.


if __name__ == '__main__':
    prob = StaffingProblem()
    prob.solve()
    prob.print_results()

قم بتشغيل البرنامج النصي وسترى ما يلي:

StaffingProblem: Optimal
employee_shifts[('Melisandre', 0)] 0.0
employee_shifts[('Melisandre', 1)] 1.0
employee_shifts[('Melisandre', 4)] 1.0
employee_shifts[('Bran', 1)] 0.0
employee_shifts[('Bran', 2)] 1.0
employee_shifts[('Bran', 3)] 1.0
employee_shifts[('Bran', 4)] 0.0
employee_shifts[('Cersei', 2)] 0.0
employee_shifts[('Cersei', 3)] 0.0
employee_shifts[('Daenerys', 3)] 1.0
employee_shifts[('Daenerys', 4)] 0.0
employee_shifts[('Theon', 1)] 1.0
employee_shifts[('Theon', 3)] 1.0
employee_shifts[('Theon', 4)] 0.0
employee_shifts[('Jon', 0)] 0.0
employee_shifts[('Jon', 2)] 1.0
employee_shifts[('Jon', 4)] 0.0
employee_shifts[('Tyrion', 1)] 1.0
employee_shifts[('Tyrion', 3)] 1.0
employee_shifts[('Tyrion', 4)] 0.0
employee_shifts[('Jaime', 1)] 1.0
employee_shifts[('Jaime', 2)] 0.0
employee_shifts[('Jaime', 4)] 1.0
employee_shifts[('Arya', 0)] 1.0
employee_shifts[('Arya', 1)] 0.0
employee_shifts[('Arya', 3)] 1.0
dothraki_workers[0] 0.0
dothraki_workers[1] 0.0
dothraki_workers[2] 1.0
dothraki_workers[3] 0.0
dothraki_workers[4] 0.0
TotalCostObjective: 335.00
CostObjective: 290.00 * 1
DothrakiCostObjective: 45.00 * 1
shift_requirement_0: 1.00
shift_requirement_1: 4.00
shift_requirement_2: 3.00
shift_requirement_3: 5.00
shift_requirement_4: 2.00
Conflict_Jon_Cersei_2: 1.00
Conflict_Jon_Jaime_2: 1.00
Conflict_Jon_Jaime_4: 1.00
Conflict_Daenerys_Cersei_3: 1.00
Conflict_Daenerys_Jaime_4: 1.00
Conflict_Arya_Jaime_1: 1.00
Conflict_Arya_Cersei_3: 1.00
Conflict_Arya_Melisandre_0: 1.00
Conflict_Arya_Melisandre_1: 1.00
Conflict_Jaime_Cersei_2: 0.00
labor_standard_Melisandre: 2.00
labor_standard_Bran: 2.00
labor_standard_Cersei: 0.00
labor_standard_Daenerys: 1.00
labor_standard_Theon: 2.00
labor_standard_Jon: 1.00
labor_standard_Tyrion: 2.00
labor_standard_Jaime: 2.00
labor_standard_Arya: 2.00

إذا قارنت هذا بالمشكلة التي طبقناها في البرنامج التعليمي السابق فسترى أن النتائج متطابقة.

منشور ذات صلة

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

السلة