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

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

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

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

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

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

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

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

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

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

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

حل مسئله بهینه سازی در Net

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

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

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

3x + y با توجه به قیود زیر به حداکثر برسانید:

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

تابع هدف در این مثال 3x + y است. هم تابع هدف و هم قیود با عبارات خطی داده می شوند که این مسئله را به صورت خطی تبدیل می کند.

مراحل اصلی در حل مشکل

برای هر زبان، مراحل اولیه برای تنظیم و حل یک مشکل یکسان است:

  1. وارد کردن کتابخانه های مورد نیاز،
  2. حل کننده را اعلام کنید،
  3. ایجاد متغیرها،
  4. محدودیت ها را تعریف کنید،
  5. تابع هدف را تعریف کنید،
  6. حل کننده را فراخوانی و
  7. نمایش نتایج.

برنامه .Net

این بخش از طریق یک برنامه دات نت می گذرد که مشکل را راه اندازی و حل می کند.

در اینجا مراحل انجام می شود:

  • کتابخانه های مورد نیاز را وارد کنید. 
    using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;
  • حل کننده را اعلام کنید.
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    Console.WriteLine("Could not create solver GLOP");
    return;
}
     MPSolver پوششی برای حل هرگونه برنامه ریزی خطی یا برنامه نویسی عدد صحیح مختلط است.
  • متغیرها را ایجاد کنید. 
    // Create the variables x and y.
Variable x = solver.MakeNumVar(0.0, 1.0, "x");
Variable y = solver.MakeNumVar(0.0, 2.0, "y");

Console.WriteLine("Number of variables = " + solver.NumVariables());
  • محدودیت ها را تعریف کنید. دو قید اول، 0 ≤ x ≤ 1 و 0 ≤ y ≤ 2 ، قبلاً با تعاریف متغیرها تنظیم شده اند. کد زیر محدودیت x + y ≤ 2 را تعریف می کند:
    // Create a linear constraint, x + y <= 2.
Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
constraint.SetCoefficient(x, 1);
constraint.SetCoefficient(y, 1);

Console.WriteLine("Number of constraints = " + solver.NumConstraints());
     روش SetCoefficient ضرایب x و y را در عبارت محدودیت تنظیم می کند.
  • تابع هدف را تعریف کنید.
    // Create the objective function, 3 * x + y.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 1);
objective.SetMaximization();
     متد setMaximization این را به عنوان یک مشکل بیشینه سازی اعلام می کند. (روش زیربنایی C++ SetMaximization است.
  • حل کننده را فراخوانی کنید و نتایج را نمایش دهید. 
    Console.WriteLine("Solving with " + solver.SolverVersion());
Solver.ResultStatus resultStatus = solver.Solve();
Console.WriteLine("Status: " + resultStatus);
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    if (resultStatus == Solver.ResultStatus.FEASIBLE)
    {
        Console.WriteLine("A potentially suboptimal solution was found");
    }
    else
    {
        Console.WriteLine("The solver could not solve the problem.");
        return;
    }
}

Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

برنامه کامل

برنامه کامل در زیر نشان داده شده است.

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            Console.WriteLine("Could not create solver GLOP");
            return;
        }

        // Create the variables x and y.
        Variable x = solver.MakeNumVar(0.0, 1.0, "x");
        Variable y = solver.MakeNumVar(0.0, 2.0, "y");

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

        Console.WriteLine("Status: " + resultStatus);
        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("The problem does not have an optimal solution!");
            if (resultStatus == Solver.ResultStatus.FEASIBLE)
            {
                Console.WriteLine("A potentially suboptimal solution was found");
            }
            else
            {
                Console.WriteLine("The solver could not solve the problem.");
                return;
            }
        }

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

اجرای برنامه دات نت

می توانید برنامه بالا را به صورت زیر اجرا کنید:

  1. کد بالا را کپی کرده و در فایل جدید قرار دهید و آن را به عنوان BasicExample.cs ذخیره کنید. در زیر شاخه examples/dotnet دایرکتوری که OR-Tools را در آن نصب کرده اید.
  2. در همان فهرست، یک فایل جدید به نام BasicExample.csproj ایجاد کنید و کد زیر را اضافه کنید: 
    <Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <LangVersion>7.3</LangVersion>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <EnableDefaultItems>false</EnableDefaultItems>
    <!-- see https://github.com/dotnet/docs/issues/12237 -->
    <RollForward>LatestMajor</RollForward>
    <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
    <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
    <IsPackable>true</IsPackable>
  </PropertyGroup>

  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugType>full</DebugType>
    <Optimize>true</Optimize>
    <GenerateTailCalls>true</GenerateTailCalls>
  </PropertyGroup>

  <ItemGroup>
    <Compile Include="BasicExample.cs" />
    <PackageReference Include="Google.OrTools" Version="9.1.*" />
  </ItemGroup>
</Project>
  3. در سطح بالای دایرکتوری که OR-Tools را نصب کرده اید، یک پنجره فرمان باز کنید و وارد کنید: 
    make run SOURCE=examples/dotnet/BasicExample.cs

امکان ذخیره و اجرای برنامه های .Net در دایرکتوری متفاوتی غیر از examples/dotnet/ وجود دارد، اما این کمی پیچیده تر است: شما باید خط زیر فایل csproj را که در بالا نشان داده شده است تغییر دهید:

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json
 برای داشتن مسیر صحیح به دایرکتوری packages .

ساده ترین راه حل این است که برنامه های .Net خود را در پوشه examples/dotnet/ قرار دهید.

برنامه مقادیر x و y را برمی گرداند که تابع هدف را به حداکثر می رساند: 

Solution:
x =  1.0
y =  1.0

برای کامپایل کردن برنامه بدون اجرای آن، وارد کنید: 

make build SOURCE=relative/path/to/SimpleProgram.cs

اگر تغییراتی در برنامه ایجاد کردید، باید آن را مانند تصویر بالا دوباره کامپایل کنید.

نمونه های بیشتر .Net

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

شناسایی نوع مشکلی که می خواهید حل کنید

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

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

در زیر مروری مختصر از انواع مشکلاتی که OR-Tools حل می‌کند، و پیوندهایی به بخش‌های این راهنما که نحوه حل هر نوع مشکل را توضیح می‌دهد، خواهید دید.

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

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

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

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

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

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

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

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

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

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

تکلیف

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

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

بسته بندی

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

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

برنامه ریزی

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

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

مسیریابی

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

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

جریان شبکه

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

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

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