با OR-Tools برای پایتون شروع کنید

بخش های زیر شما را با OR-Tools برای پایتون شروع می کند:

مشکل بهینه سازی چیست؟

هدف بهینه سازی یافتن بهترین راه حل برای یک مسئله از میان مجموعه بزرگی از راه حل های ممکن است. (گاهی اوقات شما با یافتن هر راه حل عملی راضی خواهید بود؛ OR-Tools نیز می تواند این کار را انجام دهد.)

در اینجا یک مشکل بهینه سازی معمولی وجود دارد. فرض کنید که یک شرکت حمل و نقل با استفاده از ناوگان کامیون بسته ها را به مشتریان خود تحویل می دهد. شرکت باید هر روز بسته هایی را به کامیون ها اختصاص دهد و سپس مسیری را برای هر کامیون برای تحویل بسته های خود انتخاب کند. هر تخصیص احتمالی بسته ها و مسیرها هزینه ای دارد که بر اساس کل مسافت طی شده برای کامیون ها و احتمالاً عوامل دیگر است. مشکل انتخاب تکالیف بسته ها و مسیرهایی است که کمترین هزینه را داشته باشد.

مانند تمام مسائل بهینه سازی، این مشکل دارای عناصر زیر است:

  • هدف : مقداری که می خواهید بهینه کنید. در مثال بالا، هدف به حداقل رساندن هزینه است. برای تنظیم یک مسئله بهینه سازی، باید تابعی را تعریف کنید که مقدار هدف را برای هر راه حل ممکن محاسبه کند. به این تابع هدف می گویند. در مثال قبل، تابع هدف هزینه کل هر تخصیص بسته ها و مسیرها را محاسبه می کند.

    راه حل بهینه راه حلی است که مقدار تابع هدف برای آن بهترین باشد. ("بهترین" می تواند حداکثر یا حداقل باشد.)

  • محدودیت ها - محدودیت ها در مجموعه راه حل های ممکن، بر اساس الزامات خاص مشکل. برای مثال، اگر شرکت حمل‌ونقل نتواند بسته‌های بالاتر از وزن معین را به کامیون‌ها اختصاص دهد، این امر محدودیت‌هایی را بر راه‌حل‌ها تحمیل می‌کند.

    یک راه حل عملی راه حلی است که تمام محدودیت های داده شده برای مسئله را برآورده کند، بدون اینکه لزوماً بهینه باشد.

اولین گام در حل مسئله بهینه سازی، شناسایی هدف و محدودیت ها است.

حل مسئله بهینه سازی در پایتون

در مرحله بعد، مثالی از یک مسئله بهینه‌سازی ارائه می‌دهیم و نحوه راه‌اندازی و حل آن را در پایتون نشان می‌دهیم.

یک مثال بهینه سازی خطی

یکی از قدیمی‌ترین و پرکاربردترین حوزه‌های بهینه‌سازی، بهینه‌سازی خطی (یا برنامه‌ریزی خطی ) است که در آن تابع هدف و محدودیت‌ها را می‌توان به صورت عبارات خطی نوشت. در اینجا یک مثال ساده از این نوع مشکلات آورده شده است.

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 یک پوشش پایتون برای حل کننده زیرین 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 ≤ x ≤ 1 و 0 ≤ 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-Tools حل می‌کند، و پیوندهایی به بخش‌های این راهنما که نحوه حل هر نوع مشکل را توضیح می‌دهد، خواهید دید.

بهینه سازی خطی

همانطور که در بخش قبل آموختید، یک مسئله بهینه سازی خطی مسئله ای است که در آن تابع هدف و محدودیت ها عبارت های خطی در متغیرها هستند.

حل‌کننده اولیه در OR-Tools برای این نوع مسائل، حل‌کننده بهینه‌سازی خطی است که در واقع یک پوشش برای چندین کتابخانه مختلف برای بهینه‌سازی اعداد صحیح خطی و مختلط ، از جمله کتابخانه‌های شخص ثالث است.

درباره بهینه سازی خطی بیشتر بدانید

بهینه سازی اعداد صحیح مختلط

