بدء استخدام OR-أدوات لـ Python

ستساعدك الأقسام التالية في بدء استخدام OR-أدوات في بايثون:

ما المقصود بمشكلة التحسين؟

الهدف من التحسين هو العثور على أفضل حلّ لمشكلة من ضمن مجموعة كبيرة من الحلول الممكنة. (أحيانًا تكون راضيًا عن إيجاد أي حل ممكن، أو يمكن لـ OR-الأدوات القيام بذلك أيضًا.)

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

وكما هو الحال في جميع مشكلات التحسين، تحتوي هذه المشكلة على العناصر التالية:

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

    الحل الأمثل هو الذي تكون فيه قيمة الدالة الموضوعية هي الأفضل. (يمكن أن يكون "الأفضل" الحد الأقصى أو الأدنى.)

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

    الحل الممكن هو الذي يفي بجميع القيود المحددة للمشكلة، دون أن يكون بالضرورة هو الأمثل.

تتمثل الخطوة الأولى في حل مشكلة التحسين في تحديد الهدف والقيود.

حل مشكلة تحسين في بايثون

بعد ذلك، سنقدم مثالاً لمشكلة تحسين، ونعرض كيفية إعدادها وحلها في بايثون.

مثال على التحسين الخطي

تُعدّ التحسين الخطي (أو البرمجة الخطية) أحد أقدمها وأكثرها استخدامًا على نطاق واسع، حيث يمكن كتابة الدالة الموضوعية والقيود كتعبيرات خطية. إليك مثالاً بسيطًا على هذا النوع من المشكلات.

يمكنك زيادة 3x + y إلى أقصى حد وفقًا للقيود التالية:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

دالة الهدف في هذا المثال هي 3x + y. يتم تحديد كل من الدالة الموضوعية والقيود بواسطة التعبيرات الخطية، مما يجعل هذه مشكلة خطية.

الخطوات الأساسية لحل المشكلة

بالنسبة إلى كل لغة، فإن الخطوات الأساسية لإعداد المشكلات وحلها هي نفسها:

  1. قم باستيراد المكتبات المطلوبة،
  2. عرِّف أداة الحلّ:
  3. أنشئ المتغيرات،
  4. حدد القيود
  5. تعريف الدالة الموضوعية،
  6. عليك استدعاء أداة الحلّ.
  7. عرض النتائج.

برنامج بايثون

يتناول هذا القسم برنامج بايثون الذي يُعِد المسألة ويحلها.

إليك الخطوات التي يمكنك اتّباعها:

  • استورِد المكتبات المطلوبة. 
    from ortools.init.python import init
from ortools.linear_solver import pywraplp
  • يُرجى تعريف أداة الحلّ. 
    # Create the linear solver with the GLOP backend.
solver = pywraplp.Solver.CreateSolver("GLOP")
if not solver:
    print("Could not create solver GLOP")
    return
    pywraplp هو برنامج تضمين في لغة Python لأداة حلّ C++ الأساسية. تحدّد الوسيطة "GLOP" GLOP، أداة الحلّ الخطية في OR-Tools.
  • أنشِئ المتغيّرات. 
    # Create the variables x and y.
x_var = solver.NumVar(0, 1, "x")
y_var = solver.NumVar(0, 2, "y")

print("Number of variables =", solver.NumVariables())
  • حدد القيود. تم ضبط أول قيدين، وهما 0 &leq؛ x ≤ 1 و0 &leq؛ y ≤ 2، من خلال تعريفات المتغيّرات. يحدّد الرمز البرمجي التالي القيد x + y ≤ 2: 
    infinity = solver.infinity()
# Create a linear constraint, x + y <= 2.
constraint = solver.Constraint(-infinity, 2, "ct")
constraint.SetCoefficient(x_var, 1)
constraint.SetCoefficient(y_var, 1)

print("Number of constraints =", solver.NumConstraints())
    تضبط الطريقة SetCoefficient معاملَي x وy في تعبير القيد.
  • تعريف الدالة الموضوعية. 
    # Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x_var, 3)
objective.SetCoefficient(y_var, 1)
objective.SetMaximization()
    تصنّف الطريقة SetMaximization على أنّها مشكلة تكبير.
  • استدعِ أداة الحلّ واعرض النتائج. 
    print(f"Solving with {solver.SolverVersion()}")
result_status = solver.Solve()
print(f"Status: {result_status}")
if result_status != pywraplp.Solver.OPTIMAL:
    print("The problem does not have an optimal solution!")
    if result_status == pywraplp.Solver.FEASIBLE:
        print("A potentially suboptimal solution was found")
    else:
        print("The solver could not solve the problem.")
        return

