Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงเส้นจำนวนเต็มผสมหลายวัตถุประสงค์

ผู้เสนอ
Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
ปี
1980s–2000s
ประเภท
Mathematical optimization
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมเชิงเส้นจำนวนเต็มผสมหลายวัตถุประสงค์ (Multi-Objective Mixed-Integer Programming หรือ MO-MIP) เป็นกรอบการทำงานสำหรับการหาค่าเหมาะที่สุดที่ปรับปรุงฟังก์ชันวัตถุประสงค์สองฟังก์ชันขึ้นไปที่มีความขัดแย้งกันพร้อมกัน ภายใต้ข้อจำกัดเชิงเส้นหรือไม่เป็นเชิงเส้น โดยที่ตัวแปรตัดสินใจบางตัวถูกจำกัดให้เป็นค่าจำนวนเต็มและตัวแปรอื่น ๆ เป็นค่าต่อเนื่อง มีการประยุกต์ใช้อย่างกว้างขวางในการออกแบบทางวิศวกรรม การวางแผนห่วงโซ่อุปทาน การจัดสรรทรัพยากร และปัญหาการจัดตารางเวลาที่ต้องการการเลือกแบบไม่ต่อเนื่องควบคู่ไปกับปริมาณต่อเนื่อง

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

การโปรแกรมเชิงเส้นจำนวนเต็มผสมได้รับการกำหนดอย่างเป็นทางการในช่วงทศวรรษ 1950-1960 จากผลงานของ Gomory และ Land และ Doig การขยายผลแบบหลายวัตถุประสงค์เกิดขึ้นในช่วงทศวรรษ 1970-1980 เมื่อนักวิจัยตระหนักว่าปัญหาทางวิศวกรรมและการวิจัยการดำเนินงานจำนวนมากเกี่ยวข้องกับเป้าหมายที่แข่งขันกัน การจัดการอย่างเป็นระบบได้รับการรวบรวมโดย Ehrgott (2005) และ Mavrotas (2009) ซึ่งการนำ epsilon-constraint ไปใช้ยังคงเป็นข้อมูลอ้างอิงที่อ้างถึงอย่างกว้างขวางสำหรับการใช้งาน MO-MIP ในทางปฏิบัติ

ควรใช้เมื่อใด

ใช้ MO-MIP เมื่อปัญหาการตัดสินใจเกี่ยวข้องกับตัวแปรจำนวนเต็มหรือไบนารีโดยธรรมชาติ (การเลือกที่ตั้งโรงงาน การเลือกโครงการ การจัดตารางเวลา) ควบคู่ไปกับปริมาณต่อเนื่อง และเมื่อต้องมีการแลกเปลี่ยนระหว่างวัตถุประสงค์ที่ขัดแย้งกันสองอย่างขึ้นไปอย่างชัดเจน เหมาะสมเมื่อต้องการคำตอบ Pareto ที่แม่นยำหรือใกล้เคียงความแม่นยำ และทรัพยากรการคำนวณเอื้ออำนวยต่อการค้นหาแบบ branch-and-bound ห้ามใช้เมื่อตัวแปรทั้งหมดเป็นแบบต่อเนื่อง (ให้ใช้ multi-objective LP หรือ nonlinear programming แทน) เมื่อขนาดของปัญหาทำให้การแก้ MIP แบบแม่นยำเป็นไปไม่ได้และ metaheuristics มีประโยชน์มากกว่า หรือเมื่อวัตถุประสงค์รวมเพียงอย่างเดียวเพียงพอและการวิเคราะห์หลายวัตถุประสงค์ไม่ได้เพิ่มคุณค่าในการตัดสินใจ

ข้อจำกัดและข้อควรพิจารณา

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

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ให้คำตอบที่เหมาะสมที่สุดหรือใกล้เคียงที่สุดที่พิสูจน์ได้สำหรับปัญหาย่อยที่ปรับเป็นสเกลาร์แต่ละปัญหา รับประกันคุณภาพของ Pareto front สำหรับขนาดปัญหาที่จัดการได้
  • จัดการกับการเลือกแบบไม่ต่อเนื่องในโลกแห่งความเป็นจริงได้อย่างเป็นธรรมชาติ (การตัดสินใจแบบไบนารี ปริมาณจำนวนเต็ม) ซึ่งการผ่อนคลายแบบต่อเนื่องไม่สามารถแสดงได้อย่างถูกต้อง
  • ให้ Pareto front ที่สมบูรณ์ ทำให้ผู้ตัดสินใจได้รับข้อมูลการแลกเปลี่ยนที่โปร่งใสและมีโครงสร้าง แทนที่จะเป็นการประนีประนอมที่ถูกบังคับเพียงครั้งเดียว
  • วิธีข้อจำกัดเอปไซลอนและการปรับเป็นสเกลาร์แบบเป็นระบบอื่น ๆ ช่วยให้สามารถสำรวจชุดคำตอบที่ไม่ถูกครอบงำได้อย่างหนาแน่นและควบคุมได้
  • เข้ากันได้กับตัวแก้ปัญหาเชิงพาณิชย์และโอเพนซอร์สที่หลากหลาย (CPLEX, Gurobi, GLPK, CBC) ที่จัดการปัญหา MIP ขนาดใหญ่ได้

