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

การโปรแกรมเชิงเส้นหลายวัตถุประสงค์ (Multi-Objective Linear Programming - MOLP)

ผู้เสนอ
Steuer, R. E.; Charnes, A.; Cooper, W. W.
ปี
1955–1986
ประเภท
Mathematical optimization / vector optimization
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

การโปรแกรมเชิงเส้นหลายวัตถุประสงค์ (MOLP) เป็นการขยายแนวคิดของการโปรแกรมเชิงเส้นแบบดั้งเดิม เพื่อจัดการกับฟังก์ชันวัตถุประสงค์เชิงเส้นหลายฟังก์ชันที่ขัดแย้งกันไปพร้อมๆ กัน ภายในขอบเขตที่สามารถดำเนินการได้ ซึ่งกำหนดโดยข้อจำกัดเชิงเส้น แทนที่จะได้คำตอบที่ดีที่สุดเพียงคำตอบเดียว MOLP จะสร้างเส้นขอบฟ้าที่มีประสิทธิภาพแบบพาเรโต (Pareto-efficient frontier) ซึ่งผู้มีอำนาจตัดสินใจจะเลือกจุดที่ยอมรับการแลกเปลี่ยนผลประโยชน์ได้ (trade-off) วิธีการนี้เป็นพื้นฐานสำคัญในสาขาวิจัยดำเนินงาน (operations research) และวิทยาการจัดการ (management science) สำหรับปัญหาการจัดสรรทรัพยากร การวางแผน และการออกแบบที่มีเป้าหมายแข่งขันกัน

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

ในการโปรแกรมเชิงเส้นแบบปกติ คุณจะทำการลดต้นทุนให้ต่ำสุด หรือเพิ่มผลกำไรให้สูงสุด แต่การตัดสินใจในโลกแห่งความเป็นจริงมักเกี่ยวข้องกับเป้าหมายที่แข่งขันกันหลายประการเสมอ เช่น ลดต้นทุนพร้อมๆ กับเพิ่มระดับการให้บริการ และลดการปล่อยมลพิษไปพร้อมกัน MOLP ตระหนักดีว่าไม่มีคำตอบใดที่ดีที่สุดสำหรับทุกวัตถุประสงค์ในคราวเดียว วิธีการนี้จะแสดงแผนที่ของชุดคำตอบที่ไม่มีใครด้อยกว่า (non-dominated) หรือมีประสิทธิภาพแบบพาเรโต (Pareto-efficient) ทั้งหมด ซึ่งการปรับปรุงวัตถุประสงค์หนึ่งจะส่งผลให้วัตถุประสงค์อื่นแย่ลงอย่างหลีกเลี่ยงไม่ได้ จากนั้น ผู้มีอำนาจตัดสินใจจะใช้ข้อมูลความพึงพอใจ เช่น น้ำหนัก (weights) ระดับความปรารถนา (aspiration levels) หรือการสอบถามแบบโต้ตอบ (interactive queries) เพื่อเลือกคำตอบสุดท้ายจากเส้นขอบฟ้าดังกล่าว ทำให้การแลกเปลี่ยนผลประโยชน์มีความชัดเจน แทนที่จะถูกซ่อนอยู่ภายในคะแนนรวม

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

รากฐานทางทฤษฎีของการโปรแกรมเชิงเส้นหลายวัตถุประสงค์สืบย้อนไปถึงงานของ Charnes และ Cooper ในปี 1950 เกี่ยวกับการโปรแกรมตามเป้าหมาย (goal programming) และ Koopmans เกี่ยวกับการผลิตที่มีประสิทธิภาพ (efficient production) หนังสือของ Steuer ในปี 1986 ได้รวบรวมองค์ความรู้ในสาขานี้ โดยจัดระบบวิธีผลรวมถ่วงน้ำหนัก วิธีอิงข้อจำกัดเอปไซลอน และวิธีแบบโต้ตอบ ซึ่งยังคงเป็นมาตรฐานมาจนถึงปัจจุบัน ปัจจุบัน MOLP เป็นหัวข้อหลักในหลักสูตรวิจัยดำเนินงานทั่วโลก

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

