เริ่มต้นใช้งาน OR-Tools สำหรับ Java

ส่วนต่อไปนี้จะช่วยคุณในการเริ่มต้นใช้งาน OR-Tools สำหรับ Java:

• ปัญหาในการเพิ่มประสิทธิภาพคืออะไร
• การแก้ปัญหาการเพิ่มประสิทธิภาพใน Java
• ตัวอย่าง Java เพิ่มเติม
• การระบุประเภทปัญหาที่คุณต้องการแก้ไข

ปัญหาในการเพิ่มประสิทธิภาพคืออะไร

เป้าหมายของการเพิ่มประสิทธิภาพคือการค้นหาวิธีแก้ปัญหาที่ดีที่สุดจากชุดวิธีแก้ปัญหาขนาดใหญ่ที่เป็นไปได้ (บางครั้งคุณพึงพอใจกับการหาวิธีแก้ปัญหาที่ทำได้ หรือเครื่องมือก็สามารถทำได้เช่นกัน)

ต่อไปนี้คือปัญหาการเพิ่มประสิทธิภาพโดยทั่วไป สมมติว่าบริษัทจัดส่งแห่งหนึ่งส่งพัสดุภัณฑ์ให้กับลูกค้าโดยใช้รถบรรทุกคัน ในทุกๆ วัน บริษัทต้องกำหนดพัสดุให้กับรถบรรทุก แล้วเลือกเส้นทางที่ให้รถบรรทุกแต่ละคันเพื่อนำส่งพัสดุ การมอบหมายพัสดุและเส้นทางแต่ละเส้นจะมีค่าใช้จ่ายตามระยะทางในการเดินทางรวมของรถบรรทุกและอาจมีปัจจัยอื่นๆ ด้วย ปัญหาคือการเลือกการกำหนดแพ็กเกจและเส้นทางที่มีค่าใช้จ่ายน้อยที่สุด

เช่นเดียวกับปัญหาการเพิ่มประสิทธิภาพทั้งหมด ปัญหานี้มีองค์ประกอบต่อไปนี้:

• วัตถุประสงค์ ซึ่งก็คือจำนวนที่คุณต้องการเพิ่มประสิทธิภาพ ในตัวอย่างด้านบน มีวัตถุประสงค์เพื่อลดค่าใช้จ่าย ในการสร้างโจทย์การเพิ่มประสิทธิภาพ คุณต้องระบุฟังก์ชันที่คํานวณค่าของวัตถุประสงค์สําหรับวิธีแก้ปัญหาที่เป็นไปได้ ซึ่งเรียกว่าฟังก์ชันวัตถุประสงค์ ในตัวอย่างก่อนหน้านี้ ฟังก์ชันวัตถุประสงค์จะคำนวณต้นทุนทั้งหมดของการกำหนดแพ็กเกจและเส้นทาง

  โซลูชันที่เหมาะสมที่สุดคือวิธีที่ค่าของฟังก์ชันวัตถุประสงค์ได้ดีที่สุด ("ดีที่สุด" อาจเป็นจำนวนสูงสุดหรือต่ำสุดก็ได้)

• ข้อจำกัด - ข้อจำกัดเกี่ยวกับแนวทางการแก้ปัญหาที่เป็นไปได้โดยอิงตามข้อกำหนดเฉพาะของปัญหา เช่น หากบริษัทจัดส่งไม่สามารถกำหนดพัสดุที่มีน้ำหนักเกินกว่าน้ำหนักที่กำหนดกับรถบรรทุกได้ ก็จะทำให้เกิดข้อจำกัดในโซลูชัน

  วิธีแก้ปัญหาที่เป็นไปได้คือวิธีที่ตอบสนองต่อข้อจำกัดทั้งหมดที่ระบุของปัญหาโดยไม่จำเป็นต้องมีประสิทธิภาพสูงสุด

ขั้นตอนแรกในการแก้ปัญหาการเพิ่มประสิทธิภาพคือการระบุวัตถุประสงค์และข้อจำกัด

การแก้ไขปัญหาการเพิ่มประสิทธิภาพใน 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 ที่ตั้งค่าและแก้ปัญหา

หมายเหตุ: โปรแกรม 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 เป็น 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());

• กำหนดข้อจำกัด ข้อจำกัด 2 รายการแรก ได้แก่ 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 เพิ่มเติม

