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

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

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

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

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

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

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

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

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

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

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

حل مشكلة تحسين في C++

بعد ذلك، سنقدم مثالاً لمشكلة تحسين، ونوضح كيفية إعدادها وحلها في C++.

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

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

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

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

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

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

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

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

برنامج C++

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

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

  • استورِد المكتبات المطلوبة. 
    #include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"
  • يُرجى تعريف أداة الحلّ. 
    // Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
  LOG(WARNING) << "Could not create solver GLOP";
  return;
}
    تشكّل السمة MPSolver برنامج تضمين لحلّ أي مسائل البرمجة الخطية أو برمجة الأعداد الصحيحة المختلطة.
  • أنشِئ المتغيّرات. 
    // Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();
  • حدد القيود. تم ضبط أول قيدين، وهما 0 &leq؛ x ≤ 1 و0 &leq؛ y ≤ 2، من خلال تعريفات المتغيّرات. يحدّد الرمز البرمجي التالي القيد x + y &leq; 2: 
    // Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
    تضبط الطريقة SetCoefficient معاملَي x وy في تعبير القيد.
  • تعريف الدالة الموضوعية. 
    // Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
    تصنّف الطريقة SetMaximization على أنّها مشكلة تكبير.
  • استدعِ أداة الحلّ واعرض النتائج. 
    LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
  LOG(INFO) << "The problem does not have an optimal solution!";
  if (result_status == MPSolver::FEASIBLE) {
    LOG(INFO) << "A potentially suboptimal solution was found";
  } else {
    LOG(WARNING) << "The solver could not solve the problem.";
    return;
  }
}

LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

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

في ما يلي البرنامج الكامل.

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

تشغيل برنامج C++

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

  1. انسخ الرمز أعلاه والصقه في ملف جديد، واحفظه باسم program.cc.
  2. افتح نافذة أوامر في المستوى الأعلى من الدليل حيث تم تثبيت OR-Tools، وأدخِل ما يلي: 
    make run SOURCE=relative/path/to/program.cc
    حيث يكون relative/path/to/ هو مسار الدليل الذي حفظت فيه البرنامج.

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/program.cc

التجميع في وضع التفعيل

للتجميع في وضع O3:

make DEBUG='-O3' all

تشغيل ملف C++ القابل للتنفيذ

عند تجميع برنامج OR-أدوات C++ باستخدام make، يتم إنشاء الملف التنفيذي في دليل bin. يمكنك تشغيل الملف التنفيذي لمثال البرنامج على النحو التالي:

cd bin && ./program

إذا أجريت تغييرات على البرنامج، فستحتاج إلى إعادة تجميعه كما هو موضح أعلاه.

المزيد من أمثلة C++

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

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

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

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

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

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

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

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

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

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

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

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

تحسين القيود

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

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

Assignment

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

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

تعبئة

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

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

الجدولة

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

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

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

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

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

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

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

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

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