ส่วนต่อไปนี้จะช่วยคุณในการเริ่มต้นใช้งานเครื่องมือ "หรือ" กับ C++
- ปัญหาในการเพิ่มประสิทธิภาพคืออะไร
- การแก้ปัญหาการเพิ่มประสิทธิภาพใน C++
- ตัวอย่าง C++ เพิ่มเติม
- การระบุประเภทปัญหาที่คุณต้องการแก้ไข
ปัญหาในการเพิ่มประสิทธิภาพคืออะไร
เป้าหมายของการเพิ่มประสิทธิภาพคือการค้นหาวิธีแก้ปัญหาที่ดีที่สุดจากชุดวิธีแก้ปัญหาขนาดใหญ่ที่เป็นไปได้ (บางครั้งคุณพึงพอใจกับการหาวิธีแก้ปัญหาที่ทำได้ หรือเครื่องมือก็สามารถทำได้เช่นกัน)
ต่อไปนี้คือปัญหาการเพิ่มประสิทธิภาพโดยทั่วไป สมมติว่าบริษัทจัดส่งแห่งหนึ่งส่งพัสดุภัณฑ์ให้กับลูกค้าโดยใช้รถบรรทุกคัน ในทุกๆ วัน บริษัทต้องกำหนดพัสดุให้กับรถบรรทุก แล้วเลือกเส้นทางที่ให้รถบรรทุกแต่ละคันเพื่อนำส่งพัสดุ การมอบหมายพัสดุและเส้นทางแต่ละเส้นจะมีค่าใช้จ่ายตามระยะทางในการเดินทางรวมของรถบรรทุกและอาจมีปัจจัยอื่นๆ ด้วย ปัญหาคือการเลือกการกำหนดแพ็กเกจและเส้นทางที่มีค่าใช้จ่ายน้อยที่สุด
เช่นเดียวกับปัญหาการเพิ่มประสิทธิภาพทั้งหมด ปัญหานี้มีองค์ประกอบต่อไปนี้:
วัตถุประสงค์ ซึ่งก็คือจำนวนที่คุณต้องการเพิ่มประสิทธิภาพ ในตัวอย่างด้านบน มีวัตถุประสงค์เพื่อลดค่าใช้จ่าย ในการสร้างโจทย์การเพิ่มประสิทธิภาพ คุณต้องระบุฟังก์ชันที่คํานวณค่าของวัตถุประสงค์สําหรับวิธีแก้ปัญหาที่เป็นไปได้ ซึ่งเรียกว่าฟังก์ชันวัตถุประสงค์ ในตัวอย่างก่อนหน้านี้ ฟังก์ชันวัตถุประสงค์จะคำนวณต้นทุนทั้งหมดของการกำหนดแพ็กเกจและเส้นทาง
โซลูชันที่เหมาะสมที่สุดคือวิธีที่ค่าของฟังก์ชันวัตถุประสงค์ได้ดีที่สุด ("ดีที่สุด" อาจเป็นจำนวนสูงสุดหรือต่ำสุดก็ได้)
ข้อจำกัด - ข้อจำกัดเกี่ยวกับแนวทางการแก้ปัญหาที่เป็นไปได้โดยอิงตามข้อกำหนดเฉพาะของปัญหา เช่น หากบริษัทจัดส่งไม่สามารถกำหนดพัสดุที่มีน้ำหนักเกินกว่าน้ำหนักที่กำหนดกับรถบรรทุกได้ ก็จะทำให้เกิดข้อจำกัดในโซลูชัน
วิธีแก้ปัญหาที่เป็นไปได้คือวิธีที่ตอบสนองต่อข้อจำกัดทั้งหมดที่ระบุของปัญหาโดยไม่จำเป็นต้องมีประสิทธิภาพสูงสุด
ขั้นตอนแรกในการแก้ปัญหาการเพิ่มประสิทธิภาพคือการระบุวัตถุประสงค์และข้อจำกัด
การแก้ไขปัญหาการเพิ่มประสิทธิภาพใน C++
ต่อไป เราจะยกตัวอย่างปัญหาการเพิ่มประสิทธิภาพ และแสดงวิธีการตั้งค่าและแก้โจทย์ใน C++
ตัวอย่างการเพิ่มประสิทธิภาพเชิงเส้น
การเพิ่มประสิทธิภาพที่เก่าที่สุดและใช้กันอย่างแพร่หลายที่สุดคือการเพิ่มประสิทธิภาพเชิงเส้น (หรือการเขียนโปรแกรมเชิงเส้น) ซึ่งจะเขียนฟังก์ชันวัตถุประสงค์และข้อจำกัดเป็นนิพจน์เชิงเส้นได้ นี่คือตัวอย่างง่ายๆ ของปัญหาประเภทนี้
เพิ่ม 3x + y
ให้มากที่สุดภายใต้ข้อจำกัดต่อไปนี้
- 0 ≤
x
≤ 1 - 0 ≤
y
≤ 2 x + y
≤ 2
ฟังก์ชันวัตถุประสงค์ในตัวอย่างนี้คือ 3x + y
ทั้งฟังก์ชันวัตถุประสงค์และข้อจำกัดต่างก็กำหนดด้วยนิพจน์เชิงเส้น ซึ่งทำให้เป็นปัญหาเชิงเส้น
ขั้นตอนหลักในการแก้ปัญหา
ขั้นตอนพื้นฐานในการตั้งค่าและแก้ปัญหาสำหรับแต่ละภาษาจะเหมือนกัน
- นำเข้าไลบรารีที่จำเป็น
- ประกาศเครื่องมือแก้โจทย์
- สร้างตัวแปร
- กำหนดข้อจำกัด
- กำหนดฟังก์ชันวัตถุประสงค์
- เรียกใช้ตัวแก้โจทย์และ
- แสดงผลลัพธ์
โปรแกรม C++
ส่วนนี้จะอธิบายโปรแกรม C++ ที่ตั้งค่าและแก้ปัญหา
มีขั้นตอนดังนี้
- นำเข้าไลบรารีที่จำเป็น
#include <memory> #include <ostream> #include "ortools/linear_solver/linear_solver.h"
- ประกาศเครื่องมือแก้โจทย์
// Create the linear solver with the GLOP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
MPSolver
เป็น Wrapper สำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นหรือการเขียนโปรแกรมจำนวนเต็มผสม - สร้างตัวแปร
// 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();
- กำหนดข้อจำกัด
ข้อจำกัด 2 รายการแรก ได้แก่
0
≤x
≤1
และ0
≤y
≤2
กำหนดโดยคำจำกัดความของตัวแปรแล้ว โค้ดต่อไปนี้กำหนดข้อจำกัดx + y
≤2
:// Create a linear constraint, 0 <= x + y <= 2. MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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
ประกาศว่านี่คือปัญหาการเกิดประโยชน์สูงสุด - เรียกใช้เครื่องมือแก้โจทย์และแสดงผลลัพธ์
solver->Solve(); LOG(INFO) << "Solution:" << std::endl; LOG(INFO) << "Objective value = " << objective->Value(); LOG(INFO) << "x = " << x->solution_value(); LOG(INFO) << "y = " << y->solution_value();
ดำเนินการตามโปรแกรมให้เสร็จสมบูรณ์
โปรดดูรายการโปรแกรมที่สมบูรณ์ด้านล่าง
#include <memory>
#include <ostream>
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
void BasicExample() {
// Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
// 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, 0 <= x + y <= 2.
MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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();
solver->Solve();
LOG(INFO) << "Solution:" << std::endl;
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();
}
} // namespace operations_research
int main() {
operations_research::BasicExample();
return EXIT_SUCCESS;
}
การเรียกใช้โปรแกรม C++
คุณเรียกใช้โปรแกรมข้างต้นได้โดยทำดังนี้
- คัดลอกและวางโค้ดข้างต้นลงในไฟล์ใหม่ แล้วบันทึกเป็น
program.cc
- เปิดหน้าต่างคำสั่งที่ระดับบนสุดของไดเรกทอรีที่ติดตั้ง "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++
เมื่อคอมไพล์โปรแกรม C++ ของ OR-Tools ด้วย make
ระบบจะสร้างไฟล์ปฏิบัติการในไดเรกทอรี bin
คุณเรียกใช้ไฟล์ปฏิบัติการสำหรับโปรแกรมตัวอย่างได้โดยทำดังนี้
cd bin && ./program
หากทำการเปลี่ยนแปลงในโปรแกรม คุณจะต้องคอมไพล์อีกครั้งดังที่แสดงด้านบน
ตัวอย่าง C++ เพิ่มเติม
ดูตัวอย่าง C++ เพิ่มเติมที่แสดงให้เห็นวิธีแก้ปัญหาการเพิ่มประสิทธิภาพประเภทต่างๆ ได้ที่ตัวอย่าง
การระบุประเภทของปัญหาที่คุณต้องการแก้ไข
ปัญหาการเพิ่มประสิทธิภาพในโลกนี้มีอยู่หลายประเภท โจทย์แต่ละประเภทมีวิธีการและอัลกอริทึมที่แตกต่างกันไปในการหาวิธีแก้ปัญหาที่ดีที่สุด
ก่อนที่จะเริ่มเขียนโปรแกรมเพื่อแก้ปัญหาการเพิ่มประสิทธิภาพ คุณต้องระบุประเภทของปัญหาที่กำลังจัดการแล้วเลือกเครื่องมือแก้ปัญหาที่เหมาะสม ซึ่งเป็นอัลกอริทึมในการค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุด
ข้อมูลด้านล่างคือภาพรวมคร่าวๆ ของประเภทปัญหาที่ "หรือ" เครื่องมือช่วยแก้ปัญหา และลิงก์ไปยังส่วนต่างๆ ในคู่มือนี้ซึ่งอธิบายวิธีแก้ปัญหาแต่ละประเภท
- การเพิ่มประสิทธิภาพเชิงเส้น
- จำกัดการเพิ่มประสิทธิภาพ
- การเพิ่มประสิทธิภาพจํานวนเต็มแบบผสม
- งาน
- การกำหนดเวลา
- การบรรจุหีบห่อ
- การกำหนดเส้นทาง
- ขั้นตอนของเครือข่าย
การเพิ่มประสิทธิภาพเชิงเส้น
ตามที่คุณได้เรียนรู้ในส่วนก่อนหน้า ปัญหาการเพิ่มประสิทธิภาพเชิงเส้นคือปัญหาหนึ่งที่ฟังก์ชันวัตถุประสงค์และข้อจํากัดเป็นนิพจน์เชิงเส้นในตัวแปร
เครื่องมือแก้โจทย์คณิตหลักใน "หรือ" สำหรับปัญหาประเภทนี้คือเครื่องมือแก้โจทย์การเพิ่มประสิทธิภาพเชิงเส้น ซึ่งเป็น Wrapper สำหรับไลบรารีต่างๆ มากมายสำหรับการเพิ่มประสิทธิภาพเชิงเส้นและจำนวนเต็มผสม รวมถึงไลบรารีของบุคคลที่สาม
ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพเชิงเส้น
การเพิ่มประสิทธิภาพจำนวนเต็มผสม
ปัญหาการเพิ่มประสิทธิภาพจำนวนเต็มผสมคือปัญหาที่ตัวแปรบางส่วนหรือทั้งหมดต้องเป็นจำนวนเต็ม ตัวอย่างเช่น ปัญหาเกี่ยวกับงานที่กลุ่มผู้ปฏิบัติงานต้องถูกมอบหมายให้กับชุดงาน สำหรับผู้ปฏิบัติงานและงานแต่ละรายการ คุณจะกำหนดตัวแปรที่มีค่าเป็น 1 หากมีการมอบหมายงานดังกล่าวให้ผู้ปฏิบัติงานที่เลือก และจะเป็น 0 สำหรับกรณีอื่นๆ ในกรณีนี้ ตัวแปรจะใช้ได้เฉพาะค่า 0 หรือ 1
ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพจำนวนเต็มผสม
การเพิ่มประสิทธิภาพข้อจำกัด
การเพิ่มประสิทธิภาพแบบจํากัด หรือการเขียนโปรแกรมข้อจํากัด (CP) ช่วยระบุวิธีแก้ปัญหาที่เป็นไปได้จากผู้สมัครจำนวนมาก โดยที่ปัญหาจะเป็นแบบจําลองในแง่ของข้อจํากัดที่กําหนดเอง CP อิงตามความเป็นไปได้ (การหาโซลูชันที่เป็นไปได้) แทนการเพิ่มประสิทธิภาพ (ค้นหาโซลูชันที่ดีที่สุด) และมุ่งเน้นที่ข้อจำกัดและตัวแปรมากกว่าฟังก์ชันที่เป็นวัตถุประสงค์ อย่างไรก็ตาม คุณจะใช้ CP เพื่อแก้ปัญหาการเพิ่มประสิทธิภาพได้ เพียงเปรียบเทียบค่าของฟังก์ชันวัตถุประสงค์สําหรับวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด
ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพข้อจำกัด
การมอบหมาย
ปัญหาในการมอบหมายงานเกี่ยวข้องกับการกำหนดกลุ่มของ Agent (เช่น ผู้ปฏิบัติงานหรือเครื่อง) ให้กับชุดงาน ซึ่งการมอบหมาย Agent แต่ละรายการให้กับงานที่เฉพาะเจาะจงมีค่าใช้จ่ายคงที่ ปัญหาคือการหางานที่มีต้นทุนรวมน้อยที่สุด ปัญหางานจริงๆ แล้วเป็นกรณีพิเศษ ของปัญหาการไหลของเครือข่าย
ดูข้อมูลเพิ่มเติมเกี่ยวกับการมอบหมาย
การบรรจุหีบห่อ
การบรรจุหีบห่อคือปัญหาในการบรรจุชุดวัตถุขนาดต่างๆ ลงในคอนเทนเนอร์ที่มีความจุต่างกัน เป้าหมายคือบรรจุออบเจ็กต์ให้ได้มากที่สุดเท่าที่จะเป็นไปได้ โดยขึ้นอยู่กับความจุของคอนเทนเนอร์ กรณีพิเศษของกรณีนี้คือปัญหา Knapsack ซึ่งมีคอนเทนเนอร์เพียงรายการเดียว
ดูข้อมูลเพิ่มเติมเกี่ยวกับการบรรจุหีบห่อ
Scheduling
ปัญหาการกำหนดเวลาเกี่ยวข้องกับการกำหนดทรัพยากรเพื่อทำงานชุดหนึ่งในเวลาที่เฉพาะเจาะจง ตัวอย่างที่สำคัญคือปัญหาของร้านงาน ซึ่งมีการประมวลผลงานหลายรายการในเครื่องหลายเครื่อง งานแต่ละงานประกอบไปด้วยงานต่างๆ ที่ต้องทำตามลำดับ และแต่ละงานต้องได้รับการประมวลผลในเครื่องเฉพาะ ปัญหาคือการกำหนดเวลาเพื่อให้งานทั้งหมดเสร็จสมบูรณ์โดยภายในระยะเวลาที่สั้นที่สุด
ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเวลา
การกำหนดเส้นทาง
ปัญหาการกำหนดเส้นทางเกี่ยวข้องกับการค้นหาเส้นทางที่ดีที่สุดสำหรับยานพาหนะกลุ่มหนึ่งเพื่อข้ามผ่านเครือข่าย ซึ่งระบุด้วยกราฟที่มีทิศทาง ปัญหาในการกำหนดแพ็กเกจให้กับรถบรรทุกสินค้าที่อธิบายไว้ในปัญหาการเพิ่มประสิทธิภาพคืออะไรเป็นตัวอย่างหนึ่งของปัญหาในการกำหนดเส้นทาง อีกประการหนึ่งคือปัญหาเกี่ยวกับพนักงานขายที่เดินทาง
ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเส้นทาง
ขั้นตอนของเครือข่าย
ปัญหาการเพิ่มประสิทธิภาพหลายอย่างอาจแสดงด้วยกราฟมีทิศทาง ซึ่งประกอบไปด้วยโหนดและส่วนโค้งที่มีทิศทางตรงระหว่างโหนดเหล่านั้น ตัวอย่างเช่น ปัญหาในการขนส่ง ซึ่งการจัดส่งสินค้าผ่านเครือข่ายทางรถไฟอาจแสดงด้วยกราฟที่เส้นโค้งเป็นทางรถไฟ และโหนดคือศูนย์กระจายสินค้า
ในปัญหาการไหลสูงสุด เส้นโค้งแต่ละโค้งจะมีความจุสูงสุดที่ถ่ายโอนได้ ปัญหาคือการกำหนดจำนวนสินค้าที่จะจัดส่งในแต่ละกราฟ เพื่อให้ปริมาณรวมที่ขนส่งมีมากที่สุดเท่าที่เป็นไปได้