ดูตัวอย่าง Java เพิ่มเติมที่แสดงวิธีแก้ปัญหาการเพิ่มประสิทธิภาพประเภทต่างๆ ได้ที่ตัวอย่าง

การระบุประเภทของปัญหาที่คุณต้องการแก้ไข

ปัญหาการเพิ่มประสิทธิภาพในโลกนี้มีอยู่หลายประเภท โจทย์แต่ละประเภทมีวิธีการและอัลกอริทึมที่แตกต่างกันไปในการหาวิธีแก้ปัญหาที่ดีที่สุด

ก่อนที่จะเริ่มเขียนโปรแกรมเพื่อแก้ปัญหาการเพิ่มประสิทธิภาพ คุณต้องระบุประเภทของปัญหาที่กำลังจัดการแล้วเลือกเครื่องมือแก้ปัญหาที่เหมาะสม ซึ่งเป็นอัลกอริทึมในการค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุด

ข้อมูลด้านล่างคือภาพรวมคร่าวๆ ของประเภทปัญหาที่ "หรือ" เครื่องมือช่วยแก้ปัญหา และลิงก์ไปยังส่วนต่างๆ ในคู่มือนี้ซึ่งอธิบายวิธีแก้ปัญหาแต่ละประเภท

• การเพิ่มประสิทธิภาพเชิงเส้น
• จำกัดการเพิ่มประสิทธิภาพ
• การเพิ่มประสิทธิภาพจํานวนเต็มแบบผสม
• งาน
• การกำหนดเวลา
• การบรรจุหีบห่อ
• การกำหนดเส้นทาง
• ขั้นตอนของเครือข่าย

การเพิ่มประสิทธิภาพเชิงเส้น

ตามที่คุณได้เรียนรู้ในส่วนก่อนหน้า ปัญหาการเพิ่มประสิทธิภาพเชิงเส้นคือปัญหาหนึ่งที่ฟังก์ชันวัตถุประสงค์และข้อจํากัดเป็นนิพจน์เชิงเส้นในตัวแปร

เครื่องมือแก้โจทย์คณิตหลักใน "หรือ" สำหรับปัญหาประเภทนี้คือเครื่องมือแก้โจทย์การเพิ่มประสิทธิภาพเชิงเส้น ซึ่งเป็น Wrapper สำหรับไลบรารีต่างๆ มากมายสำหรับการเพิ่มประสิทธิภาพเชิงเส้นและจำนวนเต็มผสม รวมถึงไลบรารีของบุคคลที่สาม

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพเชิงเส้น

การเพิ่มประสิทธิภาพจำนวนเต็มผสม

ปัญหาการเพิ่มประสิทธิภาพจำนวนเต็มผสมคือปัญหาที่ตัวแปรบางส่วนหรือทั้งหมดต้องเป็นจำนวนเต็ม ตัวอย่างเช่น ปัญหาเกี่ยวกับงานที่กลุ่มผู้ปฏิบัติงานต้องถูกมอบหมายให้กับชุดงาน สำหรับผู้ปฏิบัติงานและงานแต่ละรายการ คุณจะกำหนดตัวแปรที่มีค่าเป็น 1 หากมีการมอบหมายงานดังกล่าวให้ผู้ปฏิบัติงานที่เลือก และจะเป็น 0 สำหรับกรณีอื่นๆ ในกรณีนี้ ตัวแปรจะใช้ได้เฉพาะค่า 0 หรือ 1

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพจำนวนเต็มผสม

การเพิ่มประสิทธิภาพข้อจำกัด

การเพิ่มประสิทธิภาพแบบจํากัด หรือการเขียนโปรแกรมข้อจํากัด (CP) ช่วยระบุวิธีแก้ปัญหาที่เป็นไปได้จากผู้สมัครจำนวนมาก โดยที่ปัญหาจะเป็นแบบจําลองในแง่ของข้อจํากัดที่กําหนดเอง CP อิงตามความเป็นไปได้ (การหาโซลูชันที่เป็นไปได้) แทนการเพิ่มประสิทธิภาพ (ค้นหาโซลูชันที่ดีที่สุด) และมุ่งเน้นที่ข้อจำกัดและตัวแปรมากกว่าฟังก์ชันที่เป็นวัตถุประสงค์ อย่างไรก็ตาม คุณจะใช้ CP เพื่อแก้ปัญหาการเพิ่มประสิทธิภาพได้ เพียงเปรียบเทียบค่าของฟังก์ชันวัตถุประสงค์สําหรับวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพข้อจำกัด