یک مسئله بهینه سازی عدد صحیح مختلط مسئله ای است که در آن برخی یا همه متغیرها باید اعداد صحیح باشند. یک مثال مشکل انتساب است که در آن گروهی از کارگران باید به مجموعه ای از وظایف اختصاص داده شوند. برای هر کارگر و وظیفه، متغیری را تعریف می‌کنید که اگر کارگر معین به وظیفه داده شده اختصاص داده شود، مقدار آن 1 و در غیر این صورت 0 است. در این حالت، متغیرها فقط می توانند مقادیر 0 یا 1 را بگیرند.

درباره بهینه سازی اعداد صحیح مختلط بیشتر بدانید

بهینه سازی محدودیت

بهینه‌سازی محدودیت یا برنامه‌نویسی محدودیت (CP)، راه‌حل‌های امکان‌پذیر را از میان مجموعه‌ای بسیار بزرگ از نامزدها شناسایی می‌کند، جایی که مسئله می‌تواند بر اساس محدودیت‌های دلخواه مدل‌سازی شود. CP به جای بهینه‌سازی (یافتن راه‌حل بهینه) مبتنی بر امکان‌سنجی (پیدا کردن یک راه‌حل امکان‌پذیر) است و به جای تابع هدف، بر روی محدودیت‌ها و متغیرها تمرکز می‌کند. با این حال، CP را می توان برای حل مسائل بهینه سازی، به سادگی با مقایسه مقادیر تابع هدف برای همه راه حل های امکان پذیر، استفاده کرد.

درباره بهینه سازی محدودیت ها بیشتر بدانید

تکلیف

مشکلات انتساب شامل تخصیص گروهی از عوامل (مثلاً کارگران یا ماشین‌ها) به مجموعه‌ای از وظایف است که در آن هزینه ثابتی برای تخصیص هر عامل به یک کار خاص وجود دارد. مشکل این است که تکلیف را با کمترین هزینه کل پیدا کنید. مشکلات تخصیص در واقع یک مورد خاص از مشکلات جریان شبکه است.

درباره تکلیف بیشتر بدانید

بسته بندی

سطل بسته بندی مشکل بسته بندی مجموعه ای از اشیاء با اندازه های مختلف در ظروف با ظرفیت های مختلف است. هدف بسته بندی هرچه بیشتر اشیا با توجه به ظرفیت ظروف است. یک مورد خاص از این مشکل کوله پشتی است که در آن فقط یک ظرف وجود دارد.

درباره بسته بندی سطل زباله بیشتر بدانید

برنامه ریزی

مشکلات زمان‌بندی شامل تخصیص منابع برای انجام مجموعه‌ای از وظایف در زمان‌های خاص است. یک مثال مهم مشکل کارگاه است که در آن چندین کار بر روی چندین ماشین پردازش می شود. هر کار متشکل از دنباله ای از وظایف است که باید به ترتیب معین انجام شود و هر کار باید بر روی یک ماشین خاص پردازش شود. مشکل این است که یک برنامه زمان بندی تعیین کنید تا همه کارها در کوتاه ترین فاصله زمانی ممکن تکمیل شوند.

درباره زمان بندی بیشتر بدانید

مسیریابی

مشکلات مسیریابی شامل یافتن مسیرهای بهینه برای یک ناوگان وسایل نقلیه برای عبور از یک شبکه است که توسط یک نمودار هدایت شده تعریف شده است. مشکل تخصیص بسته‌ها به کامیون‌های تحویل، در مقاله بهینه‌سازی چیست؟ ، یکی از نمونه های مشکل مسیریابی است. مشکل دیگر فروشنده دوره گرد است.

درباره مسیریابی بیشتر بدانید

جریان شبکه

بسیاری از مسائل بهینه سازی را می توان با یک گراف جهت دار متشکل از گره ها و کمان های جهت دار بین آنها نشان داد. به عنوان مثال، مشکلات حمل و نقل، که در آن کالاها از طریق شبکه راه آهن حمل می شوند، می توانند با نموداری نمایش داده شوند که در آن قوس ها خطوط ریلی و گره ها مراکز توزیع هستند.

در مسئله ماکزیمم جریان ، هر قوس دارای حداکثر ظرفیتی است که می تواند در آن جابجا شود. مشکل این است که مقدار کالایی که باید در هر قوس حمل شود تعیین می شود تا کل مقدار حمل شده تا حد امکان زیاد باشد.

درباره جریان های شبکه بیشتر بیاموزید