การโปรแกรมเชิงเส้นหลายวัตถุประสงค์ (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 และทางเลือกแบบโอเพนซอร์ส)
- การแลกเปลี่ยนผลประโยชน์มีความชัดเจน แทนที่จะถูกรวมเข้าเป็นดัชนีที่ซับซ้อนและไม่โปร่งใส
การประยุกต์ใช้
- การวางแผนการผลิตที่สมดุลระหว่างต้นทุน ปริมาณงาน และการใช้ทรัพยากร
- การปรับพอร์ตการลงทุนโดยการแลกเปลี่ยนผลตอบแทน ความเสี่ยง และสภาพคล่อง
- การออกแบบเครือข่ายการขนส่งและโลจิสติกส์ที่มีวัตถุประสงค์ด้านต้นทุนและการบริการที่แข่งขันกัน
- การวางแผนระบบพลังงานที่ลดต้นทุนพร้อมๆ กับการบรรลุเป้าหมายด้านการปล่อยมลพิษและความน่าเชื่อถือ
- การจัดสรรทรัพยากรด้านสุขภาพที่สมดุลระหว่างความเท่าเทียม ประสิทธิภาพ และข้อจำกัดด้านงบประมาณ
- การจัดการสิ่งแวดล้อมที่ปรับปรุงประสิทธิภาพทางเศรษฐกิจและระบบนิเวศไปพร้อมๆ กัน
วิธีการทำงาน
วิธีการทำงาน
กำหนดฟังก์ชันวัตถุประสงค์เชิงเส้น 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สร้างชุดคำตอบที่มีประสิทธิภาพแบบพาเรโต (non-dominated solutions) วิธีการทั่วไป ได้แก่ วิธีผลรวมถ่วงน้ำหนัก (weighted-sum method) โดยการปรับน้ำหนักต่างๆ ในซิมเพล็กซ์ วิธีอิงข้อจำกัดเอปไซลอน (epsilon-constraint method) โดยการหาค่าที่เหมาะสมที่สุดของวัตถุประสงค์หนึ่งขณะจำกัดขอบเขตของวัตถุประสงค์อื่น และวิธีเชบิเชฟ (Chebyshev method) แต่ละวิธีจะติดตามส่วนหนึ่งหรือทั้งหมดของเส้นขอบฟ้าที่มีประสิทธิภาพ
ใช้เทคนิคการแปลงสเกลาร์ (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รวบรวมจุดยอดที่มีประสิทธิภาพและเส้นเชื่อมต่อเพื่ออธิบายลักษณะของเส้นขอบฟ้าพาเรโต วิเคราะห์ช่วงของแต่ละวัตถุประสงค์ตลอดเส้นขอบฟ้าเพื่อทำความเข้าใจขนาดของการแลกเปลี่ยนผลประโยชน์ นำเสนอเส้นขอบฟ้าแก่ผู้มีอำนาจตัดสินใจผ่านตารางหรือกราฟสองวัตถุประสงค์
ให้ผู้มีอำนาจตัดสินใจมีส่วนร่วมในการเลือกคำตอบที่ต้องการจากชุดคำตอบที่มีประสิทธิภาพ วิธีการแบบโต้ตอบ (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) ของเส้นขอบฟ้า วิธีอิงข้อจำกัดเอปไซลอนสามารถครอบคลุมเส้นขอบฟ้าทั้งหมดได้ แม้ในกรณีที่เป็นบริเวณที่ไม่เป็นนูน และโดยทั่วไปจะแนะนำสำหรับการวิเคราะห์ที่ละเอียด วิธีการแบบโต้ตอบจะดีที่สุดเมื่อผู้มีอำนาจตัดสินใจสามารถมีส่วนร่วมได้
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.
ISBN: 9780471888468คัดลอกแล้วChankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว