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

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

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

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

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

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

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

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

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

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

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

حل مشكلة تحسين في .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

يتناول هذا القسم برنامج .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 &leq؛ x ≤ 1 و0 &leq؛ 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");
    }
}

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

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

  1. انسخ الرمز أعلاه والصقه في ملف جديد واحفظه باسم BasicExample.cs. في الدليل الفرعي examples/dotnet من الدليل حيث قمت بتثبيت OR-الأدوات.
  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، وروابط إلى الأقسام في هذا الدليل التي توضح كيفية حل كل نوع من أنواع المشكلات.

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

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

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

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

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

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

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

تحسين القيود

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

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

Assignment

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

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

تعبئة

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

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

الجدولة

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

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

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

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

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

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

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

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

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