การประยุกต์ใช้

  • การเลือกที่ตั้งโรงงานและการออกแบบเครือข่ายห่วงโซ่อุปทาน: ลดต้นทุนและเพิ่มความครอบคลุมการบริการลูกค้าพร้อมกันด้วยตัวแปรไบนารีเปิด/ปิด
  • การจัดทำงบประมาณลงทุนและการเลือกกลุ่มโครงการ: เพิ่มผลตอบแทนและลดความเสี่ยงภายใต้ข้อจำกัดด้านงบประมาณและทรัพยากรด้วยตัวแปรไบนารีการเลือกโครงการ
  • การจัดตารางการผลิต: ลด makespan และ tardiness พร้อมกันด้วยขนาดล็อตจำนวนเต็มและการกำหนดเครื่องจักรแบบไบนารี
  • การวางแผนระบบพลังงาน: ปรับต้นทุนและการปล่อย CO2 ให้เหมาะสมสำหรับส่วนผสมโรงไฟฟ้าด้วยการตัดสินใจลงทุนแบบไม่ต่อเนื่องและตัวแปรการจัดส่งแบบต่อเนื่อง
  • การจัดสรรทรัพยากรด้านการดูแลสุขภาพ: เพิ่มความครอบคลุมของผู้ป่วยและความเท่าเทียมกันในขณะที่ลดค่าใช้จ่ายโดยใช้จำนวนพนักงานที่เป็นจำนวนเต็มและการตัดสินใจเกี่ยวกับสิ่งอำนวยความสะดวกแบบไบนารี
  • การขนส่งและโลจิสติกส์: ลดเวลาเดินทางและการปล่อยมลพิษพร้อมกันด้วยจำนวนยานพาหนะที่เป็นจำนวนเต็มและการตัดสินใจเส้นทาง

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดปัญหาโดยระบุฟังก์ชันวัตถุประสงค์ k ฟังก์ชัน f_1(x), ..., f_k(x) ที่จะลดหรือเพิ่มให้มากที่สุด ชุดของข้อจำกัดเชิงเส้นหรือไม่เป็นเชิงเส้น Ax <= b และโดเมนตัวแปรที่ตัวแปรบางตัวเป็นค่าจำนวนเต็ม (เช่น ไบนารี 0/1) และตัวแปรอื่น ๆ เป็นค่าต่อเนื่อง กำหนดขอบเขตและข้อมูลให้ชัดเจนก่อนการแก้ปัญหา

2

ใช้กลยุทธ์การปรับเป็นสเกลาร์ (scalarization) หรือการแยกส่วน (decomposition) เพื่อแปลงปัญหาหลายวัตถุประสงค์ให้เป็นลำดับของปัญหาย่อย MIP แบบวัตถุประสงค์เดียว กลยุทธ์ทั่วไปได้แก่ วิธีผลรวมถ่วงน้ำหนัก (minimize sum of w_i * f_i) วิธีข้อจำกัดเอปไซลอน (optimize one objective while constraining others to threshold levels) และฟังก์ชันปรับเป็นสเกลาร์แบบบรรลุเป้าหมาย (achievement scalarizing functions)

3

แก้ปัญหาย่อย MIP ที่ปรับเป็นสเกลาร์แต่ละปัญหาโดยใช้วิธี branch-and-bound, branch-and-cut หรือตัวแก้ปัญหาที่แม่นยำอื่น ๆ (เช่น CPLEX, Gurobi, GLPK) สำหรับปัญหาย่อยแต่ละปัญหา ตัวแก้ปัญหาจะสำรวจพื้นที่คำตอบที่เป็นไปได้สำหรับจำนวนเต็ม โดยใช้การผ่อนคลาย LP ที่แต่ละโหนดและตัดกิ่งที่ไม่เป็นไปได้หรือถูกครอบงำออก