print("Solution:")
print("Objective value =", objective.Value())
print("x =", x_var.solution_value())
print("y =", y_var.solution_value())

إكمال البرنامج

في ما يلي البرنامج الكامل.

from ortools.init.python import init
from ortools.linear_solver import pywraplp


def main():
    print("Google OR-Tools version:", init.OrToolsVersion.version_string())

    # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if not solver:
        print("Could not create solver GLOP")
        return

    # Create the variables x and y.
    x_var = solver.NumVar(0, 1, "x")
    y_var = solver.NumVar(0, 2, "y")

    print("Number of variables =", solver.NumVariables())

    infinity = solver.infinity()
    # Create a linear constraint, x + y <= 2.
    constraint = solver.Constraint(-infinity, 2, "ct")
    constraint.SetCoefficient(x_var, 1)
    constraint.SetCoefficient(y_var, 1)

    print("Number of constraints =", solver.NumConstraints())

    # Create the objective function, 3 * x + y.
    objective = solver.Objective()
    objective.SetCoefficient(x_var, 3)
    objective.SetCoefficient(y_var, 1)
    objective.SetMaximization()

    print(f"Solving with {solver.SolverVersion()}")
    result_status = solver.Solve()

    print(f"Status: {result_status}")
    if result_status != pywraplp.Solver.OPTIMAL:
        print("The problem does not have an optimal solution!")
        if result_status == pywraplp.Solver.FEASIBLE:
            print("A potentially suboptimal solution was found")
        else:
            print("The solver could not solve the problem.")
            return

    print("Solution:")
    print("Objective value =", objective.Value())
    print("x =", x_var.solution_value())
    print("y =", y_var.solution_value())

    print("Advanced usage:")
    print(f"Problem solved in {solver.wall_time():d} milliseconds")
    print(f"Problem solved in {solver.iterations():d} iterations")


if __name__ == "__main__":
    init.CppBridge.init_logging("basic_example.py")
    cpp_flags = init.CppFlags()
    cpp_flags.stderrthreshold = True
    cpp_flags.log_prefix = False
    init.CppBridge.set_flags(cpp_flags)
    main()

تشغيل البرنامج

يمكنك تشغيل البرنامج أعلاه كما يلي:

  1. انسخ الرمز أعلاه والصقه في ملف جديد واحفظه باسم program.py.
  2. افتح نافذة أوامر وبدِّل إلى الدليل الذي حفظت فيه program.py. في موجّه الأوامر، أدخِل:
    python relative/path/to/program.py
    حيث يكون relative/path/to/ هو مسار الدليل الذي حفظت فيه البرنامج.

يعرض البرنامج قيمتَي x وy اللتين تحققان أقصى قيمة لدالة الهدف:

Solution:
x =  1.0
y =  1.0

المزيد من الأمثلة في لغة بايثون

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

تحديد نوع المشكلة التي ترغب في حلها

هناك أنواع مختلفة من مشكلات التحسين في العالم. لكل نوع من المشكلات، هناك مناهج وخوارزميات مختلفة لإيجاد الحل الأمثل.

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

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

التحسين الخطي

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

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

مزيد من المعلومات حول التحسين المجدوَل

تحسين الأعداد الصحيحة المختلطة

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

مزيد من المعلومات عن تحسين الأعداد الصحيحة المختلطة

تحسين القيود

يحدد تحسين القيد أو برمجة القيد (CP)، الحلول الممكنة من مجموعة كبيرة جدًا من المرشحين، حيث يمكن نمذجة المشكلة من حيث القيود العشوائية. يعتمد CP على الإمكانية (إيجاد حل ممكن) بدلاً من التحسين (إيجاد حل مثالي) ويركز على القيود والمتغيرات بدلاً من الدالة الموضوعية. ومع ذلك، يمكن استخدام CP لحل مشاكل التحسين ببساطة من خلال مقارنة قيم الدالة الموضوعية لجميع الحلول الممكنة.

مزيد من المعلومات عن تحسين القيود

Assignment

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

مزيد من المعلومات عن المهمة

تعبئة

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

مزيد من المعلومات حول تغليف السلال

الجدولة

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

مزيد من المعلومات حول جدولة المواعيد

يتم الآن تخطيط المسار

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

مزيد من المعلومات عن التوجيه

تدفقات الشبكة

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

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

مزيد من المعلومات عن تدفقات الشبكة