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

ستبدأ الأقسام التالية في بدء استخدام أدوات OR لـ Java:

• ما المقصود بمشكلة التحسين؟
• حل مشكلة تحسين في Java
• المزيد من أمثلة Java
• تحديد نوع المشكلة التي تريد حلّها

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

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

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

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

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

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

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

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

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

حل مشكلة متعلقة بالتحسين في Java

فيما يلي مثال على مشكلة من مشكلات التحسين، ونوضح كيفية إعدادها وحلها في Java.

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

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

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

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

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

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

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

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

برنامج Java<

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

ملاحظة: يظهر برنامج Java الكامل وخطوات تشغيله في نهاية القسم.

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

• استورِد المكتبات المطلوبة.

  import com.google.ortools.Loader;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• يُرجى تعريف أداة الحلّ.

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");

  MPSolver هو برنامج تضمين لحلّ أي مسائل متعلقة بالبرمجة الخطية أو برمجة الأعداد الصحيحة المختلطة.
• أنشِئ المتغيّرات.

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• حدد القيود. تم ضبط أول قيدَين، وهما 0 &leq؛ x ≤ 1 و0 &leq؛ y ≤ 2، من خلال تعريفات المتغيّرات. تُحدِّد التعليمة البرمجية التالية القيد x + y &leq; 2:

  // Create a linear constraint, 0 <= x + y <= 2.
  MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  تضبط الطريقة setCoefficient معاملي x وy في تعبير القيد.
• تعريف الدالة الموضوعية.

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  تصف الطريقة setMaximization أنها مشكلة تكبير.
• استدعِ أداة الحلّ واعرض النتائج.

  solver.solve();
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

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

يظهر البرنامج الكامل أدناه.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

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

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

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

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

1. انسخ الرمز أعلاه والصقه في ملف جديد، واحفظه باسم my_program.java.
2. افتح نافذة أوامر في المستوى الأعلى من الدليل الذي تم فيه تثبيت OR-Tools، وأدخِل عبارة:

   make run SOURCE=relative/path/to/my_program.java

   حيث يكون relative/path/to/ هو المسار إلى الدليل الذي حفظت فيه البرنامج.

ملاحظة: عليك تشغيل الأمر أعلاه من المستوى الأعلى من الدليل الذي ثبّت فيه OR-Tools (حيث يتوفّر Makefile).

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

Solution:
x =  1.0
y =  1.0

لتجميع البرنامج فقط بدون تشغيله، أدخِل:

make build SOURCE=relative/path/to/my_program.java

المزيد من أمثلة Java

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

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

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

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

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

• التحسين الخطي
• تحسين القيود
• تحسين الأعداد الصحيحة المختلطة
• نقل الحقوق
• الجدولة
• التعبئة
• التوجيه
• تدفقات الشبكة

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

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

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

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

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

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

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

تحسين القيد

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

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

Assignment

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

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

تعبئة

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

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

الجدولة

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

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

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

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

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

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

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

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

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