תחילת העבודה עם OR-כלים עבור Java

הקטעים הבאים יעזרו לך להתחיל בעבודה עם OR-Tools עבור 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.init.OrToolsVersion;
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");
if (solver == null) {
  System.out.println("Could not create solver GLOP");
  return;
}
    MPSolver הוא wrapper לפתרון כל בעיה שקשורה לתכנות לינארי או לתכנות מספרים שלמים מעורבים.
  • יוצרים את המשתנים. 
    // 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: 
    double infinity = Double.POSITIVE_INFINITY;
// Create a linear constraint, x + y <= 2.
MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("Number of constraints = " + solver.numConstraints());
    ה-method 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 זו 'בעיית אופטימיזציה'.
  • מפעילים את הפותר ומציגים את התוצאות. 
    System.out.println("Solving with " + solver.solverVersion());
final MPSolver.ResultStatus resultStatus = solver.solve();
System.out.println("Status: " + resultStatus);
if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("The problem does not have an optimal solution!");
  if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
    System.out.println("A potentially suboptimal solution was found");
  } else {
    System.out.println("The solver could not solve the problem.");
    return;
  }
}

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.init.OrToolsVersion;
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();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

    // 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());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 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();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

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

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

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private BasicExample() {}
}

הפעלת תוכנית Java

אפשר להריץ את התוכנית שלמעלה באופן הבא:

  1. מעתיקים, מדביקים את הקוד שלמעלה בקובץ חדש, ושומרים אותו בתור my_program.java.
  2. פותחים חלון פקודה ברמה העליונה של הספרייה שבה התקנתם את OR-Tools, ומזינים:
    make run SOURCE=relative/path/to/my_program.java
    כאשר relative/path/to/ הוא הנתיב לספרייה שבה שמרתם את התוכנה.

התוכנית מחזירה את הערכים של x ו-y שמגדילים את פונקציית המטרה:

Solution:
x =  1.0
y =  1.0

כדי להדר את התוכנית מבלי להפעיל אותה, מזינים:

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

דוגמאות נוספות ל-Java

לדוגמאות נוספות של Java שממחישות איך לפתור סוגים שונים של בעיות אופטימיזציה, ראו דוגמאות.

זיהוי סוג הבעיה שברצונך לפתור

יש הרבה סוגים שונים של בעיות אופטימיזציה בעולם. לכל סוג של בעיה יש גישות ואלגוריתמים שונים למציאת פתרון אופטימלי.

לפני שתוכלו להתחיל לכתוב תוכנית לפתרון בעיית אופטימיזציה, עליכם לזהות את סוג הבעיה שבה אתם מתמודדים ולבחור פותר מתאים – אלגוריתם למציאת פתרון אופטימלי.

בהמשך מופיעה סקירה קצרה של סוגי הבעיות שנפתרות באמצעות OR-Tools, וקישורים לקטעים במדריך זה שמסבירים איך לפתור כל סוג של בעיה.

אופטימיזציה לינארית

כפי שלמדתם בקטע הקודם, בעיית אופטימיזציה לינארית היא בעיה שבה פונקציית המטרה והאילוצים הם ביטויים לינאריים במשתנים.

הפותר הראשי בכלי OR-כלים לפתרון בעיות כאלה הוא פותר האופטימיזציה הלינארית, שהוא למעשה wrapper של כמה ספריות שונות, לאופטימיזציה לינארית ולאופטימיזציה של מספרים שלמים מעורבים, כולל ספריות של צד שלישי.

מידע נוסף על אופטימיזציה לינארית

אופטימיזציה של מספרים מעורבים שלמים

בעיה באופטימיזציה של מספרים שלמים מעורבים היא בעיה שבה חלק מהמשתנים או כולם חייבים להיות מספרים שלמים. בעיה בהקצאה, למשל, היא שצריך להקצות קבוצת עובדים לקבוצת משימות. לכל עובד ומשימה, עליכם להגדיר משתנה שהערך שלו הוא 1 אם העובד הנתון מוקצה למשימה הנתונה, אחרת הערך הוא 0. במקרה הזה, המשתנים יכולים לקבל רק את הערכים 0 או 1.

מידע נוסף על אופטימיזציה של מספרים מעורבים

אופטימיזציה של מגבלות

אופטימיזציה אילוצים, או תכנות אילוצים (CP), מזהה פתרונות אפשריים מתוך קבוצה גדולה מאוד של מועמדים, שבהם ניתן ליצור מודל לבעיה באמצעות אילוצים שרירותיים. הבדיקה מבוססת על היתכנות (מציאת פתרון בר-ביצוע) ולא על אופטימיזציה (מציאת פתרון אופטימלי) ומתמקדת באילוצים ובמשתנים ולא בפונקציה למטרה. אבל אפשר להשתמש ב-CP כדי לפתור בעיות אופטימיזציה פשוט על ידי השוואת הערכים של פונקציית המטרה לכל הפתרונות האפשריים.

מידע נוסף על אופטימיזציה של אילוצים

מטלה

בעיות בהקצאה כוללות הקצאה של קבוצת סוכנים (למשל, עובדים או מכונות) לקבוצת משימות, שבה יש עלות קבועה להקצאה של כל סוכן למשימה ספציפית. הבעיה היא למצוא את המטלה עם העלות הכוללת הנמוכה ביותר. בעיות בהקצאה הן למעשה מקרה מיוחד של בעיות בזרימת הרשת.

למידע נוסף על הקצאה

אריזה

אריזת פחים היא הבעיה באריזת קבוצת אובייקטים בגדלים שונים במיכלים עם קיבולת שונה. המטרה היא לארוז כמה שיותר אובייקטים, בכפוף לקיבולת של הקונטיינרים. מקרה מיוחד לכך הוא בעיית Knapsack, שבה יש רק קונטיינר אחד.

מידע נוסף על אריזה בסל

תזמון

בעיות תזמון כוללות הקצאת משאבים לביצוע סדרת משימות בזמנים ספציפיים. דוגמה חשובה היא בעיה של חנות עבודות, שבה מספר משימות מעובדות במספר מכונות. כל משימה מורכבת מרצף של משימות, שצריכות להתבצע בסדר נתון ושצריך לעבד כל משימה במכונה ספציפית. הבעיה היא להקצות לוח זמנים כדי שכל המשימות יושלמו בפרק זמן קצר ככל האפשר.

מידע נוסף על תזמון

יצירת מסלול מתבצעת

בעיות שקשורות למסלולים כוללות מציאת המסלולים האופטימליים בשביל צי כלי רכב שחוצים רשת, לפי גרף מכוון. הבעיה של הקצאת חבילות למשאיות משלוחים, המתוארת בקטע מהי בעיית אופטימיזציה?, היא אחת הדוגמאות לבעיית מסלול. בעיה אחרת היא הבעיה של אנשי המכירות בנסיעה.

מידע נוסף על מסלולים

זרימות רשת

אפשר לייצג בעיות אופטימיזציה רבות על ידי גרף מכוון שמכיל צמתים וקשתות מכוונות ביניהם. לדוגמה, אפשר לייצג בעיות תחבורה, שבהן סחורות נשלחות ברשת מסילות, בתרשים שבו הקשתות הן קווי רכבת והצמתים הם מרכזי הפצה.

במקרה של בעיית הזרימה המקסימלית, לכל קשת יש קיבולת מקסימלית שאפשר להעביר אליה. הבעיה היא להקצות את כמות הסחורות שצריך לשלוח בכל קשת, כדי שהכמות הכוללת תהיה גדולה ככל האפשר.

מידע נוסף על תהליכי עבודה ברשת