กำหนดฟังก์ชันวัตถุประสงค์เชิงเส้น k ฟังก์ชัน f1(x) ถึง fk(x) และขอบเขตที่สามารถดำเนินการได้ X ซึ่งกำหนดโดยข้อจำกัดอสมการและสมการเชิงเส้น (Ax <= b, x >= 0) ระบุว่าวัตถุประสงค์ใดควรถูกลดค่าให้ต่ำสุด และวัตถุประสงค์ใดควรถูกเพิ่มค่าให้สูงสุด ตรวจสอบให้แน่ใจว่าฟังก์ชันวัตถุประสงค์และข้อจำกัดทั้งหมดเป็นเชิงเส้นในตัวแปรตัดสินใจ

สูตร
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

สร้างชุดคำตอบที่มีประสิทธิภาพแบบพาเรโต (non-dominated solutions) วิธีการทั่วไป ได้แก่ วิธีผลรวมถ่วงน้ำหนัก (weighted-sum method) โดยการปรับน้ำหนักต่างๆ ในซิมเพล็กซ์ วิธีอิงข้อจำกัดเอปไซลอน (epsilon-constraint method) โดยการหาค่าที่เหมาะสมที่สุดของวัตถุประสงค์หนึ่งขณะจำกัดขอบเขตของวัตถุประสงค์อื่น และวิธีเชบิเชฟ (Chebyshev method) แต่ละวิธีจะติดตามส่วนหนึ่งหรือทั้งหมดของเส้นขอบฟ้าที่มีประสิทธิภาพ

3

ใช้เทคนิคการแปลงสเกลาร์ (scalarization technique) เพื่อแปลงปัญหาเวกเตอร์ให้เป็นปัญหา LP แบบวัตถุประสงค์เดียวตามลำดับ ในแนวทางผลรวมถ่วงน้ำหนัก ให้แก้ปัญหา min sum(wi * fi(x)) สำหรับเวกเตอร์น้ำหนักที่เปลี่ยนแปลงอย่างเป็นระบบ บันทึกจุดยอดที่มีประสิทธิภาพแต่ละจุดของปริภูมิวัตถุประสงค์

สูตร
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

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

5

ให้ผู้มีอำนาจตัดสินใจมีส่วนร่วมในการเลือกคำตอบที่ต้องการจากชุดคำตอบที่มีประสิทธิภาพ วิธีการแบบโต้ตอบ (interactive methods) เช่น STEM, NIMBUS สลับระหว่างการนำเสนอคำตอบและการสอบถามผู้มีอำนาจตัดสินใจเพื่อแสดงความพึงพอใจ โดยจะค่อยๆ เข้าใกล้การเลือกขั้นสุดท้ายที่สะท้อนลำดับความสำคัญของพวกเขาได้ดีที่สุด

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

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

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

MOLP แตกต่างจากการโปรแกรมตามเป้าหมาย (goal programming) อย่างไร?

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

MOLP สามารถจัดการกับวัตถุประสงค์มากกว่าสองข้อได้หรือไม่?

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

จะทำอย่างไรหากข้อมูลของฉันมีความไม่แน่นอน?

MOLP มาตรฐานจะสมมติว่าสัมประสิทธิ์เป็นค่าที่แน่นอน ความไม่แน่นอนสามารถจัดการได้โดยการขยายไปสู่การโปรแกรมเชิงเส้นหลายวัตถุประสงค์เชิงสุ่ม (stochastic multi-objective linear programming) (เช่น ข้อจำกัดโอกาส (chance constraints) หรือแนวทางที่อิงตามสถานการณ์ (scenario-based approaches)) หรือการหาค่าที่เหมาะสมที่สุดแบบทนทาน (robust multi-objective optimization) ซึ่งเป็นวิธีการที่แยกต่างหาก

MOLP เหมือนกับการหาค่าที่เหมาะสมที่สุดหลายวัตถุประสงค์ (multi-objective optimization) หรือไม่?

MOLP เป็นกรณีพิเศษของการหาค่าที่เหมาะสมที่สุดหลายวัตถุประสงค์ ซึ่งวัตถุประสงค์และข้อจำกัดทั้งหมดเป็นเชิงเส้น การหาค่าที่เหมาะสมที่สุดหลายวัตถุประสงค์เป็นสาขาที่กว้างกว่า ซึ่งรวมถึงรูปแบบที่ไม่เป็นเชิงเส้น แบบจำนวนเต็ม และแบบผสม (combinatorial) ด้วย

ควรใช้วิธีการแปลงสเกลาร์ (scalarization method) แบบใด?

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

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

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

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN: 9780471888468
    คัดลอกแล้ว
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว