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

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

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

الهدف من عملية التحسين هو العثور على أفضل حلّ لمشكلة من بين مجموعة كبيرة من الحلول الممكنة. (في بعض الأحيان تكون راضيًا عن إيجاد أي حل ممكن؛ يمكن لـ 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

يتناول هذا القسم برنامج Net .الذي يُعِدّ المشكلة ويحلها.

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

  • استورِد المكتبات المطلوبة. 
    using System;
using Google.OrTools.LinearSolver;
  • يُرجى تعريف أداة الحلّ. 
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    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, 0 <= x + y <= 2.
Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
ct.SetCoefficient(x, 1);
ct.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.
  • استدعِ أداة الحلّ واعرض النتائج. 
    solver.Solve();
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.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            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, 0 <= x + y <= 2.
        Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
        ct.SetCoefficient(x, 1);
        ct.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();

        solver.Solve();

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

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

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

  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" لهذا النوع من المشاكل هي أداة حلّ التحسين الخطي، وهي في الواقع برنامج تضمين للعديد من المكتبات المختلفة لتحسين الأعداد الخطية وأعداد الأعداد الصحيحة المختلطة، بما في ذلك المكتبات التابعة لجهات خارجية.

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

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

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

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

تحسين القيد

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

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

Assignment

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

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

تعبئة

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

مزيد من المعلومات عن تعبئة السلال

الجدولة

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

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

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

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

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

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

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

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

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