การมอบหมาย

ปัญหาในการมอบหมายงานเกี่ยวข้องกับการกำหนดกลุ่มของ Agent (เช่น ผู้ปฏิบัติงานหรือเครื่อง) ให้กับชุดงาน ซึ่งการมอบหมาย Agent แต่ละรายการให้กับงานที่เฉพาะเจาะจงมีค่าใช้จ่ายคงที่ ปัญหาคือการหางานที่มีต้นทุนรวมน้อยที่สุด ปัญหางานจริงๆ แล้วเป็นกรณีพิเศษ ของปัญหาการไหลของเครือข่าย

ดูข้อมูลเพิ่มเติมเกี่ยวกับการมอบหมาย

การบรรจุหีบห่อ

การบรรจุหีบห่อคือปัญหาในการบรรจุชุดวัตถุขนาดต่างๆ ลงในคอนเทนเนอร์ที่มีความจุต่างกัน เป้าหมายคือบรรจุออบเจ็กต์ให้ได้มากที่สุดเท่าที่จะเป็นไปได้ โดยขึ้นอยู่กับความจุของคอนเทนเนอร์ กรณีพิเศษของกรณีนี้คือปัญหา Knapsack ซึ่งมีคอนเทนเนอร์เพียงรายการเดียว

ดูข้อมูลเพิ่มเติมเกี่ยวกับการบรรจุหีบห่อ

Scheduling

ปัญหาการกำหนดเวลาเกี่ยวข้องกับการกำหนดทรัพยากรเพื่อทำงานชุดหนึ่งในเวลาที่เฉพาะเจาะจง ตัวอย่างที่สำคัญคือปัญหาของร้านงาน ซึ่งมีการประมวลผลงานหลายรายการในเครื่องหลายเครื่อง งานแต่ละงานประกอบไปด้วยงานต่างๆ ที่ต้องทำตามลำดับ และแต่ละงานต้องได้รับการประมวลผลในเครื่องเฉพาะ ปัญหาคือการกำหนดเวลาเพื่อให้งานทั้งหมดเสร็จสมบูรณ์โดยภายในระยะเวลาที่สั้นที่สุด

ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเวลา

การกำหนดเส้นทาง

ปัญหาการกำหนดเส้นทางเกี่ยวข้องกับการค้นหาเส้นทางที่ดีที่สุดสำหรับยานพาหนะกลุ่มหนึ่งเพื่อข้ามผ่านเครือข่าย ซึ่งระบุด้วยกราฟที่มีทิศทาง ปัญหาในการกำหนดแพ็กเกจให้กับรถบรรทุกสินค้าที่อธิบายไว้ในปัญหาการเพิ่มประสิทธิภาพคืออะไรเป็นตัวอย่างหนึ่งของปัญหาในการกำหนดเส้นทาง อีกประการหนึ่งคือปัญหาเกี่ยวกับพนักงานขายที่เดินทาง

ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเส้นทาง

ขั้นตอนของเครือข่าย

ปัญหาการเพิ่มประสิทธิภาพหลายอย่างอาจแสดงด้วยกราฟมีทิศทาง ซึ่งประกอบไปด้วยโหนดและส่วนโค้งที่มีทิศทางตรงระหว่างโหนดเหล่านั้น ตัวอย่างเช่น ปัญหาในการขนส่ง ซึ่งการจัดส่งสินค้าผ่านเครือข่ายทางรถไฟอาจแสดงด้วยกราฟที่เส้นโค้งเป็นทางรถไฟ และโหนดคือศูนย์กระจายสินค้า

ในปัญหาการไหลสูงสุด เส้นโค้งแต่ละโค้งจะมีความจุสูงสุดที่ถ่ายโอนได้ ปัญหาคือการกำหนดจำนวนสินค้าที่จะจัดส่งในแต่ละกราฟ เพื่อให้ปริมาณรวมที่ขนส่งมีมากที่สุดเท่าที่เป็นไปได้

ดูข้อมูลเพิ่มเติมเกี่ยวกับโฟลว์ของเครือข่าย