4

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

5

นำเสนอ Pareto front ให้กับผู้ตัดสินใจพร้อมกับการแสดงภาพประกอบ (แผนภาพกระจาย, แผนภาพพิกัดขนาน) ใช้กฎการตัดสินใจหลายเกณฑ์ ความชอบของผู้มีส่วนได้ส่วนเสีย หรือการจัดลำดับตามพจนานุกรมเพื่อเลือกคำตอบที่ต้องการจากชุดคำตอบที่ไม่ถูกครอบงำสำหรับการนำไปใช้

ข้อผิดพลาดที่พบบ่อย

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

คำถามที่พบบ่อย

MO-MIP แตกต่างจากการโปรแกรมเชิงเส้นหลายวัตถุประสงค์มาตรฐานอย่างไร?

ในการโปรแกรมเชิงเส้นหลายวัตถุประสงค์ ตัวแปรตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง ดังนั้นจึงสามารถหาคำตอบ Pareto ที่มีประสิทธิภาพได้ที่จุดยอดของรูปทรงหลายเหลี่ยมนูน MO-MIP กำหนดให้ตัวแปรบางตัวหรือทั้งหมดเป็นค่าจำนวนเต็ม ทำให้ชุดที่เป็นไปได้ไม่นูนและไม่ต่อเนื่อง ซึ่งต้องใช้การค้นหาแบบ branch-and-bound แทนที่จะเป็นวิธีที่ใช้ simplex

ฉันสามารถใช้ metaheuristics เช่น NSGA-II แทนตัวแก้ปัญหา MIP ที่แม่นยำได้หรือไม่?

ได้ และสำหรับปัญหาขนาดใหญ่หรือปัญหาที่ซับซ้อนเชิงการจัดหมู่ มักนิยมใช้ metaheuristics เนื่องจากปรับขนาดได้ดีกว่า ข้อเสียคือให้ Pareto fronts โดยประมาณโดยไม่มีการรับประกันความเหมาะสมที่สุด ในขณะที่ตัวแก้ปัญหา MO-MIP ที่แม่นยำรับประกันการไม่ถูกครอบงำสำหรับคำตอบที่พบ

วิธีข้อจำกัดเอปไซลอนคืออะไรและทำไมจึงแนะนำ?

วิธีข้อจำกัดเอปไซลอนจะปรับปรุงวัตถุประสงค์หนึ่งในขณะที่จำกัดวัตถุประสงค์อื่น ๆ ทั้งหมดไม่ให้แย่ไปกว่าขอบเขตที่กำหนด (epsilons) สามารถค้นหาคำตอบในภูมิภาค Pareto ที่ไม่นูนซึ่งวิธีผลรวมถ่วงน้ำหนักพลาดไปได้ ทำให้เชื่อถือได้มากกว่าสำหรับปัญหา MO-MIP ทั่วไป

ฉันควรสร้างคำตอบ Pareto กี่คำตอบ?

ขึ้นอยู่กับจำนวนวัตถุประสงค์และความละเอียดที่จำเป็นสำหรับการตัดสินใจ สำหรับสองวัตถุประสงค์ โดยทั่วไป 20-50 คำตอบที่เว้นระยะห่างเท่ากันก็เพียงพอที่จะอธิบาย front ได้ สำหรับสามวัตถุประสงค์ขึ้นไป จำนวนจะเพิ่มขึ้นแบบผสมผสาน; แนะนำให้ใช้วิธีแบบโต้ตอบหรือแบบนำโดยความชอบเพื่อหลีกเลี่ยงการมีคำตอบมากเกินไป

MO-MIP เหมาะสำหรับปัญหาที่มีความไม่แน่นอนในข้อมูลหรือไม่?

MO-MIP มาตรฐานถือว่าข้อมูลเป็นแบบกำหนด การเมื่อข้อมูลนำเข้าไม่แน่นอน ควรใช้ร่วมกับการปรับปรุงการหาค่าเหมาะที่สุดที่แข็งแกร่ง (robust optimization) หรือการโปรแกรมเชิงสุ่ม (stochastic programming) เช่น MO-MIP แบบสุ่มสองขั้นตอน หรือ MO-MIP ที่แข็งแกร่งพร้อมขอบเขตวัตถุประสงค์กรณีที่เลวร้ายที่สุด

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.

    ISBN: 9783540213987
    คัดลอกแล้ว
  2. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว